[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