libyang FEATURE sorting of data nodes
1. Plugin type 'lyds_tree' is integrated. Used in metadata and it is
internal, which is distinguished by the unset print callback.
Internal metadata must not be printed.
2. Leaf-list and list data instances are now automatically sorted.
3. Both the explicit and implicit YANG statement 'ordered-by system'
will cause the nodes to be ordered.
4. The first instance of the list or leaf-list of node contain
new metadata named 'lyds_tree'.
5. Data nodes are sorted only if their data types have
callback 'sort' set.
6. Sorting can be turned off so far only by adding the 'ordered-by user'
statement to the YANG model.
7. If the sort fails for some reason, the node is still inserted
as the last instance. A warning message informs about this situation.
8. The time required for sorting should be relatively small thanks to
the Red-black tree implementation.
9. Memory requirements will now increase by 40 bytes per list/leaf-list
data node, plus metadata structure overhead.
10. New internal lyds_tree plugin type.
diff --git a/src/out.c b/src/out.c
index a37bc94..9eed077 100644
--- a/src/out.c
+++ b/src/out.c
@@ -29,6 +29,7 @@
#include "compat.h"
#include "log.h"
#include "ly_common.h"
+#include "metadata.h"
#include "printer_data.h"
#include "tree_data.h"
#include "tree_schema.h"
@@ -89,6 +90,21 @@
return 1;
}
+LIBYANG_API_DEF ly_bool
+lyd_metadata_should_print(const struct lyd_meta *meta)
+{
+ const char *arg;
+
+ assert(meta->annotation);
+
+ arg = meta->annotation->argument;
+ if (!strcmp(arg, "lyds_tree")) {
+ return 0;
+ } else {
+ return 1;
+ }
+}
+
LIBYANG_API_DEF LY_OUT_TYPE
ly_out_type(const struct ly_out *out)
{
diff --git a/src/plugins.c b/src/plugins.c
index 3f120c4..c1bdad5 100644
--- a/src/plugins.c
+++ b/src/plugins.c
@@ -81,6 +81,11 @@
extern const struct lyplg_type_record plugins_node_instanceid[];
/*
+ * lyds_tree
+ */
+extern const struct lyplg_type_record plugins_lyds_tree[];
+
+/*
* internal extension plugins records
*/
extern struct lyplg_ext_record plugins_metadata[];
@@ -484,6 +489,9 @@
/* ietf-netconf-acm */
LY_CHECK_GOTO(ret = plugins_insert(LYPLG_TYPE, plugins_node_instanceid), error);
+ /* lyds_tree */
+ LY_CHECK_GOTO(ret = plugins_insert(LYPLG_TYPE, plugins_lyds_tree), error);
+
/* internal extensions */
LY_CHECK_GOTO(ret = plugins_insert(LYPLG_EXTENSION, plugins_metadata), error);
LY_CHECK_GOTO(ret = plugins_insert(LYPLG_EXTENSION, plugins_nacm), error);
diff --git a/src/plugins_types/lyds_tree.c b/src/plugins_types/lyds_tree.c
new file mode 100644
index 0000000..d1c88f6
--- /dev/null
+++ b/src/plugins_types/lyds_tree.c
@@ -0,0 +1,146 @@
+/**
+ * @file lyds_tree.c
+ * @author Adam Piecek <piecek@cesnet.cz>
+ * @brief Internal type plugin for sorting data nodes.
+ *
+ * Copyright (c) 2019-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
+ */
+
+#include "plugins_types.h"
+
+#include <assert.h> /* assert */
+#include <stddef.h> /* NULL */
+#include <string.h> /* memset */
+
+#include "common.h"
+#include "compat.h"
+#include "libyang.h"
+#include "tree_data_sorted.h"
+
+static void lyplg_type_free_lyds(const struct ly_ctx *ctx, struct lyd_value *value);
+
+static LY_ERR
+lyplg_type_store_lyds(const struct ly_ctx *ctx, const struct lysc_type *type, const void *value,
+ size_t UNUSED(value_len), uint32_t options, LY_VALUE_FORMAT format, void *UNUSED(prefix_data),
+ uint32_t UNUSED(hints), const struct lysc_node *UNUSED(ctx_node), struct lyd_value *storage,
+ struct lys_glob_unres *UNUSED(unres), struct ly_err_item **UNUSED(err))
+{
+ int ret;
+ struct rb_node *rbt = NULL;
+ struct lyd_value_lyds_tree *val = NULL;
+
+ /* Prepare value memory. */
+ LYPLG_TYPE_VAL_INLINE_PREPARE(storage, val);
+ LY_CHECK_ERR_GOTO(!val, ret = LY_EMEM, cleanup);
+
+ if (format == LY_VALUE_CANON) {
+ /* The canonical value for lyds_tree type is the empty string, so @p value is like NULL. */
+ memset(storage->fixed_mem, 0, LYD_VALUE_FIXED_MEM_SIZE);
+ storage->realtype = type;
+ return LY_SUCCESS;
+ } else if ((format != LY_VALUE_LYB) || (options & LYPLG_TYPE_STORE_DYNAMIC)) {
+ return LY_EVALID;
+ }
+
+ /* Create a new Red-black tree. The insertion of additional data nodes should be done via lyds_insert(). */
+ ret = lyds_create_node((struct lyd_node *)value, &rbt);
+ LY_CHECK_GOTO(ret, cleanup);
+
+ /* Set the root of the Red-black tree. */
+ storage->realtype = type;
+ val->rbt = rbt;
+
+cleanup:
+ if (ret) {
+ lyplg_type_free_lyds(ctx, storage);
+ }
+
+ return ret;
+}
+
+static void
+lyplg_type_free_lyds(const struct ly_ctx *UNUSED(ctx), struct lyd_value *value)
+{
+ struct lyd_value_lyds_tree *val = NULL;
+
+ /* The canonical value is not used at all. */
+ assert(!value->_canonical);
+ LYD_VALUE_GET(value, val);
+
+ /* Release Red-black tree. */
+ lyds_free_tree(val->rbt);
+ LYPLG_TYPE_VAL_INLINE_DESTROY(val);
+ memset(value->fixed_mem, 0, LYD_VALUE_FIXED_MEM_SIZE);
+}
+
+static LY_ERR
+lyplg_type_dupl_lyds(const struct ly_ctx *UNUSED(ctx), const struct lyd_value *original, struct lyd_value *dup)
+{
+ /* The duplicate is not created here, but at the caller, which creates a duplicate lyds tree
+ * implicitly by inserting duplicate nodes into the data tree.
+ */
+ memset(dup, 0, sizeof *dup);
+ dup->realtype = original->realtype;
+
+ return LY_SUCCESS;
+}
+
+static LY_ERR
+lyplg_type_compare_lyds(const struct ly_ctx *UNUSED(ctx), const struct lyd_value *UNUSED(val1),
+ const struct lyd_value *UNUSED(val2))
+{
+ return LY_ENOT;
+}
+
+static int
+lyplg_type_sort_lyds(const struct ly_ctx *UNUSED(ctx), const struct lyd_value *UNUSED(val1),
+ const struct lyd_value *UNUSED(val2))
+{
+ return 0;
+}
+
+static const void *
+lyplg_type_print_lyds(const struct ly_ctx *UNUSED(ctx), const struct lyd_value *UNUSED(value),
+ LY_VALUE_FORMAT UNUSED(format), void *UNUSED(prefix_data), ly_bool *dynamic, size_t *value_len)
+{
+ if (dynamic) {
+ *dynamic = 0;
+ }
+ if (value_len) {
+ *value_len = 0;
+ }
+
+ return "";
+}
+
+/**
+ * @brief Plugin information for lyds_tree type implementation.
+ *
+ * Note that external plugins are supposed to use:
+ *
+ * LYPLG_TYPES = {
+ */
+const struct lyplg_type_record plugins_lyds_tree[] = {
+ {
+ .module = "yang",
+ .revision = NULL,
+ .name = "lyds_tree",
+
+ .plugin.id = "libyang 2 - lyds_tree, version 1",
+ .plugin.store = lyplg_type_store_lyds,
+ .plugin.validate = NULL,
+ .plugin.compare = lyplg_type_compare_lyds,
+ .plugin.sort = lyplg_type_sort_lyds,
+ .plugin.print = lyplg_type_print_lyds,
+ .plugin.duplicate = lyplg_type_dupl_lyds,
+ .plugin.free = lyplg_type_free_lyds,
+ .plugin.lyb_data_len = 0
+ },
+ {0}
+};
diff --git a/src/printer_data.h b/src/printer_data.h
index fb2a5fb..ef21aff 100644
--- a/src/printer_data.h
+++ b/src/printer_data.h
@@ -189,6 +189,15 @@
*/
LIBYANG_API_DECL ly_bool lyd_node_should_print(const struct lyd_node *node, uint32_t options);
+/**
+ * @brief Check whether the metadata should be printed.
+ *
+ * @param[in] meta Metadata to check.
+ * @return 0 if not,
+ * @return non-0 if should be printed.
+ */
+LIBYANG_API_DECL ly_bool lyd_metadata_should_print(const struct lyd_meta *meta);
+
#ifdef __cplusplus
}
#endif
diff --git a/src/printer_json.c b/src/printer_json.c
index 414fad0..29ca0e7 100644
--- a/src/printer_json.c
+++ b/src/printer_json.c
@@ -455,6 +455,9 @@
}
for (meta = node->meta; meta; meta = meta->next) {
+ if (!lyd_metadata_should_print(meta)) {
+ continue;
+ }
PRINT_COMMA;
ly_print_(pctx->out, "%*s\"%s:%s\":%s", INDENT, meta->annotation->module->name, meta->name, DO_FORMAT ? " " : "");
LY_CHECK_RET(json_print_value(pctx, LYD_CTX(node), &meta->value, NULL));
@@ -465,6 +468,30 @@
}
/**
+ * @brief Check if a value can be printed for at least one metadata.
+ *
+ * @param[in] node Node to check.
+ * @return 1 if node has printable meta otherwise 0.
+ */
+static ly_bool
+node_has_printable_meta(const struct lyd_node *node)
+{
+ struct lyd_meta *iter;
+
+ if (!node->meta) {
+ return 0;
+ }
+
+ LY_LIST_FOR(node->meta, iter) {
+ if (lyd_metadata_should_print(iter)) {
+ return 1;
+ }
+ }
+
+ return 0;
+}
+
+/**
* @brief Print attributes/metadata of the given @p node. Accepts both regular as well as opaq nodes.
*
* @param[in] ctx JSON printer context.
@@ -485,7 +512,7 @@
wdmod = ly_ctx_get_module_implemented(LYD_CTX(node), "ietf-netconf-with-defaults");
}
- if (node->schema && (node->meta || wdmod)) {
+ if (node->schema && (wdmod || node_has_printable_meta(node))) {
if (inner) {
LY_CHECK_RET(json_print_member2(pctx, lyd_parent(node), LY_VALUE_JSON, NULL, 1));
} else {
@@ -799,7 +826,7 @@
/* we have implicit OR explicit default node, get with-defaults module */
wdmod = ly_ctx_get_module_implemented(LYD_CTX(node), "ietf-netconf-with-defaults");
}
- if (node->meta || wdmod) {
+ if (wdmod || node_has_printable_meta(node)) {
/* we will be printing metadata for these siblings */
pctx->first_leaflist = node;
}
@@ -855,7 +882,7 @@
} else {
iter_wdmod = NULL;
}
- if ((iter->schema && (iter->meta || iter_wdmod)) || (opaq && opaq->attr)) {
+ if ((iter->schema && (node_has_printable_meta(iter) || iter_wdmod)) || (opaq && opaq->attr)) {
ly_print_(pctx->out, "%*s%s", INDENT, DO_FORMAT ? "{\n" : "{");
LEVEL_INC;
diff --git a/src/printer_lyb.c b/src/printer_lyb.c
index 110cb29..de6ae97 100644
--- a/src/printer_lyb.c
+++ b/src/printer_lyb.c
@@ -765,6 +765,9 @@
++count;
}
for (iter = node->meta; iter; iter = iter->next) {
+ if (!lyd_metadata_should_print(iter)) {
+ continue;
+ }
if (count == UINT8_MAX) {
LOGERR(lybctx->lybctx->ctx, LY_EINT, "Maximum supported number of data node metadata is %u.", UINT8_MAX);
return LY_EINT;
@@ -784,6 +787,10 @@
/* write all the node metadata */
LY_LIST_FOR(node->meta, iter) {
+ if (!lyd_metadata_should_print(iter)) {
+ continue;
+ }
+
/* model */
LY_CHECK_RET(lyb_print_model(out, iter->annotation->module, 0, lybctx->lybctx));
diff --git a/src/printer_xml.c b/src/printer_xml.c
index d33a725..31c5ad4 100644
--- a/src/printer_xml.c
+++ b/src/printer_xml.c
@@ -209,6 +209,10 @@
}
for (meta = node->meta; meta; meta = meta->next) {
+ if (!lyd_metadata_should_print(meta)) {
+ continue;
+ }
+
/* store the module of the default namespace, NULL because there is none */
ly_set_add(&ns_list, NULL, 0, NULL);
diff --git a/src/printer_yang.c b/src/printer_yang.c
index 73802f1..9dd95a8 100644
--- a/src/printer_yang.c
+++ b/src/printer_yang.c
@@ -288,10 +288,27 @@
LY_ARRAY_COUNT_TYPE u;
LY_ARRAY_FOR(exts, u) {
+ if (exts[u].flags & LYS_INTERNAL) {
+ continue;
+ }
yprp_extension_instance(pctx, substmt, substmt_index, &exts[u], flag);
}
}
+static ly_bool
+yprp_extension_has_printable_instances(struct lysp_ext_instance *exts)
+{
+ LY_ARRAY_COUNT_TYPE u;
+
+ LY_ARRAY_FOR(exts, u) {
+ if (!(exts[u].flags & LYS_INTERNAL)) {
+ return 1;
+ }
+ }
+
+ return 0;
+}
+
static void
yprc_extension_instances(struct lys_ypr_ctx *pctx, enum ly_stmt substmt, uint8_t substmt_index,
struct lysc_ext_instance *exts, ly_bool *flag)
@@ -2148,7 +2165,7 @@
YPR_EXTRA_LINE(modp->extensions, pctx);
- if (modp->exts) {
+ if (yprp_extension_has_printable_instances(modp->exts)) {
YPR_EXTRA_LINE_PRINT(pctx);
yprp_extension_instances(pctx, LY_STMT_MODULE, 0, modp->exts, NULL);
}
diff --git a/src/printer_yin.c b/src/printer_yin.c
index cb01c21..c3a31a6 100644
--- a/src/printer_yin.c
+++ b/src/printer_yin.c
@@ -1283,7 +1283,9 @@
LY_ARRAY_COUNT_TYPE u;
LY_ARRAY_FOR(modp->imports, u){
- ly_print_(pctx->out, "\n%*sxmlns:%s=\"%s\"", indent + INDENT, modp->imports[u].prefix, modp->imports[u].module->ns);
+ if (!(modp->imports[u].flags & LYS_INTERNAL)) {
+ ly_print_(pctx->out, "\n%*sxmlns:%s=\"%s\"", indent + INDENT, modp->imports[u].prefix, modp->imports[u].module->ns);
+ }
}
}
diff --git a/src/schema_compile_node.c b/src/schema_compile_node.c
index d0b3431..360e351 100644
--- a/src/schema_compile_node.c
+++ b/src/schema_compile_node.c
@@ -2700,12 +2700,15 @@
/* list ordering */
if (node->nodetype & (LYS_LIST | LYS_LEAFLIST)) {
if ((node->flags & (LYS_CONFIG_R | LYS_IS_OUTPUT | LYS_IS_NOTIF)) && (node->flags & LYS_ORDBY_MASK)) {
+ node->flags &= ~LYS_ORDBY_MASK;
LOGVRB("The ordered-by statement is ignored in lists representing %s (%s).",
(node->flags & LYS_IS_OUTPUT) ? "RPC/action output parameters" :
(ctx->compile_opts & LYS_IS_NOTIF) ? "notification content" : "state data", ctx->path);
- node->flags &= ~LYS_ORDBY_MASK;
- node->flags |= LYS_ORDBY_SYSTEM;
- } else if (!(node->flags & LYS_ORDBY_MASK)) {
+ }
+ if (node->flags & (LYS_IS_OUTPUT | LYS_IS_NOTIF)) {
+ /* it is probably better not to order them */
+ node->flags |= LYS_ORDBY_USER;
+ } else if (!(node->flags & LYS_ORDBY_MASK) || (node->flags & LYS_CONFIG_R)) {
/* default ordering is system */
node->flags |= LYS_ORDBY_SYSTEM;
}
diff --git a/src/tree_data.c b/src/tree_data.c
index 0d10d72..bfe27dd 100644
--- a/src/tree_data.c
+++ b/src/tree_data.c
@@ -45,6 +45,7 @@
#include "set.h"
#include "tree.h"
#include "tree_data_internal.h"
+#include "tree_data_sorted.h"
#include "tree_edit.h"
#include "tree_schema.h"
#include "tree_schema_internal.h"
@@ -658,38 +659,52 @@
return 1;
}
-void
-lyd_insert_node(struct lyd_node *parent, struct lyd_node **first_sibling_p, struct lyd_node *node, ly_bool last)
+/**
+ * @brief Get the first subsequent data node that contains a different schema definition.
+ *
+ * @param[in] first_sibling First sibling, NULL if no top-level sibling exist yet.
+ * @param[in] node Node to be inserted.
+ * @return Subsequent data node with a different schema.
+ */
+static struct lyd_node *
+lyd_insert_node_find_anchor(struct lyd_node *first_sibling, struct lyd_node *node)
+{
+ struct lyd_node *anchor;
+
+ if (first_sibling && (first_sibling->flags & LYD_EXT)) {
+ return NULL;
+ }
+
+ /* find the anchor, so we can insert somewhere before it */
+ anchor = lyd_insert_get_next_anchor(first_sibling, node);
+ /* cannot insert data node after opaque nodes */
+ if (!anchor && node->schema && first_sibling && !first_sibling->prev->schema) {
+ anchor = first_sibling->prev;
+ while ((anchor != first_sibling) && !anchor->prev->schema) {
+ anchor = anchor->prev;
+ }
+ }
+
+ return anchor;
+}
+
+/**
+ * @brief Insert a node into parent/siblings.
+ *
+ * @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.
+ */
+static void
+lyd_insert_node_ordby_schema(struct lyd_node *parent, struct lyd_node **first_sibling_p, struct lyd_node *node,
+ ly_bool last)
{
struct lyd_node *anchor, *first_sibling;
- /* inserting list without its keys is not supported */
- assert((parent || first_sibling_p) && node && (node->hash || !node->schema));
- assert(!parent || !parent->schema ||
- (parent->schema->nodetype & (LYS_CONTAINER | LYS_LIST | LYS_RPC | LYS_ACTION | LYS_NOTIF)));
-
- if (!parent && first_sibling_p && (*first_sibling_p) && (*first_sibling_p)->parent) {
- parent = lyd_parent(*first_sibling_p);
- }
-
/* get first sibling */
first_sibling = parent ? lyd_child(parent) : *first_sibling_p;
-
- if (last || (first_sibling && (first_sibling->flags & LYD_EXT))) {
- /* no next anchor */
- anchor = NULL;
- } else {
- /* find the anchor, our next node, so we can insert before it */
- anchor = lyd_insert_get_next_anchor(first_sibling, node);
-
- /* cannot insert data node after opaque nodes */
- if (!anchor && node->schema && first_sibling && !first_sibling->prev->schema) {
- anchor = first_sibling->prev;
- while ((anchor != first_sibling) && !anchor->prev->schema) {
- anchor = anchor->prev;
- }
- }
- }
+ anchor = !last ? lyd_insert_node_find_anchor(first_sibling, node) : NULL;
if (anchor) {
/* insert before the anchor */
@@ -708,6 +723,91 @@
/* insert as the only sibling */
*first_sibling_p = node;
}
+}
+
+/**
+ * @brief Insert a node into parent/siblings. It is sorted using sort callbacks in the plugin types and lyds tree.
+ *
+ * The lyds tree is a Binary search tree that allows to sort instances of the same leaf-list or list.
+ * This Binary search tree is always found in the first instance of the (leaf-)list in its metadata.
+ *
+ * @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.
+ * @return LY_ERR value.
+ */
+static LY_ERR
+lyd_insert_node_ordby_lyds(struct lyd_node *parent, struct lyd_node **first_sibling_p, struct lyd_node *node)
+{
+ LY_ERR ret = LY_SUCCESS;
+ struct lyd_node *anchor, *first_sibling, *leader;
+
+ /* get first sibling */
+ first_sibling = parent ? lyd_child(parent) : *first_sibling_p;
+
+ if (!parent && !first_sibling) {
+ /* insert as the only sibling */
+ *first_sibling_p = node;
+ /* node is alone, no lyds tree is created */
+ } else if (parent && !first_sibling) {
+ /* insert as the only child */
+ ret = lyds_create_metadata(node);
+ LY_CHECK_RET(ret);
+ lyd_insert_only_child(parent, node);
+ } else if (lyd_find_sibling_schema(first_sibling, node->schema, &leader) == LY_SUCCESS) {
+ /* Found the first instance of (leaf-)list, let's mark it as 'leader'. */
+ /* ensure that leader has meta set (use-case for top-level nodes) */
+ ret = lyds_create_metadata(leader);
+ LY_CHECK_RET(ret);
+ /* insert @p node to the BST tree and put him in line */
+ ret = lyds_insert(&leader, node);
+ LY_CHECK_RET(ret);
+ } else if ((anchor = lyd_insert_node_find_anchor(first_sibling, node))) {
+ /* insert before the anchor */
+ ret = lyds_create_metadata(node);
+ LY_CHECK_RET(ret);
+ lyd_insert_before_node(anchor, node);
+ } else {
+ /* insert as the last node, there is probably no other option */
+ ret = lyds_create_metadata(node);
+ LY_CHECK_RET(ret);
+ lyd_insert_after_node(first_sibling->prev, node);
+ }
+
+ if (first_sibling_p && !node->prev->next) {
+ /* move first sibling */
+ *first_sibling_p = node;
+ }
+
+ return LY_SUCCESS;
+}
+
+void
+lyd_insert_node(struct lyd_node *parent, struct lyd_node **first_sibling_p, struct lyd_node *node, ly_bool last)
+{
+ LY_ERR ret = LY_SUCCESS;
+
+ /* inserting list without its keys is not supported */
+ assert((parent || first_sibling_p) && node && (node->hash || !node->schema));
+ assert(!parent || !parent->schema ||
+ (parent->schema->nodetype & (LYS_CONTAINER | LYS_LIST | LYS_RPC | LYS_ACTION | LYS_NOTIF)));
+
+ if (!parent && first_sibling_p && (*first_sibling_p) && (*first_sibling_p)->parent) {
+ parent = lyd_parent(*first_sibling_p);
+ }
+
+ if (lyds_is_supported(node)) {
+ ret = lyd_insert_node_ordby_lyds(parent, first_sibling_p, node);
+ 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(node), "Data in \"%s\" are not sorted.", node->schema->name);
+ lyd_insert_node_ordby_schema(parent, first_sibling_p, node, last);
+ }
+ } else {
+ lyd_insert_node_ordby_schema(parent, first_sibling_p, node, last);
+ }
/* insert into parent HT */
lyd_insert_hash(node);
@@ -910,12 +1010,18 @@
void
lyd_unlink(struct lyd_node *node)
{
- struct lyd_node *iter;
+ struct lyd_node *iter, *leader;
if (!node) {
return;
}
+ /* unlink from the lyds tree */
+ if (lyds_is_supported(node)) {
+ lyd_find_sibling_val(node, node->schema, NULL, 0, &leader);
+ lyds_unlink(&leader, node);
+ }
+
/* update hashes while still linked into the tree */
lyd_unlink_hash(node);
diff --git a/src/tree_data.h b/src/tree_data.h
index 39b4994..a929d8b 100644
--- a/src/tree_data.h
+++ b/src/tree_data.h
@@ -47,6 +47,7 @@
struct lyd_node_term;
struct timespec;
struct lyxp_var;
+struct rb_node;
/**
* @page howtoData Data Instances
@@ -228,11 +229,12 @@
*
* When inserting a node into data tree (no matter if the node already exists, via ::lyd_insert_child() and
* ::lyd_insert_sibling(), or a new node is being created), the node is automatically inserted to the place respecting the
- * nodes order from the YANG schema. So the node is not inserted to the end or beginning of the siblings list, but after the
- * existing instance of the closest preceding sibling node from the schema. In case the node is opaq (it is not connected
- * with any schema node), it is placed to the end of the sibling node in the order they are inserted in. The only situation
- * when it is possible to influence the order of the nodes is the order of user-ordered list/leaf-list instances. In such
- * a case the ::lyd_insert_after() or ::lyd_insert_before() can be used.
+ * nodes order from the YANG schema. A leaf-list instances are sorted based on the value and the ::lyplg_type_sort_clb
+ * function defined in the given datatype. A list instances are ordered similarly based on keys. In case the node is opaq
+ * (it is not connected with any schema node), it is placed to the end of the sibling node in the order they are inserted in.
+ * The only situation when it is possible to influence the order of the nodes is the order of user-ordered list/leaf-list
+ * instances. In such a case the ::lyd_insert_after(), ::lyd_insert_before() can be used and ::lyd_insert_child(),
+ * ::lyd_insert_sibling() adds the node after the existing instance of the closest preceding sibling node from the schema.
*
* Creating data is generally possible in two ways, they can be combined. You can add nodes one-by-one based on
* the node name and/or its parent (::lyd_new_inner(), ::lyd_new_term(), ::lyd_new_any(), ::lyd_new_list(), ::lyd_new_list2()
@@ -527,6 +529,17 @@
#define LYD_CTX(node) ((node)->schema ? (node)->schema->module->ctx : ((const struct lyd_node_opaq *)(node))->ctx)
/**
+ * @brief Find out if the node is the only instance, i.e. it has no siblings with the same schema.
+ *
+ * @param[in] NODE Pointer to the struct lyd_node.
+ * @return 1 @p NODE is a single instance (is alone).
+ * @return 0 @p NODE is not alone.
+ */
+#define LYD_NODE_IS_ALONE(NODE) \
+ (((NODE)->prev == NODE) || \
+ (((NODE)->prev->schema != (NODE)->schema) && (!(NODE)->next || ((NODE)->schema != (NODE)->next->schema))))
+
+/**
* @brief Data input/output formats supported by libyang [parser](@ref howtoDataParsers) and
* [printer](@ref howtoDataPrinters) functions.
*/
@@ -710,6 +723,13 @@
};
/**
+ * @brief Special lyd_value structure for lyds tree value.
+ */
+struct lyd_value_lyds_tree {
+ struct rb_node *rbt; /**< Root of the Red-black tree. */
+};
+
+/**
* @brief Generic prefix and namespace mapping, meaning depends on the format.
*
* The union is used as a reference to the data's module and according to the format, it can be used as a key for
@@ -2006,7 +2026,8 @@
#define LYD_DUP_RECURSIVE 0x01 /**< Duplicate not just the node but also all the children. Note that
list's keys are always duplicated. */
-#define LYD_DUP_NO_META 0x02 /**< Do not duplicate metadata (or attributes) of any node. */
+#define LYD_DUP_NO_META 0x02 /**< Do not duplicate metadata (or attributes) of any node. Flag has no effect
+ on 'lyds_tree' metadata. */
#define LYD_DUP_WITH_PARENTS 0x04 /**< If a nested node is being duplicated, duplicate also all the parents.
Keys are also duplicated for lists. Return value does not change! */
#define LYD_DUP_WITH_FLAGS 0x08 /**< Also copy any data node flags. That will cause the duplicated data to preserve
diff --git a/src/tree_data_free.c b/src/tree_data_free.c
index 3927091..188b52c 100644
--- a/src/tree_data_free.c
+++ b/src/tree_data_free.c
@@ -24,6 +24,7 @@
#include "tree.h"
#include "tree_data.h"
#include "tree_data_internal.h"
+#include "tree_data_sorted.h"
#include "tree_schema.h"
static void
@@ -222,7 +223,6 @@
} else if (node->schema->nodetype & LYD_NODE_INNER) {
/* remove children hash table in case of inner data node */
lyht_free(((struct lyd_node_inner *)node)->children_ht, NULL);
- ((struct lyd_node_inner *)node)->children_ht = NULL;
/* free the children */
LY_LIST_FOR_SAFE(lyd_child(node), next, iter) {
@@ -286,6 +286,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_free_subtree(iter);
diff --git a/src/tree_data_internal.h b/src/tree_data_internal.h
index 5168101..8f22fac 100644
--- a/src/tree_data_internal.h
+++ b/src/tree_data_internal.h
@@ -393,7 +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.
+ * @param[in] last If set, do not search for the correct anchor but always insert at the end. Flag has no effect
+ * for (leaf-)list instances that have the LYS_ORDBY_SYSTEM flag set.
*/
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_new.c b/src/tree_data_new.c
index 13bb9bc..289d2da 100644
--- a/src/tree_data_new.c
+++ b/src/tree_data_new.c
@@ -43,6 +43,7 @@
#include "set.h"
#include "tree.h"
#include "tree_data_internal.h"
+#include "tree_data_sorted.h"
#include "tree_edit.h"
#include "tree_schema.h"
#include "tree_schema_internal.h"
@@ -1272,17 +1273,19 @@
}
/**
- * @brief Change the value of @p term by @p val.
+ * @brief Change the value of @p term by @p val and reinsert the node if necessary.
*
- * @param[in] term Term node to change.
+ * Reinserting ensures that the node is in the correct position and the data instances remain properly ordered.
+ *
+ * @param[in] term Term node to change. If it is a key, the parental list is inserted again.
* @param[in] val New value for @p term.
* @return LY_SUCCESS on success.
*/
static LY_ERR
-lyd_change_term_value(struct lyd_node_term *term, struct lyd_value *val)
+lyd_change_node_value(struct lyd_node_term *term, struct lyd_value *val)
{
LY_ERR ret = LY_SUCCESS;
- struct lyd_node *target;
+ struct lyd_node *target, *first;
if (term->schema->nodetype == LYS_LEAFLIST) {
target = (struct lyd_node *)term;
@@ -1296,11 +1299,24 @@
return LY_SUCCESS;
}
- /* unlink hash */
- lyd_unlink_hash(target);
- /* change value */
- term->value.realtype->plugin->free(LYD_CTX(term), &term->value);
- term->value = *val;
+ if (!LYD_NODE_IS_ALONE(target) && lyds_is_supported(target)) {
+ /* changing the value may cause a change in the order */
+ first = lyd_first_sibling(target);
+ first = first == target ? first->next : first;
+ /* unlink hash and unlink the target node in the lyds tree */
+ lyd_unlink_tree(target);
+ /* change value */
+ term->value.realtype->plugin->free(LYD_CTX(term), &term->value);
+ term->value = *val;
+ /* reinserting */
+ lyd_insert_node(NULL, &first, target, 0);
+ } else {
+ /* unlink hash */
+ lyd_unlink_hash(target);
+ /* change value */
+ term->value.realtype->plugin->free(LYD_CTX(term), &term->value);
+ term->value = *val;
+ }
lyd_hash(target);
ret = lyd_insert_hash(target);
@@ -1347,7 +1363,7 @@
/* compare original and new value */
if (type->plugin->compare(LYD_CTX(term), &t->value, &val)) {
/* values differ, switch them */
- lyd_change_term_value(t, &val);
+ lyd_change_node_value(t, &val);
/* make the node non-validated */
term->flags &= LYD_NEW;
val_change = 1;
diff --git a/src/tree_data_sorted.c b/src/tree_data_sorted.c
new file mode 100644
index 0000000..13a0ad5
--- /dev/null
+++ b/src/tree_data_sorted.c
@@ -0,0 +1,1075 @@
+/**
+ * @file tree_data_sorted.c
+ * @author Adam Piecek <piecek@cesnet.cz>
+ * @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 <provos@citi.umich.edu>
+ * Copyright (c) 2016 David Gwynne <dlg@openbsd.org>
+ */
+
+#include <assert.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "common.h"
+#include "dict.h"
+#include "log.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 Metadata name of the Red-black tree.
+ */
+#define RB_NAME "lyds_tree"
+#define RB_NAME_LEN strlen(RB_NAME)
+
+/**
+ * @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, RB_NAME)) {
+ 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] rbn Node to free.
+ */
+static void
+rb_free_node(struct rb_node *rbn)
+{
+ free(rbn);
+}
+
+/**
+ * @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.
+ */
+static void
+rb_insert_node(struct rb_node **rbt, struct rb_node *rbn)
+{
+ 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;
+ }
+
+ tmp = *rbt;
+ while (tmp != NULL) {
+ parent = tmp;
+
+ comp = rb_compare(RBN_DNODE(tmp), RBN_DNODE(rbn));
+ if (comp > 0) {
+ tmp = RBN_LEFT(tmp);
+ } 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);
+}
+
+/**
+ * @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;
+}
+
+/**
+ * @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);
+ assert(rbn && (RBN_DNODE(rbn) == node));
+
+ /* remove node */
+ rbn = rb_remove(rbt, rbn);
+ *removed = rbn;
+
+ /* 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(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] 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 **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(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);
+ }
+}
+
+LY_ERR
+lyds_create_metadata(struct lyd_node *leader)
+{
+ LY_ERR ret;
+ uint32_t i;
+ struct lyd_meta *meta;
+ struct rb_node *rbn = NULL, *rbt;
+ struct lys_module *modyang;
+
+ LY_CHECK_ARG_RET(NULL, leader, leader->schema, LY_EINVAL);
+
+ rbt = lyds_get_rb_tree(leader, &meta);
+ if (rbt) {
+ /* nothing to do, the metadata is already set */
+ return LY_SUCCESS;
+ }
+ LY_CHECK_RET(!LYD_NODE_IS_ALONE(leader), LY_EINT);
+
+ if (meta) {
+ /* if the node was duplicated, then the meta is present, but its value is NULL */
+ ret = lyds_create_node(leader, &rbn);
+ LY_CHECK_RET(ret);
+ RBT_SET(meta, rbn);
+ 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 with a root that contains @p leader */
+ ret = lyd_create_meta(leader, &meta, modyang, RB_NAME, RB_NAME_LEN, (void *)leader, 0, 0, NULL,
+ LY_VALUE_LYB, NULL, LYD_HINT_DATA, leader->schema, 0, NULL);
+ LY_CHECK_RET(ret);
+
+ 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);
+
+ return LY_SUCCESS;
+}
+
+LY_ERR
+lyds_insert(struct lyd_node **leader, struct lyd_node *node)
+{
+ LY_ERR ret = LY_SUCCESS;
+ struct rb_node *rbn, *rbt, *orig_rbt;
+ struct lyd_meta *root_meta;
+
+ LY_CHECK_ARG_RET(NULL, leader, node, LY_EINVAL);
+
+ /* check that the @p node has no siblings */
+ if (!LYD_NODE_IS_ALONE(node)) {
+ /* @p node must not be part of another Red-black tree, only single node can satisfy this condition */
+ return LY_EINVAL;
+ }
+
+ /* Clear the @p node. It may have unnecessary data due to duplication or due to lyds_unlink_node() calls. */
+ rbt = lyds_get_rb_tree(node, &root_meta);
+ if (root_meta) {
+ assert(!rbt || (!RBN_LEFT(rbt) && !RBN_PARENT(rbt) && !RBN_RIGHT(rbt)));
+ /* node has no siblings but contains an empty tree or a tree where it is alone */
+ lyd_free_meta_single(root_meta);
+ }
+
+ /* get the Red-black tree from the @p leader */
+ rbt = orig_rbt = lyds_get_rb_tree(*leader, &root_meta);
+ LY_CHECK_ERR_RET(!rbt, LOGWRN(LYD_CTX(node), "Red-black tree not found."), LY_EINT);
+
+ /* insert red-black node with @p node to the Red-black tree */
+ ret = rb_insert(node, &rbt, &rbn);
+ LY_CHECK_RET(ret);
+ if (orig_rbt != rbt) {
+ /* the root of the Red-black tree has changed due to insertion, so update the pointer to the root */
+ RBT_SET(root_meta, rbt);
+ }
+
+ /* Insert the node to the correct order. */
+ lyds_link_data_node(leader, node, root_meta, rbn);
+
+ 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);
+
+ if (LYD_NODE_IS_ALONE(node)) {
+ /* node is the leader and it is alone, so free metadata including Red-black tree */
+ lyds_get_rb_tree(node, &root_meta);
+ /* release the metadata and the Red-black tree. */
+ lyd_free_meta_single(root_meta);
+ 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);
+
+ if (!rbt) {
+ /* the Red-black tree is removed, so delete the metadata too */
+ lyd_free_meta_single(root_meta);
+ }
+}
+
+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);
+ }
+}
diff --git a/src/tree_data_sorted.h b/src/tree_data_sorted.h
new file mode 100644
index 0000000..e3f2903
--- /dev/null
+++ b/src/tree_data_sorted.h
@@ -0,0 +1,107 @@
+/**
+ * @file tree_data_sorted.h
+ * @author Adam Piecek <piecek@cesnet.cz>
+ * @brief Binary search tree (BST) for sorting data nodes.
+ *
+ * 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
+ */
+
+#ifndef _LYDS_TREE_H_
+#define _LYDS_TREE_H_
+
+#include "log.h"
+
+struct lyd_node;
+struct rb_node;
+
+/* This functionality applies to list and leaf-list with the "ordered-by system" statement,
+ * which is implicit. The BST is implemented using a Red-black tree and is used for sorting nodes.
+ * For example, a list of valid users would typically be sorted alphabetically. This tree is saved
+ * in the first instance of the leaf-list/list in the metadata named lyds_tree. Thanks to the tree,
+ * it is possible to insert a sibling data node in such a way that the order of the nodes is preserved.
+ * The decision whether the value is greater or less takes place in the callback function ::lyplg_type_sort_clb
+ * in the corresponding type.
+ *
+ * Parameters always must be from the same context.
+ */
+
+/**
+ * @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.
+ *
+ * @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);
+
+/**
+ * @brief Create metadata and the BST with @p leader as the root.
+ *
+ * Creates the BST and stores it in metadata that is also created or uses an existing one.
+ * If the node already contains a BST, then nothing happens.
+ *
+ * @param[in] leader First and only instance of the (leaf-)list.
+ * @return LY_ERR value.
+ */
+LY_ERR lyds_create_metadata(struct lyd_node *leader);
+
+/**
+ * @brief Create new BST node.
+ *
+ * @param[in] node Data node to link with new red-black node.
+ * @param[out] rbn Created red-black node.
+ * @return LY_SUCCESS on success.
+ */
+LY_ERR lyds_create_node(struct lyd_node *node, struct rb_node **rbn);
+
+/**
+ * @brief Insert the @p node into BST and into @p leader's siblings.
+ *
+ * Parameters @p leader and @p node must be from the same context.
+ * Sibling data nodes of the @p leader are also modified.
+ *
+ * @param[in,out] leader First instance of the (leaf-)list. Must contain BST and if it doesn't, call
+ * lyds_create() first. After executing the function, @p leader does not have to be be first if @p node was
+ * inserted before @p leader.
+ * @param[in] node A single (without siblings) node or tree to be inserted. It must not be part of another BST
+ * and if it is, it must be unlinked first.
+ * @return LY_ERR value.
+ */
+LY_ERR lyds_insert(struct lyd_node **leader, struct lyd_node *node);
+
+/**
+ * @brief Unlink (remove) the specified data node from BST.
+ *
+ * Pointers in sibling data nodes (lyd_node) are NOT modified. This means that the data node is NOT unlinked.
+ * If the BST will remain empty, it will be freed along with the metadata.
+ * Hash for data nodes is not removed.
+ *
+ * @param[in,out] leader First instance of (leaf-)list. If it is NULL, nothing happens.
+ * @param[in] node Some instance of (leaf-)list to be unlinked.
+ */
+void lyds_unlink(struct lyd_node **leader, struct lyd_node *node);
+
+/**
+ * @brief Release the metadata including BST.
+ *
+ * No more nodes can be inserted after the function is executed.
+ *
+ * @param[in] node Data node of the type (leaf-)list that may contain metadata and BST.
+ */
+void lyds_free_metadata(struct lyd_node *node);
+
+/**
+ * @brief Release all BST nodes including the root.
+ *
+ * @param[in] rbt Root of the Red-black tree.
+ */
+void lyds_free_tree(struct rb_node *rbt);
+
+#endif /* _LYDS_TREE_H_ */
diff --git a/src/tree_schema.c b/src/tree_schema.c
index 77bbd8e..e8b9857 100644
--- a/src/tree_schema.c
+++ b/src/tree_schema.c
@@ -1738,6 +1738,67 @@
return LY_SUCCESS;
}
+/**
+ * @brief Define a new internal 'lyds_tree' value for metadata.
+ *
+ * The 'lyds_tree' is a data type containing a reference to a binary search tree
+ * by which the data nodes are ordered.
+ *
+ * @param[in] pctx Parse context.
+ * @param[in] mod Parsed module to add to.
+ * @return LY_SUCCESS on success.
+ * @return LY_ERR on error.
+ */
+static LY_ERR
+lysp_add_internal_yang(struct lysp_ctx *pctx, struct lysp_module *mod)
+{
+ struct lysp_ext_instance *extp, *prev_exts = mod->exts;
+ struct lysp_stmt *stmt;
+ struct lysp_tpdf *tpdf;
+ uint32_t idx;
+
+ /* add new typedef */
+ LY_ARRAY_NEW_RET(PARSER_CTX(pctx), mod->typedefs, tpdf, LY_EMEM);
+ LY_CHECK_RET(lydict_insert(PARSER_CTX(pctx), "lyds_tree", 0, &tpdf->name));
+ LY_CHECK_RET(lydict_insert(PARSER_CTX(pctx), "uint64", 0, &tpdf->type.name));
+ tpdf->type.pmod = mod;
+
+ /* add new extension instance */
+ LY_ARRAY_NEW_RET(PARSER_CTX(pctx), mod->exts, extp, LY_EMEM);
+
+ /* fill in the extension instance fields */
+ LY_CHECK_RET(lydict_insert(mod->mod->ctx, "md:annotation", 0, &extp->name));
+ LY_CHECK_RET(lydict_insert(mod->mod->ctx, "lyds_tree", 0, &extp->argument));
+ extp->format = LY_VALUE_SCHEMA;
+ extp->prefix_data = mod;
+ extp->parent = mod;
+ extp->parent_stmt = LY_STMT_MODULE;
+ extp->flags = LYS_INTERNAL;
+
+ /* prepare for metadata plugin */
+ extp->child = stmt = calloc(1, sizeof *extp->child);
+ LY_CHECK_ERR_RET(!stmt, LOGMEM(mod->mod->ctx), LY_EMEM);
+ LY_CHECK_RET(lydict_insert(mod->mod->ctx, "type", 0, &stmt->stmt));
+ LY_CHECK_RET(lydict_insert(mod->mod->ctx, "lyds_tree", 0, &stmt->arg));
+ stmt->format = LY_VALUE_SCHEMA;
+ stmt->prefix_data = mod;
+ stmt->kw = LY_STMT_TYPE;
+
+ if (!prev_exts) {
+ /* first extension instances */
+ assert(pctx->main_ctx == pctx);
+ LY_CHECK_RET(ly_set_add(&pctx->ext_inst, mod->exts, 1, NULL));
+ } else {
+ /* replace previously stored extension instances */
+ if (!ly_set_contains(&pctx->ext_inst, prev_exts, &idx)) {
+ LOGINT_RET(mod->mod->ctx);
+ }
+ pctx->ext_inst.objs[idx] = mod->exts;
+ }
+
+ return LY_SUCCESS;
+}
+
LY_ERR
lys_parse_in(struct ly_ctx *ctx, struct ly_in *in, LYS_INFORMAT format,
LY_ERR (*custom_check)(const struct ly_ctx *ctx, struct lysp_module *mod, struct lysp_submodule *submod, void *data),
@@ -1852,6 +1913,8 @@
LY_CHECK_GOTO(ret = lysp_add_internal_ietf_netconf(pctx, mod->parsed), cleanup);
} else if (!strcmp(mod->name, "ietf-netconf-with-defaults")) {
LY_CHECK_GOTO(ret = lysp_add_internal_ietf_netconf_with_defaults(pctx, mod->parsed), cleanup);
+ } else if (!strcmp(mod->name, "yang")) {
+ LY_CHECK_GOTO(ret = lysp_add_internal_yang(pctx, mod->parsed), cleanup);
}
/* add the module into newly created module set, will also be freed from there on any error */