Tarantool development patches archive
 help / color / mirror / Atom feed
From: Vladimir Davydov <vdavydov.dev@gmail.com>
To: Kirill Shcherbatov <kshcherbatov@tarantool.org>
Cc: tarantool-patches@freelists.org, kostja@tarantool.org
Subject: Re: [PATCH v6 2/4] lib: implement JSON tree class for json library
Date: Mon, 10 Dec 2018 20:36:58 +0300	[thread overview]
Message-ID: <20181210173658.kt3egtdr2s3jbykc@esperanza> (raw)
In-Reply-To: <250f3d856ef46a94e1712dc2aa1c3cb987809492.1544084229.git.kshcherbatov@tarantool.org>

On Thu, Dec 06, 2018 at 11:42:29AM +0300, Kirill Shcherbatov wrote:
> 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.
> 
> Needed for #1012
> ---
>  src/lib/json/CMakeLists.txt |   1 +
>  src/lib/json/json.c         | 257 ++++++++++++++++++++++++++++++++
>  src/lib/json/json.h         | 287 +++++++++++++++++++++++++++++++++++-
>  test/unit/json_path.c       | 243 +++++++++++++++++++++++++++++-
>  test/unit/json_path.result  |  60 +++++++-
>  5 files changed, 845 insertions(+), 3 deletions(-)

I cleaned up the patch and pushed it to 2.1.

Here's the list of my changes:
 - Forbid root = NULL in json_tree_lookup_path.
 - Make loop variable first in foreach macros argument list.
 - Use int instead of uint32_t unless uint32_t is specifically
   required.
 - Set max_child_idx to -1 if children array is empty to avoid
   ambiguity.
 - Fix child index allocation for JSON_TOKEN_STR.
 - Rework json_tree_add and json_tree_del to make them more
   straightforward.
 - Add comments and cleanup code.

Here's the incremental diff:

diff --git a/src/lib/json/json.c b/src/lib/json/json.c
index 65169b04..6f3cccc4 100644
--- a/src/lib/json/json.c
+++ b/src/lib/json/json.c
@@ -30,12 +30,19 @@
  */
 
 #include "json.h"
-#include "third_party/PMurHash.h"
+
+#include <assert.h>
 #include <ctype.h>
 #include <stdbool.h>
+#include <stddef.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
 #include <unicode/uchar.h>
 #include <unicode/utf8.h>
+
 #include "trivia/util.h"
+#include "third_party/PMurHash.h"
 
 /**
  * Read a single symbol from a string starting from an offset.
@@ -245,7 +252,9 @@ json_lexer_next_token(struct json_lexer *lexer, struct json_token *token)
 	}
 }
 
-/** Compare JSON tokens keys. */
+/**
+ * Compare JSON token keys.
+ */
 static int
 json_token_cmp(const struct json_token *a, const struct json_token *b)
 {
@@ -279,14 +288,18 @@ json_token_cmp(const struct json_token *a, const struct json_token *b)
 
 static const uint32_t hash_seed = 13U;
 
-/** Compute the hash value of a JSON token. */
+/**
+ * Compute the hash value of a JSON token.
+ *
+ * See the comment to json_tree::hash for implementation details.
+ */
 static uint32_t
 json_token_hash(struct json_token *token)
 {
 	uint32_t h = token->parent->hash;
 	uint32_t carry = 0;
 	const void *data;
-	uint32_t data_size;
+	int data_size;
 	if (token->type == JSON_TOKEN_STR) {
 		data = token->str;
 		data_size = token->len;
@@ -306,6 +319,8 @@ json_tree_create(struct json_tree *tree)
 	memset(tree, 0, sizeof(struct json_tree));
 	tree->root.hash = hash_seed;
 	tree->root.type = JSON_TOKEN_END;
+	tree->root.max_child_idx = -1;
+	tree->root.sibling_idx = -1;
 	tree->hash = mh_json_new();
 	return tree->hash == NULL ? -1 : 0;
 }
@@ -313,16 +328,10 @@ json_tree_create(struct json_tree *tree)
 static void
 json_token_destroy(struct json_token *token)
 {
-#ifndef NDEBUG
-	/* Token mustn't have JSON subtree. */
-	struct json_token *iter;
-	uint32_t nodes = 0;
-	json_tree_foreach_preorder(token, iter)
-		nodes++;
-	assert(nodes == 0);
-#endif /* NDEBUG */
-
+ 	assert(token->max_child_idx == -1);
+	assert(token->sibling_idx == -1);
 	free(token->children);
+	token->children = NULL;
 }
 
 void
@@ -347,7 +356,7 @@ json_tree_lookup_slowpath(struct json_tree *tree, struct json_token *parent,
 	if (id == mh_end(tree->hash))
 		return NULL;
 	struct json_token **entry = mh_json_node(tree->hash, id);
-	assert(entry != NULL);
+	assert(entry != NULL && *entry != NULL);
 	return *entry;
 }
 
@@ -355,89 +364,90 @@ int
 json_tree_add(struct json_tree *tree, struct json_token *parent,
 	      struct json_token *token)
 {
-	int ret = 0;
-	token->parent = parent;
-	uint32_t hash = json_token_hash(token);
 	assert(json_tree_lookup(tree, parent, token) == NULL);
-	uint32_t insert_idx = token->type == JSON_TOKEN_NUM ?
-			      (uint32_t)token->num :
-			      parent->children_capacity;
+	token->parent = parent;
+	token->children = NULL;
+	token->children_capacity = 0;
+	token->max_child_idx = -1;
+	token->hash = json_token_hash(token);
+	int insert_idx = token->type == JSON_TOKEN_NUM ?
+			 (int)token->num : parent->max_child_idx + 1;
+	/*
+	 * Dynamically grow the children array if necessary.
+	 */
 	if (insert_idx >= parent->children_capacity) {
-		uint32_t new_size = parent->children_capacity == 0 ?
-				    8 : 2 * parent->children_capacity;
+		int new_size = parent->children_capacity == 0 ?
+			       8 : 2 * parent->children_capacity;
 		while (insert_idx >= new_size)
 			new_size *= 2;
-		struct json_token **children =
-			realloc(parent->children, new_size*sizeof(void *));
-		if (children == NULL) {
-			ret = -1;
-			goto end;
-		}
+		struct json_token **children = realloc(parent->children,
+						new_size * sizeof(void *));
+		if (children == NULL)
+			return -1; /* out of memory */
 		memset(children + parent->children_capacity, 0,
-		       (new_size - parent->children_capacity)*sizeof(void *));
+		       (new_size - parent->children_capacity) * sizeof(void *));
 		parent->children = children;
 		parent->children_capacity = new_size;
 	}
+	/*
+	 * Insert the token into the hash (only for tokens representing
+	 * JSON map entries, see the comment to json_tree::hash).
+	 */
+	if (token->type == JSON_TOKEN_STR) {
+		mh_int_t id = mh_json_put(tree->hash,
+			(const struct json_token **)&token, NULL, NULL);
+		if (id == mh_end(tree->hash))
+			return -1; /* out of memory */
+	}
+	/*
+	 * Success, now we can insert the new token into its parent's
+	 * children array.
+	 */
 	assert(parent->children[insert_idx] == NULL);
 	parent->children[insert_idx] = token;
 	parent->max_child_idx = MAX(parent->max_child_idx, insert_idx);
 	token->sibling_idx = insert_idx;
-	token->hash = hash;
-	token->parent = parent;
-	if (token->type != JSON_TOKEN_STR)
-		goto end;
-	/*
-	 * Add string token to json_tree hash to make lookup
-	 * by name.
-	 */
-	mh_int_t rc =
-		mh_json_put(tree->hash, (const struct json_token **)&token,
-			    NULL, NULL);
-	if (rc == mh_end(tree->hash)) {
-		parent->children[insert_idx] = NULL;
-		ret = -1;
-		goto end;
-	}
-end:
 	assert(json_tree_lookup(tree, parent, token) == token);
-	return ret;
+	return 0;
 }
 
 void
 json_tree_del(struct json_tree *tree, struct json_token *token)
 {
 	struct json_token *parent = token->parent;
+	assert(token->sibling_idx >= 0);
+	assert(parent->children[token->sibling_idx] == token);
 	assert(json_tree_lookup(tree, parent, token) == token);
-	struct json_token **child_slot = &parent->children[token->sibling_idx];
-	assert(child_slot != NULL && *child_slot == token);
-	*child_slot = NULL;
-	/* The max_child_idx field may require update. */
-	if (token->sibling_idx == parent->max_child_idx &&
-	    parent->max_child_idx > 0) {
-		uint32_t idx = token->sibling_idx - 1;
-		while (idx > 0 && parent->children[idx] == 0)
-			idx--;
-		parent->max_child_idx = idx;
+	/*
+	 * Clear the entry corresponding to this token in parent's
+	 * children array and update max_child_idx if necessary.
+	 */
+	parent->children[token->sibling_idx] = NULL;
+	token->sibling_idx = -1;
+	while (parent->max_child_idx >= 0 &&
+	       parent->children[parent->max_child_idx] == NULL)
+		parent->max_child_idx--;
+	/*
+	 * Remove the token from the hash (only for tokens representing
+	 * JSON map entries, see the comment to json_tree::hash).
+	 */
+	if (token->type == JSON_TOKEN_STR) {
+		mh_int_t id = mh_json_find(tree->hash, token, NULL);
+		assert(id != mh_end(tree->hash));
+		mh_json_del(tree->hash, id, NULL);
 	}
-	if (token->type != JSON_TOKEN_STR)
-		goto end;
-	/* Remove string token from json_tree hash. */
-	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);
-end:
 	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, uint32_t index_base)
+json_tree_lookup_path(struct json_tree *tree, struct json_token *root,
+		      const char *path, int path_len, int index_base)
 {
 	int rc;
 	struct json_lexer lexer;
 	struct json_token token;
-	struct json_token *ret = parent != NULL ? parent : &tree->root;
+	struct json_token *ret = root;
 	json_lexer_create(&lexer, path, path_len, index_base);
 	while ((rc = json_lexer_next_token(&lexer, &token)) == 0 &&
 	       token.type != JSON_TOKEN_END && ret != NULL) {
@@ -448,6 +458,11 @@ json_tree_lookup_path(struct json_tree *tree, struct json_token *parent,
 	return ret;
 }
 
+/**
+ * Return the child of @parent following @pos or NULL if @pos
+ * points to the last child in the children array. If @pos is
+ * NULL, this function returns the first child.
+ */
 static struct json_token *
 json_tree_child_next(struct json_token *parent, struct json_token *pos)
 {
@@ -455,12 +470,16 @@ json_tree_child_next(struct json_token *parent, struct json_token *pos)
 	struct json_token **arr = parent->children;
 	if (arr == NULL)
 		return NULL;
-	uint32_t idx = pos != NULL ? pos->sibling_idx + 1 : 0;
+	int idx = pos != NULL ? pos->sibling_idx + 1 : 0;
 	while (idx <= parent->max_child_idx && arr[idx] == NULL)
 		idx++;
 	return idx <= parent->max_child_idx ? arr[idx] : NULL;
 }
 
+/**
+ * Return the leftmost descendant of the tree rooted at @pos
+ * or NULL if the tree is empty.
+ */
 static struct json_token *
 json_tree_leftmost(struct json_token *pos)
 {
diff --git a/src/lib/json/json.h b/src/lib/json/json.h
index 4ff2b9c6..8aa2765f 100644
--- a/src/lib/json/json.h
+++ b/src/lib/json/json.h
@@ -30,12 +30,18 @@
  * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.
  */
+#include <stddef.h>
+#include <stdint.h>
 #include "trivia/util.h"
 
 #ifdef __cplusplus
 extern "C" {
 #endif
 
+#ifndef typeof
+#define typeof __typeof__
+#endif
+
 /**
  * Lexer for JSON paths:
  * <field>, <.field>, <[123]>, <['field']> and their combinations.
@@ -84,26 +90,33 @@ struct json_token {
 		/** Index value. */
 		uint64_t num;
 	};
+	/** Pointer to the parent token in a JSON tree. */
+	struct json_token *parent;
 	/**
-	 * Hash value of the token. Used for lookups in a JSON tree.
-	 * For more details, see the comment to json_tree::hash_table.
-	 */
-	uint32_t hash;
-	/**
-	 * Array of child records. Indexes in this array
-	 * match [token.num] index for JSON_TOKEN_NUM type and
-	 * are allocated sequentially for JSON_TOKEN_STR child
+	 * Array of child tokens in a JSON tree. Indexes in this
+	 * array match [token.num] index for JSON_TOKEN_NUM type
+	 * and are allocated sequentially for JSON_TOKEN_STR child
 	 * tokens.
 	 */
 	struct json_token **children;
 	/** Allocation size of children array. */
-	uint32_t children_capacity;
-	/** Max occupied index in the children array. */
-	uint32_t max_child_idx;
-	/** Index of node in parent children array. */
-	uint32_t sibling_idx;
-	/** Pointer to parent node. */
-	struct json_token *parent;
+	int children_capacity;
+	/**
+	 * Max occupied index in the children array or -1 if
+	 * the children array is empty.
+	 */
+	int max_child_idx;
+	/**
+	 * Index of this token in parent's children array or -1
+	 * if the token was removed from a JSON tree or represents
+	 * a JSON tree root.
+	 */
+	int sibling_idx;
+	/**
+	 * Hash value of the token. Used for lookups in a JSON tree.
+	 * For more details, see the comment to json_tree::hash.
+	 */
+	uint32_t hash;
 };
 
 struct mh_json_t;
@@ -222,32 +235,43 @@ 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. */
+/**
+ * Initialize a new empty JSON tree.
+ *
+ * Returns 0 on success, -1 on memory allocation error.
+ */
 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.
+ * Destroy a JSON tree.
+ *
+ * Note, this routine expects the tree to be empty - the caller
+ * is supposed to use json_tree_foreach_safe() and json_tree_del()
+ * to dismantle the tree before calling this function.
  */
 void
 json_tree_destroy(struct json_tree *tree);
 
-/** Internal function, use json_tree_lookup instead. */
+/**
+ * Internal function, use json_tree_lookup() instead.
+ */
 struct json_token *
 json_tree_lookup_slowpath(struct json_tree *tree, struct json_token *parent,
 			  const struct json_token *token);
 
 /**
- * Look up a token in a tree at position specified with parent.
+ * Look up a token in a JSON tree given a parent token and a key.
+ *
+ * Returns NULL if not found.
  */
 static inline struct json_token *
 json_tree_lookup(struct json_tree *tree, struct json_token *parent,
 		 const struct json_token *token)
 {
 	struct json_token *ret = NULL;
-	if (token->type == JSON_TOKEN_NUM) {
-		ret = likely(token->num < parent->children_capacity) ?
+	if (likely(token->type == JSON_TOKEN_NUM)) {
+		ret = (int)token->num < parent->children_capacity ?
 		      parent->children[token->num] : NULL;
 	} else {
 		ret = json_tree_lookup_slowpath(tree, parent, token);
@@ -256,147 +280,171 @@ json_tree_lookup(struct json_tree *tree, struct json_token *parent,
 }
 
 /**
- * Append token to the given parent position in a JSON tree. The
- * parent mustn't have a child with such content.
+ * Insert a token into a JSON tree at a given position.
+ *
+ * The token key (json_token::type and num/str,len) must be set,
+ * e.g. by json_lexer_next_token(). The caller must ensure that
+ * no token with the same key is linked to the same parent, e.g.
+ * with json_tree_lookup().
+ *
+ * Returns 0 on success, -1 on memory allocation error.
  */
 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.
+ * Delete a token from a JSON tree.
+ *
+ * The token must be linked to the tree (see json_tree_add())
+ * and must not have any children.
  */
 void
 json_tree_del(struct json_tree *tree, struct json_token *token);
 
-/** Lookup child by path in JSON tree. */
+/**
+ * Look up a token in a JSON tree by path.
+ *
+ * The path is relative to the given root token. In order to
+ * look up a token by absolute path, pass json_tree::root.
+ * The index_base is passed to json_lexer used for tokenizing
+ * the path, see json_lexer_create() for more details.
+ *
+ * Returns NULL if no token is found or the path is invalid.
+ */
 struct json_token *
-json_tree_lookup_path(struct json_tree *tree, struct json_token *parent,
-		      const char *path, uint32_t path_len, uint32_t index_base);
+json_tree_lookup_path(struct json_tree *tree, struct json_token *root,
+		      const char *path, int path_len, int index_base);
 
-/** Do pre order traversal in JSON tree. */
+/**
+ * Perform pre-order traversal in a JSON subtree rooted
+ * at a given node.
+ *
+ * To start a new traversal, pass NULL for @pos.
+ * Returns @root at the first iteration.
+ * Returns NULL when traversal is over.
+ */
 struct json_token *
 json_tree_preorder_next(struct json_token *root, struct json_token *pos);
 
-/** Do post order traversal in JSON tree. */
+/**
+ * Perform post-order traversal in a JSON subtree rooted
+ * at a given node.
+ *
+ * To start a new traversal, pass NULL for @pos.
+ * Returns @root at the last iteration.
+ * Returns NULL when traversal is over.
+ */
 struct json_token *
 json_tree_postorder_next(struct json_token *root, struct json_token *pos);
 
-#ifndef typeof
-#define typeof __typeof__
-#endif
+/**
+ * Perform pre-order JSON tree traversal.
+ * Note, this function does not visit the root node.
+ * See also json_tree_preorder_next().
+ */
+#define json_tree_foreach_preorder(pos, root)				     \
+	for ((pos) = json_tree_preorder_next((root), (root));		     \
+	     (pos) != NULL;						     \
+	     (pos) = json_tree_preorder_next((root), (pos)))
 
-/** Return container entry by json_tree_node node. */
-#define json_tree_entry(node, type, member) \
-	container_of((node), type, member)
 /**
- * Return container entry by json_tree_node or NULL if
- * node is NULL.
+ * Perform post-order JSON tree traversal.
+ * Note, this function does not visit the root node.
+ * See also json_tree_postorder_next().
  */
-#define json_tree_entry_safe(node, type, member) ({			     \
-	(node) != NULL ? json_tree_entry((node), type, member) : NULL;	     \
-})
+#define json_tree_foreach_postorder(pos, root)				     \
+	for ((pos) = json_tree_postorder_next((root), NULL);		     \
+	     (pos) != (root);						     \
+	     (pos) = json_tree_postorder_next((root), (pos)))
 
-/** Do entry pre order traversal in JSON tree */
-#define json_tree_preorder_next_entry(root, node, type, member) ({	     \
-	struct json_token *__next =					     \
-		json_tree_preorder_next((root), (node));		     \
-	json_tree_entry_safe(__next, type, member);			     \
-})
+/**
+ * Perform post-order JSON tree traversal safe against node removal.
+ * Note, this function does not visit the root node.
+ * See also json_tree_postorder_next().
+ */
+#define json_tree_foreach_safe(pos, root, tmp)				     \
+	for ((pos) = json_tree_postorder_next((root), NULL);		     \
+	     (pos) != (root) &&						     \
+	     ((tmp) = json_tree_postorder_next((root), (pos))) != NULL;	     \
+	     (pos) = (tmp))
 
 /**
- * Do entry post order traversal in JSON tree.
- * This cycle doesn't visit root node.
+ * Return a container of a json_tree_token.
  */
-#define json_tree_postorder_next_entry(root, node, type, member) ({	     \
-	struct json_token *__next =					     \
-		json_tree_postorder_next((root), (node));		     \
-	json_tree_entry_safe(__next, type, member);			     \
-})
+#define json_tree_entry(token, type, member)				     \
+	container_of((token), type, member)
 
 /**
- * Lookup in tree by path and return entry.
- * This cycle doesn't visit root node.
+ * Return a container of a json_tree_token or NULL if @token is NULL.
  */
-#define json_tree_lookup_path_entry(tree, parent, path, path_len,	     \
-				    index_base, type, member) ({	     \
-	struct json_token *__node =					     \
-		json_tree_lookup_path((tree), (parent), path, path_len,	     \
-				      index_base);			     \
-	json_tree_entry_safe(__node, type, member);			     \
-})
+#define json_tree_entry_safe(token, type, member)			     \
+	((token) != NULL ? json_tree_entry((token), type, member) : NULL);   \
 
-/** Lookup in tree by token and return entry. */
+/**
+ * Container-aware wrapper around json_tree_lookup().
+ */
 #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);			     \
+	struct json_token *ret = json_tree_lookup((tree), (parent), (token));\
+	json_tree_entry_safe(ret, type, member);			     \
 })
 
 /**
- * Do pre-order traversal in JSON tree.
- * This cycle doesn't visit root node.
+ * Container-aware wrapper around json_tree_lookup_path().
  */
-#define json_tree_foreach_preorder(root, node)				     \
-	for ((node) = json_tree_preorder_next((root), (root));		     \
-	     (node) != NULL;						     \
-	     (node) = json_tree_preorder_next((root), (node)))
+#define json_tree_lookup_path_entry(tree, root, path, path_len, index_base,  \
+				    type, member) ({			     \
+	struct json_token *ret = json_tree_lookup_path((tree), (root),	     \
+					(path), (path_len), (index_base));   \
+	json_tree_entry_safe(ret, type, member);			     \
+})
 
 /**
- * Do post-order traversal in JSON tree.
- * This cycle doesn't visit root node.
+ * Container-aware wrapper around json_tree_preorder_next().
  */
-#define json_tree_foreach_postorder(root, node)				     \
-	for ((node) = json_tree_postorder_next((root), NULL);		     \
-	     (node) != (root);						     \
-	     (node) = json_tree_postorder_next((root), (node)))
+#define json_tree_preorder_next_entry(root, pos, type, member) ({	     \
+	struct json_token *next = json_tree_preorder_next((root), (pos));    \
+	json_tree_entry_safe(next, type, member);			     \
+})
 
 /**
- * Do safe post-order traversal in JSON tree.
- * May be used for destructors.
- * This cycle doesn't visit root node.
+ * Container-aware wrapper around json_tree_postorder_next().
  */
-#define json_tree_foreach_safe(root, node, tmp)				     \
-	for ((node) = json_tree_postorder_next((root), NULL);		     \
-	     (node) != (root) &&					     \
-	     ((tmp) =  json_tree_postorder_next((root), (node)));	     \
-	     (node) = (tmp))
+#define json_tree_postorder_next_entry(root, pos, type, member) ({	     \
+	struct json_token *next = json_tree_postorder_next((root), (pos));   \
+	json_tree_entry_safe(next, type, member);			     \
+})
 
 /**
- * Do post-order traversal in JSON tree and return entry.
- * This cycle doesn't visit root node.
+ * Container-aware version of json_tree_foreach_preorder().
  */
-#define json_tree_foreach_entry_preorder(root, node, type, member)	     \
-	for ((node) = json_tree_preorder_next_entry((root), (root),	     \
-						    type, member);	     \
-	     (node) != NULL;						     \
-	     (node) = json_tree_preorder_next_entry((root), &(node)->member, \
-						    type, member))
+#define json_tree_foreach_entry_preorder(pos, root, type, member)	     \
+	for ((pos) = json_tree_preorder_next_entry((root), (root),	     \
+						   type, member);	     \
+	     (pos) != NULL;						     \
+	     (pos) = json_tree_preorder_next_entry((root), &(pos)->member,   \
+						   type, member))
 
 /**
- * Do pre-order traversal in JSON tree and return entry.
- * This cycle doesn't visit root node.
+ * Container-aware version of json_tree_foreach_postorder().
  */
-#define json_tree_foreach_entry_postorder(root, node, type, member)	     \
-	for ((node) = json_tree_postorder_next_entry((root), NULL, type,     \
-						     member);		     \
-	     &(node)->member != (root);					     \
-	     (node) = json_tree_postorder_next_entry((root), &(node)->member,\
+#define json_tree_foreach_entry_postorder(pos, root, type, member)	     \
+	for ((pos) = json_tree_postorder_next_entry((root), NULL,	     \
+						    type, member);	     \
+	     &(pos)->member != (root);					     \
+	     (pos) = json_tree_postorder_next_entry((root), &(pos)->member,  \
 						     type, member))
 
 /**
- * Do secure post-order traversal in JSON tree and return entry.
- * This cycle doesn't visit root node.
+ * Container-aware version of json_tree_foreach_safe().
  */
-#define json_tree_foreach_entry_safe(root, node, type, member, tmp)	     \
-	for ((node) = json_tree_postorder_next_entry((root), NULL,	     \
-						     type, member);	     \
-	     &(node)->member != (root) &&				     \
-	     ((tmp) =  json_tree_postorder_next_entry((root),		     \
-						      &(node)->member,	     \
-						      type, member));	     \
-	     (node) = (tmp))
+#define json_tree_foreach_entry_safe(pos, root, type, member, tmp)	     \
+	for ((pos) = json_tree_postorder_next_entry((root), NULL,	     \
+						    type, member);	     \
+	     &(pos)->member != (root) &&				     \
+	     ((tmp) = json_tree_postorder_next_entry((root), &(pos)->member, \
+						     type, member)) != NULL; \
+	     (pos) = (tmp))
 
 #ifdef __cplusplus
 }
diff --git a/test/unit/json_path.c b/test/unit/json_path.c
index 04d36688..b72865e4 100644
--- a/test/unit/json_path.c
+++ b/test/unit/json_path.c
@@ -250,17 +250,17 @@ test_tree()
 			     &records_idx);
 	is(node, &records[5], "add path '%s'", path4_copy);
 
-	node = json_tree_lookup_path_entry(&tree, NULL, path1, strlen(path1),
-					   JSON_INDEX_BASE, struct test_struct,
-					   node);
+	node = json_tree_lookup_path_entry(&tree, &tree.root, path1,
+					   strlen(path1), JSON_INDEX_BASE,
+					   struct test_struct, node);
 	is(node, &records[1], "lookup path '%s'", path1);
 
-	node = json_tree_lookup_path_entry(&tree, NULL, path2, strlen(path2),
-					   JSON_INDEX_BASE, struct test_struct,
-					   node);
+	node = json_tree_lookup_path_entry(&tree, &tree.root, path2,
+					   strlen(path2), JSON_INDEX_BASE,
+					   struct test_struct, node);
 	is(node, &records[3], "lookup path '%s'", path2);
 
-	node = json_tree_lookup_path_entry(&tree, NULL, path_unregistered,
+	node = json_tree_lookup_path_entry(&tree, &tree.root, path_unregistered,
 					   strlen(path_unregistered),
 					   JSON_INDEX_BASE, struct test_struct,
 					   node);
@@ -274,7 +274,7 @@ test_tree()
 	int cnt = sizeof(tokens_preorder)/sizeof(tokens_preorder[0]);
 	int idx = 0;
 
-	json_tree_foreach_preorder(&tree.root, token) {
+	json_tree_foreach_preorder(token, &tree.root) {
 		if (idx >= cnt)
 			break;
 		struct test_struct *t1 =
@@ -294,7 +294,7 @@ test_tree()
 		 &records[3].node, &records[2].node, &records[0].node};
 	cnt = sizeof(tree_nodes_postorder)/sizeof(tree_nodes_postorder[0]);
 	idx = 0;
-	json_tree_foreach_postorder(&tree.root, token) {
+	json_tree_foreach_postorder(token, &tree.root) {
 		if (idx >= cnt)
 			break;
 		struct test_struct *t1 =
@@ -310,7 +310,7 @@ test_tree()
 	is(idx, cnt, "records iterated count %d of %d", idx, cnt);
 
 	idx = 0;
-	json_tree_foreach_safe(&tree.root, token, tmp) {
+	json_tree_foreach_safe(token, &tree.root, tmp) {
 		if (idx >= cnt)
 			break;
 		struct test_struct *t1 =
@@ -326,7 +326,7 @@ test_tree()
 	is(idx, cnt, "records iterated count %d of %d", idx, cnt);
 
 	idx = 0;
-	json_tree_foreach_entry_preorder(&tree.root, node, struct test_struct,
+	json_tree_foreach_entry_preorder(node, &tree.root, struct test_struct,
 					 node) {
 		if (idx >= cnt)
 			break;
@@ -341,7 +341,7 @@ test_tree()
 	is(idx, cnt, "records iterated count %d of %d", idx, cnt);
 
 	idx = 0;
-	json_tree_foreach_entry_postorder(&tree.root, node, struct test_struct,
+	json_tree_foreach_entry_postorder(node, &tree.root, struct test_struct,
 					  node) {
 		if (idx >= cnt)
 			break;
@@ -362,21 +362,21 @@ test_tree()
 	is(records[3].node.max_child_idx, 1, "max_child_index %d expected of %d",
 	   records[3].node.max_child_idx, 1);
 	json_tree_del(&tree, &records[4].node);
-	is(records[3].node.max_child_idx, 0, "max_child_index %d expected of %d",
-	   records[3].node.max_child_idx, 0);
-	node = json_tree_lookup_path_entry(&tree, NULL, path3, strlen(path3),\
-					   JSON_INDEX_BASE, struct test_struct,
-					   node);
+	is(records[3].node.max_child_idx, -1, "max_child_index %d expected of %d",
+	   records[3].node.max_child_idx, -1);
+	node = json_tree_lookup_path_entry(&tree, &tree.root, path3,
+					   strlen(path3), JSON_INDEX_BASE,
+					   struct test_struct, node);
 	is(node, NULL, "lookup removed path '%s'", path3);
 
-	node = json_tree_lookup_path_entry(&tree, NULL, path4, strlen(path4),
-					   JSON_INDEX_BASE, struct test_struct,
-					   node);
+	node = json_tree_lookup_path_entry(&tree, &tree.root, path4,
+					   strlen(path4), JSON_INDEX_BASE,
+					   struct test_struct, node);
 	is(node, NULL, "lookup removed path '%s'", path4);
 
-	node = json_tree_lookup_path_entry(&tree, NULL, path2, strlen(path2),
-					   JSON_INDEX_BASE, struct test_struct,
-					   node);
+	node = json_tree_lookup_path_entry(&tree, &tree.root, path2,
+					   strlen(path2), JSON_INDEX_BASE,
+					   struct test_struct, node);
 	is(node, &records[3], "lookup path was not corrupted '%s'", path2);
 
 	const struct json_token *tree_nodes_postorder_new[] =
@@ -385,7 +385,7 @@ test_tree()
 	cnt = sizeof(tree_nodes_postorder_new) /
 	      sizeof(tree_nodes_postorder_new[0]);
 	idx = 0;
-	json_tree_foreach_entry_safe(&tree.root, node, struct test_struct,
+	json_tree_foreach_entry_safe(node, &tree.root, struct test_struct,
 				     node, node_tmp) {
 		if (idx >= cnt)
 			break;
diff --git a/test/unit/json_path.result b/test/unit/json_path.result
index 0ee970c8..ee23e70c 100644
--- a/test/unit/json_path.result
+++ b/test/unit/json_path.result
@@ -147,7 +147,7 @@ ok 2 - subtests
     ok 43 - records iterated count 6 of 6
     ok 44 - max_child_index 7 expected of 7
     ok 45 - max_child_index 1 expected of 1
-    ok 46 - max_child_index 0 expected of 0
+    ok 46 - max_child_index -1 expected of -1
     ok 47 - lookup removed path '[1][20].file[2]'
     ok 48 - lookup removed path '[1][20].file[8]'
     ok 49 - lookup path was not corrupted '[1][20].file'

  reply	other threads:[~2018-12-10 17:36 UTC|newest]

Thread overview: 9+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-12-06  8:42 [PATCH v6 0/4] box: JSON tree class Kirill Shcherbatov
2018-12-06  8:42 ` [PATCH v6 1/4] lib: make index_base support for json_lexer Kirill Shcherbatov
2018-12-10 17:34   ` Vladimir Davydov
2018-12-06  8:42 ` [PATCH v6 2/4] lib: implement JSON tree class for json library Kirill Shcherbatov
2018-12-10 17:36   ` Vladimir Davydov [this message]
2018-12-06  8:42 ` [PATCH v6 3/4] box: manage format fields with JSON tree class Kirill Shcherbatov
2018-12-11  9:52   ` Vladimir Davydov
2018-12-06  8:42 ` [PATCH v6 4/4] lib: introduce json_path_cmp, json_path_validate Kirill Shcherbatov
2018-12-10 17:38   ` Vladimir Davydov

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20181210173658.kt3egtdr2s3jbykc@esperanza \
    --to=vdavydov.dev@gmail.com \
    --cc=kostja@tarantool.org \
    --cc=kshcherbatov@tarantool.org \
    --cc=tarantool-patches@freelists.org \
    --subject='Re: [PATCH v6 2/4] lib: implement JSON tree class for json library' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox