From 4b53b1e31a93af8c739ba555970cb88d73063bce Mon Sep 17 00:00:00 2001 From: Garrett D'Amore Date: Thu, 29 Dec 2016 01:09:36 -0800 Subject: Implementation of an id hash for hashing pipes by ID. We use some hints from Python's dict implementation, using an open addressing scheme, and just ripping off the lower bits as needed. Since we assign IDs consecutively, this should work well. We shrink the table when it is only 1/8 full, and we ensure that we grow the table when it is 2/3 full. (The growth will start by at minimum doubling the required size.) --- src/CMakeLists.txt | 2 + src/core/idhash.c | 188 ++++++++++++++++++++++++++++++++++++++++++++++++++++ src/core/idhash.h | 55 +++++++++++++++ src/core/nng_impl.h | 1 + src/nng.c | 3 + src/nng.h | 1 + 6 files changed, 250 insertions(+) create mode 100644 src/core/idhash.c create mode 100644 src/core/idhash.h (limited to 'src') diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt index 7ac2a46f..f68afa32 100644 --- a/src/CMakeLists.txt +++ b/src/CMakeLists.txt @@ -29,6 +29,8 @@ set (NNG_SOURCES core/defs.h core/endpt.c + core/idhash.c + core/idhash.h core/init.c core/init.h core/list.c diff --git a/src/core/idhash.c b/src/core/idhash.c new file mode 100644 index 00000000..85759b93 --- /dev/null +++ b/src/core/idhash.c @@ -0,0 +1,188 @@ +// +// Copyright 2016 Garrett D'Amore +// +// This software is supplied under the terms of the MIT License, a +// copy of which should be located in the distribution where this +// file was obtained (LICENSE.txt). A copy of the license may also be +// found online at https://opensource.org/licenses/MIT. +// + +#include "core/nng_impl.h" + +#include + +int +nni_idhash_init(nni_idhash *h) +{ + h->ih_entries = nni_alloc(8 * sizeof (nni_idhash_entry)); + if (h->ih_entries == NULL) { + return (NNG_ENOMEM); + } + (void) memset(h->ih_entries, 0, (8 * sizeof (nni_idhash_entry))); + h->ih_count = 0; + h->ih_cap = 8; + h->ih_maxcount = 5; + h->ih_mincount = 0; // never shrink below this + return (0); +} + + +void +nni_idhash_fini(nni_idhash *h) +{ + nni_free(h->ih_entries, h->ih_cap * sizeof (nni_idhash_entry)); +} + + +// 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)) + +int +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) { + return (NNG_ENOENT); + } + if (h->ih_entries[index].ihe_key == id) { + *valp = h->ih_entries[index].ihe_val; + return (0); + } + index = NNI_IDHASH_NEXTPROBE(h, index); + } +} + + +static int +nni_hash_resize(nni_idhash *h) +{ + uint32_t newsize; + uint32_t oldsize; + nni_idhash_entry *newents; + nni_idhash_entry *oldents; + + if ((h->ih_count < h->ih_maxcount) && (h->ih_count >= h->ih_mincount)) { + // No resize needed. + return (0); + } + + oldsize = h->ih_cap; + newsize = h->ih_cap; + + newsize = 8; + while (newsize < (h->ih_count * 2)) { + newsize *= 2; + } + + oldents = h->ih_entries; + newents = nni_alloc(sizeof (nni_idhash_entry) * newsize); + if (newents == NULL) { + return (NNG_ENOMEM); + } + h->ih_entries = newents; + h->ih_cap = newsize; + if (newsize > 8) { + h->ih_mincount = newsize / 8; + h->ih_maxcount = newsize * 2 / 3; + } else { + h->ih_mincount = 0; + h->ih_maxcount = 5; + } + for (int i = 0; i < oldsize; i++) { + uint32_t index; + if (oldents[i].ihe_val == NULL) { + continue; + } + index = oldents[i].ihe_key & (newsize - 1); + for (;;) { + if (newents[index].ihe_val == NULL) { + newents[index].ihe_val = oldents[i].ihe_val; + newents[index].ihe_key = oldents[i].ihe_key; + break; + } + index = NNI_IDHASH_NEXTPROBE(h, index); + } + } + nni_free(oldents, sizeof (nni_idhash_entry) * oldsize); + return (0); +} + + +int +nni_hash_remove(nni_idhash *h, uint32_t id) +{ + uint32_t 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; + h->ih_count--; + break; + } + index = NNI_IDHASH_NEXTPROBE(h, index); + } + + // Shrink -- but it's ok if we can't. + (void) nni_hash_resize(h); + + return (0); +} + + +int +nni_hash_insert(nni_idhash *h, uint32_t id, void *val) +{ + uint32_t index; + + // 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); + } + index = id & (h->ih_cap - 1); + for (;;) { + if (h->ih_entries[index].ihe_val == NULL) { + h->ih_entries[index].ihe_key = id; + h->ih_entries[index].ihe_val = val; + h->ih_count++; + return (0); + } + index = NNI_IDHASH_NEXTPROBE(h, index); + } +} + + +int +nni_idhash_count(nni_idhash *h, uint32_t *countp) +{ + *countp = h->ih_count; + return (0); +} + + +int +nni_idhash_walk(nni_idhash *h, nni_idhash_walkfn fn, void *arg) +{ + int i, rv; + + for (i = 0; i < h->ih_cap; i++) { + nni_idhash_entry *ent = &h->ih_entries[i]; + + if (ent->ihe_val == NULL) { + continue; + } + rv = fn(arg, ent->ihe_key, ent->ihe_val); + if (rv != 0) { + return (rv); + } + } + return (0); +} diff --git a/src/core/idhash.h b/src/core/idhash.h new file mode 100644 index 00000000..ffc60858 --- /dev/null +++ b/src/core/idhash.h @@ -0,0 +1,55 @@ +// +// Copyright 2016 Garrett D'Amore +// +// This software is supplied under the terms of the MIT License, a +// copy of which should be located in the distribution where this +// file was obtained (LICENSE.txt). A copy of the license may also be +// found online at https://opensource.org/licenses/MIT. +// + +#ifndef CORE_IDHASH_H +#define CORE_IDHASH_H + +#include "core/nng_impl.h" + +// We find that we often want to have a list of things listed by a +// numeric ID, which is generally monotonically increasing. This is +// most often a pipe ID. To help keep collections of these things +// indexed by their ID (which might start from a very large value), +// we offer a hash table. The hash table uses open addressing, but +// 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. + +// 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; + +// nni_idhash_walkfn is called when walking a hash table. If the +// return value is non-zero, then nni_idhash_walk will terminate further +// 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. +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_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_count(nni_idhash *, uint32_t *); +extern int nni_idhash_walk(nni_idhash *, nni_idhash_walkfn, void *); + +#endif // CORE_IDHASH_H diff --git a/src/core/nng_impl.h b/src/core/nng_impl.h index f45394e9..a0a1a2e6 100644 --- a/src/core/nng_impl.h +++ b/src/core/nng_impl.h @@ -23,6 +23,7 @@ // symbols should be found in the toplevel nng.h header. #include "core/defs.h" #include "core/list.h" +#include "core/idhash.h" #include "core/init.h" #include "core/message.h" #include "core/msgqueue.h" diff --git a/src/nng.c b/src/nng.c index 7c6c403f..d92f3290 100644 --- a/src/nng.c +++ b/src/nng.c @@ -169,6 +169,9 @@ nng_strerror(int num) case NNG_ESTATE: return ("Incorrect state"); + case NNG_ENOENT: + return ("Entry not found"); + default: return ("Unknown error"); } diff --git a/src/nng.h b/src/nng.h index 335094c7..36800139 100644 --- a/src/nng.h +++ b/src/nng.h @@ -363,6 +363,7 @@ NNG_DECL int nng_device(nng_socket *, nng_socket *); #define NNG_ENOTSUP (-9) #define NNG_EADDRINUSE (-10) #define NNG_ESTATE (-11) +#define NNG_ENOENT (-12) // Maximum length of a socket address. This includes the terminating NUL. // This limit is built into other implementations, so do not change it. -- cgit v1.2.3-70-g09d2