diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/CMakeLists.txt | 2 | ||||
| -rw-r--r-- | src/core/idhash.c | 188 | ||||
| -rw-r--r-- | src/core/idhash.h | 55 | ||||
| -rw-r--r-- | src/core/nng_impl.h | 1 | ||||
| -rw-r--r-- | src/nng.c | 3 | ||||
| -rw-r--r-- | src/nng.h | 1 |
6 files changed, 250 insertions, 0 deletions
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 <garrett@damore.org> +// +// 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 <string.h> + +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 <garrett@damore.org> +// +// 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" @@ -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"); } @@ -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. |