From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: From: Kirill Shcherbatov Subject: [PATCH v1 1/1] lib: implement JSON tree class for json library Date: Mon, 1 Oct 2018 15:27:02 +0300 Message-Id: <51204844504cf430967af4414fb98b552c8f07f7.1538396782.git.kshcherbatov@tarantool.org> To: tarantool-patches@freelists.org Cc: vdavydov.dev@gmail.com, Kirill Shcherbatov List-ID: New JSON tree class would store JSON paths for tuple fields for registered non-plain indexes. Part of #1012. --- Branch: http://github.com/tarantool/tarantool/tree/kshch/gh-1012-json-tree-class Issue: https://github.com/tarantool/tarantool/issues/1012 src/lib/json/CMakeLists.txt | 2 + src/lib/json/tree.c | 272 ++++++++++++++++++++++++++++++++++++++++++++ src/lib/json/tree.h | 207 +++++++++++++++++++++++++++++++++ test/unit/json_path.c | 210 +++++++++++++++++++++++++++++++++- 4 files changed, 690 insertions(+), 1 deletion(-) create mode 100644 src/lib/json/tree.c create mode 100644 src/lib/json/tree.h diff --git a/src/lib/json/CMakeLists.txt b/src/lib/json/CMakeLists.txt index 203fe6f..9702b79 100644 --- a/src/lib/json/CMakeLists.txt +++ b/src/lib/json/CMakeLists.txt @@ -1,6 +1,8 @@ set(lib_sources path.c + tree.c ) set_source_files_compile_flags(${lib_sources}) add_library(json_path STATIC ${lib_sources}) +target_link_libraries(json_path misc salad small) diff --git a/src/lib/json/tree.c b/src/lib/json/tree.c new file mode 100644 index 0000000..a393d5b --- /dev/null +++ b/src/lib/json/tree.c @@ -0,0 +1,272 @@ + +/* + * Copyright 2010-2018 Tarantool AUTHORS: please see AUTHORS file. + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * 1. Redistributions of source code must retain the above + * copyright notice, this list of conditions and the + * following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials + * provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY ``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 + * 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 +#include +#include +#include +#include +#include + +#include "tree.h" +#include "path.h" +#include "third_party/PMurHash.h" + +/** Hash record representing json_tree_node. */ +struct mh_json_tree_node { + struct json_path_node key; + uint32_t key_hash; + struct json_tree_node *node; +}; + +/** + * Compare json_tree_node hash bindings @a and @b. + * @param a Hash record to compare. + * @param b Hash record to compare. + * @retval 0 On equal, not 0 otherwise. + */ +bool +mh_json_tree_node_cmp(const struct mh_json_tree_node *a, + const struct mh_json_tree_node *b) +{ + return (a->key.type != b->key.type) || + ((a->key.type != JSON_PATH_STR || + a->key.len != b->key.len || + memcmp(a->key.str, b->key.str, + a->key.len) != 0) && + (a->key.type != JSON_PATH_NUM || + a->key_hash != b->key_hash)); +} + +/** Define tree record hashtable. */ +#define MH_SOURCE 1 +#define mh_name _json_tree_node +#define mh_key_t struct mh_json_tree_node * +#define mh_node_t struct mh_json_tree_node +#define mh_arg_t void * +#define mh_hash(a, arg) ((a)->key_hash) +#define mh_hash_key(a, arg) ((a)->key_hash) +#define mh_cmp(a, b, arg) (mh_json_tree_node_cmp((a), (b))) +#define mh_cmp_key(a, b, arg) mh_cmp(a, b, arg) +#include "salad/mhash.h" + +static const uint32_t json_path_node_hash_seed = 13U; + +uint32_t +json_path_node_hash(struct json_path_node *key) +{ + uint32_t h = json_path_node_hash_seed; + uint32_t carry = 0; + uint8_t *data; + uint32_t data_size; + if (key->type == JSON_PATH_STR) { + data = (uint8_t *)key->str; + data_size = key->len; + } else if (key->type == JSON_PATH_NUM) { + data = (uint8_t *)&key->num; + data_size = sizeof(key->num); + } else { + assert(0); + } + PMurHash32_Process(&h, &carry, data, data_size); + return PMurHash32_Result(h, carry, data_size); +} + +int +json_tree_node_create(struct json_tree_node *node, + struct json_path_node *path_node, uint32_t path_node_hash) +{ + assert(path_node == NULL || + path_node_hash == json_path_node_hash(path_node)); + memset(node, 0, sizeof(struct json_tree_node)); + node->children_ht = mh_json_tree_node_new(); + if (node->children_ht == NULL) + return -1; + if (path_node != NULL) { + memcpy(&node->key, path_node, sizeof(struct json_path_node)); + node->key_hash = path_node_hash; + } else { + node->key.type = JSON_PATH_END; + } + rlist_create(&node->siblings); + rlist_create(&node->children); + return 0; +} + +void +json_tree_node_destroy(struct json_tree_node *node) +{ + mh_json_tree_node_delete(node->children_ht); +} + +struct json_tree_node * +json_tree_lookup(struct json_tree_node *root, struct json_path_node *path_node, + uint32_t path_node_hash) +{ + struct mh_json_tree_node info; + memcpy(&info.key, path_node, sizeof(struct json_path_node)); + info.key_hash = path_node_hash; + mh_int_t id = mh_json_tree_node_find(root->children_ht, &info, NULL); + if (id == mh_end(root->children_ht)) + return NULL; + struct mh_json_tree_node *ht_node = + mh_json_tree_node_node(root->children_ht, id); + assert(ht_node == NULL || ht_node->node != NULL); + struct json_tree_node *ret = ht_node != NULL ? ht_node->node : NULL; + assert(ret == NULL || ret->parent == root); + return ret; +} + +int +json_tree_add(struct json_tree_node *root, struct json_tree_node *node) +{ + assert(node->parent == NULL); + assert(json_tree_lookup(root, &node->key, node->key_hash) == NULL); + struct mh_json_tree_node ht_node; + memcpy(&ht_node.key, &node->key, sizeof(struct json_path_node)); + ht_node.key_hash = node->key_hash; + ht_node.node = node; + mh_int_t rc = mh_json_tree_node_put(root->children_ht, &ht_node, NULL, + NULL); + if (rc == mh_end(node->children_ht)) + return -1; + node->parent = root; + rlist_add(&root->children, &node->siblings); + return 0; +} + +void +json_tree_remove(struct json_tree_node *root, struct json_tree_node *node) +{ + assert(node->parent == root); + assert(json_tree_lookup(root, &node->key, node->key_hash) == node); + rlist_del_entry(node, siblings); + struct mh_json_tree_node info; + memcpy(&info.key, &node->key, + sizeof(struct json_path_node)); + info.key_hash = node->key_hash; + mh_int_t id = mh_json_tree_node_find(root->children_ht, &info, NULL); + assert(id != mh_end(root->children_ht)); + mh_json_tree_node_del(root->children_ht, id, NULL); + assert(json_tree_lookup(root, &node->key, node->key_hash) == NULL); +} + +struct json_tree_node * +json_tree_lookup_path(struct json_tree_node *root, const char *path, + uint32_t path_len) +{ + int rc; + struct json_path_parser parser; + struct json_path_node path_node; + json_path_parser_create(&parser, path, path_len); + while ((rc = json_path_next(&parser, &path_node)) == 0 && + path_node.type != JSON_PATH_END && root != NULL) { + uint32_t path_node_hash = json_path_node_hash(&path_node); + struct json_tree_node *node = + json_tree_lookup(root, &path_node, path_node_hash); + assert(node == NULL || node->parent == root); + root = node; + } + if (rc != 0 || path_node.type != JSON_PATH_END) + return NULL; + return root; +} + +/** + * Get JSON tree node next child. + * @param pos JSON tree node iterator. + * @param parent Parent of @pos record. + * @retval not NULL pointer to next item if exists. + */ +static struct json_tree_node * +json_tree_next_child(struct json_tree_node *pos, + struct json_tree_node *parent) +{ + struct json_tree_node *next; + if (pos == NULL) { + next = rlist_first_entry(&parent->children, + struct json_tree_node, siblings); + } else { + next = rlist_next_entry(pos, siblings); + } + if (&next->siblings != &parent->children) + return next; + return NULL; +} + +/** + * Find leftmost child rellative for iterator @pos. + * @param pos JSON tree node iterator. + * @retval not NULL pointer to next item if exists. + */ +static struct json_tree_node * +json_tree_leftmost_descendant(struct json_tree_node *pos) +{ + struct json_tree_node *last; + do { + last = pos; + pos = json_tree_next_child(NULL, pos); + } while (pos); + return last; +} + +struct json_tree_node * +json_tree_preorder_next(struct json_tree_node *pos, struct json_tree_node *root) +{ + if (pos == NULL) + return root; + struct json_tree_node *next = json_tree_next_child(NULL, pos); + if (next != NULL) + return next; + while (pos != root) { + next = json_tree_next_child(pos, pos->parent); + if (next != NULL) + return next; + pos = pos->parent; + } + return NULL; +} + +struct json_tree_node * +json_tree_postorder_next(struct json_tree_node *pos, + struct json_tree_node *root) +{ + struct json_tree_node *next; + if (pos == NULL) + return json_tree_leftmost_descendant(root); + if (pos == root) + return NULL; + next = json_tree_next_child(pos, pos->parent); + if (next != NULL) + return json_tree_leftmost_descendant(next); + return pos->parent; +} diff --git a/src/lib/json/tree.h b/src/lib/json/tree.h new file mode 100644 index 0000000..aa77b51 --- /dev/null +++ b/src/lib/json/tree.h @@ -0,0 +1,207 @@ +#ifndef TARANTOOL_JSON_TREE_H_INCLUDED +#define TARANTOOL_JSON_TREE_H_INCLUDED +/* + * Copyright 2010-2018 Tarantool AUTHORS: please see AUTHORS file. + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * 1. Redistributions of source code must retain the above + * copyright notice, this list of conditions and the + * following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials + * provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY ``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 + * 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 +#include "small/rlist.h" +#include "path.h" + +#ifdef __cplusplus +extern "C" +{ +#endif + +/** JSON path tree hash structure. */ +struct mh_json_tree_node_t; + +/** JSON path tree record structure. */ +struct json_tree_node { + /** JSON parser node path. */ + struct json_path_node key; + /** Hash calculated for key field. */ + uint32_t key_hash; + /** Childs hashtable: json_path_node -> json_tree_node. */ + struct mh_json_tree_node_t *children_ht; + /** Siblings nodes list. */ + struct rlist siblings; + /** Child nodes list. */ + struct rlist children; + /** Pointer to parent json_tree_node record. */ + struct json_tree_node *parent; +}; + +/** + * Calculate json_path_node hash. + * @param key JSON parser node to calculate hash. + * @retval Hash value. + */ +uint32_t +json_path_node_hash(struct json_path_node *key); + +/** + * Init JSON tree node. + * @param node JSON tree node to initialize. + * @param path_node Source JSON parser node to use on initialize. + * @param path_node_hash Hash of @path_node. + * @retval 0 On success, -1 otherwise. + */ +int +json_tree_node_create(struct json_tree_node *node, + struct json_path_node *path_node, + uint32_t path_node_hash); + +/** + * Destroy JSON tree node. + * @param node JSON tree node to destruct. + * @retval 0 On success, -1 on error. + */ +void +json_tree_node_destroy(struct json_tree_node *node); + +/** + * Lookup record with data @path_node having hash @path_node_hash + * in JSON tree @node childs. + * @param node JSON tree root node. + * @param path_node JSON parser node with data. + * @param path_node_hash Hash of @path_node. + * @retval not NULL pointer to JSON tree node if any. + */ +struct json_tree_node * +json_tree_lookup(struct json_tree_node *root, + struct json_path_node *path_node, + uint32_t path_node_hash); + +/** + * Append JSON tree node @node to @root. Root JSON tree node @root + * shouldn't have childs with same content. + * @param root JSON tree root node. + * @param node JSON tree node to append. + * @retval 0 On success, -1 on memory allocation error. + */ +int +json_tree_add(struct json_tree_node *root, + struct json_tree_node *node); + +/** + * Detach JSON tree node @node by @root. Root JSON tree node @root + * should have such child. + * @param root JSON tree root node. + * @param node JSON tree node to add. + */ +void +json_tree_remove(struct json_tree_node *root, + struct json_tree_node *node); + +/** + * Lookup JSON path @path having length @path_len in JSON + * tree @root. + * @param root JSON tree root node. + * @param path JSON path string. + * @param path_len Length of @path. + * @retval not NULL pointer to leaf record if any. + */ +struct json_tree_node * +json_tree_lookup_path(struct json_tree_node *root, + const char *path, uint32_t path_len); + +/** + * Make pre order traversal iterator @pos step. + * @param pos Iterator pointer, NULL for initialization. + * @param root The JSON path tree to walk root. + * @retval not NULL pointer to next node. NULL if nothing found. + */ +struct json_tree_node * +json_tree_preorder_next(struct json_tree_node *pos, + struct json_tree_node *root); + +/** + * Make post order traversal iterator @pos step. + * @param pos Iterator pointer, NULL for initialization. + * @param root The JSON path tree to walk root. + * @retval not NULL pointer to next node. NULL if nothing found. + */ +struct json_tree_node * +json_tree_postorder_next(struct json_tree_node *pos, + struct json_tree_node *root); + + +/** + * Define macros to operate with containers. + */ + +/** Return entry by json_tree_node item. */ +#define json_tree_node_entry(item, type, member) ({ \ + const typeof( ((type *)0)->member ) *__mptr = (item); \ + (type *)( (char *)__mptr - ((size_t) &((type *)0)->member) ); }) + +/** Make lookup in tree by path and return entry on found. */ +#define json_tree_lookup_path_entry(root, path, path_len, type, member) \ +({struct json_tree_node *__tree_node = \ + json_tree_lookup_path(&(root)->member, path, path_len); \ + __tree_node != NULL ? json_tree_node_entry(__tree_node, type, member) : \ + NULL; }) + +/** Make lookup in tree by path_node and return entry on found. */ +#define json_tree_lookup_entry(root, path_node, path_node_hash, type, member)\ +({struct json_tree_node *__tree_node = \ + json_tree_lookup(&(root)->member, path_node, path_node_hash); \ + __tree_node != NULL ? json_tree_node_entry(__tree_node, type, member) : \ + NULL; }) + +/** Make traversal in JSON tree. */ +#define json_tree_foreach_entry(order, item, root, member) \ +for (struct json_tree_node *__iter = \ + json_tree_##order##_next(NULL, &(root)->member); \ + __iter != NULL && (item = json_tree_node_entry(__iter, typeof(*root), \ + member)); \ + __iter = json_tree_##order##_next(__iter, &(root)->member)) + +/** + * Make secure traversal in JSON tree that works even on + * destruction under iterator. + */ +#define json_tree_foreach_entry_safe(order, item, root, member) \ +for (struct json_tree_node *__tmp_iter, *__iter = \ + json_tree_##order##_next(NULL, &(root)->member); \ + __iter != NULL && ((item) = json_tree_node_entry(__iter, typeof(*root), \ + member)) && \ + (__iter != NULL && (__tmp_iter = \ + json_tree_##order##_next(__iter, \ + &(root)->member))), \ + (__iter != NULL && ((item) = json_tree_node_entry(__iter, typeof(*root),\ + member))); \ + __iter = __tmp_iter) + +#ifdef __cplusplus +} +#endif + +#endif /* TARANTOOL_JSON_TREE_H_INCLUDED */ diff --git a/test/unit/json_path.c b/test/unit/json_path.c index 1d7e7d3..fb16162 100644 --- a/test/unit/json_path.c +++ b/test/unit/json_path.c @@ -1,7 +1,9 @@ #include "json/path.h" +#include "json/tree.h" #include "unit.h" #include "trivia/util.h" #include +#include #define reset_to_new_path(value) \ path = value; \ @@ -159,14 +161,220 @@ test_errors() footer(); } +enum tuple_field_type { + TUPLE_FIELD_TYPE_ANY, + TUPLE_FIELD_TYPE_MAP, + TUPLE_FIELD_TYPE_ARRAY, + TUPLE_FIELD_TYPE_OTHER, +}; + +const char *field_type_strs[] = { + /** TUPLE_FIELD_TYPE_ANY */ "any", + /** TUPLE_FIELD_TYPE_MAP */ "map", + /** TUPLE_FIELD_TYPE_ARRAY */ "array", + /** TUPLE_FIELD_TYPE_OTHER */ "other" +}; + +struct tuple_field { + enum tuple_field_type type; + struct json_tree_node tree_node; +}; + +static inline enum tuple_field_type +tuple_field_by_leaf_node_type(enum json_path_type path_type) +{ + if (path_type == JSON_PATH_STR) + return TUPLE_FIELD_TYPE_MAP; + if (path_type == JSON_PATH_NUM) + return TUPLE_FIELD_TYPE_ARRAY; + return TUPLE_FIELD_TYPE_OTHER; +} + +struct tuple_field * +tuple_field_new(struct json_path_node *node, uint32_t node_hash) +{ + struct tuple_field *ret = calloc(1, sizeof(struct tuple_field)); + assert(ret != NULL); + if (json_tree_node_create(&ret->tree_node, node, node_hash) != 0) { + free(ret); + return NULL; + } + ret->type = TUPLE_FIELD_TYPE_ANY; + return ret; +} + +void +tuple_field_delete(struct tuple_field *field) +{ + json_tree_node_destroy(&field->tree_node); + free(field); +} + +int +tuple_field_add_path(struct tuple_field *root, const char *path, + uint32_t path_len, struct tuple_field **leaf) +{ + int rc; + struct json_path_parser parser; + struct json_path_node path_node; + struct tuple_field *field = root; + json_path_parser_create(&parser, path, path_len); + while ((rc = json_path_next(&parser, &path_node)) == 0 && + path_node.type != JSON_PATH_END) { + enum tuple_field_type type = + tuple_field_by_leaf_node_type(path_node.type); + if (field->type != TUPLE_FIELD_TYPE_ANY && field->type != type) + return -1; + uint32_t path_node_hash = json_path_node_hash(&path_node); + struct tuple_field *new_field = + json_tree_lookup_entry(field, &path_node, + path_node_hash, + struct tuple_field, tree_node); + if (new_field == NULL) { + new_field = + tuple_field_new(&path_node, path_node_hash); + assert(new_field != NULL); + rc = json_tree_node_create(&new_field->tree_node, + &path_node, path_node_hash); + assert(rc == 0); + rc = json_tree_add(&field->tree_node, + &new_field->tree_node); + assert(rc == 0); + assert(memcmp(&path_node, &new_field->tree_node.key, + sizeof(path_node)) == 0); + assert(json_tree_lookup_entry(field, &path_node, + path_node_hash, + struct tuple_field, + tree_node) != NULL); + } + field->type = type; + field = new_field; + } + assert(rc == 0 && path_node.type == JSON_PATH_END); + *leaf = field; + return 0; +} + +void +test_tree() +{ + header(); + plan(19); + + struct tuple_field *root_field = tuple_field_new(NULL, 0); + assert(root_field != NULL); + + /* Add paths to tree. */ + int rc = 0; + struct tuple_field *node; + const char *path1 = "[1][10]"; + const char *path2 = "[1].aaa"; + const char *path3 = "[1][100]"; + const char *path4 = "[1][100].a"; + const char *path5 = "[1000].map"; + rc = tuple_field_add_path(root_field, path1, strlen(path1), &node); + is(rc, 0, "add valid path '%s' - normal ret", path1); + isnt(node, NULL, "add valid path '%s' - not NULL pointer", path1); + node->type = TUPLE_FIELD_TYPE_OTHER; + + rc = tuple_field_add_path(root_field, path2, strlen(path2), &node); + isnt(rc, 0, "add path with conflicting interm. node '%s' - error ret", + path2); + assert(rc != 0); + + rc = tuple_field_add_path(root_field, path3, strlen(path3), &node); + is(rc, 0, "add valid path '%s' - normal ret", path3); + isnt(node, NULL, "add valid path '%s' - not NULL pointer", path3); + node->type = TUPLE_FIELD_TYPE_OTHER; + + rc = tuple_field_add_path(root_field, path4, strlen(path4), &node); + isnt(rc, 0, "add path with conflicting leaf node '%s' - error ret", + path4); + + rc = tuple_field_add_path(root_field, path5, strlen(path5), &node); + is(rc, 0, "add path with map container '%s' - normal ret", path5); + isnt(node, NULL, "add path with map container '%s' - not NULL pointer", + path5); + node->type = TUPLE_FIELD_TYPE_OTHER; + + /* Test registered paths. */ + node = json_tree_lookup_path_entry(root_field, path2, strlen(path2), + struct tuple_field, tree_node); + is(node, NULL, "lookup by unregistered path '%s'", path2); + + node = json_tree_lookup_path_entry(root_field, path1, strlen(path1), + struct tuple_field, tree_node); + isnt(node, NULL, "lookup by registered path '%s'", path1); + /* Iterate over tree. */ + int sum = 0; + struct tuple_field *field; + json_tree_foreach_entry(preorder, field, root_field, tree_node) { + if (field->tree_node.key.type == JSON_PATH_NUM) + sum += field->tree_node.key.num; + } + is(sum, 1111, "iterate over the tree and calculate sum"); + if (node != NULL) { + json_tree_remove(node->tree_node.parent, &node->tree_node); + tuple_field_delete(node); + node = json_tree_lookup_path_entry(root_field, path1, strlen(path1), + struct tuple_field, tree_node); + is(node, NULL, "lookup after registered path '%s' deletion", + path1); + } + sum = 0; + json_tree_foreach_entry(postorder, field, root_field, tree_node) { + if (field->tree_node.key.type == JSON_PATH_NUM) + sum += field->tree_node.key.num; + } + is(sum, 1101, "iterate over the tree and calculate sum after leaf " + "deletion"); + + /* Destroy tree. */ + /** + * [1] + * | + * [ ... 10 ... 100 ... 1000] + * | | | + * * # {"map"} + * | + * * + * + * Item marked with # should be already deleted. + */ + enum tuple_field_type destruction_order[] = + {TUPLE_FIELD_TYPE_OTHER, TUPLE_FIELD_TYPE_MAP, + TUPLE_FIELD_TYPE_OTHER, TUPLE_FIELD_TYPE_ARRAY, + TUPLE_FIELD_TYPE_ARRAY}; + int destruction_order_size = + sizeof(destruction_order)/sizeof(destruction_order[0]); + int idx = 0; + json_tree_foreach_entry_safe(postorder, field, root_field, tree_node) { + if (idx > destruction_order_size) + break; + is(field->type, destruction_order[idx], + "destruct valid order - delete record %s, expected %s", + field_type_strs[field->type], + field_type_strs[destruction_order[idx]]); + tuple_field_delete(field); + idx++; + } + is(idx, destruction_order_size, + "valid count of destructed items - have %d, expected %d", + idx, destruction_order_size); + + check_plan(); + footer(); +} + int main() { header(); - plan(2); + plan(3); test_basic(); test_errors(); + test_tree(); int rc = check_plan(); footer(); -- 2.7.4