[PATCH v1 1/1] lib: implement JSON tree class for json library
Kirill Shcherbatov
kshcherbatov at tarantool.org
Mon Oct 1 15:27:02 MSK 2018
New JSON tree class would store JSON paths for tuple fields
for registered non-plain indexes.
Part of #1012.
---
Branch: http://github.com/tarantool/tarantool/tree/kshch/gh-1012-json-tree-class
Issue: https://github.com/tarantool/tarantool/issues/1012
src/lib/json/CMakeLists.txt | 2 +
src/lib/json/tree.c | 272 ++++++++++++++++++++++++++++++++++++++++++++
src/lib/json/tree.h | 207 +++++++++++++++++++++++++++++++++
test/unit/json_path.c | 210 +++++++++++++++++++++++++++++++++-
4 files changed, 690 insertions(+), 1 deletion(-)
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..9702b79 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 salad small)
diff --git a/src/lib/json/tree.c b/src/lib/json/tree.c
new file mode 100644
index 0000000..a393d5b
--- /dev/null
+++ b/src/lib/json/tree.c
@@ -0,0 +1,272 @@
+
+/*
+ * 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 <unicode/uchar.h>
+#include <unicode/utf8.h>
+
+#include "tree.h"
+#include "path.h"
+#include "third_party/PMurHash.h"
+
+/** Hash record representing json_tree_node. */
+struct mh_json_tree_node {
+ struct json_path_node key;
+ uint32_t key_hash;
+ struct json_tree_node *node;
+};
+
+/**
+ * Compare json_tree_node hash bindings @a and @b.
+ * @param a Hash record to compare.
+ * @param b Hash record to compare.
+ * @retval 0 On equal, not 0 otherwise.
+ */
+bool
+mh_json_tree_node_cmp(const struct mh_json_tree_node *a,
+ const struct mh_json_tree_node *b)
+{
+ return (a->key.type != b->key.type) ||
+ ((a->key.type != JSON_PATH_STR ||
+ a->key.len != b->key.len ||
+ memcmp(a->key.str, b->key.str,
+ a->key.len) != 0) &&
+ (a->key.type != JSON_PATH_NUM ||
+ a->key_hash != b->key_hash));
+}
+
+/** Define tree record hashtable. */
+#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;
+ uint8_t *data;
+ uint32_t data_size;
+ if (key->type == JSON_PATH_STR) {
+ data = (uint8_t *)key->str;
+ data_size = key->len;
+ } else if (key->type == JSON_PATH_NUM) {
+ data = (uint8_t *)&key->num;
+ data_size = sizeof(key->num);
+ } else {
+ assert(0);
+ }
+ PMurHash32_Process(&h, &carry, data, data_size);
+ return PMurHash32_Result(h, carry, data_size);
+}
+
+int
+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));
+ node->children_ht = mh_json_tree_node_new();
+ if (node->children_ht == NULL)
+ return -1;
+ if (path_node != NULL) {
+ memcpy(&node->key, path_node, sizeof(struct json_path_node));
+ node->key_hash = path_node_hash;
+ } else {
+ node->key.type = JSON_PATH_END;
+ }
+ rlist_create(&node->siblings);
+ rlist_create(&node->children);
+ return 0;
+}
+
+void
+json_tree_node_destroy(struct json_tree_node *node)
+{
+ mh_json_tree_node_delete(node->children_ht);
+}
+
+struct json_tree_node *
+json_tree_lookup(struct json_tree_node *root, struct json_path_node *path_node,
+ uint32_t path_node_hash)
+{
+ struct mh_json_tree_node info;
+ memcpy(&info.key, path_node, sizeof(struct json_path_node));
+ info.key_hash = path_node_hash;
+ mh_int_t id = mh_json_tree_node_find(root->children_ht, &info, NULL);
+ if (id == mh_end(root->children_ht))
+ return NULL;
+ struct mh_json_tree_node *ht_node =
+ mh_json_tree_node_node(root->children_ht, 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 == root);
+ return ret;
+}
+
+int
+json_tree_add(struct json_tree_node *root, struct json_tree_node *node)
+{
+ assert(node->parent == NULL);
+ assert(json_tree_lookup(root, &node->key, node->key_hash) == NULL);
+ struct mh_json_tree_node ht_node;
+ memcpy(&ht_node.key, &node->key, sizeof(struct json_path_node));
+ ht_node.key_hash = node->key_hash;
+ ht_node.node = node;
+ mh_int_t rc = mh_json_tree_node_put(root->children_ht, &ht_node, NULL,
+ NULL);
+ if (rc == mh_end(node->children_ht))
+ return -1;
+ node->parent = root;
+ rlist_add(&root->children, &node->siblings);
+ return 0;
+}
+
+void
+json_tree_remove(struct json_tree_node *root, struct json_tree_node *node)
+{
+ assert(node->parent == root);
+ assert(json_tree_lookup(root, &node->key, node->key_hash) == node);
+ rlist_del_entry(node, siblings);
+ struct mh_json_tree_node info;
+ memcpy(&info.key, &node->key,
+ sizeof(struct json_path_node));
+ info.key_hash = node->key_hash;
+ mh_int_t id = mh_json_tree_node_find(root->children_ht, &info, NULL);
+ assert(id != mh_end(root->children_ht));
+ mh_json_tree_node_del(root->children_ht, id, NULL);
+ assert(json_tree_lookup(root, &node->key, node->key_hash) == NULL);
+}
+
+struct json_tree_node *
+json_tree_lookup_path(struct json_tree_node *root, const char *path,
+ uint32_t path_len)
+{
+ int rc;
+ struct json_path_parser parser;
+ struct json_path_node path_node;
+ json_path_parser_create(&parser, path, path_len);
+ while ((rc = json_path_next(&parser, &path_node)) == 0 &&
+ path_node.type != JSON_PATH_END && root != NULL) {
+ uint32_t path_node_hash = json_path_node_hash(&path_node);
+ struct json_tree_node *node =
+ json_tree_lookup(root, &path_node, path_node_hash);
+ assert(node == NULL || node->parent == root);
+ root = node;
+ }
+ if (rc != 0 || path_node.type != JSON_PATH_END)
+ return NULL;
+ return root;
+}
+
+/**
+ * Get JSON tree node next child.
+ * @param pos JSON tree node iterator.
+ * @param parent Parent of @pos record.
+ * @retval not NULL pointer to next item if exists.
+ */
+static struct json_tree_node *
+json_tree_next_child(struct json_tree_node *pos,
+ struct json_tree_node *parent)
+{
+ struct json_tree_node *next;
+ if (pos == NULL) {
+ next = rlist_first_entry(&parent->children,
+ struct json_tree_node, siblings);
+ } else {
+ next = rlist_next_entry(pos, siblings);
+ }
+ if (&next->siblings != &parent->children)
+ return next;
+ return NULL;
+}
+
+/**
+ * Find leftmost child rellative for iterator @pos.
+ * @param pos JSON tree node iterator.
+ * @retval not NULL pointer to next item if exists.
+ */
+static struct json_tree_node *
+json_tree_leftmost_descendant(struct json_tree_node *pos)
+{
+ struct json_tree_node *last;
+ do {
+ last = pos;
+ pos = json_tree_next_child(NULL, pos);
+ } while (pos);
+ return last;
+}
+
+struct json_tree_node *
+json_tree_preorder_next(struct json_tree_node *pos, struct json_tree_node *root)
+{
+ if (pos == NULL)
+ return root;
+ struct json_tree_node *next = json_tree_next_child(NULL, pos);
+ if (next != NULL)
+ return next;
+ while (pos != root) {
+ next = json_tree_next_child(pos, pos->parent);
+ if (next != NULL)
+ return next;
+ pos = pos->parent;
+ }
+ return NULL;
+}
+
+struct json_tree_node *
+json_tree_postorder_next(struct json_tree_node *pos,
+ struct json_tree_node *root)
+{
+ struct json_tree_node *next;
+ if (pos == NULL)
+ return json_tree_leftmost_descendant(root);
+ if (pos == root)
+ return NULL;
+ next = json_tree_next_child(pos, pos->parent);
+ if (next != NULL)
+ return json_tree_leftmost_descendant(next);
+ return pos->parent;
+}
diff --git a/src/lib/json/tree.h b/src/lib/json/tree.h
new file mode 100644
index 0000000..aa77b51
--- /dev/null
+++ b/src/lib/json/tree.h
@@ -0,0 +1,207 @@
+#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 <stdint.h>
+#include "small/rlist.h"
+#include "path.h"
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif
+
+/** JSON path tree hash structure. */
+struct mh_json_tree_node_t;
+
+/** JSON path tree record structure. */
+struct json_tree_node {
+ /** JSON parser node path. */
+ struct json_path_node key;
+ /** Hash calculated for key field. */
+ uint32_t key_hash;
+ /** Childs hashtable: json_path_node -> json_tree_node. */
+ struct mh_json_tree_node_t *children_ht;
+ /** Siblings nodes list. */
+ struct rlist siblings;
+ /** Child nodes list. */
+ struct rlist children;
+ /** Pointer to parent json_tree_node record. */
+ struct json_tree_node *parent;
+};
+
+/**
+ * Calculate json_path_node hash.
+ * @param key JSON parser node to calculate hash.
+ * @retval Hash value.
+ */
+uint32_t
+json_path_node_hash(struct json_path_node *key);
+
+/**
+ * Init JSON tree node.
+ * @param node JSON tree node to initialize.
+ * @param path_node Source JSON parser node to use on initialize.
+ * @param path_node_hash Hash of @path_node.
+ * @retval 0 On success, -1 otherwise.
+ */
+int
+json_tree_node_create(struct json_tree_node *node,
+ struct json_path_node *path_node,
+ uint32_t path_node_hash);
+
+/**
+ * Destroy JSON tree node.
+ * @param node JSON tree node to destruct.
+ * @retval 0 On success, -1 on error.
+ */
+void
+json_tree_node_destroy(struct json_tree_node *node);
+
+/**
+ * Lookup record with data @path_node having hash @path_node_hash
+ * in JSON tree @node childs.
+ * @param node JSON tree root node.
+ * @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.
+ */
+struct json_tree_node *
+json_tree_lookup(struct json_tree_node *root,
+ struct json_path_node *path_node,
+ uint32_t path_node_hash);
+
+/**
+ * Append JSON tree node @node to @root. Root JSON tree node @root
+ * shouldn't have childs with same content.
+ * @param root JSON tree root 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 *root,
+ struct json_tree_node *node);
+
+/**
+ * Detach JSON tree node @node by @root. Root JSON tree node @root
+ * should have such child.
+ * @param root JSON tree root node.
+ * @param node JSON tree node to add.
+ */
+void
+json_tree_remove(struct json_tree_node *root,
+ struct json_tree_node *node);
+
+/**
+ * Lookup JSON path @path having length @path_len in JSON
+ * tree @root.
+ * @param root JSON tree root 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_path(struct json_tree_node *root,
+ const char *path, uint32_t path_len);
+
+/**
+ * Make pre order traversal iterator @pos step.
+ * @param pos Iterator pointer, NULL for initialization.
+ * @param root The JSON path tree to walk root.
+ * @retval not NULL pointer to next node. NULL if nothing found.
+ */
+struct json_tree_node *
+json_tree_preorder_next(struct json_tree_node *pos,
+ struct json_tree_node *root);
+
+/**
+ * Make post order traversal iterator @pos step.
+ * @param pos Iterator pointer, NULL for initialization.
+ * @param root The JSON path tree to walk root.
+ * @retval not NULL pointer to next node. NULL if nothing found.
+ */
+struct json_tree_node *
+json_tree_postorder_next(struct json_tree_node *pos,
+ struct json_tree_node *root);
+
+
+/**
+ * Define macros to operate with containers.
+ */
+
+/** Return entry by json_tree_node item. */
+#define json_tree_node_entry(item, type, member) ({ \
+ const typeof( ((type *)0)->member ) *__mptr = (item); \
+ (type *)( (char *)__mptr - ((size_t) &((type *)0)->member) ); })
+
+/** Make lookup in tree by path and return entry on found. */
+#define json_tree_lookup_path_entry(root, path, path_len, type, member) \
+({struct json_tree_node *__tree_node = \
+ json_tree_lookup_path(&(root)->member, path, path_len); \
+ __tree_node != NULL ? json_tree_node_entry(__tree_node, type, member) : \
+ NULL; })
+
+/** Make lookup in tree by path_node and return entry on found. */
+#define json_tree_lookup_entry(root, path_node, path_node_hash, type, member)\
+({struct json_tree_node *__tree_node = \
+ json_tree_lookup(&(root)->member, path_node, path_node_hash); \
+ __tree_node != NULL ? json_tree_node_entry(__tree_node, type, member) : \
+ NULL; })
+
+/** Make traversal in JSON tree. */
+#define json_tree_foreach_entry(order, item, root, member) \
+for (struct json_tree_node *__iter = \
+ json_tree_##order##_next(NULL, &(root)->member); \
+ __iter != NULL && (item = json_tree_node_entry(__iter, typeof(*root), \
+ member)); \
+ __iter = json_tree_##order##_next(__iter, &(root)->member))
+
+/**
+ * Make secure traversal in JSON tree that works even on
+ * destruction under iterator.
+ */
+#define json_tree_foreach_entry_safe(order, item, root, member) \
+for (struct json_tree_node *__tmp_iter, *__iter = \
+ json_tree_##order##_next(NULL, &(root)->member); \
+ __iter != NULL && ((item) = json_tree_node_entry(__iter, typeof(*root), \
+ member)) && \
+ (__iter != NULL && (__tmp_iter = \
+ json_tree_##order##_next(__iter, \
+ &(root)->member))), \
+ (__iter != NULL && ((item) = json_tree_node_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..fb16162 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,220 @@ test_errors()
footer();
}
+enum tuple_field_type {
+ TUPLE_FIELD_TYPE_ANY,
+ TUPLE_FIELD_TYPE_MAP,
+ TUPLE_FIELD_TYPE_ARRAY,
+ TUPLE_FIELD_TYPE_OTHER,
+};
+
+const char *field_type_strs[] = {
+ /** TUPLE_FIELD_TYPE_ANY */ "any",
+ /** TUPLE_FIELD_TYPE_MAP */ "map",
+ /** TUPLE_FIELD_TYPE_ARRAY */ "array",
+ /** TUPLE_FIELD_TYPE_OTHER */ "other"
+};
+
+struct tuple_field {
+ enum tuple_field_type type;
+ struct json_tree_node tree_node;
+};
+
+static inline enum tuple_field_type
+tuple_field_by_leaf_node_type(enum json_path_type path_type)
+{
+ if (path_type == JSON_PATH_STR)
+ return TUPLE_FIELD_TYPE_MAP;
+ if (path_type == JSON_PATH_NUM)
+ return TUPLE_FIELD_TYPE_ARRAY;
+ return TUPLE_FIELD_TYPE_OTHER;
+}
+
+struct tuple_field *
+tuple_field_new(struct json_path_node *node, uint32_t node_hash)
+{
+ struct tuple_field *ret = calloc(1, sizeof(struct tuple_field));
+ assert(ret != NULL);
+ if (json_tree_node_create(&ret->tree_node, node, node_hash) != 0) {
+ free(ret);
+ return NULL;
+ }
+ ret->type = TUPLE_FIELD_TYPE_ANY;
+ return ret;
+}
+
+void
+tuple_field_delete(struct tuple_field *field)
+{
+ json_tree_node_destroy(&field->tree_node);
+ free(field);
+}
+
+int
+tuple_field_add_path(struct tuple_field *root, const char *path,
+ uint32_t path_len, struct tuple_field **leaf)
+{
+ int rc;
+ struct json_path_parser parser;
+ struct json_path_node path_node;
+ struct tuple_field *field = root;
+ json_path_parser_create(&parser, path, path_len);
+ while ((rc = json_path_next(&parser, &path_node)) == 0 &&
+ path_node.type != JSON_PATH_END) {
+ enum tuple_field_type type =
+ tuple_field_by_leaf_node_type(path_node.type);
+ if (field->type != TUPLE_FIELD_TYPE_ANY && field->type != type)
+ return -1;
+ uint32_t path_node_hash = json_path_node_hash(&path_node);
+ struct tuple_field *new_field =
+ json_tree_lookup_entry(field, &path_node,
+ path_node_hash,
+ struct tuple_field, tree_node);
+ if (new_field == NULL) {
+ new_field =
+ tuple_field_new(&path_node, path_node_hash);
+ assert(new_field != NULL);
+ rc = json_tree_node_create(&new_field->tree_node,
+ &path_node, path_node_hash);
+ assert(rc == 0);
+ rc = json_tree_add(&field->tree_node,
+ &new_field->tree_node);
+ assert(rc == 0);
+ assert(memcmp(&path_node, &new_field->tree_node.key,
+ sizeof(path_node)) == 0);
+ assert(json_tree_lookup_entry(field, &path_node,
+ path_node_hash,
+ struct tuple_field,
+ tree_node) != NULL);
+ }
+ field->type = type;
+ field = new_field;
+ }
+ assert(rc == 0 && path_node.type == JSON_PATH_END);
+ *leaf = field;
+ return 0;
+}
+
+void
+test_tree()
+{
+ header();
+ plan(19);
+
+ struct tuple_field *root_field = tuple_field_new(NULL, 0);
+ assert(root_field != NULL);
+
+ /* Add paths to tree. */
+ int rc = 0;
+ struct tuple_field *node;
+ const char *path1 = "[1][10]";
+ const char *path2 = "[1].aaa";
+ const char *path3 = "[1][100]";
+ const char *path4 = "[1][100].a";
+ const char *path5 = "[1000].map";
+ rc = tuple_field_add_path(root_field, path1, strlen(path1), &node);
+ is(rc, 0, "add valid path '%s' - normal ret", path1);
+ isnt(node, NULL, "add valid path '%s' - not NULL pointer", path1);
+ node->type = TUPLE_FIELD_TYPE_OTHER;
+
+ rc = tuple_field_add_path(root_field, path2, strlen(path2), &node);
+ isnt(rc, 0, "add path with conflicting interm. node '%s' - error ret",
+ path2);
+ assert(rc != 0);
+
+ rc = tuple_field_add_path(root_field, path3, strlen(path3), &node);
+ is(rc, 0, "add valid path '%s' - normal ret", path3);
+ isnt(node, NULL, "add valid path '%s' - not NULL pointer", path3);
+ node->type = TUPLE_FIELD_TYPE_OTHER;
+
+ rc = tuple_field_add_path(root_field, path4, strlen(path4), &node);
+ isnt(rc, 0, "add path with conflicting leaf node '%s' - error ret",
+ path4);
+
+ rc = tuple_field_add_path(root_field, path5, strlen(path5), &node);
+ is(rc, 0, "add path with map container '%s' - normal ret", path5);
+ isnt(node, NULL, "add path with map container '%s' - not NULL pointer",
+ path5);
+ node->type = TUPLE_FIELD_TYPE_OTHER;
+
+ /* Test registered paths. */
+ node = json_tree_lookup_path_entry(root_field, path2, strlen(path2),
+ struct tuple_field, tree_node);
+ is(node, NULL, "lookup by unregistered path '%s'", path2);
+
+ node = json_tree_lookup_path_entry(root_field, path1, strlen(path1),
+ struct tuple_field, tree_node);
+ isnt(node, NULL, "lookup by registered path '%s'", path1);
+ /* Iterate over tree. */
+ int sum = 0;
+ struct tuple_field *field;
+ json_tree_foreach_entry(preorder, field, root_field, tree_node) {
+ if (field->tree_node.key.type == JSON_PATH_NUM)
+ sum += field->tree_node.key.num;
+ }
+ is(sum, 1111, "iterate over the tree and calculate sum");
+ if (node != NULL) {
+ json_tree_remove(node->tree_node.parent, &node->tree_node);
+ tuple_field_delete(node);
+ node = json_tree_lookup_path_entry(root_field, path1, strlen(path1),
+ struct tuple_field, tree_node);
+ is(node, NULL, "lookup after registered path '%s' deletion",
+ path1);
+ }
+ sum = 0;
+ json_tree_foreach_entry(postorder, field, root_field, tree_node) {
+ if (field->tree_node.key.type == JSON_PATH_NUM)
+ sum += field->tree_node.key.num;
+ }
+ is(sum, 1101, "iterate over the tree and calculate sum after leaf "
+ "deletion");
+
+ /* Destroy tree. */
+ /**
+ * [1]
+ * |
+ * [ ... 10 ... 100 ... 1000]
+ * | | |
+ * * # {"map"}
+ * |
+ * *
+ *
+ * Item marked with # should be already deleted.
+ */
+ enum tuple_field_type destruction_order[] =
+ {TUPLE_FIELD_TYPE_OTHER, TUPLE_FIELD_TYPE_MAP,
+ TUPLE_FIELD_TYPE_OTHER, TUPLE_FIELD_TYPE_ARRAY,
+ TUPLE_FIELD_TYPE_ARRAY};
+ int destruction_order_size =
+ sizeof(destruction_order)/sizeof(destruction_order[0]);
+ int idx = 0;
+ json_tree_foreach_entry_safe(postorder, field, root_field, tree_node) {
+ if (idx > destruction_order_size)
+ break;
+ is(field->type, destruction_order[idx],
+ "destruct valid order - delete record %s, expected %s",
+ field_type_strs[field->type],
+ field_type_strs[destruction_order[idx]]);
+ tuple_field_delete(field);
+ idx++;
+ }
+ is(idx, destruction_order_size,
+ "valid count of destructed items - have %d, expected %d",
+ idx, destruction_order_size);
+
+ check_plan();
+ footer();
+}
+
int
main()
{
header();
- plan(2);
+ plan(3);
test_basic();
test_errors();
+ test_tree();
int rc = check_plan();
footer();
--
2.7.4
More information about the Tarantool-patches
mailing list