Richer tests and fixes for idhash. Also dynamically allocate idhash.

3 files changed, 85 insertions, 41 deletions

diff --git a/src/core/idhash.c b/src/core/idhash.c
index 050ba4fb..abd04e7e 100644
--- a/src/core/idhash.c
+++ b/src/core/idhash.c
@@ -11,33 +11,59 @@
 
 #include <string.h>
 
+typedef struct {
+	uint32_t	ihe_key;
+	uint32_t	ihe_skips;
+	void *		ihe_val;
+} nni_idhash_entry;
+
+struct nni_idhash {
+	uint32_t		ih_cap;
+	uint32_t		ih_count;
+	uint32_t		ih_load;
+	uint32_t		ih_minload; // considers placeholders
+	uint32_t		ih_maxload;
+	uint32_t		ih_walkers;
+	nni_idhash_entry *	ih_entries;
+};
+
 int
-nni_idhash_init(nni_idhash *h)
+nni_idhash_create(nni_idhash **hp)
 {
+	nni_idhash *h;
+
+	if ((h = nni_alloc(sizeof (*h))) == NULL) {
+		return (NNG_ENOMEM);
+	}
 	h->ih_entries = nni_alloc(8 * sizeof (nni_idhash_entry));
 	if (h->ih_entries == NULL) {
+		nni_free(h, sizeof (*h));
 		return (NNG_ENOMEM);
 	}
 	(void) memset(h->ih_entries, 0, (8 * sizeof (nni_idhash_entry)));
 	h->ih_count = 0;
+	h->ih_load = 0;
 	h->ih_cap = 8;
-	h->ih_maxcount = 5;
-	h->ih_mincount = 0; // never shrink below this
+	h->ih_maxload = 5;
+	h->ih_minload = 0; // never shrink below this
+	h->ih_walkers = 0;
+	*hp = h;
 	return (0);
 }
 
 
 void
-nni_idhash_fini(nni_idhash *h)
+nni_idhash_destroy(nni_idhash *h)
 {
 	nni_free(h->ih_entries, h->ih_cap * sizeof (nni_idhash_entry));
+	nni_free(h, sizeof (*h));
 }
 
 
 // Inspired by Python dict implementation.  This probe will visit every
 // cell.  We always hash consecutively assigned IDs.
 #define NNI_IDHASH_NEXTPROBE(h, j) \
-	((((j) * 5) + 1) & ~(h->ih_cap))
+	((((j) * 5) + 1) & (h->ih_cap - 1))
 
 int
 nni_idhash_find(nni_idhash *h, uint32_t id, void **valp)
@@ -45,7 +71,8 @@ nni_idhash_find(nni_idhash *h, uint32_t id, void **valp)
 	uint32_t index = id & (h->ih_cap - 1);
 
 	for (;;) {
-		if (h->ih_entries[index].ihe_val == NULL) {
+		if ((h->ih_entries[index].ihe_val == NULL) &&
+		    (h->ih_entries[index].ihe_skips == 0)) {
 			return (NNG_ENOENT);
 		}
 		if (h->ih_entries[index].ihe_key == id) {
@@ -65,10 +92,15 @@ nni_hash_resize(nni_idhash *h)
 	nni_idhash_entry *newents;
 	nni_idhash_entry *oldents;
 
-	if ((h->ih_count < h->ih_maxcount) && (h->ih_count >= h->ih_mincount)) {
+	if ((h->ih_load < h->ih_maxload) && (h->ih_load >= h->ih_minload)) {
 		// No resize needed.
 		return (0);
 	}
+	if (h->ih_walkers && (h->ih_load < (h->ih_cap-1))) {
+		// Don't resize when walkers are running.  This way
+		// walk functions can remove hash nodes.
+		return (0);
+	}
 
 	oldsize = h->ih_cap;
 	newsize = h->ih_cap;
@@ -83,14 +115,16 @@ nni_hash_resize(nni_idhash *h)
 	if (newents == NULL) {
 		return (NNG_ENOMEM);
 	}
+	memset(newents, 0, sizeof (nni_idhash_entry) * newsize);
+
 	h->ih_entries = newents;
 	h->ih_cap = newsize;
 	if (newsize > 8) {
-		h->ih_mincount = newsize / 8;
-		h->ih_maxcount = newsize * 2 / 3;
+		h->ih_minload = newsize / 8;
+		h->ih_maxload = newsize * 2 / 3;
 	} else {
-		h->ih_mincount = 0;
-		h->ih_maxcount = 5;
+		h->ih_minload = 0;
+		h->ih_maxload = 5;
 	}
 	for (int i = 0; i < oldsize; i++) {
 		uint32_t index;
@@ -100,10 +134,12 @@ nni_hash_resize(nni_idhash *h)
 		index = oldents[i].ihe_key & (newsize - 1);
 		for (;;) {
 			if (newents[index].ihe_val == NULL) {
+				h->ih_load++;
 				newents[index].ihe_val = oldents[i].ihe_val;
 				newents[index].ihe_key = oldents[i].ihe_key;
 				break;
 			}
+			newents[index].ihe_skips++;
 			index = NNI_IDHASH_NEXTPROBE(h, index);
 		}
 	}
@@ -115,18 +151,36 @@ nni_hash_resize(nni_idhash *h)
 int
 nni_idhash_remove(nni_idhash *h, uint32_t id)
 {
-	uint32_t index = id & (h->ih_cap - 1);
+	int rv;
+	void *val;
+	uint32_t index;
+
+	// First check that it is in the table.  This may double the
+	// lookup time, but it means that if we get past this then we KNOW
+	// we are going to delete an element.
+	if ((rv = nni_idhash_find(h, id, &val)) != 0) {
+		return (rv);
+	}
+
+	index = id & (h->ih_cap - 1);
 
 	for (;;) {
-		if (h->ih_entries[index].ihe_val == NULL) {
-			return (NNG_ENOENT);
-		}
-		if (h->ih_entries[index].ihe_key == id) {
-			h->ih_entries[index].ihe_val = NULL;
-			h->ih_entries[index].ihe_key = 0;
+		nni_idhash_entry *ent = &h->ih_entries[index];
+		if (ent->ihe_key == id) {
+			ent->ihe_val = NULL;
+			if (ent->ihe_skips == 0) {
+				h->ih_load--;
+			}
 			h->ih_count--;
 			break;
 		}
+		if (ent->ihe_skips < 1) {
+			nni_panic("Skips should be nonzero!");
+		}
+		ent->ihe_skips--;
+		if ((ent->ihe_skips == 0) && (ent->ihe_val == NULL)) {
+			h->ih_load--;
+		}
 		index = NNI_IDHASH_NEXTPROBE(h, index);
 	}
 
@@ -149,15 +203,17 @@ nni_idhash_insert(nni_idhash *h, uint32_t id, void *val)
 	}
 	index = id & (h->ih_cap - 1);
 	for (;;) {
-		if ((h->ih_entries[index].ihe_val == NULL) ||
-		    (h->ih_entries[index].ihe_key == id)) {
-			if (h->ih_entries[index].ihe_val == NULL) {
+		nni_idhash_entry *ent = &h->ih_entries[index];
+		if ((ent->ihe_val == NULL) || (ent->ihe_key == id)) {
+			if (ent->ihe_val == NULL) {
 				h->ih_count++;
+				h->ih_load++;
 			}
-			h->ih_entries[index].ihe_key = id;
-			h->ih_entries[index].ihe_val = val;
+			ent->ihe_key = id;
+			ent->ihe_val = val;
 			return (0);
 		}
+		ent->ihe_skips++;
 		index = NNI_IDHASH_NEXTPROBE(h, index);
 	}
 }
diff --git a/src/core/idhash.h b/src/core/idhash.h
index ffc60858..bfd0f595 100644
--- a/src/core/idhash.h
+++ b/src/core/idhash.h
@@ -23,20 +23,7 @@
 // must be non-NULL.  The caller is responsible for providing any
 // locking required.
 
-// In order to make life easy, we just define the ID hash structure
-// directly, and let consumers directly inline it.
-typedef struct {
-	uint32_t	ihe_key;
-	void *		ihe_val;
-} nni_idhash_entry;
-
-typedef struct {
-	uint32_t		ih_cap;
-	uint32_t		ih_count;
-	uint32_t		ih_mincount;
-	uint32_t		ih_maxcount;
-	nni_idhash_entry *	ih_entries;
-} nni_idhash;
+typedef struct nni_idhash   nni_idhash;
 
 // nni_idhash_walkfn is called when walking a hash table.  If the
 // return value is non-zero, then nni_idhash_walk will terminate further
@@ -44,8 +31,8 @@ typedef struct {
 // 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.
 typedef int (*nni_idhash_walkfn)(void *, uint32_t, void *);
-extern int nni_idhash_init(nni_idhash *);
-extern void nni_idhash_fini(nni_idhash *);
+extern int nni_idhash_create(nni_idhash **);
+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 *);
diff --git a/src/core/options.h b/src/core/options.h
index 7319bdf4..ec5d28f1 100644
--- a/src/core/options.h
+++ b/src/core/options.h
@@ -30,8 +30,9 @@ extern int nni_getopt_duration(nni_duration *, void *, size_t *);
 // nni_setopt_int sets an integer, which must be between the minimum and
 // maximum values (inclusive).
 extern int nni_setopt_int(int *, const void *, size_t, int, int);
-#define NNI_MAXINT ((int)2147483647)
-#define	NNI_MININT ((int)-2147483648)
+
+#define NNI_MAXINT	((int) 2147483647)
+#define NNI_MININT	((int) -2147483648)
 
 // nni_getopt_int gets an integer.
 extern int nni_getopt_int(int *, void *, size_t *);