Re: [tarantool-patches] Re: [PATCH v1 1/1] lib: implement JSON tree class for json library

[Kirill Shcherbatov <kshcherbatov@tarantool.org>]

Hi thank you for review!
I've fixed most your suggestions, and tried to use class in main patch.
Thus I've implemented lazy-initialization for hashtable.

> Shouldn't we use json_path_node for a key?
No, we also need to pass hash that lacks in key re

>   json_tree_next_child(NULL, node)
> 
> looks unnatural to me.
Ok for here, but I've kept such order for foreach defines
foreach(iterator, object) is looking good for me.


> I wouldn't use _entry variants here, because 'next' may be not a list
> entry, but a list head, which you check below.
Sorry, I don't understand, how should I implement the other way.
I've adopted this code from cgroups.

> Please rewrite the test without any reference to tuple fields.
> All you need is check all functions so I expect the test to be
> simple and clear.
Ok, done.

> Do you really need all these dependencies? AFAICS you only use header
> files (rlist.h and mhash.h) so no new dependencies should be introduced
Yes, I do. We need a hash functions that are the part of misc.
target_link_libraries(json_path misc)

=================================================

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         | 288 ++++++++++++++++++++++++++++++++++++++++++++
 src/lib/json/tree.h         | 241 ++++++++++++++++++++++++++++++++++++
 test/unit/json_path.c       | 205 ++++++++++++++++++++++++++++++-
 4 files changed, 735 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..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..505118d
--- /dev/null
+++ b/src/lib/json/tree.c
@@ -0,0 +1,288 @@
+
+/*
+ * 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 "module.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);
+}
+
+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;
+	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;
+}
+
+/**
+ * Return the next child of a JSON tree node.
+ * @param parent Parent of @pos record.
+ * @param pos Last visited JSON tree node record.
+ * @retval not NULL pointer to next item if exists.
+ */
+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;
+}
+
+/**
+ * Find leftmost record relative for node.
+ * @param pos JSON tree node.
+ * @retval not NULL pointer to next item if exists.
+ */
+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..7a9b309
--- /dev/null
+++ b/src/lib/json/tree.h
@@ -0,0 +1,241 @@
+#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
+
+struct mh_json_tree_node_t;
+
+/**
+ * JSON tree is a hierarchical data structure that organize JSON
+ * nodes produced by parser.
+ * Structure key records point to source strings memory.
+ */
+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);
+
+/**
+ * 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) ); })
+
+/** 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..369a02b 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,215 @@ 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[3].tree_node, &records[4].tree_node,
+		 &records[2].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[4].tree_node, &records[3].tree_node,
+		 &records[2].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();
-- 
2.7.4