fixes #1289 zerotier should have it's own copy of the id hashing code

fixes #1288 id allocation can overallocate
fixes #1126 consider removing lock from idhash

This substantially refactors the id hash code, giving a cleaner API,
and eliminating a extra locking as well as some wasteful allocations.

The ZeroTier code has it's own copy, that is 64-bit friendly, as the
rest of the consumers need only a simpler 32-bit API.

3 files changed, 276 insertions, 260 deletions

diff --git a/tests/CMakeLists.txt b/tests/CMakeLists.txt
index 90d674ff..d7842bfb 100644
--- a/tests/CMakeLists.txt
+++ b/tests/CMakeLists.txt
@@ -127,6 +127,7 @@ endif ()
 nng_test(aio)
 nng_test(bufsz)
 nng_test(bug1247)
+nng_test(id)
 nng_test(platform)
 nng_test(reconnect)
 nng_test(sock)
@@ -136,7 +137,6 @@ add_nng_test(errors 2)
 add_nng_test(files 5)
 add_nng_test1(httpclient 60 NNG_SUPP_HTTP)
 add_nng_test1(httpserver 30 NNG_SUPP_HTTP)
-add_nng_test(idhash 30)
 add_nng_test(inproc 5)
 add_nng_test(ipc 5)
 add_nng_test(ipcperms 5)
diff --git a/tests/id.c b/tests/id.c
new file mode 100644
index 00000000..e8944547
--- /dev/null
+++ b/tests/id.c
@@ -0,0 +1,275 @@
+//
+// Copyright 2020 Staysail Systems, Inc. <info@staysail.tech>
+//
+// This software is supplied under the terms of the MIT License, a
+// copy of which should be located in the distribution where this
+// file was obtained (LICENSE.txt).  A copy of the license may also be
+// found online at https://opensource.org/licenses/MIT.
+//
+
+#include "acutest.h"
+#include "testutil.h"
+
+#include "core/idhash.h"
+
+void
+test_basic(void)
+{
+	nni_id_map m;
+	char *     five = "five";
+	char *     four = "four";
+
+	nni_id_map_init(&m, 0, 0, false);
+
+	// insert it
+	TEST_NNG_PASS(nni_id_set(&m, 5, five));
+	// retrieve it
+	TEST_CHECK(nni_id_get(&m, 5) == five);
+
+	// change it
+	TEST_NNG_PASS(nni_id_set(&m, 5, four));
+	TEST_CHECK(nni_id_get(&m, 5) == four);
+
+	// delete
+	TEST_NNG_PASS(nni_id_remove(&m, 5));
+
+	nni_id_map_fini(&m);
+}
+
+void
+test_random(void)
+{
+	int      i;
+	uint32_t id;
+	for (i = 0; i < 2; i++) {
+		nni_id_map m;
+		nni_id_map_init(&m, 0, 0, true);
+		TEST_NNG_PASS(nni_id_alloc(&m, &id, &id));
+		nni_id_map_fini(&m);
+		TEST_CHECK(id != 0);
+		if (id != 1) {
+			break;
+		}
+		// one chance in 4 billion, but try again
+	}
+
+	TEST_CHECK(id != 1);
+	TEST_CHECK(i < 2);
+}
+
+void
+test_collision(void)
+{
+	nni_id_map m;
+	char *     five = "five";
+	char *     four = "four";
+
+	nni_id_map_init(&m, 0, 0, false);
+
+	// Carefully crafted -- 13 % 8 == 5.
+	TEST_NNG_PASS(nni_id_set(&m, 5, five));
+	TEST_NNG_PASS(nni_id_set(&m, 13, four));
+	TEST_CHECK(nni_id_get(&m, 5) == five);
+	TEST_CHECK(nni_id_get(&m, 13) == four);
+
+	// Delete the intermediate
+	TEST_NNG_PASS(nni_id_remove(&m, 5));
+	TEST_CHECK(nni_id_get(&m, 13) == four);
+
+	nni_id_map_fini(&m);
+}
+
+void
+test_empty(void)
+{
+	nni_id_map m;
+	nni_id_map_init(&m, 0, 0, false);
+
+	TEST_CHECK(nni_id_get(&m, 42) == NULL);
+	TEST_NNG_FAIL(nni_id_remove(&m, 42), NNG_ENOENT);
+	TEST_NNG_FAIL(nni_id_remove(&m, 1), NNG_ENOENT);
+	nni_id_map_fini(&m);
+}
+
+void
+test_not_found(void)
+{
+	nni_id_map m;
+	uint32_t   id;
+	nni_id_map_init(&m, 0, 0, false);
+
+	TEST_NNG_PASS(nni_id_alloc(&m, &id, &id));
+	TEST_NNG_FAIL(nni_id_remove(&m, 42), NNG_ENOENT);
+	TEST_NNG_FAIL(nni_id_remove(&m, 2), NNG_ENOENT);
+	TEST_NNG_PASS(nni_id_remove(&m, id));
+	nni_id_map_fini(&m);
+}
+
+void
+test_resize(void)
+{
+	nni_id_map m;
+	int        rv;
+	int        i;
+	int        expect[1024];
+
+	for (i = 0; i < 1024; i++) {
+		expect[i] = i;
+	}
+
+	nni_id_map_init(&m, 0, 0, false);
+
+	for (i = 0; i < 1024; i++) {
+		if ((rv = nni_id_set(&m, i, &expect[i])) != 0) {
+			TEST_NNG_PASS(rv);
+		}
+	}
+
+	for (i = 0; i < 1024; i++) {
+		if ((rv = nni_id_remove(&m, i)) != 0) {
+			TEST_NNG_PASS(rv);
+		}
+	}
+	nni_id_map_fini(&m);
+}
+
+void
+test_dynamic(void)
+{
+	nni_id_map m;
+	int        expect[5];
+	uint32_t   id;
+
+	nni_id_map_init(&m, 10, 13, false);
+
+        // We can fill the table.
+	TEST_NNG_PASS(nni_id_alloc(&m, &id, &expect[0]));
+	TEST_CHECK(id == 10);
+	TEST_NNG_PASS(nni_id_alloc(&m, &id, &expect[1]));
+	TEST_CHECK(id == 11);
+	TEST_NNG_PASS(nni_id_alloc(&m, &id, &expect[2]));
+	TEST_CHECK(id == 12);
+	TEST_NNG_PASS(nni_id_alloc(&m, &id, &expect[3]));
+	TEST_CHECK(id == 13);
+
+	// Adding another fails.
+	TEST_NNG_FAIL(nni_id_alloc(&m, &id, &expect[4]), NNG_ENOMEM);
+
+	// Delete one.
+	TEST_NNG_PASS(nni_id_remove(&m, 11));
+
+	// And now we can allocate one.
+	TEST_NNG_PASS(nni_id_alloc(&m, &id, &expect[4]));
+	TEST_CHECK(id == 11);
+	nni_id_map_fini(&m);
+}
+
+void
+test_set_out_of_range(void)
+{
+	nni_id_map m;
+	int        x;
+	uint32_t   id;
+
+	nni_id_map_init(&m, 10, 13, false);
+
+	// We can insert outside the range forcibly.
+	TEST_NNG_PASS(nni_id_set(&m, 1, &x));
+	TEST_NNG_PASS(nni_id_set(&m, 100, &x));
+	TEST_NNG_PASS(nni_id_alloc(&m, &id, &x));
+	TEST_CHECK(id == 10);
+	nni_id_map_fini(&m);
+}
+
+#define STRESS_LOAD 50000
+#define NUM_VALUES 1000
+
+void
+test_stress(void)
+{
+	void *     values[NUM_VALUES];
+	nni_id_map m;
+	size_t     i;
+	int        rv;
+	void *     x;
+	int        v;
+
+	nni_id_map_init(&m, 0, 0, false);
+	for (i = 0; i < NUM_VALUES; i++) {
+		values[i] = NULL;
+	}
+
+	for (i = 0; i < STRESS_LOAD; i++) {
+		v = rand() % NUM_VALUES; // Keep it constrained
+
+		switch (rand() & 3) {
+		case 0:
+			x         = &values[rand() % NUM_VALUES];
+			values[v] = x;
+			if ((rv = nni_id_set(&m, v, x)) != 0) {
+				TEST_NNG_PASS(rv);
+				goto out;
+			}
+			break;
+
+		case 1:
+			rv = nni_id_remove(&m, v);
+			if (values[v] == NULL) {
+				if (rv != NNG_ENOENT) {
+					TEST_NNG_FAIL(rv, NNG_ENOENT);
+					goto out;
+				}
+			} else {
+				values[v] = NULL;
+				if (rv != 0) {
+					TEST_NNG_PASS(rv);
+					goto out;
+				}
+			}
+			break;
+		case 2:
+			x = nni_id_get(&m, v);
+			if (x != values[v]) {
+				TEST_CHECK(x == values[v]);
+				goto out;
+			}
+			break;
+		}
+	}
+out:
+	TEST_CHECK(i == STRESS_LOAD);
+
+	// Post stress check.
+	for (i = 0; i < NUM_VALUES; i++) {
+		x = nni_id_get(&m, i);
+		if (x != values[i]) {
+			TEST_CHECK(x == values[i]);
+			break;
+		}
+
+		// We only use the test macros if we know they are going
+		// to fail.  Otherwise there will be too many errors reported.
+		rv = nni_id_remove(&m, i);
+		if ((x == NULL) && (rv != NNG_ENOENT)) {
+			TEST_NNG_FAIL(rv, NNG_ENOENT);
+		} else if ((x != NULL) && (rv != 0)) {
+			TEST_NNG_PASS(rv);
+		}
+	}
+	TEST_CHECK(i == NUM_VALUES);
+
+	nni_id_map_fini(&m);
+}
+
+TEST_LIST = {
+	{ "basic", test_basic },
+	{ "random", test_random },
+	{ "collision", test_collision },
+	{ "empty", test_empty },
+	{ "not found", test_not_found },
+	{ "resize", test_resize },
+	{ "dynamic", test_dynamic },
+	{ "set out of range", test_set_out_of_range },
+	{ "stress", test_stress },
+	{ NULL, NULL },
+};
diff --git a/tests/idhash.c b/tests/idhash.c
deleted file mode 100644
index 60a7133a..00000000
--- a/tests/idhash.c
+++ /dev/null
@@ -1,259 +0,0 @@
-//
-// Copyright 2018 Staysail Systems, Inc. <info@staysail.tech>
-// Copyright 2018 Capitar IT Group BV <info@capitar.com>
-//
-// This software is supplied under the terms of the MIT License, a
-// copy of which should be located in the distribution where this
-// file was obtained (LICENSE.txt).  A copy of the license may also be
-// found online at https://opensource.org/licenses/MIT.
-//
-
-#include "core/idhash.c"
-#include "core/nng_impl.h"
-
-#include "convey.h"
-
-#define STRESSLOAD 50000
-#define NVALUES 1000
-
-int
-stress(nni_idhash *h, void **values, size_t nvalues, int iter)
-{
-	for (int i = 0; i < iter; i++) {
-		void *x;
-		int   v = rand() % nvalues; // Keep it constrained
-
-		switch (rand() & 3) {
-		case 0:
-			x         = &values[rand() % nvalues];
-			values[v] = x;
-			if (nni_idhash_insert(h, v, x) != 0) {
-				return (-1);
-			}
-			break;
-
-		case 1:
-			if (values[v] == NULL) {
-				if (nni_idhash_remove(h, v) != NNG_ENOENT) {
-					return (-1);
-				} else {
-					break;
-				}
-			} else {
-				if (nni_idhash_remove(h, v) != 0) {
-					return (-1);
-				}
-				values[v] = NULL;
-			}
-			break;
-		case 2:
-			if (values[v] == NULL) {
-				if (nni_idhash_find(h, v, &x) != NNG_ENOENT) {
-					return (-1);
-				}
-
-			} else {
-				if ((nni_idhash_find(h, v, &x) != 0) ||
-				    (x != values[v])) {
-					return (-1);
-				}
-			}
-			break;
-		}
-	}
-	return (0);
-}
-
-int
-poststress(nni_idhash *h, void **values, size_t nvalues)
-{
-	for (size_t i = 0; i < nvalues; i++) {
-		void *x;
-		if (values[i] == NULL) {
-			if ((nni_idhash_find(h, i, &x) != NNG_ENOENT) ||
-			    (nni_idhash_remove(h, i) != NNG_ENOENT)) {
-				return (-1);
-			}
-			continue;
-		}
-		if (((nni_idhash_find(h, i, &x) != 0) || (x != values[i])) ||
-		    (nni_idhash_remove(h, i) != 0)) {
-			return (-1);
-		}
-	}
-	return (0);
-}
-
-Main({
-	nni_init();
-	atexit(nni_fini);
-	Test("General ID Hash", {
-		int rv;
-
-		Convey("Given an id hash", {
-			nni_idhash *h = NULL;
-
-			So(nni_idhash_init(&h) == 0);
-			So(h != NULL);
-
-			Reset({ nni_idhash_fini(h); });
-
-			Convey("We can insert an element", {
-				char *five = "five";
-				char *four = "four";
-				rv         = nni_idhash_insert(h, 5, five);
-				So(rv == 0);
-
-				Convey("And we can find it", {
-					void *ptr;
-					rv = nni_idhash_find(h, 5, &ptr);
-					So(rv == 0);
-					So(ptr == five);
-				});
-				Convey("We can delete it", {
-					void *ptr;
-					rv = nni_idhash_remove(h, 5);
-					So(rv == 0);
-					rv = nni_idhash_find(h, 5, &ptr);
-					So(rv == NNG_ENOENT);
-				});
-				Convey("We can change the value", {
-					void *ptr;
-					So(nni_idhash_insert(h, 5, four) == 0);
-					So(nni_idhash_find(h, 5, &ptr) == 0);
-					So(ptr == four);
-				});
-				Convey("We can insert a hash collision", {
-					void *ptr;
-					So(nni_idhash_insert(h, 13, four) ==
-					    0);
-					So(nni_idhash_find(h, 5, &ptr) == 0);
-					So(ptr == five);
-					So(nni_idhash_find(h, 13, &ptr) == 0);
-					So(ptr == four);
-					Convey("And delete intermediate", {
-						So(nni_idhash_remove(h, 5) ==
-						    0);
-						ptr = NULL;
-						So(nni_idhash_find(
-						       h, 13, &ptr) == 0);
-						So(ptr == four);
-					});
-				});
-			});
-			Convey("We cannot find bogus values", {
-				void *ptr;
-				ptr = NULL;
-				rv  = nni_idhash_find(h, 42, &ptr);
-				So(rv == NNG_ENOENT);
-				So(ptr == NULL);
-			});
-
-			Convey("64-bit hash values work", {
-				char *   huge    = "huge";
-				void *   ptr     = NULL;
-				uint64_t hugenum = 0x1234567890ULL;
-
-				nni_idhash_set_limits(h, 1, 1ULL << 63, 1);
-				So(nni_idhash_insert(h, hugenum, huge) == 0);
-				So(nni_idhash_find(h, hugenum, &ptr) == 0);
-				So((char *) ptr == huge);
-			});
-
-			Convey("64-bit dynvals work", {
-				char *   huge = "dynhuge";
-				void *   ptr  = NULL;
-				uint64_t id;
-
-				nni_idhash_set_limits(
-				    h, 1ULL << 32, 1ULL << 63, 1);
-				So(nni_idhash_alloc(h, &id, huge) == 0);
-				So(id > 0xffffffff);
-				So(nni_idhash_find(h, id, &ptr) == 0);
-				So((char *) ptr == huge);
-			});
-		});
-	});
-
-	Test("Resize ID Hash", {
-		int expect[1024];
-		int i;
-
-		for (i = 0; i < 1024; i++) {
-			expect[i] = i;
-		}
-		Convey("Given an id hash", {
-			nni_idhash *h;
-
-			So(nni_idhash_init(&h) == 0);
-
-			Reset({ nni_idhash_fini(h); });
-
-			Convey("We can insert 1024 items", {
-				for (i = 0; i < 1024; i++) {
-					nni_idhash_insert(h, i, &expect[i]);
-				}
-
-				Convey("We can remove them", {
-					for (i = 0; i < 1024; i++) {
-						nni_idhash_remove(h, i);
-					}
-				});
-			});
-		});
-	});
-
-	Test("Dynamic ID generation", {
-		Convey("Given a small ID hash", {
-			nni_idhash *h;
-			int         expect[5];
-			uint64_t    id;
-			So(nni_idhash_init(&h) == 0);
-			Reset({ nni_idhash_fini(h); });
-			nni_idhash_set_limits(h, 10, 13, 10);
-			So(1);
-			Convey("We can fill the table", {
-				for (uint64_t i = 0; i < 4; i++) {
-					So(nni_idhash_alloc(
-					       h, &id, &expect[i]) == 0);
-					So(id == (i + 10));
-				}
-				Convey("Adding another fails", {
-					So(nni_idhash_alloc(h, &id,
-					       &expect[5]) == NNG_ENOMEM);
-				});
-				Convey("Deleting one lets us reinsert", {
-					nni_idhash_remove(h, 11);
-					So(nni_idhash_alloc(
-					       h, &id, &expect[5]) == 0);
-					So(id == 11);
-				});
-			});
-			Convey("We can insert outside range forcibly", {
-				So(nni_idhash_insert(h, 1, &expect[0]) == 0);
-				So(nni_idhash_insert(h, 100, &expect[0]) == 0);
-				So(nni_idhash_alloc(h, &id, &expect[1]) == 0);
-				So(id >= 10);
-				So(id <= 13);
-			});
-		});
-	});
-
-	Test("Stress it", {
-		void *values[NVALUES];
-
-		Convey("Given a hash", {
-			nni_idhash *h;
-			So(nni_idhash_init(&h) == 0);
-			Reset({ nni_idhash_fini(h); });
-			memset(values, 0, sizeof(values));
-
-			Convey("A stress run works", {
-				So(stress(h, values, NVALUES, STRESSLOAD) ==
-				    0);
-				So(poststress(h, values, NVALUES) == 0);
-				So(nni_idhash_count(h) == 0);
-			});
-		});
-	});
-})