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.

6 files changed, 89 insertions, 3 deletions

diff --git a/docs/man/nng_id_map.3supp.adoc b/docs/man/nng_id_map.3supp.adoc
index 343c0667..5bebf1c4 100644
--- a/docs/man/nng_id_map.3supp.adoc
+++ b/docs/man/nng_id_map.3supp.adoc
@@ -29,6 +29,7 @@ void *nng_id_get(nng_id_map *map, uint64_t id);
 int   nng_id_set(nng_id_map *map, uint64_t, void *value);
 int   nng_id_alloc(nng_id_map *map, uint64_t *id_p, void *value);
 int   nng_id_remove(nng_id_map *map, uint64_t id);
+bool  nng_id_visit(nng_id_map *map, uint64_t *id_p, void **value_p, uint32_t *cursor);
 
 ----
 
@@ -74,6 +75,13 @@ the supplied _value_.
 
 The `nng_id_remove()` function removes the identifier and its associated value from the table.
 
+The `nng_id_visit()` function is used to iterate over all items in the table.
+The caller starts the iteration by setting the _cursor_ to 0 before calling it.
+For each call, the associated key and value of the next item will be returned in __id_p__, and __value_p__ and the _cursor_ will be updated.
+When all items have been iterated, the function returns `false`.
+The order of items returned is not guaranteed to be sequential.
+The caller must not attempt to derive any value of the _cursor_ as it refers to internal table indices.
+
 NOTE: These functions are limited to storing at most 2^32^ identifiers, even though the identifers may
 themselves be larger than 2^32^.
 
diff --git a/include/nng/supplemental/util/idhash.h b/include/nng/supplemental/util/idhash.h
index 8f691d08..f231a554 100644
--- a/include/nng/supplemental/util/idhash.h
+++ b/include/nng/supplemental/util/idhash.h
@@ -27,6 +27,7 @@ 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);
+NNG_DECL bool  nng_id_visit(nng_id_map *, uint64_t *, void **, uint32_t *);
 
 #ifdef __cplusplus
 }
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 },