aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/core/idhash.c102
-rw-r--r--src/core/idhash.h19
-rw-r--r--src/core/options.h5
-rw-r--r--tests/idhash.c77
4 files changed, 131 insertions, 72 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 *);
diff --git a/tests/idhash.c b/tests/idhash.c
index de3f28f4..73e5f741 100644
--- a/tests/idhash.c
+++ b/tests/idhash.c
@@ -15,61 +15,76 @@ Main({
int rv;
Convey("Given an id hash", {
- nni_idhash h;
+ nni_idhash *h;
- rv = nni_idhash_init(&h);
+ rv = nni_idhash_create(&h);
So(rv == 0);
- So(h.ih_cap == 8);
- So(h.ih_entries != NULL);
- So(h.ih_count == 0);
+ So(h->ih_cap == 8);
+ So(h->ih_entries != NULL);
+ So(h->ih_count == 0);
Reset({
- nni_idhash_fini(&h);
+ nni_idhash_destroy(h);
})
Convey("We can insert an element", {
char *five = "five";
char *four = "four";
- rv = nni_idhash_insert(&h, 5, five);
+ rv = nni_idhash_insert(h, 5, five);
So(rv == 0);
+ So(h->ih_load == 1);
+ So(h->ih_count == 1);
+
Convey("And we can find it", {
void *ptr;
- rv = nni_idhash_find(&h, 5, &ptr);
+ rv = nni_idhash_find(h, 5, &ptr);
So(rv == 0);
So(ptr == five);
})
Convey("We can delete it", {
void *ptr;
- rv = nni_idhash_remove(&h, 5);
+ rv = nni_idhash_remove(h, 5);
So(rv == 0);
- rv = nni_idhash_find(&h, 5, &ptr);
+ rv = nni_idhash_find(h, 5, &ptr);
So(rv == NNG_ENOENT);
})
Convey("We can change the value", {
void *ptr;
- rv = nni_idhash_insert(&h, 5, four);
+ rv = nni_idhash_insert(h, 5, four);
So(rv == 0);
- So(h.ih_count == 1);
- rv = nni_idhash_find(&h, 5, &ptr);
+ So(h->ih_count == 1);
+ rv = nni_idhash_find(h, 5, &ptr);
So(rv == 0);
So(ptr == four);
})
Convey("We can insert a hash collision", {
void *ptr;
- rv = nni_idhash_insert(&h, 13, four);
- So(h.ih_count == 2);
- rv = nni_idhash_find(&h, 5, &ptr);
+ rv = nni_idhash_insert(h, 13, four);
+ So(rv == 0);
+ So(h->ih_load == 2);
+ So(h->ih_count == 2);
+ rv = nni_idhash_find(h, 5, &ptr);
So(rv == 0);
So(ptr == five);
- rv = nni_idhash_find(&h, 13, &ptr);
+ rv = nni_idhash_find(h, 13, &ptr);
So(rv == 0);
So(ptr == four);
+ So(h->ih_entries[5].ihe_skips == 1);
+ Convey("And delete the intermediate", {
+ rv = nni_idhash_remove(h, 5);
+ So(rv == 0);
+ ptr = NULL;
+ rv = nni_idhash_find(h, 13, &ptr);
+ So(rv == 0);
+ So(ptr == four);
+ So(h->ih_load == 2);
+ })
})
})
Convey("We cannot find bogus values", {
void *ptr = NULL;
- rv = nni_idhash_find(&h, 42, &ptr);
+ rv = nni_idhash_find(h, 42, &ptr);
So(rv == NNG_ENOENT);
So(ptr == NULL);
})
@@ -85,34 +100,34 @@ Main({
expect[i] = i;
}
Convey("Given an id hash", {
- nni_idhash h;
+ nni_idhash *h;
- rv = nni_idhash_init(&h);
+ rv = nni_idhash_create(&h);
So(rv == 0);
- So(h.ih_cap == 8);
- So(h.ih_entries != NULL);
- So(h.ih_count == 0);
+ So(h->ih_cap == 8);
+ So(h->ih_entries != NULL);
+ So(h->ih_count == 0);
Reset({
- nni_idhash_fini(&h);
+ nni_idhash_destroy(h);
})
Convey("We can insert 1024 items", {
uint32_t count;
for (int i = 0; i < 1024; i++) {
- nni_idhash_insert(&h, i, &expect[i]);
+ nni_idhash_insert(h, i, &expect[i]);
}
- So(nni_idhash_count(&h, &count) == 0);
+ So(nni_idhash_count(h, &count) == 0);
So(count == 1024);
- So(h.ih_cap = 2048);
- So(h.ih_count == 1024);
+ So(h->ih_cap = 2048);
+ So(h->ih_count == 1024);
Convey("We can remove them", {
for (int i = 0; i < 1024; i++) {
- nni_idhash_remove(&h, i);
+ nni_idhash_remove(h, i);
}
- So(h.ih_count == 0);
- So(h.ih_cap == 8);
+ So(h->ih_count == 0);
+ So(h->ih_cap == 8);
})
})
})
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2026-01-18 20:14:02 +0000