tree data OPTIMIZE unlink-insert for lyds nodes
Unlink and then insert is inefficient for sorted (lyds) list and
leaf-list nodes. Also improved lyd_unlink_siblings().
diff --git a/src/tree_data.c b/src/tree_data.c
index 9332ca8..782b118 100644
--- a/src/tree_data.c
+++ b/src/tree_data.c
@@ -775,6 +775,180 @@
}
/**
+ * @brief Check that @p node can be unlinked.
+ *
+ * @param[in] node Node to check
+ * @return LY_ERR value.
+ */
+static LY_ERR
+lyd_unlink_check(struct lyd_node *node)
+{
+ if (!node) {
+ return LY_SUCCESS;
+ }
+
+ if (lysc_is_key(node->schema) && node->parent) {
+ LOGERR(LYD_CTX(node), LY_EINVAL, "Cannot unlink a list key \"%s\", unlink the list instance instead.",
+ LYD_NAME(node));
+ return LY_EINVAL;
+ }
+
+ return LY_SUCCESS;
+}
+
+/**
+ * @brief Move schema instances before anchor or as the last.
+ *
+ * The nodes will remain sorted according to the schema.
+ *
+ * @param[in] first_sibling First sibling, destination.
+ * @param[in] node Starting node, all following nodes with the same schema will be moved.
+ * @param[out] next_p Next node that has a different schema or NULL.
+ * @return LY_ERR value.
+ */
+static LY_ERR
+lyd_move_nodes_ordby_schema(struct lyd_node *first_sibling, struct lyd_node *node, struct lyd_node **next_p)
+{
+ struct lyd_node *second, *anchor, *iter, *next, *dst, *src;
+
+ assert(first_sibling && !first_sibling->prev->next && node && next_p);
+
+ if ((anchor = lyd_insert_node_find_anchor(first_sibling, node))) {
+ /* move the first node to the correct place according to the schema */
+ LY_CHECK_RET(lyd_unlink_check(node));
+ second = node->next;
+ lyd_unlink_ignore_lyds(node);
+ lyd_insert_before_node(anchor, node);
+ lyd_insert_hash(node);
+ if (!second || (node->schema != second->schema)) {
+ /* no more nodes to move */
+ *next_p = second;
+ return LY_SUCCESS;
+ }
+ dst = node;
+ src = second;
+ } else {
+ /* just move all instances to the end */
+ dst = first_sibling->prev;
+ src = node;
+ }
+
+ /* move the rest of source instances after @p node */
+ LY_LIST_FOR_SAFE(src, next, iter) {
+ LY_CHECK_RET(lyd_unlink_check(iter));
+ if (iter->schema != src->schema) {
+ break;
+ }
+ lyd_unlink_ignore_lyds(iter);
+ lyd_insert_after_node(dst, iter);
+ lyd_insert_hash(iter);
+ dst = iter;
+ }
+ *next_p = iter;
+
+ return LY_SUCCESS;
+}
+
+/**
+ * @brief Move nodes regardless of schema.
+ *
+ * The destination for the move is NULL, or a childless parent.
+ *
+ * @param[in] parent Parent to insert into, NULL for top-level sibling.
+ * @param[in] first_src First sibling, all following nodes will be moved.
+ * @return LY_ERR value.
+ */
+static LY_ERR
+lyd_move_nodes_at_once(struct lyd_node *parent, struct lyd_node *first_src)
+{
+ struct lyd_node *start, *next, *iter;
+
+ assert(!lyd_child(parent) && first_src && !first_src->prev->next && !first_src->parent);
+
+ LY_CHECK_RET(lyd_unlink_check(first_src));
+
+ /* move the first node */
+ start = first_src->next;
+ if (parent) {
+ lyd_unlink_ignore_lyds(first_src);
+ lyd_insert_only_child(parent, first_src);
+ lyd_insert_hash(first_src);
+ } else {
+ lyd_unlink_ignore_lyds(first_src);
+ }
+
+ /* move the rest of the nodes */
+ LY_LIST_FOR_SAFE(start, next, iter) {
+ LY_CHECK_RET(lyd_unlink_check(iter));
+ lyd_unlink_ignore_lyds(iter);
+ lyd_insert_after_node(first_src->prev, iter);
+ lyd_insert_hash(iter);
+ }
+
+ return LY_SUCCESS;
+}
+
+/**
+ * @brief Move the nodes in parts according to the schema.
+ *
+ * @param[in] first_sibling First sibling, destination.
+ * @param[in] first_src First sibling, all following nodes will be moved.
+ * @return LY_ERR value.
+ */
+static LY_ERR
+lyd_move_nodes_by_schema(struct lyd_node *first_sibling, struct lyd_node *first_src)
+{
+ LY_ERR ret;
+ struct lyd_node *next, *iter, *leader;
+
+ assert(first_sibling && !first_sibling->prev->next && first_src && !first_src->prev->next && !first_src->parent);
+
+ for (iter = first_src; iter; iter = next) {
+ if (lyds_is_supported(iter) &&
+ (lyd_find_sibling_schema(first_sibling, iter->schema, &leader) == LY_SUCCESS)) {
+ ret = lyds_merge(&leader, iter, &next);
+ 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.
+ */
+ LOGWRN(LYD_CTX(first_src), "Data in \"%s\" are not sorted.", leader->schema->name);
+ LY_CHECK_RET(lyd_move_nodes_ordby_schema(first_sibling, next, &next));
+ }
+ } else {
+ LY_CHECK_RET(lyd_move_nodes_ordby_schema(first_sibling, iter, &next));
+ }
+ first_sibling = iter->prev->next ? first_sibling : iter;
+ }
+
+ return LY_SUCCESS;
+}
+
+/**
+ * @brief Move a nodes into parent/siblings.
+ *
+ * @param[in] parent Parent to insert into, NULL for top-level sibling.
+ * @param[in] first_sibling First sibling, NULL if no top-level sibling exist yet. Can be also NULL if @p parent is set.
+ * @param[in] first_src First sibling, all following nodes will be moved.
+ * @return LY_ERR value.
+ */
+static LY_ERR
+lyd_move_nodes(struct lyd_node *parent, struct lyd_node *first_sibling, struct lyd_node *first_src)
+{
+ LY_ERR ret;
+
+ assert(first_src && (!first_sibling || !first_sibling->prev->next) && !first_src->prev->next);
+
+ first_sibling = first_sibling ? first_sibling : lyd_child(parent);
+ if (!first_sibling) {
+ ret = lyd_move_nodes_at_once(parent, first_src);
+ } else {
+ ret = lyd_move_nodes_by_schema(first_sibling, first_src);
+ }
+
+ return ret;
+}
+
+/**
* @brief Check schema place of a node to be inserted.
*
* @param[in] parent Schema node of the parent data node.
@@ -825,28 +999,18 @@
LIBYANG_API_DEF LY_ERR
lyd_insert_child(struct lyd_node *parent, struct lyd_node *node)
{
- struct lyd_node *iter;
-
LY_CHECK_ARG_RET(NULL, parent, node, !parent->schema || (parent->schema->nodetype & LYD_NODE_INNER), LY_EINVAL);
LY_CHECK_CTX_EQUAL_RET(LYD_CTX(parent), LYD_CTX(node), LY_EINVAL);
LY_CHECK_RET(lyd_insert_check_schema(parent->schema, NULL, node->schema));
- if (node->schema && (node->schema->flags & LYS_KEY)) {
- LOGERR(LYD_CTX(parent), LY_EINVAL, "Cannot insert key \"%s\".", node->schema->name);
- return LY_EINVAL;
- }
-
- if (node->parent || node->prev->next) {
- lyd_unlink(node);
- }
-
- while (node) {
- iter = node->next;
- lyd_unlink(node);
+ if (node->parent || node->prev->next || !node->next) {
+ lyd_unlink_tree(node);
lyd_insert_node(parent, NULL, node, 0);
- node = iter;
+ } else {
+ lyd_move_nodes(parent, NULL, node);
}
+
return LY_SUCCESS;
}
@@ -875,7 +1039,7 @@
LIBYANG_API_DEF LY_ERR
lyd_insert_sibling(struct lyd_node *sibling, struct lyd_node *node, struct lyd_node **first)
{
- struct lyd_node *iter;
+ struct lyd_node *first_sibling;
LY_CHECK_ARG_RET(NULL, node, LY_EINVAL);
@@ -883,30 +1047,16 @@
LY_CHECK_RET(lyd_insert_check_schema(NULL, sibling->schema, node->schema));
}
- sibling = lyd_first_sibling(sibling);
-
- if (node->parent || node->prev->next) {
- lyd_unlink(node);
- }
-
- while (node) {
- if (lysc_is_key(node->schema)) {
- LOGERR(LYD_CTX(node), LY_EINVAL, "Cannot insert key \"%s\".", node->schema->name);
- return LY_EINVAL;
- }
-
- iter = node->next;
- lyd_unlink(node);
- lyd_insert_node(NULL, &sibling, node, 0);
- node = iter;
+ first_sibling = lyd_first_sibling(sibling);
+ if (node->parent || node->prev->next || !node->next) {
+ lyd_unlink_tree(node);
+ lyd_insert_node(NULL, &first_sibling, node, 0);
+ } else {
+ lyd_move_nodes(NULL, first_sibling, node);
}
if (first) {
- /* find the first sibling */
- *first = sibling;
- while ((*first)->prev->next) {
- *first = (*first)->prev;
- }
+ *first = node->prev->next ? first_sibling : node;
}
return LY_SUCCESS;
@@ -961,23 +1111,9 @@
}
void
-lyd_unlink(struct lyd_node *node)
+lyd_unlink_ignore_lyds(struct lyd_node *node)
{
- struct lyd_node *iter, *leader;
-
- if (!node) {
- return;
- }
-
- /* unlink from the lyds tree */
- if (lyds_is_supported(node)) {
- if (LYD_NODE_IS_ALONE(node)) {
- leader = node;
- } else {
- lyd_find_sibling_val(node, node->schema, NULL, 0, &leader);
- }
- lyds_unlink(&leader, node);
- }
+ struct lyd_node *iter;
/* update hashes while still linked into the tree */
lyd_unlink_hash(node);
@@ -1024,32 +1160,59 @@
node->prev = node;
}
+void
+lyd_unlink(struct lyd_node *node)
+{
+ struct lyd_node *leader;
+
+ if (!node) {
+ return;
+ }
+
+ /* unlink from the lyds tree */
+ if (lyds_is_supported(node)) {
+ if (!node->prev->next || (node->prev->schema != node->schema)) {
+ leader = node;
+ } else {
+ lyd_find_sibling_val(node, node->schema, NULL, 0, &leader);
+ assert(leader);
+ }
+ lyds_unlink(&leader, node);
+ }
+
+ /* unlink data tree */
+ lyd_unlink_ignore_lyds(node);
+}
+
LIBYANG_API_DEF void
lyd_unlink_siblings(struct lyd_node *node)
{
- struct lyd_node *next, *elem, *first = NULL;
+ struct lyd_node *next, *iter, *leader, *start;
- LY_LIST_FOR_SAFE(node, next, elem) {
- if (lysc_is_key(elem->schema) && elem->parent) {
- LOGERR(LYD_CTX(elem), LY_EINVAL, "Cannot unlink a list key \"%s\", unlink the list instance instead.",
- LYD_NAME(elem));
- return;
- }
+ if (lyds_is_supported(node) && node->prev->next && (node->prev->schema == node->schema)) {
+ /* unlink starts at the non-first item in the (leaf-)list */
+ lyd_find_sibling_val(node, node->schema, NULL, 0, &leader);
+ lyds_split(leader, node, &start);
+ } else {
+ /* unlink @p node */
+ LY_CHECK_RET(lyd_unlink_check(node), );
+ start = node->next;
+ lyd_unlink_ignore_lyds(node);
+ }
- lyd_unlink(elem);
- lyd_insert_node(NULL, &first, elem, 1);
+ /* continue unlinking the rest */
+ LY_LIST_FOR_SAFE(start, next, iter) {
+ LY_CHECK_RET(lyd_unlink_check(iter), );
+ lyd_unlink_ignore_lyds(iter);
+ lyd_insert_after_node(node->prev, iter);
+ lyd_insert_hash(iter);
}
}
LIBYANG_API_DEF void
lyd_unlink_tree(struct lyd_node *node)
{
- if (node && lysc_is_key(node->schema) && node->parent) {
- LOGERR(LYD_CTX(node), LY_EINVAL, "Cannot unlink a list key \"%s\", unlink the list instance instead.",
- LYD_NAME(node));
- return;
- }
-
+ LY_CHECK_RET(lyd_unlink_check(node), );
lyd_unlink(node);
}
diff --git a/src/tree_data_free.c b/src/tree_data_free.c
index b1b48b3..d76a4aa 100644
--- a/src/tree_data_free.c
+++ b/src/tree_data_free.c
@@ -282,7 +282,7 @@
/* in case of the top-level nodes (node->parent is NULL), no unlinking needed */
if (iter->parent) {
lyds_free_metadata(iter);
- lyd_unlink(iter);
+ lyd_unlink_ignore_lyds(iter);
}
lyd_free_subtree(iter);
}
diff --git a/src/tree_data_internal.h b/src/tree_data_internal.h
index 1cc58c6..d3aa1a7 100644
--- a/src/tree_data_internal.h
+++ b/src/tree_data_internal.h
@@ -665,4 +665,13 @@
*/
LY_ERR lyd_unlink_leafref_node(const struct lyd_node_term *node, const struct lyd_node_term *leafref_node);
+/**
+ * @brief Unlink the specified data subtree.
+ *
+ * The lyds_unlink() is NOT called in this function.
+ *
+ * @param[in] node Data tree node to be unlinked (together with all the children).
+ */
+void lyd_unlink_ignore_lyds(struct lyd_node *node);
+
#endif /* LY_TREE_DATA_INTERNAL_H_ */
diff --git a/src/tree_data_sorted.c b/src/tree_data_sorted.c
index 94f47cc..39b16ef 100644
--- a/src/tree_data_sorted.c
+++ b/src/tree_data_sorted.c
@@ -118,6 +118,16 @@
RBN_COLOR(DST) = RBN_COLOR(SRC);
/**
+ * @brief Reset the red-black node and set new dnode.
+ *
+ * @param[in] RBN Node to reset.
+ * @param[in] DNODE New dnode value for @p rbn.
+ */
+#define RBN_RESET(RBN, DNODE) \
+ *(RBN) = (const struct rb_node){0}; \
+ RBN_DNODE(RBN) = DNODE;
+
+/**
* @brief Metadata name of the Red-black tree.
*/
#define RB_NAME "lyds_tree"
@@ -1085,6 +1095,67 @@
}
void
+lyds_split(struct lyd_node *leader, struct lyd_node *node, struct lyd_node **next_p)
+{
+ struct rb_node *rbt, *rbn;
+ struct lyd_node *iter, *next, *start, *dst;
+ struct lyd_meta *root_meta;
+
+ assert(leader && node);
+
+ rbt = lyds_get_rb_tree(leader, &root_meta);
+ if (!rbt || (leader == node)) {
+ /* Second list is just unlinked */
+ start = node->next;
+ lyd_unlink_ignore_lyds(node);
+ dst = node;
+ LY_LIST_FOR_SAFE(start, next, iter) {
+ if (iter->schema != node->schema) {
+ break;
+ }
+ lyd_unlink_ignore_lyds(iter);
+ lyd_insert_after_node(dst, iter);
+ dst = iter;
+ }
+ *next_p = iter;
+ return;
+ }
+
+ start = node->next;
+ if (!start || (start->schema != node->schema)) {
+ /* @p node is the last node, remove from Red-black tree and unlink */
+ rb_remove_node(root_meta, &rbt, node, &rbn);
+ rb_free_node(rbn);
+ lyd_unlink_ignore_lyds(node);
+ *next_p = start;
+ goto cleanup;
+ }
+
+ /* remove @p node from Red-black tree and unlink */
+ rb_remove_node(root_meta, &rbt, node, &rbn);
+ rb_free_node(rbn);
+ lyd_unlink_ignore_lyds(node);
+
+ /* remove the rest of nodes from Red-black tree and unlink */
+ dst = node;
+ LY_LIST_FOR_SAFE(start, next, iter) {
+ if (iter->schema != node->schema) {
+ break;
+ }
+ rb_remove_node(root_meta, &rbt, iter, &rbn);
+ rb_free_node(rbn);
+ lyd_unlink_ignore_lyds(iter);
+ /* insert them to the second (leaf-)list */
+ lyd_insert_after_node(dst, iter);
+ dst = iter;
+ }
+ *next_p = iter;
+
+cleanup:
+ RBT_SET(root_meta, rbt);
+}
+
+void
lyds_free_metadata(struct lyd_node *node)
{
struct lyd_meta *root_meta;
@@ -1095,6 +1166,280 @@
}
}
+/**
+ * @brief Merge nodes (src) without Red-black tree into (dst) nodes with Red-black tree.
+ *
+ * @param[in,out] leader_dst First instance of the destination (leaf-)list.
+ * @param[in] root_meta_dst Metadata 'lyds_tree' from @p leader_dst.
+ * @param[in] rbt_dst Root of the destination Red-black tree.
+ * @param[in] leader_src First instance of the source (leaf-)list.
+ * @param[out] next_p Data node located after source (leaf-)list.
+ * On error, it points to the some node in source (leaf-)list that failed to merge.
+ * @return LY_ERR value.
+ */
+static LY_ERR
+lyds_merge_nodes1(struct lyd_node **leader_dst, struct lyd_meta *root_meta_dst, struct rb_node *rbt_dst,
+ struct lyd_node *leader_src, struct lyd_node **next_p)
+{
+ LY_ERR ret;
+ struct rb_node *rbn;
+ struct lyd_node *iter, *next;
+ const struct lysc_node *schema;
+
+ schema = leader_src->schema;
+ for (iter = leader_src; iter && (iter->schema == schema); iter = next) {
+ ret = rb_insert(iter, &rbt_dst, &rbn);
+ if (ret) {
+ /* allocation failed, @p next_p must refer to failed node */
+ break;
+ }
+ next = iter->next;
+ lyd_unlink_ignore_lyds(iter);
+ lyds_link_data_node(leader_dst, iter, root_meta_dst, rbn);
+ lyd_insert_hash(iter);
+ }
+ *next_p = iter;
+
+ RBT_SET(root_meta_dst, rbt_dst);
+
+ return LY_SUCCESS;
+}
+
+/**
+ * @brief Merge nodes which belongs before @p leader_dst.
+ *
+ * Reminder:
+ * Merge nodes (src) with Red-black tree into (dst) nodes without Red-black tree.
+ * Create red-black nodes from destination (leaf-)list and insert them into @p rbt_src.
+ * At the end of the lyds_merge_nodes2(), rbt_src will move and become rbt_dst.
+ *
+ * @param[in,out] leader_dst First instance of the destination (leaf-)list.
+ * @param[in] leader_src First instance of the source (leaf-)list.
+ * @param[in,out] rbt_src Root of the source Red-black tree.
+ * @param[out] dst_iter Last merged node into the @p rbt_src.
+ * @param[out] next_p On error, points to data node which failed to merge.
+ * @return LY_ERR value.
+ */
+static LY_ERR
+lyds_merge_nodes2_front(struct lyd_node **leader_dst, struct lyd_node *leader_src,
+ struct rb_node **rbt_src, struct rb_node **dst_iter, struct lyd_node **next_p)
+{
+ LY_ERR ret;
+ struct rb_node *prev, *iter;
+ struct lyd_node *dst;
+
+ /* insert destination leader */
+ ret = rb_insert(*leader_dst, rbt_src, dst_iter);
+ LY_CHECK_ERR_RET(ret, *next_p = leader_src, ret);
+
+ /* iterate over source RB tree and move the nodes belonging before destination leader */
+ prev = rb_prev(*dst_iter);
+ dst = *leader_dst;
+ for (iter = prev; iter; iter = rb_prev(iter)) {
+ lyd_unlink_ignore_lyds(RBN_DNODE(iter));
+ lyd_insert_before_node(dst, RBN_DNODE(iter));
+ lyd_insert_hash(RBN_DNODE(iter));
+ dst = RBN_DNODE(iter);
+ }
+ if (prev) {
+ *leader_dst = dst;
+ }
+
+ return LY_SUCCESS;
+}
+
+/**
+ * @brief Merge nodes which belongs between destination (leaf-)list nodes.
+ *
+ * Reminder:
+ * Merge nodes (src) with Red-black tree into (dst) nodes without Red-black tree.
+ * Create red-black nodes from destination (leaf-)list and insert them into @p rbt_src.
+ * At the end of the lyds_merge_nodes2(), rbt_src will move and become rbt_dst.
+ *
+ * @param[in,out] leader_dst First instance of the destination (leaf-)list.
+ * @param[in,out] rbt_src Root of the source Red-black tree.
+ * @param[out] dst_iter Last merged node into the @p rbt_src.
+ * @param[out] next_p On error, points to data node which failed to merge.
+ * @return LY_ERR value.
+ */
+static LY_ERR
+lyds_merge_nodes2_among(struct lyd_node **leader_dst, struct rb_node **rbt_src, struct rb_node **dst_iter,
+ struct lyd_node **next_p)
+{
+ LY_ERR ret;
+ struct rb_node *rbn, *iter, *rbn_prev;
+ struct lyd_node *dst, *node;
+ const struct lysc_node *schema;
+
+ schema = (*leader_dst)->schema;
+ rbn = *dst_iter;
+ for (node = RBN_DNODE(*dst_iter); node->next && (node->schema == schema); node = dst->next) {
+ /* insert node from destination (leaf-)list into @p rbt_src */
+ rbn_prev = rbn;
+ ret = rb_insert(node->next, rbt_src, &rbn);
+ LY_CHECK_ERR_RET(ret, *next_p = RBN_DNODE(rb_next(rbn_prev)), ret);
+
+ dst = node;
+ /* move source data nodes between next-to-last inserted node and last inserted node */
+ for (iter = rb_next(rbn_prev); iter != rbn; iter = rb_next(iter)) {
+ lyd_unlink_ignore_lyds(RBN_DNODE(iter));
+ /* insert source data nodes into destination (leaf-)list */
+ lyd_insert_after_node(dst, RBN_DNODE(iter));
+ lyd_insert_hash(RBN_DNODE(iter));
+ dst = RBN_DNODE(iter);
+ }
+ }
+ *dst_iter = rbn;
+
+ return LY_SUCCESS;
+}
+
+/**
+ * @brief Merge nodes which belongs after destination (leaf-)list nodes.
+ *
+ * Reminder:
+ * Merge nodes (src) with Red-black tree into (dst) nodes without Red-black tree.
+ * Create red-black nodes from destination (leaf-)list and insert them into @p rbt_src.
+ * At the end of the lyds_merge_nodes2(), rbt_src will move and become rbt_dst.
+ *
+ * @param[in] dst_iter Last merged node into the @p rbt_src.
+ * @param[out] next_p Data node located after source (leaf-)list.
+ */
+static void
+lyds_merge_nodes2_back(struct rb_node *dst_iter, struct lyd_node **next_p)
+{
+ struct rb_node *iter, *begin;
+ struct lyd_node *dst;
+
+ begin = rb_next(dst_iter);
+ LY_CHECK_RET(!begin,; );
+ dst = RBN_DNODE(dst_iter);
+ for (iter = begin; iter; iter = rb_next(iter)) {
+ *next_p = RBN_DNODE(iter)->next;
+ lyd_unlink_ignore_lyds(RBN_DNODE(iter));
+ lyd_insert_after_node(dst, RBN_DNODE(iter));
+ lyd_insert_hash(RBN_DNODE(iter));
+ dst = RBN_DNODE(iter);
+ }
+}
+
+/**
+ * @brief Merge nodes (src) with Red-black tree into (dst) nodes without Red-black tree.
+ *
+ * Create red-black nodes from destination (leaf-)list and insert them into @p rbt_src.
+ * At the end of the lyds_merge_nodes2(), rbt_src will move and become rbt_dst.
+ *
+ * @param[in,out] leader_dst First instance of the destination (leaf-)list.
+ * @param[in] leader_src First instance of the source (leaf-)list.
+ * @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.
+ * On error, points to data node which failed to merge.
+ * @return LY_ERR value.
+ */
+static LY_ERR
+lyds_merge_nodes2(struct lyd_node **leader_dst, struct lyd_node *leader_src, struct lyd_meta *root_meta_src,
+ struct rb_node *rbt_src, struct lyd_node **next_p)
+{
+ LY_ERR ret;
+ struct rb_node *dst_iter;
+
+ /* merge first destination node, move source nodes which belongs before this node */
+ ret = lyds_merge_nodes2_front(leader_dst, leader_src, &rbt_src, &dst_iter, next_p);
+ LY_CHECK_GOTO(ret, cleanup);
+
+ /* RB tree si moved from source to destination (leaf-)list */
+ lyds_move_meta(*leader_dst, root_meta_src);
+
+ /* merge the rest of the destination nodes, move corresponding source nodes */
+ ret = lyds_merge_nodes2_among(leader_dst, &rbt_src, &dst_iter, next_p);
+ LY_CHECK_GOTO(ret, cleanup);
+
+ /* move the rest of the source nodes */
+ lyds_merge_nodes2_back(dst_iter, next_p);
+
+cleanup:
+ RBT_SET(root_meta_src, rbt_src);
+
+ return ret;
+}
+
+/**
+ * @brief Merge nodes (src) with Red-black tree into (dst) nodes with Red-black tree.
+ *
+ * Possible improvement: find out which rb_tree is bigger and then move nodes into it.
+ * Current implementation blindly guesses that the source Red-black tree is smaller.
+ *
+ * @param[in,out] leader_dst First instance of the destination (leaf-)list.
+ * @param[in] root_meta_dst Metadata 'lyds_tree' from @p leader_dst.
+ * @param[in] rbt_dst Root of the destination Red-black tree.
+ * @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.
+ */
+static void
+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)
+{
+ struct rb_node *iter, *iter_state;
+ struct lyd_node *node;
+
+ /* release source RB tree */
+ RBT_SET(root_meta_src, NULL);
+ lyd_free_meta_single(root_meta_src);
+
+ /* 'randomly' iterate over all source nodes, merge and move to the destination */
+ for (iter = rb_iter_begin(rbt_src, &iter_state); iter; iter = rb_iter_next(&iter_state)) {
+ node = RBN_DNODE(iter);
+ *next_p = node->next;
+ RBN_RESET(iter, node);
+ rb_insert_node(&rbt_dst, iter);
+ 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);
+}
+
+LY_ERR
+lyds_merge(struct lyd_node **leader_dst, struct lyd_node *leader_src, struct lyd_node **next_p)
+{
+ LY_ERR ret = LY_SUCCESS;
+ struct rb_node *rbt_dst, *rbt_src;
+ struct lyd_meta *root_meta_dst, *root_meta_src = NULL;
+
+ assert(leader_dst && leader_src && next_p);
+
+ rbt_dst = lyds_get_rb_tree(*leader_dst, &root_meta_dst);
+ rbt_src = lyds_get_rb_tree(leader_src, &root_meta_src);
+
+ if (root_meta_src && !rbt_src) {
+ /* Release unnecessary metadata which can be empty, e.g. when duplicating a node */
+ lyd_free_meta_single(root_meta_src);
+ }
+
+ 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));
+ 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 */
+ ret = lyds_merge_nodes1(leader_dst, root_meta_dst, rbt_dst, leader_src, next_p);
+ } else if (!rbt_dst && rbt_src) {
+ /* merge destination nodes with RB tree, move RB tree and source nodes */
+ ret = lyds_merge_nodes2(leader_dst, leader_src, root_meta_src, rbt_src, next_p);
+ } else {
+ /* merge and move source nodes, release source RB tree */
+ assert(rbt_dst && rbt_src);
+ lyds_merge_nodes3(leader_dst, root_meta_dst, rbt_dst,
+ root_meta_src, rbt_src, next_p);
+ }
+
+ return ret;
+}
+
int
lyds_compare_single(struct lyd_node *node1, struct lyd_node *node2)
{
diff --git a/src/tree_data_sorted.h b/src/tree_data_sorted.h
index dfeb719..238ffc6 100644
--- a/src/tree_data_sorted.h
+++ b/src/tree_data_sorted.h
@@ -88,6 +88,45 @@
void lyds_unlink(struct lyd_node **leader, struct lyd_node *node);
/**
+ * @brief Split the (leaf-)list in two.
+ *
+ * The second (leaf-)list is unlinked from the rest of the data nodes.
+ * The hash for the data nodes is removed.
+ *
+ * @param[in] leader First instance of (leaf-)list.
+ * @param[in] node Node in the (leaf-)list from which the second (leaf-)list will start.
+ * @param[out] next Data node located after the second (leaf-)list.
+ * The rest of the (leaf-)list nodes will belong under the second (leaf-)list.
+ */
+void lyds_split(struct lyd_node *leader, struct lyd_node *node, struct lyd_node **next);
+
+/**
+ * @brief Merge source (leaf-)list nodes into destination (leaf-)list nodes.
+ *
+ * Pointers in sibling data nodes (lyd_node) are modified.
+ * The hash for the data nodes will be adjusted.
+ *
+ * @param[in,out] leader_dst Destination (leaf-)list, first instance. It may not contain
+ * the lyds_tree metadata or BST. After merge @p leader_dst can be reset to new leader.
+ * @param[in] leader_src Source (leaf-)list, first instance. It may not contain the lyds_tree metadata or BST.
+ * @param[out] next Data node located after source (leaf-)list.
+ * On error, points to data node which failed to merge.
+ * @return LY_ERR value.
+ */
+LY_ERR lyds_merge(struct lyd_node **leader_dst, struct lyd_node *leader_src, struct lyd_node **next);
+
+/**
+ * @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);
+
+/**
* @brief Release the metadata including BST.
*
* No more nodes can be inserted after the function is executed.
@@ -103,15 +142,4 @@
*/
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_ */