Added dynamic ID generation & management for idhash tables.

This will allow us to use idhash tables to manage id handles a bit more
flexibly.  For example, sockets, pipe IDs, etc. can all be generated, and
we can use hash tables to ensure that values do not collide.

3 files changed, 104 insertions, 3 deletions

diff --git a/src/core/idhash.c b/src/core/idhash.c
index e541ef36..40d134a5 100644
--- a/src/core/idhash.c
+++ b/src/core/idhash.c
@@ -24,6 +24,9 @@ struct nni_idhash {
 	uint32_t		ih_minload; // considers placeholders
 	uint32_t		ih_maxload;
 	uint32_t		ih_walkers;
+	uint32_t		ih_minval;
+	uint32_t		ih_maxval;
+	uint32_t		ih_dynval;
 	nni_idhash_entry *	ih_entries;
 };
 
@@ -31,6 +34,7 @@ int
 nni_idhash_create(nni_idhash **hp)
 {
 	nni_idhash *h;
+	int rv;
 
 	if ((h = NNI_ALLOC_STRUCT(h)) == NULL) {
 		return (NNG_ENOMEM);
@@ -47,12 +51,28 @@ nni_idhash_create(nni_idhash **hp)
 	h->ih_maxload = 5;
 	h->ih_minload = 0; // never shrink below this
 	h->ih_walkers = 0;
+	h->ih_minval = 0;
+	h->ih_maxval = 0xffffffff;
+	h->ih_dynval = 0;
 	*hp = h;
 	return (0);
 }
 
 
 void
+nni_idhash_set_limits(nni_idhash *h, uint32_t minval, uint32_t maxval,
+    uint32_t start)
+{
+	h->ih_minval = minval;
+	h->ih_maxval = maxval;
+	h->ih_dynval = start;
+	NNI_ASSERT(minval < maxval);
+	NNI_ASSERT(start >= minval);
+	NNI_ASSERT(start <= maxval);
+}
+
+
+void
 nni_idhash_destroy(nni_idhash *h)
 {
 	if (h != NULL) {
@@ -199,6 +219,10 @@ nni_idhash_insert(nni_idhash *h, uint32_t id, void *val)
 {
 	uint32_t index;
 
+	if ((id < h->ih_minval) || (id > h->ih_maxval)) {
+		return (NNG_EINVAL);
+	}
+
 	// Try to resize.  If we can't, but we still have room, go ahead
 	// and store it.
 	if ((nni_hash_resize(h) != 0) && (h->ih_count >= (h->ih_cap - 1))) {
@@ -219,6 +243,47 @@ nni_idhash_insert(nni_idhash *h, uint32_t id, void *val)
 		ent->ihe_skips++;
 		index = NNI_IDHASH_NEXTPROBE(h, index);
 	}
+
+	// If this was the old dynamic value, just bump it.
+	if (h->ih_dynval == id) {
+		h->ih_dynval++;
+		// Roll over...
+		if (h->ih_dynval == h->ih_maxval) {
+			h->ih_dynval = h->ih_minval;
+		}
+	}
+}
+
+
+int
+nni_idhash_alloc(nni_idhash *h, uint32_t *idp, void *val)
+{
+	uint32_t id, index;
+	void *scrap;
+	int rv;
+
+	if (h->ih_count > (h->ih_maxval - h->ih_minval)) {
+		// Really more like ENOSPC.. the table is filled to max.
+		return (NNG_ENOMEM);
+	}
+
+	for (;;) {
+		id = h->ih_dynval;
+		h->ih_dynval++;
+		if (h->ih_dynval > h->ih_maxval) {
+			h->ih_dynval = h->ih_minval;
+		}
+
+		if (nni_idhash_find(h, id, &scrap) == NNG_ENOENT) {
+			break;
+		}
+	}
+
+	rv = nni_idhash_insert(h, id, val);
+	if (rv == 0) {
+		*idp = id;
+	}
+	return (rv);
 }
 
 
diff --git a/src/core/idhash.h b/src/core/idhash.h
index bfd0f595..e8876ad5 100644
--- a/src/core/idhash.h
+++ b/src/core/idhash.h
@@ -20,8 +20,7 @@
 // we use a better probe (taken from Python) to avoid hitting the same
 // positions.  Our hash algorithm is just the low order bits, and we
 // use table sizes that are powers of two.  Note that hash items
-// must be non-NULL.  The caller is responsible for providing any
-// locking required.
+// must be non-NULL.  The table is locked.
 
 typedef struct nni_idhash   nni_idhash;
 
@@ -30,12 +29,16 @@ typedef struct nni_idhash   nni_idhash;
 // process and return that return value.  The function takes the generic
 // opaque value for the walk as its first argument, and the next two
 // arguments are the hash key and the opaque value stored with it.
+// Note that the walkfn must not attempt to change the hash table.
+// The user must provide any locking needed.
 typedef int (*nni_idhash_walkfn)(void *, uint32_t, void *);
 extern int nni_idhash_create(nni_idhash **);
+extern void nni_idhash_set_limits(nni_idhash *, uint32_t, uint32_t, uint32_t);
 extern void nni_idhash_destroy(nni_idhash *);
 extern int nni_idhash_find(nni_idhash *, uint32_t, void **);
 extern int nni_idhash_remove(nni_idhash *, uint32_t);
 extern int nni_idhash_insert(nni_idhash *, uint32_t, void *);
+extern int nni_idhash_alloc(nni_idhash *, uint32_t *, void *);
 extern int nni_idhash_count(nni_idhash *, uint32_t *);
 extern int nni_idhash_walk(nni_idhash *, nni_idhash_walkfn, void *);
 
diff --git a/tests/idhash.c b/tests/idhash.c
index fb240078..b05b4b2f 100644
--- a/tests/idhash.c
+++ b/tests/idhash.c
@@ -7,9 +7,9 @@
 // found online at https://opensource.org/licenses/MIT.
 //
 
-#include "core/idhash.c"
 #include "convey.h"
 #include "stubs.h"
+#include "core/idhash.c"
 
 Main({
 	Test("General ID Hash", {
@@ -133,4 +133,37 @@ Main({
 			})
 		})
 	})
+
+	Test("Dynamic ID generation", {
+		Convey("Given a small ID hash", {
+			nni_idhash *h;
+			int expect[5];
+			uint32_t id;
+			int i;
+			So(nni_idhash_create(&h) == 0);
+			Reset({
+				nni_idhash_destroy(h);
+			})
+			nni_idhash_set_limits(h, 10, 13, 10);
+			So(1);
+			Convey("We can fill the table", {
+				for (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 cannot insert bogus values", {
+				So(nni_idhash_insert(h, 1, &expect[0]) == NNG_EINVAL);
+				So(nni_idhash_insert(h, 100, &expect[0]) == NNG_EINVAL);
+			})
+		})
+	})
 })