From eb3b131db73610274a41f04d8fd6b7cf879cc016 Mon Sep 17 00:00:00 2001
From: Garrett D'Amore <garrett@damore.org>
Date: Tue, 17 Jan 2017 16:55:25 -0800
Subject: 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.
---
 src/core/idhash.c | 65 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 src/core/idhash.h |  7 ++++--
 2 files changed, 70 insertions(+), 2 deletions(-)

(limited to 'src/core')

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,11 +51,27 @@ 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)
 {
@@ -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 *);
 
-- 
cgit v1.2.3-70-g09d2