[njs] Introduced flat hash.
Vadim Zhestikov
v.zhestikov at f5.com
Wed Aug 30 19:07:50 UTC 2023
details: https://hg.nginx.org/njs/rev/c7d2a7846b0b
branches:
changeset: 2186:c7d2a7846b0b
user: Vadim Zhestikov <v.zhestikov at f5.com>
date: Wed Aug 30 12:06:12 2023 -0700
description:
Introduced flat hash.
Object property enumeration order is corrected.
This fixes #189 issue on Github.
diffstat:
auto/sources | 2 +-
external/njs_shell.c | 4 +-
src/njs_array.c | 45 +++-
src/njs_array.h | 2 +
src/njs_array_buffer.c | 4 +-
src/njs_async.c | 4 +-
src/njs_buffer.c | 4 +-
src/njs_date.c | 4 +-
src/njs_encoding.c | 8 +-
src/njs_error.c | 40 +-
src/njs_flathsh.c | 560 ++++++++++++++++++++++++++++++++++++++++++
src/njs_flathsh.h | 156 +++++++++++
src/njs_function.c | 8 +-
src/njs_main.h | 2 +-
src/njs_number.c | 4 +-
src/njs_object.c | 511 +++++++++++++++++++++++--------------
src/njs_object_prop.c | 1 +
src/njs_promise.c | 4 +-
src/njs_regexp.c | 4 +-
src/njs_string.c | 4 +-
src/njs_symbol.c | 4 +-
src/njs_typed_array.c | 40 +-
src/njs_value.c | 43 ++-
src/njs_value.h | 3 +-
src/njs_vm.c | 2 +-
src/test/lvlhsh_unit_test.c | 2 +-
src/test/njs_externals_test.c | 2 +-
src/test/njs_unit_test.c | 39 +-
28 files changed, 1215 insertions(+), 291 deletions(-)
diffs (truncated from 2123 to 1000 lines):
diff -r c0f581b26e84 -r c7d2a7846b0b auto/sources
--- a/auto/sources Wed Aug 23 10:09:22 2023 -0700
+++ b/auto/sources Wed Aug 30 12:06:12 2023 -0700
@@ -10,7 +10,7 @@ NJS_LIB_SRCS=" \
src/njs_utf16.c \
src/njs_arr.c \
src/njs_rbtree.c \
- src/njs_lvlhsh.c \
+ src/njs_flathsh.c \
src/njs_trace.c \
src/njs_random.c \
src/njs_md5.c \
diff -r c0f581b26e84 -r c7d2a7846b0b external/njs_shell.c
--- a/external/njs_shell.c Wed Aug 23 10:09:22 2023 -0700
+++ b/external/njs_shell.c Wed Aug 30 12:06:12 2023 -0700
@@ -11,7 +11,7 @@
#include <njs_arr.h>
#include <njs_queue.h>
#include <njs_rbtree.h>
-#include <njs_lvlhsh.h>
+#include <njs_flathsh.h>
#include <njs_djb_hash.h>
#if (!defined NJS_FUZZER_TARGET && defined NJS_HAVE_READLINE)
@@ -1636,7 +1636,7 @@ lvlhsh_key_test(njs_lvlhsh_query_t *lhq,
static void *
lvlhsh_pool_alloc(void *pool, size_t size)
{
- return njs_mp_align(pool, size, size);
+ return njs_mp_align(pool, NJS_MAX_ALIGNMENT, size);
}
diff -r c0f581b26e84 -r c7d2a7846b0b src/njs_array.c
--- a/src/njs_array.c Wed Aug 23 10:09:22 2023 -0700
+++ b/src/njs_array.c Wed Aug 30 12:06:12 2023 -0700
@@ -609,10 +609,10 @@ njs_array_of(njs_vm_t *vm, njs_value_t *
static const njs_object_prop_t njs_array_constructor_properties[] =
{
+ NJS_DECLARE_PROP_LENGTH(1),
+
NJS_DECLARE_PROP_NAME("Array"),
- NJS_DECLARE_PROP_LENGTH(1),
-
NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0),
NJS_DECLARE_PROP_NATIVE("from", njs_array_from, 1, 0),
@@ -1828,6 +1828,47 @@ njs_array_indices_handler(const void *fi
}
+int
+njs_array_indices_handler_nums(const void *first, const void *second, void *ctx)
+{
+ double num1, num2;
+ int64_t diff;
+ const njs_value_t *val1, *val2;
+
+ val1 = first;
+ val2 = second;
+
+ num1 = njs_string_to_index(val1);
+ num2 = njs_string_to_index(val2);
+
+ if (!isnan(num1) || !isnan(num2)) {
+ if (isnan(num1)) {
+ if (!isnan(num2)) {
+ return 1;
+
+ } else {
+
+ return 0;
+ }
+ }
+
+ if (isnan(num2)) {
+ return -1;
+ }
+
+ diff = (int64_t) (num1 - num2);
+
+ if (diff < 0) {
+ return -1;
+ }
+
+ return diff != 0;
+ }
+
+ return 0;
+}
+
+
njs_array_t *
njs_array_keys(njs_vm_t *vm, njs_value_t *object, njs_bool_t all)
{
diff -r c0f581b26e84 -r c7d2a7846b0b src/njs_array.h
--- a/src/njs_array.h Wed Aug 23 10:09:22 2023 -0700
+++ b/src/njs_array.h Wed Aug 30 12:06:12 2023 -0700
@@ -36,6 +36,8 @@ njs_int_t njs_array_expand(njs_vm_t *vm,
uint32_t append);
njs_int_t njs_array_prototype_to_string(njs_vm_t *vm, njs_value_t *args,
njs_uint_t nargs, njs_index_t unused, njs_value_t *retval);
+int njs_array_indices_handler_nums(const void *first, const void *second,
+ void *ctx);
njs_inline njs_value_t *
diff -r c0f581b26e84 -r c7d2a7846b0b src/njs_array_buffer.c
--- a/src/njs_array_buffer.c Wed Aug 23 10:09:22 2023 -0700
+++ b/src/njs_array_buffer.c Wed Aug 30 12:06:12 2023 -0700
@@ -141,9 +141,9 @@ njs_array_buffer_writable(njs_vm_t *vm,
static const njs_object_prop_t njs_array_buffer_constructor_properties[] =
{
- NJS_DECLARE_PROP_NAME("ArrayBuffer"),
+ NJS_DECLARE_PROP_LENGTH(1),
- NJS_DECLARE_PROP_LENGTH(1),
+ NJS_DECLARE_PROP_NAME("ArrayBuffer"),
NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0),
diff -r c0f581b26e84 -r c7d2a7846b0b src/njs_async.c
--- a/src/njs_async.c Wed Aug 23 10:09:22 2023 -0700
+++ b/src/njs_async.c Wed Aug 30 12:06:12 2023 -0700
@@ -163,9 +163,9 @@ njs_async_context_free(njs_vm_t *vm, njs
static const njs_object_prop_t njs_async_constructor_properties[] =
{
- NJS_DECLARE_PROP_NAME("AsyncFunction"),
+ NJS_DECLARE_PROP_LENGTH(1),
- NJS_DECLARE_PROP_LENGTH(1),
+ NJS_DECLARE_PROP_NAME("AsyncFunction"),
NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0),
};
diff -r c0f581b26e84 -r c7d2a7846b0b src/njs_buffer.c
--- a/src/njs_buffer.c Wed Aug 23 10:09:22 2023 -0700
+++ b/src/njs_buffer.c Wed Aug 30 12:06:12 2023 -0700
@@ -2538,10 +2538,10 @@ const njs_object_init_t njs_buffer_prot
static const njs_object_prop_t njs_buffer_constructor_properties[] =
{
+ NJS_DECLARE_PROP_LENGTH(0),
+
NJS_DECLARE_PROP_NAME("Buffer"),
- NJS_DECLARE_PROP_LENGTH(0),
-
NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0),
NJS_DECLARE_PROP_NATIVE("alloc", njs_buffer_alloc_safe, 0, 1),
diff -r c0f581b26e84 -r c7d2a7846b0b src/njs_date.c
--- a/src/njs_date.c Wed Aug 23 10:09:22 2023 -0700
+++ b/src/njs_date.c Wed Aug 30 12:06:12 2023 -0700
@@ -1109,9 +1109,9 @@ njs_date_number_parse(int64_t *value, co
static const njs_object_prop_t njs_date_constructor_properties[] =
{
- NJS_DECLARE_PROP_NAME("Date"),
+ NJS_DECLARE_PROP_LENGTH(7),
- NJS_DECLARE_PROP_LENGTH(7),
+ NJS_DECLARE_PROP_NAME("Date"),
NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0),
diff -r c0f581b26e84 -r c7d2a7846b0b src/njs_encoding.c
--- a/src/njs_encoding.c Wed Aug 23 10:09:22 2023 -0700
+++ b/src/njs_encoding.c Wed Aug 30 12:06:12 2023 -0700
@@ -256,9 +256,9 @@ const njs_object_init_t njs_text_encode
static const njs_object_prop_t njs_text_encoder_constructor_properties[] =
{
- NJS_DECLARE_PROP_NAME("TextEncoder"),
+ NJS_DECLARE_PROP_LENGTH(0),
- NJS_DECLARE_PROP_LENGTH(0),
+ NJS_DECLARE_PROP_NAME("TextEncoder"),
NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0),
};
@@ -593,9 +593,9 @@ const njs_object_init_t njs_text_decode
static const njs_object_prop_t njs_text_decoder_constructor_properties[] =
{
- NJS_DECLARE_PROP_NAME("TextDecoder"),
+ NJS_DECLARE_PROP_LENGTH(0),
- NJS_DECLARE_PROP_LENGTH(0),
+ NJS_DECLARE_PROP_NAME("TextDecoder"),
NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0),
};
diff -r c0f581b26e84 -r c7d2a7846b0b src/njs_error.c
--- a/src/njs_error.c Wed Aug 23 10:09:22 2023 -0700
+++ b/src/njs_error.c Wed Aug 30 12:06:12 2023 -0700
@@ -354,9 +354,9 @@ njs_error_constructor(njs_vm_t *vm, njs_
static const njs_object_prop_t njs_error_constructor_properties[] =
{
- NJS_DECLARE_PROP_NAME("Error"),
+ NJS_DECLARE_PROP_LENGTH(1),
- NJS_DECLARE_PROP_LENGTH(1),
+ NJS_DECLARE_PROP_NAME("Error"),
NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0),
};
@@ -370,9 +370,9 @@ const njs_object_init_t njs_error_const
static const njs_object_prop_t njs_eval_error_constructor_properties[] =
{
- NJS_DECLARE_PROP_NAME("EvalError"),
+ NJS_DECLARE_PROP_LENGTH(1),
- NJS_DECLARE_PROP_LENGTH(1),
+ NJS_DECLARE_PROP_NAME("EvalError"),
NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0),
};
@@ -386,9 +386,9 @@ const njs_object_init_t njs_eval_error_
static const njs_object_prop_t njs_internal_error_constructor_properties[] =
{
- NJS_DECLARE_PROP_NAME("InternalError"),
+ NJS_DECLARE_PROP_LENGTH(1),
- NJS_DECLARE_PROP_LENGTH(1),
+ NJS_DECLARE_PROP_NAME("InternalError"),
NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0),
};
@@ -402,9 +402,9 @@ const njs_object_init_t njs_internal_er
static const njs_object_prop_t njs_range_error_constructor_properties[] =
{
- NJS_DECLARE_PROP_NAME("RangeError"),
+ NJS_DECLARE_PROP_LENGTH(1),
- NJS_DECLARE_PROP_LENGTH(1),
+ NJS_DECLARE_PROP_NAME("RangeError"),
NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0),
};
@@ -418,9 +418,9 @@ const njs_object_init_t njs_range_error
static const njs_object_prop_t njs_reference_error_constructor_properties[] =
{
- NJS_DECLARE_PROP_NAME("ReferenceError"),
+ NJS_DECLARE_PROP_LENGTH(1),
- NJS_DECLARE_PROP_LENGTH(1),
+ NJS_DECLARE_PROP_NAME("ReferenceError"),
NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0),
};
@@ -434,9 +434,9 @@ const njs_object_init_t njs_reference_e
static const njs_object_prop_t njs_syntax_error_constructor_properties[] =
{
- NJS_DECLARE_PROP_NAME("SyntaxError"),
+ NJS_DECLARE_PROP_LENGTH(1),
- NJS_DECLARE_PROP_LENGTH(1),
+ NJS_DECLARE_PROP_NAME("SyntaxError"),
NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0),
};
@@ -450,9 +450,9 @@ const njs_object_init_t njs_syntax_erro
static const njs_object_prop_t njs_type_error_constructor_properties[] =
{
- NJS_DECLARE_PROP_NAME("TypeError"),
+ NJS_DECLARE_PROP_LENGTH(1),
- NJS_DECLARE_PROP_LENGTH(1),
+ NJS_DECLARE_PROP_NAME("TypeError"),
NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0),
};
@@ -466,9 +466,9 @@ const njs_object_init_t njs_type_error_
static const njs_object_prop_t njs_uri_error_constructor_properties[] =
{
- NJS_DECLARE_PROP_NAME("URIError"),
+ NJS_DECLARE_PROP_LENGTH(1),
- NJS_DECLARE_PROP_LENGTH(1),
+ NJS_DECLARE_PROP_NAME("URIError"),
NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0),
};
@@ -482,9 +482,9 @@ const njs_object_init_t njs_uri_error_c
static const njs_object_prop_t njs_aggregate_error_constructor_properties[] =
{
- NJS_DECLARE_PROP_NAME("AggregateError"),
+ NJS_DECLARE_PROP_LENGTH(1),
- NJS_DECLARE_PROP_LENGTH(1),
+ NJS_DECLARE_PROP_NAME("AggregateError"),
NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0),
};
@@ -566,9 +566,9 @@ njs_memory_error_prototype_create(njs_vm
static const njs_object_prop_t njs_memory_error_constructor_properties[] =
{
- NJS_DECLARE_PROP_NAME("MemoryError"),
+ NJS_DECLARE_PROP_LENGTH(1),
- NJS_DECLARE_PROP_LENGTH(1),
+ NJS_DECLARE_PROP_NAME("MemoryError"),
NJS_DECLARE_PROP_HANDLER("prototype", njs_memory_error_prototype_create,
0, 0, 0),
diff -r c0f581b26e84 -r c7d2a7846b0b src/njs_flathsh.c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/njs_flathsh.c Wed Aug 30 12:06:12 2023 -0700
@@ -0,0 +1,560 @@
+
+/*
+ * Copyright (C) NGINX, Inc.
+ */
+
+#include <njs_main.h>
+
+/*
+ * Flat hash consists of dynamic DATA STRUCTURE and set of OPERATIONS.
+ *
+ * DATA STRUCTURE
+ * Consists of 3 parts allocated one by one in chunk of memory:
+ *
+ * HASH_CELLS array of indices of 1st list element in ELEMENTS array,
+ * or 0 if list is empty. HASH_CELLS_length is power of 2.
+ * DESCRIPTOR contains hash_mask (= HASH_CELLS_Length - 1), ELEMENTS_size,
+ * number of last used element in ELEMENTS,
+ * number of deleted elements in ELEMENTS;
+ * ELEMENTS array of: [index of next element, hash_function(KEY),
+ * link to stored value or NULL if element is not used)].
+ *
+ * PROPERTIES of flat hash
+ * It is relocatable in memory, preserve insertion order, expand and shrink
+ * depending on number elements in it, maximum occupancy is 2^32-2 elements.
+ *
+ * OPERATIONS
+ * ADD element by key S with value V
+ * Prerequisite: be sure if flat hash not contains S. If ELEMENTS has free
+ * space after last element, then this element is populated by: V,
+ * hash_function(S), S. Then element is added to correspondent HASH_CELL.
+ * In case when no free element in ELEMENTS, DATA STRUCTURE is expanded by
+ * expnad_elts(). It does the following: ELEMENTS_size is increased by
+ * EXPAND_FACTOR, which value is expected to be > 1. For fast access to
+ * stored values, HASH_CELLS_size need to be big enough to provide its low
+ * population: in average less than 1 element per HASH_CELL. So,
+ * if HASH_CELLS_size < ELEMENTS_size then it will try doubling
+ * HASH_CELLS_size, until new HASH_CELLS_size >= ELEMENTS_size. Now
+ * new HASH_CELLS_size and new ELEMENTS_size are both defined. New
+ * expanded hash is obtained as:
+ * if HASH_CELLS_size is not increased, then
+ * reallocate full DATA STRUCTURE,
+ * else
+ * create new DATA STRUCTURE and populate it
+ * by ELEMENTS from old DATA STRUCTURE.
+ * Replace old DATA STRUCTURE by new one and release old one.
+ *
+ * FIND element by key S
+ * HASH_CELLS is array which contains cells of hash
+ * table. As entry to the table the following index is used:
+ * cell_num = hash_function(S) & hash_nask
+ * hash_function is external and it is not specified here, it is needed to
+ * be good hash function for Ss, and produce results in range from 0 to
+ * at least 2^32 - 1; hash_mask is located in DESCRIPTOR, and it is equal
+ * to HASH_CELLS_size - 1, where HASH_CELLS_size is always power of 2.
+ * hash cell contains (may be empty) list of hash elements with same
+ * cell_num. Now run over the list of elements and test if some element
+ * contains link to S. Test function is external and is not specified here.
+ *
+ * DELETE element by key S
+ * Locate S in ELEMENTS and remove it from elements list. Update number
+ * of removed elements in hash_decriptor. Mark deleted
+ * element as not used/deleted. If number of deleted elements is big
+ * enough, then use shrink_elts(): it removes gaps in ELEMENTS, shrinks if
+ * required HASH_CELLS, and creates new DATA STRUCTURE.
+ *
+ * ENUMERATE all elements in order of insertion
+ * Returns one by one used elements from ELEMENTS.
+ */
+
+
+#define NJS_FLATHSH_ELTS_INITIAL_SIZE 2
+#define NJS_FLATHSH_HASH_INITIAL_SIZE 4
+#define NJS_FLATHSH_ELTS_EXPAND_FACTOR_NUM 3
+#define NJS_FLATHSH_ELTS_EXPAND_FACTOR_DENOM 2
+#define NJS_FLATHSH_ELTS_FRACTION_TO_SHRINK 2
+#define NJS_FLATHSH_ELTS_MINIMUM_TO_SHRINK 8
+
+
+struct njs_flathsh_descr_s {
+ uint32_t hash_mask;
+ uint32_t elts_size; /* allocated properties */
+ uint32_t elts_count; /* include deleted properties */
+ uint32_t elts_deleted_count;
+};
+
+
+static njs_flathsh_descr_t *njs_flathsh_alloc(njs_flathsh_query_t *fhq,
+ size_t hash_size, size_t elts_size);
+static njs_flathsh_descr_t *njs_expand_elts(njs_flathsh_query_t *fhq,
+ njs_flathsh_descr_t *h, uint32_t count);
+
+
+njs_inline size_t
+njs_flathsh_chunk_size(size_t hash_size, size_t elts_size)
+{
+ return hash_size * sizeof(uint32_t) + sizeof(njs_flathsh_descr_t) +
+ elts_size * sizeof(njs_flathsh_elt_t);
+}
+
+
+njs_inline void *
+njs_flathsh_malloc(njs_flathsh_query_t *fhq, size_t size)
+{
+ return
+#ifdef NJS_FLATHSH_USE_SYSTEM_ALLOCATOR
+ malloc(size)
+#else
+ fhq->proto->alloc(fhq->pool, size)
+#endif
+ ;
+}
+
+
+njs_inline void
+njs_flathsh_free(njs_flathsh_query_t *fhq, void *ptr)
+{
+#ifdef NJS_FLATHSH_USE_SYSTEM_ALLOCATOR
+ free(ptr)
+#else
+ fhq->proto->free(fhq->pool, ptr, 0)
+#endif
+ ;
+}
+
+
+njs_inline njs_flathsh_descr_t *
+njs_flathsh_descr(void *chunk, size_t hash_size)
+{
+ return (njs_flathsh_descr_t *) ((uint32_t *) chunk + hash_size);
+}
+
+
+njs_inline uint32_t *
+njs_hash_cells_end(njs_flathsh_descr_t *h)
+{
+ return (uint32_t *) h;
+}
+
+
+njs_inline void *
+njs_flathsh_chunk(njs_flathsh_descr_t *h)
+{
+ return njs_hash_cells_end(h) - ((njs_int_t) h->hash_mask + 1);
+}
+
+
+njs_inline njs_flathsh_elt_t *
+njs_hash_elts(njs_flathsh_descr_t *h)
+{
+ return (njs_flathsh_elt_t *) ((char *) h + sizeof(njs_flathsh_descr_t));
+}
+
+
+/*
+ * Create a new empty flat hash.
+ */
+njs_flathsh_descr_t *
+njs_flathsh_new(njs_flathsh_query_t *fhq)
+{
+ return njs_flathsh_alloc(fhq, NJS_FLATHSH_HASH_INITIAL_SIZE,
+ NJS_FLATHSH_ELTS_INITIAL_SIZE);
+}
+
+
+static njs_flathsh_descr_t *
+njs_flathsh_alloc(njs_flathsh_query_t *fhq, size_t hash_size, size_t elts_size)
+{
+ void *chunk;
+ size_t size;
+ njs_flathsh_descr_t *h;
+
+ njs_assert_msg(hash_size != 0 && (hash_size & (hash_size - 1)) == 0,
+ "hash_size must be a power of two");
+
+ size = njs_flathsh_chunk_size(hash_size, elts_size);
+
+ chunk = njs_flathsh_malloc(fhq, size);
+ if (njs_slow_path(chunk == NULL)) {
+ return NULL;
+ }
+
+ h = njs_flathsh_descr(chunk, hash_size);
+
+ njs_memzero(chunk, sizeof(uint32_t) * hash_size);
+
+ h->hash_mask = hash_size - 1;
+ h->elts_size = elts_size;
+ h->elts_count = 0;
+ h->elts_deleted_count = 0;
+
+ return h;
+}
+
+
+njs_flathsh_elt_t *
+njs_flathsh_add_elt(njs_flathsh_t *fh, njs_flathsh_query_t *fhq)
+{
+ njs_int_t cell_num;
+ njs_flathsh_elt_t *elt, *elts;
+ njs_flathsh_descr_t *h;
+
+ h = fh->slot;
+ if (njs_slow_path(h == NULL)) {
+ return NULL;
+ }
+
+ if (njs_slow_path(h->elts_count >= h->elts_size)) {
+ h = njs_expand_elts(fhq, fh->slot, h->elts_count + 1);
+ if (njs_slow_path(h == NULL)) {
+ return NULL;
+ }
+
+ fh->slot = h;
+ }
+
+ elts = njs_hash_elts(h);
+ elt = &elts[h->elts_count++];
+
+ elt->value = fhq->value;
+ elt->key_hash = fhq->key_hash;
+
+ cell_num = fhq->key_hash & h->hash_mask;
+ elt->next_elt = njs_hash_cells_end(h)[-cell_num - 1];
+ njs_hash_cells_end(h)[-cell_num - 1] = h->elts_count;
+
+ return elt;
+}
+
+
+static njs_flathsh_descr_t *
+njs_expand_elts(njs_flathsh_query_t *fhq, njs_flathsh_descr_t *h,
+ uint32_t count)
+{
+ void *chunk;
+ size_t size;
+ uint32_t new_elts_size, new_hash_size, new_hash_mask, i;
+ njs_int_t cell_num;
+ njs_flathsh_elt_t *elt;
+ njs_flathsh_descr_t *h_src;
+
+ new_elts_size = h->elts_size * NJS_FLATHSH_ELTS_EXPAND_FACTOR_NUM /
+ NJS_FLATHSH_ELTS_EXPAND_FACTOR_DENOM;
+ new_elts_size = njs_max(count, new_elts_size);
+
+ new_hash_size = h->hash_mask + 1;
+
+ while (new_hash_size < new_elts_size) {
+ new_hash_size = 2 * new_hash_size;
+ }
+
+ if (new_hash_size != (h->hash_mask + 1)) {
+
+ /* Expand both hash table cells and its elts. */
+
+ h_src = h;
+ size = njs_flathsh_chunk_size(new_hash_size, new_elts_size);
+ chunk = njs_flathsh_malloc(fhq, size);
+ if (njs_slow_path(chunk == NULL)) {
+ return NULL;
+ }
+
+ h = njs_flathsh_descr(chunk, new_hash_size);
+
+ memcpy(h, h_src, sizeof(njs_flathsh_descr_t) +
+ sizeof(njs_flathsh_elt_t) * h_src->elts_size);
+
+ new_hash_mask = new_hash_size - 1;
+ h->hash_mask = new_hash_mask;
+ njs_memzero(chunk, sizeof(uint32_t) * new_hash_size);
+
+ for (i = 0, elt = njs_hash_elts(h); i < h->elts_count; i++, elt++) {
+ if (elt->value != NULL) {
+ cell_num = elt->key_hash & new_hash_mask;
+ elt->next_elt = njs_hash_cells_end(h)[-cell_num - 1];
+ njs_hash_cells_end(h)[-cell_num - 1] = i + 1;
+ }
+ }
+
+ njs_flathsh_free(fhq, njs_flathsh_chunk(h_src));
+
+ } else {
+
+ size = njs_flathsh_chunk_size(new_hash_size, new_elts_size);
+
+ /* Expand elts only. */
+#ifdef NJS_FLATHSH_USE_SYSTEM_ALLOCATOR
+ chunk = realloc(njs_flathsh_chunk(h), size);
+ if (njs_slow_path(chunk == NULL)) {
+ return NULL;
+ }
+
+#else
+ chunk = fhq->proto->alloc(fhq->pool, size);
+ if (njs_slow_path(chunk == NULL)) {
+ return NULL;
+ }
+
+ memcpy(chunk, njs_flathsh_chunk(h),
+ njs_flathsh_chunk_size(h->hash_mask + 1, h->elts_size));
+
+ fhq->proto->free(fhq->pool, njs_flathsh_chunk(h), 0);
+#endif
+ h = njs_flathsh_descr(chunk, new_hash_size);
+ }
+
+ h->elts_size = new_elts_size;
+
+ return h;
+}
+
+
+njs_int_t
+njs_flathsh_find(const njs_flathsh_t *fh, njs_flathsh_query_t *fhq)
+{
+ njs_int_t cell_num, elt_num;
+ njs_flathsh_elt_t *e, *elts;
+ njs_flathsh_descr_t *h;
+
+ h = fh->slot;
+ if (njs_slow_path(h == NULL)) {
+ return NJS_DECLINED;
+ }
+
+ cell_num = fhq->key_hash & h->hash_mask;
+ elt_num = njs_hash_cells_end(h)[-cell_num - 1];
+ elts = njs_hash_elts(h);
+
+ while (elt_num != 0) {
+ e = &elts[elt_num - 1];
+
+ /* TODO: need to be replaced by atomic test. */
+
+ if (e->key_hash == fhq->key_hash &&
+ fhq->proto->test(fhq, e->value) == NJS_OK)
+ {
+ fhq->value = e->value;
+ return NJS_OK;
+ }
+
+ elt_num = e->next_elt;
+ }
+
+ return NJS_DECLINED;
+}
+
+
+njs_int_t
+njs_flathsh_insert(njs_flathsh_t *fh, njs_flathsh_query_t *fhq)
+{
+ void *tmp;
+ njs_int_t cell_num, elt_num;
+ njs_flathsh_elt_t *elt, *elts;
+ njs_flathsh_descr_t *h;
+
+ h = fh->slot;
+
+ if (h == NULL) {
+ h = njs_flathsh_new(fhq);
+ if (h == NULL) {
+ return NJS_ERROR;
+ }
+
+ fh->slot = h;
+ }
+
+ cell_num = fhq->key_hash & h->hash_mask;
+ elt_num = njs_hash_cells_end(h)[-cell_num - 1];
+ elts = njs_hash_elts(h);
+
+ while (elt_num != 0) {
+ elt = &elts[elt_num - 1];
+
+ /* TODO: need to be replaced by atomic test. */
+
+ if (elt->key_hash == fhq->key_hash &&
+ fhq->proto->test(fhq, elt->value) == NJS_OK)
+ {
+ if (fhq->replace) {
+ tmp = fhq->value;
+ fhq->value = elt->value;
+ elt->value = tmp;
+
+ return NJS_OK;
+
+ } else {
+ fhq->value = elt->value;
+
+ return NJS_DECLINED;
+ }
+ }
+
+ elt_num = elt->next_elt;
+ }
+
+ elt = njs_flathsh_add_elt(fh, fhq);
+ if (elt == NULL) {
+ return NJS_ERROR;
+ }
+
+ elt->value = fhq->value;
+
+ return NJS_OK;
+}
+
+
+static njs_flathsh_descr_t *
+njs_shrink_elts(njs_flathsh_query_t *fhq, njs_flathsh_descr_t *h)
+{
+ void *chunk;
+ njs_int_t cell_num;
+ uint32_t i, j, new_hash_size, new_hash_mask, new_elts_size;
+ njs_flathsh_elt_t *elt, *elt_src;
+ njs_flathsh_descr_t *h_src;
+
+ new_elts_size = njs_max(NJS_FLATHSH_ELTS_INITIAL_SIZE,
+ h->elts_count - h->elts_deleted_count);
+
+ njs_assert(new_elts_size <= h->elts_size);
+
+ new_hash_size = h->hash_mask + 1;
+ while ((new_hash_size / 2) >= new_elts_size) {
+ new_hash_size = new_hash_size / 2;
+ }
+
+ new_hash_mask = new_hash_size - 1;
+
+ h_src = h;
+ chunk = njs_flathsh_malloc(fhq, njs_flathsh_chunk_size(new_hash_size,
+ new_elts_size));
+ if (njs_slow_path(chunk == NULL)) {
+ return NULL;
+ }
+
+ h = njs_flathsh_descr(chunk, new_hash_size);
+ memcpy(h, h_src, sizeof(njs_flathsh_descr_t));
+
+ njs_memzero(njs_hash_cells_end(h) - new_hash_size,
+ sizeof(uint32_t) * new_hash_size);
+
+ elt_src = njs_hash_elts(h_src);
+ for (i = 0, j = 0, elt = njs_hash_elts(h); i < h->elts_count; i++) {
+ if (elt_src->value != NULL) {
+ elt->value = elt_src->value;
+ elt->key_hash = elt_src->key_hash;
+
+ cell_num = elt_src->key_hash & new_hash_mask;
+ elt->next_elt = njs_hash_cells_end(h)[-cell_num - 1];
+ njs_hash_cells_end(h)[-cell_num - 1] = j + 1;
+ j++;
+ elt++;
+ }
+
+ elt_src++;
+ }
+
+ njs_assert(j == (h->elts_count - h->elts_deleted_count));
+
+ h->hash_mask = new_hash_mask;
+ h->elts_size = new_elts_size;
+ h->elts_deleted_count = 0;
+ h->elts_count = j;
+
+ njs_flathsh_free(fhq, njs_flathsh_chunk(h_src));
+
+ return h;
+}
+
+
+njs_int_t
+njs_flathsh_delete(njs_flathsh_t *fh, njs_flathsh_query_t *fhq)
+{
+ njs_int_t cell_num, elt_num;
+ njs_flathsh_elt_t *elt, *elt_prev, *elts;
+ njs_flathsh_descr_t *h;
+
+ h = fh->slot;
+
+ if (njs_slow_path(h == NULL)) {
+ return NJS_DECLINED;
+ }
+
+ cell_num = fhq->key_hash & h->hash_mask;
+ elt_num = njs_hash_cells_end(h)[-cell_num - 1];
+ elts = njs_hash_elts(h);
+ elt_prev = NULL;
+
+ while (elt_num != 0) {
+ elt = &elts[elt_num - 1];
+
+ /* TODO: use atomic comparision. */
+
+ if (elt->key_hash == fhq->key_hash &&
+ fhq->proto->test(fhq, elt->value) == NJS_OK)
+ {
+ fhq->value = elt->value;
+
+ if (elt_prev != NULL) {
+ elt_prev->next_elt = elt->next_elt;
+
+ } else {
+ njs_hash_cells_end(h)[-cell_num - 1] = elt->next_elt;
+ }
+
+ h->elts_deleted_count++;
+
+ elt->value = NULL;
+
+ /* Shrink elts if elts_deleted_count is eligible. */
+
+ if (h->elts_deleted_count >= NJS_FLATHSH_ELTS_MINIMUM_TO_SHRINK
+ && h->elts_deleted_count
+ >= (h->elts_count / NJS_FLATHSH_ELTS_FRACTION_TO_SHRINK))
+ {
+ h = njs_shrink_elts(fhq, h);
+ if (njs_slow_path(h == NULL)) {
+ return NJS_ERROR;
+ }
+
+ fh->slot = h;
+ }
+
+ if (h->elts_deleted_count == h->elts_count) {
+ njs_flathsh_free(fhq, njs_flathsh_chunk(h));
+ fh->slot = NULL;
+ }
+
+ return NJS_OK;
+ }
+
+ elt_prev = elt;
+ elt_num = elt->next_elt;
+ }
+
+ return NJS_DECLINED;
+}
+
+
+void *
+njs_flathsh_each(const njs_flathsh_t *fh, njs_flathsh_each_t *fhe)
+{
+ void *v;
+ njs_flathsh_elt_t *elt;
+ njs_flathsh_descr_t *h;
+
+ h = fh->slot;
+ if (njs_slow_path(h == NULL)) {
+ return NULL;
+ }
+
+ elt = njs_hash_elts(h);
+
+ while (fhe->cp < h->elts_count) {
+ v = elt[fhe->cp++].value;
+ if (v != NULL) {
+ return v;
+ }
+ }
+
+ return NULL;
+}
diff -r c0f581b26e84 -r c7d2a7846b0b src/njs_flathsh.h
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/njs_flathsh.h Wed Aug 30 12:06:12 2023 -0700
@@ -0,0 +1,156 @@
+
+/*
+ * Copyright (C) NGINX, Inc.
+ */
+
+#ifndef _NJS_FLATHSH_H_INCLUDED_
+#define _NJS_FLATHSH_H_INCLUDED_
+
+
+typedef struct {
+ void *slot;
+} njs_flathsh_t;
+
+
+typedef struct {
+ uint32_t next_elt;
+ uint32_t key_hash;
+ void *value;
+} njs_flathsh_elt_t;
+
+
+typedef struct njs_flathsh_descr_s njs_flathsh_descr_t;
+typedef struct njs_flathsh_query_s njs_flathsh_query_t;
+
+typedef njs_int_t (*njs_flathsh_test_t)(njs_flathsh_query_t *fhq, void *data);
+typedef void *(*njs_flathsh_alloc_t)(void *ctx, size_t size);
+typedef void (*njs_flathsh_free_t)(void *ctx, void *p, size_t size);
+
+typedef struct njs_flathsh_proto_s njs_flathsh_proto_t;
+
+
+struct njs_flathsh_proto_s {
+ uint32_t not_used;
+ njs_flathsh_test_t test;
+ njs_flathsh_alloc_t alloc;
+ njs_flathsh_free_t free;
+};
+
+
+struct njs_flathsh_query_s {
+ uint32_t key_hash;
+ njs_str_t key;
+
+ uint8_t replace; /* 1 bit */
+ void *value;
+
+ const njs_flathsh_proto_t *proto;
+ void *pool;
+
+ /* Opaque data passed for the test function. */
+ void *data;
+};
+
+
+#define njs_flathsh_is_empty(fh) \
+ ((fh)->slot == NULL)
+
+
+#define njs_flathsh_init(fh) \
+ (fh)->slot = NULL
+
+
+#define njs_flathsh_eq(fhl, fhr) \
+ ((fhl)->slot == (fhr)->slot)
+
+
+/*
+ * njs_flathsh_find() finds a hash element. If the element has been
+ * found then it is stored in the fhq->value and njs_flathsh_find()
+ * returns NJS_OK. Otherwise NJS_DECLINED is returned.
+ *
+ * The required njs_flathsh_query_t fields: key_hash, key, proto.
+ */
+NJS_EXPORT njs_int_t njs_flathsh_find(const njs_flathsh_t *fh,
+ njs_flathsh_query_t *fhq);
+
+/*
+ * njs_flathsh_insert() adds a hash element. If the element is already
+ * present in flathsh and the fhq->replace flag is zero, then fhq->value
+ * is updated with the old element and NJS_DECLINED is returned.
+ * If the element is already present in flathsh and the fhq->replace flag
+ * is non-zero, then the old element is replaced with the new element.
+ * fhq->value is updated with the old element, and NJS_OK is returned.
+ * If the element is not present in flathsh, then it is inserted and
+ * NJS_OK is returned. The fhq->value is not changed.
+ * On memory allocation failure NJS_ERROR is returned.
+ *
+ * The required njs_flathsh_query_t fields: key_hash, key, proto, replace,
+ * value.
+ * The optional njs_flathsh_query_t fields: pool.
+ */
+NJS_EXPORT njs_int_t njs_flathsh_insert(njs_flathsh_t *fh,
+ njs_flathsh_query_t *fhq);
+
+/*
+ * njs_flathsh_delete() deletes a hash element. If the element has been
+ * found then it is removed from flathsh and is stored in the fhq->value,
+ * and NJS_OK is returned. Otherwise NJS_DECLINED is returned.
+ *
+ * The required njs_flathsh_query_t fields: key_hash, key, proto.
+ * The optional njs_flathsh_query_t fields: pool.
+ */
+NJS_EXPORT njs_int_t njs_flathsh_delete(njs_flathsh_t *fh,
+ njs_flathsh_query_t *fhq);
+
+
+typedef struct {
+ const njs_flathsh_proto_t *proto;
+ uint32_t key_hash;
+ uint32_t cp;
+} njs_flathsh_each_t;
+
More information about the nginx-devel
mailing list