diff options
34 files changed, 812 insertions, 1883 deletions
@@ -301,12 +301,12 @@ njs_fuzzer: $NJS_BUILD_DIR/njs_auto_config.h \\ lib_test: $NJS_BUILD_DIR/njs_auto_config.h \\ $NJS_BUILD_DIR/random_unit_test \\ $NJS_BUILD_DIR/rbtree_unit_test \\ - $NJS_BUILD_DIR/lvlhsh_unit_test \\ + $NJS_BUILD_DIR/flathsh_unit_test \\ $NJS_BUILD_DIR/unicode_unit_test $NJS_BUILD_DIR/random_unit_test $NJS_BUILD_DIR/rbtree_unit_test - $NJS_BUILD_DIR/lvlhsh_unit_test + $NJS_BUILD_DIR/flathsh_unit_test $NJS_BUILD_DIR/unicode_unit_test test262_njs: njs diff --git a/auto/sources b/auto/sources index 0e8db2cd..1a89edf5 100644 --- a/auto/sources +++ b/auto/sources @@ -57,7 +57,7 @@ QJS_LIB_SRCS=" \ " NJS_LIB_TEST_SRCS=" \ - src/test/lvlhsh_unit_test.c \ + src/test/flathsh_unit_test.c \ src/test/random_unit_test.c \ src/test/rbtree_unit_test.c \ src/test/unicode_unit_test.c \ diff --git a/src/njs_array.c b/src/njs_array.c index 3f424bc4..bcf428e9 100644 --- a/src/njs_array.c +++ b/src/njs_array.c @@ -81,7 +81,7 @@ njs_array_alloc(njs_vm_t *vm, njs_bool_t flat, uint64_t length, uint32_t spare) } array->start = array->data; - njs_lvlhsh_init(&array->object.hash); + njs_flathsh_init(&array->object.hash); array->object.shared_hash = vm->shared->array_instance_hash; array->object.__proto__ = njs_vm_proto(vm, NJS_OBJ_TYPE_ARRAY); array->object.slots = NULL; @@ -1615,13 +1615,13 @@ njs_array_prototype_to_string(njs_vm_t *vm, njs_value_t *args, njs_uint_t nargs, { njs_int_t ret; njs_value_t value; - njs_flathsh_query_t lhq; + njs_flathsh_query_t fhq; if (njs_is_object(njs_argument(args, 0))) { - lhq.proto = &njs_object_hash_proto; - lhq.key_hash = NJS_ATOM_STRING_join; + fhq.proto = &njs_object_hash_proto; + fhq.key_hash = NJS_ATOM_STRING_join; - ret = njs_object_property(vm, njs_object(njs_argument(args, 0)), &lhq, + ret = njs_object_property(vm, njs_object(njs_argument(args, 0)), &fhq, &value); if (njs_slow_path(ret == NJS_ERROR)) { diff --git a/src/njs_array_buffer.c b/src/njs_array_buffer.c index c0e51c9f..9f1ee49a 100644 --- a/src/njs_array_buffer.c +++ b/src/njs_array_buffer.c @@ -35,8 +35,8 @@ njs_array_buffer_alloc(njs_vm_t *vm, uint64_t size, njs_bool_t zeroing) proto = njs_vm_proto(vm, NJS_OBJ_TYPE_ARRAY_BUFFER); - njs_lvlhsh_init(&array->object.hash); - njs_lvlhsh_init(&array->object.shared_hash); + njs_flathsh_init(&array->object.hash); + njs_flathsh_init(&array->object.shared_hash); array->object.__proto__ = proto; array->object.slots = NULL; array->object.type = NJS_ARRAY_BUFFER; diff --git a/src/njs_atom.c b/src/njs_atom.c index dc66f886..45733f45 100644 --- a/src/njs_atom.c +++ b/src/njs_atom.c @@ -8,8 +8,8 @@ #include <njs_main.h> -static njs_int_t njs_lexer_hash_test(njs_lvlhsh_query_t *lhq, void *data); -static njs_int_t njs_atom_hash_test(njs_flathsh_query_t *lhq, void *data); +static njs_int_t njs_lexer_hash_test(njs_flathsh_query_t *fhq, void *data); +static njs_int_t njs_atom_hash_test(njs_flathsh_query_t *fhq, void *data); const njs_value_t njs_atom[] = { @@ -33,28 +33,26 @@ const njs_value_t njs_atom[] = { }; -const njs_lvlhsh_proto_t njs_lexer_hash_proto +const njs_flathsh_proto_t njs_lexer_hash_proto njs_aligned(64) = { - NJS_LVLHSH_DEFAULT, njs_lexer_hash_test, - njs_lvlhsh_alloc, - njs_lvlhsh_free, + njs_flathsh_proto_alloc, + njs_flathsh_proto_free, }; const njs_flathsh_proto_t njs_atom_hash_proto njs_aligned(64) = { - 0, njs_atom_hash_test, - njs_lvlhsh_alloc, - njs_lvlhsh_free, + njs_flathsh_proto_alloc, + njs_flathsh_proto_free, }; static njs_int_t -njs_lexer_hash_test(njs_lvlhsh_query_t *lhq, void *data) +njs_lexer_hash_test(njs_flathsh_query_t *fhq, void *data) { u_char *start; njs_value_t *name; @@ -63,13 +61,13 @@ njs_lexer_hash_test(njs_lvlhsh_query_t *lhq, void *data) njs_assert(name->type == NJS_STRING); - if (lhq->key.length != name->string.data->size) { + if (fhq->key.length != name->string.data->size) { return NJS_DECLINED; } start = name->string.data->start; - if (memcmp(start, lhq->key.start, lhq->key.length) == 0) { + if (memcmp(start, fhq->key.start, fhq->key.length) == 0) { return NJS_OK; } @@ -81,33 +79,33 @@ njs_value_t * njs_atom_find_or_add(njs_vm_t *vm, u_char *key, size_t size, size_t length, uint32_t hash) { - njs_int_t ret; - njs_object_prop_t *prop; - njs_lvlhsh_query_t lhq; + njs_int_t ret; + njs_object_prop_t *prop; + njs_flathsh_query_t fhq; - lhq.key.start = key; - lhq.key.length = size; - lhq.key_hash = hash; - lhq.proto = &njs_lexer_hash_proto; + fhq.key.start = key; + fhq.key.length = size; + fhq.key_hash = hash; + fhq.proto = &njs_lexer_hash_proto; - ret = njs_lvlhsh_find(vm->atom_hash_current, &lhq); + ret = njs_flathsh_find(vm->atom_hash_current, &fhq); if (ret == NJS_OK) { - return njs_prop_value(lhq.value); + return njs_prop_value(fhq.value); } - ret = njs_lvlhsh_find(&vm->atom_hash_shared, &lhq); + ret = njs_flathsh_find(&vm->atom_hash_shared, &fhq); if (ret == NJS_OK) { - return njs_prop_value(lhq.value); + return njs_prop_value(fhq.value); } - lhq.pool = vm->mem_pool; + fhq.pool = vm->mem_pool; - ret = njs_lvlhsh_insert(vm->atom_hash_current, &lhq); + ret = njs_flathsh_insert(vm->atom_hash_current, &fhq); if (njs_slow_path(ret != NJS_OK)) { return NULL; } - prop = lhq.value; + prop = fhq.value; ret = njs_string_create(vm, &prop->u.value, key, size); if (njs_slow_path(ret != NJS_OK)) { @@ -130,35 +128,35 @@ static njs_value_t * njs_atom_find_or_add_string(njs_vm_t *vm, njs_value_t *value, uint32_t hash) { - njs_int_t ret; - njs_object_prop_t *prop; - njs_lvlhsh_query_t lhq; + njs_int_t ret; + njs_object_prop_t *prop; + njs_flathsh_query_t fhq; njs_assert(njs_is_string(value)); - lhq.key.start = value->string.data->start; - lhq.key.length = value->string.data->size; - lhq.key_hash = hash; - lhq.proto = &njs_lexer_hash_proto; + fhq.key.start = value->string.data->start; + fhq.key.length = value->string.data->size; + fhq.key_hash = hash; + fhq.proto = &njs_lexer_hash_proto; - ret = njs_lvlhsh_find(vm->atom_hash_current, &lhq); + ret = njs_flathsh_find(vm->atom_hash_current, &fhq); if (ret == NJS_OK) { - return njs_prop_value(lhq.value); + return njs_prop_value(fhq.value); } - ret = njs_lvlhsh_find(&vm->atom_hash_shared, &lhq); + ret = njs_flathsh_find(&vm->atom_hash_shared, &fhq); if (ret == NJS_OK) { - return njs_prop_value(lhq.value); + return njs_prop_value(fhq.value);; } - lhq.pool = vm->mem_pool; + fhq.pool = vm->mem_pool; - ret = njs_lvlhsh_insert(vm->atom_hash_current, &lhq); + ret = njs_flathsh_insert(vm->atom_hash_current, &fhq); if (njs_slow_path(ret != NJS_OK)) { return NULL; } - prop = lhq.value; + prop = fhq.value; prop->u.value = *value; @@ -175,7 +173,7 @@ njs_atom_find_or_add_string(njs_vm_t *vm, njs_value_t *value, static njs_int_t -njs_atom_hash_test(njs_flathsh_query_t *lhq, void *data) +njs_atom_hash_test(njs_flathsh_query_t *fhq, void *data) { size_t size; u_char *start; @@ -184,25 +182,25 @@ njs_atom_hash_test(njs_flathsh_query_t *lhq, void *data) name = data; if (name->type == NJS_STRING - && ((njs_value_t *) lhq->value)->type == NJS_STRING) + && ((njs_value_t *) fhq->value)->type == NJS_STRING) { size = name->string.data->length; - if (lhq->key.length != size) { + if (fhq->key.length != size) { return NJS_DECLINED; } start = (u_char *) name->string.data->start; - if (memcmp(start, lhq->key.start, lhq->key.length) == 0) { + if (memcmp(start, fhq->key.start, fhq->key.length) == 0) { return NJS_OK; } } if (name->type == NJS_SYMBOL - && ((njs_value_t *) lhq->value)->type == NJS_SYMBOL) + && ((njs_value_t *) fhq->value)->type == NJS_SYMBOL) { - if (lhq->key_hash == name->atom_id) { + if (fhq->key_hash == name->atom_id) { return NJS_OK; } } @@ -219,23 +217,23 @@ njs_atom_hash_init(njs_vm_t *vm) njs_int_t ret; njs_uint_t n; const njs_value_t *value, *values; - njs_flathsh_query_t lhq; + njs_flathsh_query_t fhq; values = &njs_atom[0]; - njs_lvlhsh_init(&vm->atom_hash_shared); + njs_flathsh_init(&vm->atom_hash_shared); - lhq.replace = 0; - lhq.proto = &njs_atom_hash_proto; - lhq.pool = vm->mem_pool; + fhq.replace = 0; + fhq.proto = &njs_atom_hash_proto; + fhq.pool = vm->mem_pool; for (n = 0; n < NJS_ATOM_SIZE; n++) { value = &values[n]; if (value->type == NJS_SYMBOL) { - lhq.key_hash = value->string.atom_id; + fhq.key_hash = value->string.atom_id; - ret = njs_flathsh_insert(&vm->atom_hash_shared, &lhq); + ret = njs_flathsh_insert(&vm->atom_hash_shared, &fhq); if (njs_slow_path(ret != NJS_OK)) { njs_internal_error(vm, "flathsh insert/replace failed"); return 0xffffffff; @@ -246,18 +244,18 @@ njs_atom_hash_init(njs_vm_t *vm) start = value->string.data->start; len = value->string.data->length; - lhq.key_hash = njs_djb_hash(start, len); - lhq.key.length = len; - lhq.key.start = start; + fhq.key_hash = njs_djb_hash(start, len); + fhq.key.length = len; + fhq.key.start = start; - ret = njs_flathsh_insert(&vm->atom_hash_shared, &lhq); + ret = njs_flathsh_insert(&vm->atom_hash_shared, &fhq); if (njs_slow_path(ret != NJS_OK)) { njs_internal_error(vm, "flathsh insert/replace failed"); return 0xffffffff; } } - *njs_prop_value(lhq.value) = *value; + *njs_prop_value(fhq.value) = *value; } vm->atom_hash_current = &vm->atom_hash_shared; @@ -349,26 +347,26 @@ njs_int_t njs_atom_symbol_add(njs_vm_t *vm, njs_value_t *value) { njs_int_t ret; - njs_flathsh_query_t lhq; + njs_flathsh_query_t fhq; njs_assert(value->atom_id == NJS_ATOM_STRING_unknown); - lhq.replace = 0; - lhq.proto = &njs_lexer_hash_proto; - lhq.pool = vm->mem_pool; + fhq.replace = 0; + fhq.proto = &njs_lexer_hash_proto; + fhq.pool = vm->mem_pool; value->atom_id = vm->atom_id_generator++; if (value->type == NJS_SYMBOL) { - lhq.key_hash = value->atom_id; + fhq.key_hash = value->atom_id; - ret = njs_flathsh_insert(vm->atom_hash_current, &lhq); + ret = njs_flathsh_insert(vm->atom_hash_current, &fhq); if (njs_slow_path(ret != NJS_OK)) { njs_internal_error(vm, "flathsh insert/replace failed"); return NJS_ERROR; } - *njs_prop_value(lhq.value) = *value; + *njs_prop_value(fhq.value) = *value; } return NJS_OK; diff --git a/src/njs_buffer.c b/src/njs_buffer.c index dbe9447a..93426e5c 100644 --- a/src/njs_buffer.c +++ b/src/njs_buffer.c @@ -156,8 +156,8 @@ njs_buffer_set(njs_vm_t *vm, njs_value_t *value, const u_char *start, proto = njs_vm_proto(vm, NJS_OBJ_TYPE_ARRAY_BUFFER); - njs_lvlhsh_init(&buffer->object.hash); - njs_lvlhsh_init(&buffer->object.shared_hash); + njs_flathsh_init(&buffer->object.hash); + njs_flathsh_init(&buffer->object.shared_hash); buffer->object.__proto__ = proto; buffer->object.slots = NULL; buffer->object.type = NJS_ARRAY_BUFFER; @@ -171,8 +171,8 @@ njs_buffer_set(njs_vm_t *vm, njs_value_t *value, const u_char *start, proto = njs_vm_proto(vm, NJS_OBJ_TYPE_BUFFER); array->type = NJS_OBJ_TYPE_UINT8_ARRAY; - njs_lvlhsh_init(&array->object.hash); - njs_lvlhsh_init(&array->object.shared_hash); + njs_flathsh_init(&array->object.hash); + njs_flathsh_init(&array->object.shared_hash); array->object.__proto__ = proto; array->object.slots = NULL; array->object.type = NJS_TYPED_ARRAY; diff --git a/src/njs_builtin.c b/src/njs_builtin.c index 5ce2ec7e..1b486ba9 100644 --- a/src/njs_builtin.c +++ b/src/njs_builtin.c @@ -158,7 +158,7 @@ njs_builtin_objects_create(njs_vm_t *vm) vm->shared = shared; - njs_lvlhsh_init(&shared->values_hash); + njs_flathsh_init(&shared->values_hash); vm->atom_id_generator = njs_atom_hash_init(vm); if (njs_slow_path(vm->atom_id_generator == 0xffffffff)) { @@ -300,13 +300,13 @@ njs_builtin_objects_create(njs_vm_t *vm) vm->global_object.shared = 0; string_object = &shared->string_object; - njs_lvlhsh_init(&string_object->hash); + njs_flathsh_init(&string_object->hash); string_object->shared_hash = shared->string_instance_hash; string_object->type = NJS_OBJECT_VALUE; string_object->shared = 1; string_object->extensible = 0; - njs_lvlhsh_init(&shared->modules_hash); + njs_flathsh_init(&shared->modules_hash); return NJS_OK; } @@ -323,7 +323,7 @@ njs_builtin_traverse(njs_vm_t *vm, njs_traverse_t *traverse, void *data) njs_value_t key, *value, prop_name; njs_function_t *func, *target; njs_object_prop_t *prop; - njs_flathsh_query_t lhq; + njs_flathsh_query_t fhq; njs_builtin_traverse_t *ctx; njs_traverse_t *path[NJS_TRAVERSE_MAX_DEPTH]; u_char buf[256]; @@ -438,18 +438,18 @@ njs_builtin_traverse(njs_vm_t *vm, njs_traverse_t *traverse, void *data) return ret; } - lhq.key_hash = prop_name.atom_id; - lhq.replace = 1; - lhq.pool = vm->mem_pool; - lhq.proto = &njs_object_hash_proto; + fhq.key_hash = prop_name.atom_id; + fhq.replace = 1; + fhq.pool = vm->mem_pool; + fhq.proto = &njs_object_hash_proto; - ret = njs_flathsh_unique_insert(&ctx->keys, &lhq); + ret = njs_flathsh_unique_insert(&ctx->keys, &fhq); if (njs_slow_path(ret != NJS_OK)) { - njs_internal_error(vm, "lvlhsh insert/replace failed"); + njs_internal_error(vm, "flathsh insert/replace failed"); return NJS_ERROR; } - prop = lhq.value; + prop = fhq.value; prop->type = NJS_PROPERTY; prop->enumerable = 0; @@ -480,7 +480,7 @@ njs_builtin_match_native_function(njs_vm_t *vm, njs_function_t *function, njs_value_t value, tag; njs_object_t object; njs_object_prop_t *prop; - njs_lvlhsh_each_t lhe; + njs_flathsh_each_t lhe; njs_exotic_slots_t *slots; njs_function_name_t *fn; njs_function_native_t native; @@ -538,7 +538,7 @@ njs_builtin_match_native_function(njs_vm_t *vm, njs_function_t *function, /* Modules. */ - njs_lvlhsh_each_init(&lhe, &njs_modules_hash_proto); + njs_flathsh_each_init(&lhe, &njs_modules_hash_proto); for ( ;; ) { prop = (njs_object_prop_t *) njs_flathsh_each(&vm->modules_hash, &lhe); @@ -807,7 +807,7 @@ njs_global_this_object(njs_vm_t *vm, njs_object_prop_t *self, uint32_t atom_id, { njs_int_t ret; njs_object_prop_t *prop; - njs_flathsh_query_t lhq; + njs_flathsh_query_t fhq; if (retval == NULL) { return NJS_DECLINED; @@ -819,18 +819,18 @@ njs_global_this_object(njs_vm_t *vm, njs_object_prop_t *self, uint32_t atom_id, njs_value_assign(retval, setval); } - lhq.key_hash = atom_id; - lhq.replace = 1; - lhq.pool = vm->mem_pool; - lhq.proto = &njs_object_hash_proto; + fhq.key_hash = atom_id; + fhq.replace = 1; + fhq.pool = vm->mem_pool; + fhq.proto = &njs_object_hash_proto; - ret = njs_flathsh_unique_insert(njs_object_hash(global), &lhq); + ret = njs_flathsh_unique_insert(njs_object_hash(global), &fhq); if (njs_slow_path(ret != NJS_OK)) { - njs_internal_error(vm, "lvlhsh insert/replace failed"); + njs_internal_error(vm, "flathsh insert/replace failed"); return NJS_ERROR; } - prop = lhq.value; + prop = fhq.value; prop->type = NJS_PROPERTY; prop->enumerable = self->enumerable; @@ -849,7 +849,7 @@ njs_top_level_object(njs_vm_t *vm, njs_object_prop_t *self, uint32_t atom_id, njs_int_t ret; njs_object_t *object; njs_object_prop_t *prop; - njs_flathsh_query_t lhq; + njs_flathsh_query_t fhq; if (njs_slow_path(setval != NULL)) { njs_value_assign(retval, setval); @@ -869,18 +869,18 @@ njs_top_level_object(njs_vm_t *vm, njs_object_prop_t *self, uint32_t atom_id, object->__proto__ = njs_vm_proto(vm, NJS_OBJ_TYPE_OBJECT); } - lhq.key_hash = atom_id; - lhq.replace = 1; - lhq.pool = vm->mem_pool; - lhq.proto = &njs_object_hash_proto; + fhq.key_hash = atom_id; + fhq.replace = 1; + fhq.pool = vm->mem_pool; + fhq.proto = &njs_object_hash_proto; - ret = njs_flathsh_unique_insert(njs_object_hash(global), &lhq); + ret = njs_flathsh_unique_insert(njs_object_hash(global), &fhq); if (njs_slow_path(ret != NJS_OK)) { - njs_internal_error(vm, "lvlhsh insert/replace failed"); + njs_internal_error(vm, "flathsh insert/replace failed"); return NJS_ERROR; } - prop = lhq.value; + prop = fhq.value; prop->type = NJS_PROPERTY; prop->enumerable = self->enumerable; @@ -900,7 +900,7 @@ njs_top_level_constructor(njs_vm_t *vm, njs_object_prop_t *self, njs_int_t ret; njs_function_t *ctor; njs_object_prop_t *prop; - njs_flathsh_query_t lhq; + njs_flathsh_query_t fhq; if (njs_slow_path(setval != NULL)) { njs_value_assign(retval, setval); @@ -917,18 +917,18 @@ njs_top_level_constructor(njs_vm_t *vm, njs_object_prop_t *self, return NJS_OK; } - lhq.key_hash = atom_id; - lhq.replace = 1; - lhq.pool = vm->mem_pool; - lhq.proto = &njs_object_hash_proto; + fhq.key_hash = atom_id; + fhq.replace = 1; + fhq.pool = vm->mem_pool; + fhq.proto = &njs_object_hash_proto; - ret = njs_flathsh_unique_insert(njs_object_hash(global), &lhq); + ret = njs_flathsh_unique_insert(njs_object_hash(global), &fhq); if (njs_slow_path(ret != NJS_OK)) { - njs_internal_error(vm, "lvlhsh insert/replace failed"); + njs_internal_error(vm, "flathsh insert/replace failed"); return NJS_ERROR; } - prop = lhq.value; + prop = fhq.value; prop->type = NJS_PROPERTY; prop->enumerable = 0; @@ -1189,7 +1189,7 @@ njs_process_object_argv(njs_vm_t *vm, njs_object_prop_t *pr, uint32_t unused, njs_uint_t i; njs_array_t *argv; njs_object_prop_t *prop; - njs_flathsh_query_t lhq; + njs_flathsh_query_t fhq; argv = njs_array_alloc(vm, 1, vm->options.argc, 0); if (njs_slow_path(argv == NULL)) { @@ -1206,18 +1206,18 @@ njs_process_object_argv(njs_vm_t *vm, njs_object_prop_t *pr, uint32_t unused, } } - lhq.key_hash = NJS_ATOM_STRING_argv; - lhq.replace = 1; - lhq.pool = vm->mem_pool; - lhq.proto = &njs_object_hash_proto; + fhq.key_hash = NJS_ATOM_STRING_argv; + fhq.replace = 1; + fhq.pool = vm->mem_pool; + fhq.proto = &njs_object_hash_proto; - ret = njs_flathsh_unique_insert(njs_object_hash(process), &lhq); + ret = njs_flathsh_unique_insert(njs_object_hash(process), &fhq); if (njs_slow_path(ret != NJS_OK)) { - njs_internal_error(vm, "lvlhsh insert failed"); + njs_internal_error(vm, "flathsh insert failed"); return NJS_ERROR; } - prop = lhq.value; + prop = fhq.value; prop->type = NJS_PROPERTY; prop->enumerable = 1; @@ -1244,11 +1244,11 @@ njs_env_hash_init(njs_vm_t *vm, njs_flathsh_t *hash, char **environment) const u_char *val, *entry, *s, *end; njs_object_prop_t *prop; njs_string_prop_t string; - njs_flathsh_query_t lhq; + njs_flathsh_query_t fhq; - lhq.replace = 0; - lhq.pool = vm->mem_pool; - lhq.proto = &njs_object_hash_proto; + fhq.replace = 0; + fhq.pool = vm->mem_pool; + fhq.proto = &njs_object_hash_proto; ep = environment; @@ -1286,12 +1286,12 @@ njs_env_hash_init(njs_vm_t *vm, njs_flathsh_t *hash, char **environment) return ret; } - lhq.key_hash = prop_name.atom_id; + fhq.key_hash = prop_name.atom_id; - ret = njs_flathsh_unique_insert(hash, &lhq); + ret = njs_flathsh_unique_insert(hash, &fhq); if (njs_slow_path(ret != NJS_OK)) { if (ret == NJS_ERROR) { - njs_internal_error(vm, "lvlhsh insert failed"); + njs_internal_error(vm, "flathsh insert failed"); return NJS_ERROR; } @@ -1304,7 +1304,7 @@ njs_env_hash_init(njs_vm_t *vm, njs_flathsh_t *hash, char **environment) continue; } - prop = lhq.value; + prop = fhq.value; prop->type = NJS_PROPERTY; prop->enumerable = 1; @@ -1328,7 +1328,7 @@ njs_process_object_env(njs_vm_t *vm, njs_object_prop_t *pr, uint32_t unused, njs_int_t ret; njs_object_t *env; njs_object_prop_t *prop; - njs_flathsh_query_t lhq; + njs_flathsh_query_t fhq; env = njs_object_alloc(vm); if (njs_slow_path(env == NULL)) { @@ -1337,18 +1337,19 @@ njs_process_object_env(njs_vm_t *vm, njs_object_prop_t *pr, uint32_t unused, env->shared_hash = vm->shared->env_hash; - lhq.replace = 1; - lhq.pool = vm->mem_pool; - lhq.proto = &njs_object_hash_proto; - lhq.key_hash = NJS_ATOM_STRING_env; + fhq.replace = 1; + fhq.pool = vm->mem_pool; + fhq.proto = &njs_object_hash_proto; + fhq.key_hash = NJS_ATOM_STRING_env; - ret = njs_flathsh_unique_insert(njs_object_hash(process), &lhq); + ret = njs_flathsh_unique_insert(njs_object_hash(process), &fhq); if (njs_slow_path(ret != NJS_OK)) { - njs_internal_error(vm, "lvlhsh insert failed"); + njs_internal_error(vm, "flathsh insert failed"); + return NJS_ERROR; } - prop = lhq.value; + prop = fhq.value; prop->type = NJS_PROPERTY; prop->enumerable = 1; diff --git a/src/njs_date.c b/src/njs_date.c index 2832abbd..03e866a1 100644 --- a/src/njs_date.c +++ b/src/njs_date.c @@ -375,8 +375,8 @@ njs_date_alloc(njs_vm_t *vm, double time) return NULL; } - njs_lvlhsh_init(&date->object.hash); - njs_lvlhsh_init(&date->object.shared_hash); + njs_flathsh_init(&date->object.hash); + njs_flathsh_init(&date->object.shared_hash); date->object.type = NJS_DATE; date->object.shared = 0; date->object.extensible = 1; @@ -1443,13 +1443,13 @@ njs_date_prototype_to_json(njs_vm_t *vm, njs_value_t *args, njs_uint_t nargs, { njs_int_t ret; njs_value_t value; - njs_flathsh_query_t lhq; + njs_flathsh_query_t fhq; if (njs_is_object(njs_argument(args, 0))) { - lhq.proto = &njs_object_hash_proto; - lhq.key_hash = NJS_ATOM_STRING_toISOString; + fhq.proto = &njs_object_hash_proto; + fhq.key_hash = NJS_ATOM_STRING_toISOString; - ret = njs_object_property(vm, njs_object(njs_argument(args, 0)), &lhq, + ret = njs_object_property(vm, njs_object(njs_argument(args, 0)), &fhq, &value); if (njs_slow_path(ret == NJS_ERROR)) { diff --git a/src/njs_error.c b/src/njs_error.c index d19e0e22..57ab477a 100644 --- a/src/njs_error.c +++ b/src/njs_error.c @@ -186,7 +186,7 @@ njs_error_alloc(njs_vm_t *vm, njs_object_t *proto, const njs_value_t *name, njs_object_t *error; njs_object_prop_t *prop; njs_object_value_t *ov; - njs_flathsh_query_t lhq; + njs_flathsh_query_t fhq; ov = njs_mp_alloc(vm->mem_pool, sizeof(njs_object_value_t)); if (njs_slow_path(ov == NULL)) { @@ -196,8 +196,8 @@ njs_error_alloc(njs_vm_t *vm, njs_object_t *proto, const njs_value_t *name, njs_set_data(&ov->value, NULL, NJS_DATA_TAG_ANY); error = &ov->object; - njs_lvlhsh_init(&error->hash); - njs_lvlhsh_init(&error->shared_hash); + njs_flathsh_init(&error->hash); + njs_flathsh_init(&error->shared_hash); error->type = NJS_OBJECT_VALUE; error->shared = 0; error->extensible = 1; @@ -207,20 +207,20 @@ njs_error_alloc(njs_vm_t *vm, njs_object_t *proto, const njs_value_t *name, error->__proto__ = proto; error->slots = NULL; - lhq.replace = 0; - lhq.pool = vm->mem_pool; - lhq.proto = &njs_object_hash_proto; + fhq.replace = 0; + fhq.pool = vm->mem_pool; + fhq.proto = &njs_object_hash_proto; if (name != NULL) { - lhq.key_hash = NJS_ATOM_STRING_name; + fhq.key_hash = NJS_ATOM_STRING_name; - ret = njs_flathsh_unique_insert(&error->hash, &lhq); + ret = njs_flathsh_unique_insert(&error->hash, &fhq); if (njs_slow_path(ret != NJS_OK)) { - njs_internal_error(vm, "lvlhsh insert failed"); + njs_internal_error(vm, "flathsh insert failed"); return NULL; } - prop = lhq.value; + prop = fhq.value; prop->type = NJS_PROPERTY; prop->enumerable = 1; @@ -231,15 +231,15 @@ njs_error_alloc(njs_vm_t *vm, njs_object_t *proto, const njs_value_t *name, } if (message!= NULL) { - lhq.key_hash = NJS_ATOM_STRING_message; + fhq.key_hash = NJS_ATOM_STRING_message; - ret = njs_flathsh_unique_insert(&error->hash, &lhq); + ret = njs_flathsh_unique_insert(&error->hash, &fhq); if (njs_slow_path(ret != NJS_OK)) { - njs_internal_error(vm, "lvlhsh insert failed"); + njs_internal_error(vm, "flathsh insert failed"); return NULL; } - prop = lhq.value; + prop = fhq.value; prop->type = NJS_PROPERTY; prop->enumerable = 0; @@ -250,15 +250,15 @@ njs_error_alloc(njs_vm_t *vm, njs_object_t *proto, const njs_value_t *name, } if (errors != NULL) { - lhq.key_hash = NJS_ATOM_STRING_errors; + fhq.key_hash = NJS_ATOM_STRING_errors; - ret = njs_flathsh_unique_insert(&error->hash, &lhq); + ret = njs_flathsh_unique_insert(&error->hash, &fhq); if (njs_slow_path(ret != NJS_OK)) { - njs_internal_error(vm, "lvlhsh insert failed"); + njs_internal_error(vm, "flathsh insert failed"); return NULL; } - prop = lhq.value; + prop = fhq.value; prop->type = NJS_PROPERTY; prop->enumerable = 0; @@ -495,8 +495,8 @@ njs_memory_error_set(njs_vm_t *vm, njs_value_t *value) njs_set_data(&ov->value, NULL, NJS_DATA_TAG_ANY); object = &ov->object; - njs_lvlhsh_init(&object->hash); - njs_lvlhsh_init(&object->shared_hash); + njs_flathsh_init(&object->hash); + njs_flathsh_init(&object->shared_hash); object->__proto__ = njs_vm_proto(vm, NJS_OBJ_TYPE_INTERNAL_ERROR); object->slots = NULL; object->type = NJS_OBJECT_VALUE; diff --git a/src/njs_extern.c b/src/njs_extern.c index adc8cd67..bbac8c73 100644 --- a/src/njs_extern.c +++ b/src/njs_extern.c @@ -25,22 +25,22 @@ njs_external_add(njs_vm_t *vm, njs_arr_t *protos, njs_function_t *function; njs_object_prop_t *prop; njs_exotic_slots_t *slot, *next; - njs_flathsh_query_t lhq; + njs_flathsh_query_t fhq; const njs_external_t *end; slot = njs_arr_add(protos); njs_memzero(slot, sizeof(njs_exotic_slots_t)); hash = &slot->external_shared_hash; - njs_lvlhsh_init(hash); + njs_flathsh_init(hash); if (n == 0) { return NJS_OK; } - lhq.replace = 0; - lhq.proto = &njs_object_hash_proto; - lhq.pool = vm->mem_pool; + fhq.replace = 0; + fhq.proto = &njs_object_hash_proto; + fhq.pool = vm->mem_pool; end = external + n; @@ -59,7 +59,7 @@ njs_external_add(njs_vm_t *vm, njs_arr_t *protos, } if (external->flags & NJS_EXTERN_SYMBOL) { - lhq.key_hash = external->name.symbol; + fhq.key_hash = external->name.symbol; } else { ret = njs_atom_string_create(vm, &prop_name, @@ -69,16 +69,16 @@ njs_external_add(njs_vm_t *vm, njs_arr_t *protos, return NJS_ERROR; } - lhq.key_hash = prop_name.atom_id; + fhq.key_hash = prop_name.atom_id; } - ret = njs_flathsh_unique_insert(hash, &lhq); + ret = njs_flathsh_unique_insert(hash, &fhq); if (njs_slow_path(ret != NJS_OK)) { - njs_internal_error(vm, "lvlhsh insert failed"); + njs_internal_error(vm, "flathsh insert failed"); return NJS_ERROR; } - prop = lhq.value; + prop = fhq.value; prop->type = NJS_PROPERTY; prop->enumerable = external->enumerable; @@ -142,7 +142,7 @@ njs_external_add(njs_vm_t *vm, njs_arr_t *protos, prop->u.value.type = NJS_INVALID; prop->u.value.data.truth = 1; njs_prop_magic16(prop) = next - slot; - njs_prop_magic32(prop) = lhq.key_hash; + njs_prop_magic32(prop) = fhq.key_hash; njs_prop_handler(prop) = njs_external_prop_handler; if (external->u.object.prop_handler) { @@ -194,7 +194,7 @@ njs_external_prop_handler(njs_vm_t *vm, njs_object_prop_t *self, njs_external_ptr_t external; njs_object_value_t *ov; njs_exotic_slots_t *slots; - njs_flathsh_query_t lhq; + njs_flathsh_query_t fhq; if (njs_slow_path(retval == NULL)) { return NJS_DECLINED; @@ -222,18 +222,18 @@ njs_external_prop_handler(njs_vm_t *vm, njs_object_prop_t *self, njs_set_object_value(retval, ov); } - lhq.key_hash = atom_id; - lhq.replace = 1; - lhq.pool = vm->mem_pool; - lhq.proto = &njs_object_hash_proto; + fhq.key_hash = atom_id; + fhq.replace = 1; + fhq.pool = vm->mem_pool; + fhq.proto = &njs_object_hash_proto; - ret = njs_flathsh_unique_insert(njs_object_hash(value), &lhq); + ret = njs_flathsh_unique_insert(njs_object_hash(value), &fhq); if (njs_slow_path(ret != NJS_OK)) { - njs_internal_error(vm, "lvlhsh insert/replace failed"); + njs_internal_error(vm, "flathsh insert/replace failed"); return NJS_ERROR; } - prop = lhq.value; + prop = fhq.value; prop->type = NJS_PROPERTY; prop->enumerable = self->enumerable; diff --git a/src/njs_flathsh.c b/src/njs_flathsh.c index 7e374c62..601018d1 100644 --- a/src/njs_flathsh.c +++ b/src/njs_flathsh.c @@ -143,7 +143,7 @@ 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); + NJS_FLATHSH_ELTS_INITIAL_SIZE); } diff --git a/src/njs_flathsh.h b/src/njs_flathsh.h index 06fd00c0..2d2f6ae1 100644 --- a/src/njs_flathsh.h +++ b/src/njs_flathsh.h @@ -46,7 +46,6 @@ 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; @@ -164,37 +163,4 @@ NJS_EXPORT njs_flathsh_descr_t *njs_flathsh_new(njs_flathsh_query_t *fhq); NJS_EXPORT void njs_flathsh_destroy(njs_flathsh_t *fh, 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) - -njs_inline njs_flathsh_elt_t * -njs_lvlhsh_each(const njs_flathsh_t *lh, njs_flathsh_each_t *lhe) -{ - njs_flathsh_elt_t *e; - - e = njs_flathsh_each(lh, lhe); - if (e == NULL) { - return NULL; - } - - return e; -} - - #endif /* _NJS_FLATHSH_H_INCLUDED_ */ diff --git a/src/njs_function.c b/src/njs_function.c index 09bc2ebb..9ed4bb42 100644 --- a/src/njs_function.c +++ b/src/njs_function.c @@ -28,7 +28,7 @@ njs_function_alloc(njs_vm_t *vm, njs_function_lambda_t *lambda, /* * njs_mp_zalloc() does also: - * njs_lvlhsh_init(&function->object.hash); + * njs_flathsh_init(&function->object.hash); * function->object.__proto__ = NULL; */ @@ -124,20 +124,20 @@ njs_function_name_set(njs_vm_t *vm, njs_function_t *function, njs_value_t value; njs_string_prop_t string; njs_object_prop_t *prop; - njs_flathsh_query_t lhq; + njs_flathsh_query_t fhq; - lhq.key_hash = NJS_ATOM_STRING_name; - lhq.replace = 0; - lhq.pool = vm->mem_pool; - lhq.proto = &njs_object_hash_proto; + fhq.key_hash = NJS_ATOM_STRING_name; + fhq.replace = 0; + fhq.pool = vm->mem_pool; + fhq.proto = &njs_object_hash_proto; - ret = njs_flathsh_unique_insert(&function->object.hash, &lhq); + ret = njs_flathsh_unique_insert(&function->object.hash, &fhq); if (njs_slow_path(ret != NJS_OK)) { - njs_internal_error(vm, "lvlhsh insert failed"); + njs_internal_error(vm, "flathsh insert failed"); return NJS_ERROR; } - prop = lhq.value; + prop = fhq.value; prop->type = NJS_PROPERTY; prop->enumerable = 0; @@ -892,21 +892,21 @@ njs_function_property_prototype_set(njs_vm_t *vm, njs_flathsh_t *hash, { njs_int_t ret; njs_object_prop_t *prop; - njs_flathsh_query_t lhq; + njs_flathsh_query_t fhq; - lhq.key_hash = NJS_ATOM_STRING_prototype; - lhq.replace = 1; - lhq.pool = vm->mem_pool; - lhq.proto = &njs_object_hash_proto; + fhq.key_hash = NJS_ATOM_STRING_prototype; + fhq.replace = 1; + fhq.pool = vm->mem_pool; + fhq.proto = &njs_object_hash_proto; - ret = njs_flathsh_unique_insert(hash, &lhq); + ret = njs_flathsh_unique_insert(hash, &fhq); if (njs_slow_path(ret != NJS_OK)) { - njs_internal_error(vm, "lvlhsh insert failed"); + njs_internal_error(vm, "flathsh insert failed"); return NULL; } - prop = lhq.value; + prop = fhq.value; prop->type = NJS_PROPERTY; prop->enumerable = 0; @@ -1353,7 +1353,7 @@ njs_function_prototype_bind(njs_vm_t *vm, njs_value_t *args, njs_uint_t nargs, function->native = 1; function->u.native = njs_function_bound_call; - njs_lvlhsh_init(&function->object.hash); + njs_flathsh_init(&function->object.hash); /* Bound functions have no "prototype" property. */ function->object.shared_hash = vm->shared->arrow_instance_hash; diff --git a/src/njs_json.c b/src/njs_json.c index 49c2b7e7..d77befdd 100644 --- a/src/njs_json.c +++ b/src/njs_json.c @@ -339,7 +339,7 @@ njs_json_parse_object(njs_json_parse_ctx_t *ctx, njs_value_t *value, njs_object_t *object; njs_value_t prop_name, prop_value; njs_object_prop_t *prop; - njs_flathsh_query_t lhq; + njs_flathsh_query_t fhq; if (njs_slow_path(--ctx->depth == 0)) { njs_json_parse_exception(ctx, "Nested too deep", p); @@ -394,18 +394,18 @@ njs_json_parse_object(njs_json_parse_ctx_t *ctx, njs_value_t *value, return NULL; } - lhq.key_hash = prop_name.atom_id; - lhq.replace = 1; - lhq.pool = ctx->pool; - lhq.proto = &njs_object_hash_proto; + fhq.key_hash = prop_name.atom_id; + fhq.replace = 1; + fhq.pool = ctx->pool; + fhq.proto = &njs_object_hash_proto; - ret = njs_flathsh_unique_insert(&object->hash, &lhq); + ret = njs_flathsh_unique_insert(&object->hash, &fhq); if (njs_slow_path(ret != NJS_OK)) { - njs_internal_error(ctx->vm, "lvlhsh insert/replace failed"); + njs_internal_error(ctx->vm, "flathsh insert/replace failed"); return NULL; } - prop = lhq.value; + prop = fhq.value; prop->type = NJS_PROPERTY; prop->enumerable = 1; @@ -1235,13 +1235,13 @@ njs_object_to_json_function(njs_vm_t *vm, njs_value_t *value) { njs_int_t ret; njs_value_t retval; - njs_flathsh_query_t lhq; + njs_flathsh_query_t fhq; if (njs_is_object(value)) { - lhq.proto = &njs_object_hash_proto; - lhq.key_hash = NJS_ATOM_STRING_toJSON; + fhq.proto = &njs_object_hash_proto; + fhq.key_hash = NJS_ATOM_STRING_toJSON; - ret = njs_object_property(vm, njs_object(value), &lhq, &retval); + ret = njs_object_property(vm, njs_object(value), &fhq, &retval); if (njs_slow_path(ret == NJS_ERROR)) { return NULL; @@ -1601,7 +1601,7 @@ njs_json_wrap_value(njs_vm_t *vm, njs_value_t *wrapper, { njs_int_t ret; njs_object_prop_t *prop; - njs_flathsh_query_t lhq; + njs_flathsh_query_t fhq; wrapper->data.u.object = njs_object_alloc(vm); if (njs_slow_path(njs_object(wrapper) == NULL)) { @@ -1611,17 +1611,17 @@ njs_json_wrap_value(njs_vm_t *vm, njs_value_t *wrapper, wrapper->type = NJS_OBJECT; wrapper->data.truth = 1; - lhq.key_hash = NJS_ATOM_STRING_empty; - lhq.replace = 0; - lhq.pool = vm->mem_pool; - lhq.proto = &njs_object_hash_proto; + fhq.key_hash = NJS_ATOM_STRING_empty; + fhq.replace = 0; + fhq.pool = vm->mem_pool; + fhq.proto = &njs_object_hash_proto; - ret = njs_flathsh_unique_insert(njs_object_hash(wrapper), &lhq); + ret = njs_flathsh_unique_insert(njs_object_hash(wrapper), &fhq); if (njs_slow_path(ret != NJS_OK)) { return NULL; } - prop = lhq.value; + prop = fhq.value; prop->type = NJS_PROPERTY; prop->enumerable = 1; @@ -2051,7 +2051,7 @@ njs_vm_value_dump(njs_vm_t *vm, njs_str_t *retval, njs_value_t *value, goto exception; } - prop = pq.lhq.value; + prop = pq.fhq.value; if (prop->type == NJS_WHITEOUT || !prop->enumerable) { if (!state->array) { @@ -2069,8 +2069,8 @@ njs_vm_value_dump(njs_vm_t *vm, njs_str_t *retval, njs_value_t *value, njs_dump_empty(stringify, state, &chain, 1); if (!state->array || isnan(njs_key_to_index(key))) { - njs_atom_string_get(vm, key->atom_id, &pq.lhq.key); - njs_chb_append(&chain, pq.lhq.key.start, pq.lhq.key.length); + njs_atom_string_get(vm, key->atom_id, &pq.fhq.key); + njs_chb_append(&chain, pq.fhq.key.start, pq.fhq.key.length); njs_chb_append_literal(&chain, ":"); if (stringify->space.length != 0) { njs_chb_append_literal(&chain, " "); @@ -2082,7 +2082,7 @@ njs_vm_value_dump(njs_vm_t *vm, njs_str_t *retval, njs_value_t *value, if (prop->type == NJS_PROPERTY_HANDLER) { pq.scratch = *prop; prop = &pq.scratch; - ret = njs_prop_handler(prop)(vm, prop, pq.lhq.key_hash, + ret = njs_prop_handler(prop)(vm, prop, pq.fhq.key_hash, &state->value, NULL, njs_prop_value(prop)); diff --git a/src/njs_lvlhsh.c b/src/njs_lvlhsh.c deleted file mode 100644 index 8443a08c..00000000 --- a/src/njs_lvlhsh.c +++ /dev/null @@ -1,854 +0,0 @@ - -/* - * Copyright (C) Igor Sysoev - * Copyright (C) NGINX, Inc. - */ - - -#include <njs_main.h> - - -/* - * The level hash consists of hierarchical levels of arrays of pointers. - * The pointers may point to another level, a bucket, or NULL. - * The levels and buckets must be allocated in manner alike posix_memalign() - * to bookkeep additional information in pointer low bits. - * - * A level is an array of pointers. Its size is a power of 2. Levels - * may be different sizes, but on the same level the sizes are the same. - * Level sizes are specified by number of bits per level in lvlhsh->shift - * array. A hash may have up to 7 levels. There are two predefined - * shift arrays given by the first two shift array values: - * - * 1) [0, 0]: [4, 4, 4, 4, 4, 4, 4] on a 64-bit platform or - * [5, 5, 5, 5, 5, 5, 0] on a 32-bit platform, - * so default size of levels is 128 bytes. - * - * 2) [0, 10]: [10, 4, 4, 4, 4, 4, 0] on a 64-bit platform or - * [10, 5, 5, 5, 5, 0, 0] on a 32-bit platform, - * so default size of levels is 128 bytes on all levels except - * the first level. The first level is 8K or 4K on 64-bit or 32-bit - * platforms respectively. - * - * All buckets in a hash are the same size which is a power of 2. - * A bucket contains several entries stored and tested sequentially. - * The bucket size should be one or two CPU cache line size, a minimum - * allowed size is 32 bytes. A default 128-byte bucket contains 10 64-bit - * entries or 15 32-bit entries. Each entry consists of pointer to value - * data and 32-bit key. If an entry value pointer is NULL, the entry is free. - * On a 64-bit platform entry value pointers are no aligned, therefore they - * are accessed as two 32-bit integers. The rest trailing space in a bucket - * is used as pointer to next bucket and this pointer is always aligned. - * Although the level hash allows to store a lot of values in a bucket chain, - * this is non optimal way. The large data set should be stored using - * several levels. - */ - -#define njs_lvlhsh_is_bucket(p) \ - ((uintptr_t) (p) & 1) - - -#define njs_lvlhsh_count_inc(n) \ - n = (void *) ((uintptr_t) (n) + 2) - - -#define njs_lvlhsh_count_dec(n) \ - n = (void *) ((uintptr_t) (n) - 2) - - -#define njs_lvlhsh_level_size(proto, nlvl) \ - ((uintptr_t) 1 << proto->shift[nlvl]) - - -#define njs_lvlhsh_level(lvl, mask) \ - (void **) ((uintptr_t) lvl & (~mask << 2)) - - -#define njs_lvlhsh_level_entries(lvl, mask) \ - ((uintptr_t) lvl & (mask << 1)) - - -#define njs_lvlhsh_store_bucket(slot, bkt) \ - slot = (void **) ((uintptr_t) bkt | 2 | 1) - - -#define njs_lvlhsh_bucket_size(proto) \ - proto->bucket_size - - -#define njs_lvlhsh_bucket(proto, bkt) \ - (uint32_t *) ((uintptr_t) bkt & ~(uintptr_t) proto->bucket_mask) - - -#define njs_lvlhsh_bucket_entries(proto, bkt) \ - (((uintptr_t) bkt & (uintptr_t) proto->bucket_mask) >> 1) - - -#define njs_lvlhsh_bucket_end(proto, bkt) \ - &bkt[proto->bucket_end] - - -#define njs_lvlhsh_free_entry(e) \ - (!(njs_lvlhsh_valid_entry(e))) - - -#define njs_lvlhsh_next_bucket(proto, bkt) \ - ((void **) &bkt[proto->bucket_end]) - -#if (NJS_64BIT) - -#define njs_lvlhsh_valid_entry(e) \ - (((e)[0] | (e)[1]) != 0) - - -#define njs_lvlhsh_entry_value(e) \ - (void *) (((uintptr_t) (e)[1] << 32) + (e)[0]) - - -#define njs_lvlhsh_set_entry_value(e, n) \ - (e)[0] = (uint32_t) (uintptr_t) n; \ - (e)[1] = (uint32_t) ((uintptr_t) n >> 32) - - -#define njs_lvlhsh_entry_key(e) \ - (e)[2] - - -#define njs_lvlhsh_set_entry_key(e, n) \ - (e)[2] = n - -#else - -#define njs_lvlhsh_valid_entry(e) \ - ((e)[0] != 0) - - -#define njs_lvlhsh_entry_value(e) \ - (void *) (e)[0] - - -#define njs_lvlhsh_set_entry_value(e, n) \ - (e)[0] = (uint32_t) n - - -#define njs_lvlhsh_entry_key(e) \ - (e)[1] - - -#define njs_lvlhsh_set_entry_key(e, n) \ - (e)[1] = n - -#endif - - -#define NJS_LVLHSH_BUCKET_DONE ((void *) -1) - - -static njs_int_t njs_lvlhsh_level_find(njs_lvlhsh_query_t *lhq, void **lvl, - uint32_t key, njs_uint_t nlvl); -static njs_int_t njs_lvlhsh_bucket_find(njs_lvlhsh_query_t *lhq, void **bkt); -static njs_int_t njs_lvlhsh_new_bucket(njs_lvlhsh_query_t *lhq, void **slot); -static njs_int_t njs_lvlhsh_level_insert(njs_lvlhsh_query_t *lhq, - void **slot, uint32_t key, njs_uint_t nlvl); -static njs_int_t njs_lvlhsh_bucket_insert(njs_lvlhsh_query_t *lhq, - void **slot, uint32_t key, njs_int_t nlvl); -static njs_int_t njs_lvlhsh_convert_bucket_to_level(njs_lvlhsh_query_t *lhq, - void **slot, njs_uint_t nlvl, uint32_t *bucket); -static njs_int_t njs_lvlhsh_level_convertion_insert(njs_lvlhsh_query_t *lhq, - void **parent, uint32_t key, njs_uint_t nlvl); -static njs_int_t njs_lvlhsh_bucket_convertion_insert(njs_lvlhsh_query_t *lhq, - void **slot, uint32_t key, njs_int_t nlvl); -static njs_int_t njs_lvlhsh_free_level(njs_lvlhsh_query_t *lhq, void **level, - njs_uint_t size); -static njs_int_t njs_lvlhsh_level_delete(njs_lvlhsh_query_t *lhq, void **slot, - uint32_t key, njs_uint_t nlvl); -static njs_int_t njs_lvlhsh_bucket_delete(njs_lvlhsh_query_t *lhq, void **bkt); -static void *njs_lvlhsh_level_each(njs_lvlhsh_each_t *lhe, void **level, - njs_uint_t nlvl, njs_uint_t shift); -static void *njs_lvlhsh_bucket_each(njs_lvlhsh_each_t *lhe); - - -njs_int_t -njs_lvlhsh_find(const njs_lvlhsh_t *lh, njs_lvlhsh_query_t *lhq) -{ - void *slot; - - slot = lh->slot; - - if (njs_fast_path(slot != NULL)) { - - if (njs_lvlhsh_is_bucket(slot)) { - return njs_lvlhsh_bucket_find(lhq, slot); - } - - return njs_lvlhsh_level_find(lhq, slot, lhq->key_hash, 0); - } - - return NJS_DECLINED; -} - - -static njs_int_t -njs_lvlhsh_level_find(njs_lvlhsh_query_t *lhq, void **lvl, uint32_t key, - njs_uint_t nlvl) -{ - void **slot; - uintptr_t mask; - njs_uint_t shift; - - shift = lhq->proto->shift[nlvl]; - mask = ((uintptr_t) 1 << shift) - 1; - - lvl = njs_lvlhsh_level(lvl, mask); - slot = lvl[key & mask]; - - if (slot != NULL) { - - if (njs_lvlhsh_is_bucket(slot)) { - return njs_lvlhsh_bucket_find(lhq, slot); - } - - return njs_lvlhsh_level_find(lhq, slot, key >> shift, nlvl + 1); - } - - return NJS_DECLINED; -} - - -static njs_int_t -njs_lvlhsh_bucket_find(njs_lvlhsh_query_t *lhq, void **bkt) -{ - void *value; - uint32_t *bucket, *e; - njs_uint_t n; - - do { - bucket = njs_lvlhsh_bucket(lhq->proto, bkt); - n = njs_lvlhsh_bucket_entries(lhq->proto, bkt); - e = bucket; - - do { - if (njs_lvlhsh_valid_entry(e)) { - n--; - - if (njs_lvlhsh_entry_key(e) == lhq->key_hash) { - - value = njs_lvlhsh_entry_value(e); - - if (lhq->proto->test(lhq, value) == NJS_OK) { - lhq->value = value; - - return NJS_OK; - } - } - } - - e += NJS_LVLHSH_ENTRY_SIZE; - - } while (n != 0); - - bkt = *njs_lvlhsh_next_bucket(lhq->proto, bucket); - - } while (bkt != NULL); - - return NJS_DECLINED; -} - - -njs_int_t -njs_lvlhsh_insert(njs_lvlhsh_t *lh, njs_lvlhsh_query_t *lhq) -{ - uint32_t key; - - if (njs_fast_path(lh->slot != NULL)) { - - key = lhq->key_hash; - - if (njs_lvlhsh_is_bucket(lh->slot)) { - return njs_lvlhsh_bucket_insert(lhq, &lh->slot, key, -1); - } - - return njs_lvlhsh_level_insert(lhq, &lh->slot, key, 0); - } - - return njs_lvlhsh_new_bucket(lhq, &lh->slot); -} - - -static njs_int_t -njs_lvlhsh_new_bucket(njs_lvlhsh_query_t *lhq, void **slot) -{ - uint32_t *bucket; - - bucket = lhq->proto->alloc(lhq->pool, njs_lvlhsh_bucket_size(lhq->proto)); - - if (njs_fast_path(bucket != NULL)) { - - njs_lvlhsh_set_entry_value(bucket, lhq->value); - njs_lvlhsh_set_entry_key(bucket, lhq->key_hash); - - *njs_lvlhsh_next_bucket(lhq->proto, bucket) = NULL; - - njs_lvlhsh_store_bucket(*slot, bucket); - - return NJS_OK; - } - - return NJS_ERROR; -} - - -static njs_int_t -njs_lvlhsh_level_insert(njs_lvlhsh_query_t *lhq, void **parent, uint32_t key, - njs_uint_t nlvl) -{ - void **slot, **lvl; - njs_int_t ret; - uintptr_t mask; - njs_uint_t shift; - - shift = lhq->proto->shift[nlvl]; - mask = ((uintptr_t) 1 << shift) - 1; - - lvl = njs_lvlhsh_level(*parent, mask); - slot = &lvl[key & mask]; - - if (*slot != NULL) { - key >>= shift; - - if (njs_lvlhsh_is_bucket(*slot)) { - return njs_lvlhsh_bucket_insert(lhq, slot, key, nlvl); - } - - return njs_lvlhsh_level_insert(lhq, slot, key, nlvl + 1); - } - - ret = njs_lvlhsh_new_bucket(lhq, slot); - - if (njs_fast_path(ret == NJS_OK)) { - njs_lvlhsh_count_inc(*parent); - } - - return ret; -} - - -static njs_int_t -njs_lvlhsh_bucket_insert(njs_lvlhsh_query_t *lhq, void **slot, uint32_t key, - njs_int_t nlvl) -{ - void **bkt, **vacant_bucket, *value; - uint32_t *bucket, *e, *vacant_entry; - njs_int_t ret; - uintptr_t n; - const void *new_value; - const njs_lvlhsh_proto_t *proto; - - bkt = slot; - vacant_entry = NULL; - vacant_bucket = NULL; - proto = lhq->proto; - - /* Search for duplicate entry in bucket chain. */ - - do { - bucket = njs_lvlhsh_bucket(proto, *bkt); - n = njs_lvlhsh_bucket_entries(proto, *bkt); - e = bucket; - - do { - if (njs_lvlhsh_valid_entry(e)) { - - if (njs_lvlhsh_entry_key(e) == lhq->key_hash) { - - value = njs_lvlhsh_entry_value(e); - - if (proto->test(lhq, value) == NJS_OK) { - - new_value = lhq->value; - lhq->value = value; - - if (lhq->replace) { - njs_lvlhsh_set_entry_value(e, new_value); - - return NJS_OK; - } - - return NJS_DECLINED; - } - } - - n--; - - } else { - /* - * Save a hole vacant position in bucket - * and continue to search for duplicate entry. - */ - if (vacant_entry == NULL) { - vacant_entry = e; - vacant_bucket = bkt; - } - } - - e += NJS_LVLHSH_ENTRY_SIZE; - - } while (n != 0); - - if (e < njs_lvlhsh_bucket_end(proto, bucket)) { - /* - * Save a vacant position on incomplete bucket's end - * and continue to search for duplicate entry. - */ - if (vacant_entry == NULL) { - vacant_entry = e; - vacant_bucket = bkt; - } - } - - bkt = njs_lvlhsh_next_bucket(proto, bucket); - - } while (*bkt != NULL); - - if (vacant_entry != NULL) { - njs_lvlhsh_set_entry_value(vacant_entry, lhq->value); - njs_lvlhsh_set_entry_key(vacant_entry, lhq->key_hash); - njs_lvlhsh_count_inc(*vacant_bucket); - - return NJS_OK; - } - - /* All buckets are full. */ - - nlvl++; - - if (njs_fast_path(proto->shift[nlvl] != 0)) { - - ret = njs_lvlhsh_convert_bucket_to_level(lhq, slot, nlvl, bucket); - - if (njs_fast_path(ret == NJS_OK)) { - return njs_lvlhsh_level_insert(lhq, slot, key, nlvl); - } - - return ret; - } - - /* The last allowed level, only buckets may be allocated here. */ - - return njs_lvlhsh_new_bucket(lhq, bkt); -} - - -static njs_int_t -njs_lvlhsh_convert_bucket_to_level(njs_lvlhsh_query_t *lhq, void **slot, - njs_uint_t nlvl, uint32_t *bucket) -{ - void *lvl, **level; - uint32_t *e, *end, key; - njs_int_t ret; - njs_uint_t i, shift, size; - njs_lvlhsh_query_t q; - const njs_lvlhsh_proto_t *proto; - - proto = lhq->proto; - size = njs_lvlhsh_level_size(proto, nlvl); - - lvl = proto->alloc(lhq->pool, size * (sizeof(void *))); - - if (njs_slow_path(lvl == NULL)) { - return NJS_ERROR; - } - - njs_memzero(lvl, size * (sizeof(void *))); - - level = lvl; - shift = 0; - - for (i = 0; i < nlvl; i++) { - /* - * Using SIMD operations in this trivial loop with maximum - * 8 iterations may increase code size by 170 bytes. - */ - njs_pragma_loop_disable_vectorization; - - shift += proto->shift[i]; - } - - end = njs_lvlhsh_bucket_end(proto, bucket); - - for (e = bucket; e < end; e += NJS_LVLHSH_ENTRY_SIZE) { - - q.proto = proto; - q.pool = lhq->pool; - q.value = njs_lvlhsh_entry_value(e); - key = njs_lvlhsh_entry_key(e); - q.key_hash = key; - - ret = njs_lvlhsh_level_convertion_insert(&q, &lvl, key >> shift, nlvl); - - if (njs_slow_path(ret != NJS_OK)) { - return njs_lvlhsh_free_level(lhq, level, size); - } - } - - *slot = lvl; - - proto->free(lhq->pool, bucket, njs_lvlhsh_bucket_size(proto)); - - return NJS_OK; -} - - -static njs_int_t -njs_lvlhsh_level_convertion_insert(njs_lvlhsh_query_t *lhq, void **parent, - uint32_t key, njs_uint_t nlvl) -{ - void **slot, **lvl; - njs_int_t ret; - uintptr_t mask; - njs_uint_t shift; - - shift = lhq->proto->shift[nlvl]; - mask = ((uintptr_t) 1 << shift) - 1; - - lvl = njs_lvlhsh_level(*parent, mask); - slot = &lvl[key & mask]; - - if (*slot == NULL) { - ret = njs_lvlhsh_new_bucket(lhq, slot); - - if (njs_fast_path(ret == NJS_OK)) { - njs_lvlhsh_count_inc(*parent); - } - - return ret; - } - - /* Only backets can be here. */ - - return njs_lvlhsh_bucket_convertion_insert(lhq, slot, key >> shift, nlvl); -} - - -/* - * The special bucket insertion procedure is required because during - * convertion lhq->key contains garbage values and the test function - * cannot be called. Besides, the procedure can be simpler because - * a new entry is inserted just after occupied entries. - */ - -static njs_int_t -njs_lvlhsh_bucket_convertion_insert(njs_lvlhsh_query_t *lhq, void **slot, - uint32_t key, njs_int_t nlvl) -{ - void **bkt; - uint32_t *bucket, *e; - njs_int_t ret; - uintptr_t n; - const njs_lvlhsh_proto_t *proto; - - bkt = slot; - proto = lhq->proto; - - do { - bucket = njs_lvlhsh_bucket(proto, *bkt); - n = njs_lvlhsh_bucket_entries(proto, *bkt); - e = bucket + n * NJS_LVLHSH_ENTRY_SIZE; - - if (njs_fast_path(e < njs_lvlhsh_bucket_end(proto, bucket))) { - - njs_lvlhsh_set_entry_value(e, lhq->value); - njs_lvlhsh_set_entry_key(e, lhq->key_hash); - njs_lvlhsh_count_inc(*bkt); - - return NJS_OK; - } - - bkt = njs_lvlhsh_next_bucket(proto, bucket); - - } while (*bkt != NULL); - - /* All buckets are full. */ - - nlvl++; - - if (njs_fast_path(proto->shift[nlvl] != 0)) { - - ret = njs_lvlhsh_convert_bucket_to_level(lhq, slot, nlvl, bucket); - - if (njs_fast_path(ret == NJS_OK)) { - return njs_lvlhsh_level_insert(lhq, slot, key, nlvl); - } - - return ret; - } - - /* The last allowed level, only buckets may be allocated here. */ - - return njs_lvlhsh_new_bucket(lhq, bkt); -} - - -static njs_int_t -njs_lvlhsh_free_level(njs_lvlhsh_query_t *lhq, void **level, njs_uint_t size) -{ - size_t bsize; - njs_uint_t i; - const njs_lvlhsh_proto_t *proto; - - proto = lhq->proto; - bsize = njs_lvlhsh_bucket_size(proto); - - for (i = 0; i < size; i++) { - - if (level[i] != NULL) { - /* - * Chained buckets are not possible here, since even - * in the worst case one bucket cannot be converted - * in two chained buckets but remains the same bucket. - */ - proto->free(lhq->pool, njs_lvlhsh_bucket(proto, level[i]), bsize); - } - } - - proto->free(lhq->pool, level, size * (sizeof(void *))); - - return NJS_ERROR; -} - - -njs_int_t -njs_lvlhsh_delete(njs_lvlhsh_t *lh, njs_lvlhsh_query_t *lhq) -{ - if (njs_fast_path(lh->slot != NULL)) { - - if (njs_lvlhsh_is_bucket(lh->slot)) { - return njs_lvlhsh_bucket_delete(lhq, &lh->slot); - } - - return njs_lvlhsh_level_delete(lhq, &lh->slot, lhq->key_hash, 0); - } - - return NJS_DECLINED; -} - - -static njs_int_t -njs_lvlhsh_level_delete(njs_lvlhsh_query_t *lhq, void **parent, uint32_t key, - njs_uint_t nlvl) -{ - size_t size; - void **slot, **lvl; - uintptr_t mask; - njs_int_t ret; - njs_uint_t shift; - - shift = lhq->proto->shift[nlvl]; - mask = ((uintptr_t) 1 << shift) - 1; - - lvl = njs_lvlhsh_level(*parent, mask); - slot = &lvl[key & mask]; - - if (*slot != NULL) { - - if (njs_lvlhsh_is_bucket(*slot)) { - ret = njs_lvlhsh_bucket_delete(lhq, slot); - - } else { - key >>= shift; - ret = njs_lvlhsh_level_delete(lhq, slot, key, nlvl + 1); - } - - if (*slot == NULL) { - njs_lvlhsh_count_dec(*parent); - - if (njs_lvlhsh_level_entries(*parent, mask) == 0) { - *parent = NULL; - size = njs_lvlhsh_level_size(lhq->proto, nlvl); - lhq->proto->free(lhq->pool, lvl, size * sizeof(void *)); - } - } - - return ret; - } - - return NJS_DECLINED; -} - - -static njs_int_t -njs_lvlhsh_bucket_delete(njs_lvlhsh_query_t *lhq, void **bkt) -{ - void *value; - size_t size; - uint32_t *bucket, *e; - uintptr_t n; - const njs_lvlhsh_proto_t *proto; - - proto = lhq->proto; - - do { - bucket = njs_lvlhsh_bucket(proto, *bkt); - n = njs_lvlhsh_bucket_entries(proto, *bkt); - e = bucket; - - do { - if (njs_lvlhsh_valid_entry(e)) { - - if (njs_lvlhsh_entry_key(e) == lhq->key_hash) { - - value = njs_lvlhsh_entry_value(e); - - if (proto->test(lhq, value) == NJS_OK) { - - if (njs_lvlhsh_bucket_entries(proto, *bkt) == 1) { - *bkt = *njs_lvlhsh_next_bucket(proto, bucket); - size = njs_lvlhsh_bucket_size(proto); - proto->free(lhq->pool, bucket, size); - - } else { - njs_lvlhsh_count_dec(*bkt); - njs_lvlhsh_set_entry_value(e, NULL); - } - - lhq->value = value; - - return NJS_OK; - } - } - - n--; - } - - e += NJS_LVLHSH_ENTRY_SIZE; - - } while (n != 0); - - bkt = njs_lvlhsh_next_bucket(proto, bucket); - - } while (*bkt != NULL); - - return NJS_DECLINED; -} - - -void * -njs_lvlhsh_each(const njs_lvlhsh_t *lh, njs_lvlhsh_each_t *lhe) -{ - void **slot; - - if (lhe->bucket == NJS_LVLHSH_BUCKET_DONE) { - slot = lh->slot; - - if (njs_lvlhsh_is_bucket(slot)) { - return NULL; - } - - } else { - if (njs_slow_path(lhe->bucket == NULL)) { - - /* The first iteration only. */ - - slot = lh->slot; - - if (slot == NULL) { - return NULL; - } - - if (!njs_lvlhsh_is_bucket(slot)) { - goto level; - } - - lhe->bucket = njs_lvlhsh_bucket(lhe->proto, slot); - lhe->entries = njs_lvlhsh_bucket_entries(lhe->proto, slot); - } - - return njs_lvlhsh_bucket_each(lhe); - } - -level: - - return njs_lvlhsh_level_each(lhe, slot, 0, 0); -} - - -static void * -njs_lvlhsh_level_each(njs_lvlhsh_each_t *lhe, void **level, njs_uint_t nlvl, - njs_uint_t shift) -{ - void **slot, *value; - uintptr_t mask; - njs_uint_t n, level_shift; - - level_shift = lhe->proto->shift[nlvl]; - mask = ((uintptr_t) 1 << level_shift) - 1; - - level = njs_lvlhsh_level(level, mask); - - do { - n = (lhe->current >> shift) & mask; - slot = level[n]; - - if (slot != NULL) { - if (njs_lvlhsh_is_bucket(slot)) { - - if (lhe->bucket != NJS_LVLHSH_BUCKET_DONE) { - - lhe->bucket = njs_lvlhsh_bucket(lhe->proto, slot); - lhe->entries = njs_lvlhsh_bucket_entries(lhe->proto, slot); - lhe->entry = 0; - - return njs_lvlhsh_bucket_each(lhe); - } - - lhe->bucket = NULL; - - } else { - value = njs_lvlhsh_level_each(lhe, slot, nlvl + 1, - shift + level_shift); - if (value != NULL) { - return value; - } - } - } - - lhe->current &= ~(mask << shift); - n = ((n + 1) & mask) << shift; - lhe->current |= n; - - } while (n != 0); - - return NULL; -} - - -static void * -njs_lvlhsh_bucket_each(njs_lvlhsh_each_t *lhe) -{ - void *value, **next; - uint32_t *bucket; - - /* At least one valid entry must present here. */ - do { - bucket = &lhe->bucket[lhe->entry]; - lhe->entry += NJS_LVLHSH_ENTRY_SIZE; - - } while (njs_lvlhsh_free_entry(bucket)); - - value = njs_lvlhsh_entry_value(bucket); - lhe->key_hash = njs_lvlhsh_entry_key(bucket); - - lhe->entries--; - - if (lhe->entries == 0) { - next = *njs_lvlhsh_next_bucket(lhe->proto, lhe->bucket); - - lhe->bucket = (next == NULL) ? NJS_LVLHSH_BUCKET_DONE - : njs_lvlhsh_bucket(lhe->proto, next); - - lhe->entries = njs_lvlhsh_bucket_entries(lhe->proto, next); - lhe->entry = 0; - } - - return value; -} diff --git a/src/njs_lvlhsh.h b/src/njs_lvlhsh.h deleted file mode 100644 index ab58de2d..00000000 --- a/src/njs_lvlhsh.h +++ /dev/null @@ -1,178 +0,0 @@ - -/* - * Copyright (C) Igor Sysoev - * Copyright (C) NGINX, Inc. - */ - -#ifndef _NJS_LVLHSH_H_INCLUDED_ -#define _NJS_LVLHSH_H_INCLUDED_ - - -typedef struct njs_lvlhsh_query_s njs_lvlhsh_query_t; - -typedef njs_int_t (*njs_lvlhsh_test_t)(njs_lvlhsh_query_t *lhq, void *data); -typedef void *(*njs_lvlhsh_alloc_t)(void *ctx, size_t size); -typedef void (*njs_lvlhsh_free_t)(void *ctx, void *p, size_t size); - - -#if (NJS_64BIT) - -#define NJS_LVLHSH_DEFAULT_BUCKET_SIZE 128 -#define NJS_LVLHSH_ENTRY_SIZE 3 - -/* 3 is shift of 64-bit pointer. */ -#define NJS_LVLHSH_MEMALIGN_SHIFT (NJS_MAX_MEMALIGN_SHIFT - 3) - -#else - -#define NJS_LVLHSH_DEFAULT_BUCKET_SIZE 64 -#define NJS_LVLHSH_ENTRY_SIZE 2 - -/* 2 is shift of 32-bit pointer. */ -#define NJS_LVLHSH_MEMALIGN_SHIFT (NJS_MAX_MEMALIGN_SHIFT - 2) - -#endif - - -#if (NJS_LVLHSH_MEMALIGN_SHIFT < 10) -#define NJS_LVLHSH_MAX_MEMALIGN_SHIFT NJS_LVLHSH_MEMALIGN_SHIFT -#else -#define NJS_LVLHSH_MAX_MEMALIGN_SHIFT 10 -#endif - - -#define NJS_LVLHSH_BUCKET_END(bucket_size) \ - (((bucket_size) - sizeof(void *)) \ - / (NJS_LVLHSH_ENTRY_SIZE * sizeof(uint32_t)) \ - * NJS_LVLHSH_ENTRY_SIZE) - - -#define NJS_LVLHSH_BUCKET_SIZE(bucket_size) \ - NJS_LVLHSH_BUCKET_END(bucket_size), bucket_size, (bucket_size - 1) - - -#define NJS_LVLHSH_DEFAULT \ - NJS_LVLHSH_BUCKET_SIZE(NJS_LVLHSH_DEFAULT_BUCKET_SIZE), \ - { 4, 4, 4, 4, 4, 4, 4, 0 } - - -#define NJS_LVLHSH_LARGE_SLAB \ - NJS_LVLHSH_BUCKET_SIZE(NJS_LVLHSH_DEFAULT_BUCKET_SIZE), \ - { 10, 4, 4, 4, 4, 4, 4, 0 } - - -#define NJS_LVLHSH_LARGE_MEMALIGN \ - NJS_LVLHSH_BUCKET_SIZE(NJS_LVLHSH_DEFAULT_BUCKET_SIZE), \ - { NJS_LVLHSH_MAX_MEMALIGN_SHIFT, 4, 4, 4, 4, 0, 0, 0 } - - -typedef struct { - uint32_t bucket_end; - uint32_t bucket_size; - uint32_t bucket_mask; - uint8_t shift[8]; - - njs_lvlhsh_test_t test; - njs_lvlhsh_alloc_t alloc; - njs_lvlhsh_free_t free; -} njs_lvlhsh_proto_t; - - -typedef struct { - void *slot; -} njs_lvlhsh_t; - - -struct njs_lvlhsh_query_s { - uint32_t key_hash; - njs_str_t key; - - uint8_t replace; /* 1 bit */ - void *value; - - const njs_lvlhsh_proto_t *proto; - void *pool; - - /* Opaque data passed for the test function. */ - void *data; -}; - - -#define njs_lvlhsh_is_empty(lh) \ - ((lh)->slot == NULL) - - -#define njs_lvlhsh_init(lh) \ - (lh)->slot = NULL - - -#define njs_lvlhsh_eq(lhl, lhr) \ - ((lhl)->slot == (lhr)->slot) - -/* - * njs_lvlhsh_find() finds a hash element. If the element has been - * found then it is stored in the lhq->value and njs_lvlhsh_find() - * returns NJS_OK. Otherwise NJS_DECLINED is returned. - * - * The required njs_lvlhsh_query_t fields: key_hash, key, proto. - */ -NJS_EXPORT njs_int_t njs_lvlhsh_find(const njs_lvlhsh_t *lh, - njs_lvlhsh_query_t *lhq); - -/* - * njs_lvlhsh_insert() adds a hash element. If the element already - * presents in lvlhsh and the lhq->replace flag is zero, then lhq->value - * is updated with the old element and NJS_DECLINED is returned. - * If the element already presents in lvlhsh and the lhq->replace flag - * is non-zero, then the old element is replaced with the new element. - * lhq->value is updated with the old element, and NJS_OK is returned. - * If the element is not present in lvlhsh, then it is inserted and - * NJS_OK is returned. The lhq->value is not changed. - * On memory allocation failure NJS_ERROR is returned. - * - * The required njs_lvlhsh_query_t fields: key_hash, key, proto, replace, value. - * The optional njs_lvlhsh_query_t fields: pool. - */ -NJS_EXPORT njs_int_t njs_lvlhsh_insert(njs_lvlhsh_t *lh, - njs_lvlhsh_query_t *lhq); - -/* - * njs_lvlhsh_delete() deletes a hash element. If the element has been - * found then it is removed from lvlhsh and is stored in the lhq->value, - * and NJS_OK is returned. Otherwise NJS_DECLINED is returned. - * - * The required njs_lvlhsh_query_t fields: key_hash, key, proto. - * The optional njs_lvlhsh_query_t fields: pool. - */ -NJS_EXPORT njs_int_t njs_lvlhsh_delete(njs_lvlhsh_t *lh, - njs_lvlhsh_query_t *lhq); - - -typedef struct { - const njs_lvlhsh_proto_t *proto; - - /* - * Fields to store current bucket entry position. They cannot be - * combined in a single bucket pointer with number of entries in low - * bits, because entry positions are not aligned. A current level is - * stored as key bit path from the root. - */ - uint32_t *bucket; - uint32_t current; - uint32_t entry; - uint32_t entries; - uint32_t key_hash; -} njs_lvlhsh_each_t; - - -#define njs_lvlhsh_each_init(lhe, _proto) \ - do { \ - njs_memzero(lhe, sizeof(njs_lvlhsh_each_t)); \ - (lhe)->proto = _proto; \ - } while (0) - -NJS_EXPORT void *njs_lvlhsh_each(const njs_lvlhsh_t *lh, - njs_lvlhsh_each_t *lhe); - - -#endif /* _NJS_LVLHSH_H_INCLUDED_ */ diff --git a/src/njs_module.c b/src/njs_module.c index 7d58972c..b971035a 100644 --- a/src/njs_module.c +++ b/src/njs_module.c @@ -9,13 +9,13 @@ static njs_int_t -njs_module_hash_test(njs_lvlhsh_query_t *lhq, void *data) +njs_module_hash_test(njs_flathsh_query_t *fhq, void *data) { njs_mod_t *module; module = *(njs_mod_t **) data; - if (njs_strstr_eq(&lhq->key, &module->name)) { + if (njs_strstr_eq(&fhq->key, &module->name)) { return NJS_OK; } @@ -23,35 +23,36 @@ njs_module_hash_test(njs_lvlhsh_query_t *lhq, void *data) } -const njs_lvlhsh_proto_t njs_modules_hash_proto +const njs_flathsh_proto_t njs_modules_hash_proto njs_aligned(64) = { - NJS_LVLHSH_DEFAULT, njs_module_hash_test, - njs_lvlhsh_alloc, - njs_lvlhsh_free, + njs_flathsh_proto_alloc, + njs_flathsh_proto_free, }; njs_mod_t * njs_module_find(njs_vm_t *vm, njs_str_t *name, njs_bool_t shared) { - njs_int_t ret; - njs_mod_t *shrd, *module; - njs_object_t *object; - njs_object_prop_t *prop; - njs_lvlhsh_query_t lhq; - - lhq.key = *name; - lhq.key_hash = njs_djb_hash(name->start, name->length); - lhq.proto = &njs_modules_hash_proto; - - if (njs_lvlhsh_find(&vm->modules_hash, &lhq) == NJS_OK) { - return njs_prop_module(lhq.value); + njs_int_t ret; + njs_mod_t *shrd, *module; + njs_object_t *object; + njs_object_prop_t *prop; + njs_flathsh_query_t fhq; + + fhq.key = *name; + fhq.key_hash = njs_djb_hash(name->start, name->length); + fhq.proto = &njs_modules_hash_proto; + + ret = njs_flathsh_find(&vm->modules_hash, &fhq); + if (ret == NJS_OK) { + return njs_prop_module(fhq.value); } - if (njs_lvlhsh_find(&vm->shared->modules_hash, &lhq) == NJS_OK) { - shrd = njs_prop_module(lhq.value); + ret = njs_flathsh_find(&vm->shared->modules_hash, &fhq); + if (ret == NJS_OK) { + shrd = ((njs_object_prop_t *)fhq.value)->u.mod; if (shared) { return shrd; @@ -70,15 +71,15 @@ njs_module_find(njs_vm_t *vm, njs_str_t *name, njs_bool_t shared) return NULL; } - lhq.replace = 0; - lhq.pool = vm->mem_pool; + fhq.replace = 0; + fhq.pool = vm->mem_pool; - ret = njs_lvlhsh_insert(&vm->modules_hash, &lhq); + ret = njs_flathsh_insert(&vm->modules_hash, &fhq); if (njs_slow_path(ret != NJS_OK)) { return NULL; } - prop = lhq.value; + prop = fhq.value; prop->u.mod = module; @@ -93,10 +94,10 @@ njs_module_find(njs_vm_t *vm, njs_str_t *name, njs_bool_t shared) njs_mod_t * njs_module_add(njs_vm_t *vm, njs_str_t *name, njs_value_t *value) { - njs_int_t ret; - njs_mod_t *module; - njs_object_prop_t *prop; - njs_lvlhsh_query_t lhq; + njs_int_t ret; + njs_mod_t *module; + njs_object_prop_t *prop; + njs_flathsh_query_t fhq; module = njs_mp_zalloc(vm->mem_pool, sizeof(njs_mod_t)); if (njs_slow_path(module == NULL)) { @@ -110,19 +111,19 @@ njs_module_add(njs_vm_t *vm, njs_str_t *name, njs_value_t *value) return NULL; } - lhq.replace = 0; - lhq.key = *name; - lhq.key_hash = njs_djb_hash(name->start, name->length); - lhq.pool = vm->mem_pool; - lhq.proto = &njs_modules_hash_proto; + fhq.replace = 0; + fhq.key = *name; + fhq.key_hash = njs_djb_hash(name->start, name->length); + fhq.pool = vm->mem_pool; + fhq.proto = &njs_modules_hash_proto; - ret = njs_lvlhsh_insert(&vm->shared->modules_hash, &lhq); + ret = njs_flathsh_insert(&vm->shared->modules_hash, &fhq); if (njs_slow_path(ret != NJS_OK)) { - njs_internal_error(vm, "lvlhsh insert failed"); + njs_internal_error(vm, "flathsh insert failed"); return NULL; } - prop = lhq.value; + prop = fhq.value; prop->u.mod = module; diff --git a/src/njs_module.h b/src/njs_module.h index 23853ad0..4510a9b0 100644 --- a/src/njs_module.h +++ b/src/njs_module.h @@ -23,8 +23,8 @@ njs_int_t njs_module_require(njs_vm_t *vm, njs_value_t *args, njs_uint_t nargs, njs_index_t unused, njs_value_t *retval); -extern njs_module_t *njs_modules[]; -extern const njs_lvlhsh_proto_t njs_modules_hash_proto; +extern njs_module_t *njs_modules[]; +extern const njs_flathsh_proto_t njs_modules_hash_proto; #endif /* _NJS_MODULE_H_INCLUDED_ */ diff --git a/src/njs_number.c b/src/njs_number.c index 29df50a5..15f08651 100644 --- a/src/njs_number.c +++ b/src/njs_number.c @@ -35,7 +35,7 @@ njs_key_to_index(const njs_value_t *value) array = njs_array(value); - if (njs_lvlhsh_is_empty(&array->object.hash)) { + if (njs_flathsh_is_empty(&array->object.hash)) { if (array->length == 0) { /* An empty array value is zero. */ diff --git a/src/njs_object.c b/src/njs_object.c index 0c592176..7f0b1822 100644 --- a/src/njs_object.c +++ b/src/njs_object.c @@ -15,7 +15,7 @@ typedef enum { static njs_object_prop_t *njs_object_exist_in_proto(const njs_object_t *begin, - const njs_object_t *end, njs_flathsh_query_t *lhq); + const njs_object_t *end, njs_flathsh_query_t *fhq); static njs_int_t njs_object_enumerate_array(njs_vm_t *vm, const njs_array_t *array, njs_array_t *items, uint32_t flags); static njs_int_t njs_object_enumerate_typed_array(njs_vm_t *vm, @@ -41,8 +41,8 @@ njs_object_alloc(njs_vm_t *vm) object = njs_mp_alloc(vm->mem_pool, sizeof(njs_object_t)); if (njs_fast_path(object != NULL)) { - njs_lvlhsh_init(&object->hash); - njs_lvlhsh_init(&object->shared_hash); + njs_flathsh_init(&object->hash); + njs_flathsh_init(&object->shared_hash); object->__proto__ = njs_vm_proto(vm, NJS_OBJ_TYPE_OBJECT); object->slots = NULL; object->type = NJS_OBJECT; @@ -126,13 +126,13 @@ njs_object_value_alloc(njs_vm_t *vm, njs_uint_t prototype_index, size_t extra, return NULL; } - njs_lvlhsh_init(&ov->object.hash); + njs_flathsh_init(&ov->object.hash); if (prototype_index == NJS_OBJ_TYPE_STRING) { ov->object.shared_hash = vm->shared->string_instance_hash; } else { - njs_lvlhsh_init(&ov->object.shared_hash); + njs_flathsh_init(&ov->object.shared_hash); } ov->object.type = NJS_OBJECT_VALUE; @@ -158,23 +158,23 @@ njs_object_hash_create(njs_vm_t *vm, njs_flathsh_t *hash, { njs_int_t ret; njs_object_prop_t *obj_prop; - njs_flathsh_query_t lhq; + njs_flathsh_query_t fhq; - lhq.replace = 0; - lhq.proto = &njs_object_hash_proto; - lhq.pool = vm->mem_pool; + fhq.replace = 0; + fhq.proto = &njs_object_hash_proto; + fhq.pool = vm->mem_pool; while (n != 0) { - lhq.key_hash = prop->desc.atom_id; - lhq.value = (void *) prop; + fhq.key_hash = prop->desc.atom_id; + fhq.value = (void *) prop; - ret = njs_flathsh_unique_insert(hash, &lhq); + ret = njs_flathsh_unique_insert(hash, &fhq); if (njs_slow_path(ret != NJS_OK)) { - njs_internal_error(vm, "lvlhsh insert failed"); + njs_internal_error(vm, "flathsh insert failed"); return NJS_ERROR; } - obj_prop = lhq.value; + obj_prop = fhq.value; obj_prop->type = prop->desc.type; obj_prop->enumerable = prop->desc.enumerable; @@ -193,10 +193,9 @@ njs_object_hash_create(njs_vm_t *vm, njs_flathsh_t *hash, const njs_flathsh_proto_t njs_object_hash_proto njs_aligned(64) = { - 0, NULL, - njs_lvlhsh_alloc, - njs_lvlhsh_free, + njs_flathsh_proto_alloc, + njs_flathsh_proto_free, }; @@ -380,28 +379,28 @@ njs_object_entries(njs_vm_t *vm, njs_value_t *args, njs_uint_t nargs, static njs_object_prop_t * njs_object_exist_in_proto(const njs_object_t *object, const njs_object_t *end, - njs_flathsh_query_t *lhq) + njs_flathsh_query_t *fhq) { njs_int_t ret; njs_object_prop_t *prop; while (object != end) { - ret = njs_flathsh_unique_find(&object->hash, lhq); + ret = njs_flathsh_unique_find(&object->hash, fhq); if (njs_fast_path(ret == NJS_OK)) { - prop = lhq->value; + prop = fhq->value; if (prop->type == NJS_WHITEOUT) { goto next; } - return lhq->value; + return fhq->value; } - ret = njs_flathsh_unique_find(&object->shared_hash, lhq); + ret = njs_flathsh_unique_find(&object->shared_hash, fhq); if (njs_fast_path(ret == NJS_OK)) { - return lhq->value; + return fhq->value; } next: @@ -919,7 +918,7 @@ njs_get_own_ordered_keys(njs_vm_t *vm, const njs_object_t *object, njs_flathsh_elt_t *elt; njs_flathsh_each_t lhe; const njs_flathsh_t *hash; - njs_flathsh_query_t lhq; + njs_flathsh_query_t fhq; items_length = items->length; @@ -933,7 +932,7 @@ njs_get_own_ordered_keys(njs_vm_t *vm, const njs_object_t *object, return NJS_ERROR; } - lhq.proto = &njs_object_hash_proto; + fhq.proto = &njs_object_hash_proto; njs_flathsh_each_init(&lhe, &njs_object_hash_proto); hash = &object->shared_hash; @@ -959,14 +958,14 @@ njs_get_own_ordered_keys(njs_vm_t *vm, const njs_object_t *object, continue; } - lhq.key_hash = elt->key_hash; + fhq.key_hash = elt->key_hash; - ext_prop = njs_object_exist_in_proto(parent, object, &lhq); + ext_prop = njs_object_exist_in_proto(parent, object, &fhq); if (ext_prop != NULL) { continue; } - ret = njs_flathsh_unique_find(&object->hash, &lhq); + ret = njs_flathsh_unique_find(&object->hash, &fhq); if (ret != NJS_OK) { if (!(prop->enumerable || !(flags & NJS_ENUM_ENUMERABLE_ONLY))) { @@ -989,7 +988,7 @@ njs_get_own_ordered_keys(njs_vm_t *vm, const njs_object_t *object, } else { - if (!(((njs_object_prop_t *) (lhq.value))->enumerable + if (!(((njs_object_prop_t *) (fhq.value))->enumerable || !(flags & NJS_ENUM_ENUMERABLE_ONLY))) { continue; @@ -1000,7 +999,7 @@ njs_get_own_ordered_keys(njs_vm_t *vm, const njs_object_t *object, num = njs_string_to_index(&prop_name); if (!njs_number_is_integer_index(num)) { - njs_object_prop_t *hash_prop = lhq.value; + njs_object_prop_t *hash_prop = fhq.value; if (hash_prop->type != NJS_WHITEOUT) { njs_process_prop(vm, &prop_name, flags, items_string, @@ -1035,9 +1034,9 @@ local_hash: continue; } - lhq.key_hash = elt->key_hash; + fhq.key_hash = elt->key_hash; - ext_prop = njs_object_exist_in_proto(parent, object, &lhq); + ext_prop = njs_object_exist_in_proto(parent, object, &fhq); if (ext_prop != NULL) { continue; } @@ -1052,7 +1051,7 @@ local_hash: } else { - ret = njs_flathsh_unique_find(&object->shared_hash, &lhq); + ret = njs_flathsh_unique_find(&object->shared_hash, &fhq); if (ret != NJS_OK) { /* prop is: in_hash && !in_shared_hash */ @@ -1326,8 +1325,8 @@ njs_object_make_shared(njs_vm_t *vm, njs_object_t *object) (void) njs_traverse_visit(&visited, &s->value); - pq.lhq.replace = 0; - pq.lhq.pool = vm->mem_pool; + pq.fhq.replace = 0; + pq.fhq.pool = vm->mem_pool; for ( ;; ) { @@ -1359,16 +1358,16 @@ njs_object_make_shared(njs_vm_t *vm, njs_object_t *object) } - prop = pq.lhq.value; + prop = pq.fhq.value; ret = njs_flathsh_unique_insert(&njs_object(&s->value)->shared_hash, - &pq.lhq); + &pq.fhq); if (njs_slow_path(ret != NJS_OK)) { njs_internal_error(vm, "flathsh insert failed"); return NJS_ERROR; } - obj_prop = pq.lhq.value; + obj_prop = pq.fhq.value; obj_prop->type = prop->type; obj_prop->enumerable = prop->enumerable; @@ -1481,9 +1480,9 @@ njs_object_traverse(njs_vm_t *vm, njs_object_t *object, void *ctx, return NJS_ERROR; } - prop = pq.lhq.value; + prop = pq.fhq.value; s->prop = prop; - s->atom_id = pq.lhq.key_hash; + s->atom_id = pq.fhq.key_hash; ret = cb(vm, s, ctx); if (njs_slow_path(ret != NJS_OK)) { @@ -1497,7 +1496,7 @@ njs_object_traverse(njs_vm_t *vm, njs_object_t *object, void *ctx, njs_value_assign(&value, njs_prop_value(prop)); if (prop->type == NJS_PROPERTY_HANDLER) { - ret = njs_prop_handler(prop)(vm, prop, pq.lhq.key_hash, &s->value, + ret = njs_prop_handler(prop)(vm, prop, pq.fhq.key_hash, &s->value, NULL, &value); if (njs_slow_path(ret == NJS_ERROR)) { return ret; @@ -1617,7 +1616,7 @@ njs_object_define_properties(njs_vm_t *vm, njs_value_t *args, njs_uint_t nargs, goto done; } - prop = pq.lhq.value; + prop = pq.fhq.value; if (ret == NJS_DECLINED || !prop->enumerable) { continue; @@ -1676,7 +1675,7 @@ njs_object_get_own_property_descriptors(njs_vm_t *vm, njs_value_t *args, njs_value_t descriptor, *value, *key; njs_object_t *descriptors; njs_object_prop_t *prop; - njs_flathsh_query_t lhq; + njs_flathsh_query_t fhq; value = njs_arg(args, nargs, 1); @@ -1701,9 +1700,9 @@ njs_object_get_own_property_descriptors(njs_vm_t *vm, njs_value_t *args, goto done; } - lhq.replace = 0; - lhq.pool = vm->mem_pool; - lhq.proto = &njs_object_hash_proto; + fhq.replace = 0; + fhq.pool = vm->mem_pool; + fhq.proto = &njs_object_hash_proto; for (i = 0; i < length; i++) { key = &names->start[i]; @@ -1713,15 +1712,15 @@ njs_object_get_own_property_descriptors(njs_vm_t *vm, njs_value_t *args, goto done; } - lhq.key_hash = key->atom_id; + fhq.key_hash = key->atom_id; - ret = njs_flathsh_unique_insert(&descriptors->hash, &lhq); + ret = njs_flathsh_unique_insert(&descriptors->hash, &fhq); if (njs_slow_path(ret != NJS_OK)) { - njs_internal_error(vm, "lvlhsh insert failed"); + njs_internal_error(vm, "flathsh insert failed"); goto done; } - prop = lhq.value; + prop = fhq.value; prop->type = NJS_PROPERTY; prop->enumerable = 1; @@ -2069,7 +2068,7 @@ njs_object_assign(njs_vm_t *vm, njs_value_t *args, njs_uint_t nargs, goto exception; } - prop = pq.lhq.value; + prop = pq.fhq.value; if (!prop->enumerable) { continue; } @@ -2188,22 +2187,22 @@ njs_property_prototype_create(njs_vm_t *vm, njs_flathsh_t *hash, { njs_int_t ret; njs_object_prop_t *prop; - njs_flathsh_query_t lhq; + njs_flathsh_query_t fhq; - lhq.key_hash = NJS_ATOM_STRING_prototype; + fhq.key_hash = NJS_ATOM_STRING_prototype; - lhq.replace = 1; - lhq.pool = vm->mem_pool; - lhq.proto = &njs_object_hash_proto; + fhq.replace = 1; + fhq.pool = vm->mem_pool; + fhq.proto = &njs_object_hash_proto; - ret = njs_flathsh_unique_insert(hash, &lhq); + ret = njs_flathsh_unique_insert(hash, &fhq); if (njs_slow_path(ret != NJS_OK)) { - njs_internal_error(vm, "lvlhsh insert failed"); + njs_internal_error(vm, "flathsh insert failed"); return NULL; } - prop = lhq.value; + prop = fhq.value; prop->type = NJS_PROPERTY; prop->enumerable = 0; @@ -2448,21 +2447,21 @@ njs_property_constructor_set(njs_vm_t *vm, njs_flathsh_t *hash, { njs_int_t ret; njs_object_prop_t *prop; - njs_flathsh_query_t lhq; + njs_flathsh_query_t fhq; - lhq.key_hash = NJS_ATOM_STRING_constructor; + fhq.key_hash = NJS_ATOM_STRING_constructor; - lhq.replace = 1; - lhq.pool = vm->mem_pool; - lhq.proto = &njs_object_hash_proto; + fhq.replace = 1; + fhq.pool = vm->mem_pool; + fhq.proto = &njs_object_hash_proto; - ret = njs_flathsh_unique_insert(hash, &lhq); + ret = njs_flathsh_unique_insert(hash, &fhq); if (njs_slow_path(ret != NJS_OK)) { - njs_internal_error(vm, "lvlhsh insert/replace failed"); + njs_internal_error(vm, "flathsh insert/replace failed"); return NULL; } - prop = lhq.value; + prop = fhq.value; prop->type = NJS_PROPERTY; prop->enumerable = 0; @@ -2530,7 +2529,7 @@ njs_object_to_string(njs_vm_t *vm, njs_value_t *this, njs_value_t *retval) name = NJS_ATOM_STRING__object_Array_; } else if (njs_is_object(this) - && njs_lvlhsh_eq(&njs_object(this)->shared_hash, + && njs_flathsh_eq(&njs_object(this)->shared_hash, &vm->shared->arguments_object_instance_hash)) { name = NJS_ATOM_STRING__object_Arguments_; @@ -2671,7 +2670,7 @@ njs_object_prototype_prop_is_enumerable(njs_vm_t *vm, njs_value_t *args, switch (ret) { case NJS_OK: - prop = pq.lhq.value; + prop = pq.fhq.value; njs_set_boolean(retval, prop->enumerable); break; diff --git a/src/njs_object.h b/src/njs_object.h index dd5334d2..d2b49180 100644 --- a/src/njs_object.h +++ b/src/njs_object.h @@ -104,7 +104,7 @@ njs_int_t njs_prop_private_copy(njs_vm_t *vm, njs_property_query_t *pq, void njs_object_prop_init(njs_object_prop_t *prop, njs_object_prop_type_t type, uint8_t attributes); njs_int_t njs_object_property(njs_vm_t *vm, njs_object_t *object, - njs_flathsh_query_t *lhq, njs_value_t *retval); + njs_flathsh_query_t *fhq, njs_value_t *retval); njs_object_prop_t *njs_object_property_add(njs_vm_t *vm, njs_value_t *object, uint32_t atom_id, njs_bool_t replace); njs_int_t njs_object_prop_define(njs_vm_t *vm, njs_value_t *object, diff --git a/src/njs_object_prop.c b/src/njs_object_prop.c index 6b93960c..aeaeb71b 100644 --- a/src/njs_object_prop.c +++ b/src/njs_object_prop.c @@ -44,24 +44,24 @@ njs_object_prop_init(njs_object_prop_t *prop, njs_object_prop_type_t type, njs_int_t njs_object_property(njs_vm_t *vm, njs_object_t *object, - njs_flathsh_query_t *lhq, njs_value_t *retval) + njs_flathsh_query_t *fhq, njs_value_t *retval) { njs_int_t ret; njs_value_t value; njs_object_prop_t *prop; do { - ret = njs_flathsh_unique_find(&object->hash, lhq); + ret = njs_flathsh_unique_find(&object->hash, fhq); if (njs_fast_path(ret == NJS_OK)) { - prop = lhq->value; + prop = fhq->value; if (prop->type != NJS_WHITEOUT) { goto found; } } - ret = njs_flathsh_unique_find(&object->shared_hash, lhq); + ret = njs_flathsh_unique_find(&object->shared_hash, fhq); if (njs_fast_path(ret == NJS_OK)) { goto found; @@ -77,7 +77,7 @@ njs_object_property(njs_vm_t *vm, njs_object_t *object, found: - prop = lhq->value; + prop = fhq->value; if (njs_is_data_descriptor(prop)) { njs_value_assign(retval, njs_prop_value(prop)); @@ -101,20 +101,20 @@ njs_object_property_add(njs_vm_t *vm, njs_value_t *object, unsigned atom_id, { njs_int_t ret; njs_object_prop_t *prop; - njs_flathsh_query_t lhq; + njs_flathsh_query_t fhq; - lhq.key_hash = atom_id; - lhq.replace = replace; - lhq.pool = vm->mem_pool; - lhq.proto = &njs_object_hash_proto; + fhq.key_hash = atom_id; + fhq.replace = replace; + fhq.pool = vm->mem_pool; + fhq.proto = &njs_object_hash_proto; - ret = njs_flathsh_unique_insert(njs_object_hash(object), &lhq); + ret = njs_flathsh_unique_insert(njs_object_hash(object), &fhq); if (njs_slow_path(ret != NJS_OK)) { - njs_internal_error(vm, "lvlhsh insert failed"); + njs_internal_error(vm, "flathsh insert failed"); return NULL; } - prop = lhq.value; + prop = fhq.value; prop->type = NJS_PROPERTY; prop->enumerable = 1; @@ -213,9 +213,9 @@ again: set_prop: if (!njs_object(object)->extensible) { - njs_atom_string_get(vm, atom_id, &pq.lhq.key); + njs_atom_string_get(vm, atom_id, &pq.fhq.key); njs_type_error(vm, "Cannot add property \"%V\", " - "object is not extensible", &pq.lhq.key); + "object is not extensible", &pq.fhq.key); return NJS_ERROR; } @@ -264,8 +264,8 @@ set_prop: prop->configurable = 0; } - if (njs_slow_path(pq.lhq.value != NULL)) { - prev = pq.lhq.value; + if (njs_slow_path(pq.fhq.value != NULL)) { + prev = pq.fhq.value; if (njs_slow_path(prev->type == NJS_WHITEOUT)) { /* Previously deleted property. */ @@ -276,18 +276,18 @@ set_prop: } else { - pq.lhq.key_hash = atom_id; - pq.lhq.proto = &njs_object_hash_proto; - pq.lhq.replace = 0; - pq.lhq.pool = vm->mem_pool; + pq.fhq.key_hash = atom_id; + pq.fhq.proto = &njs_object_hash_proto; + pq.fhq.replace = 0; + pq.fhq.pool = vm->mem_pool; - ret = njs_flathsh_unique_insert(njs_object_hash(object), &pq.lhq); + ret = njs_flathsh_unique_insert(njs_object_hash(object), &pq.fhq); if (njs_slow_path(ret != NJS_OK)) { - njs_internal_error(vm, "lvlhsh insert failed"); + njs_internal_error(vm, "flathsh insert failed"); return NJS_ERROR; } - obj_prop = pq.lhq.value; + obj_prop = pq.fhq.value; obj_prop->enumerable = prop->enumerable; obj_prop->configurable = prop->configurable; obj_prop->writable = prop->writable; @@ -300,7 +300,7 @@ set_prop: /* Updating existing prop. */ - prev = pq.lhq.value; + prev = pq.fhq.value; switch (prev->type) { case NJS_PROPERTY: @@ -402,7 +402,7 @@ set_prop: */ if (pq.temp) { - pq.lhq.value = NULL; + pq.fhq.value = NULL; prop->configurable = prev->configurable; prop->enumerable = prev->enumerable; goto set_prop; @@ -457,7 +457,7 @@ set_prop: done: if (njs_slow_path(njs_is_fast_array(object) - && pq.lhq.key_hash == NJS_ATOM_STRING_length) + && pq.fhq.key_hash == NJS_ATOM_STRING_length) && (set_writable && !prop->writable)) { array = njs_array(object); @@ -498,7 +498,7 @@ done: } if (ret == NJS_DECLINED) { - pq.lhq.value = NULL; + pq.fhq.value = NULL; goto set_prop; } @@ -511,7 +511,7 @@ done: } else { if (njs_slow_path(njs_is_array(object) - && pq.lhq.key_hash == NJS_ATOM_STRING_length)) + && pq.fhq.key_hash == NJS_ATOM_STRING_length)) { if (!prev->configurable && !prev->writable @@ -555,8 +555,8 @@ done: exception: - njs_atom_string_get(vm, atom_id, &pq.lhq.key); - njs_type_error(vm, "Cannot redefine property: \"%V\"", &pq.lhq.key); + njs_atom_string_get(vm, atom_id, &pq.fhq.key); + njs_type_error(vm, "Cannot redefine property: \"%V\"", &pq.fhq.key); return NJS_ERROR; } @@ -572,18 +572,18 @@ njs_prop_private_copy(njs_vm_t *vm, njs_property_query_t *pq, njs_function_t *function; njs_object_prop_t *prop, *shared; - shared = pq->lhq.value; + shared = pq->fhq.value; - pq->lhq.replace = 0; - pq->lhq.pool = vm->mem_pool; + pq->fhq.replace = 0; + pq->fhq.pool = vm->mem_pool; - ret = njs_flathsh_unique_insert(&proto->hash, &pq->lhq); + ret = njs_flathsh_unique_insert(&proto->hash, &pq->fhq); if (njs_slow_path(ret != NJS_OK)) { - njs_internal_error(vm, "lvlhsh insert failed"); + njs_internal_error(vm, "flathsh insert failed"); return NJS_ERROR; } - prop = pq->lhq.value; + prop = pq->fhq.value; prop->enumerable = shared->enumerable; prop->configurable = shared->configurable; prop->writable = shared->writable; @@ -640,7 +640,7 @@ njs_prop_private_copy(njs_vm_t *vm, njs_property_query_t *pq, return NJS_ERROR; } - ret = njs_atom_to_value(vm, &prop_name, pq->lhq.key_hash); + ret = njs_atom_to_value(vm, &prop_name, pq->fhq.key_hash); if (ret != NJS_OK) { return NJS_ERROR; } @@ -665,7 +665,7 @@ njs_descriptor_prop(njs_vm_t *vm, const njs_value_t *desc, njs_value_t value; njs_object_t *desc_object; njs_function_t *getter, *setter; - njs_flathsh_query_t lhq; + njs_flathsh_query_t fhq; if (!njs_is_object(desc)) { njs_type_error(vm, "property descriptor must be an object"); @@ -685,10 +685,10 @@ njs_descriptor_prop(njs_vm_t *vm, const njs_value_t *desc, setter = NJS_PROP_PTR_UNSET; desc_object = njs_object(desc); - lhq.proto = &njs_object_hash_proto; - lhq.key_hash = NJS_ATOM_STRING_get; + fhq.proto = &njs_object_hash_proto; + fhq.key_hash = NJS_ATOM_STRING_get; - ret = njs_object_property(vm, desc_object, &lhq, &value); + ret = njs_object_property(vm, desc_object, &fhq, &value); if (njs_slow_path(ret == NJS_ERROR)) { return NULL; } @@ -703,9 +703,9 @@ njs_descriptor_prop(njs_vm_t *vm, const njs_value_t *desc, getter = njs_is_function(&value) ? njs_function(&value) : NULL; } - lhq.key_hash = NJS_ATOM_STRING_set; + fhq.key_hash = NJS_ATOM_STRING_set; - ret = njs_object_property(vm, desc_object, &lhq, &value); + ret = njs_object_property(vm, desc_object, &fhq, &value); if (njs_slow_path(ret == NJS_ERROR)) { return NULL; } @@ -720,9 +720,9 @@ njs_descriptor_prop(njs_vm_t *vm, const njs_value_t *desc, setter = njs_is_function(&value) ? njs_function(&value) : NULL; } - lhq.key_hash = NJS_ATOM_STRING_value; + fhq.key_hash = NJS_ATOM_STRING_value; - ret = njs_object_property(vm, desc_object, &lhq, &value); + ret = njs_object_property(vm, desc_object, &fhq, &value); if (njs_slow_path(ret == NJS_ERROR)) { return NULL; } @@ -732,9 +732,9 @@ njs_descriptor_prop(njs_vm_t *vm, const njs_value_t *desc, njs_value_assign(njs_prop_value(prop), &value); } - lhq.key_hash = NJS_ATOM_STRING_writable; + fhq.key_hash = NJS_ATOM_STRING_writable; - ret = njs_object_property(vm, desc_object, &lhq, &value); + ret = njs_object_property(vm, desc_object, &fhq, &value); if (njs_slow_path(ret == NJS_ERROR)) { return NULL; } @@ -751,9 +751,9 @@ njs_descriptor_prop(njs_vm_t *vm, const njs_value_t *desc, return NULL; } - lhq.key_hash = NJS_ATOM_STRING_enumerable; + fhq.key_hash = NJS_ATOM_STRING_enumerable; - ret = njs_object_property(vm, desc_object, &lhq, &value); + ret = njs_object_property(vm, desc_object, &fhq, &value); if (njs_slow_path(ret == NJS_ERROR)) { return NULL; } @@ -763,9 +763,9 @@ njs_descriptor_prop(njs_vm_t *vm, const njs_value_t *desc, *set_enumerable = 1; } - lhq.key_hash = NJS_ATOM_STRING_configurable; + fhq.key_hash = NJS_ATOM_STRING_configurable; - ret = njs_object_property(vm, desc_object, &lhq, &value); + ret = njs_object_property(vm, desc_object, &fhq, &value); if (njs_slow_path(ret == NJS_ERROR)) { return NULL; } @@ -793,7 +793,7 @@ njs_object_prop_descriptor(njs_vm_t *vm, njs_value_t *dest, njs_object_t *desc; njs_object_prop_t *pr, *prop; const njs_value_t *setval; - njs_flathsh_query_t lhq; + njs_flathsh_query_t fhq; njs_property_query_t pq; njs_property_query_init(&pq, NJS_PROPERTY_QUERY_GET, 1); @@ -809,7 +809,7 @@ njs_object_prop_descriptor(njs_vm_t *vm, njs_value_t *dest, switch (ret) { case NJS_OK: - prop = pq.lhq.value; + prop = pq.fhq.value; switch (prop->type) { case NJS_PROPERTY: @@ -849,20 +849,20 @@ njs_object_prop_descriptor(njs_vm_t *vm, njs_value_t *dest, return NJS_ERROR; } - lhq.proto = &njs_object_hash_proto; - lhq.replace = 0; - lhq.pool = vm->mem_pool; + fhq.proto = &njs_object_hash_proto; + fhq.replace = 0; + fhq.pool = vm->mem_pool; if (njs_is_data_descriptor(prop)) { - lhq.key_hash = NJS_ATOM_STRING_value; + fhq.key_hash = NJS_ATOM_STRING_value; - ret = njs_flathsh_unique_insert(&desc->hash, &lhq); + ret = njs_flathsh_unique_insert(&desc->hash, &fhq); if (njs_slow_path(ret != NJS_OK)) { - njs_internal_error(vm, "lvlhsh insert failed"); + njs_internal_error(vm, "flathsh insert failed"); return NJS_ERROR; } - pr = lhq.value; + pr = fhq.value; pr->type = NJS_PROPERTY; pr->enumerable = 1; @@ -870,17 +870,17 @@ njs_object_prop_descriptor(njs_vm_t *vm, njs_value_t *dest, pr->writable = 1; pr->u.value = *(njs_prop_value(prop)); - lhq.key_hash = NJS_ATOM_STRING_writable; + fhq.key_hash = NJS_ATOM_STRING_writable; setval = (prop->writable == 1) ? &njs_value_true : &njs_value_false; - ret = njs_flathsh_unique_insert(&desc->hash, &lhq); + ret = njs_flathsh_unique_insert(&desc->hash, &fhq); if (njs_slow_path(ret != NJS_OK)) { - njs_internal_error(vm, "lvlhsh insert failed"); + njs_internal_error(vm, "flathsh insert failed"); return NJS_ERROR; } - pr = lhq.value; + pr = fhq.value; pr->type = NJS_PROPERTY; pr->enumerable = 1; @@ -890,15 +890,15 @@ njs_object_prop_descriptor(njs_vm_t *vm, njs_value_t *dest, } else { - lhq.key_hash = NJS_ATOM_STRING_get; + fhq.key_hash = NJS_ATOM_STRING_get; - ret = njs_flathsh_unique_insert(&desc->hash, &lhq); + ret = njs_flathsh_unique_insert(&desc->hash, &fhq); if (njs_slow_path(ret != NJS_OK)) { - njs_internal_error(vm, "lvlhsh insert failed"); + njs_internal_error(vm, "flathsh insert failed"); return NJS_ERROR; } - pr = lhq.value; + pr = fhq.value; pr->type = NJS_PROPERTY; pr->enumerable = 1; @@ -910,15 +910,15 @@ njs_object_prop_descriptor(njs_vm_t *vm, njs_value_t *dest, njs_set_function(njs_prop_value(pr), njs_prop_getter(prop)); } - lhq.key_hash = NJS_ATOM_STRING_set; + fhq.key_hash = NJS_ATOM_STRING_set; - ret = njs_flathsh_unique_insert(&desc->hash, &lhq); + ret = njs_flathsh_unique_insert(&desc->hash, &fhq); if (njs_slow_path(ret != NJS_OK)) { - njs_internal_error(vm, "lvlhsh insert failed"); + njs_internal_error(vm, "flathsh insert failed"); return NJS_ERROR; } - pr = lhq.value; + pr = fhq.value; pr->type = NJS_PROPERTY; pr->enumerable = 1; @@ -931,17 +931,17 @@ njs_object_prop_descriptor(njs_vm_t *vm, njs_value_t *dest, } } - lhq.key_hash = NJS_ATOM_STRING_enumerable; + fhq.key_hash = NJS_ATOM_STRING_enumerable; setval = (prop->enumerable == 1) ? &njs_value_true : &njs_value_false; - ret = njs_flathsh_unique_insert(&desc->hash, &lhq); + ret = njs_flathsh_unique_insert(&desc->hash, &fhq); if (njs_slow_path(ret != NJS_OK)) { - njs_internal_error(vm, "lvlhsh insert failed"); + njs_internal_error(vm, "flathsh insert failed"); return NJS_ERROR; } - pr = lhq.value; + pr = fhq.value; pr->type = NJS_PROPERTY; pr->enumerable = 1; @@ -949,17 +949,17 @@ njs_object_prop_descriptor(njs_vm_t *vm, njs_value_t *dest, pr->writable = 1; pr->u.value = *setval; - lhq.key_hash = NJS_ATOM_STRING_configurable; + fhq.key_hash = NJS_ATOM_STRING_configurable; setval = (prop->configurable == 1) ? &njs_value_true : &njs_value_false; - ret = njs_flathsh_unique_insert(&desc->hash, &lhq); + ret = njs_flathsh_unique_insert(&desc->hash, &fhq); if (njs_slow_path(ret != NJS_OK)) { - njs_internal_error(vm, "lvlhsh insert failed"); + njs_internal_error(vm, "flathsh insert failed"); return NJS_ERROR; } - pr = lhq.value; + pr = fhq.value; pr->type = NJS_PROPERTY; pr->enumerable = 1; @@ -1007,7 +1007,7 @@ njs_object_props_init(njs_vm_t *vm, const njs_object_init_t* init, njs_int_t ret; njs_object_t *object; njs_object_prop_t *prop; - njs_flathsh_query_t lhq; + njs_flathsh_query_t fhq; object = njs_object_alloc(vm); if (object == NULL) { @@ -1020,18 +1020,18 @@ njs_object_props_init(njs_vm_t *vm, const njs_object_init_t* init, return NJS_ERROR; } - lhq.key_hash = atom_id; - lhq.replace = 1; - lhq.pool = vm->mem_pool; - lhq.proto = &njs_object_hash_proto; + fhq.key_hash = atom_id; + fhq.replace = 1; + fhq.pool = vm->mem_pool; + fhq.proto = &njs_object_hash_proto; - ret = njs_flathsh_unique_insert(njs_object_hash(value), &lhq); + ret = njs_flathsh_unique_insert(njs_object_hash(value), &fhq); if (njs_slow_path(ret != NJS_OK)) { - njs_internal_error(vm, "lvlhsh insert failed"); + njs_internal_error(vm, "flathsh insert failed"); return NJS_ERROR; } - prop = lhq.value; + prop = fhq.value; prop->enumerable = base->enumerable; prop->configurable = base->configurable; diff --git a/src/njs_promise.c b/src/njs_promise.c index 78043af4..a0ca8516 100644 --- a/src/njs_promise.c +++ b/src/njs_promise.c @@ -117,8 +117,8 @@ njs_promise_alloc(njs_vm_t *vm) goto memory_error; } - njs_lvlhsh_init(&promise->object.hash); - njs_lvlhsh_init(&promise->object.shared_hash); + njs_flathsh_init(&promise->object.hash); + njs_flathsh_init(&promise->object.shared_hash); promise->object.type = NJS_PROMISE; promise->object.shared = 0; promise->object.extensible = 1; diff --git a/src/njs_regexp.c b/src/njs_regexp.c index d958e2af..7d09d5c8 100644 --- a/src/njs_regexp.c +++ b/src/njs_regexp.c @@ -501,7 +501,7 @@ njs_regexp_alloc(njs_vm_t *vm, njs_regexp_pattern_t *pattern) regexp = njs_mp_alloc(vm->mem_pool, sizeof(njs_regexp_t)); if (njs_fast_path(regexp != NULL)) { - njs_lvlhsh_init(®exp->object.hash); + njs_flathsh_init(®exp->object.hash); regexp->object.shared_hash = vm->shared->regexp_instance_hash; regexp->object.__proto__ = njs_vm_proto(vm, NJS_OBJ_TYPE_REGEXP); regexp->object.slots = NULL; @@ -1007,7 +1007,7 @@ njs_regexp_exec_result(njs_vm_t *vm, njs_value_t *r, njs_utf8_t utf8, njs_regexp_t *regexp; njs_object_prop_t *prop; njs_regexp_group_t *group; - njs_flathsh_query_t lhq; + njs_flathsh_query_t fhq; njs_regexp_pattern_t *pattern; regexp = njs_regexp(r); @@ -1039,17 +1039,17 @@ njs_regexp_exec_result(njs_vm_t *vm, njs_value_t *r, njs_utf8_t utf8, /* FIXME: implement fast CreateDataPropertyOrThrow(). */ - lhq.key_hash = NJS_ATOM_STRING_index; - lhq.replace = 0; - lhq.pool = vm->mem_pool; - lhq.proto = &njs_object_hash_proto; + fhq.key_hash = NJS_ATOM_STRING_index; + fhq.replace = 0; + fhq.pool = vm->mem_pool; + fhq.proto = &njs_object_hash_proto; - ret = njs_flathsh_unique_insert(&array->object.hash, &lhq); + ret = njs_flathsh_unique_insert(&array->object.hash, &fhq); if (njs_slow_path(ret != NJS_OK)) { goto insert_fail; } - prop = lhq.value; + prop = fhq.value; prop->type = NJS_PROPERTY; prop->enumerable = 1; @@ -1067,14 +1067,14 @@ njs_regexp_exec_result(njs_vm_t *vm, njs_value_t *r, njs_utf8_t utf8, njs_set_number(&prop->u.value, index); - lhq.key_hash = NJS_ATOM_STRING_input; + fhq.key_hash = NJS_ATOM_STRING_input; - ret = njs_flathsh_unique_insert(&array->object.hash, &lhq); + ret = njs_flathsh_unique_insert(&array->object.hash, &fhq); if (njs_slow_path(ret != NJS_OK)) { goto insert_fail; } - prop = lhq.value; + prop = fhq.value; prop->type = NJS_PROPERTY; prop->enumerable = 1; @@ -1082,14 +1082,14 @@ njs_regexp_exec_result(njs_vm_t *vm, njs_value_t *r, njs_utf8_t utf8, prop->writable = 1; prop->u.value = regexp->string; - lhq.key_hash = NJS_ATOM_STRING_groups; + fhq.key_hash = NJS_ATOM_STRING_groups; - ret = njs_flathsh_unique_insert(&array->object.hash, &lhq); + ret = njs_flathsh_unique_insert(&array->object.hash, &fhq); if (njs_slow_path(ret != NJS_OK)) { goto insert_fail; } - prop = lhq.value; + prop = fhq.value; prop->type = NJS_PROPERTY; prop->enumerable = 1; @@ -1116,14 +1116,14 @@ njs_regexp_exec_result(njs_vm_t *vm, njs_value_t *r, njs_utf8_t utf8, goto fail; } - lhq.key_hash = name.atom_id; + fhq.key_hash = name.atom_id; - ret = njs_flathsh_unique_insert(&groups->hash, &lhq); + ret = njs_flathsh_unique_insert(&groups->hash, &fhq); if (njs_slow_path(ret != NJS_OK)) { goto insert_fail; } - prop = lhq.value; + prop = fhq.value; prop->type = NJS_PROPERTY; prop->enumerable = 1; @@ -1141,7 +1141,7 @@ njs_regexp_exec_result(njs_vm_t *vm, njs_value_t *r, njs_utf8_t utf8, insert_fail: - njs_internal_error(vm, "lvlhsh insert failed"); + njs_internal_error(vm, "flathsh insert failed"); fail: @@ -1157,14 +1157,14 @@ static void njs_regexp_exec_result_free(njs_vm_t *vm, njs_array_t *result) { njs_flathsh_t *hash; - njs_flathsh_query_t lhq; + njs_flathsh_query_t fhq; hash = &result->object.hash; - lhq.pool = vm->mem_pool; - lhq.proto = &njs_object_hash_proto; + fhq.pool = vm->mem_pool; + fhq.proto = &njs_object_hash_proto; - njs_flathsh_destroy(hash, &lhq); + njs_flathsh_destroy(hash, &fhq); njs_array_destroy(vm, result); } diff --git a/src/njs_scope.c b/src/njs_scope.c index 7959849a..cd1176a2 100644 --- a/src/njs_scope.c +++ b/src/njs_scope.c @@ -103,7 +103,7 @@ njs_scope_value_get(njs_vm_t *vm, njs_index_t index) static njs_int_t -njs_scope_values_hash_test(njs_lvlhsh_query_t *lhq, void *data) +njs_scope_values_hash_test(njs_flathsh_query_t *fhq, void *data) { njs_str_t string; njs_value_t *value; @@ -119,8 +119,8 @@ njs_scope_values_hash_test(njs_lvlhsh_query_t *lhq, void *data) string.length = sizeof(njs_value_t); } - if (lhq->key.length == string.length - && memcmp(lhq->key.start, string.start, string.length) == 0) + if (fhq->key.length == string.length + && memcmp(fhq->key.start, string.start, string.length) == 0) { return NJS_OK; } @@ -129,13 +129,12 @@ njs_scope_values_hash_test(njs_lvlhsh_query_t *lhq, void *data) } -static const njs_lvlhsh_proto_t njs_values_hash_proto +static const njs_flathsh_proto_t njs_values_hash_proto njs_aligned(64) = { - NJS_LVLHSH_DEFAULT, njs_scope_values_hash_test, - njs_lvlhsh_alloc, - njs_lvlhsh_free, + njs_flathsh_proto_alloc, + njs_flathsh_proto_free, }; @@ -148,16 +147,16 @@ static njs_value_t * njs_scope_value_index(njs_vm_t *vm, const njs_value_t *src, njs_uint_t runtime, njs_index_t **index) { - u_char *start; - uint32_t value_size, size, length; - njs_int_t ret; - njs_str_t str; - njs_bool_t is_string; - njs_value_t *value; - njs_string_t *string; - njs_lvlhsh_t *values_hash; - njs_object_prop_t *pr; - njs_lvlhsh_query_t lhq; + u_char *start; + uint32_t value_size, size, length; + njs_int_t ret; + njs_str_t str; + njs_bool_t is_string; + njs_value_t *value; + njs_string_t *string; + njs_flathsh_t *values_hash; + njs_object_prop_t *pr; + njs_flathsh_query_t fhq; is_string = 0; value_size = sizeof(njs_value_t); @@ -176,18 +175,18 @@ njs_scope_value_index(njs_vm_t *vm, const njs_value_t *src, njs_uint_t runtime, start = (u_char *) src; } - lhq.key_hash = njs_djb_hash(start, size); - lhq.key.length = size; - lhq.key.start = start; - lhq.proto = &njs_values_hash_proto; + fhq.key_hash = njs_djb_hash(start, size); + fhq.key.length = size; + fhq.key.start = start; + fhq.proto = &njs_values_hash_proto; - if (njs_lvlhsh_find(&vm->shared->values_hash, &lhq) == NJS_OK) { - value = ((njs_object_prop_t *) lhq.value)->u.val; + if (njs_flathsh_find(&vm->shared->values_hash, &fhq) == NJS_OK) { + value = ((njs_object_prop_t *) fhq.value)->u.val; *index = (njs_index_t *) ((u_char *) value + sizeof(njs_value_t)); - } else if (runtime && njs_lvlhsh_find(&vm->values_hash, &lhq) == NJS_OK) { - value = ((njs_object_prop_t *) lhq.value)->u.val; + } else if (runtime && njs_flathsh_find(&vm->values_hash, &fhq) == NJS_OK) { + value = ((njs_object_prop_t *) fhq.value)->u.val; *index = (njs_index_t *) ((u_char *) value + sizeof(njs_value_t)); @@ -228,17 +227,17 @@ njs_scope_value_index(njs_vm_t *vm, const njs_value_t *src, njs_uint_t runtime, *index = (njs_index_t *) ((u_char *) value + sizeof(njs_value_t)); **index = NJS_INDEX_ERROR; - lhq.replace = 0; - lhq.pool = vm->mem_pool; + fhq.replace = 0; + fhq.pool = vm->mem_pool; values_hash = runtime ? &vm->values_hash : &vm->shared->values_hash; - ret = njs_lvlhsh_insert(values_hash, &lhq); + ret = njs_flathsh_insert(values_hash, &fhq); if (njs_slow_path(ret != NJS_OK)) { return NULL; } - pr = lhq.value; + pr = fhq.value; pr->u.val = value; } diff --git a/src/njs_typed_array.c b/src/njs_typed_array.c index d7ca2e83..39440172 100644 --- a/src/njs_typed_array.c +++ b/src/njs_typed_array.c @@ -178,8 +178,8 @@ njs_typed_array_alloc(njs_vm_t *vm, njs_value_t *args, njs_uint_t nargs, } } - njs_lvlhsh_init(&array->object.hash); - njs_lvlhsh_init(&array->object.shared_hash); + njs_flathsh_init(&array->object.hash); + njs_flathsh_init(&array->object.shared_hash); array->object.__proto__ = njs_vm_proto(vm, type); array->object.type = NJS_TYPED_ARRAY; array->object.extensible = 1; @@ -2400,8 +2400,8 @@ njs_data_view_constructor(njs_vm_t *vm, njs_value_t *args, njs_uint_t nargs, view->byte_length = size; view->type = NJS_OBJ_TYPE_DATA_VIEW; - njs_lvlhsh_init(&view->object.hash); - njs_lvlhsh_init(&view->object.shared_hash); + njs_flathsh_init(&view->object.hash); + njs_flathsh_init(&view->object.shared_hash); view->object.__proto__ = njs_vm_proto(vm, view->type); view->object.type = NJS_DATA_VIEW; view->object.extensible = 1; diff --git a/src/njs_value.c b/src/njs_value.c index 78f03821..7959c4ed 100644 --- a/src/njs_value.c +++ b/src/njs_value.c @@ -43,7 +43,7 @@ njs_value_to_primitive(njs_vm_t *vm, njs_value_t *dst, njs_value_t *value, njs_int_t ret; njs_uint_t tries; njs_value_t method, retval; - njs_flathsh_query_t lhq; + njs_flathsh_query_t fhq; static const uint32_t atoms[] = { NJS_ATOM_STRING_valueOf, @@ -56,7 +56,7 @@ njs_value_to_primitive(njs_vm_t *vm, njs_value_t *dst, njs_value_t *value, } tries = 0; - lhq.proto = &njs_object_hash_proto; + fhq.proto = &njs_object_hash_proto; for ( ;; ) { ret = NJS_ERROR; @@ -64,9 +64,9 @@ njs_value_to_primitive(njs_vm_t *vm, njs_value_t *dst, njs_value_t *value, if (njs_is_object(value) && tries < 2) { hint ^= tries++; - lhq.key_hash = atoms[hint]; + fhq.key_hash = atoms[hint]; - ret = njs_object_property(vm, njs_object(value), &lhq, &method); + ret = njs_object_property(vm, njs_object(value), &fhq, &method); if (njs_slow_path(ret == NJS_ERROR)) { return ret; @@ -542,7 +542,7 @@ njs_value_is_data_view(const njs_value_t *value) * ES5.1, 8.12.1: [[GetOwnProperty]], [[GetProperty]]. * The njs_property_query() returns values * NJS_OK property has been found in object, - * retval of type njs_object_prop_t * is in pq->lhq.value. + * retval of type njs_object_prop_t * is in pq->fhq.value. * in NJS_PROPERTY_QUERY_GET * prop->type is NJS_PROPERTY or NJS_PROPERTY_HANDLER. * in NJS_PROPERTY_QUERY_SET, NJS_PROPERTY_QUERY_DELETE @@ -550,7 +550,7 @@ njs_value_is_data_view(const njs_value_t *value) * NJS_PROPERTY_TYPED_ARRAY_REF or * NJS_PROPERTY_HANDLER. * NJS_DECLINED property was not found in object, - * if pq->lhq.value != NULL it contains retval of type + * if pq->fhq.value != NULL it contains retval of type * njs_object_prop_t * where prop->type is NJS_WHITEOUT * NJS_ERROR exception has been thrown. */ @@ -598,8 +598,8 @@ njs_property_query(njs_vm_t *vm, njs_property_query_t *pq, njs_value_t *value, case NJS_UNDEFINED: case NJS_NULL: default: - njs_atom_string_get(vm, atom_id, &pq->lhq.key); - njs_type_error(vm, "cannot get property \"%V\" of %s", &pq->lhq.key, + njs_atom_string_get(vm, atom_id, &pq->fhq.key); + njs_type_error(vm, "cannot get property \"%V\" of %s", &pq->fhq.key, njs_type_string(value->type)); return NJS_ERROR; } @@ -628,7 +628,7 @@ njs_object_property_query(njs_vm_t *vm, njs_property_query_t *pq, njs_typed_array_t *tarray; njs_object_value_t *ov; - pq->lhq.proto = &njs_object_hash_proto; + pq->fhq.proto = &njs_object_hash_proto; own = pq->own; pq->own = 1; @@ -705,12 +705,12 @@ njs_object_property_query(njs_vm_t *vm, njs_property_query_t *pq, break; } - pq->lhq.key_hash = atom_id; + pq->fhq.key_hash = atom_id; - ret = njs_flathsh_unique_find(&proto->hash, &pq->lhq); + ret = njs_flathsh_unique_find(&proto->hash, &pq->fhq); if (ret == NJS_OK) { - prop = pq->lhq.value; + prop = pq->fhq.value; if (prop->type != NJS_WHITEOUT) { return ret; @@ -721,7 +721,7 @@ njs_object_property_query(njs_vm_t *vm, njs_property_query_t *pq, } } else { - ret = njs_flathsh_unique_find(&proto->shared_hash, &pq->lhq); + ret = njs_flathsh_unique_find(&proto->shared_hash, &pq->fhq); if (ret == NJS_OK) { return njs_prop_private_copy(vm, pq, proto); } @@ -803,11 +803,11 @@ njs_array_property_query(njs_vm_t *vm, njs_property_query_t *pq, } } - pq->lhq.key_hash = atom_id; + pq->fhq.key_hash = atom_id; - ret = njs_flathsh_unique_find(&array->object.hash, &pq->lhq); + ret = njs_flathsh_unique_find(&array->object.hash, &pq->fhq); if (ret == NJS_OK) { - prop = pq->lhq.value; + prop = pq->fhq.value; if (prop->type != NJS_WHITEOUT) { return NJS_OK; @@ -852,7 +852,7 @@ prop: prop->enumerable = 1; prop->configurable = 1; - pq->lhq.value = prop; + pq->fhq.value = prop; return NJS_OK; } @@ -890,7 +890,7 @@ njs_typed_array_property_query(njs_vm_t *vm, njs_property_query_t *pq, prop->enumerable = 1; prop->configurable = 0; - pq->lhq.value = prop; + pq->fhq.value = prop; return NJS_OK; } @@ -922,7 +922,7 @@ njs_string_property_query(njs_vm_t *vm, njs_property_query_t *pq, prop->enumerable = 1; prop->configurable = 0; - pq->lhq.value = prop; + pq->fhq.value = prop; return NJS_OK; } @@ -958,7 +958,7 @@ njs_external_property_query(njs_vm_t *vm, njs_property_query_t *pq, njs_prop_magic32(prop) = slots->magic32; - pq->lhq.value = prop; + pq->fhq.value = prop; prop->type = NJS_PROPERTY; prop->writable = slots->writable; @@ -968,7 +968,7 @@ njs_external_property_query(njs_vm_t *vm, njs_property_query_t *pq, switch (pq->query) { case NJS_PROPERTY_QUERY_GET: - return slots->prop_handler(vm, prop, pq->lhq.key_hash, value, NULL, + return slots->prop_handler(vm, prop, pq->fhq.key_hash, value, NULL, njs_prop_value(prop)); case NJS_PROPERTY_QUERY_SET: @@ -1053,7 +1053,7 @@ slow_path: switch (ret) { case NJS_OK: - prop = pq.lhq.value; + prop = pq.fhq.value; switch (prop->type) { case NJS_PROPERTY: @@ -1176,14 +1176,14 @@ slow_path: switch (ret) { case NJS_OK: - prop = pq.lhq.value; + prop = pq.fhq.value; if (njs_is_data_descriptor(prop)) { if (!prop->writable) { - njs_atom_string_get(vm, atom_id, &pq.lhq.key); + njs_atom_string_get(vm, atom_id, &pq.fhq.key); njs_type_error(vm, "Cannot assign to read-only property \"%V\" of %s", - &pq.lhq.key, njs_type_string(value->type)); + &pq.fhq.key, njs_type_string(value->type)); return NJS_ERROR; } @@ -1193,10 +1193,10 @@ slow_path: value, setval, 1, &retval); } - njs_atom_string_get(vm, atom_id, &pq.lhq.key); + njs_atom_string_get(vm, atom_id, &pq.fhq.key); njs_type_error(vm, "Cannot set property \"%V\" of %s which has only a getter", - &pq.lhq.key, njs_type_string(value->type)); + &pq.fhq.key, njs_type_string(value->type)); return NJS_ERROR; } @@ -1257,9 +1257,9 @@ slow_path: goto fail; } - pq.lhq.pool = vm->mem_pool; + pq.fhq.pool = vm->mem_pool; - int rc = njs_flathsh_unique_delete(pq.own_whiteout, &pq.lhq); + int rc = njs_flathsh_unique_delete(pq.own_whiteout, &pq.fhq); if (rc != NJS_OK) { return NJS_ERROR; } @@ -1267,7 +1267,7 @@ slow_path: h = pq.own_whiteout->slot; if (h == NULL) { - h = njs_flathsh_new(&pq.lhq); + h = njs_flathsh_new(&pq.fhq); if (njs_slow_path(h == NULL)) { return NJS_ERROR; } @@ -1275,7 +1275,7 @@ slow_path: pq.own_whiteout->slot = h; } - elt = njs_flathsh_add_elt(pq.own_whiteout, &pq.lhq); + elt = njs_flathsh_add_elt(pq.own_whiteout, &pq.fhq); if (njs_slow_path(elt == NULL)) { return NJS_ERROR; } @@ -1317,17 +1317,17 @@ slow_path: } - pq.lhq.replace = 0; - pq.lhq.key_hash = atom_id; - pq.lhq.pool = vm->mem_pool; + pq.fhq.replace = 0; + pq.fhq.key_hash = atom_id; + pq.fhq.pool = vm->mem_pool; - ret = njs_flathsh_unique_insert(njs_object_hash(value), &pq.lhq); + ret = njs_flathsh_unique_insert(njs_object_hash(value), &pq.fhq); if (njs_slow_path(ret != NJS_OK)) { - njs_internal_error(vm, "lvlhsh insert failed"); + njs_internal_error(vm, "flathsh insert failed"); return NJS_ERROR; } - prop = pq.lhq.value; + prop = pq.fhq.value; prop->type = NJS_PROPERTY; prop->enumerable = 1; prop->configurable = 1; @@ -1341,9 +1341,9 @@ found: fail: - njs_atom_string_get(vm, atom_id, &pq.lhq.key); + njs_atom_string_get(vm, atom_id, &pq.fhq.key); njs_type_error(vm, "Cannot add property \"%V\", object is not extensible", - &pq.lhq.key); + &pq.fhq.key); return NJS_ERROR; } @@ -1386,13 +1386,13 @@ slow_path: return ret; } - prop = pq.lhq.value; + prop = pq.fhq.value; if (njs_slow_path(!prop->configurable)) { if (thrw) { - njs_atom_string_get(vm, atom_id, &pq.lhq.key); + njs_atom_string_get(vm, atom_id, &pq.fhq.key); njs_type_error(vm, "Cannot delete property \"%V\" of %s", - &pq.lhq.key, njs_type_string(value->type)); + &pq.fhq.key, njs_type_string(value->type)); return NJS_ERROR; } diff --git a/src/njs_value.h b/src/njs_value.h index 3fba344b..2ffa04e7 100644 --- a/src/njs_value.h +++ b/src/njs_value.h @@ -350,14 +350,14 @@ struct njs_object_prop_init_s { typedef struct { - njs_flathsh_query_t lhq; + njs_flathsh_query_t fhq; uint8_t query; /* scratch is used to get the value of an NJS_PROPERTY_HANDLER property. */ njs_object_prop_t scratch; - njs_flathsh_t *own_whiteout; + njs_flathsh_t *own_whiteout; uint8_t temp; uint8_t own; @@ -987,7 +987,7 @@ njs_property_query_init(njs_property_query_t *pq, njs_prop_query_t query, pq->own = own; if (query == NJS_PROPERTY_QUERY_SET) { - pq->lhq.value = NULL; + pq->fhq.value = NULL; pq->own_whiteout = NULL; pq->temp = 0; } diff --git a/src/njs_vm.c b/src/njs_vm.c index e6aac927..19c50e48 100644 --- a/src/njs_vm.c +++ b/src/njs_vm.c @@ -54,7 +54,7 @@ njs_vm_create(njs_vm_opt_t *options) return NULL; } - njs_lvlhsh_init(&vm->values_hash); + njs_flathsh_init(&vm->values_hash); vm->options = *options; @@ -414,7 +414,7 @@ njs_vm_clone(njs_vm_t *vm, njs_external_ptr_t external) nvm->shared_atom_count = vm->atom_id_generator; - njs_lvlhsh_init(&nvm->atom_hash); + njs_flathsh_init(&nvm->atom_hash); nvm->atom_hash_current = &nvm->atom_hash; ret = njs_vm_runtime_init(nvm); @@ -492,9 +492,9 @@ njs_vm_runtime_init(njs_vm_t *vm) return NJS_ERROR; } - njs_lvlhsh_init(&vm->values_hash); + njs_flathsh_init(&vm->values_hash); - njs_lvlhsh_init(&vm->modules_hash); + njs_flathsh_init(&vm->modules_hash); njs_rbtree_init(&vm->global_symbols, njs_symbol_rbtree_cmp); @@ -904,7 +904,7 @@ njs_vm_bind2(njs_vm_t *vm, const njs_str_t *var_name, njs_object_prop_t *prop, njs_object_t *global; njs_flathsh_t *hash; njs_object_prop_t *obj_prop; - njs_flathsh_query_t lhq; + njs_flathsh_query_t fhq; ret = njs_atom_string_create(vm, &prop_name, var_name->start, var_name->length); @@ -912,21 +912,21 @@ njs_vm_bind2(njs_vm_t *vm, const njs_str_t *var_name, njs_object_prop_t *prop, return NJS_ERROR; } - lhq.key_hash = prop_name.atom_id; - lhq.replace = 1; - lhq.pool = vm->mem_pool; - lhq.proto = &njs_object_hash_proto; + fhq.key_hash = prop_name.atom_id; + fhq.replace = 1; + fhq.pool = vm->mem_pool; + fhq.proto = &njs_object_hash_proto; global = &vm->global_object; hash = shared ? &global->shared_hash : &global->hash; - ret = njs_flathsh_unique_insert(hash, &lhq); + ret = njs_flathsh_unique_insert(hash, &fhq); if (njs_slow_path(ret != NJS_OK)) { - njs_internal_error(vm, "lvlhsh insert failed"); + njs_internal_error(vm, "flathsh insert failed"); return ret; } - obj_prop = lhq.value; + obj_prop = fhq.value; obj_prop->type = prop->type; obj_prop->enumerable = prop->enumerable; @@ -1218,7 +1218,7 @@ njs_vm_object_alloc(njs_vm_t *vm, njs_value_t *retval, ...) njs_value_t *name, *value; njs_object_t *object; njs_object_prop_t *prop; - njs_flathsh_query_t lhq; + njs_flathsh_query_t fhq; object = njs_object_alloc(vm); if (njs_slow_path(object == NULL)) { @@ -1253,18 +1253,18 @@ njs_vm_object_alloc(njs_vm_t *vm, njs_value_t *retval, ...) } } - lhq.key_hash = name->atom_id; - lhq.replace = 0; - lhq.pool = vm->mem_pool; - lhq.proto = &njs_object_hash_proto; + fhq.key_hash = name->atom_id; + fhq.replace = 0; + fhq.pool = vm->mem_pool; + fhq.proto = &njs_object_hash_proto; - ret = njs_flathsh_unique_insert(&object->hash, &lhq); + ret = njs_flathsh_unique_insert(&object->hash, &fhq); if (njs_slow_path(ret != NJS_OK)) { njs_internal_error(vm, NULL); goto done; } - prop = lhq.value; + prop = fhq.value; prop->type = NJS_PROPERTY; prop->enumerable = 1; @@ -1637,14 +1637,14 @@ njs_vm_string_compare(njs_vm_t *vm, const njs_value_t *v1, void * -njs_lvlhsh_alloc(void *data, size_t size) +njs_flathsh_proto_alloc(void *data, size_t size) { return njs_mp_align(data, NJS_MAX_ALIGNMENT, size); } void -njs_lvlhsh_free(void *data, void *p, size_t size) +njs_flathsh_proto_free(void *data, void *p, size_t size) { njs_mp_free(data, p); } diff --git a/src/njs_vm.h b/src/njs_vm.h index 3e21fdf2..3351dee4 100644 --- a/src/njs_vm.h +++ b/src/njs_vm.h @@ -128,16 +128,16 @@ struct njs_vm_s { njs_native_frame_t *top_frame; njs_frame_t *active_frame; - njs_lvlhsh_t atom_hash_shared; - njs_lvlhsh_t atom_hash; - njs_lvlhsh_t *atom_hash_current; + njs_flathsh_t atom_hash_shared; + njs_flathsh_t atom_hash; + njs_flathsh_t *atom_hash_current; uint32_t shared_atom_count; uint32_t atom_id_generator; - njs_lvlhsh_t values_hash; + njs_flathsh_t values_hash; njs_arr_t *modules; - njs_lvlhsh_t modules_hash; + njs_flathsh_t modules_hash; uint32_t event_id; njs_queue_t jobs; @@ -207,7 +207,7 @@ typedef struct { struct njs_vm_shared_s { - njs_lvlhsh_t values_hash; + njs_flathsh_t values_hash; njs_flathsh_t array_instance_hash; njs_flathsh_t string_instance_hash; @@ -218,7 +218,7 @@ struct njs_vm_shared_s { njs_flathsh_t regexp_instance_hash; size_t module_items; - njs_lvlhsh_t modules_hash; + njs_flathsh_t modules_hash; njs_flathsh_t env_hash; @@ -253,8 +253,8 @@ njs_int_t njs_builtin_match_native_function(njs_vm_t *vm, void njs_disassemble(u_char *start, u_char *end, njs_int_t count, njs_arr_t *lines); -void *njs_lvlhsh_alloc(void *data, size_t size); -void njs_lvlhsh_free(void *data, void *p, size_t size); +void *njs_flathsh_proto_alloc(void *data, size_t size); +void njs_flathsh_proto_free(void *data, void *p, size_t size); extern const njs_str_t njs_entry_empty; diff --git a/src/njs_vmcode.c b/src/njs_vmcode.c index 727dc6d0..70da4630 100644 --- a/src/njs_vmcode.c +++ b/src/njs_vmcode.c @@ -2064,7 +2064,7 @@ njs_vmcode_property_init(njs_vm_t *vm, njs_value_t *value, njs_value_t *key, njs_array_t *array; njs_value_t *val, name; njs_object_prop_t *prop; - njs_flathsh_query_t lhq; + njs_flathsh_query_t fhq; switch (value->type) { case NJS_ARRAY: @@ -2123,18 +2123,18 @@ njs_vmcode_property_init(njs_vm_t *vm, njs_value_t *value, njs_value_t *key, } } - lhq.key_hash = name.atom_id; - lhq.replace = 1; - lhq.pool = vm->mem_pool; - lhq.proto = &njs_object_hash_proto; + fhq.key_hash = name.atom_id; + fhq.replace = 1; + fhq.pool = vm->mem_pool; + fhq.proto = &njs_object_hash_proto; - ret = njs_flathsh_unique_insert(njs_object_hash(value), &lhq); + ret = njs_flathsh_unique_insert(njs_object_hash(value), &fhq); if (njs_slow_path(ret != NJS_OK)) { - njs_internal_error(vm, "lvlhsh insert/replace failed"); + njs_internal_error(vm, "flathsh insert/replace failed"); return NJS_ERROR; } - prop = lhq.value; + prop = fhq.value; prop->type = NJS_PROPERTY; prop->enumerable = 1; @@ -2164,26 +2164,26 @@ njs_vmcode_proto_init(njs_vm_t *vm, njs_value_t *value, njs_value_t *unused, njs_value_t retval; njs_jump_off_t ret; njs_object_prop_t *prop; - njs_flathsh_query_t lhq; + njs_flathsh_query_t fhq; - lhq.key_hash = NJS_ATOM_STRING___proto__; - lhq.proto = &njs_object_hash_proto; - lhq.pool = vm->mem_pool; + fhq.key_hash = NJS_ATOM_STRING___proto__; + fhq.proto = &njs_object_hash_proto; + fhq.pool = vm->mem_pool; obj = njs_object(value); - ret = njs_flathsh_unique_find(&obj->__proto__->shared_hash, &lhq); + ret = njs_flathsh_unique_find(&obj->__proto__->shared_hash, &fhq); if (njs_slow_path(ret != NJS_OK)) { goto fail; } - prop = lhq.value; + prop = fhq.value; if (prop->type != NJS_PROPERTY_HANDLER) { goto fail; } - ret = njs_prop_handler(prop)(vm, prop, lhq.key_hash, value, init, &retval); + ret = njs_prop_handler(prop)(vm, prop, fhq.key_hash, value, init, &retval); if (njs_slow_path(ret != NJS_OK)) { goto fail; } diff --git a/src/test/flathsh_unit_test.c b/src/test/flathsh_unit_test.c new file mode 100644 index 00000000..b2a76f30 --- /dev/null +++ b/src/test/flathsh_unit_test.c @@ -0,0 +1,205 @@ + +/* + * Copyright (C) Igor Sysoev + * Copyright (C) NGINX, Inc. + */ + + +#include <njs_main.h> + + +static njs_int_t +flathsh_unit_test_key_test(njs_flathsh_query_t *fhq, void *data) +{ + if (*(uintptr_t *) fhq->key.start == *(uintptr_t *) data) { + return NJS_OK; + } + + return NJS_DECLINED; +} + + +static void * +flathsh_unit_test_pool_alloc(void *pool, size_t size) +{ + return njs_mp_align(pool, NJS_MAX_ALIGNMENT, size); +} + + +static void +flathsh_unit_test_pool_free(void *pool, void *p, size_t size) +{ + njs_mp_free(pool, p); +} + + +static const njs_flathsh_proto_t flathsh_proto njs_aligned(64) = { + flathsh_unit_test_key_test, + flathsh_unit_test_pool_alloc, + flathsh_unit_test_pool_free, +}; + + +static njs_int_t +flathsh_unit_test_add(njs_flathsh_t *lh, const njs_flathsh_proto_t *proto, + void *pool, uintptr_t key) +{ + njs_flathsh_query_t fhq; + + fhq.key_hash = key; + fhq.replace = 0; + fhq.key.length = sizeof(uintptr_t); + fhq.key.start = (u_char *) &key; + fhq.proto = proto; + fhq.pool = pool; + + switch (njs_flathsh_insert(lh, &fhq)) { + + case NJS_OK: + ((njs_flathsh_elt_t *) fhq.value)->value[0] = (void *) key; + return NJS_OK; + + case NJS_DECLINED: + njs_printf("flathsh unit test failed: key %08Xl is already in hash\n", + (long) key); + /* Fall through. */ + + default: + return NJS_ERROR; + } +} + + +static njs_int_t +flathsh_unit_test_get(njs_flathsh_t *lh, const njs_flathsh_proto_t *proto, + uintptr_t key) +{ + njs_flathsh_query_t fhq; + + fhq.key_hash = key; + fhq.key.length = sizeof(uintptr_t); + fhq.key.start = (u_char *) &key; + fhq.proto = proto; + + if (njs_flathsh_find(lh, &fhq) == NJS_OK) { + + if (key == (uintptr_t) ((njs_flathsh_elt_t *) fhq.value)->value[0]) { + return NJS_OK; + } + } + + njs_printf("flathsh unit test failed: key %08Xl not found in hash\n", + (long) key); + + return NJS_ERROR; +} + + +static njs_int_t +flathsh_unit_test_delete(njs_flathsh_t *lh, const njs_flathsh_proto_t *proto, + void *pool, uintptr_t key) +{ + njs_int_t ret; + njs_flathsh_query_t fhq; + + fhq.key_hash = key; + fhq.key.length = sizeof(uintptr_t); + fhq.key.start = (u_char *) &key; + fhq.proto = proto; + fhq.pool = pool; + + ret = njs_flathsh_delete(lh, &fhq); + + if (ret != NJS_OK) { + njs_printf("flathsh unit test failed: key %08lX not found in hash\n", + (long) key); + } + + return ret; +} + + +static njs_int_t +flathsh_unit_test(njs_uint_t n) +{ + njs_mp_t *pool; + uint32_t key; + njs_uint_t i; + njs_flathsh_t lh; + njs_flathsh_each_t lhe; + + const size_t min_chunk_size = 32; + const size_t page_size = 1024; + const size_t page_alignment = 128; + const size_t cluster_size = 4096; + + pool = njs_mp_create(cluster_size, page_alignment, page_size, + min_chunk_size); + if (pool == NULL) { + return NJS_ERROR; + } + + njs_printf("flathsh unit test started: %l items\n", (long) n); + + njs_memzero(&lh, sizeof(njs_flathsh_t)); + + key = 0; + for (i = 0; i < n; i++) { + key = njs_murmur_hash2(&key, sizeof(uint32_t)); + + if (flathsh_unit_test_add(&lh, &flathsh_proto, pool, key) != NJS_OK) { + njs_printf("flathsh add unit test failed at %l\n", (long) i); + return NJS_ERROR; + } + } + + key = 0; + for (i = 0; i < n; i++) { + key = njs_murmur_hash2(&key, sizeof(uint32_t)); + + if (flathsh_unit_test_get(&lh, &flathsh_proto, key) != NJS_OK) { + return NJS_ERROR; + } + } + + njs_flathsh_each_init(&lhe, &flathsh_proto); + + for (i = 0; i < n + 1; i++) { + if (njs_flathsh_each(&lh, &lhe) == NULL) { + break; + } + } + + if (i != n) { + njs_printf("flathsh each unit test failed at %l of %l\n", + (long) i, (long) n); + return NJS_ERROR; + } + + key = 0; + for (i = 0; i < n; i++) { + key = njs_murmur_hash2(&key, sizeof(uint32_t)); + + if (flathsh_unit_test_delete(&lh, &flathsh_proto, pool, key) != NJS_OK) { + return NJS_ERROR; + } + } + + if (!njs_mp_is_empty(pool)) { + njs_printf("mem cache pool is not empty\n"); + return NJS_ERROR; + } + + njs_mp_destroy(pool); + + njs_printf("flathsh unit test passed\n"); + + return NJS_OK; +} + + +int +main(void) +{ + return flathsh_unit_test(1000 * 1000); +} diff --git a/src/test/lvlhsh_unit_test.c b/src/test/lvlhsh_unit_test.c deleted file mode 100644 index 0e334c5d..00000000 --- a/src/test/lvlhsh_unit_test.c +++ /dev/null @@ -1,206 +0,0 @@ - -/* - * Copyright (C) Igor Sysoev - * Copyright (C) NGINX, Inc. - */ - - -#include <njs_main.h> - - -static njs_int_t -lvlhsh_unit_test_key_test(njs_lvlhsh_query_t *lhq, void *data) -{ - if (*(uintptr_t *) lhq->key.start == *(uintptr_t *) data) { - return NJS_OK; - } - - return NJS_DECLINED; -} - - -static void * -lvlhsh_unit_test_pool_alloc(void *pool, size_t size) -{ - return njs_mp_align(pool, NJS_MAX_ALIGNMENT, size); -} - - -static void -lvlhsh_unit_test_pool_free(void *pool, void *p, size_t size) -{ - njs_mp_free(pool, p); -} - - -static const njs_lvlhsh_proto_t lvlhsh_proto njs_aligned(64) = { - NJS_LVLHSH_LARGE_SLAB, - lvlhsh_unit_test_key_test, - lvlhsh_unit_test_pool_alloc, - lvlhsh_unit_test_pool_free, -}; - - -static njs_int_t -lvlhsh_unit_test_add(njs_lvlhsh_t *lh, const njs_lvlhsh_proto_t *proto, - void *pool, uintptr_t key) -{ - njs_lvlhsh_query_t lhq; - - lhq.key_hash = key; - lhq.replace = 0; - lhq.key.length = sizeof(uintptr_t); - lhq.key.start = (u_char *) &key; - lhq.proto = proto; - lhq.pool = pool; - - switch (njs_lvlhsh_insert(lh, &lhq)) { - - case NJS_OK: - ((njs_flathsh_elt_t *) lhq.value)->value[0] = (void *) key; - return NJS_OK; - - case NJS_DECLINED: - njs_printf("lvlhsh unit test failed: key %08Xl is already in hash\n", - (long) key); - /* Fall through. */ - - default: - return NJS_ERROR; - } -} - - -static njs_int_t -lvlhsh_unit_test_get(njs_lvlhsh_t *lh, const njs_lvlhsh_proto_t *proto, - uintptr_t key) -{ - njs_lvlhsh_query_t lhq; - - lhq.key_hash = key; - lhq.key.length = sizeof(uintptr_t); - lhq.key.start = (u_char *) &key; - lhq.proto = proto; - - if (njs_lvlhsh_find(lh, &lhq) == NJS_OK) { - - if (key == (uintptr_t) ((njs_flathsh_elt_t *) lhq.value)->value[0]) { - return NJS_OK; - } - } - - njs_printf("lvlhsh unit test failed: key %08Xl not found in hash\n", - (long) key); - - return NJS_ERROR; -} - - -static njs_int_t -lvlhsh_unit_test_delete(njs_lvlhsh_t *lh, const njs_lvlhsh_proto_t *proto, - void *pool, uintptr_t key) -{ - njs_int_t ret; - njs_lvlhsh_query_t lhq; - - lhq.key_hash = key; - lhq.key.length = sizeof(uintptr_t); - lhq.key.start = (u_char *) &key; - lhq.proto = proto; - lhq.pool = pool; - - ret = njs_lvlhsh_delete(lh, &lhq); - - if (ret != NJS_OK) { - njs_printf("lvlhsh unit test failed: key %08lX not found in hash\n", - (long) key); - } - - return ret; -} - - -static njs_int_t -lvlhsh_unit_test(njs_uint_t n) -{ - njs_mp_t *pool; - uint32_t key; - njs_uint_t i; - njs_lvlhsh_t lh; - njs_lvlhsh_each_t lhe; - - const size_t min_chunk_size = 32; - const size_t page_size = 1024; - const size_t page_alignment = 128; - const size_t cluster_size = 4096; - - pool = njs_mp_create(cluster_size, page_alignment, page_size, - min_chunk_size); - if (pool == NULL) { - return NJS_ERROR; - } - - njs_printf("lvlhsh unit test started: %l items\n", (long) n); - - njs_memzero(&lh, sizeof(njs_lvlhsh_t)); - - key = 0; - for (i = 0; i < n; i++) { - key = njs_murmur_hash2(&key, sizeof(uint32_t)); - - if (lvlhsh_unit_test_add(&lh, &lvlhsh_proto, pool, key) != NJS_OK) { - njs_printf("lvlhsh add unit test failed at %l\n", (long) i); - return NJS_ERROR; - } - } - - key = 0; - for (i = 0; i < n; i++) { - key = njs_murmur_hash2(&key, sizeof(uint32_t)); - - if (lvlhsh_unit_test_get(&lh, &lvlhsh_proto, key) != NJS_OK) { - return NJS_ERROR; - } - } - - njs_lvlhsh_each_init(&lhe, &lvlhsh_proto); - - for (i = 0; i < n + 1; i++) { - if (njs_lvlhsh_each(&lh, &lhe) == NULL) { - break; - } - } - - if (i != n) { - njs_printf("lvlhsh each unit test failed at %l of %l\n", - (long) i, (long) n); - return NJS_ERROR; - } - - key = 0; - for (i = 0; i < n; i++) { - key = njs_murmur_hash2(&key, sizeof(uint32_t)); - - if (lvlhsh_unit_test_delete(&lh, &lvlhsh_proto, pool, key) != NJS_OK) { - return NJS_ERROR; - } - } - - if (!njs_mp_is_empty(pool)) { - njs_printf("mem cache pool is not empty\n"); - return NJS_ERROR; - } - - njs_mp_destroy(pool); - - njs_printf("lvlhsh unit test passed\n"); - - return NJS_OK; -} - - -int -main(void) -{ - return lvlhsh_unit_test(1000 * 1000); -} diff --git a/src/test/njs_externals_test.c b/src/test/njs_externals_test.c index d3d3f1c1..d34ec1f2 100644 --- a/src/test/njs_externals_test.c +++ b/src/test/njs_externals_test.c @@ -13,7 +13,7 @@ typedef struct { - njs_lvlhsh_t hash; + njs_flathsh_t hash; uint32_t a; uint32_t d; @@ -56,7 +56,7 @@ njs_module_t njs_unit_test_external_module = { static njs_int_t -lvlhsh_unit_test_key_test(njs_lvlhsh_query_t *lhq, void *data) +flathsh_unit_test_key_test(njs_flathsh_query_t *fhq, void *data) { njs_str_t name; njs_unit_test_prop_t *prop; @@ -64,11 +64,11 @@ lvlhsh_unit_test_key_test(njs_lvlhsh_query_t *lhq, void *data) prop = *(njs_unit_test_prop_t **) data; name = prop->name; - if (name.length != lhq->key.length) { + if (name.length != fhq->key.length) { return NJS_DECLINED; } - if (memcmp(name.start, lhq->key.start, lhq->key.length) == 0) { + if (memcmp(name.start, fhq->key.start, fhq->key.length) == 0) { return NJS_OK; } @@ -77,29 +77,28 @@ lvlhsh_unit_test_key_test(njs_lvlhsh_query_t *lhq, void *data) static void * -lvlhsh_unit_test_pool_alloc(void *pool, size_t size) +flathsh_unit_test_pool_alloc(void *pool, size_t size) { return njs_mp_align(pool, NJS_MAX_ALIGNMENT, size); } static void -lvlhsh_unit_test_pool_free(void *pool, void *p, size_t size) +flathsh_unit_test_pool_free(void *pool, void *p, size_t size) { njs_mp_free(pool, p); } -static const njs_lvlhsh_proto_t lvlhsh_proto njs_aligned(64) = { - NJS_LVLHSH_LARGE_SLAB, - lvlhsh_unit_test_key_test, - lvlhsh_unit_test_pool_alloc, - lvlhsh_unit_test_pool_free, +static const njs_flathsh_proto_t flathsh_proto njs_aligned(64) = { + flathsh_unit_test_key_test, + flathsh_unit_test_pool_alloc, + flathsh_unit_test_pool_free, }; static njs_unit_test_prop_t * -lvlhsh_unit_test_alloc(njs_mp_t *pool, const njs_str_t *name, +flathsh_unit_test_alloc(njs_mp_t *pool, const njs_str_t *name, const njs_value_t *value) { njs_unit_test_prop_t *prop; @@ -120,22 +119,21 @@ lvlhsh_unit_test_alloc(njs_mp_t *pool, const njs_str_t *name, static njs_int_t -lvlhsh_unit_test_add(njs_mp_t *pool, njs_unit_test_req_t *r, +flathsh_unit_test_add(njs_mp_t *pool, njs_unit_test_req_t *r, njs_unit_test_prop_t *prop) { - njs_lvlhsh_query_t lhq; + njs_flathsh_query_t fhq; - lhq.key = prop->name; - lhq.key_hash = njs_djb_hash(lhq.key.start, lhq.key.length); + fhq.key = prop->name; + fhq.key_hash = njs_djb_hash(fhq.key.start, fhq.key.length); - lhq.replace = 1; - lhq.proto = &lvlhsh_proto; - lhq.pool = pool; - - switch (njs_lvlhsh_insert(&r->hash, &lhq)) { + fhq.replace = 1; + fhq.proto = &flathsh_proto; + fhq.pool = pool; + switch (njs_flathsh_insert(&r->hash, &fhq)) { case NJS_OK: - ((njs_flathsh_elt_t *) lhq.value)->value[0] = (void *) prop; + ((njs_flathsh_elt_t *) fhq.value)->value[0] = (void *) prop; return NJS_OK; case NJS_DECLINED: @@ -237,7 +235,7 @@ njs_unit_test_r_vars(njs_vm_t *vm, njs_object_prop_t *self, uint32_t atom_id, njs_value_t *value, njs_value_t *setval, njs_value_t *retval) { njs_int_t ret; - njs_lvlhsh_query_t lhq; + njs_flathsh_query_t fhq; njs_unit_test_req_t *r; njs_unit_test_prop_t *prop; @@ -247,7 +245,7 @@ njs_unit_test_r_vars(njs_vm_t *vm, njs_object_prop_t *self, uint32_t atom_id, return NJS_DECLINED; } - ret = njs_vm_prop_name(vm, atom_id, &lhq.key); + ret = njs_vm_prop_name(vm, atom_id, &fhq.key); if (ret != NJS_OK) { if (setval == NULL && retval != NULL) { /* Get. */ @@ -260,7 +258,7 @@ njs_unit_test_r_vars(njs_vm_t *vm, njs_object_prop_t *self, uint32_t atom_id, if (setval != NULL || retval == NULL) { /* Set or Delete. */ - if (lhq.key.length == 5 && memcmp(lhq.key.start, "error", 5) == 0) { + if (fhq.key.length == 5 && memcmp(fhq.key.start, "error", 5) == 0) { njs_vm_error(vm, "cannot %s \"error\" prop", retval != NULL ? "set" : "delete"); return NJS_ERROR; @@ -269,15 +267,15 @@ njs_unit_test_r_vars(njs_vm_t *vm, njs_object_prop_t *self, uint32_t atom_id, if (setval != NULL) { /* Set. */ - prop = lvlhsh_unit_test_alloc(njs_vm_memory_pool(vm), &lhq.key, setval); + prop = flathsh_unit_test_alloc(njs_vm_memory_pool(vm), &fhq.key, setval); if (prop == NULL) { njs_vm_memory_error(vm); return NJS_ERROR; } - ret = lvlhsh_unit_test_add(njs_vm_memory_pool(vm), r, prop); + ret = flathsh_unit_test_add(njs_vm_memory_pool(vm), r, prop); if (ret != NJS_OK) { - njs_vm_error(vm, "lvlhsh_unit_test_add() failed"); + njs_vm_error(vm, "flathsh_unit_test_add() failed"); return NJS_ERROR; } @@ -286,13 +284,13 @@ njs_unit_test_r_vars(njs_vm_t *vm, njs_object_prop_t *self, uint32_t atom_id, /* Get or Delete. */ - lhq.key_hash = njs_djb_hash(lhq.key.start, lhq.key.length); - lhq.proto = &lvlhsh_proto; + fhq.key_hash = njs_djb_hash(fhq.key.start, fhq.key.length); + fhq.proto = &flathsh_proto; - ret = njs_lvlhsh_find(&r->hash, &lhq); + ret = njs_flathsh_find(&r->hash, &fhq); if (ret == NJS_OK) { - prop = ((njs_flathsh_elt_t *) lhq.value)->value[0]; + prop = ((njs_flathsh_elt_t *) fhq.value)->value[0]; if (retval == NULL) { njs_value_invalid_set(njs_value_arg(&prop->value)); @@ -1130,19 +1128,19 @@ njs_externals_init_internal(njs_vm_t *vm, njs_unit_test_req_init_t *init, return NJS_ERROR; } - prop = lvlhsh_unit_test_alloc(njs_vm_memory_pool(vm), - &init[i].props[j].name, - njs_value_arg(&value)); + prop = flathsh_unit_test_alloc(njs_vm_memory_pool(vm), + &init[i].props[j].name, + njs_value_arg(&value)); if (njs_slow_path(prop == NULL)) { - njs_printf("lvlhsh_unit_test_alloc() failed\n"); + njs_printf("flathsh_unit_test_alloc() failed\n"); return NJS_ERROR; } - ret = lvlhsh_unit_test_add(njs_vm_memory_pool(vm), &requests[i], - prop); + ret = flathsh_unit_test_add(njs_vm_memory_pool(vm), &requests[i], + prop); if (njs_slow_path(ret != NJS_OK)) { - njs_printf("lvlhsh_unit_test_add() failed\n"); + njs_printf("flathsh_unit_test_add() failed\n"); return NJS_ERROR; } } |