Optimized internal representation of JSON objects and arrays.

1 files changed, 264 insertions, 178 deletions

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;
             }