tree data OPTIMIZE lyds in lyd_merge()
There is no more freeing of memory and then allocation regarding
regarding lyds data. Memory intended to be freed is temporarily
not freed and instead waits for an opportunity to use it again.
diff --git a/src/tree_data.c b/src/tree_data.c
index 2e7ee00..0b1dbcb 100644
--- a/src/tree_data.c
+++ b/src/tree_data.c
@@ -712,14 +712,7 @@
}
}
-/**
- * @brief Insert a node 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] node Individual node (without siblings) to insert.
- */
-static void
+void
lyd_insert_node_ordby_schema(struct lyd_node *parent, struct lyd_node *first_sibling, struct lyd_node *node)
{
struct lyd_node *anchor;
@@ -2413,17 +2406,21 @@
* @param[in] merge_cb Optional merge callback.
* @param[in] cb_data Arbitrary callback data.
* @param[in] options Merge options.
+ * @param[in] lyds Pool of lyds data which can be reused.
+ * @param[in,out] leader_p Cached first instance of target (leaf-)list.
* @param[in,out] dup_inst Duplicate instance cache for all @p first_trg siblings.
* @return LY_ERR value.
*/
static LY_ERR
-lyd_merge_sibling_r(struct lyd_node **first_trg, struct lyd_node *parent_trg, const struct lyd_node **sibling_src_p,
- lyd_merge_cb merge_cb, void *cb_data, uint16_t options, struct ly_ht **dup_inst)
+lyd_merge_sibling_r(struct lyd_node **first_trg, struct lyd_node *parent_trg,
+ const struct lyd_node **sibling_src_p, lyd_merge_cb merge_cb, void *cb_data, uint16_t options,
+ struct lyds_pool *lyds, struct lyd_node **leader_p, struct ly_ht **dup_inst)
{
const struct lyd_node *child_src, *tmp, *sibling_src;
- struct lyd_node *match_trg, *dup_src, *elem;
+ struct lyd_node *match_trg, *dup_src, *elem, *leader;
struct lyd_node_opaq *opaq_trg, *opaq_src;
struct lysc_type *type;
+ const struct lysc_node *schema;
struct ly_ht *child_dup_inst = NULL;
LY_ERR r;
ly_bool first_inst = 0;
@@ -2497,20 +2494,29 @@
/* check descendants, recursively */
r = LY_SUCCESS;
+ leader = NULL;
+ schema = NULL;
LY_LIST_FOR_SAFE(lyd_child_no_keys(sibling_src), tmp, child_src) {
- r = lyd_merge_sibling_r(lyd_node_child_p(match_trg), match_trg, &child_src, merge_cb, cb_data, options,
- &child_dup_inst);
+ if ((options & LYD_MERGE_DESTRUCT) && (schema != child_src->schema) && LYDS_NODE_IS_LEADER(child_src)) {
+ schema = child_src->schema;
+ /* unlink lyds data and add them to the pool */
+ lyds_pool_add((struct lyd_node *)child_src, lyds);
+ }
+
+ r = lyd_merge_sibling_r(lyd_node_child_p(match_trg), match_trg, &child_src,
+ merge_cb, cb_data, options, lyds, &leader, &child_dup_inst);
if (r) {
break;
}
}
+
lyd_dup_inst_free(child_dup_inst);
LY_CHECK_RET(r);
} else {
/* node not found, merge it */
if (options & LYD_MERGE_DESTRUCT) {
dup_src = (struct lyd_node *)sibling_src;
- lyd_unlink(dup_src);
+ lyd_unlink_ignore_lyds(dup_src);
/* spend it */
*sibling_src_p = NULL;
} else {
@@ -2525,8 +2531,13 @@
}
}
- /* insert */
- lyd_insert_node(parent_trg, first_trg, dup_src, 0);
+ if (lyds->rbn) {
+ /* insert node and try to reuse free lyds data */
+ lyds_insert2(parent_trg, first_trg, leader_p, dup_src, lyds);
+ } else {
+ /* generic insert node */
+ lyd_insert_node(parent_trg, first_trg, dup_src, 0);
+ }
if (first_inst) {
/* remember not to find this instance next time */
@@ -2547,9 +2558,12 @@
lyd_merge_cb merge_cb, void *cb_data, uint16_t options, ly_bool nosiblings)
{
const struct lyd_node *sibling_src, *tmp;
+ const struct lysc_node *schema;
+ struct lyd_node *leader;
struct ly_ht *dup_inst = NULL;
ly_bool first;
LY_ERR ret = LY_SUCCESS;
+ struct lyds_pool lyds = {0};
LY_CHECK_ARG_RET(NULL, target, LY_EINVAL);
LY_CHECK_CTX_EQUAL_RET(*target ? LYD_CTX(*target) : NULL, source ? LYD_CTX(source) : NULL, mod ? mod->ctx : NULL,
@@ -2565,14 +2579,23 @@
return LY_EINVAL;
}
+ leader = NULL;
+ schema = NULL;
LY_LIST_FOR_SAFE(source, tmp, sibling_src) {
if (mod && (lyd_owner_module(sibling_src) != mod)) {
/* skip data nodes from different modules */
continue;
}
+ if ((options & LYD_MERGE_DESTRUCT) && (schema != sibling_src->schema) && LYDS_NODE_IS_LEADER(sibling_src)) {
+ schema = sibling_src->schema;
+ /* unlink lyds data and add them to the pool */
+ lyds_pool_add((struct lyd_node *)sibling_src, &lyds);
+ }
+
first = (sibling_src == source) ? 1 : 0;
- ret = lyd_merge_sibling_r(target, NULL, &sibling_src, merge_cb, cb_data, options, &dup_inst);
+ ret = lyd_merge_sibling_r(target, NULL, &sibling_src, merge_cb, cb_data, options,
+ &lyds, &leader, &dup_inst);
if (ret) {
break;
}
@@ -2585,6 +2608,7 @@
break;
}
}
+ lyds_pool_clean(&lyds);
if (options & LYD_MERGE_DESTRUCT) {
/* free any leftover source data that were not merged */
diff --git a/src/tree_data_internal.h b/src/tree_data_internal.h
index 0e0768b..f7bf216 100644
--- a/src/tree_data_internal.h
+++ b/src/tree_data_internal.h
@@ -399,6 +399,15 @@
void lyd_insert_node(struct lyd_node *parent, struct lyd_node **first_sibling, struct lyd_node *node, ly_bool last);
/**
+ * @brief Insert a node into parent/siblings, either before the 'anchor' or as the last sibling.
+ *
+ * @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] node Individual node (without siblings) to insert.
+ */
+void lyd_insert_node_ordby_schema(struct lyd_node *parent, struct lyd_node *first_sibling, struct lyd_node *node);
+
+/**
* @brief Unlink the specified data subtree.
*
* @param[in] node Data tree node to be unlinked (together with all the children).
diff --git a/src/tree_data_sorted.c b/src/tree_data_sorted.c
index 914327a..f2ba654 100644
--- a/src/tree_data_sorted.c
+++ b/src/tree_data_sorted.c
@@ -853,6 +853,100 @@
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.
*
@@ -885,7 +979,7 @@
}
ly_bool
-lyds_is_supported(struct lyd_node *node)
+lyds_is_supported(const struct lyd_node *node)
{
if (!node->schema || !(node->schema->flags & LYS_ORDBY_SYSTEM)) {
return 0;
@@ -938,6 +1032,38 @@
}
/**
+ * @brief Additionally create the Red-black nodes.
+ *
+ * @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 **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(iter);
+ lyds_link_data_node(leader, iter, root_meta, rbn);
+ }
+ }
+
+ return LY_SUCCESS;
+}
+
+/**
* @brief Additionally create the Red-black tree for the sorted nodes.
*
* @param[in,out] leader First instance of the (leaf-)list.
@@ -949,9 +1075,7 @@
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);
@@ -959,21 +1083,53 @@
*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, &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);
- }
- }
+ ret = lyds_additionally_create_rb_nodes(leader, root_meta, rbt, (*leader)->next);
/* store pointer to the root */
RBT_SET(root_meta, *rbt);
- return LY_SUCCESS;
+ return ret;
+}
+
+/**
+ * @brief Additionally reuse the Red-black tree for the sorted nodes.
+ *
+ * @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 **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(iter);
+ lyds_link_data_node(leader, iter, root_meta, pool->rbn);
+ }
+ pool->rbn = rb_iter_next(&pool->iter_state);
+ }
+
+ *next = NULL;
}
LY_ERR
@@ -1081,6 +1237,82 @@
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(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(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(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)
{
diff --git a/src/tree_data_sorted.h b/src/tree_data_sorted.h
index 238ffc6..848ac62 100644
--- a/src/tree_data_sorted.h
+++ b/src/tree_data_sorted.h
@@ -33,6 +33,19 @@
*/
/**
+ * @brief BST and 'lyds_tree' metadata pool.
+ *
+ * The structure stores a free Red-black tree and metadata, which can be reused. Thanks to this,
+ * it is possible to work with data more efficiently and thus prevent repeated allocation and freeing of memory.
+ */
+struct lyds_pool {
+ struct rb_node *rbn; /**< The current free node to use. If set, the pool is not empty. */
+ struct lyd_meta *meta; /**< Pointer to the list of free 'lyds_tree' metadata to reuse. */
+ /* Private items */
+ struct rb_node *iter_state; /**< Internal iterator over a Red-black tree. Pointer to a successor. */
+};
+
+/**
* @brief Check that ordering is supported for the @p node.
*
* If the function returns 0 for a given node, other lyds_* or rb_* functions must not be called for this node.
@@ -40,7 +53,16 @@
* @param[in] node Node to check. Expected (leaf-)list or list with key(s).
* @return 1 if @p node can be sorted.
*/
-ly_bool lyds_is_supported(struct lyd_node *node);
+ly_bool lyds_is_supported(const struct lyd_node *node);
+
+/**
+ * @brief Determine if the data node supports lyds and if the node is a 'leader'.
+ *
+ * @param[in] NODE Data node (struct lyd_node) to check.
+ * @return 1 if @p NODE is the first instance of the (leaf-)list with lyds support.
+ */
+#define LYDS_NODE_IS_LEADER(NODE) \
+ (lyds_is_supported(NODE) && (!NODE->prev->next || (NODE->prev->schema != NODE->schema)))
/**
* @brief Create the 'lyds_tree' metadata.
@@ -76,6 +98,22 @@
LY_ERR lyds_insert(struct lyd_node **leader, struct lyd_node *node);
/**
+ * @brief Insert the @p node into BST and into @p leader's siblings and use @p pool.
+ *
+ * @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,out] leader First instance of the (leaf-)list. It can be set to NULL or even incorrectly set,
+ * in which case the leader is found inside the function. It is convenient to keep the found pointer
+ * at the caller and be used during the next call.
+ * @param[in] node Individual node (without siblings) to insert.
+ * @param[in,out] pool Pool from which the lyds data will be reused. If empty, data is allocated as needed.
+ * @return LY_ERR value.
+ */
+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);
+
+/**
* @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.
@@ -88,6 +126,21 @@
void lyds_unlink(struct lyd_node **leader, struct lyd_node *node);
/**
+ * @brief Unlink lyds data from @p leader and add them to the pool.
+ *
+ * @param[in] leader First instance of the (leaf-)list.
+ * @param[in,out] pool Pool to add lyds data to.
+ */
+void lyds_pool_add(struct lyd_node *leader, struct lyds_pool *pool);
+
+/**
+ * @brief Clear lyds data in pool, memory deallocation.
+ *
+ * @param[in,out] pool Pool from which the lyds data will be released. Pointers will be set to NULL.
+ */
+void lyds_pool_clean(struct lyds_pool *pool);
+
+/**
* @brief Split the (leaf-)list in two.
*
* The second (leaf-)list is unlinked from the rest of the data nodes.