From e64a3762a629c91f0e44742bc6f7948c0851e8a5 Mon Sep 17 00:00:00 2001 From: Vadim Zhestikov Date: Wed, 30 Aug 2023 12:06:12 -0700 Subject: [PATCH] Introduced flat hash. Object property enumeration order is corrected. This fixes #189 issue on Github. --- 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 | 399 +++++++++++++++--------- 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, 1159 insertions(+), 235 deletions(-) create mode 100644 src/njs_flathsh.c create mode 100644 src/njs_flathsh.h diff --git a/auto/sources b/auto/sources index 87867b51..fa80724d 100644 --- a/auto/sources +++ b/auto/sources @@ -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 --git a/external/njs_shell.c b/external/njs_shell.c index 3a92092f..f2eacb6a 100644 --- a/external/njs_shell.c +++ b/external/njs_shell.c @@ -11,7 +11,7 @@ #include #include #include -#include +#include #include #if (!defined NJS_FUZZER_TARGET && defined NJS_HAVE_READLINE) @@ -1636,7 +1636,7 @@ lvlhsh_key_test(njs_lvlhsh_query_t *lhq, void *data) 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 --git a/src/njs_array.c b/src/njs_array.c index 7a57c886..e8d1c6bd 100644 --- a/src/njs_array.c +++ b/src/njs_array.c @@ -609,10 +609,10 @@ njs_array_of(njs_vm_t *vm, njs_value_t *args, njs_uint_t nargs, static const njs_object_prop_t njs_array_constructor_properties[] = { - NJS_DECLARE_PROP_NAME("Array"), - NJS_DECLARE_PROP_LENGTH(1), + NJS_DECLARE_PROP_NAME("Array"), + 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 *first, const void *second, void *ctx) } +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 --git a/src/njs_array.h b/src/njs_array.h index e513413a..cc96936e 100644 --- a/src/njs_array.h +++ b/src/njs_array.h @@ -36,6 +36,8 @@ njs_int_t njs_array_expand(njs_vm_t *vm, njs_array_t *array, uint32_t prepend, 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 --git a/src/njs_array_buffer.c b/src/njs_array_buffer.c index 68eb8db0..dece7329 100644 --- a/src/njs_array_buffer.c +++ b/src/njs_array_buffer.c @@ -141,10 +141,10 @@ njs_array_buffer_writable(njs_vm_t *vm, njs_array_buffer_t *buffer) static const njs_object_prop_t njs_array_buffer_constructor_properties[] = { - NJS_DECLARE_PROP_NAME("ArrayBuffer"), - NJS_DECLARE_PROP_LENGTH(1), + NJS_DECLARE_PROP_NAME("ArrayBuffer"), + NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0), { diff --git a/src/njs_async.c b/src/njs_async.c index 3d47f4af..77b4605f 100644 --- a/src/njs_async.c +++ b/src/njs_async.c @@ -163,10 +163,10 @@ njs_async_context_free(njs_vm_t *vm, njs_async_ctx_t *ctx) static const njs_object_prop_t njs_async_constructor_properties[] = { - NJS_DECLARE_PROP_NAME("AsyncFunction"), - NJS_DECLARE_PROP_LENGTH(1), + NJS_DECLARE_PROP_NAME("AsyncFunction"), + NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0), }; diff --git a/src/njs_buffer.c b/src/njs_buffer.c index 7f2067fa..1d42cd06 100644 --- a/src/njs_buffer.c +++ b/src/njs_buffer.c @@ -2538,10 +2538,10 @@ const njs_object_init_t njs_buffer_prototype_init = { static const njs_object_prop_t njs_buffer_constructor_properties[] = { - NJS_DECLARE_PROP_NAME("Buffer"), - NJS_DECLARE_PROP_LENGTH(0), + NJS_DECLARE_PROP_NAME("Buffer"), + NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0), NJS_DECLARE_PROP_NATIVE("alloc", njs_buffer_alloc_safe, 0, 1), diff --git a/src/njs_date.c b/src/njs_date.c index 8aa6ea6e..788ed41d 100644 --- a/src/njs_date.c +++ b/src/njs_date.c @@ -1109,10 +1109,10 @@ njs_date_number_parse(int64_t *value, const u_char *p, const u_char *end, static const njs_object_prop_t njs_date_constructor_properties[] = { - NJS_DECLARE_PROP_NAME("Date"), - NJS_DECLARE_PROP_LENGTH(7), + NJS_DECLARE_PROP_NAME("Date"), + NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0), NJS_DECLARE_PROP_NATIVE("UTC", njs_date_utc, 7, 0), diff --git a/src/njs_encoding.c b/src/njs_encoding.c index edb16035..649adf70 100644 --- a/src/njs_encoding.c +++ b/src/njs_encoding.c @@ -256,10 +256,10 @@ const njs_object_init_t njs_text_encoder_init = { static const njs_object_prop_t njs_text_encoder_constructor_properties[] = { - NJS_DECLARE_PROP_NAME("TextEncoder"), - NJS_DECLARE_PROP_LENGTH(0), + NJS_DECLARE_PROP_NAME("TextEncoder"), + NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0), }; @@ -593,10 +593,10 @@ const njs_object_init_t njs_text_decoder_init = { static const njs_object_prop_t njs_text_decoder_constructor_properties[] = { - NJS_DECLARE_PROP_NAME("TextDecoder"), - NJS_DECLARE_PROP_LENGTH(0), + NJS_DECLARE_PROP_NAME("TextDecoder"), + NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0), }; diff --git a/src/njs_error.c b/src/njs_error.c index 4989b897..db360d04 100644 --- a/src/njs_error.c +++ b/src/njs_error.c @@ -354,10 +354,10 @@ njs_error_constructor(njs_vm_t *vm, njs_value_t *args, njs_uint_t nargs, static const njs_object_prop_t njs_error_constructor_properties[] = { - NJS_DECLARE_PROP_NAME("Error"), - NJS_DECLARE_PROP_LENGTH(1), + NJS_DECLARE_PROP_NAME("Error"), + NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0), }; @@ -370,10 +370,10 @@ const njs_object_init_t njs_error_constructor_init = { static const njs_object_prop_t njs_eval_error_constructor_properties[] = { - NJS_DECLARE_PROP_NAME("EvalError"), - NJS_DECLARE_PROP_LENGTH(1), + NJS_DECLARE_PROP_NAME("EvalError"), + NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0), }; @@ -386,10 +386,10 @@ const njs_object_init_t njs_eval_error_constructor_init = { static const njs_object_prop_t njs_internal_error_constructor_properties[] = { - NJS_DECLARE_PROP_NAME("InternalError"), - NJS_DECLARE_PROP_LENGTH(1), + NJS_DECLARE_PROP_NAME("InternalError"), + NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0), }; @@ -402,10 +402,10 @@ const njs_object_init_t njs_internal_error_constructor_init = { static const njs_object_prop_t njs_range_error_constructor_properties[] = { - NJS_DECLARE_PROP_NAME("RangeError"), - NJS_DECLARE_PROP_LENGTH(1), + NJS_DECLARE_PROP_NAME("RangeError"), + NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0), }; @@ -418,10 +418,10 @@ const njs_object_init_t njs_range_error_constructor_init = { static const njs_object_prop_t njs_reference_error_constructor_properties[] = { - NJS_DECLARE_PROP_NAME("ReferenceError"), - NJS_DECLARE_PROP_LENGTH(1), + NJS_DECLARE_PROP_NAME("ReferenceError"), + NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0), }; @@ -434,10 +434,10 @@ const njs_object_init_t njs_reference_error_constructor_init = { static const njs_object_prop_t njs_syntax_error_constructor_properties[] = { - NJS_DECLARE_PROP_NAME("SyntaxError"), - NJS_DECLARE_PROP_LENGTH(1), + NJS_DECLARE_PROP_NAME("SyntaxError"), + NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0), }; @@ -450,10 +450,10 @@ const njs_object_init_t njs_syntax_error_constructor_init = { static const njs_object_prop_t njs_type_error_constructor_properties[] = { - NJS_DECLARE_PROP_NAME("TypeError"), - NJS_DECLARE_PROP_LENGTH(1), + NJS_DECLARE_PROP_NAME("TypeError"), + NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0), }; @@ -466,10 +466,10 @@ const njs_object_init_t njs_type_error_constructor_init = { static const njs_object_prop_t njs_uri_error_constructor_properties[] = { - NJS_DECLARE_PROP_NAME("URIError"), - NJS_DECLARE_PROP_LENGTH(1), + NJS_DECLARE_PROP_NAME("URIError"), + NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0), }; @@ -482,10 +482,10 @@ const njs_object_init_t njs_uri_error_constructor_init = { static const njs_object_prop_t njs_aggregate_error_constructor_properties[] = { - NJS_DECLARE_PROP_NAME("AggregateError"), - NJS_DECLARE_PROP_LENGTH(1), + NJS_DECLARE_PROP_NAME("AggregateError"), + NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0), }; @@ -566,10 +566,10 @@ njs_memory_error_prototype_create(njs_vm_t *vm, njs_object_prop_t *prop, static const njs_object_prop_t njs_memory_error_constructor_properties[] = { - NJS_DECLARE_PROP_NAME("MemoryError"), - NJS_DECLARE_PROP_LENGTH(1), + NJS_DECLARE_PROP_NAME("MemoryError"), + NJS_DECLARE_PROP_HANDLER("prototype", njs_memory_error_prototype_create, 0, 0, 0), }; diff --git a/src/njs_flathsh.c b/src/njs_flathsh.c new file mode 100644 index 00000000..fb799bba --- /dev/null +++ b/src/njs_flathsh.c @@ -0,0 +1,560 @@ + +/* + * Copyright (C) NGINX, Inc. + */ + +#include + +/* + * 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 --git a/src/njs_flathsh.h b/src/njs_flathsh.h new file mode 100644 index 00000000..b3d39d20 --- /dev/null +++ b/src/njs_flathsh.h @@ -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; + + +#define njs_flathsh_each_init(lhe, _proto) \ + do { \ + njs_memzero(lhe, sizeof(njs_flathsh_each_t)); \ + (lhe)->proto = _proto; \ + } while (0) + + +NJS_EXPORT void *njs_flathsh_each(const njs_flathsh_t *fh, + njs_flathsh_each_t *fhe); + +/* + * Add element into hash. + * The element value is not initialized. + * Returns NULL if memory error in hash expand. + */ +NJS_EXPORT njs_flathsh_elt_t *njs_flathsh_add_elt(njs_flathsh_t *fh, + njs_flathsh_query_t *fhq); + +NJS_EXPORT njs_flathsh_descr_t *njs_flathsh_new(njs_flathsh_query_t *fhq); + + +/* Temporary backward compatibility .*/ + +typedef struct njs_flathsh_query_s njs_lvlhsh_query_t; + +#define NJS_LVLHSH_DEFAULT 0 +#define NJS_LVLHSH_LARGE_SLAB 0 + +typedef struct njs_flathsh_proto_s njs_lvlhsh_proto_t; + +#define njs_lvlhsh_is_empty njs_flathsh_is_empty +#define njs_lvlhsh_init njs_flathsh_init +#define njs_lvlhsh_eq njs_flathsh_eq +#define njs_lvlhsh_t njs_flathsh_t +#define njs_lvlhsh_each_t njs_flathsh_each_t +#define njs_lvlhsh_find(lh, lhq) njs_flathsh_find(lh, lhq) +#define njs_lvlhsh_insert(lh, lhq) njs_flathsh_insert(lh, lhq) +#define njs_lvlhsh_delete(lh, lhq) njs_flathsh_delete(lh, lhq) +#define njs_lvlhsh_each_init(lhe, _proto) njs_flathsh_each_init(lhe, _proto) +#define njs_lvlhsh_each(lh, lhe) njs_flathsh_each(lh, lhe) + + +#endif /* _NJS_FLATHSH_H_INCLUDED_ */ diff --git a/src/njs_function.c b/src/njs_function.c index 1d91fde3..da269c4c 100644 --- a/src/njs_function.c +++ b/src/njs_function.c @@ -1157,10 +1157,10 @@ fail: static const njs_object_prop_t njs_function_constructor_properties[] = { - NJS_DECLARE_PROP_NAME("Function"), - NJS_DECLARE_PROP_LENGTH(1), + NJS_DECLARE_PROP_NAME("Function"), + NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0), }; @@ -1431,10 +1431,10 @@ njs_function_prototype_bind(njs_vm_t *vm, njs_value_t *args, njs_uint_t nargs, static const njs_object_prop_t njs_function_prototype_properties[] = { - NJS_DECLARE_PROP_NAME(""), - NJS_DECLARE_PROP_LENGTH(0), + NJS_DECLARE_PROP_NAME(""), + NJS_DECLARE_PROP_HANDLER("constructor", njs_object_prototype_create_constructor, 0, 0, NJS_OBJECT_PROP_VALUE_CW), diff --git a/src/njs_main.h b/src/njs_main.h index b02a4311..25d7d31e 100644 --- a/src/njs_main.h +++ b/src/njs_main.h @@ -25,7 +25,7 @@ #include #include #include -#include +#include #include #include #include diff --git a/src/njs_number.c b/src/njs_number.c index ebd64d32..9f2d6512 100644 --- a/src/njs_number.c +++ b/src/njs_number.c @@ -439,10 +439,10 @@ njs_number_is_finite(njs_vm_t *vm, njs_value_t *args, njs_uint_t nargs, static const njs_object_prop_t njs_number_constructor_properties[] = { - NJS_DECLARE_PROP_NAME("Number"), - NJS_DECLARE_PROP_LENGTH(1), + NJS_DECLARE_PROP_NAME("Number"), + NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0), NJS_DECLARE_PROP_VALUE("EPSILON", njs_value(NJS_NUMBER, 1, DBL_EPSILON), 0), diff --git a/src/njs_object.c b/src/njs_object.c index 91ae922a..683cabde 100644 --- a/src/njs_object.c +++ b/src/njs_object.c @@ -872,229 +872,346 @@ njs_object_enumerate_object(njs_vm_t *vm, const njs_object_t *object, } +#define njs_process_prop(vm, prop, type, items, items_symbol) \ + if (!(type & NJS_ENUM_SYMBOL && njs_is_symbol(&prop->name))) { \ + /* \ + * prop from shared_hash is not symbol: \ + * add to items before props from hash \ + */ \ + \ + ret = njs_array_add(vm, items, &prop->name); \ + if (njs_slow_path(ret != NJS_OK)) { \ + return NJS_ERROR; \ + } \ + \ + } else { \ + /* \ + * prop from shared_hash is symbol: \ + * add to items_symbol \ + */ \ + ret = njs_array_add(vm, items_symbol, &prop->name); \ + if (njs_slow_path(ret != NJS_OK)) { \ + return NJS_ERROR; \ + } \ + } + + static njs_int_t -njs_object_own_enumerate_object(njs_vm_t *vm, const njs_object_t *object, +njs_get_own_ordered_keys(njs_vm_t *vm, const njs_object_t *object, const njs_object_t *parent, njs_array_t *items, njs_object_enum_t kind, njs_object_enum_type_t type, njs_bool_t all) { + double num; + uint32_t items_length; njs_int_t ret; - njs_value_t value, *v; - njs_array_t *entry; + njs_array_t *items_string, *items_symbol; njs_lvlhsh_each_t lhe; njs_object_prop_t *prop, *ext_prop; njs_lvlhsh_query_t lhq; const njs_lvlhsh_t *hash; + items_length = items->length; + + items_string = njs_array_alloc(vm, 1, 0, NJS_ARRAY_SPARE); + if (njs_slow_path(items_string == NULL)) { + return NJS_ERROR; + } + + items_symbol = njs_array_alloc(vm, 1, 0, NJS_ARRAY_SPARE); + if (njs_slow_path(items_symbol == NULL)) { + return NJS_ERROR; + } + lhq.proto = &njs_object_hash_proto; njs_lvlhsh_each_init(&lhe, &njs_object_hash_proto); - hash = &object->hash; + hash = &object->shared_hash; - switch (kind) { - case NJS_ENUM_KEYS: - for ( ;; ) { - prop = njs_lvlhsh_each(hash, &lhe); + for ( ;; ) { + prop = njs_lvlhsh_each(hash, &lhe); - if (prop == NULL) { - break; - } + if (prop == NULL) { + break; + } - if (!njs_is_enumerable(&prop->name, type)) { + if (!njs_is_enumerable(&prop->name, type)) { + continue; + } + + njs_object_property_key_set(&lhq, &prop->name, lhe.key_hash); + + ext_prop = njs_object_exist_in_proto(parent, object, &lhq); + if (ext_prop != NULL) { + continue; + } + + ret = njs_lvlhsh_find(&object->hash, &lhq); + if (ret != NJS_OK) { + + if (!(prop->enumerable || all)) { continue; } - njs_object_property_key_set(&lhq, &prop->name, lhe.key_hash); + /* prop is: !in_hash && in_shared_hash */ - ext_prop = njs_object_exist_in_proto(parent, object, &lhq); + num = njs_string_to_index(&prop->name); + if (!njs_number_is_integer_index(num)) { + njs_process_prop(vm, prop, type, items_string, items_symbol); - if (ext_prop == NULL && prop->type != NJS_WHITEOUT - && (prop->enumerable || all)) - { + } else { ret = njs_array_add(vm, items, &prop->name); if (njs_slow_path(ret != NJS_OK)) { return NJS_ERROR; } } - } - - njs_lvlhsh_each_init(&lhe, &njs_object_hash_proto); - hash = &object->shared_hash; - for ( ;; ) { - prop = njs_lvlhsh_each(hash, &lhe); - - if (prop == NULL) { - break; - } + } else { - if (!njs_is_enumerable(&prop->name, type)) { + if (!(((njs_object_prop_t *)(lhq.value))->enumerable || all)) { continue; } - njs_object_property_key_set(&lhq, &prop->name, lhe.key_hash); + /* prop is: in_hash && in_shared_hash */ - ret = njs_lvlhsh_find(&object->hash, &lhq); + num = njs_string_to_index(&prop->name); + if (!njs_number_is_integer_index(num)) { - if (ret != NJS_OK) { - ext_prop = njs_object_exist_in_proto(parent, object, &lhq); + njs_object_prop_t *hash_prop = lhq.value; - if (ext_prop == NULL && (prop->enumerable || all)) { - ret = njs_array_add(vm, items, &prop->name); - if (njs_slow_path(ret != NJS_OK)) { - return NJS_ERROR; - } + /* select names of prop which are not deleted and + * not deleted and created again i.e., + * they are replaced shared hash props + */ + if (hash_prop->type != NJS_WHITEOUT && + !(hash_prop->enum_in_object_hash)) + { + njs_process_prop(vm, prop, type, items_string, + items_symbol); } } } + } - break; + njs_lvlhsh_each_init(&lhe, &njs_object_hash_proto); + hash = &object->hash; - case NJS_ENUM_VALUES: - for ( ;; ) { - prop = njs_lvlhsh_each(hash, &lhe); + for ( ;; ) { + prop = njs_lvlhsh_each(hash, &lhe); - if (prop == NULL) { - break; - } + if (prop == NULL) { + break; + } - if (!njs_is_enumerable(&prop->name, type)) { - continue; - } + if (!njs_is_enumerable(&prop->name, type) || + !(prop->enumerable || all) || + prop->type == NJS_WHITEOUT) + { + continue; + } - njs_object_property_key_set(&lhq, &prop->name, lhe.key_hash); + njs_object_property_key_set(&lhq, &prop->name, lhe.key_hash); - ext_prop = njs_object_exist_in_proto(parent, object, &lhq); + ext_prop = njs_object_exist_in_proto(parent, object, &lhq); + if (ext_prop != NULL) { + continue; + } - if (ext_prop == NULL && prop->type != NJS_WHITEOUT - && (prop->enumerable || all)) - { - v = (prop->type != NJS_ACCESSOR) - ? njs_prop_value(prop) - : njs_value_arg(&njs_value_undefined); - ret = njs_array_add(vm, items, v); - if (njs_slow_path(ret != NJS_OK)) { - return NJS_ERROR; - } + num = njs_string_to_index(&prop->name); + if (njs_number_is_integer_index(num)) { + + ret = njs_array_add(vm, items, &prop->name); + if (njs_slow_path(ret != NJS_OK)) { + return NJS_ERROR; } - } - njs_lvlhsh_each_init(&lhe, &njs_object_hash_proto); - hash = &object->shared_hash; + } else { - for ( ;; ) { - prop = njs_lvlhsh_each(hash, &lhe); + ret = njs_lvlhsh_find(&object->shared_hash, &lhq); + if (ret != NJS_OK) { + /* prop is: in_hash && !in_shared_hash */ - if (prop == NULL) { - break; - } + /* select names of not deleted props */ - if (!njs_is_enumerable(&prop->name, type)) { - continue; - } + njs_process_prop(vm, prop, type, items_string, + items_symbol); - njs_object_property_key_set(&lhq, &prop->name, lhe.key_hash); + } else { + /* prop is: in_hash && in_shared_hash */ - ret = njs_lvlhsh_find(&object->hash, &lhq); + /* select names of not deleted and created again */ - if (ret != NJS_OK) { - ext_prop = njs_object_exist_in_proto(parent, object, &lhq); - - if (ext_prop == NULL && (prop->enumerable || all)) { - v = (prop->type != NJS_ACCESSOR) - ? njs_prop_value(prop) - : njs_value_arg(&njs_value_undefined); - ret = njs_array_add(vm, items, v); - if (njs_slow_path(ret != NJS_OK)) { - return NJS_ERROR; - } + if (prop->enum_in_object_hash) { + njs_process_prop(vm, prop, type, items_string, + items_symbol); } } } + } - break; + if (items->length >= 2) { + njs_qsort(&items->start[items_length], items->length-items_length, + sizeof(njs_value_t), njs_array_indices_handler_nums, NULL); + } - case NJS_ENUM_BOTH: - for ( ;; ) { - prop = njs_lvlhsh_each(hash, &lhe); + if (items_string->length != 0) { + ret = njs_array_expand(vm, items, 0, items_string->length); + if (njs_slow_path(ret != NJS_OK)) { + return NJS_ERROR; + } - if (prop == NULL) { - break; - } + memcpy(&items->start[items->length], &items_string->start[0], + items_string->length * sizeof(njs_value_t)); - if (!njs_is_enumerable(&prop->name, type)) { - continue; - } + items->length += items_string->length; + } - njs_object_property_key_set(&lhq, &prop->name, lhe.key_hash); + if (items_symbol->length != 0) { + ret = njs_array_expand(vm, items, 0, items_symbol->length); + if (njs_slow_path(ret != NJS_OK)) { + return NJS_ERROR; + } - ext_prop = njs_object_exist_in_proto(parent, object, &lhq); + memcpy(&items->start[items->length], &items_symbol->start[0], + items_symbol->length * sizeof(njs_value_t)); - if (ext_prop == NULL && prop->type != NJS_WHITEOUT - && (prop->enumerable || all)) - { - entry = njs_array_alloc(vm, 0, 2, 0); - if (njs_slow_path(entry == NULL)) { - return NJS_ERROR; - } + items->length += items_symbol->length; + } - njs_string_copy(&entry->start[0], &prop->name); + njs_array_destroy(vm, items_string); + njs_array_destroy(vm, items_symbol); - v = (prop->type != NJS_ACCESSOR) - ? njs_prop_value(prop) - : njs_value_arg(&njs_value_undefined); + return NJS_OK; +} - njs_value_assign(&entry->start[1], v); - njs_set_array(&value, entry); +static njs_int_t +njs_add_obj_prop_kind(njs_vm_t *vm, const njs_object_t *object, + const njs_lvlhsh_t *hash, njs_lvlhsh_query_t *lhq, + njs_object_enum_t kind, njs_array_t *items) +{ + njs_int_t ret; + njs_value_t value, *v, value1; + njs_array_t *entry; + njs_object_prop_t *prop; - ret = njs_array_add(vm, items, &value); - if (njs_slow_path(ret != NJS_OK)) { - return NJS_ERROR; - } - } + ret = njs_lvlhsh_find(hash, lhq); + if (ret != NJS_OK) { + return NJS_DECLINED; + } + + prop = (njs_object_prop_t *) (lhq->value); + + if (prop->type != NJS_ACCESSOR) { + v = njs_prop_value(prop); + + } else { + if (njs_is_data_descriptor(prop)) { + v = njs_prop_value(prop); + goto add; } - njs_lvlhsh_each_init(&lhe, &njs_object_hash_proto); - hash = &object->shared_hash; + if (njs_prop_getter(prop) == NULL) { + v = njs_value_arg(&njs_value_undefined); + goto add; + } - for ( ;; ) { - prop = njs_lvlhsh_each(hash, &lhe); + v = &value1; - if (prop == NULL) { - break; - } + njs_set_object(&value, (njs_object_t *) object); + ret = njs_function_apply(vm, njs_prop_getter(prop), &value, 1, v); + if (ret != NJS_OK) { + return NJS_ERROR; + } + } - if (!njs_is_enumerable(&prop->name, type)) { - continue; - } +add: + if (kind != NJS_ENUM_VALUES) { + entry = njs_array_alloc(vm, 0, 2, 0); + if (njs_slow_path(entry == NULL)) { + return NJS_ERROR; + } + + njs_string_copy(&entry->start[0], &prop->name); + njs_value_assign(&entry->start[1], v); + + njs_set_array(&value, entry); + v = &value; + } + + ret = njs_array_add(vm, items, v); + if (njs_slow_path(ret != NJS_OK)) { + return NJS_ERROR; + } - njs_object_property_key_set(&lhq, &prop->name, lhe.key_hash); + return NJS_OK; +} - ret = njs_lvlhsh_find(&object->hash, &lhq); - if (ret != NJS_OK && (prop->enumerable || all)) { - ext_prop = njs_object_exist_in_proto(parent, object, &lhq); +static njs_int_t +njs_object_own_enumerate_object(njs_vm_t *vm, const njs_object_t *object, + const njs_object_t *parent, njs_array_t *items, njs_object_enum_t kind, + njs_object_enum_type_t type, njs_bool_t all) +{ + njs_int_t ret; + uint32_t i; + njs_array_t *items_sorted; + njs_lvlhsh_each_t lhe; + njs_lvlhsh_query_t lhq; - if (ext_prop == NULL) { - entry = njs_array_alloc(vm, 0, 2, 0); - if (njs_slow_path(entry == NULL)) { - return NJS_ERROR; - } + lhq.proto = &njs_object_hash_proto; + + njs_lvlhsh_each_init(&lhe, &njs_object_hash_proto); - njs_string_copy(&entry->start[0], &prop->name); - njs_value_assign(&entry->start[1], njs_prop_value(prop)); + switch (kind) { + case NJS_ENUM_KEYS: + ret = njs_get_own_ordered_keys(vm, object, parent, items, kind, type, + all); + if (ret != NJS_OK) { + return NJS_ERROR; + } - njs_set_array(&value, entry); + break; - ret = njs_array_add(vm, items, &value); - if (njs_slow_path(ret != NJS_OK)) { - return NJS_ERROR; - } + case NJS_ENUM_VALUES: + case NJS_ENUM_BOTH: + items_sorted = njs_array_alloc(vm, 1, 0, NJS_ARRAY_SPARE); + if (njs_slow_path(items == NULL)) { + return NJS_ERROR; + } + + ret = njs_get_own_ordered_keys(vm, object, parent, items_sorted, kind, + type, all); + if (ret != NJS_OK) { + return NJS_ERROR; + } + + for (i = 0; i< items_sorted->length; i++) { + + lhe.key_hash = 0; + njs_object_property_key_set(&lhq, &items_sorted->start[i], + lhe.key_hash); + + ret = njs_add_obj_prop_kind(vm, object, &object->hash, &lhq, kind, + items); + if (ret != NJS_DECLINED) { + if (ret != NJS_OK) { + return NJS_ERROR; + } + + } else { + ret = njs_add_obj_prop_kind(vm, object, &object->shared_hash, + &lhq, kind, items); + njs_assert(ret != NJS_DECLINED); + if (ret != NJS_OK) { + return NJS_ERROR; } } } + njs_array_destroy(vm, items_sorted); + break; + } return NJS_OK; @@ -1930,10 +2047,10 @@ njs_property_prototype_create(njs_vm_t *vm, njs_lvlhsh_t *hash, static const njs_object_prop_t njs_object_constructor_properties[] = { - NJS_DECLARE_PROP_NAME("Object"), - NJS_DECLARE_PROP_LENGTH(1), + NJS_DECLARE_PROP_NAME("Object"), + NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0), NJS_DECLARE_PROP_NATIVE("create", njs_object_create, 2, 0), diff --git a/src/njs_object_prop.c b/src/njs_object_prop.c index e154f064..c9147bba 100644 --- a/src/njs_object_prop.c +++ b/src/njs_object_prop.c @@ -68,6 +68,7 @@ njs_object_prop_alloc2(njs_vm_t *vm, const njs_value_t *name, } prop->type = type; + prop->enum_in_object_hash = 0; if (flags != NJS_OBJECT_PROP_UNSET) { prop->enumerable = !!(flags & NJS_OBJECT_PROP_ENUMERABLE); diff --git a/src/njs_promise.c b/src/njs_promise.c index d9cebe04..79b5caf0 100644 --- a/src/njs_promise.c +++ b/src/njs_promise.c @@ -1846,10 +1846,10 @@ njs_promise_species(njs_vm_t *vm, njs_value_t *args, njs_uint_t nargs, static const njs_object_prop_t njs_promise_constructor_properties[] = { - NJS_DECLARE_PROP_NAME("Promise"), - NJS_DECLARE_PROP_LENGTH(1), + NJS_DECLARE_PROP_NAME("Promise"), + NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0), NJS_DECLARE_PROP_NATIVE("resolve", njs_promise_object_resolve, 1, 0), diff --git a/src/njs_regexp.c b/src/njs_regexp.c index e432651c..37d95d29 100644 --- a/src/njs_regexp.c +++ b/src/njs_regexp.c @@ -1772,10 +1772,10 @@ done: static const njs_object_prop_t njs_regexp_constructor_properties[] = { - NJS_DECLARE_PROP_NAME("RegExp"), - NJS_DECLARE_PROP_LENGTH(2), + NJS_DECLARE_PROP_NAME("RegExp"), + NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0), }; diff --git a/src/njs_string.c b/src/njs_string.c index 24dff724..ed07509f 100644 --- a/src/njs_string.c +++ b/src/njs_string.c @@ -647,10 +647,10 @@ njs_string_constructor(njs_vm_t *vm, njs_value_t *args, njs_uint_t nargs, static const njs_object_prop_t njs_string_constructor_properties[] = { - NJS_DECLARE_PROP_NAME("String"), - NJS_DECLARE_PROP_LENGTH(1), + NJS_DECLARE_PROP_NAME("String"), + NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0), NJS_DECLARE_PROP_NATIVE("fromCharCode", njs_string_from_char_code, 1, 0), diff --git a/src/njs_symbol.c b/src/njs_symbol.c index 05f5ae51..a284d4e9 100644 --- a/src/njs_symbol.c +++ b/src/njs_symbol.c @@ -231,10 +231,10 @@ njs_symbol_key_for(njs_vm_t *vm, njs_value_t *args, njs_uint_t nargs, static const njs_object_prop_t njs_symbol_constructor_properties[] = { - NJS_DECLARE_PROP_NAME("Symbol"), - NJS_DECLARE_PROP_LENGTH(0), + NJS_DECLARE_PROP_NAME("Symbol"), + NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0), NJS_DECLARE_PROP_NATIVE("for", njs_symbol_for, 1, 0), diff --git a/src/njs_typed_array.c b/src/njs_typed_array.c index 3bc37b22..945c0e2d 100644 --- a/src/njs_typed_array.c +++ b/src/njs_typed_array.c @@ -2194,10 +2194,10 @@ njs_typed_array_constructor_intrinsic(njs_vm_t *vm, njs_value_t *args, static const njs_object_prop_t njs_typed_array_constructor_props[] = { - NJS_DECLARE_PROP_NAME("TypedArray"), - NJS_DECLARE_PROP_LENGTH(0), + NJS_DECLARE_PROP_NAME("TypedArray"), + NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0), { @@ -2431,10 +2431,10 @@ memory_error: static const njs_object_prop_t njs_data_view_constructor_props[] = { - NJS_DECLARE_PROP_NAME("DataView"), - NJS_DECLARE_PROP_LENGTH(1), + NJS_DECLARE_PROP_NAME("DataView"), + NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0), }; @@ -2761,10 +2761,10 @@ const njs_object_type_init_t njs_data_view_type_init = { static const njs_object_prop_t njs_typed_array_u8_constructor_props[] = { - NJS_DECLARE_PROP_NAME("Uint8Array"), - NJS_DECLARE_PROP_LENGTH(3), + NJS_DECLARE_PROP_NAME("Uint8Array"), + NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0), NJS_DECLARE_PROP_LVALUE("BYTES_PER_ELEMENT", njs_value(NJS_NUMBER, 1, 1), @@ -2856,10 +2856,10 @@ const njs_object_type_init_t njs_typed_array_u8clamped_type_init = { static const njs_object_prop_t njs_typed_array_i8_constructor_props[] = { - NJS_DECLARE_PROP_NAME("Int8Array"), - NJS_DECLARE_PROP_LENGTH(3), + NJS_DECLARE_PROP_NAME("Int8Array"), + NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0), NJS_DECLARE_PROP_LVALUE("BYTES_PER_ELEMENT", njs_value(NJS_NUMBER, 1, 1), @@ -2901,10 +2901,10 @@ const njs_object_type_init_t njs_typed_array_i8_type_init = { static const njs_object_prop_t njs_typed_array_u16_constructor_props[] = { - NJS_DECLARE_PROP_NAME("Uint16Array"), - NJS_DECLARE_PROP_LENGTH(3), + NJS_DECLARE_PROP_NAME("Uint16Array"), + NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0), NJS_DECLARE_PROP_LVALUE("BYTES_PER_ELEMENT", njs_value(NJS_NUMBER, 1, 2), @@ -2946,10 +2946,10 @@ const njs_object_type_init_t njs_typed_array_u16_type_init = { static const njs_object_prop_t njs_typed_array_i16_constructor_props[] = { - NJS_DECLARE_PROP_NAME("Int16Array"), - NJS_DECLARE_PROP_LENGTH(3), + NJS_DECLARE_PROP_NAME("Int16Array"), + NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0), NJS_DECLARE_PROP_LVALUE("BYTES_PER_ELEMENT", njs_value(NJS_NUMBER, 1, 2), @@ -2991,10 +2991,10 @@ const njs_object_type_init_t njs_typed_array_i16_type_init = { static const njs_object_prop_t njs_typed_array_u32_constructor_props[] = { - NJS_DECLARE_PROP_NAME("Uint32Array"), - NJS_DECLARE_PROP_LENGTH(3), + NJS_DECLARE_PROP_NAME("Uint32Array"), + NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0), NJS_DECLARE_PROP_LVALUE("BYTES_PER_ELEMENT", njs_value(NJS_NUMBER, 1, 4), @@ -3036,10 +3036,10 @@ const njs_object_type_init_t njs_typed_array_u32_type_init = { static const njs_object_prop_t njs_typed_array_i32_constructor_props[] = { - NJS_DECLARE_PROP_NAME("Int32Array"), - NJS_DECLARE_PROP_LENGTH(3), + NJS_DECLARE_PROP_NAME("Int32Array"), + NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0), NJS_DECLARE_PROP_LVALUE("BYTES_PER_ELEMENT", njs_value(NJS_NUMBER, 1, 4), @@ -3081,10 +3081,10 @@ const njs_object_type_init_t njs_typed_array_i32_type_init = { static const njs_object_prop_t njs_typed_array_f32_constructor_props[] = { - NJS_DECLARE_PROP_NAME("Float32Array"), - NJS_DECLARE_PROP_LENGTH(3), + NJS_DECLARE_PROP_NAME("Float32Array"), + NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0), NJS_DECLARE_PROP_LVALUE("BYTES_PER_ELEMENT", njs_value(NJS_NUMBER, 1, 4), @@ -3126,10 +3126,10 @@ const njs_object_type_init_t njs_typed_array_f32_type_init = { static const njs_object_prop_t njs_typed_array_f64_constructor_props[] = { - NJS_DECLARE_PROP_NAME("Float64Array"), - NJS_DECLARE_PROP_LENGTH(3), + NJS_DECLARE_PROP_NAME("Float64Array"), + NJS_DECLARE_PROP_HANDLER("prototype", njs_object_prototype_create, 0, 0, 0), NJS_DECLARE_PROP_LVALUE("BYTES_PER_ELEMENT", njs_value(NJS_NUMBER, 1, 8), diff --git a/src/njs_value.c b/src/njs_value.c index 361e11f6..407baed9 100644 --- a/src/njs_value.c +++ b/src/njs_value.c @@ -799,7 +799,7 @@ njs_object_property_query(njs_vm_t *vm, njs_property_query_t *pq, } if (pq->own) { - pq->own_whiteout = prop; + pq->own_whiteout = &proto->hash; } } else { @@ -895,7 +895,7 @@ njs_array_property_query(njs_vm_t *vm, njs_property_query_t *pq, } if (pq->own) { - pq->own_whiteout = prop; + pq->own_whiteout = &array->object.hash; } return NJS_DECLINED; @@ -1221,8 +1221,10 @@ njs_value_property_set(njs_vm_t *vm, njs_value_t *value, njs_value_t *key, njs_int_t ret; njs_array_t *array; njs_value_t retval; + njs_flathsh_elt_t *elt; njs_object_prop_t *prop; njs_typed_array_t *tarray; + njs_flathsh_descr_t *h; njs_property_query_t pq; static const njs_str_t length_key = njs_str("length"); @@ -1352,12 +1354,44 @@ slow_path: case NJS_DECLINED: if (njs_slow_path(pq.own_whiteout != NULL)) { - /* Previously deleted property. */ + + /* + * Previously deleted property. + * + * delete it, and then + * insert it again as new one to preserve insertion order. + */ + if (!njs_object(value)->extensible) { goto fail; } - prop = pq.own_whiteout; + pq.lhq.pool = vm->mem_pool; + + int rc = njs_lvlhsh_delete(pq.own_whiteout, &pq.lhq); + if (rc != NJS_OK) { + return NJS_ERROR; + } + + h = pq.own_whiteout->slot; + + if (h == NULL) { + h = njs_flathsh_new(&pq.lhq); + if (njs_slow_path(h == NULL)) { + return NJS_ERROR; + } + + pq.own_whiteout->slot = h; + } + + elt = njs_flathsh_add_elt(pq.own_whiteout, &pq.lhq); + if (njs_slow_path(elt == NULL)) { + return NJS_ERROR; + } + + elt->value = (&pq.lhq)->value; + + prop = (njs_object_prop_t *) elt->value; prop->type = NJS_PROPERTY; prop->enumerable = 1; @@ -1529,6 +1563,7 @@ slow_path: } prop->type = NJS_WHITEOUT; + prop->enum_in_object_hash = 1; return NJS_OK; } diff --git a/src/njs_value.h b/src/njs_value.h index 9491702a..0ce2ee03 100644 --- a/src/njs_value.h +++ b/src/njs_value.h @@ -379,6 +379,7 @@ struct njs_object_prop_s { #define njs_prop_setter(_p) (_p)->u.accessor.setter njs_object_prop_type_t type:8; /* 3 bits */ + njs_object_prop_type_t enum_in_object_hash:8; /* 3 bits */ njs_object_attribute_t writable:8; /* 2 bits */ njs_object_attribute_t enumerable:8; /* 2 bits */ @@ -395,8 +396,8 @@ typedef struct { njs_object_prop_t scratch; njs_value_t key; + njs_lvlhsh_t *own_whiteout; - njs_object_prop_t *own_whiteout; uint8_t temp; uint8_t own; } njs_property_query_t; diff --git a/src/njs_vm.c b/src/njs_vm.c index 920f836f..e9601f55 100644 --- a/src/njs_vm.c +++ b/src/njs_vm.c @@ -1754,7 +1754,7 @@ njs_vm_value_string_copy(njs_vm_t *vm, njs_str_t *retval, void * njs_lvlhsh_alloc(void *data, size_t size) { - return njs_mp_align(data, size, size); + return njs_mp_align(data, NJS_MAX_ALIGNMENT, size); } diff --git a/src/test/lvlhsh_unit_test.c b/src/test/lvlhsh_unit_test.c index a06cfd19..6172c1c7 100644 --- a/src/test/lvlhsh_unit_test.c +++ b/src/test/lvlhsh_unit_test.c @@ -22,7 +22,7 @@ lvlhsh_unit_test_key_test(njs_lvlhsh_query_t *lhq, void *data) static void * lvlhsh_unit_test_pool_alloc(void *pool, size_t size) { - return njs_mp_align(pool, size, size); + return njs_mp_align(pool, NJS_MAX_ALIGNMENT, size); } diff --git a/src/test/njs_externals_test.c b/src/test/njs_externals_test.c index 2fa75109..c4230877 100644 --- a/src/test/njs_externals_test.c +++ b/src/test/njs_externals_test.c @@ -74,7 +74,7 @@ lvlhsh_unit_test_key_test(njs_lvlhsh_query_t *lhq, void *data) static void * lvlhsh_unit_test_pool_alloc(void *pool, size_t size) { - return njs_mp_align(pool, size, size); + return njs_mp_align(pool, NJS_MAX_ALIGNMENT, size); } diff --git a/src/test/njs_unit_test.c b/src/test/njs_unit_test.c index f58e968e..b94e8391 100644 --- a/src/test/njs_unit_test.c +++ b/src/test/njs_unit_test.c @@ -4017,7 +4017,7 @@ static njs_unit_test_t njs_test[] = njs_str("2,true,0,true") }, { njs_str("njs.dump({break:1,3:2,'a':4,\"b\":2,true:1,null:0,async:2})"), - njs_str("{break:1,3:2,a:4,b:2,true:1,null:0,async:2}") }, + njs_str("{3:2,break:1,a:4,b:2,true:1,null:0,async:2}") }, { njs_str("var o1 = {a:1,b:2}, o2 = {c:3}; o1.a + o2.c"), njs_str("4") }, @@ -4425,7 +4425,7 @@ static njs_unit_test_t njs_test[] = njs_str("[[1,2,3,,4,5],6]") }, { njs_str("njs.dump([].concat([1,2,3], {length:3, 1:4, 2:5}))"), - njs_str("[1,2,3,{length:3,1:4,2:5}]") }, + njs_str("[1,2,3,{1:4,2:5,length:3}]") }, { njs_str("Array.prototype[1] = 1; var x = [0]; x.length = 2; " "x.concat().hasOwnProperty('1') === true"), @@ -4687,12 +4687,12 @@ static njs_unit_test_t njs_test[] = { njs_str("var obj = {length: 5, 3: 1}; [].copyWithin.call(obj, 0, 3);" "Object.keys(obj)"), - njs_str("length,3,0") }, + njs_str("0,3,length") }, { njs_str("var obj = {length: 5, 1: 'a', 2: 'b', 3: 'c', 4: 'd', 5: 'e'};" "[].copyWithin.call(obj, 0, -2, -1);" "Object.keys(obj) + '|' + Object.values(obj)"), - njs_str("length,1,2,3,4,5,0|5,a,b,c,d,e,c") }, + njs_str("0,1,2,3,4,5,length|c,a,b,c,d,e,5") }, { njs_str("var o = {length:1}; Object.defineProperty(o, '0', {get:()=>{throw Error('Oops')}});" "Array.prototype.copyWithin.call(o, 0, 0)"), @@ -5665,12 +5665,12 @@ static njs_unit_test_t njs_test[] = { njs_str("var a = Array.prototype.fill.apply(" "Object({length: 40}), [\"a\", 1, 20]); Object.values(a)"), - njs_str("a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,40,a,a,a,a") }, + njs_str("a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,40") }, { njs_str("var a = Array.prototype.fill.apply({length: " "{ valueOf: function() { return 40 }}}, [\"a\", 1, 20]);" "Object.values(a)"), - njs_str("a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,[object Object],a,a,a,a") }, + njs_str("a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,[object Object]") }, { njs_str("[NaN, false, ''].map(" "(x) => Array.prototype.fill.call(x)" @@ -7381,7 +7381,7 @@ static njs_unit_test_t njs_test[] = { njs_str("var a = {length:3, 0:'Z', 2:'A'};" "njs.dump([Array.prototype.toSorted.call(a), Array.prototype.sort.call(a)])"), - njs_str("[['A','Z',undefined],{length:3,0:'A',1:'Z'}]") }, + njs_str("[['A','Z',undefined],{0:'A',1:'Z',length:3}]") }, { njs_str("var a = {length: 1}; a.__proto__ = {0:'A'};" "njs.dump([Array.prototype.toSorted.call(a), Array.prototype.sort.call(a)])"), @@ -14444,7 +14444,7 @@ static njs_unit_test_t njs_test[] = { njs_str("var s = new String('αβ'); s.two = null; s[3] = true;" "Object.entries(s)"), - njs_str("0,α,1,β,two,,3,true") }, + njs_str("0,α,1,β,3,true,two,") }, { njs_str("Object.entries(true)"), njs_str("") }, @@ -15407,10 +15407,10 @@ static njs_unit_test_t njs_test[] = njs_str("a,b") }, { njs_str("Object.getOwnPropertyNames(Object.defineProperty([], 'b', {}))"), - njs_str("b,length") }, + njs_str("length,b") }, { njs_str("Object.getOwnPropertyNames(Object.defineProperty(new String(), 'b', {}))"), - njs_str("b,length") }, + njs_str("length,b") }, { njs_str("Object.getOwnPropertyNames([1,2,3])"), njs_str("0,1,2,length") }, @@ -15422,10 +15422,22 @@ static njs_unit_test_t njs_test[] = njs_str("length,name,prototype") }, { njs_str("Object.getOwnPropertyNames(Array)"), - njs_str("name,length,prototype,from,isArray,of") }, + njs_str("length,name,prototype,from,isArray,of") }, { njs_str("Object.getOwnPropertyNames(Array.isArray)"), - njs_str("name,length") }, + njs_str("length,name") }, + + { njs_str("var not_arr_ind_1st = 0xFFFFFFFF, not_arr_ind_2nd = not_arr_ind_1st + 1," + "arr_ind_last = not_arr_ind_1st - 1, arr_ind_pre_last = not_arr_ind_1st - 2;" + "var o = {};" + "o[not_arr_ind_2nd] = 'not_arr_ind_2nd';" + "o[not_arr_ind_1st] = 'not_arr_ind_1st';" + "o[arr_ind_pre_last] = 'arr_ind_pre_last';" + "o[arr_ind_last] = 'arr_ind_last';" + "Object.entries(o)"), + njs_str("4294967293,arr_ind_pre_last,4294967294,arr_ind_last," + "4294967296,not_arr_ind_2nd,4294967295,not_arr_ind_1st") + }, /* Object.freeze() */ @@ -23305,9 +23317,8 @@ static njs_unit_test_t njs_backtraces_test[] = " at main (:1)\n") }, { njs_str("$shared.method({}.a.a)"), - /* FIXME: at $shared.method (native) */ njs_str("TypeError: cannot get property \"a\" of undefined\n" - " at $r.method (native)\n" + " at $shared.method (native)\n" " at main (:1)\n") }, { njs_str("new Function(\n\n@)"), -- 2.47.3