[PATCH v4 08/14] lib: implement JSON tree class for json library
Kirill Shcherbatov
kshcherbatov at tarantool.org
Thu Oct 11 10:58:53 MSK 2018
New JSON tree class would store JSON paths for tuple fields
for registered non-plain indexes. It is a hierarchical data
structure that organize JSON nodes produced by parser.
Class provides API to lookup node by path and iterate over the
tree.
JSON Indexes patch require such functionality to make lookup
for tuple_fields by path, make initialization of field map and
build vynyl_stmt msgpack for secondary index via JSON tree
iteration.
Need for #1012.
---
src/lib/json/CMakeLists.txt | 2 +
src/lib/json/tree.c | 300 ++++++++++++++++++++++++++++++++++++++++++++
src/lib/json/tree.h | 260 ++++++++++++++++++++++++++++++++++++++
test/unit/json_path.c | 204 +++++++++++++++++++++++++++++-
test/unit/json_path.result | 48 ++++++-
5 files changed, 812 insertions(+), 2 deletions(-)
create mode 100644 src/lib/json/tree.c
create mode 100644 src/lib/json/tree.h
diff --git a/src/lib/json/CMakeLists.txt b/src/lib/json/CMakeLists.txt
index 203fe6f..9eaba37 100644
--- a/src/lib/json/CMakeLists.txt
+++ b/src/lib/json/CMakeLists.txt
@@ -1,6 +1,8 @@
set(lib_sources
path.c
+ tree.c
)
set_source_files_compile_flags(${lib_sources})
add_library(json_path STATIC ${lib_sources})
+target_link_libraries(json_path misc)
diff --git a/src/lib/json/tree.c b/src/lib/json/tree.c
new file mode 100644
index 0000000..2f82287
--- /dev/null
+++ b/src/lib/json/tree.c
@@ -0,0 +1,300 @@
+
+/*
+ * Copyright 2010-2018 Tarantool AUTHORS: please see AUTHORS file.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above
+ * copyright notice, this list of conditions and the
+ * following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above
+ * copyright notice, this list of conditions and the following
+ * disclaimer in the documentation and/or other materials
+ * provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY <COPYRIGHT HOLDER> ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
+ * <COPYRIGHT HOLDER> OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
+ * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include <assert.h>
+#include <ctype.h>
+#include <string.h>
+#include <stdbool.h>
+#include <stddef.h>
+#include <stdint.h>
+
+#include "small/rlist.h"
+#include "trivia/util.h"
+#include "tree.h"
+#include "path.h"
+#include "third_party/PMurHash.h"
+
+
+/**
+ * Hash table: json_path_node => json_tree_node.
+ */
+struct mh_json_tree_node {
+ struct json_path_node key;
+ uint32_t key_hash;
+ struct json_tree_node *node;
+};
+
+/**
+ * Compare hash records of two json tree nodes. Return 0 if equal.
+ */
+static inline int
+mh_json_tree_node_cmp(const struct mh_json_tree_node *a,
+ const struct mh_json_tree_node *b)
+{
+ if (a->key.type != b->key.type)
+ return a->key.type - b->key.type;
+ if (a->key.type == JSON_PATH_STR) {
+ if (a->key.len != b->key.len)
+ return a->key.len - b->key.len;
+ return memcmp(a->key.str, b->key.str, a->key.len);
+ } else if (a->key.type == JSON_PATH_NUM) {
+ return a->key_hash - b->key_hash;
+ }
+ unreachable();
+}
+
+#define MH_SOURCE 1
+#define mh_name _json_tree_node
+#define mh_key_t struct mh_json_tree_node *
+#define mh_node_t struct mh_json_tree_node
+#define mh_arg_t void *
+#define mh_hash(a, arg) ((a)->key_hash)
+#define mh_hash_key(a, arg) ((a)->key_hash)
+#define mh_cmp(a, b, arg) (mh_json_tree_node_cmp((a), (b)))
+#define mh_cmp_key(a, b, arg) mh_cmp(a, b, arg)
+#include "salad/mhash.h"
+
+static const uint32_t json_path_node_hash_seed = 13U;
+
+uint32_t
+json_path_node_hash(struct json_path_node *key)
+{
+ uint32_t h = json_path_node_hash_seed;
+ uint32_t carry = 0;
+ const void *data;
+ uint32_t data_size;
+ if (key->type == JSON_PATH_STR) {
+ data = key->str;
+ data_size = key->len;
+ } else if (key->type == JSON_PATH_NUM) {
+ data = &key->num;
+ data_size = sizeof(key->num);
+ } else {
+ unreachable();
+ }
+ PMurHash32_Process(&h, &carry, data, data_size);
+ return PMurHash32_Result(h, carry, data_size);
+}
+
+void
+json_tree_node_create(struct json_tree_node *node,
+ struct json_path_node *path_node, uint32_t path_node_hash)
+{
+ assert(path_node == NULL ||
+ path_node_hash == json_path_node_hash(path_node));
+ memset(node, 0, sizeof(struct json_tree_node));
+ if (path_node != NULL) {
+ node->key = *path_node;
+ node->key_hash = path_node_hash;
+ } else {
+ node->key.type = JSON_PATH_END;
+ }
+ rlist_create(&node->sibling);
+ rlist_create(&node->children);
+}
+
+uint32_t
+json_tree_node_children_count(struct json_tree_node *node)
+{
+ return node->child_by_path_node != NULL ?
+ mh_size(node->child_by_path_node) : 0;
+}
+
+void
+json_tree_node_destroy(struct json_tree_node *node)
+{
+ if (node->child_by_path_node != NULL)
+ mh_json_tree_node_delete(node->child_by_path_node);
+}
+
+struct json_tree_node *
+json_tree_lookup_by_path_node(struct json_tree_node *parent,
+ struct json_path_node *path_node,
+ uint32_t path_node_hash)
+{
+ if (unlikely(parent->child_by_path_node == NULL))
+ return NULL;
+ struct mh_json_tree_node info;
+ info.key = *path_node;
+ info.key_hash = path_node_hash;
+ mh_int_t id =
+ mh_json_tree_node_find(parent->child_by_path_node, &info, NULL);
+ if (id == mh_end(parent->child_by_path_node))
+ return NULL;
+ struct mh_json_tree_node *ht_node =
+ mh_json_tree_node_node(parent->child_by_path_node, id);
+ assert(ht_node == NULL || ht_node->node != NULL);
+ struct json_tree_node *ret = ht_node != NULL ? ht_node->node : NULL;
+ assert(ret == NULL || ret->parent == parent);
+ return ret;
+}
+
+int
+json_tree_add(struct json_tree_node *parent, struct json_tree_node *node)
+{
+ assert(node->parent == NULL);
+ if (unlikely(parent->child_by_path_node == NULL)) {
+ parent->child_by_path_node = mh_json_tree_node_new();
+ if (parent->child_by_path_node == NULL)
+ return -1;
+ }
+ assert(json_tree_lookup_by_path_node(parent, &node->key,
+ node->key_hash) == NULL);
+ struct mh_json_tree_node ht_node;
+ ht_node.key = node->key;
+ ht_node.key_hash = node->key_hash;
+ ht_node.node = node;
+ mh_int_t rc = mh_json_tree_node_put(parent->child_by_path_node,
+ &ht_node, NULL, NULL);
+ if (rc == mh_end(parent->child_by_path_node))
+ return -1;
+ node->parent = parent;
+ if (node->key.type == JSON_PATH_NUM) {
+ /*
+ * Insert an entry into the list, keeping the
+ * numerical values in ascending order.
+ */
+ struct json_tree_node *curr_entry = NULL;
+ struct rlist *prev_rlist_node = &parent->children;
+ rlist_foreach_entry(curr_entry, &parent->children, sibling) {
+ assert(curr_entry->key.type == JSON_PATH_NUM);
+ if (curr_entry->key.num >= node->key.num)
+ break;
+ prev_rlist_node = &curr_entry->sibling;
+ }
+ rlist_add(prev_rlist_node, &node->sibling);
+ } else {
+ rlist_add(&parent->children, &node->sibling);
+ }
+ return 0;
+}
+
+void
+json_tree_remove(struct json_tree_node *parent, struct json_tree_node *node)
+{
+ assert(node->parent == parent);
+ assert(parent->child_by_path_node != NULL);
+ assert(json_tree_lookup_by_path_node(parent, &node->key,
+ node->key_hash) == node);
+ rlist_del(&node->sibling);
+ struct mh_json_tree_node info;
+ info.key = node->key;
+ info.key_hash = node->key_hash;
+ mh_int_t id =
+ mh_json_tree_node_find(parent->child_by_path_node, &info, NULL);
+ assert(id != mh_end(parent->child_by_path_node));
+ mh_json_tree_node_del(parent->child_by_path_node, id, NULL);
+ assert(json_tree_lookup_by_path_node(parent, &node->key,
+ node->key_hash) == NULL);
+}
+
+struct json_tree_node *
+json_tree_lookup_by_path(struct json_tree_node *parent, const char *path,
+ uint32_t path_len)
+{
+ if (unlikely(parent->child_by_path_node == NULL))
+ return NULL;
+ int rc;
+ struct json_path_parser parser;
+ struct json_path_node path_node;
+ struct json_tree_node *ret = parent;
+ json_path_parser_create(&parser, path, path_len);
+ while ((rc = json_path_next(&parser, &path_node)) == 0 &&
+ path_node.type != JSON_PATH_END && ret != NULL) {
+ uint32_t path_node_hash = json_path_node_hash(&path_node);
+ struct json_tree_node *node =
+ json_tree_lookup_by_path_node(ret, &path_node,
+ path_node_hash);
+ assert(node == NULL || node->parent == ret);
+ ret = node;
+ }
+ if (rc != 0 || path_node.type != JSON_PATH_END)
+ return NULL;
+ return ret;
+}
+
+static struct json_tree_node *
+json_tree_next_child(struct json_tree_node *parent, struct json_tree_node *pos)
+{
+ struct json_tree_node *next;
+ if (pos == NULL) {
+ next = rlist_first_entry(&parent->children,
+ struct json_tree_node, sibling);
+ } else {
+ next = rlist_next_entry(pos, sibling);
+ }
+ if (&next->sibling != &parent->children)
+ return next;
+ return NULL;
+}
+
+static struct json_tree_node *
+json_tree_leftmost(struct json_tree_node *pos)
+{
+ struct json_tree_node *last;
+ do {
+ last = pos;
+ pos = json_tree_next_child(pos, NULL);
+ } while (pos != NULL);
+ return last;
+}
+
+struct json_tree_node *
+json_tree_next_pre(struct json_tree_node *parent, struct json_tree_node *pos)
+{
+ if (pos == NULL)
+ return parent;
+ struct json_tree_node *next = json_tree_next_child(pos, NULL);
+ if (next != NULL)
+ return next;
+ while (pos != parent) {
+ next = json_tree_next_child(pos->parent, pos);
+ if (next != NULL)
+ return next;
+ pos = pos->parent;
+ }
+ return NULL;
+}
+
+struct json_tree_node *
+json_tree_next_post(struct json_tree_node *parent, struct json_tree_node *pos)
+{
+ struct json_tree_node *next;
+ if (pos == NULL)
+ return json_tree_leftmost(parent);
+ if (pos == parent)
+ return NULL;
+ next = json_tree_next_child(pos->parent, pos);
+ if (next != NULL)
+ return json_tree_leftmost(next);
+ return pos->parent;
+}
diff --git a/src/lib/json/tree.h b/src/lib/json/tree.h
new file mode 100644
index 0000000..45bf975
--- /dev/null
+++ b/src/lib/json/tree.h
@@ -0,0 +1,260 @@
+#ifndef TARANTOOL_JSON_TREE_H_INCLUDED
+#define TARANTOOL_JSON_TREE_H_INCLUDED
+/*
+ * Copyright 2010-2018 Tarantool AUTHORS: please see AUTHORS file.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above
+ * copyright notice, this list of conditions and the
+ * following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above
+ * copyright notice, this list of conditions and the following
+ * disclaimer in the documentation and/or other materials
+ * provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY <COPYRIGHT HOLDER> ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
+ * <COPYRIGHT HOLDER> OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
+ * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+#include <stdbool.h>
+#include <stdint.h>
+#include "small/rlist.h"
+#include "path.h"
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif
+
+struct mh_json_tree_node_t;
+
+/**
+ * JSON tree is a hierarchical data structure that organize JSON
+ * nodes produced by parser.
+ * 1. Numeric records are sorted in ascending order in sibling rlist.
+ * 2. Structure key records point to source strings memory.
+ * 3. Lookup by path complexity is O(path_len):
+ * path = path_token1 + .. + path_tokenN
+ * - Complexity of hash(path_tokenI) - O(strlen(path_tokenN))
+ * - Complexity of hash lookup - O(1) + strcmp on collision
+ */
+struct json_tree_node {
+ /** Path component represented by this node. */
+ struct json_path_node key;
+ /** Hash calculated for key field. */
+ uint32_t key_hash;
+ /**
+ * Children hashtable:
+ * json_path_node -> json_tree_node.
+ */
+ struct mh_json_tree_node_t *child_by_path_node;
+ /**
+ * Link in json_tree_node::children of the parent node.
+ */
+ struct rlist sibling;
+ /**
+ * List of child nodes, linked by
+ * json_tree_node::sibling.
+ */
+ struct rlist children;
+ /** Pointer to parent json_tree_node record. */
+ struct json_tree_node *parent;
+};
+
+/**
+ * Compute the hash value of a JSON path component.
+ * @param key JSON path component to compute the hash for.
+ * @retval Hash value.
+ */
+uint32_t
+json_path_node_hash(struct json_path_node *key);
+
+/**
+ * Init a JSON tree node.
+ * @param node JSON tree node to initialize.
+ * @param path_node JSON path component the new node will
+ * represent. May be NULL, in this case
+ * @node initialized as root record.
+ * @param path_node_hash Hash of @path_node, should be calculated
+ * with json_path_node_hash.
+ */
+void
+json_tree_node_create(struct json_tree_node *node,
+ struct json_path_node *path_node,
+ uint32_t path_node_hash);
+
+/**
+ * Destroy a JSON tree node.
+ * @param node JSON tree node to destruct.
+ */
+void
+json_tree_node_destroy(struct json_tree_node *node);
+
+/**
+ * Return count of JSON tree node direct descendant.
+ * Matches the size of the child_by_path_node hashtable.
+ * @param node JSON tree node to analyze.
+ * @retval Count of descendant.
+ */
+uint32_t
+json_tree_node_children_count(struct json_tree_node *node);
+
+/**
+ * Look up a child of a JSON tree node by a path component.
+ * @param parent JSON tree node to start lookup with.
+ * @param path_node JSON parser node with data.
+ * @param path_node_hash Hash of @path_node.
+ * @retval not NULL pointer to JSON tree node if any.
+ * @retval NULL on nothing found.
+ */
+struct json_tree_node *
+json_tree_lookup_by_path_node(struct json_tree_node *parent,
+ struct json_path_node *path_node,
+ uint32_t path_node_hash);
+
+/**
+ * Add a new JSON tree node at the given position in the tree.
+ * The parent node must not have a child representing the same
+ * path component.
+ * @param parent JSON tree parent node.
+ * @param node JSON tree node to append.
+ * @retval 0 On success, -1 on memory allocation error.
+ */
+int
+json_tree_add(struct json_tree_node *parent,
+ struct json_tree_node *node);
+
+/**
+ * Delete a JSON tree node at the given position in the tree.
+ * The parent node must have such child.
+ * @param parent JSON tree parent node.
+ * @param node JSON tree node to add.
+ */
+void
+json_tree_remove(struct json_tree_node *parent,
+ struct json_tree_node *node);
+
+/**
+ * Lookup a field by path in given position in the JSON tree.
+ * @param parent JSON tree parent node.
+ * @param path JSON path string.
+ * @param path_len Length of @path.
+ * @retval not NULL pointer to leaf record if any.
+ */
+struct json_tree_node *
+json_tree_lookup_by_path(struct json_tree_node *parent,
+ const char *path, uint32_t path_len);
+
+/**
+ * Make pre order traversal in JSON tree.
+ * @param parent The JSON path tree to walk parent.
+ * @param pos Iterator pointer, NULL for initialization.
+ * @retval not NULL pointer to next node. NULL if nothing found.
+ */
+struct json_tree_node *
+json_tree_next_pre(struct json_tree_node *parent,
+ struct json_tree_node *pos);
+
+/**
+ * Make post order traversal in JSON tree.
+ * @param parent The JSON path tree to walk parent.
+ * @param pos Iterator pointer, NULL for initialization.
+ * @retval not NULL pointer to next node. NULL if nothing found.
+ */
+struct json_tree_node *
+json_tree_next_post(struct json_tree_node *parent,
+ struct json_tree_node *pos);
+
+/** Return entry by json_tree_node item. */
+#define json_tree_entry(item, type, member) ({ \
+ const typeof( ((type *)0)->member ) *__mptr = (item); \
+ (type *)( (char *)__mptr - ((size_t) &((type *)0)->member) ); })
+
+/** Return entry by json_tree_node item or NULL if item is NULL.*/
+#define json_tree_entry_safe(item, type, member) ({ \
+ (item) != NULL ? json_tree_entry((item), type, member) : NULL; })
+
+/** Make lookup in tree by path and return entry. */
+#define json_tree_lookup_entry_by_path(root, path, path_len, type, member) \
+({struct json_tree_node *__tree_node = \
+ json_tree_lookup_by_path(&(root)->member, path, path_len); \
+ __tree_node != NULL ? json_tree_entry(__tree_node, type, member) : \
+ NULL; })
+
+/** Make lookup in tree by path_node and return entry. */
+#define json_tree_lookup_entry_by_path_node(root, path_node, path_node_hash, \
+ type, member) \
+({struct json_tree_node *__tree_node = \
+ json_tree_lookup_by_path_node(&(root)->member, path_node, \
+ path_node_hash); \
+ __tree_node != NULL ? json_tree_entry(__tree_node, type, member) : \
+ NULL; })
+
+/** Make pre-order traversal in JSON tree. */
+#define json_tree_foreach_pre(item, root) \
+for ((item) = json_tree_next_pre((root), NULL); (item) != NULL; \
+ (item) = json_tree_next_pre((root), (item)))
+
+/** Make post-order traversal in JSON tree. */
+#define json_tree_foreach_post(item, root) \
+for ((item) = json_tree_next_post((root), NULL); (item) != NULL; \
+ (item) = json_tree_next_post((root), (item)))
+
+/**
+ * Make safe post-order traversal in JSON tree.
+ * Safe for building destructors.
+ */
+#define json_tree_foreach_safe(item, root) \
+for (struct json_tree_node *__iter = json_tree_next_post((root), NULL); \
+ (((item) = __iter) && (__iter = json_tree_next_post((root), (item))), \
+ (item) != NULL);)
+
+/** Make post-order traversal in JSON tree and return entry. */
+#define json_tree_foreach_entry_pre(item, root, member) \
+for (struct json_tree_node *__iter = \
+ json_tree_next_pre(&(root)->member, NULL); \
+ __iter != NULL && ((item) = json_tree_entry(__iter, typeof(*(root)), \
+ member)); \
+ __iter = json_tree_next_pre(&(root)->member, __iter))
+
+/** Make pre-order traversal in JSON tree and return entry. */
+#define json_tree_foreach_entry_post(item, root, member) \
+for (struct json_tree_node *__iter = \
+ json_tree_next_post(&(root)->member, NULL); \
+ __iter != NULL && ((item) = json_tree_entry(__iter, typeof(*(root)), \
+ member)); \
+ __iter = json_tree_next_post(&(root)->member, __iter))
+
+/**
+ * Make secure post-order traversal in JSON tree and return entry.
+ */
+#define json_tree_foreach_entry_safe(item, root, member) \
+for (struct json_tree_node *__tmp_iter, *__iter = \
+ json_tree_next_post(NULL, &(root)->member); \
+ __iter != NULL && ((item) = json_tree_entry(__iter, typeof(*(root)), \
+ member)) && \
+ (__iter != NULL && (__tmp_iter = \
+ json_tree_next_post(&(root)->member, __iter))), \
+ (__iter != NULL && ((item) = json_tree_entry(__iter, typeof(*(root)), \
+ member))); \
+ __iter = __tmp_iter)
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* TARANTOOL_JSON_TREE_H_INCLUDED */
diff --git a/test/unit/json_path.c b/test/unit/json_path.c
index 1d7e7d3..9a1de06 100644
--- a/test/unit/json_path.c
+++ b/test/unit/json_path.c
@@ -1,7 +1,9 @@
#include "json/path.h"
+#include "json/tree.h"
#include "unit.h"
#include "trivia/util.h"
#include <string.h>
+#include <stdbool.h>
#define reset_to_new_path(value) \
path = value; \
@@ -159,14 +161,214 @@ test_errors()
footer();
}
+struct test_struct {
+ int value;
+ struct json_tree_node tree_node;
+};
+
+struct test_struct *
+test_add_path(struct test_struct *root, const char *path, uint32_t path_len,
+ struct test_struct *records_pool, int *pool_idx)
+{
+ int rc;
+ struct json_path_parser parser;
+ struct json_path_node path_node;
+ struct test_struct *parent = root;
+ json_path_parser_create(&parser, path, path_len);
+ while ((rc = json_path_next(&parser, &path_node)) == 0 &&
+ path_node.type != JSON_PATH_END) {
+ uint32_t path_node_hash = json_path_node_hash(&path_node);
+ struct test_struct *new_node =
+ json_tree_lookup_entry_by_path_node(parent, &path_node,
+ path_node_hash,
+ struct test_struct,
+ tree_node);
+ if (new_node == NULL) {
+ new_node = &records_pool[*pool_idx];
+ *pool_idx = *pool_idx + 1;
+ json_tree_node_create(&new_node->tree_node, &path_node,
+ path_node_hash);
+ rc = json_tree_add(&parent->tree_node,
+ &new_node->tree_node);
+ fail_if(rc != 0);
+ }
+ parent = new_node;
+ }
+ fail_if(rc != 0 || path_node.type != JSON_PATH_END);
+ return parent;
+}
+
+void
+test_tree()
+{
+ header();
+ plan(42);
+
+ struct test_struct records[6];
+ for (int i = 0; i < 6; i++)
+ records[i].value = i;
+ json_tree_node_create(&records[0].tree_node, NULL, 0);
+ fail_if(&records[0] != json_tree_entry(&records[0].tree_node,
+ struct test_struct, tree_node));
+
+ const char *path1 = "[1][10]";
+ const char *path2 = "[1][20].file";
+ const char *path3_to_remove = "[2]";
+ const char *path_unregistered = "[1][3]";
+
+ int records_idx = 1;
+ struct test_struct *node;
+ node = test_add_path(&records[0], path1, strlen(path1), records,
+ &records_idx);
+ is(node, &records[2], "add path '%s'", path1);
+
+ node = test_add_path(&records[0], path2, strlen(path2), records,
+ &records_idx);
+ is(node, &records[4], "add path '%s'", path2);
+
+ node = json_tree_lookup_entry_by_path(&records[0], path1, strlen(path1),
+ struct test_struct, tree_node);
+ is(node, &records[2], "lookup path '%s'", path1);
+
+ node = json_tree_lookup_entry_by_path(&records[0], path2, strlen(path2),
+ struct test_struct, tree_node);
+ is(node, &records[4], "lookup path '%s'", path2);
+
+ node = json_tree_lookup_entry_by_path(&records[0], path_unregistered,
+ strlen(path_unregistered),
+ struct test_struct, tree_node);
+ is(node, NULL, "lookup unregistered path '%s'", path_unregistered);
+
+ node = test_add_path(&records[0], path3_to_remove,
+ strlen(path3_to_remove), records, &records_idx);
+ is(node, &records[5], "add path to remove '%s'", path3_to_remove);
+ if (node != NULL) {
+ json_tree_remove(&records[0].tree_node, &node->tree_node);
+ json_tree_node_destroy(&node->tree_node);
+ } else {
+ isnt(node, NULL, "can't remove empty node!");
+ }
+
+ /* Test iterators. */
+ struct json_tree_node *tree_record = NULL;
+ const struct json_tree_node *tree_nodes_preorder[] =
+ {&records[0].tree_node, &records[1].tree_node,
+ &records[2].tree_node, &records[3].tree_node,
+ &records[4].tree_node};
+ int cnt = sizeof(tree_nodes_preorder)/sizeof(tree_nodes_preorder[0]);
+ int idx = 0;
+ json_tree_foreach_pre(tree_record, &records[0].tree_node) {
+ if (idx >= cnt)
+ break;
+ struct test_struct *t1 =
+ json_tree_entry(tree_record, struct test_struct,
+ tree_node);
+ struct test_struct *t2 =
+ json_tree_entry(tree_nodes_preorder[idx],
+ struct test_struct, tree_node);
+ is(tree_record, tree_nodes_preorder[idx],
+ "test foreach pre order %d: have %d expected %d",
+ idx, t1->value, t2->value);
+ ++idx;
+ }
+ is(idx, 5, "records iterated count %d of %d", idx, cnt);
+
+
+ const struct json_tree_node *tree_nodes_postorder[] =
+ {&records[2].tree_node, &records[4].tree_node, &records[3].tree_node,
+ &records[1].tree_node,
+ &records[0].tree_node};
+ cnt = sizeof(tree_nodes_postorder)/sizeof(tree_nodes_postorder[0]);
+ idx = 0;
+ json_tree_foreach_post(tree_record, &records[0].tree_node) {
+ if (idx >= cnt)
+ break;
+ struct test_struct *t1 =
+ json_tree_entry(tree_record, struct test_struct,
+ tree_node);
+ struct test_struct *t2 =
+ json_tree_entry(tree_nodes_postorder[idx],
+ struct test_struct, tree_node);
+ is(tree_record, tree_nodes_postorder[idx],
+ "test foreach post order %d: have %d expected of %d",
+ idx, t1->value, t2->value);
+ ++idx;
+ }
+ is(idx, 5, "records iterated count %d of %d", idx, cnt);
+
+ idx = 0;
+ json_tree_foreach_safe(tree_record, &records[0].tree_node) {
+ if (idx >= cnt)
+ break;
+ struct test_struct *t1 =
+ json_tree_entry(tree_record, struct test_struct,
+ tree_node);
+ struct test_struct *t2 =
+ json_tree_entry(tree_nodes_postorder[idx],
+ struct test_struct, tree_node);
+ is(tree_record, tree_nodes_postorder[idx],
+ "test foreach safe order %d: have %d expected of %d",
+ idx, t1->value, t2->value);
+ ++idx;
+ }
+ is(idx, 5, "records iterated count %d of %d", idx, cnt);
+
+ idx = 0;
+ json_tree_foreach_entry_pre(node, &records[0], tree_node) {
+ if (idx >= cnt)
+ break;
+ struct test_struct *t =
+ json_tree_entry(tree_nodes_preorder[idx],
+ struct test_struct, tree_node);
+ is(&node->tree_node, tree_nodes_preorder[idx],
+ "test foreach entry pre order %d: have %d expected of %d",
+ idx, node->value, t->value);
+ idx++;
+ }
+ is(idx, 5, "records iterated count %d of %d", idx, cnt);
+
+ idx = 0;
+ json_tree_foreach_entry_post(node, &records[0], tree_node) {
+ if (idx >= cnt)
+ break;
+ struct test_struct *t =
+ json_tree_entry(tree_nodes_postorder[idx],
+ struct test_struct, tree_node);
+ is(&node->tree_node, tree_nodes_postorder[idx],
+ "test foreach entry post order %d: have %d expected of %d",
+ idx, node->value, t->value);
+ idx++;
+ }
+ is(idx, 5, "records iterated count %d of %d", idx, cnt);
+
+ idx = 0;
+ json_tree_foreach_entry_safe(node, &records[0], tree_node) {
+ if (idx >= cnt)
+ break;
+ struct test_struct *t =
+ json_tree_entry(tree_nodes_postorder[idx],
+ struct test_struct, tree_node);
+ is(&node->tree_node, tree_nodes_postorder[idx],
+ "test foreach entry safe order %d: have %d expected of %d",
+ idx, node->value, t->value);
+ json_tree_node_destroy(&node->tree_node);
+ idx++;
+ }
+ is(idx, 5, "records iterated count %d of %d", idx, cnt);
+
+ check_plan();
+ footer();
+}
+
int
main()
{
header();
- plan(2);
+ plan(3);
test_basic();
test_errors();
+ test_tree();
int rc = check_plan();
footer();
diff --git a/test/unit/json_path.result b/test/unit/json_path.result
index a2a2f82..7bc9d37 100644
--- a/test/unit/json_path.result
+++ b/test/unit/json_path.result
@@ -1,5 +1,5 @@
*** main ***
-1..2
+1..3
*** test_basic ***
1..71
ok 1 - parse <[0]>
@@ -99,4 +99,50 @@ ok 1 - subtests
ok 20 - tab inside identifier
ok 2 - subtests
*** test_errors: done ***
+ *** test_tree ***
+ 1..42
+ ok 1 - add path '[1][10]'
+ ok 2 - add path '[1][20].file'
+ ok 3 - lookup path '[1][10]'
+ ok 4 - lookup path '[1][20].file'
+ ok 5 - lookup unregistered path '[1][3]'
+ ok 6 - add path to remove '[2]'
+ ok 7 - test foreach pre order 0: have 0 expected 0
+ ok 8 - test foreach pre order 1: have 1 expected 1
+ ok 9 - test foreach pre order 2: have 2 expected 2
+ ok 10 - test foreach pre order 3: have 3 expected 3
+ ok 11 - test foreach pre order 4: have 4 expected 4
+ ok 12 - records iterated count 5 of 5
+ ok 13 - test foreach post order 0: have 2 expected of 2
+ ok 14 - test foreach post order 1: have 4 expected of 4
+ ok 15 - test foreach post order 2: have 3 expected of 3
+ ok 16 - test foreach post order 3: have 1 expected of 1
+ ok 17 - test foreach post order 4: have 0 expected of 0
+ ok 18 - records iterated count 5 of 5
+ ok 19 - test foreach safe order 0: have 2 expected of 2
+ ok 20 - test foreach safe order 1: have 4 expected of 4
+ ok 21 - test foreach safe order 2: have 3 expected of 3
+ ok 22 - test foreach safe order 3: have 1 expected of 1
+ ok 23 - test foreach safe order 4: have 0 expected of 0
+ ok 24 - records iterated count 5 of 5
+ ok 25 - test foreach entry pre order 0: have 0 expected of 0
+ ok 26 - test foreach entry pre order 1: have 1 expected of 1
+ ok 27 - test foreach entry pre order 2: have 2 expected of 2
+ ok 28 - test foreach entry pre order 3: have 3 expected of 3
+ ok 29 - test foreach entry pre order 4: have 4 expected of 4
+ ok 30 - records iterated count 5 of 5
+ ok 31 - test foreach entry post order 0: have 2 expected of 2
+ ok 32 - test foreach entry post order 1: have 4 expected of 4
+ ok 33 - test foreach entry post order 2: have 3 expected of 3
+ ok 34 - test foreach entry post order 3: have 1 expected of 1
+ ok 35 - test foreach entry post order 4: have 0 expected of 0
+ ok 36 - records iterated count 5 of 5
+ ok 37 - test foreach entry safe order 0: have 2 expected of 2
+ ok 38 - test foreach entry safe order 1: have 4 expected of 4
+ ok 39 - test foreach entry safe order 2: have 3 expected of 3
+ ok 40 - test foreach entry safe order 3: have 1 expected of 1
+ ok 41 - test foreach entry safe order 4: have 0 expected of 0
+ ok 42 - records iterated count 5 of 5
+ok 3 - subtests
+ *** test_tree: done ***
*** main: done ***
--
2.7.4
More information about the Tarantool-patches
mailing list