lyds tree OPTIMIZE flag LYD_PARSE_ORDERED
1. When inserting, the last parameter can also be used for nodes
with lyds_tree
2. The principle of lyds_tree is that it is created lazily.
That is, if it is certain that the nodes are sorted, no metadata
or lyds_tree is created.
3. If it is necessary to modify the sorted nodes, the lyds_tree
is created additionally. This means that inserting the first node
can lead to a delay.
4. The LYD_PARSE_ORDERED flag now has a positive performance effect
because the lyds_tree is created lazily.
diff --git a/src/tree_data.c b/src/tree_data.c
index bfe27dd..44e63f5 100644
--- a/src/tree_data.c
+++ b/src/tree_data.c
@@ -734,10 +734,13 @@
* @param[in] parent Parent to insert into, NULL for top-level sibling.
* @param[in,out] first_sibling First sibling, NULL if no top-level sibling exist yet. Can be also NULL if @p parent is set.
* @param[in] node Individual node (without siblings) to insert.
+ * @param[in] last Trust the caller that the @p node should be inserted last
+ * and the order of the nodes will still be correct.
* @return LY_ERR value.
*/
static LY_ERR
-lyd_insert_node_ordby_lyds(struct lyd_node *parent, struct lyd_node **first_sibling_p, struct lyd_node *node)
+lyd_insert_node_ordby_lyds(struct lyd_node *parent, struct lyd_node **first_sibling_p,
+ struct lyd_node *node, ly_bool last)
{
LY_ERR ret = LY_SUCCESS;
struct lyd_node *anchor, *first_sibling, *leader;
@@ -751,26 +754,23 @@
/* node is alone, no lyds tree is created */
} else if (parent && !first_sibling) {
/* insert as the only child */
- ret = lyds_create_metadata(node);
- LY_CHECK_RET(ret);
lyd_insert_only_child(parent, node);
+ } else if (last) {
+ /* insert as the last node, lyds_tree will be created later */
+ lyd_insert_after_node(first_sibling->prev, node);
+ /* debugging check that the caller has the order correct */
+ assert(!first_sibling->schema || !node->schema || (first_sibling->prev->schema != node->schema) ||
+ (lyds_compare_single(first_sibling->prev, node) <= 0));
} else if (lyd_find_sibling_schema(first_sibling, node->schema, &leader) == LY_SUCCESS) {
/* Found the first instance of (leaf-)list, let's mark it as 'leader'. */
- /* ensure that leader has meta set (use-case for top-level nodes) */
- ret = lyds_create_metadata(leader);
- LY_CHECK_RET(ret);
/* insert @p node to the BST tree and put him in line */
ret = lyds_insert(&leader, node);
LY_CHECK_RET(ret);
} else if ((anchor = lyd_insert_node_find_anchor(first_sibling, node))) {
/* insert before the anchor */
- ret = lyds_create_metadata(node);
- LY_CHECK_RET(ret);
lyd_insert_before_node(anchor, node);
} else {
/* insert as the last node, there is probably no other option */
- ret = lyds_create_metadata(node);
- LY_CHECK_RET(ret);
lyd_insert_after_node(first_sibling->prev, node);
}
@@ -797,7 +797,7 @@
}
if (lyds_is_supported(node)) {
- ret = lyd_insert_node_ordby_lyds(parent, first_sibling_p, node);
+ ret = lyd_insert_node_ordby_lyds(parent, first_sibling_p, node, last);
if (ret) {
/* The operation on the sorting tree unexpectedly failed due to some internal issue,
* but insert the node anyway although the nodes will not be sorted.
@@ -1018,7 +1018,11 @@
/* unlink from the lyds tree */
if (lyds_is_supported(node)) {
- lyd_find_sibling_val(node, node->schema, NULL, 0, &leader);
+ if (LYD_NODE_IS_ALONE(node)) {
+ leader = node;
+ } else {
+ lyd_find_sibling_val(node, node->schema, NULL, 0, &leader);
+ }
lyds_unlink(&leader, node);
}
diff --git a/src/tree_data_free.c b/src/tree_data_free.c
index 188b52c..b1b48b3 100644
--- a/src/tree_data_free.c
+++ b/src/tree_data_free.c
@@ -273,12 +273,7 @@
return;
}
- /* get the first sibling */
- while (node->prev->next) {
- node = node->prev;
- }
-
- LY_LIST_FOR_SAFE(node, next, iter) {
+ LY_LIST_FOR_SAFE(lyd_first_sibling(node), next, iter) {
if (lysc_is_key(iter->schema) && iter->parent) {
LOGERR(LYD_CTX(iter), LY_EINVAL, "Cannot free a list key \"%s\", free the list instance instead.", LYD_NAME(iter));
return;
diff --git a/src/tree_data_internal.h b/src/tree_data_internal.h
index 8f22fac..1cc58c6 100644
--- a/src/tree_data_internal.h
+++ b/src/tree_data_internal.h
@@ -393,8 +393,11 @@
* @param[in] parent Parent to insert into, NULL for top-level sibling.
* @param[in,out] first_sibling First sibling, NULL if no top-level sibling exist yet. Can be also NULL if @p parent is set.
* @param[in] node Individual node (without siblings) to insert.
- * @param[in] last If set, do not search for the correct anchor but always insert at the end. Flag has no effect
- * for (leaf-)list instances that have the LYS_ORDBY_SYSTEM flag set.
+ * @param[in] last If set, do not search for the correct anchor but always insert at the end.
+ * For (leaf-)lists that have the LYS_ORDBY_SYSTEM flag set, the @p last (due to optimization) causes
+ * the sorting tree (lyds_tree) not to be created. However, it is possible to implicitly create
+ * the lyds_tree by inserting another node without setting the @p last. After that, the @p last MUST NOT be
+ * set for a given (leaf-list) instance, as this will cause the order to be corrupted.
*/
void lyd_insert_node(struct lyd_node *parent, struct lyd_node **first_sibling, struct lyd_node *node, ly_bool last);
diff --git a/src/tree_data_sorted.c b/src/tree_data_sorted.c
index 13a0ad5..94f47cc 100644
--- a/src/tree_data_sorted.c
+++ b/src/tree_data_sorted.c
@@ -919,29 +919,52 @@
}
}
+/**
+ * @brief Additionally create the Red-black tree for the sorted nodes.
+ *
+ * @param[in] leader First instance of the (leaf-)list.
+ * @param[in] root_meta From the @p leader, metadata in which is the root of the Red-black tree.
+ * @param[in] rbt From the @p root_meta, root of the Red-black tree.
+ * @return LY_ERR value.
+ */
+static LY_ERR
+lyds_additionally_create_rb_tree(struct lyd_node *leader, struct lyd_meta *root_meta, struct rb_node **rbt)
+{
+ LY_ERR ret;
+ struct rb_node *rbn;
+ struct lyd_node *iter;
+
+ /* let's begin with the leader */
+ ret = lyds_create_node(leader, &rbn);
+ LY_CHECK_RET(ret);
+ *rbt = rbn;
+
+ /* continue with the rest of the nodes */
+ for (iter = leader->next; iter && (iter->schema == leader->schema); iter = iter->next) {
+ ret = lyds_create_node(iter, &rbn);
+ LY_CHECK_RET(ret);
+ rb_insert_node(rbt, rbn);
+ }
+
+ /* store pointer to the root */
+ RBT_SET(root_meta, *rbt);
+
+ return LY_SUCCESS;
+}
+
LY_ERR
-lyds_create_metadata(struct lyd_node *leader)
+lyds_create_metadata(struct lyd_node *leader, struct lyd_meta **meta_p)
{
LY_ERR ret;
uint32_t i;
struct lyd_meta *meta;
- struct rb_node *rbn = NULL, *rbt;
struct lys_module *modyang;
- LY_CHECK_ARG_RET(NULL, leader, leader->schema, LY_EINVAL);
+ assert(leader && (!leader->prev->next || (leader->schema != leader->prev->schema)));
- rbt = lyds_get_rb_tree(leader, &meta);
- if (rbt) {
- /* nothing to do, the metadata is already set */
- return LY_SUCCESS;
- }
- LY_CHECK_RET(!LYD_NODE_IS_ALONE(leader), LY_EINT);
-
+ lyds_get_rb_tree(leader, &meta);
if (meta) {
- /* if the node was duplicated, then the meta is present, but its value is NULL */
- ret = lyds_create_node(leader, &rbn);
- LY_CHECK_RET(ret);
- RBT_SET(meta, rbn);
+ /* nothing to do, the metadata is already set */
return LY_SUCCESS;
}
@@ -954,11 +977,15 @@
}
LY_CHECK_ERR_RET(!modyang, LOGERR(LYD_CTX(leader), LY_EINT, "The yang module is not installed."), LY_EINT);
- /* create new metadata with a root that contains @p leader */
- ret = lyd_create_meta(leader, &meta, modyang, RB_NAME, RB_NAME_LEN, (void *)leader, 0, 0, NULL,
- LY_VALUE_LYB, NULL, LYD_HINT_DATA, leader->schema, 0, NULL);
+ /* create new metadata, its rbt is NULL */
+ ret = lyd_create_meta(leader, &meta, modyang, RB_NAME, RB_NAME_LEN, NULL, 0, 0, NULL,
+ LY_VALUE_CANON, NULL, LYD_HINT_DATA, NULL, 0, NULL);
LY_CHECK_RET(ret);
+ if (meta_p) {
+ *meta_p = meta;
+ }
+
return LY_SUCCESS;
}
@@ -990,41 +1017,43 @@
LY_ERR
lyds_insert(struct lyd_node **leader, struct lyd_node *node)
{
- LY_ERR ret = LY_SUCCESS;
- struct rb_node *rbn, *rbt, *orig_rbt;
+ LY_ERR ret;
+ struct rb_node *rbt, *rbn;
struct lyd_meta *root_meta;
- LY_CHECK_ARG_RET(NULL, leader, node, LY_EINVAL);
+ /* @p node must not be part of another Red-black tree, only single node can satisfy this condition */
+ assert(LYD_NODE_IS_ALONE(node) && leader && node);
- /* check that the @p node has no siblings */
- if (!LYD_NODE_IS_ALONE(node)) {
- /* @p node must not be part of another Red-black tree, only single node can satisfy this condition */
- return LY_EINVAL;
- }
-
- /* Clear the @p node. It may have unnecessary data due to duplication or due to lyds_unlink_node() calls. */
+ /* Clear the @p node. It may have unnecessary data due to duplication or due to lyds_unlink() calls. */
rbt = lyds_get_rb_tree(node, &root_meta);
if (root_meta) {
- assert(!rbt || (!RBN_LEFT(rbt) && !RBN_PARENT(rbt) && !RBN_RIGHT(rbt)));
- /* node has no siblings but contains an empty tree or a tree where it is alone */
+ assert(!rbt || (!RBN_LEFT(rbt) && !RBN_RIGHT(rbt)));
+ /* metadata in @p node will certainly no longer be needed */
lyd_free_meta_single(root_meta);
}
/* get the Red-black tree from the @p leader */
- rbt = orig_rbt = lyds_get_rb_tree(*leader, &root_meta);
- LY_CHECK_ERR_RET(!rbt, LOGWRN(LYD_CTX(node), "Red-black tree not found."), LY_EINT);
-
- /* insert red-black node with @p node to the Red-black tree */
- ret = rb_insert(node, &rbt, &rbn);
- LY_CHECK_RET(ret);
- if (orig_rbt != rbt) {
- /* the root of the Red-black tree has changed due to insertion, so update the pointer to the root */
- RBT_SET(root_meta, rbt);
+ rbt = lyds_get_rb_tree(*leader, &root_meta);
+ if (!root_meta) {
+ lyds_create_metadata(*leader, &root_meta);
+ }
+ if (!rbt) {
+ /* Due to optimization, the Red-black tree has not been created so far, so it will be
+ * created additionally now. It may still not be worth creating a tree and it may be better
+ * to insert the node by linear search instead, but that is a case for further optimization.
+ */
+ ret = lyds_additionally_create_rb_tree(*leader, root_meta, &rbt);
+ LY_CHECK_RET(ret);
}
/* Insert the node to the correct order. */
+ ret = rb_insert(node, &rbt, &rbn);
+ LY_CHECK_RET(ret);
lyds_link_data_node(leader, node, root_meta, rbn);
+ /* the root of the Red-black tree may changed due to insertion, so update the pointer to the root */
+ RBT_SET(root_meta, rbt);
+
return LY_SUCCESS;
}
@@ -1041,11 +1070,8 @@
/* get the Red-black tree from the leader */
rbt = lyds_get_rb_tree(*leader, &root_meta);
- if (LYD_NODE_IS_ALONE(node)) {
- /* node is the leader and it is alone, so free metadata including Red-black tree */
- lyds_get_rb_tree(node, &root_meta);
- /* release the metadata and the Red-black tree. */
- lyd_free_meta_single(root_meta);
+ /* find out if leader_p is alone */
+ if (!root_meta || LYD_NODE_IS_ALONE(*leader)) {
return;
}
@@ -1056,11 +1082,6 @@
rb_remove_node(root_meta, &rbt, node, &removed);
rb_free_node(removed);
-
- if (!rbt) {
- /* the Red-black tree is removed, so delete the metadata too */
- lyd_free_meta_single(root_meta);
- }
}
void
@@ -1073,3 +1094,15 @@
lyd_free_meta_single(root_meta);
}
}
+
+int
+lyds_compare_single(struct lyd_node *node1, struct lyd_node *node2)
+{
+ assert(node1 && node2 && (node1->schema == node2->schema) && lyds_is_supported(node1));
+
+ if (node1->schema->nodetype == LYS_LEAFLIST) {
+ return rb_compare_leaflists(node1, node2);
+ } else {
+ return rb_compare_lists(node1, node2);
+ }
+}
diff --git a/src/tree_data_sorted.h b/src/tree_data_sorted.h
index e3f2903..dfeb719 100644
--- a/src/tree_data_sorted.h
+++ b/src/tree_data_sorted.h
@@ -19,6 +19,7 @@
struct lyd_node;
struct rb_node;
+struct lyd_meta;
/* This functionality applies to list and leaf-list with the "ordered-by system" statement,
* which is implicit. The BST is implemented using a Red-black tree and is used for sorting nodes.
@@ -42,15 +43,14 @@
ly_bool lyds_is_supported(struct lyd_node *node);
/**
- * @brief Create metadata and the BST with @p leader as the root.
+ * @brief Create the 'lyds_tree' metadata.
*
- * Creates the BST and stores it in metadata that is also created or uses an existing one.
- * If the node already contains a BST, then nothing happens.
- *
- * @param[in] leader First and only instance of the (leaf-)list.
+ * @param[in] leader First instance of the (leaf-)list. If the node already contains the metadata,
+ * then nothing happens. The BST is unchanged or empty.
+ * @param[out] meta Newly created 'lyds_tree' metadata.
* @return LY_ERR value.
*/
-LY_ERR lyds_create_metadata(struct lyd_node *leader);
+LY_ERR lyds_create_metadata(struct lyd_node *leader, struct lyd_meta **meta);
/**
* @brief Create new BST node.
@@ -64,14 +64,13 @@
/**
* @brief Insert the @p node into BST and into @p leader's siblings.
*
- * Parameters @p leader and @p node must be from the same context.
- * Sibling data nodes of the @p leader are also modified.
+ * Sibling data nodes of the @p leader are also modified for sorting to take place.
+ * The function automatically take care of lyds_create_metadata() and lyds_create_tree() calls.
+ * Hash for data nodes is not added.
*
- * @param[in,out] leader First instance of the (leaf-)list. Must contain BST and if it doesn't, call
- * lyds_create() first. After executing the function, @p leader does not have to be be first if @p node was
- * inserted before @p leader.
- * @param[in] node A single (without siblings) node or tree to be inserted. It must not be part of another BST
- * and if it is, it must be unlinked first.
+ * @param[in,out] leader First instance of the (leaf-)list. After executing the function,
+ * @p leader does not have to be be first if @p node was inserted before @p leader.
+ * @param[in] node A single (without siblings) node or tree to be inserted. It must be unlinked.
* @return LY_ERR value.
*/
LY_ERR lyds_insert(struct lyd_node **leader, struct lyd_node *node);
@@ -80,7 +79,7 @@
* @brief Unlink (remove) the specified data node from BST.
*
* Pointers in sibling data nodes (lyd_node) are NOT modified. This means that the data node is NOT unlinked.
- * If the BST will remain empty, it will be freed along with the metadata.
+ * Even if the BST will remain empty, lyds_tree metadata will remain.
* Hash for data nodes is not removed.
*
* @param[in,out] leader First instance of (leaf-)list. If it is NULL, nothing happens.
@@ -104,4 +103,15 @@
*/
void lyds_free_tree(struct rb_node *rbt);
+/**
+ * @brief Compare (sort) 2 data nodes.
+ *
+ * @param[in] node1 The first node to compare.
+ * @param[in] node2 The second node to compare.
+ * @return Negative number if val1 < val2,
+ * @return Zero if val1 == val2,
+ * @return Positive number if val1 > val2.
+ */
+int lyds_compare_single(struct lyd_node *node1, struct lyd_node *node2);
+
#endif /* _LYDS_TREE_H_ */
diff --git a/tests/utests/data/test_tree_data_sorted.c b/tests/utests/data/test_tree_data_sorted.c
index 459e844..f68efa2 100644
--- a/tests/utests/data/test_tree_data_sorted.c
+++ b/tests/utests/data/test_tree_data_sorted.c
@@ -305,14 +305,22 @@
"leaf-list ll {type uint32;}}";
UTEST_ADD_MODULE(schema, LYS_IN_YANG, NULL, &mod);
+ /* unlink second then first */
assert_int_equal(lyd_new_term(NULL, mod, "ll", "1", 0, &first), LY_SUCCESS);
assert_int_equal(lyd_new_term(NULL, mod, "ll", "2", 0, &second), LY_SUCCESS);
assert_int_equal(lyd_insert_sibling(first, second, NULL), LY_SUCCESS);
- lyds_unlink(&first, second);
+ lyd_unlink_tree(second);
assert_non_null(first->meta);
- lyds_unlink(&first, first);
- assert_true(!first->meta && !second->meta);
+ lyd_unlink_tree(first);
+ assert_true(first->meta && !second->meta);
+
+ /* unlink first then second */
+ assert_int_equal(lyd_insert_sibling(first, second, NULL), LY_SUCCESS);
+ lyd_unlink_tree(first);
+ assert_true(!first->meta && second->meta);
+
lyd_free_all(first);
+ lyd_free_all(second);
}
static void
@@ -337,14 +345,12 @@
assert_int_equal(lyd_new_term(cont, mod, "lln", "1", 0, NULL), LY_SUCCESS);
node = lyd_child(cont);
- assert_true(node && node->meta);
- assert_string_equal(node->meta->name, META_NAME);
+ assert_true(node && !node->meta);
assert_string_equal(lyd_get_value(node), "1");
assert_int_equal(lyd_new_term(cont, mod, "llm", "2", 0, NULL), LY_SUCCESS);
node = lyd_child(cont);
- assert_true(node && node->meta && node->next);
- assert_string_equal(node->meta->name, META_NAME);
+ assert_true(node && !node->meta && node->next);
assert_string_equal(lyd_get_value(node), "2");
assert_string_equal(lyd_get_value(node->next), "1");
@@ -373,14 +379,12 @@
assert_int_equal(lyd_new_term(cont, mod, "llm", "1", 0, NULL), LY_SUCCESS);
node = lyd_child(cont);
- assert_true(node && node->meta);
- assert_string_equal(node->meta->name, META_NAME);
+ assert_true(node && !node->meta);
assert_string_equal(lyd_get_value(node), "1");
assert_int_equal(lyd_new_term(cont, mod, "lln", "2", 0, NULL), LY_SUCCESS);
node = lyd_child(cont);
- assert_true(node && node->meta && node->next);
- assert_string_equal(node->meta->name, META_NAME);
+ assert_true(node && !node->meta && node->next);
assert_string_equal(lyd_get_value(node), "1");
assert_string_equal(lyd_get_value(node->next), "2");
@@ -401,8 +405,7 @@
assert_int_equal(lyd_new_term(cont, mod, "ll", "1", 0, NULL), LY_SUCCESS);
n1 = lyd_child(cont);
- assert_true(n1 && n1->meta);
- assert_string_equal(n1->meta->name, META_NAME);
+ assert_true(n1 && !n1->meta);
assert_string_equal(lyd_get_value(n1), "1");
assert_int_equal(lyd_new_term(cont, mod, "ll", "1", 0, NULL), LY_SUCCESS);
@@ -431,8 +434,7 @@
assert_int_equal(lyd_new_list(cont, mod, "lst", 0, NULL, "1"), LY_SUCCESS);
n1 = lyd_child(cont);
- assert_true(n1 && n1->meta);
- assert_string_equal(n1->meta->name, META_NAME);
+ assert_true(n1 && !n1->meta);
assert_string_equal(lyd_get_value(lyd_child(n1)), "1");
assert_int_equal(lyd_new_list(cont, mod, "lst", 0, NULL, "1"), LY_SUCCESS);
@@ -525,8 +527,7 @@
assert_int_equal(lyd_new_term(cont, mod, "ll", "2", 0, NULL), LY_SUCCESS);
node = lyd_child(cont);
- assert_true(node && node->meta);
- assert_string_equal(node->meta->name, META_NAME);
+ assert_true(node && !node->meta);
assert_string_equal(lyd_get_value(node), "2");
assert_int_equal(lyd_new_term(cont, mod, "ll", "1", 0, NULL), LY_SUCCESS);
node = lyd_child(cont);
@@ -582,16 +583,17 @@
lyd_unlink_tree(lyd_child(cont));
lyd_unlink_tree(lyd_child(cont));
assert_null(lyd_child(cont));
- assert_true(!first->meta && !second->meta && !third->meta);
+ assert_true(!first->meta && !second->meta && third->meta && get_rbt(third->meta));
+ assert_string_equal(third->meta->name, META_NAME);
- /* insert first */
- lyd_insert_child(cont, first);
- assert_non_null(first->meta);
- assert_string_equal(first->meta->name, META_NAME);
+ /* insert third */
+ lyd_insert_child(cont, third);
+ assert_non_null(third->meta);
+ assert_string_equal(third->meta->name, META_NAME);
lyd_free_all(cont);
+ lyd_free_all(first);
lyd_free_all(second);
- lyd_free_all(third);
}
static void
@@ -728,15 +730,15 @@
/* create duplicate */
assert_int_equal(lyd_dup_single(cont, NULL, LYD_DUP_RECURSIVE, &dup), LY_SUCCESS);
node = lyd_child(dup);
- assert_true(node && node->next && get_rbt(node->meta));
+ assert_true(node && node->next && !get_rbt(node->meta));
assert_string_equal(node->meta->name, META_NAME);
- assert_ptr_not_equal(get_rbt(node->meta), get_rbt(lyd_child(cont)->meta));
/* insert into duplicate */
assert_int_equal(lyd_new_term(dup, mod, "ll", "2", 0, NULL), LY_SUCCESS);
assert_non_null(node->next->next);
assert_string_equal(lyd_get_value(node), "1");
assert_string_equal(lyd_get_value(node->next), "2");
assert_string_equal(lyd_get_value(node->next->next), "3");
+ assert_non_null(get_rbt(node->meta));
lyd_free_all(cont);
lyd_free_all(dup);
}
@@ -757,10 +759,11 @@
assert_int_equal(lyd_new_term(cont, mod, "ll", "3", 0, NULL), LY_SUCCESS);
assert_int_equal(lyd_dup_siblings(cont, NULL, LYD_DUP_NO_META | LYD_DUP_RECURSIVE, &dup), LY_SUCCESS);
node = lyd_child(dup);
- assert_true(node && get_rbt(node->meta));
- assert_string_equal(node->meta->name, META_NAME);
+ assert_true(node && !node->meta);
assert_int_equal(lyd_new_term(dup, mod, "ll", "1", 0, NULL), LY_SUCCESS);
node = lyd_child(dup);
+ assert_non_null(node->meta && get_rbt(node->meta));
+ assert_string_equal(node->meta->name, META_NAME);
assert_string_equal(lyd_get_value(node), "1");
lyd_free_all(cont);
@@ -768,6 +771,34 @@
}
static void
+test_free_meta_single(void **state)
+{
+ const char *schema;
+ struct lys_module *mod;
+ struct lyd_node *first, *second, *third;
+
+ schema = "module a {namespace urn:tests:a;prefix a;yang-version 1.1;revision 2014-05-08;"
+ "leaf-list ll {type uint32;}}";
+ UTEST_ADD_MODULE(schema, LYS_IN_YANG, NULL, &mod);
+
+ /* user free metadata with lyds tree but it will created again */
+ assert_int_equal(lyd_new_term(NULL, mod, "ll", "7", 0, &first), LY_SUCCESS);
+ assert_int_equal(lyd_new_term(NULL, mod, "ll", "8", 0, &second), LY_SUCCESS);
+ assert_int_equal(lyd_insert_sibling(first, second, NULL), LY_SUCCESS);
+ assert_non_null(first->meta);
+ assert_string_equal(first->meta->name, META_NAME);
+ lyd_free_meta_single(first->meta);
+ assert_int_equal(lyd_new_term(NULL, mod, "ll", "6", 0, &third), LY_SUCCESS);
+ lyd_insert_sibling(first, third, NULL);
+ assert_string_equal(lyd_get_value(first->prev), "6");
+ assert_string_equal(lyd_get_value(first), "7");
+ assert_string_equal(lyd_get_value(first->next), "8");
+ assert_non_null(first->prev->meta);
+ assert_string_equal(first->prev->meta->name, META_NAME);
+ lyd_free_all(first->prev);
+}
+
+static void
test_no_metadata_remains(void **state)
{
const char *schema;
@@ -906,7 +937,7 @@
assert_string_equal(lyd_get_value(f2->next->next->next), "22");
lyd_free_all(f2);
- /* only source tree have metadata */
+ /* only target tree have metadata */
assert_int_equal(lyd_new_term(NULL, mod, "ll", "1", 0, &f1), LY_SUCCESS);
assert_null(f1->meta);
assert_int_equal(lyd_new_term(NULL, mod, "ll", "21", 0, &f2), LY_SUCCESS);
@@ -914,7 +945,7 @@
assert_int_equal(lyd_insert_sibling(f2, s2, NULL), LY_SUCCESS);
assert_non_null(f2->meta);
assert_int_equal(lyd_merge_siblings(&f2, f1, 0), LY_SUCCESS);
- assert_true(f2->meta && f2->next && f2->next->next);
+ assert_true(f2->meta && f2->next);
assert_string_equal(f2->meta->name, META_NAME);
assert_string_equal(lyd_get_value(f2), "1");
assert_string_equal(lyd_get_value(f2->next), "21");
@@ -922,7 +953,7 @@
lyd_free_all(f1);
lyd_free_all(f2);
- /* only target tree have metadata */
+ /* only source tree have metadata */
assert_int_equal(lyd_new_term(NULL, mod, "ll", "1", 0, &f1), LY_SUCCESS);
assert_int_equal(lyd_new_term(NULL, mod, "ll", "2", 0, &s1), LY_SUCCESS);
assert_int_equal(lyd_insert_sibling(f1, s1, NULL), LY_SUCCESS);
@@ -994,6 +1025,46 @@
}
static void
+test_parse_ordered_data(void **state)
+{
+ const char *schema, *data;
+ struct lys_module *mod;
+ struct lyd_node *tree, *node;
+
+ schema = "module a {namespace urn:tests:a;prefix a;yang-version 1.1;revision 2014-05-08;"
+ "leaf-list ll {type uint32;}}";
+ UTEST_ADD_MODULE(schema, LYS_IN_YANG, NULL, &mod);
+
+ data = "{\"a:ll\":[1,2,3]}";
+ CHECK_PARSE_LYD_PARAM(data, LYD_JSON, LYD_PARSE_ORDERED, LYD_VALIDATE_PRESENT, LY_SUCCESS, tree);
+ assert_true(tree && !tree->meta && tree->next && tree->next->next);
+ CHECK_LYD_VALUE(((struct lyd_node_term *)tree)->value, UINT32, "1", 1);
+
+ /* unlink node with value 2 */
+ node = tree->next;
+ lyd_unlink_tree(node);
+ assert_true(tree && !tree->meta && tree->next);
+ lyd_free_all(node);
+
+ /* unlink node with value 1 */
+ node = tree;
+ tree = tree->next;
+ assert_null(tree->meta);
+ lyd_unlink_tree(node);
+ assert_true(tree && !tree->meta && !tree->next);
+
+ /* insert node with value 1 to node with value 3 */
+ lyd_insert_sibling(tree, node, NULL);
+ tree = tree->prev;
+ assert_true(tree && tree->meta && tree->next && !tree->next->meta && get_rbt(tree->meta));
+ assert_string_equal(tree->meta->name, META_NAME);
+ assert_string_equal(lyd_get_value(tree), "1");
+ assert_string_equal(lyd_get_value(tree->next), "3");
+
+ lyd_free_all(tree);
+}
+
+static void
test_print_data(void **state)
{
const char *schema, *exp;
@@ -1129,9 +1200,11 @@
UTEST(test_insert_into_duplicate),
UTEST(test_option_dup_no_meta),
UTEST(test_no_metadata_remains),
+ UTEST(test_free_meta_single),
UTEST(test_insert_multiple_keys),
UTEST(test_merge_siblings),
UTEST(test_parse_data),
+ UTEST(test_parse_ordered_data),
UTEST(test_print_data),
UTEST(test_manipulation_of_many_nodes),
UTEST(test_lyds_free_metadata),