From 48155f3a492beb101b5615dc7ff97f525133b434 Mon Sep 17 00:00:00 2001 From: Valentin Bartenev Date: Tue, 23 May 2017 14:02:37 +0300 Subject: Optimized internal representation of JSON objects and arrays. --- src/nxt_conf.h | 2 + src/nxt_conf_json.c | 442 +++++++++++++++++++++++++++++++--------------------- 2 files changed, 266 insertions(+), 178 deletions(-) (limited to 'src') diff --git a/src/nxt_conf.h b/src/nxt_conf.h index cf073e3a..43154a8f 100644 --- a/src/nxt_conf.h +++ b/src/nxt_conf.h @@ -20,6 +20,8 @@ typedef struct { nxt_conf_json_value_t *nxt_conf_json_value_get(nxt_conf_json_value_t *value, nxt_str_t *path); +nxt_conf_json_value_t *nxt_conf_json_object_get_member( + nxt_conf_json_value_t *value, u_char *name, size_t length); nxt_conf_json_value_t *nxt_conf_json_parse(u_char *pos, size_t length, nxt_mem_pool_t *pool); uintptr_t nxt_conf_json_print_value(u_char *pos, nxt_conf_json_value_t *value, diff --git a/src/nxt_conf_json.c b/src/nxt_conf_json.c index 0a9db0b3..618ed28c 100644 --- a/src/nxt_conf_json.c +++ b/src/nxt_conf_json.c @@ -25,33 +25,41 @@ typedef enum { } nxt_conf_json_type_t; +typedef struct nxt_conf_json_array_s nxt_conf_json_array_t; +typedef struct nxt_conf_json_object_s nxt_conf_json_object_t; + + struct nxt_conf_json_value_s { union { - uint32_t boolean; /* 1 bit. */ - int64_t integer; - /* double number; */ - u_char str[15]; - nxt_str_t *string; - nxt_lvlhsh_t *object; - nxt_array_t *array; + uint32_t boolean; /* 1 bit. */ + int64_t integer; + /* double number; */ + u_char str[15]; + nxt_str_t *string; + nxt_conf_json_array_t *array; + nxt_conf_json_object_t *object; } u; - nxt_conf_json_type_t type:8; /* 3 bits. */ + nxt_conf_json_type_t type:8; /* 3 bits. */ +}; + + +struct nxt_conf_json_array_s { + nxt_uint_t count; + nxt_conf_json_value_t elements[]; }; typedef struct { - nxt_conf_json_value_t name; - nxt_conf_json_value_t value; + nxt_conf_json_value_t name; + nxt_conf_json_value_t value; } nxt_conf_json_obj_member_t; -static nxt_int_t nxt_conf_json_object_hash_test(nxt_lvlhsh_query_t *lhq, - void *data); -static nxt_int_t nxt_conf_json_object_member_add(nxt_lvlhsh_t *lvlhsh, - nxt_conf_json_obj_member_t *member, nxt_mem_pool_t *pool); -static nxt_conf_json_value_t *nxt_conf_json_object_member_get( - nxt_lvlhsh_t *lvlhsh, u_char *name, size_t length); +struct nxt_conf_json_object_s { + nxt_uint_t count; + nxt_conf_json_obj_member_t members[]; +}; static u_char *nxt_conf_json_skip_space(u_char *pos, u_char *end); @@ -59,6 +67,10 @@ static u_char *nxt_conf_json_parse_value(u_char *pos, u_char *end, nxt_conf_json_value_t *value, nxt_mem_pool_t *pool); static u_char *nxt_conf_json_parse_object(u_char *pos, u_char *end, nxt_conf_json_value_t *value, nxt_mem_pool_t *pool); +static nxt_int_t nxt_conf_json_object_hash_add(nxt_lvlhsh_t *lvlhsh, + nxt_conf_json_obj_member_t *member, nxt_mem_pool_t *pool); +static nxt_int_t nxt_conf_json_object_hash_test(nxt_lvlhsh_query_t *lhq, + void *data); static u_char *nxt_conf_json_parse_array(u_char *pos, u_char *end, nxt_conf_json_value_t *value, nxt_mem_pool_t *pool); static u_char *nxt_conf_json_parse_string(u_char *pos, u_char *end, @@ -95,122 +107,69 @@ nxt_conf_json_indentation(u_char *pos, nxt_conf_json_pretty_t *pretty) } -static const nxt_lvlhsh_proto_t nxt_conf_json_object_hash_proto - nxt_aligned(64) = +nxt_conf_json_value_t * +nxt_conf_json_value_get(nxt_conf_json_value_t *value, nxt_str_t *path) { - NXT_LVLHSH_DEFAULT, - 0, - nxt_conf_json_object_hash_test, - nxt_lvlhsh_pool_alloc, - nxt_lvlhsh_pool_free, -}; - + u_char *p, *start, *end; -static nxt_int_t -nxt_conf_json_object_hash_test(nxt_lvlhsh_query_t *lhq, void *data) -{ - nxt_conf_json_value_t *name; + p = path->start; + end = p + path->length; - name = &((nxt_conf_json_obj_member_t *) data)->name; + if (p != end && end[-1] == '/') { + end--; + } - if (name->type == NXT_CONF_JSON_SHORT_STRING) { + while (p != end) { + start = p + 1; + p = start; - if (nxt_str_eq(&lhq->key, &name->u.str[1], name->u.str[0])) { - return NXT_OK; + while (p != end && *p != '/') { + p++; } - } else { + value = nxt_conf_json_object_get_member(value, start, p - start); - if (nxt_strstr_eq(&lhq->key, name->u.string)) { - return NXT_OK; + if (value == NULL) { + return NULL; } } - return NXT_DECLINED; -} - - -static nxt_int_t -nxt_conf_json_object_member_add(nxt_lvlhsh_t *lvlhsh, - nxt_conf_json_obj_member_t *member, nxt_mem_pool_t *pool) -{ - nxt_lvlhsh_query_t lhq; - nxt_conf_json_value_t *name; - - name = &member->name; - - if (name->type == NXT_CONF_JSON_SHORT_STRING) { - lhq.key.length = name->u.str[0]; - lhq.key.start = &name->u.str[1]; - - } else { - lhq.key = *name->u.string; - } - - lhq.key_hash = nxt_djb_hash(lhq.key.start, lhq.key.length); - lhq.replace = 0; - lhq.value = member; - lhq.proto = &nxt_conf_json_object_hash_proto; - lhq.pool = pool; - - return nxt_lvlhsh_insert(lvlhsh, &lhq); + return value; } -static nxt_conf_json_value_t * -nxt_conf_json_object_member_get(nxt_lvlhsh_t *lvlhsh, u_char *name, +nxt_conf_json_value_t * +nxt_conf_json_object_get_member(nxt_conf_json_value_t *value, u_char *name, size_t length) { - nxt_lvlhsh_query_t lhq; + nxt_str_t str; + nxt_uint_t n; + nxt_conf_json_object_t *object; nxt_conf_json_obj_member_t *member; - lhq.key_hash = nxt_djb_hash(name, length); - lhq.key.length = length; - lhq.key.start = name; - lhq.proto = &nxt_conf_json_object_hash_proto; - - if (nxt_fast_path(nxt_lvlhsh_find(lvlhsh, &lhq) == NXT_OK)) { - member = lhq.value; - return &member->value; + if (value->type != NXT_CONF_JSON_OBJECT) { + return NULL; } - return NULL; -} - - -nxt_conf_json_value_t * -nxt_conf_json_value_get(nxt_conf_json_value_t *value, nxt_str_t *path) -{ - u_char *p, *start, *end; - - p = path->start; - end = p + path->length; - - if (p != end && end[-1] == '/') { - end--; - } + object = value->u.object; - while (p != end) { - start = p + 1; - p = start; + for (n = 0; n < object->count; n++) { + member = &object->members[n]; - while (p != end && *p != '/') { - p++; - } + if (member->name.type == NXT_CONF_JSON_SHORT_STRING) { + str.length = member->name.u.str[0]; + str.start = &member->name.u.str[1]; - if (value->type != NXT_CONF_JSON_OBJECT) { - return NULL; + } else { + str = *member->name.u.string; } - value = nxt_conf_json_object_member_get(value->u.object, start, - p - start); - - if (value == NULL) { - return NULL; + if (nxt_str_eq(&str, name, length)) { + return &member->value; } } - return value; + return NULL; } @@ -330,23 +289,28 @@ nxt_conf_json_parse_value(u_char *pos, u_char *end, } +static const nxt_lvlhsh_proto_t nxt_conf_json_object_hash_proto + nxt_aligned(64) = +{ + NXT_LVLHSH_DEFAULT, + 0, + nxt_conf_json_object_hash_test, + nxt_lvlhsh_pool_alloc, + nxt_lvlhsh_pool_free, +}; + + static u_char * nxt_conf_json_parse_object(u_char *pos, u_char *end, nxt_conf_json_value_t *value, nxt_mem_pool_t *pool) { nxt_int_t rc; - nxt_lvlhsh_t *object; - nxt_conf_json_obj_member_t *member; - - object = nxt_mem_alloc(pool, sizeof(nxt_lvlhsh_t)); - if (nxt_slow_path(object == NULL)) { - return NULL; - } - - nxt_lvlhsh_init(object); - - value->type = NXT_CONF_JSON_OBJECT; - value->u.object = object; + nxt_uint_t count; + nxt_lvlhsh_t hash; + nxt_mem_pool_t *temp_pool; + nxt_lvlhsh_each_t lhe; + nxt_conf_json_object_t *object; + nxt_conf_json_obj_member_t *member, *element; pos = nxt_conf_json_skip_space(pos + 1, end); @@ -354,52 +318,64 @@ nxt_conf_json_parse_object(u_char *pos, u_char *end, return NULL; } + temp_pool = nxt_mem_pool_create(256); + if (nxt_slow_path(temp_pool == NULL)) { + return NULL; + } + + nxt_lvlhsh_init(&hash); + + count = 0; + if (*pos != '}') { for ( ;; ) { + count++; + if (*pos != '"') { - return NULL; + goto error; } - member = nxt_mem_alloc(pool, sizeof(nxt_conf_json_obj_member_t)); + member = nxt_mem_alloc(temp_pool, + sizeof(nxt_conf_json_obj_member_t)); if (nxt_slow_path(member == NULL)) { - return NULL; + goto error; } pos = nxt_conf_json_parse_string(pos, end, &member->name, pool); if (nxt_slow_path(pos == NULL)) { - return NULL; + goto error; + } + + rc = nxt_conf_json_object_hash_add(&hash, member, temp_pool); + + if (nxt_slow_path(rc != NXT_OK)) { + goto error; } pos = nxt_conf_json_skip_space(pos, end); if (nxt_slow_path(pos == end || *pos != ':')) { - return NULL; + goto error; } pos = nxt_conf_json_skip_space(pos + 1, end); if (nxt_slow_path(pos == end)) { - return NULL; + goto error; } pos = nxt_conf_json_parse_value(pos, end, &member->value, pool); if (nxt_slow_path(pos == NULL)) { - return NULL; - } - - rc = nxt_conf_json_object_member_add(object, member, pool); - - if (nxt_slow_path(rc != NXT_OK)) { - return NULL; + goto error; } pos = nxt_conf_json_skip_space(pos, end); if (nxt_slow_path(pos == end)) { - return NULL; + goto error; } if (*pos == '}') { @@ -407,34 +383,113 @@ nxt_conf_json_parse_object(u_char *pos, u_char *end, } if (nxt_slow_path(*pos != ',')) { - return NULL; + goto error; } pos = nxt_conf_json_skip_space(pos + 1, end); if (nxt_slow_path(pos == end)) { - return NULL; + goto error; } } } + object = nxt_mem_alloc(pool, sizeof(nxt_conf_json_object_t) + + count * sizeof(nxt_conf_json_obj_member_t)); + if (nxt_slow_path(object == NULL)) { + return NULL; + } + + value->u.object = object; + value->type = NXT_CONF_JSON_OBJECT; + + object->count = count; + member = object->members; + + nxt_memzero(&lhe, sizeof(nxt_lvlhsh_each_t)); + lhe.proto = &nxt_conf_json_object_hash_proto; + + for ( ;; ) { + element = nxt_lvlhsh_each(&hash, &lhe); + + if (element == NULL) { + break; + } + + *member++ = *element; + } + + nxt_mem_pool_destroy(temp_pool); + return pos + 1; + +error: + + nxt_mem_pool_destroy(temp_pool); + return NULL; } -static u_char * -nxt_conf_json_parse_array(u_char *pos, u_char *end, - nxt_conf_json_value_t *value, nxt_mem_pool_t *pool) +static nxt_int_t +nxt_conf_json_object_hash_add(nxt_lvlhsh_t *lvlhsh, + nxt_conf_json_obj_member_t *member, nxt_mem_pool_t *pool) { - nxt_array_t *array; + nxt_lvlhsh_query_t lhq; + nxt_conf_json_value_t *name; - array = nxt_array_create(pool, 8, sizeof(nxt_conf_json_value_t)); - if (nxt_slow_path(array == NULL)) { - return NULL; + name = &member->name; + + if (name->type == NXT_CONF_JSON_SHORT_STRING) { + lhq.key.length = name->u.str[0]; + lhq.key.start = &name->u.str[1]; + + } else { + lhq.key = *name->u.string; } - value->type = NXT_CONF_JSON_ARRAY; - value->u.array = array; + lhq.key_hash = nxt_djb_hash(lhq.key.start, lhq.key.length); + lhq.replace = 0; + lhq.value = member; + lhq.proto = &nxt_conf_json_object_hash_proto; + lhq.pool = pool; + + return nxt_lvlhsh_insert(lvlhsh, &lhq); +} + + +static nxt_int_t +nxt_conf_json_object_hash_test(nxt_lvlhsh_query_t *lhq, void *data) +{ + nxt_str_t str; + nxt_conf_json_value_t *name; + + name = &((nxt_conf_json_obj_member_t *) data)->name; + + if (name->type == NXT_CONF_JSON_SHORT_STRING) { + str.length = name->u.str[0]; + str.start = &name->u.str[1]; + + } else { + str = *name->u.string; + } + + if (nxt_strstr_eq(&lhq->key, &str)) { + return NXT_OK; + } + + return NXT_DECLINED; +} + + +static u_char * +nxt_conf_json_parse_array(u_char *pos, u_char *end, + nxt_conf_json_value_t *value, nxt_mem_pool_t *pool) +{ + nxt_uint_t count; + nxt_list_t *list; + nxt_mem_pool_t *temp_pool; + nxt_conf_json_array_t *array; + nxt_conf_json_value_t *element; pos = nxt_conf_json_skip_space(pos + 1, end); @@ -442,24 +497,38 @@ nxt_conf_json_parse_array(u_char *pos, u_char *end, return NULL; } + temp_pool = nxt_mem_pool_create(256); + if (nxt_slow_path(temp_pool == NULL)) { + return NULL; + } + + list = nxt_list_create(temp_pool, 8, sizeof(nxt_conf_json_value_t)); + if (nxt_slow_path(list == NULL)) { + goto error; + } + + count = 0; + if (*pos != ']') { for ( ;; ) { - value = nxt_array_add(array); - if (nxt_slow_path(value == NULL)) { - return NULL; + count++; + + element = nxt_list_add(list); + if (nxt_slow_path(element == NULL)) { + goto error; } - pos = nxt_conf_json_parse_value(pos, end, value, pool); + pos = nxt_conf_json_parse_value(pos, end, element, pool); if (nxt_slow_path(pos == NULL)) { - return NULL; + goto error; } pos = nxt_conf_json_skip_space(pos, end); if (nxt_slow_path(pos == end)) { - return NULL; + goto error; } if (*pos == ']') { @@ -467,18 +536,41 @@ nxt_conf_json_parse_array(u_char *pos, u_char *end, } if (nxt_slow_path(*pos != ',')) { - return NULL; + goto error; } pos = nxt_conf_json_skip_space(pos + 1, end); if (nxt_slow_path(pos == end)) { - return NULL; + goto error; } } } + array = nxt_mem_alloc(pool, sizeof(nxt_conf_json_array_t) + + count * sizeof(nxt_conf_json_value_t)); + if (nxt_slow_path(array == NULL)) { + goto error; + } + + value->u.array = array; + value->type = NXT_CONF_JSON_ARRAY; + + array->count = count; + element = array->elements; + + nxt_list_each(value, list) { + *element++ = *value; + } nxt_list_loop; + + nxt_mem_pool_destroy(temp_pool); + return pos + 1; + +error: + + nxt_mem_pool_destroy(temp_pool); + return NULL; } @@ -943,9 +1035,9 @@ static uintptr_t nxt_conf_json_print_array(u_char *pos, nxt_conf_json_value_t *value, nxt_conf_json_pretty_t *pretty) { - size_t len; - uint32_t n; - nxt_array_t *array; + size_t len; + nxt_uint_t n; + nxt_conf_json_array_t *array; array = value->u.array; @@ -957,9 +1049,9 @@ nxt_conf_json_print_array(u_char *pos, nxt_conf_json_value_t *value, pretty->level++; } - value = array->elts; + value = array->elements; - for (n = 0; n < array->nelts; n++) { + for (n = 0; n < array->count; n++) { len += nxt_conf_json_print_value(NULL, &value[n], pretty); if (pretty != NULL) { @@ -983,8 +1075,8 @@ nxt_conf_json_print_array(u_char *pos, nxt_conf_json_value_t *value, *pos++ = '['; - if (array->nelts != 0) { - value = array->elts; + if (array->count != 0) { + value = array->elements; if (pretty != NULL) { pos = nxt_conf_json_newline(pos); @@ -995,7 +1087,7 @@ nxt_conf_json_print_array(u_char *pos, nxt_conf_json_value_t *value, pos = (u_char *) nxt_conf_json_print_value(pos, &value[0], pretty); - for (n = 1; n < array->nelts; n++) { + for (n = 1; n < array->count; n++) { *pos++ = ','; if (pretty != NULL) { @@ -1029,14 +1121,10 @@ nxt_conf_json_print_object(u_char *pos, nxt_conf_json_value_t *value, nxt_conf_json_pretty_t *pretty) { size_t len; - nxt_lvlhsh_t *object; - nxt_lvlhsh_each_t lhe; + nxt_uint_t n; + nxt_conf_json_object_t *object; nxt_conf_json_obj_member_t *member; - nxt_memzero(&lhe, sizeof(nxt_lvlhsh_each_t)); - - lhe.proto = &nxt_conf_json_object_hash_proto; - object = value->u.object; if (pos == NULL) { @@ -1047,15 +1135,11 @@ nxt_conf_json_print_object(u_char *pos, nxt_conf_json_value_t *value, pretty->level++; } - for ( ;; ) { - member = nxt_lvlhsh_each(object, &lhe); - - if (member == NULL) { - break; - } + member = object->members; - len += nxt_conf_json_print_string(NULL, &member->name) + 1 - + nxt_conf_json_print_value(NULL, &member->value, pretty) + for (n = 0; n < object->count; n++) { + len += nxt_conf_json_print_string(NULL, &member[n].name) + 1 + + nxt_conf_json_print_value(NULL, &member[n].value, pretty) + 1; if (pretty != NULL) { @@ -1079,21 +1163,23 @@ nxt_conf_json_print_object(u_char *pos, nxt_conf_json_value_t *value, *pos++ = '{'; - member = nxt_lvlhsh_each(object, &lhe); - - if (member != NULL) { + if (object->count != 0) { if (pretty != NULL) { pos = nxt_conf_json_newline(pos); pretty->level++; } + member = object->members; + + n = 0; + for ( ;; ) { if (pretty != NULL) { pos = nxt_conf_json_indentation(pos, pretty); } - pos = (u_char *) nxt_conf_json_print_string(pos, &member->name); + pos = (u_char *) nxt_conf_json_print_string(pos, &member[n].name); *pos++ = ':'; @@ -1101,12 +1187,12 @@ nxt_conf_json_print_object(u_char *pos, nxt_conf_json_value_t *value, *pos++ = ' '; } - pos = (u_char *) nxt_conf_json_print_value(pos, &member->value, + pos = (u_char *) nxt_conf_json_print_value(pos, &member[n].value, pretty); - member = nxt_lvlhsh_each(object, &lhe); + n++; - if (member == NULL) { + if (n == object->count) { break; } -- cgit