lyds tree OPTIMIZE data can be unordered
If the LYD_PARSE_ORDERED flag is set incorrectly, the data may be
unordered, a warning will inform about this if the DEBUG variable
is set. But as soon as the lyds tree is created later, the data will
be sorted.
diff --git a/src/tree_data.c b/src/tree_data.c
index 782b118..faeae00 100644
--- a/src/tree_data.c
+++ b/src/tree_data.c
@@ -699,8 +699,13 @@
lyd_insert_node_last(struct lyd_node *parent, struct lyd_node *first_sibling, struct lyd_node *node)
{
if (first_sibling) {
- assert(!lyds_is_supported(node) || (first_sibling->prev->schema != node->schema) ||
- lyds_compare_single(node, first_sibling->prev));
+#ifndef NDEBUG
+ if (lyds_is_supported(node) && (first_sibling->prev->schema == node->schema) &&
+ (lyds_compare_single(first_sibling->prev, node) > 0)) {
+ LOGWRN(LYD_CTX(node), "Data in \"%s\" are not sorted, inserted node should not be added to the end.",
+ node->schema->name);
+ }
+#endif
lyd_insert_after_node(first_sibling->prev, node);
} else if (parent) {
lyd_insert_only_child(parent, node);
diff --git a/src/tree_data_internal.h b/src/tree_data_internal.h
index d3aa1a7..0e0768b 100644
--- a/src/tree_data_internal.h
+++ b/src/tree_data_internal.h
@@ -393,11 +393,8 @@
* @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.
- * 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.
+ * @param[in] last If set, do not search for the correct anchor but always insert at the end. Setting the flag can
+ * break the ordering of nodes for (leaf-)lists that have the LYS_ORDBY_SYSTEM flag set.
*/
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 39b16ef..914327a 100644
--- a/src/tree_data_sorted.c
+++ b/src/tree_data_sorted.c
@@ -668,10 +668,12 @@
*
* @param[in,out] rbt Root of the Red-black tree. After the @p rbn is inserted, the root may change.
* @param[in] rbn Node to insert.
+ * @param[out] max_p Set to 1 if the inserted node will also be maximum.
*/
static void
-rb_insert_node(struct rb_node **rbt, struct rb_node *rbn)
+rb_insert_node(struct rb_node **rbt, struct rb_node *rbn, ly_bool *max_p)
{
+ ly_bool max;
struct rb_node *tmp;
struct rb_node *parent = NULL;
int comp = 0;
@@ -684,6 +686,7 @@
rb_compare = rb_compare_lists;
}
+ max = 1;
tmp = *rbt;
while (tmp != NULL) {
parent = tmp;
@@ -691,6 +694,7 @@
comp = rb_compare(RBN_DNODE(tmp), RBN_DNODE(rbn));
if (comp > 0) {
tmp = RBN_LEFT(tmp);
+ max = 0;
} else {
tmp = RBN_RIGHT(tmp);
}
@@ -709,6 +713,10 @@
}
rb_insert_color(rbt, rbn);
+
+ if (max_p) {
+ *max_p = max;
+ }
}
/**
@@ -932,28 +940,34 @@
/**
* @brief Additionally create the Red-black tree for the sorted nodes.
*
- * @param[in] leader First instance of the (leaf-)list.
+ * @param[in,out] 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)
+lyds_additionally_create_rb_tree(struct lyd_node **leader, struct lyd_meta *root_meta, struct rb_node **rbt)
{
LY_ERR ret;
+ ly_bool max;
struct rb_node *rbn;
struct lyd_node *iter;
/* let's begin with the leader */
- ret = lyds_create_node(leader, &rbn);
+ 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) {
+ 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);
+ rb_insert_node(rbt, rbn, &max);
+ if (!max) {
+ /* nodes were not sorted, they will be sorted now */
+ lyd_unlink_ignore_lyds(iter);
+ lyds_link_data_node(leader, iter, root_meta, rbn);
+ }
}
/* store pointer to the root */
@@ -1019,7 +1033,7 @@
LY_CHECK_RET(ret);
/* insert red-black node with @p node to the Red-black tree */
- rb_insert_node(rbt, *rbn);
+ rb_insert_node(rbt, *rbn, NULL);
return LY_SUCCESS;
}
@@ -1052,7 +1066,7 @@
* 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);
+ ret = lyds_additionally_create_rb_tree(leader, root_meta, &rbt);
LY_CHECK_RET(ret);
}
@@ -1358,6 +1372,10 @@
/* move the rest of the source nodes */
lyds_merge_nodes2_back(dst_iter, next_p);
+ if (*next_p && ((*next_p)->schema == (*leader_dst)->schema)) {
+ ret = lyds_merge_nodes1(leader_dst, root_meta_src, rbt_src, *next_p, next_p);
+ }
+
cleanup:
RBT_SET(root_meta_src, rbt_src);
@@ -1376,8 +1394,9 @@
* @param[in] root_meta_src Metadata 'lyds_tree' from @p leader_src.
* @param[in] rbt_src Root of the source Red-black tree.
* @param[out] next_p Data node located after source (leaf-)list.
+ * @return LY_ERR value.
*/
-static void
+static LY_ERR
lyds_merge_nodes3(struct lyd_node **leader_dst, struct lyd_meta *root_meta_dst, struct rb_node *rbt_dst,
struct lyd_meta *root_meta_src, struct rb_node *rbt_src, struct lyd_node **next_p)
{
@@ -1393,13 +1412,19 @@
node = RBN_DNODE(iter);
*next_p = node->next;
RBN_RESET(iter, node);
- rb_insert_node(&rbt_dst, iter);
+ rb_insert_node(&rbt_dst, iter, NULL);
lyd_unlink_ignore_lyds(node);
lyds_link_data_node(leader_dst, node, root_meta_dst, iter);
lyd_insert_hash(node);
}
- RBT_SET(root_meta_dst, rbt_dst);
+ if (!*next_p || ((*next_p)->schema != (*leader_dst)->schema)) {
+ RBT_SET(root_meta_dst, rbt_dst);
+ } else {
+ LY_CHECK_RET(lyds_merge_nodes1(leader_dst, root_meta_dst, rbt_dst, *next_p, next_p));
+ }
+
+ return LY_SUCCESS;
}
LY_ERR
@@ -1422,7 +1447,7 @@
if (!rbt_dst && !rbt_src) {
/* create RB tree from destination nodes, merge and move source nodes */
LY_CHECK_RET(lyds_create_metadata(*leader_dst, &root_meta_dst));
- LY_CHECK_RET(lyds_additionally_create_rb_tree(*leader_dst, root_meta_dst, &rbt_dst));
+ LY_CHECK_RET(lyds_additionally_create_rb_tree(leader_dst, root_meta_dst, &rbt_dst));
ret = lyds_merge_nodes1(leader_dst, root_meta_dst, rbt_dst, leader_src, next_p);
} else if (rbt_dst && !rbt_src) {
/* just merge and move source nodes */
diff --git a/tests/utests/data/test_tree_data_sorted.c b/tests/utests/data/test_tree_data_sorted.c
index 8b06f4f..de2f121 100644
--- a/tests/utests/data/test_tree_data_sorted.c
+++ b/tests/utests/data/test_tree_data_sorted.c
@@ -1491,6 +1491,55 @@
lyd_free_all(cont);
}
+static void
+test_order_violation(void **state)
+{
+ const char *schema, *data;
+ struct lys_module *mod;
+ struct lyd_node *tree, *node, *dst, *first;
+
+ 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);
+
+ /* inserting a new node causes the nodes to be sorted */
+ data = "{\"a:ll\":[1,8,2]}";
+ 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);
+ assert_string_equal(lyd_get_value(tree), "1");
+ assert_string_equal(lyd_get_value(tree->next), "8");
+ assert_string_equal(lyd_get_value(tree->next->next), "2");
+#ifndef NDEBUG
+ CHECK_LOG_CTX("Data in \"ll\" are not sorted, inserted node should not be added to the end.", NULL, 0);
+#endif
+ assert_int_equal(lyd_new_term(NULL, mod, "ll", "3", 0, &node), LY_SUCCESS);
+ lyd_insert_sibling(tree, node, NULL);
+ assert_string_equal(lyd_get_value(tree), "1");
+ assert_string_equal(lyd_get_value(tree->next), "2");
+ assert_string_equal(lyd_get_value(tree->next->next), "3");
+ assert_string_equal(lyd_get_value(tree->next->next->next), "8");
+ lyd_free_all(tree);
+
+ /* move unsorted nodes causes the nodes to be sorted */
+ data = "{\"a:ll\":[1,8,2]}";
+ CHECK_PARSE_LYD_PARAM(data, LYD_JSON, LYD_PARSE_ORDERED, LYD_VALIDATE_PRESENT, LY_SUCCESS, tree);
+#ifndef NDEBUG
+ CHECK_LOG_CTX("Data in \"ll\" are not sorted, inserted node should not be added to the end.", NULL, 0);
+#endif
+ data = "{\"a:ll\":[7,5]}";
+ CHECK_PARSE_LYD_PARAM(data, LYD_JSON, LYD_PARSE_ORDERED, LYD_VALIDATE_PRESENT, LY_SUCCESS, dst);
+#ifndef NDEBUG
+ CHECK_LOG_CTX("Data in \"ll\" are not sorted, inserted node should not be added to the end.", NULL, 0);
+#endif
+ lyd_insert_sibling(dst, tree, &first);
+ assert_string_equal(lyd_get_value(first), "1");
+ assert_string_equal(lyd_get_value(first->next), "2");
+ assert_string_equal(lyd_get_value(first->next->next), "5");
+ assert_string_equal(lyd_get_value(first->next->next->next), "7");
+ assert_string_equal(lyd_get_value(first->next->next->next->next), "8");
+ lyd_free_all(first);
+}
+
int
main(void)
{
@@ -1530,6 +1579,7 @@
UTEST(test_move_part_list),
UTEST(test_merge_whole_list),
UTEST(test_unlink_siblings),
+ UTEST(test_order_violation),
};
return cmocka_run_group_tests(tests, NULL, NULL);