fixes #1740 Public ID hash API

This includes a manual page documenting the entire set of
functions in one step.  The hash is 64-bit based for now, to
be maximally flexible.  An internal 32-bit convenience for the
common internal use is also provided (not public).

The public API includes a test suite.

5 files changed, 408 insertions, 0 deletions

diff --git a/src/supplemental/CMakeLists.txt b/src/supplemental/CMakeLists.txt
index 5be439b1..3fa254e7 100644
--- a/src/supplemental/CMakeLists.txt
+++ b/src/supplemental/CMakeLists.txt
@@ -11,6 +11,7 @@ nng_directory(supplemental)
 
 add_subdirectory(base64)
 add_subdirectory(http)
+add_subdirectory(idhash)
 add_subdirectory(sha1)
 add_subdirectory(tls)
 add_subdirectory(util)
diff --git a/src/supplemental/idhash/CMakeLists.txt b/src/supplemental/idhash/CMakeLists.txt
new file mode 100644
index 00000000..3a9bbb0b
--- /dev/null
+++ b/src/supplemental/idhash/CMakeLists.txt
@@ -0,0 +1,11 @@
+#
+# Copyright 2023 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.
+#
+
+nng_sources_if(NNG_SUPP_IDHASH idhash.c idhash.h)
+nng_test_if(NNG_SUPP_IDHASH idhash_test)
diff --git a/src/supplemental/idhash/idhash.c b/src/supplemental/idhash/idhash.c
new file mode 100644
index 00000000..051b686a
--- /dev/null
+++ b/src/supplemental/idhash/idhash.c
@@ -0,0 +1,60 @@
+//
+// Copyright 2023 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 "supplemental/idhash/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/idhash/idhash.h b/src/supplemental/idhash/idhash.h
new file mode 100644
index 00000000..5fd8f235
--- /dev/null
+++ b/src/supplemental/idhash/idhash.h
@@ -0,0 +1,27 @@
+//
+// Copyright 2023 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.
+//
+
+#ifndef NNG_SUPPLEMENTAL_IDHASH_IDHASH_H
+#define NNG_SUPPLEMENTAL_IDHASH_IDHASH_H
+
+#include <nng/nng.h>
+
+typedef struct nng_id_map_s nng_id_map;
+
+#define NNG_MAP_RANDOM 1
+
+NNG_DECL int nng_id_map_alloc(
+    nng_id_map **map, uint64_t lo, uint64_t hi, int flags);
+NNG_DECL void  nng_id_map_free(nng_id_map *map);
+NNG_DECL void *nng_id_get(nng_id_map *, uint64_t);
+NNG_DECL int   nng_id_set(nng_id_map *, uint64_t, void *);
+NNG_DECL int   nng_id_alloc(nng_id_map *, uint64_t *, void *);
+NNG_DECL int   nng_id_remove(nng_id_map *, uint64_t);
+
+#endif // NNG_SUPPLEMENTAL_IDHASH_IDHASH_H
diff --git a/src/supplemental/idhash/idhash_test.c b/src/supplemental/idhash/idhash_test.c
new file mode 100644
index 00000000..367f34bc
--- /dev/null
+++ b/src/supplemental/idhash/idhash_test.c
@@ -0,0 +1,309 @@
+//
+// Copyright 2023 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 "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 },
+};