From 3298ac1e93742e7a1ef5c4dc2e9b603dfa89d3cb Mon Sep 17 00:00:00 2001 From: Garrett D'Amore Date: Fri, 29 Dec 2023 17:43:50 -0800 Subject: fixes #1740 Public ID hash API This includes a manual page documenting the entire set of functions in one step. The hash is 64-bit based for now, to be maximally flexible. An internal 32-bit convenience for the common internal use is also provided (not public). The public API includes a test suite. --- src/supplemental/CMakeLists.txt | 1 + src/supplemental/idhash/CMakeLists.txt | 11 ++ src/supplemental/idhash/idhash.c | 60 +++++++ src/supplemental/idhash/idhash.h | 27 +++ src/supplemental/idhash/idhash_test.c | 309 +++++++++++++++++++++++++++++++++ 5 files changed, 408 insertions(+) create mode 100644 src/supplemental/idhash/CMakeLists.txt create mode 100644 src/supplemental/idhash/idhash.c create mode 100644 src/supplemental/idhash/idhash.h create mode 100644 src/supplemental/idhash/idhash_test.c (limited to 'src/supplemental') diff --git a/src/supplemental/CMakeLists.txt b/src/supplemental/CMakeLists.txt index 5be439b1..3fa254e7 100644 --- a/src/supplemental/CMakeLists.txt +++ b/src/supplemental/CMakeLists.txt @@ -11,6 +11,7 @@ nng_directory(supplemental) add_subdirectory(base64) add_subdirectory(http) +add_subdirectory(idhash) add_subdirectory(sha1) add_subdirectory(tls) add_subdirectory(util) diff --git a/src/supplemental/idhash/CMakeLists.txt b/src/supplemental/idhash/CMakeLists.txt new file mode 100644 index 00000000..3a9bbb0b --- /dev/null +++ b/src/supplemental/idhash/CMakeLists.txt @@ -0,0 +1,11 @@ +# +# Copyright 2023 Staysail Systems, Inc. +# +# 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. +# + +nng_sources_if(NNG_SUPP_IDHASH idhash.c idhash.h) +nng_test_if(NNG_SUPP_IDHASH idhash_test) diff --git a/src/supplemental/idhash/idhash.c b/src/supplemental/idhash/idhash.c new file mode 100644 index 00000000..051b686a --- /dev/null +++ b/src/supplemental/idhash/idhash.c @@ -0,0 +1,60 @@ +// +// Copyright 2023 Staysail Systems, Inc. +// +// 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 "supplemental/idhash/idhash.h" +#include "core/nng_impl.h" + +struct nng_id_map_s { + nni_id_map m; +}; + +int +nng_id_map_alloc(nng_id_map **map, uint64_t lo, uint64_t hi, int flags) +{ + nng_id_map *m; + + if ((m = NNI_ALLOC_STRUCT(m)) == NULL) { + return (NNG_ENOMEM); + } + nni_id_map_init( + &m->m, lo, hi, (flags & NNG_MAP_RANDOM) ? true : false); + *map = m; + return (0); +} + +void +nng_id_map_free(nng_id_map *map) +{ + nni_id_map_fini(&map->m); + NNI_FREE_STRUCT(map); +} + +void * +nng_id_get(nng_id_map *map, uint64_t id) +{ + return (nni_id_get(&map->m, id)); +} + +int +nng_id_set(nng_id_map *map, uint64_t id, void *val) +{ + return (nni_id_set(&map->m, id, val)); +} + +int +nng_id_remove(nng_id_map *map, uint64_t id) +{ + return (nni_id_remove(&map->m, id)); +} + +int +nng_id_alloc(nng_id_map *map, uint64_t *id, void *val) +{ + return (nni_id_alloc(&map->m, id, val)); +} diff --git a/src/supplemental/idhash/idhash.h b/src/supplemental/idhash/idhash.h new file mode 100644 index 00000000..5fd8f235 --- /dev/null +++ b/src/supplemental/idhash/idhash.h @@ -0,0 +1,27 @@ +// +// Copyright 2023 Staysail Systems, Inc. +// +// 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 NNG_SUPPLEMENTAL_IDHASH_IDHASH_H +#define NNG_SUPPLEMENTAL_IDHASH_IDHASH_H + +#include + +typedef struct nng_id_map_s nng_id_map; + +#define NNG_MAP_RANDOM 1 + +NNG_DECL int nng_id_map_alloc( + nng_id_map **map, uint64_t lo, uint64_t hi, int flags); +NNG_DECL void nng_id_map_free(nng_id_map *map); +NNG_DECL void *nng_id_get(nng_id_map *, uint64_t); +NNG_DECL int nng_id_set(nng_id_map *, uint64_t, void *); +NNG_DECL int nng_id_alloc(nng_id_map *, uint64_t *, void *); +NNG_DECL int nng_id_remove(nng_id_map *, uint64_t); + +#endif // NNG_SUPPLEMENTAL_IDHASH_IDHASH_H diff --git a/src/supplemental/idhash/idhash_test.c b/src/supplemental/idhash/idhash_test.c new file mode 100644 index 00000000..367f34bc --- /dev/null +++ b/src/supplemental/idhash/idhash_test.c @@ -0,0 +1,309 @@ +// +// Copyright 2023 Staysail Systems, Inc. +// +// 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 + +#include "idhash.h" + +void +test_id_basic(void) +{ + nng_id_map *m; + char *five = "five"; + char *four = "four"; + + NUTS_PASS(nng_id_map_alloc(&m, 0, 0, 0)); + + // insert it + NUTS_PASS(nng_id_set(m, 5, five)); + // retrieve it + NUTS_TRUE(nng_id_get(m, 5) == five); + + // change it + NUTS_PASS(nng_id_set(m, 5, four)); + NUTS_TRUE(nng_id_get(m, 5) == four); + + // delete + NUTS_PASS(nng_id_remove(m, 5)); + + nng_id_map_free(m); +} + +void +test_id_random(void) +{ + int i; + uint64_t id; + for (i = 0; i < 2; i++) { + nng_id_map *m; + NUTS_PASS(nng_id_map_alloc(&m, 0, 0, NNG_MAP_RANDOM)); + NUTS_PASS(nng_id_alloc(m, &id, &id)); + nng_id_map_free(m); + NUTS_TRUE(id != 0); + if (id != 1) { + break; + } + // one chance in 4 billion, but try again + } + + NUTS_TRUE(id != 1); + NUTS_TRUE(i < 2); +} + +void +test_id_collision(void) +{ + nng_id_map *m; + char *five = "five"; + char *four = "four"; + + NUTS_PASS(nng_id_map_alloc(&m, 0, 0, 0)); + + // Carefully crafted -- 13 % 8 == 5. + NUTS_PASS(nng_id_set(m, 5, five)); + NUTS_PASS(nng_id_set(m, 13, four)); + NUTS_TRUE(nng_id_get(m, 5) == five); + NUTS_TRUE(nng_id_get(m, 13) == four); + + // Delete the intermediate + NUTS_PASS(nng_id_remove(m, 5)); + NUTS_TRUE(nng_id_get(m, 13) == four); + + nng_id_map_free(m); +} + +void +test_id_empty(void) +{ + nng_id_map *m; + + NUTS_PASS(nng_id_map_alloc(&m, 0, 0, 0)); + + NUTS_TRUE(nng_id_get(m, 42) == NULL); + NUTS_FAIL(nng_id_remove(m, 42), NNG_ENOENT); + NUTS_FAIL(nng_id_remove(m, 1), NNG_ENOENT); + nng_id_map_free(m); +} + +void +test_id_not_found(void) +{ + nng_id_map *m; + uint64_t id; + + NUTS_PASS(nng_id_map_alloc(&m, 0, 0, 0)); + + NUTS_PASS(nng_id_alloc(m, &id, &id)); + NUTS_FAIL(nng_id_remove(m, 42), NNG_ENOENT); + NUTS_FAIL(nng_id_remove(m, 2), NNG_ENOENT); + NUTS_PASS(nng_id_remove(m, id)); + nng_id_map_free(m); +} + +void +test_id_resize(void) +{ + nng_id_map *m; + int rv; + int i; + int expect[1024]; + + for (i = 0; i < 1024; i++) { + expect[i] = i; + } + + NUTS_PASS(nng_id_map_alloc(&m, 0, 0, 0)); + + for (i = 0; i < 1024; i++) { + if ((rv = nng_id_set(m, i, &expect[i])) != 0) { + NUTS_PASS(rv); + } + } + + for (i = 0; i < 1024; i++) { + if ((rv = nng_id_remove(m, i)) != 0) { + NUTS_PASS(rv); + } + } + nng_id_map_free(m); +} + +void +test_id_dynamic(void) +{ + nng_id_map *m; + int expect[5]; + uint64_t id; + + NUTS_PASS(nng_id_map_alloc(&m, 10, 13, 0)); + + // We can fill the table. + NUTS_PASS(nng_id_alloc(m, &id, &expect[0])); + NUTS_TRUE(id == 10); + NUTS_PASS(nng_id_alloc(m, &id, &expect[1])); + NUTS_TRUE(id == 11); + NUTS_PASS(nng_id_alloc(m, &id, &expect[2])); + NUTS_TRUE(id == 12); + NUTS_PASS(nng_id_alloc(m, &id, &expect[3])); + NUTS_TRUE(id == 13); + + // Adding another fails. + NUTS_FAIL(nng_id_alloc(m, &id, &expect[4]), NNG_ENOMEM); + + // Delete one. + NUTS_PASS(nng_id_remove(m, 11)); + + // And now we can allocate one. + NUTS_PASS(nng_id_alloc(m, &id, &expect[4])); + NUTS_TRUE(id == 11); + nng_id_map_free(m); +} + +void +test_id_set_out_of_range(void) +{ + nng_id_map *m; + int x; + uint64_t id; + + NUTS_PASS(nng_id_map_alloc(&m, 10, 13, 0)); + + // We can insert outside the range forcibly. + NUTS_PASS(nng_id_set(m, 1, &x)); + NUTS_PASS(nng_id_set(m, 100, &x)); + NUTS_PASS(nng_id_alloc(m, &id, &x)); + NUTS_TRUE(id == 10); + nng_id_map_free(m); +} + +#define STRESS_LOAD 50000 +#define NUM_VALUES 1000 + +void +test_id_stress(void) +{ + void *values[NUM_VALUES]; + nng_id_map *m; + size_t i; + int rv; + void *x; + int v; + + NUTS_PASS(nng_id_map_alloc(&m, 0, 0, 0)); + for (i = 0; i < NUM_VALUES; i++) { + values[i] = NULL; + } + + for (i = 0; i < STRESS_LOAD; i++) { + v = rand() % NUM_VALUES; // Keep it constrained + + switch (rand() & 3) { + case 0: + x = &values[rand() % NUM_VALUES]; + values[v] = x; + if ((rv = nng_id_set(m, v, x)) != 0) { + NUTS_PASS(rv); + goto out; + } + break; + + case 1: + rv = nng_id_remove(m, v); + if (values[v] == NULL) { + if (rv != NNG_ENOENT) { + NUTS_FAIL(rv, NNG_ENOENT); + goto out; + } + } else { + values[v] = NULL; + if (rv != 0) { + NUTS_PASS(rv); + goto out; + } + } + break; + case 2: + x = nng_id_get(m, v); + if (x != values[v]) { + NUTS_TRUE(x == values[v]); + goto out; + } + break; + } + } +out: + NUTS_TRUE(i == STRESS_LOAD); + + // Post stress check. + for (i = 0; i < NUM_VALUES; i++) { + x = nng_id_get(m, (uint32_t) i); + if (x != values[i]) { + NUTS_TRUE(x == values[i]); + break; + } + + // We only use the test macros if we know they are going + // to fail. Otherwise, there will be too many errors reported. + rv = nng_id_remove(m, (uint32_t) i); + if ((x == NULL) && (rv != NNG_ENOENT)) { + NUTS_FAIL(rv, NNG_ENOENT); + } else if ((x != NULL) && (rv != 0)) { + NUTS_PASS(rv); + } + } + NUTS_TRUE(i == NUM_VALUES); + + nng_id_map_free(m); +} + +void +test_id_alloc_long_long(void) +{ +#define TEST_IDS 100 + nng_id_map *m; + int x; + uint64_t ids[TEST_IDS]; + + NUTS_PASS(nng_id_map_alloc(&m, 1ULL << 32, (int64_t) -1, 0)); + + // We can insert outside the range forcibly - making sure we are + // choosing numbers above 64 bits. + for (int i = 0; i < TEST_IDS; i++) { + NUTS_PASS(nng_id_alloc(m, &ids[i], &x)); + NUTS_ASSERT(ids[i] > 0xFFFFFFFFULL); + } + for (int i = 0; i < TEST_IDS; i++) { + bool matched = false; + for (int j = 0; j < i; j++) { + // only dump the assertion on failure + // otherwise it is too noisy + if (ids[i] == ids[j]) { + matched = true; + break; + } + } + NUTS_ASSERT(!matched); + } + nng_id_map_free(m); +#undef TEST_IDS +} + +NUTS_TESTS = { + { "id basic", test_id_basic }, + { "id random", test_id_random }, + { "id collision", test_id_collision }, + { "id empty", test_id_empty }, + { "not found", test_id_not_found }, + { "id resize", test_id_resize }, + { "id dynamic", test_id_dynamic }, + { "id set out of range", test_id_set_out_of_range }, + { "id stress", test_id_stress }, + { "id alloc long long", test_id_alloc_long_long }, + { NULL, NULL }, +}; -- cgit v1.2.3-70-g09d2