fix idhash not public

We accidentally made idhash not public by not publishing its header
in the right place.  This is really generic utility stuff, so we
have posted it in the nng/supplemental/util/ directory.

We've also removed the ability to remove this -- its a very small amount
of additional code, as its just a wrapper on top of mandatory functionality.

3 files changed, 378 insertions, 3 deletions

diff --git a/src/supplemental/util/CMakeLists.txt b/src/supplemental/util/CMakeLists.txt
index 5a144da9..f62026fb 100644
--- a/src/supplemental/util/CMakeLists.txt
+++ b/src/supplemental/util/CMakeLists.txt
@@ -1,5 +1,5 @@
 #
-# Copyright 2019 Staysail Systems, Inc. <info@staysail.tech>
+# Copyright 2024 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
@@ -7,5 +7,9 @@
 # found online at https://opensource.org/licenses/MIT.
 #
 
-nng_sources(options.c platform.c)
-nng_headers(nng/supplemental/util/options.h nng/supplemental/util/platform.h)
+nng_sources(idhash.c options.c platform.c)
+nng_headers(
+	nng/supplemental/util/idhash.h
+	nng/supplemental/util/options.h
+	nng/supplemental/util/platform.h)
+nng_test(idhash_test)
diff --git a/src/supplemental/util/idhash.c b/src/supplemental/util/idhash.c
new file mode 100644
index 00000000..cf48df3e
--- /dev/null
+++ b/src/supplemental/util/idhash.c
@@ -0,0 +1,62 @@
+//
+// Copyright 2024 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 <nng/nng.h>
+#include <nng/supplemental/util/idhash.h>
+
+#include "core/nng_impl.h"
+
+struct nng_id_map_s {
+	nni_id_map m;
+};
+
+int
+nng_id_map_alloc(nng_id_map **map, uint64_t lo, uint64_t hi, int flags)
+{
+	nng_id_map *m;
+
+	if ((m = NNI_ALLOC_STRUCT(m)) == NULL) {
+		return (NNG_ENOMEM);
+	}
+	nni_id_map_init(
+	    &m->m, lo, hi, (flags & NNG_MAP_RANDOM) ? true : false);
+	*map = m;
+	return (0);
+}
+
+void
+nng_id_map_free(nng_id_map *map)
+{
+	nni_id_map_fini(&map->m);
+	NNI_FREE_STRUCT(map);
+}
+
+void *
+nng_id_get(nng_id_map *map, uint64_t id)
+{
+	return (nni_id_get(&map->m, id));
+}
+
+int
+nng_id_set(nng_id_map *map, uint64_t id, void *val)
+{
+	return (nni_id_set(&map->m, id, val));
+}
+
+int
+nng_id_remove(nng_id_map *map, uint64_t id)
+{
+	return (nni_id_remove(&map->m, id));
+}
+
+int
+nng_id_alloc(nng_id_map *map, uint64_t *id, void *val)
+{
+	return (nni_id_alloc(&map->m, id, val));
+}
diff --git a/src/supplemental/util/idhash_test.c b/src/supplemental/util/idhash_test.c
new file mode 100644
index 00000000..5bbdc4fb
--- /dev/null
+++ b/src/supplemental/util/idhash_test.c
@@ -0,0 +1,309 @@
+//
+// Copyright 2024 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 <nuts.h>
+
+#include <nng/supplemental/util/idhash.h>
+
+void
+test_id_basic(void)
+{
+	nng_id_map *m;
+	char       *five = "five";
+	char       *four = "four";
+
+	NUTS_PASS(nng_id_map_alloc(&m, 0, 0, 0));
+
+	// insert it
+	NUTS_PASS(nng_id_set(m, 5, five));
+	// retrieve it
+	NUTS_TRUE(nng_id_get(m, 5) == five);
+
+	// change it
+	NUTS_PASS(nng_id_set(m, 5, four));
+	NUTS_TRUE(nng_id_get(m, 5) == four);
+
+	// delete
+	NUTS_PASS(nng_id_remove(m, 5));
+
+	nng_id_map_free(m);
+}
+
+void
+test_id_random(void)
+{
+	int      i;
+	uint64_t id;
+	for (i = 0; i < 2; i++) {
+		nng_id_map *m;
+		NUTS_PASS(nng_id_map_alloc(&m, 0, 0, NNG_MAP_RANDOM));
+		NUTS_PASS(nng_id_alloc(m, &id, &id));
+		nng_id_map_free(m);
+		NUTS_TRUE(id != 0);
+		if (id != 1) {
+			break;
+		}
+		// one chance in 4 billion, but try again
+	}
+
+	NUTS_TRUE(id != 1);
+	NUTS_TRUE(i < 2);
+}
+
+void
+test_id_collision(void)
+{
+	nng_id_map *m;
+	char       *five = "five";
+	char       *four = "four";
+
+	NUTS_PASS(nng_id_map_alloc(&m, 0, 0, 0));
+
+	// Carefully crafted -- 13 % 8 == 5.
+	NUTS_PASS(nng_id_set(m, 5, five));
+	NUTS_PASS(nng_id_set(m, 13, four));
+	NUTS_TRUE(nng_id_get(m, 5) == five);
+	NUTS_TRUE(nng_id_get(m, 13) == four);
+
+	// Delete the intermediate
+	NUTS_PASS(nng_id_remove(m, 5));
+	NUTS_TRUE(nng_id_get(m, 13) == four);
+
+	nng_id_map_free(m);
+}
+
+void
+test_id_empty(void)
+{
+	nng_id_map *m;
+
+	NUTS_PASS(nng_id_map_alloc(&m, 0, 0, 0));
+
+	NUTS_TRUE(nng_id_get(m, 42) == NULL);
+	NUTS_FAIL(nng_id_remove(m, 42), NNG_ENOENT);
+	NUTS_FAIL(nng_id_remove(m, 1), NNG_ENOENT);
+	nng_id_map_free(m);
+}
+
+void
+test_id_not_found(void)
+{
+	nng_id_map *m;
+	uint64_t    id;
+
+	NUTS_PASS(nng_id_map_alloc(&m, 0, 0, 0));
+
+	NUTS_PASS(nng_id_alloc(m, &id, &id));
+	NUTS_FAIL(nng_id_remove(m, 42), NNG_ENOENT);
+	NUTS_FAIL(nng_id_remove(m, 2), NNG_ENOENT);
+	NUTS_PASS(nng_id_remove(m, id));
+	nng_id_map_free(m);
+}
+
+void
+test_id_resize(void)
+{
+	nng_id_map *m;
+	int         rv;
+	int         i;
+	int         expect[1024];
+
+	for (i = 0; i < 1024; i++) {
+		expect[i] = i;
+	}
+
+	NUTS_PASS(nng_id_map_alloc(&m, 0, 0, 0));
+
+	for (i = 0; i < 1024; i++) {
+		if ((rv = nng_id_set(m, i, &expect[i])) != 0) {
+			NUTS_PASS(rv);
+		}
+	}
+
+	for (i = 0; i < 1024; i++) {
+		if ((rv = nng_id_remove(m, i)) != 0) {
+			NUTS_PASS(rv);
+		}
+	}
+	nng_id_map_free(m);
+}
+
+void
+test_id_dynamic(void)
+{
+	nng_id_map *m;
+	int         expect[5];
+	uint64_t    id;
+
+	NUTS_PASS(nng_id_map_alloc(&m, 10, 13, 0));
+
+	// We can fill the table.
+	NUTS_PASS(nng_id_alloc(m, &id, &expect[0]));
+	NUTS_TRUE(id == 10);
+	NUTS_PASS(nng_id_alloc(m, &id, &expect[1]));
+	NUTS_TRUE(id == 11);
+	NUTS_PASS(nng_id_alloc(m, &id, &expect[2]));
+	NUTS_TRUE(id == 12);
+	NUTS_PASS(nng_id_alloc(m, &id, &expect[3]));
+	NUTS_TRUE(id == 13);
+
+	// Adding another fails.
+	NUTS_FAIL(nng_id_alloc(m, &id, &expect[4]), NNG_ENOMEM);
+
+	// Delete one.
+	NUTS_PASS(nng_id_remove(m, 11));
+
+	// And now we can allocate one.
+	NUTS_PASS(nng_id_alloc(m, &id, &expect[4]));
+	NUTS_TRUE(id == 11);
+	nng_id_map_free(m);
+}
+
+void
+test_id_set_out_of_range(void)
+{
+	nng_id_map *m;
+	int         x;
+	uint64_t    id;
+
+	NUTS_PASS(nng_id_map_alloc(&m, 10, 13, 0));
+
+	// We can insert outside the range forcibly.
+	NUTS_PASS(nng_id_set(m, 1, &x));
+	NUTS_PASS(nng_id_set(m, 100, &x));
+	NUTS_PASS(nng_id_alloc(m, &id, &x));
+	NUTS_TRUE(id == 10);
+	nng_id_map_free(m);
+}
+
+#define STRESS_LOAD 50000
+#define NUM_VALUES 1000
+
+void
+test_id_stress(void)
+{
+	void       *values[NUM_VALUES];
+	nng_id_map *m;
+	size_t      i;
+	int         rv;
+	void       *x;
+	int         v;
+
+	NUTS_PASS(nng_id_map_alloc(&m, 0, 0, 0));
+	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 = nng_id_set(m, v, x)) != 0) {
+				NUTS_PASS(rv);
+				goto out;
+			}
+			break;
+
+		case 1:
+			rv = nng_id_remove(m, v);
+			if (values[v] == NULL) {
+				if (rv != NNG_ENOENT) {
+					NUTS_FAIL(rv, NNG_ENOENT);
+					goto out;
+				}
+			} else {
+				values[v] = NULL;
+				if (rv != 0) {
+					NUTS_PASS(rv);
+					goto out;
+				}
+			}
+			break;
+		case 2:
+			x = nng_id_get(m, v);
+			if (x != values[v]) {
+				NUTS_TRUE(x == values[v]);
+				goto out;
+			}
+			break;
+		}
+	}
+out:
+	NUTS_TRUE(i == STRESS_LOAD);
+
+	// Post stress check.
+	for (i = 0; i < NUM_VALUES; i++) {
+		x = nng_id_get(m, (uint32_t) i);
+		if (x != values[i]) {
+			NUTS_TRUE(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 = nng_id_remove(m, (uint32_t) i);
+		if ((x == NULL) && (rv != NNG_ENOENT)) {
+			NUTS_FAIL(rv, NNG_ENOENT);
+		} else if ((x != NULL) && (rv != 0)) {
+			NUTS_PASS(rv);
+		}
+	}
+	NUTS_TRUE(i == NUM_VALUES);
+
+	nng_id_map_free(m);
+}
+
+void
+test_id_alloc_long_long(void)
+{
+#define TEST_IDS 100
+	nng_id_map *m;
+	int         x;
+	uint64_t    ids[TEST_IDS];
+
+	NUTS_PASS(nng_id_map_alloc(&m, 1ULL << 32, (int64_t) -1, 0));
+
+	// We can insert outside the range forcibly - making sure we are
+	// choosing numbers above 64 bits.
+	for (int i = 0; i < TEST_IDS; i++) {
+		NUTS_PASS(nng_id_alloc(m, &ids[i], &x));
+		NUTS_ASSERT(ids[i] > 0xFFFFFFFFULL);
+	}
+	for (int i = 0; i < TEST_IDS; i++) {
+		bool matched = false;
+		for (int j = 0; j < i; j++) {
+			// only dump the assertion on failure
+			// otherwise it is too noisy
+			if (ids[i] == ids[j]) {
+				matched = true;
+				break;
+			}
+		}
+		NUTS_ASSERT(!matched);
+	}
+	nng_id_map_free(m);
+#undef TEST_IDS
+}
+
+NUTS_TESTS = {
+	{ "id basic", test_id_basic },
+	{ "id random", test_id_random },
+	{ "id collision", test_id_collision },
+	{ "id empty", test_id_empty },
+	{ "not found", test_id_not_found },
+	{ "id resize", test_id_resize },
+	{ "id dynamic", test_id_dynamic },
+	{ "id set out of range", test_id_set_out_of_range },
+	{ "id stress", test_id_stress },
+	{ "id alloc long long", test_id_alloc_long_long },
+	{ NULL, NULL },
+};