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/CMakeLists.txt b/CMakeLists.txt
index 86a2abe..194babd 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -94,6 +94,7 @@
     src/plugins_types/instanceid_keys.c
     src/plugins_types/integer.c
     src/plugins_types/leafref.c
+    src/plugins_types/lyds_tree.c
     src/plugins_types/string.c
     src/plugins_types/union.c
     src/plugins_types/ipv4_address.c
@@ -134,6 +135,7 @@
     src/schema_compile_node.c
     src/schema_compile_amend.c
     src/schema_features.c
+    src/tree_data_sorted.c
     src/tree_schema.c
     src/tree_schema_free.c
     src/tree_schema_common.c
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 */
diff --git a/tests/utests/CMakeLists.txt b/tests/utests/CMakeLists.txt
index ac47611..648098a 100644
--- a/tests/utests/CMakeLists.txt
+++ b/tests/utests/CMakeLists.txt
@@ -61,6 +61,7 @@
 ly_add_utest(NAME printer_tree SOURCES schema/test_printer_tree.c)
 
 ly_add_utest(NAME tree_data SOURCES data/test_tree_data.c)
+ly_add_utest(NAME tree_data_sorted SOURCES data/test_tree_data_sorted.c)
 ly_add_utest(NAME new SOURCES data/test_new.c)
 ly_add_utest(NAME parser_xml SOURCES data/test_parser_xml.c)
 ly_add_utest(NAME printer_xml SOURCES data/test_printer_xml.c)
diff --git a/tests/utests/data/test_diff.c b/tests/utests/data/test_diff.c
index 0edd6bd..3c313c4 100644
--- a/tests/utests/data/test_diff.c
+++ b/tests/utests/data/test_diff.c
@@ -594,13 +594,13 @@
             "</df>\n";
     const char *xml3 = "<df xmlns=\"urn:libyang:tests:defaults\">\n"
             "  <list>\n"
-            "    <name>b</name>\n"
-            "    <value>-2</value>\n"
-            "  </list>\n"
-            "  <list>\n"
             "    <name>a</name>\n"
             "    <value>2</value>\n"
             "  </list>\n"
+            "  <list>\n"
+            "    <name>b</name>\n"
+            "    <value>-2</value>\n"
+            "  </list>\n"
             "</df>\n";
 
     const char *out_diff_1 =
@@ -620,14 +620,14 @@
             "</df>\n";
     const char *out_diff_2 =
             "<df xmlns=\"urn:libyang:tests:defaults\" xmlns:yang=\"urn:ietf:params:xml:ns:yang:1\" yang:operation=\"none\">\n"
-            "  <list yang:operation=\"delete\">\n"
-            "    <name>c</name>\n"
-            "    <value>3</value>\n"
-            "  </list>\n"
             "  <list yang:operation=\"create\">\n"
             "    <name>a</name>\n"
             "    <value>2</value>\n"
             "  </list>\n"
+            "  <list yang:operation=\"delete\">\n"
+            "    <name>c</name>\n"
+            "    <value>3</value>\n"
+            "  </list>\n"
             "</df>\n";
     const char *out_merge =
             "<df xmlns=\"urn:libyang:tests:defaults\" xmlns:yang=\"urn:ietf:params:xml:ns:yang:1\" yang:operation=\"none\">\n"
@@ -655,6 +655,18 @@
     xml1 =
             "<df xmlns=\"urn:libyang:tests:defaults\">"
             "  <list>"
+            "    <name>n0</name>"
+            "    <value>26</value>"
+            "    <list2>"
+            "      <name2>n22</name2>"
+            "      <value2>26</value2>"
+            "    </list2>"
+            "    <list2>"
+            "      <name2>n23</name2>"
+            "      <value2>26</value2>"
+            "    </list2>"
+            "  </list>"
+            "  <list>"
             "    <name>n1</name>"
             "    <value>25</value>"
             "    <list2>"
@@ -686,18 +698,6 @@
             "      <value2>26</value2>"
             "    </list2>"
             "  </list>"
-            "  <list>"
-            "    <name>n0</name>"
-            "    <value>26</value>"
-            "    <list2>"
-            "      <name2>n22</name2>"
-            "      <value2>26</value2>"
-            "    </list2>"
-            "    <list2>"
-            "      <name2>n23</name2>"
-            "      <value2>26</value2>"
-            "    </list2>"
-            "  </list>"
             "</df>";
     xml2 =
             "<df xmlns=\"urn:libyang:tests:defaults\">"
@@ -717,6 +717,14 @@
 
     CHECK_LYD_STRING(diff,
             "<df xmlns=\"urn:libyang:tests:defaults\" xmlns:yang=\"urn:ietf:params:xml:ns:yang:1\" yang:operation=\"none\">\n"
+            "  <list>\n"
+            "    <name>n0</name>\n"
+            "    <value yang:operation=\"replace\" yang:orig-default=\"false\" yang:orig-value=\"26\">30</value>\n"
+            "    <list2 yang:operation=\"delete\">\n"
+            "      <name2>n22</name2>\n"
+            "      <value2>26</value2>\n"
+            "    </list2>\n"
+            "  </list>\n"
             "  <list yang:operation=\"delete\">\n"
             "    <name>n1</name>\n"
             "    <value>25</value>\n"
@@ -749,14 +757,6 @@
             "      <value2>26</value2>\n"
             "    </list2>\n"
             "  </list>\n"
-            "  <list yang:operation=\"none\">\n"
-            "    <name>n0</name>\n"
-            "    <value yang:operation=\"replace\" yang:orig-default=\"false\" yang:orig-value=\"26\">30</value>\n"
-            "    <list2 yang:operation=\"delete\">\n"
-            "      <name2>n22</name2>\n"
-            "      <value2>26</value2>\n"
-            "    </list2>\n"
-            "  </list>\n"
             "</df>\n");
 
     lyd_free_all(data1);
diff --git a/tests/utests/data/test_merge.c b/tests/utests/data/test_merge.c
index 3e7b772..9a31816 100644
--- a/tests/utests/data/test_merge.c
+++ b/tests/utests/data/test_merge.c
@@ -130,24 +130,6 @@
     const char *output_template =
             "<modules-state xmlns=\"urn:ietf:params:xml:ns:yang:ietf-yang-library\">\n"
             "  <module>\n"
-            "    <name>yang</name>\n"
-            "    <revision>2016-02-11</revision>\n"
-            "    <namespace>urn:ietf:params:xml:ns:yang:1</namespace>\n"
-            "    <conformance-type>implement</conformance-type>\n"
-            "  </module>\n"
-            "  <module>\n"
-            "    <name>ietf-yang-library</name>\n"
-            "    <revision>2016-02-01</revision>\n"
-            "    <namespace>urn:ietf:params:xml:ns:yang:ietf-yang-library</namespace>\n"
-            "    <conformance-type>implement</conformance-type>\n"
-            "  </module>\n"
-            "  <module>\n"
-            "    <name>ietf-netconf-acm</name>\n"
-            "    <revision>2012-02-22</revision>\n"
-            "    <namespace>urn:ietf:params:xml:ns:yang:ietf-netconf-acm</namespace>\n"
-            "    <conformance-type>implement</conformance-type>\n"
-            "  </module>\n"
-            "  <module>\n"
             "    <name>ietf-netconf</name>\n"
             "    <revision>2011-06-01</revision>\n"
             "    <namespace>urn:ietf:params:xml:ns:netconf:base:1.0</namespace>\n"
@@ -160,6 +142,12 @@
             "    <conformance-type>implement</conformance-type>\n"
             "  </module>\n"
             "  <module>\n"
+            "    <name>ietf-netconf-acm</name>\n"
+            "    <revision>2012-02-22</revision>\n"
+            "    <namespace>urn:ietf:params:xml:ns:yang:ietf-netconf-acm</namespace>\n"
+            "    <conformance-type>implement</conformance-type>\n"
+            "  </module>\n"
+            "  <module>\n"
             "    <name>ietf-netconf-monitoring</name>\n"
             "    <revision>2010-10-04</revision>\n"
             "    <namespace>urn:ietf:params:xml:ns:yang:ietf-netconf-monitoring</namespace>\n"
@@ -171,6 +159,18 @@
             "    <namespace>urn:ietf:params:xml:ns:yang:ietf-netconf-with-defaults</namespace>\n"
             "    <conformance-type>implement</conformance-type>\n"
             "  </module>\n"
+            "  <module>\n"
+            "    <name>ietf-yang-library</name>\n"
+            "    <revision>2016-02-01</revision>\n"
+            "    <namespace>urn:ietf:params:xml:ns:yang:ietf-yang-library</namespace>\n"
+            "    <conformance-type>implement</conformance-type>\n"
+            "  </module>\n"
+            "  <module>\n"
+            "    <name>yang</name>\n"
+            "    <revision>2016-02-11</revision>\n"
+            "    <namespace>urn:ietf:params:xml:ns:yang:1</namespace>\n"
+            "    <conformance-type>implement</conformance-type>\n"
+            "  </module>\n"
             "</modules-state>\n";
 
     struct lyd_node *target;
diff --git a/tests/utests/data/test_parser_json.c b/tests/utests/data/test_parser_json.c
index 0361b6a..bebab7b 100644
--- a/tests/utests/data/test_parser_json.c
+++ b/tests/utests/data/test_parser_json.c
@@ -204,7 +204,6 @@
             1, LYS_LEAFLIST, 0, 0, NULL, 0);
     ll = (struct lyd_node_term *)tree;
     CHECK_LYD_VALUE(ll->value, UINT8, "10", 10);
-    assert_null(ll->meta);
 
     assert_non_null(tree->next);
     CHECK_LYSC_NODE(tree->next->schema, NULL, 0, LYS_CONFIG_W | LYS_STATUS_CURR | LYS_ORDBY_SYSTEM, 1, "ll1",
@@ -227,8 +226,8 @@
             1, LYS_LEAFLIST, 0, 0, NULL, 0);
     ll = (struct lyd_node_term *)tree;
     CHECK_LYD_VALUE(ll->value, UINT8, "1", 1);
-    CHECK_LYD_META(ll->meta, 1, "hint", 1, 1,  INT8, "1", 1);
-    CHECK_LYD_META(ll->meta->next, 1, "hint", 0, 1,  INT8, "10", 10);
+    CHECK_LYD_META(ll->meta->next, 1, "hint", 1, 1,  INT8, "1", 1);
+    CHECK_LYD_META(ll->meta->next->next, 1, "hint", 0, 1,  INT8, "10", 10);
 
     assert_non_null(tree->next);
     CHECK_LYSC_NODE(tree->next->schema, NULL, 0, LYS_CONFIG_W | LYS_STATUS_CURR | LYS_ORDBY_SYSTEM, 1, "ll1",
diff --git a/tests/utests/data/test_tree_data_sorted.c b/tests/utests/data/test_tree_data_sorted.c
new file mode 100644
index 0000000..459e844
--- /dev/null
+++ b/tests/utests/data/test_tree_data_sorted.c
@@ -0,0 +1,1141 @@
+/**
+ * @file test_tree_data_sorted.c
+ * @author Adam Piecek <piecek@cesnet.cz>
+ * @brief Unit tests for functions from tree_data_sorted.h
+ *
+ * Copyright (c) 2018-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
+ */
+#define _UTEST_MAIN_
+#include "utests.h"
+
+#include "common.h"
+#include "libyang.h"
+#include "tree_data_internal.h"
+#include "tree_data_sorted.h"
+
+#define META_NAME "lyds_tree"
+
+static void *
+get_rbt(struct lyd_meta *meta)
+{
+    struct lyd_value_lyds_tree *lt;
+
+    if (!meta) {
+        return NULL;
+    }
+
+    LYD_VALUE_GET(&meta->value, lt);
+    return lt ? lt->rbt : NULL;
+}
+
+static void
+test_insert_top_level_list(void **state)
+{
+    const char *schema;
+    struct lys_module *mod;
+    struct lyd_node *first, *node;
+
+    schema = "module a {namespace urn:tests:a;prefix a;yang-version 1.1;revision 2014-05-08;"
+            "list lst {key \"k\"; leaf k {type uint32;}}}";
+    UTEST_ADD_MODULE(schema, LYS_IN_YANG, NULL, &mod);
+
+    assert_int_equal(lyd_new_list(NULL, mod, "lst", 0, &first, "2"), LY_SUCCESS);
+    assert_int_equal(lyd_new_list(NULL, mod, "lst", 0, &node, "1"), LY_SUCCESS);
+    assert_int_equal(lyd_insert_sibling(first, node, NULL), LY_SUCCESS);
+    assert_int_equal(lyd_new_list(NULL, mod, "lst", 0, &node, "3"), LY_SUCCESS);
+    assert_int_equal(lyd_insert_sibling(first, node, NULL), LY_SUCCESS);
+    assert_true(first->next && first->prev && first->prev->meta);
+    assert_string_equal(first->prev->meta->name, META_NAME);
+    assert_string_equal(lyd_get_value(lyd_child(first->prev)), "1");
+    assert_string_equal(lyd_get_value(lyd_child(first)), "2");
+    assert_string_equal(lyd_get_value(lyd_child(first->next)), "3");
+    lyd_free_all(first);
+}
+
+static void
+test_insert_top_level_leaflist(void **state)
+{
+    const char *schema;
+    struct lys_module *mod;
+    struct lyd_node *first, *node;
+
+    schema = "module a {namespace urn:tests:a;prefix a;yang-version 1.1;revision 2014-05-08;"
+            "leaf-list ll {type uint32;}}";
+    UTEST_ADD_MODULE(schema, LYS_IN_YANG, NULL, &mod);
+
+    assert_int_equal(lyd_new_term(NULL, mod, "ll", "2", 0, &first), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(NULL, mod, "ll", "1", 0, &node), LY_SUCCESS);
+    assert_int_equal(lyd_insert_sibling(first, node, NULL), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(NULL, mod, "ll", "3", 0, &node), LY_SUCCESS);
+    assert_int_equal(lyd_insert_sibling(first, node, NULL), LY_SUCCESS);
+    assert_true(first->next && first->prev && first->prev->meta);
+    assert_string_equal(first->prev->meta->name, META_NAME);
+    assert_string_equal(lyd_get_value(first->prev), "1");
+    assert_string_equal(lyd_get_value(first), "2");
+    assert_string_equal(lyd_get_value(first->next), "3");
+    lyd_free_all(first);
+}
+
+static void
+test_insert_cont_list(void **state)
+{
+    const char *schema;
+    struct lys_module *mod;
+    struct lyd_node *cont, *node;
+
+    schema = "module a {namespace urn:tests:a;prefix a;yang-version 1.1;revision 2014-05-08;"
+            "container cn { list lst {key \"k\"; leaf k {type uint32;}}}}";
+    UTEST_ADD_MODULE(schema, LYS_IN_YANG, NULL, &mod);
+
+    assert_int_equal(lyd_new_inner(NULL, mod, "cn", 0, &cont), LY_SUCCESS);
+    assert_int_equal(lyd_new_list(cont, mod, "lst", 0, NULL, "2"), LY_SUCCESS);
+    assert_int_equal(lyd_new_list(cont, mod, "lst", 0, NULL, "1"), LY_SUCCESS);
+    assert_int_equal(lyd_new_list(cont, mod, "lst", 0, NULL, "3"), LY_SUCCESS);
+    node = lyd_child(cont);
+    assert_true(node && node->meta && node->next && node->next->next);
+    assert_string_equal(node->meta->name, META_NAME);
+    assert_string_equal(lyd_get_value(lyd_child(node)), "1");
+    assert_string_equal(lyd_get_value(lyd_child(node->next)), "2");
+    assert_string_equal(lyd_get_value(lyd_child(node->next->next)), "3");
+    lyd_free_all(cont);
+}
+
+static void
+test_insert_cont_leaflist(void **state)
+{
+    const char *schema;
+    struct lys_module *mod;
+    struct lyd_node *cont, *node;
+
+    schema = "module a {namespace urn:tests:a;prefix a;yang-version 1.1;revision 2014-05-08;"
+            "container cn { leaf-list ll {type uint32;}}}";
+    UTEST_ADD_MODULE(schema, LYS_IN_YANG, NULL, &mod);
+
+    assert_int_equal(lyd_new_inner(NULL, mod, "cn", 0, &cont), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(cont, mod, "ll", "2", 0, NULL), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(cont, mod, "ll", "1", 0, NULL), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(cont, mod, "ll", "3", 0, NULL), LY_SUCCESS);
+    node = lyd_child(cont);
+    assert_true(node && node->next && node->next->next && node->meta);
+    assert_string_equal(node->meta->name, META_NAME);
+    assert_string_equal(lyd_get_value(node), "1");
+    assert_string_equal(lyd_get_value(node->next), "2");
+    assert_string_equal(lyd_get_value(node->next->next), "3");
+    lyd_free_all(cont);
+}
+
+static void
+test_try_user_order_func(void **state)
+{
+    const char *schema;
+    struct lys_module *mod;
+    struct lyd_node *sibl, *node;
+
+    schema = "module a {namespace urn:tests:a;prefix a;yang-version 1.1;revision 2014-05-08;"
+            "leaf-list ll {type uint32;}}";
+    UTEST_ADD_MODULE(schema, LYS_IN_YANG, NULL, &mod);
+
+    assert_int_equal(lyd_new_term(NULL, mod, "ll", "2", 0, &sibl), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(NULL, mod, "ll", "1", 0, &node), LY_SUCCESS);
+    assert_int_equal(lyd_insert_before(sibl, node), LY_EINVAL);
+    CHECK_LOG_CTX("Can be used only for user-ordered nodes.", NULL, 0);
+    assert_int_equal(lyd_insert_after(sibl, node), LY_EINVAL);
+    CHECK_LOG_CTX("Can be used only for user-ordered nodes.", NULL, 0);
+    lyd_free_all(node);
+    lyd_free_all(sibl);
+}
+
+static void
+test_ordered_by_user(void **state)
+{
+    const char *schema;
+    struct lys_module *mod;
+    struct lyd_node *cont, *node;
+
+    schema = "module a {namespace urn:tests:a;prefix a;yang-version 1.1;revision 2014-05-08;"
+            "container cn { leaf-list ll {type uint32; ordered-by user;}}}";
+    UTEST_ADD_MODULE(schema, LYS_IN_YANG, NULL, &mod);
+    assert_int_equal(lyd_new_inner(NULL, mod, "cn", 0, &cont), LY_SUCCESS);
+
+    assert_int_equal(lyd_new_term(cont, mod, "ll", "2", 0, NULL), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(cont, mod, "ll", "1", 0, NULL), LY_SUCCESS);
+    node = lyd_child(cont);
+    assert_true(node && !node->meta);
+    assert_string_equal(lyd_get_value(node), "2");
+    assert_string_equal(lyd_get_value(node->next), "1");
+    lyd_free_all(cont);
+}
+
+static void
+test_remove(void **state)
+{
+    const char *schema;
+    struct lys_module *mod;
+    struct lyd_node *cont, *node, *deleted;
+
+    schema = "module a {namespace urn:tests:a;prefix a;yang-version 1.1;revision 2014-05-08;"
+            "container cn { leaf-list ll {type uint32;}}}";
+    UTEST_ADD_MODULE(schema, LYS_IN_YANG, NULL, &mod);
+
+    /* Remove first */
+    assert_int_equal(lyd_new_inner(NULL, mod, "cn", 0, &cont), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(cont, mod, "ll", "1", 0, NULL), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(cont, mod, "ll", "2", 0, NULL), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(cont, mod, "ll", "3", 0, NULL), LY_SUCCESS);
+    node = lyd_child(cont);
+    assert_true(node && node->next && node->next->next && node->meta);
+    assert_string_equal(node->meta->name, META_NAME);
+    deleted = node;
+    lyd_unlink_tree(deleted);
+    lyd_free_tree(deleted);
+    node = lyd_child(cont);
+    assert_true(node && node->next && node->meta);
+    assert_string_equal(node->meta->name, META_NAME);
+    assert_string_equal(lyd_get_value(node), "2");
+    assert_string_equal(lyd_get_value(node->next), "3");
+    lyd_free_all(cont);
+
+    /* Remove middle */
+    assert_int_equal(lyd_new_inner(NULL, mod, "cn", 0, &cont), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(cont, mod, "ll", "1", 0, NULL), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(cont, mod, "ll", "2", 0, NULL), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(cont, mod, "ll", "3", 0, NULL), LY_SUCCESS);
+    node = lyd_child(cont);
+    assert_true(node && node->next && node->next->next && node->meta);
+    assert_string_equal(node->meta->name, META_NAME);
+    deleted = node->next;
+    lyd_unlink_tree(deleted);
+    lyd_free_tree(deleted);
+    node = lyd_child(cont);
+    assert_true(node && node->next && node->meta);
+    assert_string_equal(node->meta->name, META_NAME);
+    assert_string_equal(lyd_get_value(node), "1");
+    assert_string_equal(lyd_get_value(node->next), "3");
+    lyd_free_all(cont);
+
+    /* Remove last */
+    assert_int_equal(lyd_new_inner(NULL, mod, "cn", 0, &cont), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(cont, mod, "ll", "1", 0, NULL), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(cont, mod, "ll", "2", 0, NULL), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(cont, mod, "ll", "3", 0, NULL), LY_SUCCESS);
+    node = lyd_child(cont);
+    assert_true(node && node->next && node->next->next && node->meta);
+    assert_string_equal(node->meta->name, META_NAME);
+    deleted = node->next->next;
+    lyd_unlink_tree(deleted);
+    lyd_free_tree(deleted);
+    node = lyd_child(cont);
+    assert_true(node && node->next && node->meta);
+    assert_string_equal(node->meta->name, META_NAME);
+    assert_string_equal(lyd_get_value(node), "1");
+    assert_string_equal(lyd_get_value(node->next), "2");
+    lyd_free_all(cont);
+
+    /* Remove all */
+    assert_int_equal(lyd_new_inner(NULL, mod, "cn", 0, &cont), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(cont, mod, "ll", "1", 0, NULL), LY_SUCCESS);
+    node = lyd_child(cont);
+    assert_non_null(node);
+    deleted = node;
+    lyd_unlink_tree(deleted);
+    lyd_free_tree(deleted);
+    node = lyd_child(cont);
+    assert_null(node);
+    lyd_free_all(cont);
+}
+
+static void
+test_remove_then_insert(void **state)
+{
+    const char *schema;
+    struct lys_module *mod;
+    struct lyd_node *cont, *node, *deleted;
+
+    schema = "module a {namespace urn:tests:a;prefix a;yang-version 1.1;revision 2014-05-08;"
+            "container cn { leaf-list ll {type uint32;}}}";
+    UTEST_ADD_MODULE(schema, LYS_IN_YANG, NULL, &mod);
+
+    /* remove first */
+    assert_int_equal(lyd_new_inner(NULL, mod, "cn", 0, &cont), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(cont, mod, "ll", "1", 0, NULL), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(cont, mod, "ll", "2", 0, NULL), LY_SUCCESS);
+    node = lyd_child(cont);
+    assert_true(node && node->next && node->meta);
+    assert_string_equal(node->meta->name, META_NAME);
+    deleted = node;
+    lyd_unlink_tree(deleted);
+    lyd_free_tree(deleted);
+    node = lyd_child(cont);
+    assert_non_null(node->meta);
+    assert_string_equal(node->meta->name, META_NAME);
+
+    /* insert last */
+    assert_int_equal(lyd_new_term(cont, mod, "ll", "3", 0, NULL), LY_SUCCESS);
+    node = lyd_child(cont);
+    assert_true(node && node->next && node->meta);
+    assert_string_equal(node->meta->name, META_NAME);
+    assert_string_equal(lyd_get_value(node), "2");
+    assert_string_equal(lyd_get_value(node->next), "3");
+
+    /* insert first */
+    assert_int_equal(lyd_new_term(cont, mod, "ll", "1", 0, NULL), LY_SUCCESS);
+    node = lyd_child(cont);
+    assert_true(node && node->next && node->next && node->meta);
+    assert_string_equal(node->meta->name, META_NAME);
+    assert_string_equal(lyd_get_value(node), "1");
+    assert_string_equal(lyd_get_value(node->next), "2");
+    assert_string_equal(lyd_get_value(node->next->next), "3");
+    lyd_free_all(cont);
+}
+
+static void
+test_unlink_all(void **state)
+{
+    const char *schema;
+    struct lys_module *mod;
+    struct lyd_node *first, *second;
+
+    schema = "module a {namespace urn:tests:a;prefix a;yang-version 1.1;revision 2014-05-08;"
+            "leaf-list ll {type uint32;}}";
+    UTEST_ADD_MODULE(schema, LYS_IN_YANG, NULL, &mod);
+
+    assert_int_equal(lyd_new_term(NULL, mod, "ll", "1", 0, &first), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(NULL, mod, "ll", "2", 0, &second), LY_SUCCESS);
+    assert_int_equal(lyd_insert_sibling(first, second, NULL), LY_SUCCESS);
+    lyds_unlink(&first, second);
+    assert_non_null(first->meta);
+    lyds_unlink(&first, first);
+    assert_true(!first->meta && !second->meta);
+    lyd_free_all(first);
+}
+
+static void
+test_insert_before_anchor(void **state)
+{
+    const char *schema;
+    struct lys_module *mod;
+    struct lyd_node *cont, *node;
+
+    schema = "module a {namespace urn:tests:a;prefix a;yang-version 1.1;revision 2014-05-08;"
+            "container cn {"
+            "  leaf-list llm {"
+            "    type string;"
+            "  }"
+            "  leaf-list lln {"
+            "    type string;"
+            "  }"
+            "}}";
+
+    UTEST_ADD_MODULE(schema, LYS_IN_YANG, NULL, &mod);
+    assert_int_equal(lyd_new_inner(NULL, mod, "cn", 0, &cont), LY_SUCCESS);
+
+    assert_int_equal(lyd_new_term(cont, mod, "lln", "1", 0, NULL), LY_SUCCESS);
+    node = lyd_child(cont);
+    assert_true(node && node->meta);
+    assert_string_equal(node->meta->name, META_NAME);
+    assert_string_equal(lyd_get_value(node), "1");
+
+    assert_int_equal(lyd_new_term(cont, mod, "llm", "2", 0, NULL), LY_SUCCESS);
+    node = lyd_child(cont);
+    assert_true(node && node->meta && node->next);
+    assert_string_equal(node->meta->name, META_NAME);
+    assert_string_equal(lyd_get_value(node), "2");
+    assert_string_equal(lyd_get_value(node->next), "1");
+
+    lyd_free_all(cont);
+}
+
+static void
+test_insert_after_anchor(void **state)
+{
+    const char *schema;
+    struct lys_module *mod;
+    struct lyd_node *cont, *node;
+
+    schema = "module a {namespace urn:tests:a;prefix a;yang-version 1.1;revision 2014-05-08;"
+            "container cn {"
+            "  leaf-list llm {"
+            "    type string;"
+            "  }"
+            "  leaf-list lln {"
+            "    type string;"
+            "  }"
+            "}}";
+
+    UTEST_ADD_MODULE(schema, LYS_IN_YANG, NULL, &mod);
+    assert_int_equal(lyd_new_inner(NULL, mod, "cn", 0, &cont), LY_SUCCESS);
+
+    assert_int_equal(lyd_new_term(cont, mod, "llm", "1", 0, NULL), LY_SUCCESS);
+    node = lyd_child(cont);
+    assert_true(node && node->meta);
+    assert_string_equal(node->meta->name, META_NAME);
+    assert_string_equal(lyd_get_value(node), "1");
+
+    assert_int_equal(lyd_new_term(cont, mod, "lln", "2", 0, NULL), LY_SUCCESS);
+    node = lyd_child(cont);
+    assert_true(node && node->meta && node->next);
+    assert_string_equal(node->meta->name, META_NAME);
+    assert_string_equal(lyd_get_value(node), "1");
+    assert_string_equal(lyd_get_value(node->next), "2");
+
+    lyd_free_all(cont);
+}
+
+static void
+test_insert_same_values_leaflist(void **state)
+{
+    const char *schema;
+    struct lys_module *mod;
+    struct lyd_node *cont, *n1, *n2;
+
+    schema = "module a {namespace urn:tests:a;prefix a;yang-version 1.1;revision 2014-05-08;"
+            "container cn { leaf-list ll {type uint32;}}}";
+    UTEST_ADD_MODULE(schema, LYS_IN_YANG, NULL, &mod);
+    assert_int_equal(lyd_new_inner(NULL, mod, "cn", 0, &cont), LY_SUCCESS);
+
+    assert_int_equal(lyd_new_term(cont, mod, "ll", "1", 0, NULL), LY_SUCCESS);
+    n1 = lyd_child(cont);
+    assert_true(n1 && n1->meta);
+    assert_string_equal(n1->meta->name, META_NAME);
+    assert_string_equal(lyd_get_value(n1), "1");
+
+    assert_int_equal(lyd_new_term(cont, mod, "ll", "1", 0, NULL), LY_SUCCESS);
+    n2 = lyd_child(cont);
+    assert_true(n2 && n2->meta && n2->next);
+    assert_string_equal(n2->meta->name, META_NAME);
+    assert_string_equal(lyd_get_value(n2), "1");
+    assert_string_equal(lyd_get_value(n2->next), "1");
+
+    assert_ptr_equal(n1, n2);
+    lyd_free_all(cont);
+}
+
+static void
+test_insert_same_values_list(void **state)
+{
+    const char *schema;
+    struct lys_module *mod;
+    struct lyd_node *cont, *n1, *n2;
+
+    schema = "module a {namespace urn:tests:a;prefix a;yang-version 1.1;revision 2014-05-08;"
+            "container cn { list lst {key \"k\"; leaf k {type uint32;}}}}";
+    UTEST_ADD_MODULE(schema, LYS_IN_YANG, NULL, &mod);
+
+    assert_int_equal(lyd_new_inner(NULL, mod, "cn", 0, &cont), LY_SUCCESS);
+
+    assert_int_equal(lyd_new_list(cont, mod, "lst", 0, NULL, "1"), LY_SUCCESS);
+    n1 = lyd_child(cont);
+    assert_true(n1 && n1->meta);
+    assert_string_equal(n1->meta->name, META_NAME);
+    assert_string_equal(lyd_get_value(lyd_child(n1)), "1");
+
+    assert_int_equal(lyd_new_list(cont, mod, "lst", 0, NULL, "1"), LY_SUCCESS);
+    n2 = lyd_child(cont);
+    assert_true(n2 && n2->meta);
+    assert_string_equal(n2->meta->name, META_NAME);
+    assert_string_equal(lyd_get_value(lyd_child(n2)), "1");
+    assert_string_equal(lyd_get_value(lyd_child(n2->next)), "1");
+
+    assert_ptr_equal(n1, n2);
+    lyd_free_all(cont);
+}
+
+static void
+test_remove_same_values_leaflist(void **state)
+{
+    const char *schema;
+    struct lys_module *mod;
+    struct lyd_node *cont, *n1, *n2, *n3, *n4, *n5, *child;
+
+    schema = "module a {namespace urn:tests:a;prefix a;yang-version 1.1;revision 2014-05-08;"
+            "container cn { leaf-list ll {type uint32;}}}";
+    UTEST_ADD_MODULE(schema, LYS_IN_YANG, NULL, &mod);
+    assert_int_equal(lyd_new_inner(NULL, mod, "cn", 0, &cont), LY_SUCCESS);
+
+    assert_int_equal(lyd_new_term(cont, mod, "ll", "1", 0, &n1), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(cont, mod, "ll", "1", 0, &n2), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(cont, mod, "ll", "1", 0, &n3), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(cont, mod, "ll", "1", 0, &n4), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(cont, mod, "ll", "1", 0, &n5), LY_SUCCESS);
+
+    /* remove second node */
+    lyd_free_tree(n2);
+    child = lyd_child(cont);
+    assert_true((child == n1) && (child->next == n3) && (child->next->next == n4) && (child->next->next->next == n5));
+
+    /* remove first node */
+    lyd_free_tree(n1);
+    child = lyd_child(cont);
+    assert_true((child == n3) && (child->next == n4) && (child->next->next == n5));
+
+    /* remove fifth node */
+    lyd_free_tree(n5);
+    child = lyd_child(cont);
+    assert_true((child == n3) && (child->next == n4));
+
+    /* remove fourth node */
+    lyd_free_tree(n4);
+    child = lyd_child(cont);
+    assert_true(child == n3);
+
+    lyd_free_all(cont);
+}
+
+static void
+test_insert_keyless_list(void **state)
+{
+    const char *schema;
+    struct lys_module *mod;
+    struct lyd_node *cont, *lst, *node;
+
+    schema = "module a {namespace urn:tests:a;prefix a;yang-version 1.1;revision 2014-05-08;"
+            "container cn { list lst {config false; leaf lf {type uint32;}}}}";
+    UTEST_ADD_MODULE(schema, LYS_IN_YANG, NULL, &mod);
+
+    /* lyds tree is not used for keyless list */
+    assert_int_equal(lyd_new_inner(NULL, mod, "cn", 0, &cont), LY_SUCCESS);
+    assert_int_equal(lyd_new_list(cont, mod, "lst", 0, &lst), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(lst, mod, "lf", "2", 0, NULL), LY_SUCCESS);
+    assert_int_equal(lyd_new_list(cont, mod, "lst", 0, &lst), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(lst, mod, "lf", "1", 0, NULL), LY_SUCCESS);
+    node = lyd_child(cont);
+    assert_true(node && !node->meta && node->next);
+    assert_string_equal(lyd_get_value(lyd_child(node)), "2");
+    assert_string_equal(lyd_get_value(lyd_child(node->next)), "1");
+    lyd_free_all(cont);
+}
+
+static void
+test_leaflist_default(void **state)
+{
+    const char *schema;
+    struct lys_module *mod;
+    struct lyd_node *cont, *node;
+
+    schema = "module a {namespace urn:tests:a;prefix a;yang-version 1.1;revision 2014-05-08;"
+            "container cn { leaf-list ll {default \"1\"; type uint32;}}}";
+    UTEST_ADD_MODULE(schema, LYS_IN_YANG, NULL, &mod);
+    assert_int_equal(lyd_new_inner(NULL, mod, "cn", 0, &cont), LY_SUCCESS);
+
+    assert_int_equal(lyd_new_term(cont, mod, "ll", "2", 0, NULL), LY_SUCCESS);
+    node = lyd_child(cont);
+    assert_true(node && node->meta);
+    assert_string_equal(node->meta->name, META_NAME);
+    assert_string_equal(lyd_get_value(node), "2");
+    assert_int_equal(lyd_new_term(cont, mod, "ll", "1", 0, NULL), LY_SUCCESS);
+    node = lyd_child(cont);
+    assert_true(node && node->next && node->meta);
+    assert_string_equal(node->meta->name, META_NAME);
+    assert_string_equal(lyd_get_value(node), "1");
+    lyd_free_all(cont);
+}
+
+static void
+test_unlink_then_insert(void **state)
+{
+    const char *schema;
+    struct lys_module *mod;
+    struct lyd_node *cont, *first, *second, *third;
+
+    schema = "module a {namespace urn:tests:a;prefix a;yang-version 1.1;revision 2014-05-08;"
+            "container cn { leaf-list ll {type uint32;}}}";
+    UTEST_ADD_MODULE(schema, LYS_IN_YANG, NULL, &mod);
+
+    /* unlink first and second */
+    assert_int_equal(lyd_new_inner(NULL, mod, "cn", 0, &cont), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(cont, mod, "ll", "2", 0, NULL), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(cont, mod, "ll", "1", 0, NULL), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(cont, mod, "ll", "3", 0, NULL), LY_SUCCESS);
+    first = lyd_child(cont);
+    lyd_unlink_tree(first);
+    second = lyd_child(cont);
+    lyd_unlink_tree(second);
+    third = lyd_child(cont);
+    assert_true(third && third->meta && !first->meta && !second->meta);
+    assert_string_equal(third->meta->name, META_NAME);
+
+    /* insert first */
+    lyd_insert_child(cont, first);
+    assert_true(first && first->meta && !third->meta);
+    assert_string_equal(first->meta->name, META_NAME);
+
+    /* insert second */
+    lyd_insert_child(cont, second);
+    assert_true(first && first->meta && !second->meta && !third->meta);
+    assert_string_equal(first->meta->name, META_NAME);
+
+    /* check the order */
+    assert_ptr_equal(lyd_child(cont), first);
+    first = lyd_child(cont);
+    assert_string_equal(lyd_get_value(first), "1");
+    assert_string_equal(lyd_get_value(first->next), "2");
+    assert_string_equal(lyd_get_value(first->next->next), "3");
+
+    /* unlink all nodes */
+    lyd_unlink_tree(lyd_child(cont));
+    lyd_unlink_tree(lyd_child(cont));
+    lyd_unlink_tree(lyd_child(cont));
+    assert_null(lyd_child(cont));
+    assert_true(!first->meta && !second->meta && !third->meta);
+
+    /* insert first */
+    lyd_insert_child(cont, first);
+    assert_non_null(first->meta);
+    assert_string_equal(first->meta->name, META_NAME);
+
+    lyd_free_all(cont);
+    lyd_free_all(second);
+    lyd_free_all(third);
+}
+
+static void
+test_change_term(void **state)
+{
+    const char *schema;
+    struct lys_module *mod;
+    struct lyd_node *cont, *first, *node;
+
+    schema = "module a {namespace urn:tests:a;prefix a;yang-version 1.1;revision 2014-05-08;"
+            "container cn { leaf-list ll {type uint32;}}}";
+    UTEST_ADD_MODULE(schema, LYS_IN_YANG, NULL, &mod);
+
+    assert_int_equal(lyd_new_inner(NULL, mod, "cn", 0, &cont), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(cont, mod, "ll", "1", 0, NULL), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(cont, mod, "ll", "2", 0, NULL), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(cont, mod, "ll", "3", 0, NULL), LY_SUCCESS);
+    first = lyd_child(cont);
+
+    /* change node which has no meta */
+    node = lyd_child(cont)->next;
+    assert_int_equal(lyd_change_term(node, "5"), LY_SUCCESS);
+    assert_string_equal(lyd_get_value(node), "5");
+    assert_true(first && first->meta && first->next && first->next->next);
+    assert_string_equal(lyd_get_value(first), "1");
+    assert_string_equal(lyd_get_value(first->next), "3");
+    assert_string_equal(lyd_get_value(first->next->next), "5");
+
+    /* change node which has meta */
+    assert_int_equal(lyd_change_term(first, "6"), LY_SUCCESS);
+    assert_string_equal(lyd_get_value(first), "6");
+    first = lyd_child(cont);
+    assert_true(first && first->meta && first->next && first->next->next);
+    assert_string_equal(lyd_get_value(first), "3");
+    assert_string_equal(lyd_get_value(first->next), "5");
+    assert_string_equal(lyd_get_value(first->next->next), "6");
+
+    lyd_free_all(cont);
+}
+
+static void
+test_change_key(void **state)
+{
+    const char *schema;
+    struct lys_module *mod;
+    struct lyd_node *cont, *first, *node;
+
+    schema = "module a {namespace urn:tests:a;prefix a;yang-version 1.1;revision 2014-05-08;"
+            "container cn { list lst {key \"k\"; leaf k {type uint32;}}}}";
+    UTEST_ADD_MODULE(schema, LYS_IN_YANG, NULL, &mod);
+
+    assert_int_equal(lyd_new_inner(NULL, mod, "cn", 0, &cont), LY_SUCCESS);
+    assert_int_equal(lyd_new_list(cont, mod, "lst", 0, NULL, "1"), LY_SUCCESS);
+    assert_int_equal(lyd_new_list(cont, mod, "lst", 0, NULL, "2"), LY_SUCCESS);
+    assert_int_equal(lyd_new_list(cont, mod, "lst", 0, NULL, "3"), LY_SUCCESS);
+    first = lyd_child(cont);
+
+    /* change node which has no meta */
+    node = lyd_child(cont)->next;
+    assert_int_equal(lyd_change_term(lyd_child(node), "5"), LY_SUCCESS);
+    assert_string_equal(lyd_get_value(lyd_child(node)), "5");
+    assert_true(first && first->meta && first->next && first->next->next);
+    assert_string_equal(lyd_get_value(lyd_child(first)), "1");
+    assert_string_equal(lyd_get_value(lyd_child(first->next)), "3");
+    assert_string_equal(lyd_get_value(lyd_child(first->next->next)), "5");
+
+    /* change node which has meta */
+    assert_int_equal(lyd_change_term(lyd_child(first), "6"), LY_SUCCESS);
+    assert_string_equal(lyd_get_value(lyd_child(first)), "6");
+    first = lyd_child(cont);
+    assert_true(first && first->meta && first->next && first->next->next);
+    assert_string_equal(lyd_get_value(lyd_child(first)), "3");
+    assert_string_equal(lyd_get_value(lyd_child(first->next)), "5");
+    assert_string_equal(lyd_get_value(lyd_child(first->next->next)), "6");
+
+    lyd_free_all(cont);
+}
+
+static void
+test_lyd_dup_meta(void **state)
+{
+    const char *schema;
+    struct lys_module *mod, *mod2;
+    struct lyd_node *node, *sibl, *par, *par2;
+    struct lyd_meta *meta, *meta2;
+    struct ly_ctx *ctx2;
+
+    schema = "module a {namespace urn:tests:a;prefix a;yang-version 1.1;revision 2014-05-08;"
+            "leaf-list ll {type uint32;}}";
+    UTEST_ADD_MODULE(schema, LYS_IN_YANG, NULL, &mod);
+
+    /* metadata duplication in the same context */
+    assert_int_equal(lyd_new_term(NULL, mod, "ll", "1", 0, &node), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(NULL, mod, "ll", "2", 0, &sibl), LY_SUCCESS);
+    assert_int_equal(lyd_insert_sibling(sibl, node, NULL), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(NULL, mod, "ll", "3", 0, &par), LY_SUCCESS);
+    assert_int_equal(lyd_dup_meta_single(node->meta, par, &meta), LY_SUCCESS);
+    assert_non_null(node->meta);
+    assert_string_equal(node->meta->name, META_NAME);
+    assert_ptr_equal(meta->annotation, node->meta->annotation);
+    assert_true(get_rbt(node->meta) && !get_rbt(meta));
+    lyd_free_meta_single(meta);
+    lyd_free_all(par);
+
+    /* metadata duplication where parameters are from different contexts */
+    assert_int_equal(ly_ctx_new(NULL, 0, &ctx2), LY_SUCCESS);
+    assert_int_equal(ly_in_new_memory(schema, &UTEST_IN), LY_SUCCESS);
+    assert_int_equal(lys_parse(ctx2, UTEST_IN, LYS_IN_YANG, NULL, &mod2), LY_SUCCESS);
+    ly_in_free(UTEST_IN, 0), UTEST_IN = NULL;
+    assert_int_equal(lyd_new_term(NULL, mod2, "ll", "1", 0, &par2), LY_SUCCESS);
+    assert_int_equal(lyd_dup_meta_single_to_ctx(ctx2, node->meta, par2, &meta2), LY_SUCCESS);
+    assert_ptr_not_equal(node->meta->annotation, meta2->annotation);
+    assert_null(get_rbt(meta2));
+    lyd_free_all(par2);
+    ly_ctx_destroy(ctx2);
+
+    lyd_free_all(node);
+}
+
+static void
+test_insert_into_duplicate(void **state)
+{
+    const char *schema;
+    struct lys_module *mod;
+    struct lyd_node *cont, *node, *dup;
+
+    schema = "module a {namespace urn:tests:a;prefix a;yang-version 1.1;revision 2014-05-08;"
+            "container cn { leaf-list ll {type uint32;}}}";
+    UTEST_ADD_MODULE(schema, LYS_IN_YANG, NULL, &mod);
+
+    assert_int_equal(lyd_new_inner(NULL, mod, "cn", 0, &cont), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(cont, mod, "ll", "3", 0, NULL), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(cont, mod, "ll", "1", 0, NULL), LY_SUCCESS);
+    /* create duplicate */
+    assert_int_equal(lyd_dup_single(cont, NULL, LYD_DUP_RECURSIVE, &dup), LY_SUCCESS);
+    node = lyd_child(dup);
+    assert_true(node && node->next && get_rbt(node->meta));
+    assert_string_equal(node->meta->name, META_NAME);
+    assert_ptr_not_equal(get_rbt(node->meta), get_rbt(lyd_child(cont)->meta));
+    /* insert into duplicate */
+    assert_int_equal(lyd_new_term(dup, mod, "ll", "2", 0, NULL), LY_SUCCESS);
+    assert_non_null(node->next->next);
+    assert_string_equal(lyd_get_value(node), "1");
+    assert_string_equal(lyd_get_value(node->next), "2");
+    assert_string_equal(lyd_get_value(node->next->next), "3");
+    lyd_free_all(cont);
+    lyd_free_all(dup);
+}
+
+static void
+test_option_dup_no_meta(void **state)
+{
+    const char *schema;
+    struct lys_module *mod;
+    struct lyd_node *cont, *dup, *node;
+
+    schema = "module a {namespace urn:tests:a;prefix a;yang-version 1.1;revision 2014-05-08;"
+            "container cn { leaf-list ll {type uint32;}}}";
+    UTEST_ADD_MODULE(schema, LYS_IN_YANG, NULL, &mod);
+
+    assert_int_equal(lyd_new_inner(NULL, mod, "cn", 0, &cont), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(cont, mod, "ll", "2", 0, NULL), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(cont, mod, "ll", "3", 0, NULL), LY_SUCCESS);
+    assert_int_equal(lyd_dup_siblings(cont, NULL, LYD_DUP_NO_META | LYD_DUP_RECURSIVE, &dup), LY_SUCCESS);
+    node = lyd_child(dup);
+    assert_true(node && get_rbt(node->meta));
+    assert_string_equal(node->meta->name, META_NAME);
+    assert_int_equal(lyd_new_term(dup, mod, "ll", "1", 0, NULL), LY_SUCCESS);
+    node = lyd_child(dup);
+    assert_string_equal(lyd_get_value(node), "1");
+
+    lyd_free_all(cont);
+    lyd_free_all(dup);
+}
+
+static void
+test_no_metadata_remains(void **state)
+{
+    const char *schema;
+    struct lys_module *mod;
+    struct lyd_node *f1, *node, *f2, *dup;
+
+    schema = "module a {namespace urn:tests:a;prefix a;yang-version 1.1;revision 2014-05-08;"
+            "leaf-list ll {type uint32;}}";
+    UTEST_ADD_MODULE(schema, LYS_IN_YANG, NULL, &mod);
+
+    /* setup */
+    /* create one node with metadata which contains the lyds tree */
+    assert_int_equal(lyd_new_term(NULL, mod, "ll", "1", 0, &f1), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(NULL, mod, "ll", "2", 0, &node), LY_SUCCESS);
+    assert_int_equal(lyd_insert_sibling(f1, node, NULL), LY_SUCCESS);
+    lyd_unlink_tree(node);
+    lyd_free_all(node);
+    assert_non_null(get_rbt(f1->meta));
+    assert_string_equal(f1->meta->name, META_NAME);
+    /* do it again with another data tree */
+    assert_int_equal(lyd_new_term(NULL, mod, "ll", "3", 0, &f2), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(NULL, mod, "ll", "4", 0, &node), LY_SUCCESS);
+    assert_int_equal(lyd_insert_sibling(f2, node, NULL), LY_SUCCESS);
+    lyd_unlink_tree(node);
+    lyd_free_all(node);
+    assert_non_null(get_rbt(f2->meta));
+    assert_string_equal(f2->meta->name, META_NAME);
+    /* also create a duplicate */
+    lyd_dup_single(f2, NULL, 0, &dup);
+    assert_true(dup->meta && !get_rbt(dup->meta));
+    assert_string_equal(dup->meta->name, META_NAME);
+
+    /* test: insert node which also has metadata */
+    assert_int_equal(lyd_insert_sibling(f1, f2, NULL), LY_SUCCESS);
+    /* inserted node no longer has metadata */
+    assert_true(f1->next && !f1->next->meta);
+    lyd_unlink_tree(f2);
+    lyd_free_all(f2);
+
+    /* test: insert duplicate node which also has metadata but no lyds_tree */
+    assert_int_equal(lyd_insert_sibling(f1, dup, NULL), LY_SUCCESS);
+    /* inserted node no longer has metadata */
+    assert_true(f1->next && !f1->next->meta);
+    lyd_unlink_tree(dup);
+    lyd_free_all(dup);
+
+    /* teardown */
+    lyd_free_all(f1);
+}
+
+static void
+test_insert_multiple_keys(void **state)
+{
+    const char *schema;
+    struct lys_module *mod;
+    struct lyd_node *cont, *node, *key;
+
+    schema = "module a {namespace urn:tests:a;prefix a;yang-version 1.1;revision 2014-05-08;"
+            "container cn { list lst {key \"k1 k2 k3\";"
+            "leaf k1 {type uint32;} leaf k2 {type uint32;} leaf k3 {type uint32;}}}}";
+    UTEST_ADD_MODULE(schema, LYS_IN_YANG, NULL, &mod);
+
+    assert_int_equal(lyd_new_inner(NULL, mod, "cn", 0, &cont), LY_SUCCESS);
+    assert_int_equal(lyd_new_list(cont, mod, "lst", 0, NULL, "2", "0", "0"), LY_SUCCESS);
+    assert_int_equal(lyd_new_list(cont, mod, "lst", 0, NULL, "1", "5", "0"), LY_SUCCESS);
+    assert_int_equal(lyd_new_list(cont, mod, "lst", 0, NULL, "1", "5", "1"), LY_SUCCESS);
+    assert_int_equal(lyd_new_list(cont, mod, "lst", 0, NULL, "1", "6", "0"), LY_SUCCESS);
+    node = lyd_child(cont);
+    assert_true(node && node->meta && node->next && node->next->next && node->next->next->next);
+    assert_string_equal(node->meta->name, META_NAME);
+    key = lyd_child(node);
+    assert_string_equal(lyd_get_value(key), "1");
+    assert_string_equal(lyd_get_value(key->next), "5");
+    assert_string_equal(lyd_get_value(key->next->next), "0");
+    key = lyd_child(node->next);
+    assert_string_equal(lyd_get_value(key), "1");
+    assert_string_equal(lyd_get_value(key->next), "5");
+    assert_string_equal(lyd_get_value(key->next->next), "1");
+    key = lyd_child(node->next->next);
+    assert_string_equal(lyd_get_value(key), "1");
+    assert_string_equal(lyd_get_value(key->next), "6");
+    assert_string_equal(lyd_get_value(key->next->next), "0");
+    key = lyd_child(node->next->next->next);
+    assert_string_equal(lyd_get_value(key), "2");
+    assert_string_equal(lyd_get_value(key->next), "0");
+    assert_string_equal(lyd_get_value(key->next->next), "0");
+    lyd_free_all(cont);
+}
+
+static void
+test_merge_siblings(void **state)
+{
+    const char *schema;
+    struct lys_module *mod;
+    struct lyd_node *f1, *f2, *s1, *s2;
+
+    schema = "module a {namespace urn:tests:a;prefix a;yang-version 1.1;revision 2014-05-08;"
+            "leaf-list ll {type uint32;}}";
+    UTEST_ADD_MODULE(schema, LYS_IN_YANG, NULL, &mod);
+
+    /* both source and target trees have metadata */
+    assert_int_equal(lyd_new_term(NULL, mod, "ll", "1", 0, &f1), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(NULL, mod, "ll", "2", 0, &s1), LY_SUCCESS);
+    assert_int_equal(lyd_insert_sibling(f1, s1, NULL), LY_SUCCESS);
+    assert_non_null(f1->meta);
+    assert_int_equal(lyd_new_term(NULL, mod, "ll", "21", 0, &f2), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(NULL, mod, "ll", "22", 0, &s2), LY_SUCCESS);
+    assert_int_equal(lyd_insert_sibling(f2, s2, NULL), LY_SUCCESS);
+    assert_non_null(f2->meta);
+    assert_int_equal(lyd_merge_siblings(&f2, f1, 0), LY_SUCCESS);
+    assert_true(f2->meta && f2->next && f2->next->next && f2->next->next->next);
+    assert_string_equal(f2->meta->name, META_NAME);
+    assert_string_equal(lyd_get_value(f2), "1");
+    assert_string_equal(lyd_get_value(f2->next), "2");
+    assert_string_equal(lyd_get_value(f2->next->next), "21");
+    assert_string_equal(lyd_get_value(f2->next->next->next), "22");
+    lyd_free_all(f1);
+    lyd_free_all(f2);
+
+    /* both source and target trees have metadata and LYD_MERGE_DESTRUCT flag is set */
+    assert_int_equal(lyd_new_term(NULL, mod, "ll", "1", 0, &f1), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(NULL, mod, "ll", "2", 0, &s1), LY_SUCCESS);
+    assert_int_equal(lyd_insert_sibling(f1, s1, NULL), LY_SUCCESS);
+    assert_non_null(f1->meta);
+    assert_int_equal(lyd_new_term(NULL, mod, "ll", "21", 0, &f2), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(NULL, mod, "ll", "22", 0, &s2), LY_SUCCESS);
+    assert_int_equal(lyd_insert_sibling(f2, s2, NULL), LY_SUCCESS);
+    assert_non_null(f2->meta);
+    assert_int_equal(lyd_merge_siblings(&f2, f1, LYD_MERGE_DESTRUCT), LY_SUCCESS);
+    assert_true(f2->meta && f2->next && f2->next->next && f2->next->next->next);
+    assert_true(get_rbt(f2->meta) && !f2->next->meta && !f2->next->next->meta && !f2->next->next->next->meta);
+    assert_string_equal(f2->meta->name, META_NAME);
+    assert_string_equal(lyd_get_value(f2), "1");
+    assert_string_equal(lyd_get_value(f2->next), "2");
+    assert_string_equal(lyd_get_value(f2->next->next), "21");
+    assert_string_equal(lyd_get_value(f2->next->next->next), "22");
+    lyd_free_all(f2);
+
+    /* only source tree have metadata */
+    assert_int_equal(lyd_new_term(NULL, mod, "ll", "1", 0, &f1), LY_SUCCESS);
+    assert_null(f1->meta);
+    assert_int_equal(lyd_new_term(NULL, mod, "ll", "21", 0, &f2), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(NULL, mod, "ll", "22", 0, &s2), LY_SUCCESS);
+    assert_int_equal(lyd_insert_sibling(f2, s2, NULL), LY_SUCCESS);
+    assert_non_null(f2->meta);
+    assert_int_equal(lyd_merge_siblings(&f2, f1, 0), LY_SUCCESS);
+    assert_true(f2->meta && f2->next && f2->next->next);
+    assert_string_equal(f2->meta->name, META_NAME);
+    assert_string_equal(lyd_get_value(f2), "1");
+    assert_string_equal(lyd_get_value(f2->next), "21");
+    assert_string_equal(lyd_get_value(f2->next->next), "22");
+    lyd_free_all(f1);
+    lyd_free_all(f2);
+
+    /* only target tree have metadata */
+    assert_int_equal(lyd_new_term(NULL, mod, "ll", "1", 0, &f1), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(NULL, mod, "ll", "2", 0, &s1), LY_SUCCESS);
+    assert_int_equal(lyd_insert_sibling(f1, s1, NULL), LY_SUCCESS);
+    assert_non_null(f1->meta);
+    assert_int_equal(lyd_new_term(NULL, mod, "ll", "21", 0, &f2), LY_SUCCESS);
+    assert_null(f2->meta);
+    assert_int_equal(lyd_merge_siblings(&f2, f1, 0), LY_SUCCESS);
+    assert_true(f2->meta && f2->next && f2->next->next);
+    assert_string_equal(f2->meta->name, META_NAME);
+    assert_string_equal(lyd_get_value(f2), "1");
+    assert_string_equal(lyd_get_value(f2->next), "2");
+    assert_string_equal(lyd_get_value(f2->next->next), "21");
+    lyd_free_all(f1);
+    lyd_free_all(f2);
+
+    /* none have metadata */
+    assert_int_equal(lyd_new_term(NULL, mod, "ll", "1", 0, &f1), LY_SUCCESS);
+    assert_null(f1->meta);
+    assert_int_equal(lyd_new_term(NULL, mod, "ll", "21", 0, &f2), LY_SUCCESS);
+    assert_null(f2->meta);
+    assert_int_equal(lyd_merge_siblings(&f2, f1, 0), LY_SUCCESS);
+    assert_true(f2->meta && f2->next);
+    assert_string_equal(f2->meta->name, META_NAME);
+    assert_string_equal(lyd_get_value(f2), "1");
+    assert_string_equal(lyd_get_value(f2->next), "21");
+    lyd_free_all(f1);
+    lyd_free_all(f2);
+}
+
+static void
+test_parse_data(void **state)
+{
+    const char *schema, *data;
+    char *lyb_out;
+    struct lys_module *mod;
+    struct lyd_node *tree, *tree2;
+
+    schema = "module a {namespace urn:tests:a;prefix a;yang-version 1.1;revision 2014-05-08;"
+            "leaf-list ll {type uint32;}}";
+    UTEST_ADD_MODULE(schema, LYS_IN_YANG, NULL, &mod);
+
+    /* json */
+    data = "{\"a:ll\":[2,1]}";
+    CHECK_PARSE_LYD_PARAM(data, LYD_JSON, 0, LYD_VALIDATE_PRESENT, LY_SUCCESS, tree);
+    assert_true(tree && tree->meta && tree->next);
+    assert_string_equal(tree->meta->name, META_NAME);
+    CHECK_LYD_VALUE(((struct lyd_node_term *)tree)->value, UINT32, "1", 1);
+    lyd_free_all(tree);
+
+    /* xml */
+    data = "<ll xmlns=\"urn:tests:a\">2</ll>"
+            "<ll xmlns=\"urn:tests:a\">1</ll>";
+    CHECK_PARSE_LYD_PARAM(data, LYD_XML, 0, LYD_VALIDATE_PRESENT, LY_SUCCESS, tree);
+    assert_true(tree && tree->meta && tree->next);
+    assert_string_equal(tree->meta->name, META_NAME);
+    CHECK_LYD_VALUE(((struct lyd_node_term *)tree)->value, UINT32, "1", 1);
+    /* data tree is used in the next check */
+
+    /* lyb */
+    assert_int_equal(lyd_print_mem(&lyb_out, tree, LYD_LYB, LYD_PRINT_WITHSIBLINGS), 0);
+    assert_int_equal(lyd_parse_data_mem(UTEST_LYCTX, lyb_out, LYD_LYB, LYD_PARSE_ONLY | LYD_PARSE_STRICT,
+            0, &tree2), LY_SUCCESS);
+    assert_true(tree2 && tree2->meta && tree2->next);
+    assert_string_equal(tree2->meta->name, META_NAME);
+    CHECK_LYD_VALUE(((struct lyd_node_term *)tree2)->value, UINT32, "1", 1);
+    free(lyb_out);
+    lyd_free_all(tree2);
+    lyd_free_all(tree);
+}
+
+static void
+test_print_data(void **state)
+{
+    const char *schema, *exp;
+    char *out;
+    struct lys_module *mod;
+    struct lyd_node *first, *node;
+
+    schema = "module a {namespace urn:tests:a;prefix a;yang-version 1.1;revision 2014-05-08;"
+            "leaf-list ll {type uint32;}}";
+    UTEST_ADD_MODULE(schema, LYS_IN_YANG, NULL, &mod);
+
+    /* lyds metadata must not be printed */
+
+    /* json */
+    assert_int_equal(lyd_new_term(NULL, mod, "ll", "2", 0, &first), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(NULL, mod, "ll", "1", 0, &node), LY_SUCCESS);
+    assert_int_equal(lyd_insert_sibling(first, node, NULL), LY_SUCCESS);
+    assert_int_equal(lyd_print_mem(&out, node, LYD_JSON, LYD_PRINT_WITHSIBLINGS | LYD_PRINT_SHRINK), 0);
+    exp = "{\"a:ll\":[1,2]}";
+    assert_string_equal(out, exp);
+    free(out);
+
+    /* xml */
+    assert_int_equal(lyd_print_mem(&out, node, LYD_XML, LYD_PRINT_WITHSIBLINGS | LYD_PRINT_SHRINK), 0);
+    exp = "<ll xmlns=\"urn:tests:a\">1</ll><ll xmlns=\"urn:tests:a\">2</ll>";
+    assert_string_equal(out, exp);
+    free(out);
+
+    lyd_free_all(first);
+}
+
+static void
+test_manipulation_of_many_nodes(void **state)
+{
+    const char *schema;
+    struct lys_module *mod;
+    struct lyd_node *cont, *iter, *prev, *node;
+    uint32_t i;
+    char *data[] = {
+        "q", "q", "n", "h", "c", "b", "h", "n", "p", "t",
+        "p", "j", "c", "h", "n", "k", "n", "q", "p", "p",
+        "s", "l", "p", "x", "h", "e", "i", "f", "u", "z",
+        "l", "n", "o", "k", "n", "t", "w", "o", "d", "b",
+        "k", "w", "w", "q", "e", "b", "x", "a", "g", "w",
+        "b", "e", "p", "r", "s", "w", "u", "w", "d", "r",
+    };
+    uint32_t data_len = sizeof(data) / sizeof(data[0]);
+
+    schema = "module a {namespace urn:tests:a;prefix a;yang-version 1.1;revision 2014-05-08;"
+            "container cn { leaf-list ll {type string;}}}";
+    UTEST_ADD_MODULE(schema, LYS_IN_YANG, NULL, &mod);
+
+    assert_int_equal(lyd_new_inner(NULL, mod, "cn", 0, &cont), LY_SUCCESS);
+
+    /* insert nodes */
+    for (i = 0; i < data_len; i++) {
+        assert_int_equal(lyd_new_term(cont, mod, "ll", data[i], 0, NULL), LY_SUCCESS);
+    }
+
+    /* sort check */
+    prev = lyd_child(cont);
+    LY_LIST_FOR(prev->next, iter) {
+        assert_true(lyd_get_value(prev)[0] <= lyd_get_value(iter)[0]);
+        prev = iter;
+    }
+
+    /* remove every even node */
+    LY_LIST_FOR(lyd_child(cont), iter) {
+        node = iter->next;
+        lyd_unlink_tree(node);
+        lyd_free_tree(node);
+    }
+    data_len /= 2;
+
+    /* sort check */
+    prev = lyd_child(cont);
+    i = 1;
+    LY_LIST_FOR(prev->next, iter) {
+        assert_true(lyd_get_value(prev)[0] <= lyd_get_value(iter)[0]);
+        prev = iter;
+        i++;
+    }
+    assert_int_equal(i, data_len);
+
+    lyd_free_all(cont);
+}
+
+static void
+test_lyds_free_metadata(void **state)
+{
+    const char *schema;
+    struct lys_module *mod;
+    struct lyd_node *first, *node;
+
+    schema = "module a {namespace urn:tests:a;prefix a;yang-version 1.1;revision 2014-05-08;"
+            "leaf-list ll {type uint32;}}";
+    UTEST_ADD_MODULE(schema, LYS_IN_YANG, NULL, &mod);
+
+    assert_int_equal(lyd_new_term(NULL, mod, "ll", "1", 0, &first), LY_SUCCESS);
+    assert_int_equal(lyd_new_term(NULL, mod, "ll", "2", 0, &node), LY_SUCCESS);
+    assert_int_equal(lyd_insert_sibling(first, node, NULL), LY_SUCCESS);
+    lyds_free_metadata(first);
+    assert_null(first->meta);
+    assert_null(node->meta);
+
+    lyd_free_all(first);
+}
+
+int
+main(void)
+{
+    const struct CMUnitTest tests[] = {
+        UTEST(test_insert_top_level_list),
+        UTEST(test_insert_top_level_leaflist),
+        UTEST(test_insert_cont_list),
+        UTEST(test_insert_cont_leaflist),
+        UTEST(test_try_user_order_func),
+        UTEST(test_ordered_by_user),
+        UTEST(test_remove),
+        UTEST(test_remove_then_insert),
+        UTEST(test_unlink_all),
+        UTEST(test_insert_before_anchor),
+        UTEST(test_insert_after_anchor),
+        UTEST(test_insert_same_values_leaflist),
+        UTEST(test_insert_same_values_list),
+        UTEST(test_remove_same_values_leaflist),
+        UTEST(test_insert_keyless_list),
+        UTEST(test_leaflist_default),
+        UTEST(test_unlink_then_insert),
+        UTEST(test_change_term),
+        UTEST(test_change_key),
+        UTEST(test_lyd_dup_meta),
+        UTEST(test_insert_into_duplicate),
+        UTEST(test_option_dup_no_meta),
+        UTEST(test_no_metadata_remains),
+        UTEST(test_insert_multiple_keys),
+        UTEST(test_merge_siblings),
+        UTEST(test_parse_data),
+        UTEST(test_print_data),
+        UTEST(test_manipulation_of_many_nodes),
+        UTEST(test_lyds_free_metadata),
+    };
+
+    return cmocka_run_group_tests(tests, NULL, NULL);
+}
diff --git a/tests/utests/node/list.c b/tests/utests/node/list.c
index 0f172d2..4a69dbb 100644
--- a/tests/utests/node/list.c
+++ b/tests/utests/node/list.c
@@ -775,7 +775,7 @@
     /* check first item */
     CHECK_PARSE_LYD_PARAM(data, LYD_XML, 0, LYD_VALIDATE_PRESENT, LY_SUCCESS, tree);
     list_tree = (void *)tree;
-    CHECK_LYD_NODE_INNER(list_tree, 1, 0, 0, 0, 1, 0, 0, 1);
+    CHECK_LYD_NODE_INNER(list_tree, 1, 0, 1, 0, 1, 0, 0, 1);
     list_leaf = (void *) list_tree->child;
     assert_string_equal(list_leaf->schema->name, "uid");
     CHECK_LYD_NODE_TERM(list_leaf, 0, 0, 1, 1, 1, UINT32, "0", 0);
@@ -814,7 +814,7 @@
     /* check first item */
     CHECK_PARSE_LYD_PARAM(data, LYD_XML, 0, LYD_VALIDATE_PRESENT, LY_SUCCESS, tree);
     list_tree = (void *)tree;
-    CHECK_LYD_NODE_INNER(list_tree, 1, 0, 0, 0, 1, 0, 0, 1);
+    CHECK_LYD_NODE_INNER(list_tree, 1, 0, 1, 0, 1, 0, 0, 1);
     list_leaf = (void *) list_tree->child;
     assert_string_equal(list_leaf->schema->name, "uid");
     CHECK_LYD_NODE_TERM(list_leaf, 0, 0, 1, 1, 1, UINT32, "0", 0);
@@ -893,13 +893,13 @@
     /* check first item */
     CHECK_PARSE_LYD_PARAM(data, LYD_XML, 0, LYD_VALIDATE_PRESENT, LY_SUCCESS, tree);
     list_tree = (void *)tree;
-    CHECK_LYD_NODE_INNER(list_tree, 1, 0, 0, 0, 1, 0, 0, 1);
+    CHECK_LYD_NODE_INNER(list_tree, 1, 0, 1, 0, 1, 0, 0, 1);
     list_leaf = (void *) list_tree->child;
     assert_string_equal(list_leaf->schema->name, "uid");
     CHECK_LYD_NODE_TERM(list_leaf, 0, 0, 1, 1, 1, UINT32, "0", 0);
     list_leaf = (void *) list_leaf->next;
     assert_string_equal(list_leaf->schema->name, "group");
-    CHECK_LYD_NODE_TERM(list_leaf, 0, 0, 1, 1, 1, STRING, "User");
+    CHECK_LYD_NODE_TERM(list_leaf, 0, 0, 1, 1, 1, STRING, "Admin");
     list_leaf = (void *) list_leaf->next;
     assert_string_equal(list_leaf->schema->name, "name");
     CHECK_LYD_NODE_TERM(list_leaf, 0, 0, 0, 1, 1, STRING, "Tomáš Novák");
@@ -911,7 +911,7 @@
     CHECK_LYD_NODE_TERM(list_leaf, 0, 0, 1, 1, 1, UINT32, "0", 0);
     list_leaf = (void *) list_leaf->next;
     assert_string_equal(list_leaf->schema->name, "group");
-    CHECK_LYD_NODE_TERM(list_leaf, 0, 0, 1, 1, 1, STRING, "Admin");
+    CHECK_LYD_NODE_TERM(list_leaf, 0, 0, 1, 1, 1, STRING, "User");
     list_leaf = (void *) list_leaf->next;
     assert_string_equal(list_leaf->schema->name, "name");
     CHECK_LYD_NODE_TERM(list_leaf, 0, 0, 0, 1, 1, STRING, "Tomáš Novák");
@@ -962,7 +962,7 @@
             "</user>";
     CHECK_PARSE_LYD_PARAM(data, LYD_XML, 0, LYD_VALIDATE_PRESENT, LY_SUCCESS, tree);
     list_tree = (void *)tree;
-    CHECK_LYD_NODE_INNER(list_tree, 1, 0, 0, 0, 1, 0, 0, 1);
+    CHECK_LYD_NODE_INNER(list_tree, 1, 0, 1, 0, 1, 0, 0, 1);
     list_leaf = (void *) list_tree->child;
     assert_string_equal(list_leaf->schema->name, "uid");
     CHECK_LYD_NODE_TERM(list_leaf, 0, 0, 1, 1, 1, UINT32, "0", 0);
@@ -1026,7 +1026,7 @@
             "</user>";
     CHECK_PARSE_LYD_PARAM(data, LYD_XML, 0, LYD_VALIDATE_PRESENT, LY_SUCCESS, tree);
     list_tree = (void *)tree;
-    CHECK_LYD_NODE_INNER(list_tree, 1, 0, 0, 0, 1, 0, 0, 1);
+    CHECK_LYD_NODE_INNER(list_tree, 1, 0, 1, 0, 1, 0, 0, 1);
     list_tree = (void *) list_tree->next;
     CHECK_LYD_NODE_INNER(list_tree, 1, 0, 0, 0, 1, 0, 0, 1);
     list_tree = (void *) list_tree->next;
@@ -1136,7 +1136,7 @@
 
     CHECK_PARSE_LYD_PARAM(data, LYD_JSON, 0, LYD_VALIDATE_PRESENT, LY_SUCCESS, tree);
     list_tree = (void *)tree;
-    CHECK_LYD_NODE_INNER(list_tree, 1, 0, 0, 0, 1, 0, 0, 1);
+    CHECK_LYD_NODE_INNER(list_tree, 1, 0, 1, 0, 1, 0, 0, 1);
     list_leaf = (void *) list_tree->child;
     assert_string_equal(list_leaf->schema->name, "uid");
     CHECK_LYD_NODE_TERM(list_leaf, 0, 0, 1, 1, 1, UINT32, "0", 0);
@@ -1170,7 +1170,7 @@
     /* check first item */
     CHECK_PARSE_LYD_PARAM(data, LYD_JSON, 0, LYD_VALIDATE_PRESENT, LY_SUCCESS, tree);
     list_tree = (void *)tree;
-    CHECK_LYD_NODE_INNER(list_tree, 1, 0, 0, 0, 1, 0, 0, 1);
+    CHECK_LYD_NODE_INNER(list_tree, 1, 0, 1, 0, 1, 0, 0, 1);
     list_leaf = (void *) list_tree->child;
     assert_string_equal(list_leaf->schema->name, "uid");
     CHECK_LYD_NODE_TERM(list_leaf, 0, 0, 1, 1, 1, UINT32, "0", 0);
@@ -1228,13 +1228,13 @@
             "]}";
     CHECK_PARSE_LYD_PARAM(data, LYD_JSON, 0, LYD_VALIDATE_PRESENT, LY_SUCCESS, tree);
     list_tree = (void *)tree;
-    CHECK_LYD_NODE_INNER(list_tree, 1, 0, 0, 0, 1, 0, 0, 1);
+    CHECK_LYD_NODE_INNER(list_tree, 1, 0, 1, 0, 1, 0, 0, 1);
     list_leaf = (void *) list_tree->child;
     assert_string_equal(list_leaf->schema->name, "uid");
     CHECK_LYD_NODE_TERM(list_leaf, 0, 0, 1, 1, 1, UINT32, "0", 0);
     list_leaf = (void *) list_leaf->next;
     assert_string_equal(list_leaf->schema->name, "group");
-    CHECK_LYD_NODE_TERM(list_leaf, 0, 0, 1, 1, 1, STRING, "User");
+    CHECK_LYD_NODE_TERM(list_leaf, 0, 0, 1, 1, 1, STRING, "Admin");
     list_leaf = (void *) list_leaf->next;
     assert_string_equal(list_leaf->schema->name, "name");
     CHECK_LYD_NODE_TERM(list_leaf, 0, 0, 0, 1, 1, STRING, "Jan Kuba");
@@ -1246,7 +1246,7 @@
     CHECK_LYD_NODE_TERM(list_leaf, 0, 0, 1, 1, 1, UINT32, "0", 0);
     list_leaf = (void *) list_leaf->next;
     assert_string_equal(list_leaf->schema->name, "group");
-    CHECK_LYD_NODE_TERM(list_leaf, 0, 0, 1, 1, 1, STRING, "Admin");
+    CHECK_LYD_NODE_TERM(list_leaf, 0, 0, 1, 1, 1, STRING, "User");
     list_leaf = (void *) list_leaf->next;
     assert_string_equal(list_leaf->schema->name, "name");
     CHECK_LYD_NODE_TERM(list_leaf, 0, 0, 0, 1, 1, STRING, "Jan Kuba");
@@ -1282,7 +1282,7 @@
 
     CHECK_PARSE_LYD_PARAM(data, LYD_JSON, 0, LYD_VALIDATE_PRESENT, LY_SUCCESS, tree);
     list_tree = (void *)tree;
-    CHECK_LYD_NODE_INNER(list_tree, 1, 0, 0, 0, 1, 0, 0, 1);
+    CHECK_LYD_NODE_INNER(list_tree, 1, 0, 1, 0, 1, 0, 0, 1);
     list_leaf = (void *) list_tree->child;
     assert_string_equal(list_leaf->schema->name, "uid");
     CHECK_LYD_NODE_TERM(list_leaf, 0, 0, 1, 1, 1, UINT32, "0", 0);
@@ -1328,7 +1328,7 @@
             "]}";
     CHECK_PARSE_LYD_PARAM(data, LYD_JSON, 0, LYD_VALIDATE_PRESENT, LY_SUCCESS, tree);
     list_tree = (void *)tree;
-    CHECK_LYD_NODE_INNER(list_tree, 1, 0, 0, 0, 1, 0, 0, 1);
+    CHECK_LYD_NODE_INNER(list_tree, 1, 0, 1, 0, 1, 0, 0, 1);
     list_tree = (void *) list_tree->next;
     CHECK_LYD_NODE_INNER(list_tree, 1, 0, 0, 0, 1, 0, 0, 1);
     list_tree = (void *) list_tree->next;