aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/core/idhash.c119
-rw-r--r--tests/CMakeLists.txt2
-rw-r--r--tests/idhash.c90
3 files changed, 166 insertions, 45 deletions
diff --git a/src/core/idhash.c b/src/core/idhash.c
index 0ba9056c..17e80210 100644
--- a/src/core/idhash.c
+++ b/src/core/idhash.c
@@ -95,28 +95,39 @@ nni_idhash_set_limits(
#define NNI_IDHASH_INDEX(h, j) \
(((j & 0xffffffff) ^ (j >> 32)) & (h->ih_cap - 1))
-static int
-nni_hash_find(nni_idhash *h, uint64_t id, void **valp)
+static size_t
+nni_hash_find_index(nni_idhash *h, uint64_t id)
{
- uint32_t index = NNI_IDHASH_INDEX(h, id);
-
+ size_t index;
if (h->ih_count == 0) {
- return (NNG_ENOENT);
+ return ((size_t) -1);
}
+ index = NNI_IDHASH_INDEX(h, id);
for (;;) {
- if ((h->ih_entries[index].ihe_val == NULL) &&
- (h->ih_entries[index].ihe_skips == 0)) {
- return (NNG_ENOENT);
+ // The value of ihe_key is only valid if ihe_val is not NULL.
+ if ((h->ih_entries[index].ihe_key == id) &&
+ (h->ih_entries[index].ihe_val != NULL)) {
+ return (index);
}
- if (h->ih_entries[index].ihe_key == id) {
- *valp = h->ih_entries[index].ihe_val;
- return (0);
+ if (h->ih_entries[index].ihe_skips == 0) {
+ return ((size_t) -1);
}
index = NNI_IDHASH_NEXTPROBE(h, index);
}
}
+static int
+nni_hash_find(nni_idhash *h, uint64_t id, void **valp)
+{
+ size_t index;
+ if ((index = nni_hash_find_index(h, id)) == (size_t) -1) {
+ return (NNG_ENOENT);
+ }
+ *valp = h->ih_entries[index].ihe_val;
+ return (0);
+}
+
int
nni_idhash_find(nni_idhash *h, uint64_t id, void **valp)
{
@@ -148,13 +159,16 @@ nni_hash_resize(nni_idhash *h)
while (newsize < (h->ih_count * 2)) {
newsize *= 2;
}
+ if (newsize == oldsize) {
+ // Same size.
+ return (0);
+ }
oldents = h->ih_entries;
newents = NNI_ALLOC_STRUCTS(newents, newsize);
if (newents == NULL) {
return (NNG_ENOMEM);
}
- memset(newents, 0, sizeof(nni_idhash_entry) * newsize);
h->ih_entries = newents;
h->ih_cap = newsize;
@@ -173,6 +187,9 @@ nni_hash_resize(nni_idhash *h)
index = oldents[i].ihe_key & (newsize - 1);
for (;;) {
if (newents[index].ihe_val == NULL) {
+ // As we are hitting this entry for the first
+ // time, it won't have any skips.
+ NNI_ASSERT(newents[index].ihe_skips == 0);
h->ih_load++;
newents[index].ihe_val = oldents[i].ihe_val;
newents[index].ihe_key = oldents[i].ihe_key;
@@ -191,43 +208,41 @@ nni_hash_resize(nni_idhash *h)
int
nni_idhash_remove(nni_idhash *h, uint64_t id)
{
- int rv;
- void * val;
- size_t index;
+ size_t index;
+ size_t srch;
+ nni_idhash_entry *ent;
nni_mtx_lock(&h->ih_mtx);
- // 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_hash_find(h, id, &val)) != 0) {
+ if ((index = nni_hash_find_index(h, id)) == (size_t) -1) {
nni_mtx_unlock(&h->ih_mtx);
- return (rv);
+ return (NNG_ENOENT);
}
- index = NNI_IDHASH_INDEX(h, id);
-
- for (;;) {
- 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!");
- }
+ // Now we have found the index where the object exists. We are going
+ // to restart the search, until the index matches, to decrement the
+ // skips counter.
+ srch = (int) NNI_IDHASH_INDEX(h, id);
+ while (srch != index) {
+ ent = &h->ih_entries[srch];
+ NNI_ASSERT(ent->ihe_skips > 0);
ent->ihe_skips--;
if ((ent->ihe_skips == 0) && (ent->ihe_val == NULL)) {
h->ih_load--;
}
- index = NNI_IDHASH_NEXTPROBE(h, index);
+ srch = NNI_IDHASH_NEXTPROBE(h, srch);
}
+ ent = &h->ih_entries[index];
+
+ ent->ihe_val = NULL;
+ ent->ihe_key = (uint64_t) -1; // scribble garbage on the key
+ if (ent->ihe_skips == 0) {
+ h->ih_load--;
+ }
+ h->ih_count--;
// Shrink -- but it's ok if we can't.
(void) nni_hash_resize(h);
+
nni_mtx_unlock(&h->ih_mtx);
return (0);
@@ -236,25 +251,36 @@ nni_idhash_remove(nni_idhash *h, uint64_t id)
static int
nni_hash_insert(nni_idhash *h, uint64_t id, void *val)
{
- size_t index;
+ size_t index;
+ nni_idhash_entry *ent;
// 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))) {
return (NNG_ENOMEM);
}
+
+ // If it already exists, just overwrite the old value.
+ if ((index = nni_hash_find_index(h, id)) != (size_t) -1) {
+ ent = &h->ih_entries[index];
+ ent->ihe_val = val;
+ return (0);
+ }
+
index = NNI_IDHASH_INDEX(h, id);
for (;;) {
- 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++;
+ ent = &h->ih_entries[index];
+ if (ent->ihe_val == NULL) {
+ if (ent->ihe_skips == 0) {
+ // Newly used entry, bump the load.
h->ih_load++;
}
+ h->ih_count++;
ent->ihe_key = id;
ent->ihe_val = val;
return (0);
}
+ // Entry already in use, so don't increment the load.
ent->ihe_skips++;
index = NNI_IDHASH_NEXTPROBE(h, index);
}
@@ -275,10 +301,11 @@ int
nni_idhash_alloc(nni_idhash *h, uint64_t *idp, void *val)
{
uint64_t id;
- void * scrap;
int rv;
nni_mtx_lock(&h->ih_mtx);
+ NNI_ASSERT(val != NULL);
+
if (h->ih_count > (h->ih_maxval - h->ih_minval)) {
// Really more like ENOSPC.. the table is filled to max.
nni_mtx_unlock(&h->ih_mtx);
@@ -293,7 +320,7 @@ nni_idhash_alloc(nni_idhash *h, uint64_t *idp, void *val)
h->ih_dynval = h->ih_minval;
}
- if (nni_hash_find(h, id, &scrap) == NNG_ENOENT) {
+ if (nni_hash_find_index(h, id) == (size_t) -1) {
break;
}
}
@@ -323,3 +350,9 @@ nni_idhash_alloc32(nni_idhash *h, uint32_t *idp, void *val)
}
return (rv);
}
+
+size_t
+nni_idhash_count(nni_idhash *h)
+{
+ return (h->ih_count);
+}
diff --git a/tests/CMakeLists.txt b/tests/CMakeLists.txt
index 4c3625b6..031c15cd 100644
--- a/tests/CMakeLists.txt
+++ b/tests/CMakeLists.txt
@@ -139,7 +139,7 @@ add_nng_test(errors 2)
add_nng_test1(files 5 NNG_STATIC_LIB)
add_nng_test1(httpclient 60 NNG_SUPP_HTTP)
add_nng_test2(httpserver 30 NNG_STATIC_LIB NNG_SUPP_HTTP)
-add_nng_test1(idhash 5 NNG_STATIC_LIB)
+add_nng_test1(idhash 30 NNG_STATIC_LIB)
add_nng_test1(inproc 5 NNG_TRANSPORT_INPROC)
add_nng_test1(ipc 5 NNG_TRANSPORT_IPC)
add_nng_test1(ipcperms 5 NNG_TRANSPORT_IPC)
diff --git a/tests/idhash.c b/tests/idhash.c
index eb62fd76..72f1a44f 100644
--- a/tests/idhash.c
+++ b/tests/idhash.c
@@ -13,6 +13,77 @@
#include "core/nng_impl.h"
+#define STRESSLOAD 50000
+#define NVALUES 1000
+
+int
+stress(nni_idhash *h, void **values, size_t nvalues, int iter)
+{
+ for (int i = 0; i < iter; i++) {
+ void *x;
+ int v = rand() % nvalues; // Keep it constrained
+
+ switch (rand() & 3) {
+ case 0:
+ x = &values[rand() % nvalues];
+ values[v] = x;
+ if (nni_idhash_insert(h, v, x) != 0) {
+ return (-1);
+ }
+ break;
+
+ case 1:
+ if (values[v] == NULL) {
+ if (nni_idhash_remove(h, v) != NNG_ENOENT) {
+ return (-1);
+ } else {
+ break;
+ }
+ } else {
+ if (nni_idhash_remove(h, v) != 0) {
+ return (-1);
+ }
+ values[v] = NULL;
+ }
+ break;
+ case 2:
+ if (values[v] == NULL) {
+ if (nni_idhash_find(h, v, &x) != NNG_ENOENT) {
+ return (-1);
+ }
+
+ } else {
+ if ((nni_idhash_find(h, v, &x) != 0) ||
+ (x != values[v])) {
+ return (-1);
+ }
+ }
+ break;
+ }
+ }
+ return (0);
+}
+
+int
+poststress(nni_idhash *h, void **values, size_t nvalues)
+{
+ for (size_t i = 0; i < nvalues; i++) {
+ void *x;
+ if (values[i] == NULL) {
+ if ((nni_idhash_find(h, i, &x) != NNG_ENOENT) ||
+ (nni_idhash_remove(h, i) != NNG_ENOENT)) {
+ return (-1);
+ }
+ continue;
+ }
+ if (((nni_idhash_find(h, i, &x) != 0) || (x != values[i])) ||
+ (nni_idhash_remove(h, i) != 0)) {
+ return (-1);
+ }
+ }
+ return (0);
+}
+
Main({
nni_init();
atexit(nni_fini);
@@ -69,7 +140,6 @@ Main({
So(ptr == four);
});
});
-
});
Convey("We cannot find bogus values", {
void *ptr;
@@ -168,4 +238,22 @@ Main({
});
});
});
+
+ Test("Stress it", {
+ void *values[NVALUES];
+
+ Convey("Given a hash", {
+ nni_idhash *h;
+ So(nni_idhash_init(&h) == 0);
+ Reset({ nni_idhash_fini(h); });
+ memset(values, 0, sizeof(values));
+
+ Convey("A stress run works", {
+ So(stress(h, values, NVALUES, STRESSLOAD) ==
+ 0);
+ So(poststress(h, values, NVALUES) == 0);
+ So(nni_idhash_count(h) == 0);
+ });
+ });
+ });
})
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2026-01-18 22:14:49 +0000