/** * @file tree_data_sorted.c * @author Adam Piecek * @brief Red-black tree implementation from FRRouting project (https://github.com/FRRouting/frr). * * The effort of this implementation was to take the working Red-black tree implementation * and adapt its interface to libyang. * * Copyright (c) 2015 - 2023 CESNET, z.s.p.o. * * This source code is licensed under BSD 3-Clause License (the "License"). * You may not use this file except in compliance with the License. * You may obtain a copy of the License at * * https://opensource.org/licenses/BSD-3-Clause */ // SPDX-License-Identifier: ISC AND BSD-2-Clause /* $OpenBSD: subr_tree.c,v 1.9 2017/06/08 03:30:52 dlg Exp $ */ /* * Copyright 2002 Niels Provos * Copyright (c) 2016 David Gwynne */ #include #include #include #include "dict.h" #include "log.h" #include "ly_common.h" #include "metadata.h" #include "plugins_internal.h" #include "plugins_types.h" #include "tree.h" #include "tree_data.h" #include "tree_data_internal.h" #include "tree_data_sorted.h" /* metadata (root_meta) ^ |________ | | | v -- | _____rbt__ | | | | | | | v | v | | _rbn_ | _rbn_____ | BST | | | | | | (Red-black tree) | ___| | | v | | | _____| | _rbn_ | | | | | | -- | v v v v ... lyd1<-->lyd2<-->lyd3<-->lyd4 ... (leader) | | |_____________________________| (leaf-)list The (leaf-)list consists of data nodes (lyd). The first instance of the (leaf-)list is named leader, which contains metadata named 'lyds_tree'. This metadata has a reference to the root of the Red-black tree. This tree consists of nodes named 'rbn'. Each of these nodes contains a reference to a left or right child, as well as a reference to a data node. */ /* * A red-black tree is a binary search tree (BST) with the node color as an * extra attribute. It fulfills a set of conditions: * - every search path from the root to a leaf consists of the same number of black nodes, * - each red node (except for the root) has a black parent, * - each leaf node is black. * * Every operation on a red-black tree is bounded as O(lg n). * The maximum height of a red-black tree is 2lg (n+1). */ #define RB_BLACK 0 /**< black node in a red-black tree */ #define RB_RED 1 /**< red node in a red-black tree */ /** * @brief Red-black node */ struct rb_node { struct rb_node *parent; /**< parent node (NULL if this is a root node) */ struct rb_node *left; /**< left node with a lower value */ struct rb_node *right; /**< left node with a greater value */ struct lyd_node *dnode; /**< assigned libyang data node */ uint8_t color; /**< color for red-black node */ }; /** * @defgroup rbngetters Macros for accessing members. * * Useful if there is a need to reduce the memory space for red-black nodes in the future. The color bit can be hidden * in some (parent/left/right) pointer and their true values can be obtained by masking. This saves 8 bytes, but there * is no guarantee that the code will be cross-platform. * * @{ */ #define RBN_LEFT(NODE) ((NODE)->left) #define RBN_RIGHT(NODE) ((NODE)->right) #define RBN_PARENT(NODE) ((NODE)->parent) #define RBN_DNODE(NODE) ((NODE)->dnode) #define RBN_COLOR(NODE) ((NODE)->color) /** @} rbngetters */ /** * @brief Rewrite members from @p SRC to @p DST. * * @param[in] DST Destination node. * @param[in] SRC Source node. */ #define RBN_COPY(DST, SRC) \ RBN_PARENT(DST) = RBN_PARENT(SRC); \ RBN_LEFT(DST) = RBN_LEFT(SRC); \ RBN_RIGHT(DST) = RBN_RIGHT(SRC); \ 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 Get red-black root from metadata. * * @param[in] META Pointer to the struct lyd_meta. * @param[out] RBT Root of the Red-black tree. */ #define RBT_GET(META, RBT) \ { \ struct lyd_value_lyds_tree *_lt; \ LYD_VALUE_GET(&META->value, _lt); \ RBT = _lt ? _lt->rbt : NULL; \ } /** * @brief Set a new red-black root to the metadata. * * @param[in] META Pointer to the struct lyd_meta. * @param[in] RBT Root of the Red-black tree. */ #define RBT_SET(META, RBT) \ { \ struct lyd_value_lyds_tree *_lt; \ LYD_VALUE_GET(&META->value, _lt); \ _lt->rbt = RBT; \ } /** * @brief Get Red-black tree from data node. * * @param[in] leader First instance of the (leaf-)list in sequence. * @param[out] meta Metadata from which the Red-black tree was obtained. The parameter is optional. * @return Root of the Red-black tree or NULL. */ static struct rb_node * lyds_get_rb_tree(const struct lyd_node *leader, struct lyd_meta **meta) { struct rb_node *rbt; struct lyd_meta *iter; if (meta) { *meta = NULL; } LY_LIST_FOR(leader->meta, iter) { if (!strcmp(iter->name, "lyds_tree")) { if (meta) { *meta = iter; } RBT_GET(iter, rbt); return rbt; } } return NULL; } /** * @brief Call plugins_types sort callback or sort values by plugin order. * * @param[in] ctx libyang context. * @param[in] val1 First value to compare. * @param[in] val2 Second value to compare. * @return Negative number if val1 < val2, * @return Zero if val1 == val2, * @return Positive number if val1 > val2. */ static int rb_sort_clb(const struct ly_ctx *ctx, const struct lyd_value *val1, const struct lyd_value *val2) { assert(val1->realtype == val2->realtype); return val1->realtype->plugin->sort(ctx, val1, val2); } /** * @brief Compare red-black nodes by rb_node.dnode from the same Red-black tree. * * @param[in] n1 First leaf-list data node. * @param[in] n2 Second leaf-list data node. * @return Negative number if val1 < val2, * @return Zero if val1 == val2, * @return Positive number if val1 > val2. */ static int rb_compare_leaflists(const struct lyd_node *n1, const struct lyd_node *n2) { struct lyd_value *val1, *val2; /* compare leaf-list values */ assert(n2->schema->nodetype == LYS_LEAFLIST); assert(n1->schema->nodetype == LYS_LEAFLIST); val1 = &((struct lyd_node_term *)n1)->value; val2 = &((struct lyd_node_term *)n2)->value; return rb_sort_clb(LYD_CTX(n1), val1, val2); } /** * @brief Compare red-black nodes by rb_node.dnode from the same Red-black tree. * * @param[in] n1 First list data node. * @param[in] n2 Second list data node. * @return Negative number if val1 < val2, * @return Zero if val1 == val2, * @return Positive number if val1 > val2. */ static int rb_compare_lists(const struct lyd_node *n1, const struct lyd_node *n2) { const struct lyd_node *k1, *k2; struct lyd_value *val1, *val2; int cmp; /* compare first list key */ assert(n1->schema->nodetype & LYS_LIST); assert(n2->schema->nodetype & LYS_LIST); /* lyd_child() is not called due to optimization */ k1 = ((const struct lyd_node_inner *)n1)->child; k2 = ((const struct lyd_node_inner *)n2)->child; val1 = &((struct lyd_node_term *)k1)->value; val2 = &((struct lyd_node_term *)k2)->value; cmp = rb_sort_clb(LYD_CTX(n1), val1, val2); if (cmp != 0) { return cmp; } /* continue with the next keys */ k1 = k1->next; k2 = k2->next; while (k1 && k1->schema && (k1->schema->flags & LYS_KEY)) { assert(k1->schema == k2->schema); val1 = &((struct lyd_node_term *)k1)->value; val2 = &((struct lyd_node_term *)k2)->value; cmp = rb_sort_clb(LYD_CTX(n1), val1, val2); if (cmp != 0) { return cmp; } k1 = k1->next; k2 = k2->next; } return cmp; } /** * @brief Release unlinked red-black node. * * @param[in,out] rbn Node to free, is set to NULL. */ static void rb_free_node(struct rb_node **rbn) { free(*rbn); *rbn = NULL; } /** * @brief Traversing all red-black nodes. * * Traversal order is not the same as traversing data nodes. * The rb_next() is available for browsing in a sorted manner. * * @param[in] current_state Current state of iterator. * @param[out] next_state The updated state of the iterator. * @return Next node or the first node. */ static struct rb_node * rb_iter_traversal(struct rb_node *current_state, struct rb_node **next_state) { struct rb_node *iter, *parent, *next; for (iter = current_state; iter; iter = next) { if (RBN_LEFT(iter)) { next = RBN_LEFT(iter); continue; } else if (RBN_RIGHT(iter)) { next = RBN_RIGHT(iter); continue; } *next_state = parent = RBN_PARENT(iter); if (parent && (RBN_LEFT(parent) == iter)) { RBN_LEFT(parent) = NULL; } else if (parent && (RBN_RIGHT(parent) == iter)) { RBN_RIGHT(parent) = NULL; } return iter; } return NULL; } /** * @brief Iterator initialization for traversing red-black tree. * * @param[in] rbt Root of the Red-black tree. * @param[out] iter_state Iterator state which must be maintained during browsing. * @return First node. */ static struct rb_node * rb_iter_begin(struct rb_node *rbt, struct rb_node **iter_state) { return rb_iter_traversal(rbt, iter_state); } /** * @brief Get the following node when traversing red-black tree. * * @param[in,out] iter_state Iterator state which must be maintained during browsing. * @return Next node. */ static struct rb_node * rb_iter_next(struct rb_node **iter_state) { return rb_iter_traversal(*iter_state, iter_state); } void lyds_free_tree(struct rb_node *rbt) { struct rb_node *rbn, *iter_state; /* There is no rebalancing. */ for (rbn = rb_iter_begin(rbt, &iter_state); rbn; rbn = rb_iter_next(&iter_state)) { rb_free_node(&rbn); } } static void rb_set(struct rb_node *rbn, struct rb_node *parent) { RBN_PARENT(rbn) = parent; RBN_LEFT(rbn) = RBN_RIGHT(rbn) = NULL; RBN_COLOR(rbn) = RB_RED; } static void rb_set_blackred(struct rb_node *black, struct rb_node *red) { RBN_COLOR(black) = RB_BLACK; RBN_COLOR(red) = RB_RED; } static void rb_rotate_left(struct rb_node **rbt, struct rb_node *rbn) { struct rb_node *parent; struct rb_node *tmp; tmp = RBN_RIGHT(rbn); RBN_RIGHT(rbn) = RBN_LEFT(tmp); if (RBN_RIGHT(rbn) != NULL) { RBN_PARENT(RBN_LEFT(tmp)) = rbn; } parent = RBN_PARENT(rbn); RBN_PARENT(tmp) = parent; if (parent != NULL) { if (rbn == RBN_LEFT(parent)) { RBN_LEFT(parent) = tmp; } else { RBN_RIGHT(parent) = tmp; } } else { *rbt = tmp; } RBN_LEFT(tmp) = rbn; RBN_PARENT(rbn) = tmp; } static void rb_rotate_right(struct rb_node **rbt, struct rb_node *rbn) { struct rb_node *parent; struct rb_node *tmp; tmp = RBN_LEFT(rbn); RBN_LEFT(rbn) = RBN_RIGHT(tmp); if (RBN_LEFT(rbn) != NULL) { RBN_PARENT(RBN_RIGHT(tmp)) = rbn; } parent = RBN_PARENT(rbn); RBN_PARENT(tmp) = parent; if (parent != NULL) { if (rbn == RBN_LEFT(parent)) { RBN_LEFT(parent) = tmp; } else { RBN_RIGHT(parent) = tmp; } } else { *rbt = tmp; } RBN_RIGHT(tmp) = rbn; RBN_PARENT(rbn) = tmp; } static void rb_insert_color(struct rb_node **rbt, struct rb_node *rbn) { struct rb_node *parent, *gparent, *tmp; while ((parent = RBN_PARENT(rbn)) != NULL && RBN_COLOR(parent) == RB_RED) { gparent = RBN_PARENT(parent); if (parent == RBN_LEFT(gparent)) { tmp = RBN_RIGHT(gparent); if ((tmp != NULL) && (RBN_COLOR(tmp) == RB_RED)) { RBN_COLOR(tmp) = RB_BLACK; rb_set_blackred(parent, gparent); rbn = gparent; continue; } if (RBN_RIGHT(parent) == rbn) { rb_rotate_left(rbt, parent); tmp = parent; parent = rbn; rbn = tmp; } rb_set_blackred(parent, gparent); rb_rotate_right(rbt, gparent); } else { tmp = RBN_LEFT(gparent); if ((tmp != NULL) && (RBN_COLOR(tmp) == RB_RED)) { RBN_COLOR(tmp) = RB_BLACK; rb_set_blackred(parent, gparent); rbn = gparent; continue; } if (RBN_LEFT(parent) == rbn) { rb_rotate_right(rbt, parent); tmp = parent; parent = rbn; rbn = tmp; } rb_set_blackred(parent, gparent); rb_rotate_left(rbt, gparent); } } RBN_COLOR(*rbt) = RB_BLACK; } static void rb_remove_color(struct rb_node **rbt, struct rb_node *parent, struct rb_node *rbn) { struct rb_node *tmp; while ((rbn == NULL || RBN_COLOR(rbn) == RB_BLACK) && rbn != *rbt && parent) { if (RBN_LEFT(parent) == rbn) { tmp = RBN_RIGHT(parent); if (RBN_COLOR(tmp) == RB_RED) { rb_set_blackred(tmp, parent); rb_rotate_left(rbt, parent); tmp = RBN_RIGHT(parent); } if (((RBN_LEFT(tmp) == NULL) || (RBN_COLOR(RBN_LEFT(tmp)) == RB_BLACK)) && ((RBN_RIGHT(tmp) == NULL) || (RBN_COLOR(RBN_RIGHT(tmp)) == RB_BLACK))) { RBN_COLOR(tmp) = RB_RED; rbn = parent; parent = RBN_PARENT(rbn); } else { if ((RBN_RIGHT(tmp) == NULL) || (RBN_COLOR(RBN_RIGHT(tmp)) == RB_BLACK)) { struct rb_node *oleft; oleft = RBN_LEFT(tmp); if (oleft != NULL) { RBN_COLOR(oleft) = RB_BLACK; } RBN_COLOR(tmp) = RB_RED; rb_rotate_right(rbt, tmp); tmp = RBN_RIGHT(parent); } RBN_COLOR(tmp) = RBN_COLOR(parent); RBN_COLOR(parent) = RB_BLACK; if (RBN_RIGHT(tmp)) { RBN_COLOR(RBN_RIGHT(tmp)) = RB_BLACK; } rb_rotate_left(rbt, parent); rbn = *rbt; break; } } else { tmp = RBN_LEFT(parent); if (RBN_COLOR(tmp) == RB_RED) { rb_set_blackred(tmp, parent); rb_rotate_right(rbt, parent); tmp = RBN_LEFT(parent); } if (((RBN_LEFT(tmp) == NULL) || (RBN_COLOR(RBN_LEFT(tmp)) == RB_BLACK)) && ((RBN_RIGHT(tmp) == NULL) || (RBN_COLOR(RBN_RIGHT(tmp)) == RB_BLACK))) { RBN_COLOR(tmp) = RB_RED; rbn = parent; parent = RBN_PARENT(rbn); } else { if ((RBN_LEFT(tmp) == NULL) || (RBN_COLOR(RBN_LEFT(tmp)) == RB_BLACK)) { struct rb_node *oright; oright = RBN_RIGHT(tmp); if (oright != NULL) { RBN_COLOR(oright) = RB_BLACK; } RBN_COLOR(tmp) = RB_RED; rb_rotate_left(rbt, tmp); tmp = RBN_LEFT(parent); } RBN_COLOR(tmp) = RBN_COLOR(parent); RBN_COLOR(parent) = RB_BLACK; if (RBN_LEFT(tmp) != NULL) { RBN_COLOR(RBN_LEFT(tmp)) = RB_BLACK; } rb_rotate_right(rbt, parent); rbn = *rbt; break; } } } if (rbn != NULL) { RBN_COLOR(rbn) = RB_BLACK; } } /** * @brief Remove node from the Red-black tree. * * @param[in,out] rbt Root of the Red-black tree. After the @p rbn is removed, the root may change. * @param[in] rbn Node to remove. * @return Removed node from the Red-black tree. */ static struct rb_node * rb_remove(struct rb_node **rbt, struct rb_node *rbn) { struct rb_node *child, *parent, *old = rbn; uint8_t color; if (RBN_LEFT(rbn) == NULL) { child = RBN_RIGHT(rbn); } else if (RBN_RIGHT(rbn) == NULL) { child = RBN_LEFT(rbn); } else { struct rb_node *tmp; rbn = RBN_RIGHT(rbn); while ((tmp = RBN_LEFT(rbn)) != NULL) { rbn = tmp; } child = RBN_RIGHT(rbn); parent = RBN_PARENT(rbn); color = RBN_COLOR(rbn); if (child != NULL) { RBN_PARENT(child) = parent; } if (parent != NULL) { if (RBN_LEFT(parent) == rbn) { RBN_LEFT(parent) = child; } else { RBN_RIGHT(parent) = child; } } else { *rbt = child; } if (RBN_PARENT(rbn) == old) { parent = rbn; } RBN_COPY(rbn, old); tmp = RBN_PARENT(old); if (tmp != NULL) { if (RBN_LEFT(tmp) == old) { RBN_LEFT(tmp) = rbn; } else { RBN_RIGHT(tmp) = rbn; } } else { *rbt = rbn; } RBN_PARENT(RBN_LEFT(old)) = rbn; if (RBN_RIGHT(old)) { RBN_PARENT(RBN_RIGHT(old)) = rbn; } goto color; } parent = RBN_PARENT(rbn); color = RBN_COLOR(rbn); if (child != NULL) { RBN_PARENT(child) = parent; } if (parent != NULL) { if (RBN_LEFT(parent) == rbn) { RBN_LEFT(parent) = child; } else { RBN_RIGHT(parent) = child; } } else { *rbt = child; } color: if (color == RB_BLACK) { rb_remove_color(rbt, parent, child); } return old; } /** * @brief Insert new node to the Red-black tree. * * @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, ly_bool *max_p) { ly_bool max; struct rb_node *tmp; struct rb_node *parent = NULL; int comp = 0; int (*rb_compare)(const struct lyd_node *n1, const struct lyd_node *n2); if (RBN_DNODE(*rbt)->schema->nodetype == LYS_LEAFLIST) { rb_compare = rb_compare_leaflists; } else { rb_compare = rb_compare_lists; } max = 1; tmp = *rbt; while (tmp != NULL) { parent = tmp; comp = rb_compare(RBN_DNODE(tmp), RBN_DNODE(rbn)); if (comp > 0) { tmp = RBN_LEFT(tmp); max = 0; } else { tmp = RBN_RIGHT(tmp); } } rb_set(rbn, parent); if (parent != NULL) { if (comp > 0) { RBN_LEFT(parent) = rbn; } else { RBN_RIGHT(parent) = rbn; } } else { *rbt = rbn; } rb_insert_color(rbt, rbn); if (max_p) { *max_p = max; } } /** * @brief Return the first lesser node (previous). * * @param[in] rbn Node from which the previous node is wanted. * @return Return the first lesser node. * @return NULL if @p rbn has the least value. */ static struct rb_node * rb_prev(struct rb_node *rbn) { if (RBN_LEFT(rbn)) { rbn = RBN_LEFT(rbn); while (RBN_RIGHT(rbn)) { rbn = RBN_RIGHT(rbn); } } else { if (RBN_PARENT(rbn) && (rbn == RBN_RIGHT(RBN_PARENT(rbn)))) { rbn = RBN_PARENT(rbn); } else { while (RBN_PARENT(rbn) && (rbn == RBN_LEFT(RBN_PARENT(rbn)))) { rbn = RBN_PARENT(rbn); } rbn = RBN_PARENT(rbn); } } return rbn; } /** * @brief Return the first greater node (next). * * @param[in] rbn Node from which the next node is wanted. * @return Return the first greater node. * @return NULL if @p rbn has the greatest value. */ static struct rb_node * rb_next(struct rb_node *rbn) { if (RBN_RIGHT(rbn) != NULL) { rbn = RBN_RIGHT(rbn); while (RBN_LEFT(rbn) != NULL) { rbn = RBN_LEFT(rbn); } } else { if (RBN_PARENT(rbn) && (rbn == RBN_LEFT(RBN_PARENT(rbn)))) { rbn = RBN_PARENT(rbn); } else { while (RBN_PARENT(rbn) && (rbn == RBN_RIGHT(RBN_PARENT(rbn)))) { rbn = RBN_PARENT(rbn); } rbn = RBN_PARENT(rbn); } } return rbn; } /** * @brief Find @p target value in the Red-black tree. * * @param[in] rbt Root of the Red-black tree. * @param[in] target Node containing the value to find. * @return red-black node which contains the same value as @p target or NULL. */ static struct rb_node * rb_find(struct rb_node *rbt, struct lyd_node *target) { struct rb_node *iter, *pivot; int comp; int (*rb_compare)(const struct lyd_node *n1, const struct lyd_node *n2); if (RBN_DNODE(rbt) == target) { return rbt; } if (RBN_DNODE(rbt)->schema->nodetype == LYS_LEAFLIST) { rb_compare = rb_compare_leaflists; } else { rb_compare = rb_compare_lists; } iter = rbt; do { comp = rb_compare(RBN_DNODE(iter), target); if (comp > 0) { iter = RBN_LEFT(iter); } else if (comp < 0) { iter = RBN_RIGHT(iter); } else if (RBN_DNODE(iter) == target) { return iter; } else { /* sequential search in nodes having the same value */ pivot = iter; /* search in predecessors */ for (iter = rb_prev(pivot); iter; iter = rb_prev(iter)) { if (rb_compare(RBN_DNODE(iter), target) != 0) { break; } else if (RBN_DNODE(iter) == target) { return iter; } } /* search in successors */ for (iter = rb_next(pivot); iter; iter = rb_next(iter)) { if (rb_compare(RBN_DNODE(iter), target) != 0) { break; } else if (RBN_DNODE(iter) == target) { return iter; } } /* node not found */ break; } } while (iter != NULL); return NULL; } LY_ERR lyds_create_node(struct lyd_node *node, struct rb_node **rbn) { *rbn = calloc(1, sizeof **rbn); LY_CHECK_ERR_RET(!(*rbn), LOGERR(LYD_CTX(node), LY_EMEM, "Allocation of red-black node failed."), LY_EMEM); RBN_DNODE(*rbn) = node; return LY_SUCCESS; } void lyds_pool_add(struct lyd_node *leader, struct lyds_pool *pool) { struct rb_node *rbt; struct lyd_meta *root_meta, *tmp; assert(pool && leader); rbt = lyds_get_rb_tree(leader, &root_meta); if (root_meta) { lyd_unlink_meta_single(root_meta); if (pool->meta) { tmp = pool->meta; pool->meta = root_meta; root_meta->next = tmp; } else { pool->meta = root_meta; } } if (!rbt) { return; } if (pool->rbn) { RBN_RESET(pool->rbn, NULL); } if (pool->iter_state) { /* insert rbn back */ assert(pool->rbn); if (RBN_LEFT(pool->iter_state)) { assert(!RBN_RIGHT(pool->iter_state)); RBN_RIGHT(pool->iter_state) = pool->rbn; } else { assert(!RBN_LEFT(pool->iter_state)); RBN_LEFT(pool->iter_state) = pool->rbn; } RBN_PARENT(pool->rbn) = pool->iter_state; } if (pool->rbn) { /* link rbt with rbn */ RBN_LEFT(pool->rbn) = rbt; RBN_PARENT(rbt) = pool->rbn; pool->rbn = rb_iter_begin(rbt, &pool->iter_state); } else { /* set new red black tree */ pool->rbn = rb_iter_begin(rbt, &pool->iter_state); } } /** * @brief Get metadata from the pool. * * @param[in,out] pool Pool containing metadata. * @return Free metadata to reuse or NULL. */ static struct lyd_meta * lyds_pool_get_meta(struct lyds_pool *pool) { struct lyd_meta *meta, *next; if (!pool->meta) { return NULL; } next = pool->meta->next; meta = pool->meta; meta->next = NULL; pool->meta = next; return meta; } void lyds_pool_clean(struct lyds_pool *pool) { struct lyd_meta *meta, *next; struct rb_node *iter; for (iter = pool->rbn; iter; iter = rb_iter_next(&pool->iter_state)) { rb_free_node(&iter); } pool->rbn = NULL; for (meta = pool->meta; meta; meta = next) { next = meta->next ? meta->next : NULL; RBT_SET(meta, NULL); lyd_free_meta_single(meta); } pool->meta = NULL; } /** * @brief Remove red-black node from the Red-black tree using the data node. * * @param[in] root_meta Metadata from leader containing a reference to the Red-black tree. * @param[in,out] rbt Root of the Red-black tree. * @param[in] node Data node used to find the corresponding red-black node. * @param[out] removed Removed node from Red-black tree. It can be deallocated or reset for further use. */ static void rb_remove_node(struct lyd_meta *root_meta, struct rb_node **rbt, struct lyd_node *node, struct rb_node **removed) { struct rb_node *rbn; assert(root_meta && rbt && node); if (!*rbt) { return; } /* find @p node in the Red-black tree. */ rbn = rb_find(*rbt, node); if (!rbn) { /* node was not inserted to the lyds tree due to optimization */ return; } assert(RBN_DNODE(rbn) == node); /* remove node */ rbn = rb_remove(rbt, rbn); *removed = rbn; if (rbn == *rbt) { /* rbn was the last node, assurance that root will be set to NULL */ *rbt = NULL; } /* the root of the Red-black tree may changed due to removal, so update the pointer to the root */ RBT_SET(root_meta, *rbt); } ly_bool lyds_is_supported(const struct lyd_node *node) { if (!node->schema || !(node->schema->flags & LYS_ORDBY_SYSTEM)) { return 0; } else if (node->schema->nodetype == LYS_LEAFLIST) { return 1; } else if ((node->schema->nodetype == LYS_LIST) && !(node->schema->flags & LYS_KEYLESS)) { return 1; } else { return 0; } } /** * @brief Unlink @p meta and insert it into @p dst data node. * * @param[in] dst Data node that will contain @p meta. * @param[in] meta Metadata that will be moved. */ static void lyds_move_meta(struct lyd_node *dst, struct lyd_meta *meta) { lyd_unlink_meta_single(meta); lyd_insert_meta(dst, meta, 0); } /** * @brief Connect data node with siblings so that the nodes are sorted. * * @param[in,out] first_sibling First sibling node. * @param[in,out] leader First instance of the (leaf-)list. * @param[in] node Data node to link. * @param[in] root_meta Metadata containing Red-black tree. Can be moved to a new leader. * @param[in] rbn red-black node of @p node. */ static void lyds_link_data_node(struct lyd_node **first_sibling, struct lyd_node **leader, struct lyd_node *node, struct lyd_meta *root_meta, struct rb_node *rbn) { struct rb_node *prev; /* insert @p node also into the data node (struct lyd_node) siblings */ prev = rb_prev(rbn); if (prev) { lyd_insert_after_node(first_sibling, RBN_DNODE(prev), RBN_DNODE(rbn)); } else { /* leader is no longer the first, the first is @p node */ lyd_insert_before_node(*leader, RBN_DNODE(rbn)); *leader = node; /* move metadata from the old leader to the new one */ lyds_move_meta(node, root_meta); /* update first_sibling */ *first_sibling = node->prev->next ? *first_sibling : node; } } /** * @brief Additionally create the Red-black nodes. * * @param[in,out] first_sibling First sibling node. * @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. * @param[in] node Start node from which rb nodes will be created. * @return LY_ERR value. */ static LY_ERR lyds_additionally_create_rb_nodes(struct lyd_node **first_sibling, struct lyd_node **leader, struct lyd_meta *root_meta, struct rb_node **rbt, struct lyd_node *node) { LY_ERR ret; ly_bool max; struct rb_node *rbn; struct lyd_node *iter; for (iter = node; iter && (iter->schema == (*leader)->schema); iter = iter->next) { ret = lyds_create_node(iter, &rbn); LY_CHECK_RET(ret); rb_insert_node(rbt, rbn, &max); if (!max) { /* nodes were not sorted, they will be sorted now */ lyd_unlink_ignore_lyds(first_sibling, iter); lyds_link_data_node(first_sibling, leader, iter, root_meta, rbn); lyd_insert_hash(iter); } } return LY_SUCCESS; } /** * @brief Additionally create the Red-black tree for the sorted nodes. * * @param[in,out] first_sibling First sibling node. * @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 **first_sibling, struct lyd_node **leader, struct lyd_meta *root_meta, struct rb_node **rbt) { LY_ERR ret; struct rb_node *rbn; /* 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 */ ret = lyds_additionally_create_rb_nodes(first_sibling, leader, root_meta, rbt, (*leader)->next); /* store pointer to the root */ RBT_SET(root_meta, *rbt); return ret; } /** * @brief Additionally reuse the Red-black tree for the sorted nodes. * * @param[in,out] first_sibling First sibling node. * @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. * @param[in,out] pool Pool from which the lyds data will be reused * @param[out] next Data node for which no free red-black node was available, * so not all nodes have been processed. Or is set to NULL, so all were sorted successfully. */ static void lyds_additionally_reuse_rb_tree(struct lyd_node **first_sibling, struct lyd_node **leader, struct lyd_meta *root_meta, struct rb_node **rbt, struct lyds_pool *pool, struct lyd_node **next) { ly_bool max; struct lyd_node *iter; /* let's begin with the leader */ RBN_RESET(pool->rbn, *leader); *rbt = pool->rbn; pool->rbn = rb_iter_next(&pool->iter_state); /* continue with the rest of the nodes */ for (iter = (*leader)->next; iter && (iter->schema == (*leader)->schema); iter = iter->next) { if (!pool->rbn) { *next = iter; return; } RBN_RESET(pool->rbn, iter); rb_insert_node(rbt, pool->rbn, &max); if (!max) { /* nodes were not sorted, they will be sorted now */ lyd_unlink_ignore_lyds(first_sibling, iter); lyds_link_data_node(first_sibling, leader, iter, root_meta, pool->rbn); lyd_insert_hash(iter); } pool->rbn = rb_iter_next(&pool->iter_state); } *next = NULL; } LY_ERR lyds_create_metadata(struct lyd_node *leader, struct lyd_meta **meta_p) { LY_ERR ret; uint32_t i; struct lyd_meta *meta; struct lys_module *modyang; assert(leader && (!leader->prev->next || (leader->schema != leader->prev->schema))); lyds_get_rb_tree(leader, &meta); if (meta) { /* nothing to do, the metadata is already set */ return LY_SUCCESS; } /* Check that the 'yang' module is defined. */ i = 0; while ((modyang = ly_ctx_get_module_iter(LYD_CTX(leader), &i))) { if (!strcmp(modyang->name, "yang")) { break; } } LY_CHECK_ERR_RET(!modyang, LOGERR(LYD_CTX(leader), LY_EINT, "The yang module is not installed."), LY_EINT); /* create new metadata, its rbt is NULL */ ret = lyd_create_meta(leader, &meta, modyang, "lyds_tree", 9, NULL, 0, 0, 1, NULL, LY_VALUE_CANON, NULL, LYD_HINT_DATA, NULL, 0, NULL); LY_CHECK_RET(ret); if (meta_p) { *meta_p = meta; } return LY_SUCCESS; } /** * @brief Create and insert a new red-black node. * * The data node itself is not sorted. To to this, call the lyds_link_data_node(). * * @param[in] node Data node to be accessed from the Red-black tree. * @param[in,out] rbt Root of the Red-black tree. * @param[out] rbn Created and inserted red-black node containing @p node. * @return LY_ERR value. */ static LY_ERR rb_insert(struct lyd_node *node, struct rb_node **rbt, struct rb_node **rbn) { LY_ERR ret; /* create a new red-black node to which the @p node will be assigned */ ret = lyds_create_node(node, rbn); LY_CHECK_RET(ret); /* insert red-black node with @p node to the Red-black tree */ rb_insert_node(rbt, *rbn, NULL); return LY_SUCCESS; } LY_ERR lyds_insert(struct lyd_node **first_sibling, struct lyd_node **leader, struct lyd_node *node) { LY_ERR ret; struct rb_node *rbt, *rbn; struct lyd_meta *root_meta; /* @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); /* 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_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 = lyds_get_rb_tree(*leader, &root_meta); if (!root_meta) { LY_CHECK_RET(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(first_sibling, 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(first_sibling, 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; } LY_ERR lyds_insert2(struct lyd_node *parent, struct lyd_node **first_sibling, struct lyd_node **leader, struct lyd_node *node, struct lyds_pool *pool) { LY_ERR ret; struct rb_node *rbt = NULL, *rbn; struct lyd_node *ld, *next; struct lyd_meta *root_meta; assert(pool && pool->rbn && first_sibling && node); if (!*leader || ((*leader)->schema != node->schema)) { /* leader has not been visited yet */ ld = NULL; lyd_find_sibling_schema(*first_sibling, node->schema, &ld); if (!ld) { /* the destination has no (leaf-)list instance yet. */ lyd_insert_node_ordby_schema(parent, first_sibling, node); *leader = node; goto cleanup; } else { /* leader has been found */ *leader = ld; } } /* get Red-black tree from leader */ rbt = lyds_get_rb_tree(*leader, &root_meta); if (!root_meta) { /* leader needs metadata */ root_meta = lyds_pool_get_meta(pool); if (!root_meta) { /* there is no free structure for metadata, a new one must be allocated */ ret = lyds_create_metadata(*leader, &root_meta); LY_CHECK_RET(ret); } else { /* reuse metadata */ lyd_insert_meta(*leader, root_meta, 0); } } if (!rbt) { /* Red-black tree needed */ lyds_additionally_reuse_rb_tree(first_sibling, leader, root_meta, &rbt, pool, &next); if (next) { /* there is no free structure for red-black node, a new ones must be allocated */ ret = lyds_additionally_create_rb_nodes(first_sibling, leader, root_meta, &rbt, next); LY_CHECK_RET(ret); } } /* insert @p node */ if (pool->rbn) { /* reuse free red-black node and insert */ rbn = pool->rbn; RBN_RESET(rbn, node); rb_insert_node(&rbt, rbn, NULL); /* prepare for the next node */ pool->rbn = rb_iter_next(&pool->iter_state); } else { /* allocate new node and insert */ ret = rb_insert(node, &rbt, &rbn); LY_CHECK_RET(ret); } /* connect @p node with siblings so that the order is maintained */ lyds_link_data_node(first_sibling, leader, node, root_meta, rbn); cleanup: if (rbt) { RBT_SET(root_meta, rbt); } lyd_insert_hash(node); *first_sibling = node->prev->next ? *first_sibling : node; return LY_SUCCESS; } void lyds_unlink(struct lyd_node **leader, struct lyd_node *node) { struct rb_node *rbt, *removed = NULL; struct lyd_meta *root_meta; if (!node || !leader || !*leader) { return; } /* get the Red-black tree from the leader */ rbt = lyds_get_rb_tree(*leader, &root_meta); /* find out if leader_p is alone */ if (!root_meta || LYD_NODE_IS_ALONE(*leader)) { return; } if (*leader == node) { /* move the metadata to the next instance. */ lyds_move_meta((*leader)->next, root_meta); } rb_remove_node(root_meta, &rbt, node, &removed); rb_free_node(&removed); } void lyds_split(struct lyd_node **first_sibling, 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(first_sibling, node); dst = node; LY_LIST_FOR_SAFE(start, next, iter) { if (iter->schema != node->schema) { break; } lyd_unlink_ignore_lyds(first_sibling, iter); lyd_insert_after_node(&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(first_sibling, 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(first_sibling, 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(first_sibling, iter); /* insert them to the second (leaf-)list */ lyd_insert_after_node(&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; if (node) { lyds_get_rb_tree(node, &root_meta); lyd_free_meta_single(root_meta); } } /** * @brief Merge nodes (src) without Red-black tree into (dst) nodes with Red-black tree. * * @param[in,out] first_dst First sibling node, destination. * @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,out] first_src First sibling node, source. * @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 **first_dst, struct lyd_node **leader_dst, struct lyd_meta *root_meta_dst, struct rb_node *rbt_dst, struct lyd_node **first_src, 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(first_src, iter); lyds_link_data_node(first_dst, 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,out] first_src First sibling node, source. * @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 **first_src, 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(first_src, 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] first_dst First sibling node, destination. * @param[in,out] leader_dst First instance of the destination (leaf-)list. * @param[in,out] first_src First sibling node, source. * @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 **first_dst, struct lyd_node **leader_dst, struct lyd_node **first_src, 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(first_src, RBN_DNODE(iter)); /* insert source data nodes into destination (leaf-)list */ lyd_insert_after_node(first_dst, 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,out] first_dst First sibling node, destination. * @param[in,out] first_src First sibling node, source. * @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 lyd_node **first_dst, struct lyd_node **first_src, 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(first_src, RBN_DNODE(iter)); lyd_insert_after_node(first_dst, 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] first_dst First sibling node, destination. * @param[in,out] leader_dst First instance of the destination (leaf-)list. * @param[in,out] first_src First sibling node, source. * @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 **first_dst, struct lyd_node **leader_dst, struct lyd_node **first_src, 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, first_src, leader_src, &rbt_src, &dst_iter, next_p); LY_CHECK_GOTO(ret, cleanup); *first_dst = !(*first_dst)->prev->next ? *first_dst : *leader_dst; /* 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(first_dst, leader_dst, first_src, &rbt_src, &dst_iter, next_p); LY_CHECK_GOTO(ret, cleanup); /* move the rest of the source nodes */ lyds_merge_nodes2_back(first_dst, first_src, dst_iter, next_p); if (*next_p && ((*next_p)->schema == (*leader_dst)->schema)) { ret = lyds_merge_nodes1(first_dst, leader_dst, root_meta_src, rbt_src, first_src, *next_p, 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] first_dst First sibling node, destination. * @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,out] first_src First sibling node, source. * @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 LY_ERR lyds_merge_nodes3(struct lyd_node **first_dst, struct lyd_node **leader_dst, struct lyd_meta *root_meta_dst, struct rb_node *rbt_dst, struct lyd_node **first_src, 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, NULL); lyd_unlink_ignore_lyds(first_src, node); lyds_link_data_node(first_dst, leader_dst, node, root_meta_dst, iter); lyd_insert_hash(node); } if (!*next_p || ((*next_p)->schema != (*leader_dst)->schema)) { RBT_SET(root_meta_dst, rbt_dst); } else { LY_CHECK_RET(lyds_merge_nodes1(first_dst, leader_dst, root_meta_dst, rbt_dst, first_src, *next_p, next_p)); } return LY_SUCCESS; } LY_ERR lyds_merge(struct lyd_node **first_dst, struct lyd_node **leader_dst, struct lyd_node **first_src, 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(first_dst, leader_dst, root_meta_dst, &rbt_dst)); ret = lyds_merge_nodes1(first_dst, leader_dst, root_meta_dst, rbt_dst, first_src, leader_src, next_p); } else if (rbt_dst && !rbt_src) { /* just merge and move source nodes */ ret = lyds_merge_nodes1(first_dst, leader_dst, root_meta_dst, rbt_dst, first_src, 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(first_dst, leader_dst, first_src, 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(first_dst, leader_dst, root_meta_dst, rbt_dst, first_src, root_meta_src, rbt_src, next_p); } return ret; } 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 == node2) { return 0; } else if (node1->schema->nodetype == LYS_LEAFLIST) { return rb_compare_leaflists(node1, node2); } else { return rb_compare_lists(node1, node2); } }