idhash: add nng_id_visit API

This allows an efficient way to iterate over the entries
stored in an ID hash. The iteration is fast, and requires no
additional storage.  The order of iteration is not guaranteed.

4 files changed, 80 insertions, 3 deletions

diff --git a/src/core/idhash.c b/src/core/idhash.c
index 67ae67ea..306c751f 100644
--- a/src/core/idhash.c
+++ b/src/core/idhash.c
@@ -1,5 +1,5 @@
 //
-// Copyright 2023 Staysail Systems, Inc. <info@staysail.tech>
+// Copyright 2024 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
@@ -366,4 +366,26 @@ nni_id_alloc32(nni_id_map *m, uint32_t *idp, void *val)
 	NNI_ASSERT(id < (1ULL << 32));
 	*idp = (uint32_t) id;
 	return (rv);
-}
\ No newline at end of file
+}
+
+bool
+nni_id_visit(nni_id_map *m, uint64_t *keyp, void **valp, uint32_t *cursor)
+{
+	// cursor is just a cursor into the table
+	uint32_t index = *cursor;
+	while (index < m->id_cap) {
+		if (m->id_entries[index].val != NULL) {
+			if (valp != NULL) {
+				*valp = m->id_entries[index].val;
+			}
+			if (keyp != NULL) {
+				*keyp = m->id_entries[index].key;
+			}
+			*cursor = index + 1;
+			return true;
+		}
+		index++;
+	}
+	*cursor = index;
+	return (false);
+}
diff --git a/src/core/idhash.h b/src/core/idhash.h
index b2c07062..11cc7a08 100644
--- a/src/core/idhash.h
+++ b/src/core/idhash.h
@@ -1,5 +1,5 @@
 //
-// Copyright 2023 Staysail Systems, Inc. <info@staysail.tech>
+// Copyright 2024 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
@@ -54,6 +54,7 @@ extern int   nni_id_alloc(nni_id_map *, uint64_t *, void *);
 extern int   nni_id_alloc32(nni_id_map *, uint32_t *, void *);
 extern int   nni_id_remove(nni_id_map *, uint64_t);
 extern void  nni_id_map_sys_fini(void);
+extern bool  nni_id_visit(nni_id_map *, uint64_t *, void **, uint32_t *);
 
 #define NNI_ID_MAP_INITIALIZER(min, max, flags)            \
 	{                                                  \
diff --git a/src/supplemental/util/idhash.c b/src/supplemental/util/idhash.c
index cf48df3e..4ededa31 100644
--- a/src/supplemental/util/idhash.c
+++ b/src/supplemental/util/idhash.c
@@ -60,3 +60,9 @@ nng_id_alloc(nng_id_map *map, uint64_t *id, void *val)
 {
 	return (nni_id_alloc(&map->m, id, val));
 }
+
+bool
+nng_id_visit(nng_id_map *map, uint64_t *id, void **valp, uint32_t *cursor)
+{
+	return (nni_id_visit(&map->m, id, valp, cursor));
+}
diff --git a/src/supplemental/util/idhash_test.c b/src/supplemental/util/idhash_test.c
index 5bbdc4fb..e0d472a0 100644
--- a/src/supplemental/util/idhash_test.c
+++ b/src/supplemental/util/idhash_test.c
@@ -182,6 +182,52 @@ test_id_set_out_of_range(void)
 	nng_id_map_free(m);
 }
 
+void
+test_id_visit(void)
+{
+	nng_id_map *m;
+	int         x, y;
+	uint64_t    id1;
+	uint64_t    id2;
+	int        *v1;
+	int        *v2;
+	uint32_t    cursor = 0;
+
+	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, &y));
+	NUTS_TRUE(nng_id_visit(m, &id1, (void **) &v1, &cursor));
+	NUTS_ASSERT(id1 == 1 || id1 == 100);
+	NUTS_ASSERT(v1 == &x || v1 == &y);
+	NUTS_TRUE(nng_id_visit(m, &id2, (void **) &v2, &cursor));
+	NUTS_ASSERT(id2 == 1 || id2 == 100);
+	NUTS_ASSERT(v2 == &x || v2 == &y);
+	NUTS_ASSERT(id1 != id2);
+	NUTS_ASSERT(v1 != v2);
+	NUTS_TRUE(!nng_id_visit(m, &id2, (void **) &v2, &cursor));
+	nng_id_map_free(m);
+}
+
+void
+test_id_visit_out_of_range(void)
+{
+	nng_id_map *m;
+	int         x, y;
+	uint64_t    id1;
+	int        *v1;
+	uint32_t    cursor = 1000;
+
+	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, &y));
+	NUTS_TRUE(!nng_id_visit(m, &id1, (void **) &v1, &cursor));
+	nng_id_map_free(m);
+}
+
 #define STRESS_LOAD 50000
 #define NUM_VALUES 1000
 
@@ -303,6 +349,8 @@ NUTS_TESTS = {
 	{ "id resize", test_id_resize },
 	{ "id dynamic", test_id_dynamic },
 	{ "id set out of range", test_id_set_out_of_range },
+	{ "id visit", test_id_visit },
+	{ "id visit out of range", test_id_visit_out_of_range },
 	{ "id stress", test_id_stress },
 	{ "id alloc long long", test_id_alloc_long_long },
 	{ NULL, NULL },