[PATCH v5 05/12] lib: implement JSON tree class for json library

[Kirill Shcherbatov <kshcherbatov@tarantool.org>]

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         | 327 ++++++++++++++++++++++++++++++++++++++++++++
 src/lib/json/tree.h         | 224 ++++++++++++++++++++++++++++++
 test/unit/json_path.c       | 211 +++++++++++++++++++++++++++-
 test/unit/json_path.result  |  42 +++++-
 5 files changed, 804 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..e40c7ac
--- /dev/null
+++ b/src/lib/json/tree.c
@@ -0,0 +1,327 @@
+
+/*
+ * 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 *parent;
+	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->parent != b->parent)
+		return a->parent - b->parent;
+	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 seed)
+{
+	uint32_t h = 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);
+}
+
+int
+json_tree_create(struct json_tree *tree)
+{
+	memset(tree, 0, sizeof(struct json_tree));
+	tree->root.rolling_hash = json_path_node_hash_seed;
+	tree->root.key.type = JSON_PATH_END;
+	tree->hash = mh_json_tree_node_new();
+	if (unlikely(tree->hash == NULL))
+		return -1;
+	return 0;
+}
+
+void
+json_tree_destroy(struct json_tree *tree)
+{
+	assert(tree->hash != NULL);
+	json_tree_node_destroy(&tree->root);
+	mh_json_tree_node_delete(tree->hash);
+}
+
+void
+json_tree_node_create(struct json_tree_node *node,
+		      struct json_path_node *path_node)
+{
+	memset(node, 0, sizeof(struct json_tree_node));
+	node->key = *path_node;
+}
+
+void
+json_tree_node_destroy(struct json_tree_node *node)
+{
+	free(node->children);
+}
+
+struct json_tree_node *
+json_tree_lookup_by_path_node(struct json_tree *tree,
+			      struct json_tree_node *parent,
+			      struct json_path_node *path_node,
+			      uint32_t rolling_hash)
+{
+	assert(parent != NULL);
+	assert(rolling_hash == json_path_node_hash(path_node,
+						   parent->rolling_hash));
+	struct mh_json_tree_node info;
+	info.key = *path_node;
+	info.key_hash = rolling_hash;
+	info.parent = parent;
+	mh_int_t id = mh_json_tree_node_find(tree->hash, &info, NULL);
+	if (unlikely(id == mh_end(tree->hash)))
+		return NULL;
+	struct mh_json_tree_node *ht_node =
+		mh_json_tree_node_node(tree->hash, 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 *tree, struct json_tree_node *parent,
+	      struct json_tree_node *node, uint32_t rolling_hash)
+{
+	assert(parent != NULL);
+	assert(node->parent == NULL);
+	assert(rolling_hash ==
+	       json_path_node_hash(&node->key, parent->rolling_hash));
+	assert(json_tree_lookup_by_path_node(tree, parent, &node->key,
+					     rolling_hash) == NULL);
+	uint32_t insert_idx = (node->key.type == JSON_PATH_NUM) ?
+			      (uint32_t)node->key.num - 1 :
+			      parent->children_count;
+	if (insert_idx >= parent->children_count) {
+		uint32_t new_size = insert_idx + 1;
+		struct json_tree_node **children =
+			realloc(parent->children, new_size*sizeof(void *));
+		if (unlikely(children == NULL))
+			return -1;
+		memset(children + parent->children_count, 0,
+		       (new_size - parent->children_count)*sizeof(void *));
+		parent->children = children;
+		parent->children_count = new_size;
+	}
+	assert(parent->children[insert_idx] == NULL);
+	parent->children[insert_idx] = node;
+	node->sibling_idx = insert_idx;
+	node->rolling_hash = rolling_hash;
+
+	struct mh_json_tree_node ht_node;
+	ht_node.key = node->key;
+	ht_node.key_hash = rolling_hash;
+	ht_node.node = node;
+	ht_node.parent = parent;
+	mh_int_t rc = mh_json_tree_node_put(tree->hash, &ht_node, NULL, NULL);
+	if (unlikely(rc == mh_end(tree->hash))) {
+		parent->children[insert_idx] = NULL;
+		return -1;
+	}
+	node->parent = parent;
+	assert(json_tree_lookup_by_path_node(tree, parent, &node->key,
+					     rolling_hash) == node);
+	return 0;
+}
+
+void
+json_tree_remove(struct json_tree *tree, struct json_tree_node *parent,
+		 struct json_tree_node *node, uint32_t rolling_hash)
+{
+	assert(parent != NULL);
+	assert(node->parent == parent);
+	assert(json_tree_lookup_by_path_node(tree, parent, &node->key,
+					     rolling_hash) == node);
+	struct json_tree_node **child_slot = NULL;
+	if (node->key.type == JSON_PATH_NUM) {
+		child_slot = &parent->children[node->key.num - 1];
+	} else {
+		uint32_t idx = 0;
+		while (idx < parent->children_count &&
+		       parent->children[idx] != node)
+			child_slot = &parent->children[idx++];
+	}
+	assert(child_slot != NULL && *child_slot == node);
+	*child_slot = NULL;
+
+	struct mh_json_tree_node info;
+	info.key = node->key;
+	info.key_hash = rolling_hash;
+	info.parent = parent;
+	mh_int_t id = mh_json_tree_node_find(tree->hash, &info, NULL);
+	assert(id != mh_end(tree->hash));
+	mh_json_tree_node_del(tree->hash, id, NULL);
+	assert(json_tree_lookup_by_path_node(tree, parent, &node->key,
+					     rolling_hash) == NULL);
+}
+
+struct json_tree_node *
+json_tree_lookup_by_path(struct json_tree *tree, struct json_tree_node *parent,
+			 const char *path, uint32_t path_len)
+{
+	int rc;
+	struct json_path_parser parser;
+	struct json_path_node path_node;
+	struct json_tree_node *ret = parent;
+	uint32_t rolling_hash = ret->rolling_hash;
+	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) {
+		rolling_hash = json_path_node_hash(&path_node, rolling_hash);
+		ret = json_tree_lookup_by_path_node(tree, ret, &path_node,
+						    rolling_hash);
+	}
+	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)
+{
+	assert(pos == NULL || pos->parent == parent);
+	struct json_tree_node **arr = parent->children;
+	uint32_t arr_size = parent->children_count;
+	if (arr == NULL)
+		return NULL;
+	uint32_t idx = pos != NULL ? pos->sibling_idx + 1 : 0;
+	while (idx < arr_size && arr[idx] == NULL)
+		idx++;
+	if (idx >= arr_size)
+		return NULL;
+	return arr[idx];
+}
+
+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)
+		pos = 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) {
+		next = json_tree_leftmost(parent);
+		return next != parent ? next : NULL;
+	}
+	if (pos == parent)
+		return NULL;
+	next = json_tree_next_child(pos->parent, pos);
+	if (next != NULL) {
+		next = json_tree_leftmost(next);
+		return next != parent ? next : NULL;
+	}
+	return pos->parent != parent ? pos->parent : NULL;
+}
diff --git a/src/lib/json/tree.h b/src/lib/json/tree.h
new file mode 100644
index 0000000..6166024
--- /dev/null
+++ b/src/lib/json/tree.h
@@ -0,0 +1,224 @@
+#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"
+#include <stdio.h>
+#include <inttypes.h>
+#include <stdint.h>
+#include <stdlib.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. Key record point to source strings
+ * memory.
+ */
+struct json_tree_node {
+	/** JSON path node produced by json_next_token. */
+	struct json_path_node key;
+	/**
+	 * Rolling hash for node calculated with
+	 * json_path_node_hash(key, parent).
+	 */
+	uint32_t rolling_hash;
+	/** Array of child records. Match indexes. */
+	struct json_tree_node **children;
+	/** Size of children array. */
+	uint32_t children_count;
+	/** Index of node in parent children array. */
+	uint32_t sibling_idx;
+	/** Pointer to parent node. */
+	struct json_tree_node *parent;
+};
+
+/** JSON tree object managing data relations. */
+struct json_tree {
+	/** JSON tree root node. */
+	struct json_tree_node root;
+	/** Hashtable af all tree nodes. */
+	struct mh_json_tree_node_t *hash;
+};
+
+/** Create a JSON tree object to manage data relations. */
+int
+json_tree_create(struct json_tree *tree);
+
+/**
+ * Destroy JSON tree object. This routine doesn't  subtree so
+ * should be called at the end of it's manual destruction.
+ */
+void
+json_tree_destroy(struct json_tree *tree);
+
+/** Compute the hash value of a JSON path component. */
+uint32_t
+json_path_node_hash(struct json_path_node *key, uint32_t seed);
+
+/** Init a JSON tree node. */
+void
+json_tree_node_create(struct json_tree_node *node,
+		      struct json_path_node *path_node);
+
+/** Destroy a JSON tree node. */
+void
+json_tree_node_destroy(struct json_tree_node *node);
+
+/**
+ * Make child lookup in tree by path_node at position specified
+ * with parent. Rolling hash should be calculated for path_node
+ * and parent with json_path_node_hash.
+ */
+struct json_tree_node *
+json_tree_lookup_by_path_node(struct json_tree *tree,
+			      struct json_tree_node *parent,
+			      struct json_path_node *path_node,
+			      uint32_t rolling_hash);
+
+/**
+ * Append node to the given parent position in JSON tree. The
+ * parent mustn't have a child with such content. Rolling
+ * hash should be calculated for path_node and parent with
+ * json_path_node_hash.
+ */
+int
+json_tree_add(struct json_tree *tree, struct json_tree_node *parent,
+	      struct json_tree_node *node, uint32_t rolling_hash);
+
+/**
+ * Delete a JSON tree node at the given parent position in JSON
+ * tree. The parent node must have such child. Rolling hash should
+ * be calculated for path_node and parent with
+ * json_path_node_hash.
+ */
+void
+json_tree_remove(struct json_tree *tree, struct json_tree_node *parent,
+		 struct json_tree_node *node, uint32_t rolling_hash);
+
+/** Make child lookup by path in JSON tree. */
+struct json_tree_node *
+json_tree_lookup_by_path(struct json_tree *tree, struct json_tree_node *parent,
+			 const char *path, uint32_t path_len);
+
+/** Make pre order traversal in JSON tree. */
+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. */
+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(tree, parent, path, path_len, type,   \
+				       member)				     \
+({struct json_tree_node *__tree_node =					     \
+	json_tree_lookup_by_path((tree), (parent), 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(tree, parent, path_node,	     \
+					    path_node_hash, type, member)    \
+({struct json_tree_node *__tree_node =					     \
+	json_tree_lookup_by_path_node((tree), (parent), 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, type, member)		     \
+for (struct json_tree_node *__iter =					     \
+     json_tree_next_pre((root), NULL);					     \
+     __iter != NULL && ((item) = json_tree_entry(__iter, type, member));     \
+     __iter = json_tree_next_pre((root), __iter))
+
+/** Make pre-order traversal in JSON tree and return entry. */
+#define json_tree_foreach_entry_post(item, root, type, member)		     \
+for (struct json_tree_node *__iter =					     \
+     json_tree_next_post((root), NULL		);			     \
+     __iter != NULL && ((item) = json_tree_entry(__iter, type, member));     \
+     __iter = json_tree_next_post((root), __iter))
+
+/**
+ * Make secure post-order traversal in JSON tree and return entry.
+ */
+#define json_tree_foreach_entry_safe(item, root, type, member)		     \
+for (struct json_tree_node *__tmp_iter, *__iter =			     \
+     json_tree_next_post((root), NULL);					     \
+     __iter != NULL && ((item) = json_tree_entry(__iter, type, member)) &&   \
+     (__iter != NULL && (__tmp_iter =					     \
+			 json_tree_next_post((root), __iter))),		     \
+     (__iter != NULL && ((item) = json_tree_entry(__iter, type, 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..75ca11b 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,221 @@ test_errors()
 	footer();
 }
 
+struct test_struct {
+	int value;
+	struct json_tree_node tree_node;
+};
+
+struct test_struct *
+test_add_path(struct json_tree *tree, 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 json_tree_node *parent = &tree->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 rolling_hash =
+			json_path_node_hash(&path_node, parent->rolling_hash);
+		struct json_tree_node *new_node =
+			json_tree_lookup_by_path_node(tree, parent, &path_node,
+						      rolling_hash);
+		if (new_node == NULL) {
+			new_node = &records_pool[*pool_idx].tree_node;
+			*pool_idx = *pool_idx + 1;
+			json_tree_node_create(new_node, &path_node);
+			rc = json_tree_add(tree, parent, new_node,
+					   rolling_hash);
+			fail_if(rc != 0);
+		}
+		parent = new_node;
+	}
+	fail_if(rc != 0 || path_node.type != JSON_PATH_END);
+	return json_tree_entry_safe(parent, struct test_struct, tree_node);
+}
+
+void
+test_tree()
+{
+	header();
+	plan(36);
+
+	struct json_tree tree;
+	int rc = json_tree_create(&tree);
+	fail_if(rc != 0);
+
+	struct test_struct records[6];
+	for (int i = 0; i < 6; i++)
+		records[i].value = i;
+
+	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(&tree, path1, strlen(path1), records,
+			     &records_idx);
+	is(node, &records[2], "add path '%s'", path1);
+
+	node = test_add_path(&tree, path2, strlen(path2), records,
+			     &records_idx);
+	is(node, &records[4], "add path '%s'", path2);
+
+	node = json_tree_lookup_entry_by_path(&tree, &tree.root, path1,
+					      strlen(path1), struct test_struct,
+					      tree_node);
+	is(node, &records[2], "lookup path '%s'", path1);
+
+	node = json_tree_lookup_entry_by_path(&tree, &tree.root, path2,
+					      strlen(path2), struct test_struct,
+					      tree_node);
+	is(node, &records[4], "lookup path '%s'", path2);
+
+	node = json_tree_lookup_entry_by_path(&tree, &tree.root,
+					      path_unregistered,
+					      strlen(path_unregistered),
+					      struct test_struct, tree_node);
+	is(node, NULL, "lookup unregistered path '%s'", path_unregistered);
+
+	node = test_add_path(&tree, 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) {
+		uint32_t rolling_hash =
+			json_path_node_hash(&node->tree_node.key,
+					    tree.root.rolling_hash);
+		json_tree_remove(&tree, &tree.root, &node->tree_node,
+				 rolling_hash);
+		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[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, &tree.root) {
+		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 of %d",
+		   idx, t1->value, t2->value);
+		++idx;
+	}
+	is(idx, cnt, "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};
+	cnt = sizeof(tree_nodes_postorder)/sizeof(tree_nodes_postorder[0]);
+	idx = 0;
+	json_tree_foreach_post(tree_record, &tree.root) {
+		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, cnt, "records iterated count %d of %d", idx, cnt);
+
+	idx = 0;
+	json_tree_foreach_safe(tree_record, &tree.root) {
+		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, cnt, "records iterated count %d of %d", idx, cnt);
+
+	idx = 0;
+	json_tree_foreach_entry_pre(node, &tree.root, struct test_struct,
+				    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, cnt, "records iterated count %d of %d", idx, cnt);
+
+	idx = 0;
+	json_tree_foreach_entry_post(node, &tree.root, struct test_struct,
+				     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, cnt, "records iterated count %d of %d", idx, cnt);
+
+	idx = 0;
+	json_tree_foreach_entry_safe(node, &tree.root, struct test_struct,
+				     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, cnt, "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..5b44fd2 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,44 @@ ok 1 - subtests
     ok 20 - tab inside identifier
 ok 2 - subtests
 	*** test_errors: done ***
+	*** test_tree ***
+    1..36
+    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 1 expected of 1
+    ok 8 - test foreach pre order 1: have 2 expected of 2
+    ok 9 - test foreach pre order 2: have 3 expected of 3
+    ok 10 - test foreach pre order 3: have 4 expected of 4
+    ok 11 - records iterated count 4 of 4
+    ok 12 - test foreach post order 0: have 2 expected of 2
+    ok 13 - test foreach post order 1: have 4 expected of 4
+    ok 14 - test foreach post order 2: have 3 expected of 3
+    ok 15 - test foreach post order 3: have 1 expected of 1
+    ok 16 - records iterated count 4 of 4
+    ok 17 - test foreach safe order 0: have 2 expected of 2
+    ok 18 - test foreach safe order 1: have 4 expected of 4
+    ok 19 - test foreach safe order 2: have 3 expected of 3
+    ok 20 - test foreach safe order 3: have 1 expected of 1
+    ok 21 - records iterated count 4 of 4
+    ok 22 - test foreach entry pre order 0: have 1 expected of 1
+    ok 23 - test foreach entry pre order 1: have 2 expected of 2
+    ok 24 - test foreach entry pre order 2: have 3 expected of 3
+    ok 25 - test foreach entry pre order 3: have 4 expected of 4
+    ok 26 - records iterated count 4 of 4
+    ok 27 - test foreach entry post order 0: have 2 expected of 2
+    ok 28 - test foreach entry post order 1: have 4 expected of 4
+    ok 29 - test foreach entry post order 2: have 3 expected of 3
+    ok 30 - test foreach entry post order 3: have 1 expected of 1
+    ok 31 - records iterated count 4 of 4
+    ok 32 - test foreach entry safe order 0: have 2 expected of 2
+    ok 33 - test foreach entry safe order 1: have 4 expected of 4
+    ok 34 - test foreach entry safe order 2: have 3 expected of 3
+    ok 35 - test foreach entry safe order 3: have 1 expected of 1
+    ok 36 - records iterated count 4 of 4
+ok 3 - subtests
+	*** test_tree: done ***
 	*** main: done ***
-- 
2.7.4