[tarantool-patches] [PATCH v5 2/9] 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/box/tuple_format.c      |  22 +--
 src/lib/json/CMakeLists.txt |   1 +
 src/lib/json/json.c         | 284 ++++++++++++++++++++++++++++++++++--
 src/lib/json/json.h         | 196 +++++++++++++++++++++++--
 test/unit/json_path.c       | 208 +++++++++++++++++++++++++-
 test/unit/json_path.result  |  41 +++++-
 6 files changed, 714 insertions(+), 38 deletions(-)

diff --git a/src/box/tuple_format.c b/src/box/tuple_format.c
index 661cfdc94..d184dbae1 100644
--- a/src/box/tuple_format.c
+++ b/src/box/tuple_format.c
@@ -584,15 +584,16 @@ tuple_field_go_to_path(const char **data, const char *path, uint32_t path_len)
 	struct json_token token;
 	json_lexer_create(&lexer, path, path_len);
 	while ((rc = json_lexer_next_token(&lexer, &token)) == 0) {
-		switch (token.type) {
+		switch (token.key.type) {
 		case JSON_TOKEN_NUM:
-			rc = tuple_field_go_to_index(data, token.num);
+			rc = tuple_field_go_to_index(data, token.key.num);
 			break;
 		case JSON_TOKEN_STR:
-			rc = tuple_field_go_to_key(data, token.str, token.len);
+			rc = tuple_field_go_to_key(data, token.key.str,
+						   token.key.len);
 			break;
 		default:
-			assert(token.type == JSON_TOKEN_END);
+			assert(token.key.type == JSON_TOKEN_END);
 			return 0;
 		}
 		if (rc != 0) {
@@ -628,9 +629,9 @@ tuple_field_raw_by_path(struct tuple_format *format, const char *tuple,
 	int rc = json_lexer_next_token(&lexer, &token);
 	if (rc != 0)
 		goto error;
-	switch(token.type) {
+	switch(token.key.type) {
 	case JSON_TOKEN_NUM: {
-		int index = token.num;
+		int index = token.key.num;
 		if (index == 0) {
 			*field = NULL;
 			return 0;
@@ -644,7 +645,7 @@ tuple_field_raw_by_path(struct tuple_format *format, const char *tuple,
 	case JSON_TOKEN_STR: {
 		/* First part of a path is a field name. */
 		uint32_t name_hash;
-		if (path_len == (uint32_t) token.len) {
+		if (path_len == (uint32_t) token.key.len) {
 			name_hash = path_hash;
 		} else {
 			/*
@@ -653,17 +654,18 @@ tuple_field_raw_by_path(struct tuple_format *format, const char *tuple,
 			 * used. A tuple dictionary hashes only
 			 * name, not path.
 			 */
-			name_hash = field_name_hash(token.str, token.len);
+			name_hash = field_name_hash(token.key.str,
+						    token.key.len);
 		}
 		*field = tuple_field_raw_by_name(format, tuple, field_map,
-						 token.str, token.len,
+						 token.key.str, token.key.len,
 						 name_hash);
 		if (*field == NULL)
 			return 0;
 		break;
 	}
 	default:
-		assert(token.type == JSON_TOKEN_END);
+		assert(token.key.type == JSON_TOKEN_END);
 		*field = NULL;
 		return 0;
 	}
diff --git a/src/lib/json/CMakeLists.txt b/src/lib/json/CMakeLists.txt
index 0f0739620..51a1f027a 100644
--- a/src/lib/json/CMakeLists.txt
+++ b/src/lib/json/CMakeLists.txt
@@ -4,3 +4,4 @@ set(lib_sources
 
 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/json.c b/src/lib/json/json.c
index eb80e4bbc..6bc74507f 100644
--- a/src/lib/json/json.c
+++ b/src/lib/json/json.c
@@ -30,6 +30,7 @@
  */
 
 #include "json.h"
+#include "third_party/PMurHash.h"
 #include <ctype.h>
 #include <stdbool.h>
 #include <unicode/uchar.h>
@@ -111,9 +112,9 @@ json_parse_string(struct json_lexer *lexer, struct json_token *token,
 			int len = lexer->offset - str_offset - 1;
 			if (len == 0)
 				return lexer->symbol_count;
-			token->type = JSON_TOKEN_STR;
-			token->str = lexer->src + str_offset;
-			token->len = len;
+			token->key.type = JSON_TOKEN_STR;
+			token->key.str = lexer->src + str_offset;
+			token->key.len = len;
 			return 0;
 		}
 	}
@@ -146,8 +147,8 @@ json_parse_integer(struct json_lexer *lexer, struct json_token *token)
 	} while (++pos < end && isdigit((c = *pos)));
 	lexer->offset += len;
 	lexer->symbol_count += len;
-	token->type = JSON_TOKEN_NUM;
-	token->num = value;
+	token->key.type = JSON_TOKEN_NUM;
+	token->key.num = value;
 	return 0;
 }
 
@@ -192,9 +193,9 @@ json_parse_identifier(struct json_lexer *lexer, struct json_token *token)
 		}
 		last_offset = lexer->offset;
 	}
-	token->type = JSON_TOKEN_STR;
-	token->str = lexer->src + str_offset;
-	token->len = lexer->offset - str_offset;
+	token->key.type = JSON_TOKEN_STR;
+	token->key.str = lexer->src + str_offset;
+	token->key.len = lexer->offset - str_offset;
 	return 0;
 }
 
@@ -202,7 +203,7 @@ int
 json_lexer_next_token(struct json_lexer *lexer, struct json_token *token)
 {
 	if (lexer->offset == lexer->src_len) {
-		token->type = JSON_TOKEN_END;
+		token->key.type = JSON_TOKEN_END;
 		return 0;
 	}
 	UChar32 c;
@@ -241,3 +242,268 @@ json_lexer_next_token(struct json_lexer *lexer, struct json_token *token)
 		return json_parse_identifier(lexer, token);
 	}
 }
+
+/** Compare JSON tokens keys. */
+static int
+json_token_key_cmp(const struct json_token *a, const struct json_token *b)
+{
+	if (a->key.type != b->key.type)
+		return a->key.type - b->key.type;
+	int ret = 0;
+	if (a->key.type == JSON_TOKEN_STR) {
+		if (a->key.len != b->key.len)
+			return a->key.len - b->key.len;
+		ret = memcmp(a->key.str, b->key.str, a->key.len);
+	} else if (a->key.type == JSON_TOKEN_NUM) {
+		ret = a->key.num - b->key.num;
+	} else {
+		unreachable();
+	}
+	return ret;
+}
+
+/**
+ * Compare hash records of two json tree nodes. Return 0 if equal.
+ */
+static inline int
+mh_json_cmp(const struct json_token *a, const struct json_token *b)
+{
+	if (a->parent != b->parent)
+		return a->parent - b->parent;
+	return json_token_key_cmp(a, b);
+}
+
+#define MH_SOURCE 1
+#define mh_name _json
+#define mh_key_t struct json_token **
+#define mh_node_t struct json_token *
+#define mh_arg_t void *
+#define mh_hash(a, arg) ((*a)->rolling_hash)
+#define mh_hash_key(a, arg) ((*a)->rolling_hash)
+#define mh_cmp(a, b, arg) (mh_json_cmp((*a), (*b)))
+#define mh_cmp_key(a, b, arg) mh_cmp(a, b, arg)
+#include "salad/mhash.h"
+
+static const uint32_t hash_seed = 13U;
+
+/** Compute the hash value of a JSON token. */
+static uint32_t
+json_token_hash(struct json_token *token, uint32_t seed)
+{
+	uint32_t h = seed;
+	uint32_t carry = 0;
+	const void *data;
+	uint32_t data_size;
+	if (token->key.type == JSON_TOKEN_STR) {
+		data = token->key.str;
+		data_size = token->key.len;
+	} else if (token->key.type == JSON_TOKEN_NUM) {
+		data = &token->key.num;
+		data_size = sizeof(token->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 = hash_seed;
+	tree->root.key.type = JSON_TOKEN_END;
+	tree->hash = mh_json_new();
+	return tree->hash == NULL ? -1 : 0;
+}
+
+static void
+json_token_destroy(struct json_token *token)
+{
+	free(token->children);
+}
+
+void
+json_tree_destroy(struct json_tree *tree)
+{
+	assert(tree->hash != NULL);
+	json_token_destroy(&tree->root);
+	mh_json_delete(tree->hash);
+}
+
+struct json_token *
+json_tree_lookup(struct json_tree *tree, struct json_token *parent,
+		 struct json_token *token)
+{
+	if (parent == NULL)
+		parent = &tree->root;
+	struct json_token *ret = NULL;
+	if (token->key.type == JSON_TOKEN_STR) {
+		struct json_token key = *token;
+		key.rolling_hash = json_token_hash(token, parent->rolling_hash);
+		key.parent = parent;
+		token = &key;
+		mh_int_t id = mh_json_find(tree->hash, &token, NULL);
+		if (unlikely(id == mh_end(tree->hash)))
+			return NULL;
+		struct json_token **entry = mh_json_node(tree->hash, id);
+		assert(entry == NULL || (*entry)->parent == parent);
+		return entry != NULL ? *entry : NULL;
+	} else if (token->key.type == JSON_TOKEN_NUM) {
+		uint32_t idx =  token->key.num - 1;
+		ret = idx < parent->child_size ? parent->children[idx] : NULL;
+	} else {
+		unreachable();
+	}
+	return ret;
+}
+
+int
+json_tree_add(struct json_tree *tree, struct json_token *parent,
+	      struct json_token *token)
+{
+	if (parent == NULL)
+		parent = &tree->root;
+	uint32_t rolling_hash =
+	       json_token_hash(token, parent->rolling_hash);
+	assert(json_tree_lookup(tree, parent, token) == NULL);
+	uint32_t insert_idx = (token->key.type == JSON_TOKEN_NUM) ?
+			      (uint32_t)token->key.num - 1 :
+			      parent->child_size;
+	if (insert_idx >= parent->child_size) {
+		uint32_t new_size =
+			parent->child_size == 0 ? 1 : 2 * parent->child_size;
+		while (insert_idx >= new_size)
+			new_size *= 2;
+		struct json_token **children =
+			realloc(parent->children, new_size*sizeof(void *));
+		if (unlikely(children == NULL))
+			return -1;
+		memset(children + parent->child_size, 0,
+		       (new_size - parent->child_size)*sizeof(void *));
+		parent->children = children;
+		parent->child_size = new_size;
+	}
+	assert(parent->children[insert_idx] == NULL);
+	parent->children[insert_idx] = token;
+	parent->child_count = MAX(parent->child_count, insert_idx + 1);
+	token->sibling_idx = insert_idx;
+	token->rolling_hash = rolling_hash;
+	token->parent = parent;
+
+	const struct json_token **key =
+		(const struct json_token **)&token;
+	mh_int_t rc = mh_json_put(tree->hash, key, NULL, NULL);
+	if (unlikely(rc == mh_end(tree->hash))) {
+		parent->children[insert_idx] = NULL;
+		return -1;
+	}
+	assert(json_tree_lookup(tree, parent, token) == token);
+	return 0;
+}
+
+void
+json_tree_del(struct json_tree *tree, struct json_token *token)
+{
+	struct json_token *parent = token->parent;
+	assert(json_tree_lookup(tree, parent, token) == token);
+	struct json_token **child_slot = NULL;
+	if (token->key.type == JSON_TOKEN_NUM) {
+		child_slot = &parent->children[token->key.num - 1];
+	} else {
+		uint32_t idx = 0;
+		while (idx < parent->child_size &&
+		       parent->children[idx] != token) { idx++; }
+		if (idx < parent->child_size &&
+		       parent->children[idx] == token)
+			child_slot = &parent->children[idx];
+	}
+	assert(child_slot != NULL && *child_slot == token);
+	*child_slot = NULL;
+
+	mh_int_t id = mh_json_find(tree->hash, &token, NULL);
+	assert(id != mh_end(tree->hash));
+	mh_json_del(tree->hash, id, NULL);
+	json_token_destroy(token);
+	assert(json_tree_lookup(tree, parent, token) == NULL);
+}
+
+struct json_token *
+json_tree_lookup_path(struct json_tree *tree, struct json_token *parent,
+		      const char *path, uint32_t path_len)
+{
+	int rc;
+	struct json_lexer lexer;
+	struct json_token token;
+	struct json_token *ret = parent != NULL ? parent : &tree->root;
+	json_lexer_create(&lexer, path, path_len);
+	while ((rc = json_lexer_next_token(&lexer, &token)) == 0 &&
+	       token.key.type != JSON_TOKEN_END && ret != NULL) {
+		ret = json_tree_lookup(tree, ret, &token);
+	}
+	if (rc != 0 || token.key.type != JSON_TOKEN_END)
+		return NULL;
+	return ret;
+}
+
+static struct json_token *
+json_tree_child_next(struct json_token *parent, struct json_token *pos)
+{
+	assert(pos == NULL || pos->parent == parent);
+	struct json_token **arr = parent->children;
+	uint32_t arr_size = parent->child_size;
+	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_token *
+json_tree_leftmost(struct json_token *pos)
+{
+	struct json_token *last;
+	do {
+		last = pos;
+		pos = json_tree_child_next(pos, NULL);
+	} while (pos != NULL);
+	return last;
+}
+
+struct json_token *
+json_tree_preorder_next(struct json_token *root, struct json_token *pos)
+{
+	if (pos == NULL)
+		pos = root;
+	struct json_token *next = json_tree_child_next(pos, NULL);
+	if (next != NULL)
+		return next;
+	while (pos != root) {
+		next = json_tree_child_next(pos->parent, pos);
+		if (next != NULL)
+			return next;
+		pos = pos->parent;
+	}
+	return NULL;
+}
+
+struct json_token *
+json_tree_postorder_next(struct json_token *root, struct json_token *pos)
+{
+	struct json_token *next;
+	if (pos == NULL) {
+		next = json_tree_leftmost(root);
+		return next != root ? next : NULL;
+	}
+	if (pos == root)
+		return NULL;
+	next = json_tree_child_next(pos->parent, pos);
+	if (next != NULL) {
+		next = json_tree_leftmost(next);
+		return next != root ? next : NULL;
+	}
+	return pos->parent != root ? pos->parent : NULL;
+}
diff --git a/src/lib/json/json.h b/src/lib/json/json.h
index ead446878..2bc159ff8 100644
--- a/src/lib/json/json.h
+++ b/src/lib/json/json.h
@@ -61,20 +61,53 @@ enum json_token_type {
 /**
  * Element of a JSON path. It can be either string or number.
  * String idenfiers are in ["..."] and between dots. Numbers are
- * indexes in [...].
+ * indexes in [...]. May be organized in a JSON tree.
  */
 struct json_token {
-	enum json_token_type type;
-	union {
-		struct {
-			/** String identifier. */
-			const char *str;
-			/** Length of @a str. */
-			int len;
+	struct {
+		enum json_token_type type;
+		union {
+			struct {
+				/** String identifier. */
+				const char *str;
+				/** Length of @a str. */
+				int len;
+			};
+			/** Index value. */
+			uint64_t num;
 		};
-		/** Index value. */
-		uint64_t num;
-	};
+	} key;
+	/** Rolling hash for node used to lookup in json_tree. */
+	uint32_t rolling_hash;
+	/**
+	 * Array of child records. Indexes in this array
+	 * follows array indexe-1 for JSON_TOKEN_NUM token type
+	 * and are allocated sequently for JSON_TOKEN_NUM child
+	 * tokens. NULLs initializations are performed with new
+	 * entries allocation.
+	 */
+	struct json_token **children;
+	/** Allocation size of children array. */
+	uint32_t child_size;
+	/**
+	 * Count of defined children array items. Equal the
+	 * maximum index of inserted item.
+	 */
+	uint32_t child_count;
+	/** Index of node in parent children array. */
+	uint32_t sibling_idx;
+	/** Pointer to parent node. */
+	struct json_token *parent;
+};
+
+struct mh_json_t;
+
+/** JSON tree object to manage tokens relations. */
+struct json_tree {
+	/** JSON tree root node. */
+	struct json_token root;
+	/** Hashtable af all tree nodes. */
+	struct mh_json_t *hash;
 };
 
 /**
@@ -104,6 +137,147 @@ json_lexer_create(struct json_lexer *lexer, const char *src, int src_len)
 int
 json_lexer_next_token(struct json_lexer *lexer, struct json_token *token);
 
+/** 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 destroy attached
+ * subtree so it should be called at the end of manual destroy.
+ */
+void
+json_tree_destroy(struct json_tree *tree);
+
+/**
+ * Make child lookup in JSON tree by token at position specified
+ * with parent. The parent may be set NULL to use tree root
+ * record.
+ */
+struct json_token *
+json_tree_lookup(struct json_tree *tree, struct json_token *parent,
+		 struct json_token *token);
+
+/**
+ * Append token to the given parent position in a JSON tree. The
+ * parent mustn't have a child with such content. The parent may
+ * be set NULL to use tree root record.
+ */
+int
+json_tree_add(struct json_tree *tree, struct json_token *parent,
+	      struct json_token *token);
+
+/**
+ * Delete a JSON tree token at the given parent position in JSON
+ * tree. Token entry shouldn't have subtree.
+ */
+void
+json_tree_del(struct json_tree *tree, struct json_token *token);
+
+/** Make child lookup by path in JSON tree. */
+struct json_token *
+json_tree_lookup_path(struct json_tree *tree, struct json_token *parent,
+		      const char *path, uint32_t path_len);
+
+/** Make pre order traversal in JSON tree. */
+struct json_token *
+json_tree_preorder_next(struct json_token *root, struct json_token *pos);
+
+/** Make post order traversal in JSON tree. */
+struct json_token *
+json_tree_postorder_next(struct json_token *root, struct json_token *pos);
+
+/**
+ * Make safe post-order traversal in JSON tree.
+ * May be used for destructors.
+ */
+#define json_tree_foreach_safe(node, root)				     \
+for (struct json_token *__next = json_tree_postorder_next((root), NULL);     \
+     (((node) = __next) &&						     \
+     (__next = json_tree_postorder_next((root), (node))), (node) != NULL);)
+
+#ifndef typeof
+/* TODO: 'typeof' is a GNU extension */
+#define typeof __typeof__
+#endif
+
+/** Return container entry by json_tree_node node. */
+#define json_tree_entry(node, type, member) ({ 				     \
+	const typeof( ((type *)0)->member ) *__mptr = (node);		     \
+	(type *)( (char *)__mptr - ((size_t) &((type *)0)->member) );	     \
+})
+
+/**
+ * Return container entry by json_tree_node or NULL if
+ * node is NULL.
+ */
+#define json_tree_entry_safe(node, type, member) ({			     \
+	(node) != NULL ? json_tree_entry((node), type, member) : NULL;	     \
+})
+
+/** Make entry pre order traversal in JSON tree  */
+#define json_tree_preorder_next_entry(node, root, type, member) ({	     \
+	struct json_token *__next =					     \
+		json_tree_preorder_next((root), (node));		     \
+	json_tree_entry_safe(__next, type, member);			     \
+})
+
+/** Make entry post order traversal in JSON tree  */
+#define json_tree_postorder_next_entry(node, root, type, member) ({	     \
+	struct json_token *__next =					     \
+		json_tree_postorder_next((root), (node));		     \
+	json_tree_entry_safe(__next, type, member);			     \
+})
+
+/** Make lookup in tree by path and return entry. */
+#define json_tree_lookup_path_entry(tree, parent, path, path_len, type,	     \
+				    member)				     \
+({struct json_token *__node =						     \
+	json_tree_lookup_path((tree), (parent), path, path_len);	     \
+	json_tree_entry_safe(__node, type, member); })
+
+/** Make lookup in tree by token and return entry. */
+#define json_tree_lookup_entry(tree, parent, token, type, member)	     \
+({struct json_token *__node =						     \
+	json_tree_lookup((tree), (parent), token);			     \
+	json_tree_entry_safe(__node, type, member);			     \
+})
+
+/** Make pre-order traversal in JSON tree. */
+#define json_tree_foreach_preorder(node, root)				     \
+for ((node) = json_tree_preorder_next((root), NULL); (node) != NULL;	     \
+     (node) = json_tree_preorder_next((root), (node)))
+
+/** Make post-order traversal in JSON tree. */
+#define json_tree_foreach_postorder(node, root)				     \
+for ((node) = json_tree_postorder_next((root), NULL); (node) != NULL;	     \
+     (node) = json_tree_postorder_next((root), (node)))
+
+/** Make post-order traversal in JSON tree and return entry. */
+#define json_tree_foreach_entry_preorder(node, root, type, member)	     \
+for ((node) = json_tree_preorder_next_entry(NULL, (root), type, member);     \
+     (node) != NULL;							     \
+     (node) = json_tree_preorder_next_entry(&(node)->member, (root), type,   \
+					    member))
+
+/** Make pre-order traversal in JSON tree and return entry. */
+#define json_tree_foreach_entry_postorder(node, root, type, member)	     \
+for ((node) = json_tree_postorder_next_entry(NULL, (root), type, member);    \
+     (node) != NULL;							     \
+     (node) = json_tree_postorder_next_entry(&(node)->member, (root), type,  \
+					     member))
+
+/**
+ * Make secure post-order traversal in JSON tree and return entry.
+ */
+#define json_tree_foreach_entry_safe(node, root, type, member)		     \
+for (type *__next = json_tree_postorder_next_entry(NULL, (root), type,	     \
+						   member);		     \
+     (((node) = __next) &&						     \
+     (__next = json_tree_postorder_next_entry(&(node)->member, (root), type, \
+					      member)),			     \
+     (node) != NULL);)
+
+
 #ifdef __cplusplus
 }
 #endif
diff --git a/test/unit/json_path.c b/test/unit/json_path.c
index a5f90ad98..f6b0472f4 100644
--- a/test/unit/json_path.c
+++ b/test/unit/json_path.c
@@ -2,6 +2,7 @@
 #include "unit.h"
 #include "trivia/util.h"
 #include <string.h>
+#include <stdbool.h>
 
 #define reset_to_new_path(value) \
 	path = value; \
@@ -12,15 +13,15 @@
 	path = lexer.src + lexer.offset; \
 	is(json_lexer_next_token(&lexer, &token), 0, "parse <%." #value_len "s>", \
 	   path); \
-	is(token.type, JSON_TOKEN_NUM, "<%." #value_len "s> is num", path); \
-	is(token.num, value, "<%." #value_len "s> is " #value, path);
+	is(token.key.type, JSON_TOKEN_NUM, "<%." #value_len "s> is num", path); \
+	is(token.key.num, value, "<%." #value_len "s> is " #value, path);
 
 #define is_next_key(value) \
 	len = strlen(value); \
 	is(json_lexer_next_token(&lexer, &token), 0, "parse <" value ">"); \
-	is(token.type, JSON_TOKEN_STR, "<" value "> is str"); \
-	is(token.len, len, "len is %d", len); \
-	is(strncmp(token.str, value, len), 0, "str is " value);
+	is(token.key.type, JSON_TOKEN_STR, "<" value "> is str"); \
+	is(token.key.len, len, "len is %d", len); \
+	is(strncmp(token.key.str, value, len), 0, "str is " value);
 
 void
 test_basic()
@@ -62,7 +63,7 @@ test_basic()
 	/* Empty path. */
 	reset_to_new_path("");
 	is(json_lexer_next_token(&lexer, &token), 0, "parse empty path");
-	is(token.type, JSON_TOKEN_END, "is str");
+	is(token.key.type, JSON_TOKEN_END, "is str");
 
 	/* Path with no '.' at the beginning. */
 	reset_to_new_path("field1.field2");
@@ -159,14 +160,207 @@ test_errors()
 	footer();
 }
 
+struct test_struct {
+	int value;
+	struct json_token node;
+};
+
+struct test_struct *
+test_struct_alloc(struct test_struct *records_pool, int *pool_idx)
+{
+	struct test_struct *ret = &records_pool[*pool_idx];
+	*pool_idx = *pool_idx + 1;
+	memset(&ret->node, 0, sizeof(ret->node));
+	return ret;
+}
+
+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_lexer lexer;
+	struct json_token *parent = NULL;
+	json_lexer_create(&lexer, path, path_len);
+	struct test_struct *field = test_struct_alloc(records_pool, pool_idx);
+	while ((rc = json_lexer_next_token(&lexer, &field->node)) == 0 &&
+		field->node.key.type != JSON_TOKEN_END) {
+		struct json_token *next =
+			json_tree_lookup(tree, parent, &field->node);
+		if (next == NULL) {
+			rc = json_tree_add(tree, parent, &field->node);
+			fail_if(rc != 0);
+			next = &field->node;
+			field = test_struct_alloc(records_pool, pool_idx);
+		}
+		parent = next;
+	}
+	fail_if(rc != 0 || field->node.key.type != JSON_TOKEN_END);
+	*pool_idx = *pool_idx - 1;
+	/* release field */
+	return json_tree_entry(parent, struct test_struct, node);
+}
+
+void
+test_tree()
+{
+	header();
+	plan(35);
+
+	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 *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_path_entry(&tree, NULL, path1, strlen(path1),
+					   struct test_struct, node);
+	is(node, &records[2], "lookup path '%s'", path1);
+
+	node = json_tree_lookup_path_entry(&tree, NULL, path2, strlen(path2),
+					   struct test_struct, node);
+	is(node, &records[4], "lookup path '%s'", path2);
+
+	node = json_tree_lookup_path_entry(&tree, NULL, path_unregistered,
+					   strlen(path_unregistered),
+					   struct test_struct, node);
+	is(node, NULL, "lookup unregistered path '%s'", path_unregistered);
+
+	/* Test iterators. */
+	struct json_token *token = NULL;
+	const struct json_token *tokens_preorder[] =
+		{&records[1].node, &records[2].node,
+		 &records[3].node, &records[4].node};
+	int cnt = sizeof(tokens_preorder)/sizeof(tokens_preorder[0]);
+	int idx = 0;
+
+	json_tree_foreach_preorder(token, &tree.root) {
+		if (idx >= cnt)
+			break;
+		struct test_struct *t1 =
+			json_tree_entry(token, struct test_struct, node);
+		struct test_struct *t2 =
+			json_tree_entry(tokens_preorder[idx],
+					struct test_struct, node);
+		is(token, tokens_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_token *tree_nodes_postorder[] =
+		{&records[2].node, &records[4].node,
+		 &records[3].node, &records[1].node};
+	cnt = sizeof(tree_nodes_postorder)/sizeof(tree_nodes_postorder[0]);
+	idx = 0;
+	json_tree_foreach_postorder(token, &tree.root) {
+		if (idx >= cnt)
+			break;
+		struct test_struct *t1 =
+			json_tree_entry(token, struct test_struct, node);
+		struct test_struct *t2 =
+			json_tree_entry(tree_nodes_postorder[idx],
+					struct test_struct, node);
+		is(token, 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(token, &tree.root) {
+		if (idx >= cnt)
+			break;
+		struct test_struct *t1 =
+			json_tree_entry(token, struct test_struct, node);
+		struct test_struct *t2 =
+			json_tree_entry(tree_nodes_postorder[idx],
+					struct test_struct, node);
+		is(token, 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_preorder(node, &tree.root, struct test_struct,
+					 node) {
+		if (idx >= cnt)
+			break;
+		struct test_struct *t =
+			json_tree_entry(tokens_preorder[idx],
+					struct test_struct, node);
+		is(&node->node, tokens_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_postorder(node, &tree.root, struct test_struct,
+					  node) {
+		if (idx >= cnt)
+			break;
+		struct test_struct *t =
+			json_tree_entry(tree_nodes_postorder[idx],
+					struct test_struct, node);
+		is(&node->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,
+				     node) {
+		if (idx >= cnt)
+			break;
+		struct test_struct *t =
+			json_tree_entry(tree_nodes_postorder[idx],
+					struct test_struct, node);
+		is(&node->node, tree_nodes_postorder[idx],
+		   "test foreach entry safe order %d: have %d expected of %d",
+		   idx, node->value, t->value);
+		json_tree_del(&tree, &node->node);
+		idx++;
+	}
+	is(idx, cnt, "records iterated count %d of %d", idx, cnt);
+	json_tree_destroy(&tree);
+
+	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 a2a2f829f..df682109c 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,43 @@ ok 1 - subtests
     ok 20 - tab inside identifier
 ok 2 - subtests
 	*** test_errors: done ***
+	*** test_tree ***
+    1..35
+    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 - test foreach pre order 0: have 1 expected of 1
+    ok 7 - test foreach pre order 1: have 2 expected of 2
+    ok 8 - test foreach pre order 2: have 3 expected of 3
+    ok 9 - test foreach pre order 3: have 4 expected of 4
+    ok 10 - records iterated count 4 of 4
+    ok 11 - test foreach post order 0: have 2 expected of 2
+    ok 12 - test foreach post order 1: have 4 expected of 4
+    ok 13 - test foreach post order 2: have 3 expected of 3
+    ok 14 - test foreach post order 3: have 1 expected of 1
+    ok 15 - records iterated count 4 of 4
+    ok 16 - test foreach safe order 0: have 2 expected of 2
+    ok 17 - test foreach safe order 1: have 4 expected of 4
+    ok 18 - test foreach safe order 2: have 3 expected of 3
+    ok 19 - test foreach safe order 3: have 1 expected of 1
+    ok 20 - records iterated count 4 of 4
+    ok 21 - test foreach entry pre order 0: have 1 expected of 1
+    ok 22 - test foreach entry pre order 1: have 2 expected of 2
+    ok 23 - test foreach entry pre order 2: have 3 expected of 3
+    ok 24 - test foreach entry pre order 3: have 4 expected of 4
+    ok 25 - records iterated count 4 of 4
+    ok 26 - test foreach entry post order 0: have 2 expected of 2
+    ok 27 - test foreach entry post order 1: have 4 expected of 4
+    ok 28 - test foreach entry post order 2: have 3 expected of 3
+    ok 29 - test foreach entry post order 3: have 1 expected of 1
+    ok 30 - records iterated count 4 of 4
+    ok 31 - test foreach entry safe order 0: have 2 expected of 2
+    ok 32 - test foreach entry safe order 1: have 4 expected of 4
+    ok 33 - test foreach entry safe order 2: have 3 expected of 3
+    ok 34 - test foreach entry safe order 3: have 1 expected of 1
+    ok 35 - records iterated count 4 of 4
+ok 3 - subtests
+	*** test_tree: done ***
 	*** main: done ***
-- 
2.19.2