data tree FEATURE schema-ordering of data
All (leaf-)list instances preserve their input
order, new instances inserted at the end.
Opaque nodes are at the end, after all the
standard nodes.
Also, now first instances of (leaf-)lists
are inserted into hash table twice, second
time without their keys/value in the hash.
diff --git a/src/context.c b/src/context.c
index b2637ff..486110c 100644
--- a/src/context.c
+++ b/src/context.c
@@ -756,11 +756,10 @@
}
if (root_bis) {
- if (lyd_insert_sibling(root_bis, root)) {
+ if (lyd_insert_sibling(root, root_bis, &root)) {
goto error;
}
- root = root_bis;
- root_bis = 0;
+ root_bis = NULL;
}
LY_CHECK_GOTO(ret = lyd_validate_all(&root, NULL, LYD_VALIDATE_PRESENT, NULL), error);
diff --git a/src/diff.c b/src/diff.c
index eddce38..04ab13b 100644
--- a/src/diff.c
+++ b/src/diff.c
@@ -121,17 +121,9 @@
/* no parent existed, must be manually connected */
if (!diff_parent) {
/* there actually was no parent to duplicate */
- if (*diff) {
- lyd_insert_sibling(*diff, dup);
- } else {
- *diff = dup;
- }
+ lyd_insert_sibling(*diff, dup, diff);
} else if (!diff_parent->parent) {
- if (*diff) {
- lyd_insert_sibling(*diff, diff_parent);
- } else {
- *diff = diff_parent;
- }
+ lyd_insert_sibling(*diff, diff_parent, diff);
}
/* get module with the operation metadata */
@@ -811,15 +803,14 @@
new_node->schema->name);
return LY_EINVAL;
}
- return lyd_insert(parent_node, new_node);
+ return lyd_insert_child(parent_node, new_node);
}
assert(!(*first_node)->parent || ((struct lyd_node *)(*first_node)->parent == parent_node));
- /* simple insert */
if (!lysc_is_userordered(new_node->schema)) {
- /* insert at the end */
- return lyd_insert_sibling(*first_node, new_node);
+ /* simple insert */
+ return lyd_insert_sibling(*first_node, new_node, first_node);
}
if (key_or_value) {
@@ -945,12 +936,10 @@
/* insert it at the end */
ret = 0;
- if (*first_node) {
- ret = lyd_insert_after((*first_node)->prev, match);
- } else if (parent_node) {
- ret = lyd_insert(parent_node, match);
+ if (parent_node) {
+ ret = lyd_insert_child(parent_node, match);
} else {
- *first_node = match;
+ ret = lyd_insert_sibling(*first_node, match, first_node);
}
if (ret) {
lyd_free_tree(match);
@@ -1481,11 +1470,7 @@
/* insert node into diff if not already */
if (!diff_parent) {
- if (*diff) {
- lyd_insert_sibling(*diff, diff_node);
- } else {
- *diff = diff_node;
- }
+ lyd_insert_sibling(*diff, diff_node, diff);
}
/* update operation */
diff --git a/src/parser_lyb.c b/src/parser_lyb.c
index 95ff05a..2f6f8df 100644
--- a/src/parser_lyb.c
+++ b/src/parser_lyb.c
@@ -892,8 +892,11 @@
attr = NULL;
}
- /* insert */
+ /* insert, keep first pointer correct */
lyd_insert_node((struct lyd_node *)parent, first, node);
+ while (!parent && (*first)->prev->next) {
+ *first = (*first)->prev;
+ }
node = NULL;
stop_subtree:
diff --git a/src/parser_xml.c b/src/parser_xml.c
index eb73a8f..cb1955d 100644
--- a/src/parser_xml.c
+++ b/src/parser_xml.c
@@ -535,9 +535,9 @@
}
if (parent && (cur->schema->flags & LYS_KEY)) {
- /* check the key order, the anchor must always be the last child */
- anchor = lyd_get_prev_key_anchor(parent->child, cur->schema);
- if ((!anchor && parent->child) || (anchor && anchor->next)) {
+ /* check the key order, the anchor must never be a key */
+ anchor = lyd_insert_get_next_anchor(parent->child, cur);
+ if (anchor && (anchor->schema->flags & LYS_KEY)) {
if (lydctx->options & LYD_PARSE_STRICT) {
LOGVAL(ctx, LY_VLOG_LINE, &xmlctx->line, LYVE_DATA, "Invalid position of the key \"%s\" in a list.",
cur->schema->name);
@@ -649,8 +649,11 @@
attr = NULL;
}
- /* insert */
+ /* insert, keep first pointer correct */
lyd_insert_node((struct lyd_node *)parent, first, cur);
+ while (!parent && (*first)->prev->next) {
+ *first = (*first)->prev;
+ }
cur = NULL;
/* parser next */
diff --git a/src/tree_data.c b/src/tree_data.c
index 2047fe2..72e8c7b 100644
--- a/src/tree_data.c
+++ b/src/tree_data.c
@@ -49,6 +49,9 @@
#include "xml.h"
#include "xpath.h"
+static LY_ERR lyd_find_sibling_schema(const struct lyd_node *siblings, const struct lysc_node *schema,
+ struct lyd_node **match);
+
LY_ERR
lyd_value_parse(struct lyd_node_term *node, const char *value, size_t value_len, int *dynamic, int second,
ly_clb_resolve_prefix get_prefix, void *parser, LYD_FORMAT format, const struct lyd_node *tree)
@@ -353,7 +356,8 @@
}
API LY_ERR
-lyd_parse_data_fd(const struct ly_ctx *ctx, int fd, LYD_FORMAT format, int parse_options, int validate_options, struct lyd_node **tree)
+lyd_parse_data_fd(const struct ly_ctx *ctx, int fd, LYD_FORMAT format, int parse_options, int validate_options,
+ struct lyd_node **tree)
{
LY_ERR ret;
struct ly_in *in;
@@ -366,7 +370,8 @@
}
API LY_ERR
-lyd_parse_data_path(const struct ly_ctx *ctx, const char *path, LYD_FORMAT format, int parse_options, int validate_options, struct lyd_node **tree)
+lyd_parse_data_path(const struct ly_ctx *ctx, const char *path, LYD_FORMAT format, int parse_options,
+ int validate_options, struct lyd_node **tree)
{
LY_ERR ret;
struct ly_in *in;
@@ -1308,17 +1313,78 @@
}
struct lyd_node *
-lyd_get_prev_key_anchor(const struct lyd_node *first_sibling, const struct lysc_node *new_key)
+lyd_insert_get_next_anchor(const struct lyd_node *first_sibling, const struct lyd_node *new_node)
{
- const struct lysc_node *prev_key;
+ const struct lysc_node *schema, *sparent;
struct lyd_node *match = NULL;
+ int found;
- if (!first_sibling) {
+ assert(new_node);
+
+ if (!first_sibling || !new_node->schema) {
+ /* insert at the end, no next anchor */
return NULL;
}
- for (prev_key = new_key->prev; !match && prev_key->next; prev_key = prev_key->prev) {
- lyd_find_sibling_val(first_sibling, prev_key, NULL, 0, &match);
+ if (first_sibling->parent && first_sibling->parent->children_ht) {
+ /* find the anchor using hashes */
+ sparent = first_sibling->parent->schema;
+ schema = lys_getnext(new_node->schema, sparent, NULL, 0);
+ while (schema) {
+ /* keep trying to find the first existing instance of the closest following schema sibling,
+ * otherwise return NULL - inserting at the end */
+ if (!lyd_find_sibling_schema(first_sibling, schema, &match)) {
+ break;
+ }
+
+ schema = lys_getnext(schema, sparent, NULL, 0);
+ }
+ } else {
+ /* find the anchor without hashes */
+ match = (struct lyd_node *)first_sibling;
+ if (!lysc_data_parent(new_node->schema)) {
+ /* we are in top-level, skip all the data from preceding modules */
+ LY_LIST_FOR(match, match) {
+ if (!match->schema || (strcmp(lyd_owner_module(match)->name, lyd_owner_module(new_node)->name) >= 0)) {
+ break;
+ }
+ }
+ }
+
+ /* get the first schema sibling */
+ sparent = lysc_data_parent(new_node->schema);
+ schema = lys_getnext(NULL, sparent, new_node->schema->module->compiled, 0);
+
+ found = 0;
+ LY_LIST_FOR(match, match) {
+ if (!match->schema || (lyd_owner_module(match) != lyd_owner_module(new_node))) {
+ /* we have found an opaque node, which must be at the end, so use it OR
+ * modules do not match, so we must have traversed all the data from new_node module (if any),
+ * we have found the first node of the next module, that is what we want */
+ break;
+ }
+
+ /* skip schema nodes until we find the instantiated one */
+ while (!found) {
+ if (new_node->schema == schema) {
+ /* we have found the schema of the new node, continue search to find the first
+ * data node with a different schema (after our schema) */
+ found = 1;
+ break;
+ }
+ if (match->schema == schema) {
+ /* current node (match) is a data node still before the new node, continue search in data */
+ break;
+ }
+ schema = lys_getnext(schema, sparent, new_node->schema->module->compiled, 0);
+ assert(schema);
+ }
+
+ if (found && (match->schema != new_node->schema)) {
+ /* find the next node after we have found our node schema data instance */
+ break;
+ }
+ }
}
return match;
@@ -1361,7 +1427,7 @@
/* remove default flags from NP containers */
par->flags &= ~LYD_DEFAULT;
}
- if ((par->schema->nodetype == LYS_LIST) && (par->schema->flags & LYS_KEYLESS)) {
+ if (par->schema && (par->schema->nodetype == LYS_LIST) && (par->schema->flags & LYS_KEYLESS)) {
/* rehash key-less list */
lyd_hash((struct lyd_node *)par);
}
@@ -1401,7 +1467,7 @@
/* remove default flags from NP containers */
par->flags &= ~LYD_DEFAULT;
}
- if ((par->schema->nodetype == LYS_LIST) && (par->schema->flags & LYS_KEYLESS)) {
+ if (par->schema && (par->schema->nodetype == LYS_LIST) && (par->schema->flags & LYS_KEYLESS)) {
/* rehash key-less list */
lyd_hash((struct lyd_node *)par);
}
@@ -1409,7 +1475,7 @@
}
/**
- * @brief Insert node as the last child of a parent.
+ * @brief Insert node as the first and only child of a parent.
*
* Handles inserting into NP containers and key-less lists.
*
@@ -1417,22 +1483,16 @@
* @param[in] node Node to insert.
*/
static void
-lyd_insert_last_node(struct lyd_node *parent, struct lyd_node *node)
+lyd_insert_only_child(struct lyd_node *parent, struct lyd_node *node)
{
struct lyd_node_inner *par;
- assert(parent && !node->next && (node->prev == node));
+ assert(parent && !lyd_node_children(parent, 0) && !node->next && (node->prev == node));
assert(!parent->schema || (parent->schema->nodetype & LYD_NODE_INNER));
par = (struct lyd_node_inner *)parent;
- if (!par->child) {
- par->child = node;
- } else {
- node->prev = par->child->prev;
- par->child->prev->next = node;
- par->child->prev = node;
- }
+ par->child = node;
node->parent = par;
for (; par; par = par->parent) {
@@ -1476,65 +1536,41 @@
}
void
-lyd_insert_node(struct lyd_node *parent, struct lyd_node **first_sibling, struct lyd_node *node)
+lyd_insert_node(struct lyd_node *parent, struct lyd_node **first_sibling_p, struct lyd_node *node)
{
- struct lyd_node *anchor;
+ struct lyd_node *anchor, *first_sibling;
- assert((parent || first_sibling) && node && (node->hash || !node->schema));
+ /* inserting list without its keys is not supported */
+ assert((parent || first_sibling_p) && node && (node->hash || !node->schema));
- if (!parent && first_sibling && (*first_sibling) && (*first_sibling)->parent) {
- parent = (struct lyd_node *)(*first_sibling)->parent;
+ if (!parent && first_sibling_p && (*first_sibling_p) && (*first_sibling_p)->parent) {
+ parent = (struct lyd_node *)(*first_sibling_p)->parent;
}
- if (parent) {
- if (node->schema && (node->schema->flags & LYS_KEY)) {
- /* it is key and we need to insert it at the correct place */
- anchor = lyd_get_prev_key_anchor(lyd_node_children(parent, 0), node->schema);
- if (anchor) {
- lyd_insert_after_node(anchor, node);
- } else if (lyd_node_children(parent, 0)) {
- lyd_insert_before_node(lyd_node_children(parent, 0), node);
- } else {
- lyd_insert_last_node(parent, node);
- }
+ /* get first sibling */
+ first_sibling = parent ? ((struct lyd_node_inner *)parent)->child : *first_sibling_p;
- /* insert into parent HT */
- lyd_insert_hash(node);
-
- /* hash list if all its keys were added */
- if (lyd_insert_has_keys(parent)) {
- lyd_hash(parent);
-
- /* now we can insert even the list into its parent HT */
- lyd_insert_hash(parent);
- }
-
- } else {
- /* last child */
- lyd_insert_last_node(parent, node);
-
- if (!node->schema || (node->schema->nodetype != LYS_LIST) || lyd_insert_has_keys(node)) {
- /* insert into parent HT */
- lyd_insert_hash(node);
- }
- }
- } else if (*first_sibling) {
- /* top-level siblings */
- anchor = (*first_sibling)->prev;
- while (anchor->prev->next && (lyd_owner_module(anchor) != lyd_owner_module(node))) {
- anchor = anchor->prev;
- }
-
- if (lyd_owner_module(anchor) == lyd_owner_module(node)) {
- /* insert after last sibling from this module */
- lyd_insert_after_node(anchor, node);
- } else {
- /* no data from this module, insert at the last position */
- lyd_insert_after_node((*first_sibling)->prev, node);
- }
+ /* find the anchor, our next node, so we can insert before it */
+ anchor = lyd_insert_get_next_anchor(first_sibling, node);
+ if (anchor) {
+ lyd_insert_before_node(anchor, node);
+ } else if (first_sibling) {
+ lyd_insert_after_node(first_sibling->prev, node);
+ } else if (parent) {
+ lyd_insert_only_child(parent, node);
} else {
- /* the only sibling */
- *first_sibling = node;
+ *first_sibling_p = node;
+ }
+
+ /* insert into parent HT */
+ lyd_insert_hash(node);
+
+ /* finish hashes for our parent, if needed and possible */
+ if (node->schema && (node->schema->flags & LYS_KEY) && lyd_insert_has_keys(parent)) {
+ lyd_hash(parent);
+
+ /* now we can insert even the list into its parent HT */
+ lyd_insert_hash(parent);
}
}
@@ -1552,7 +1588,8 @@
if (parent) {
/* inner node */
if (par2 != parent) {
- LOGERR(schema->module->ctx, LY_EINVAL, "Cannot insert, parent of \"%s\" is not \"%s\".", schema->name, parent->name);
+ LOGERR(schema->module->ctx, LY_EINVAL, "Cannot insert, parent of \"%s\" is not \"%s\".", schema->name,
+ parent->name);
return LY_EINVAL;
}
} else {
@@ -1567,7 +1604,7 @@
}
API LY_ERR
-lyd_insert(struct lyd_node *parent, struct lyd_node *node)
+lyd_insert_child(struct lyd_node *parent, struct lyd_node *node)
{
struct lyd_node *iter;
@@ -1594,17 +1631,14 @@
}
API LY_ERR
-lyd_insert_sibling(struct lyd_node *sibling, struct lyd_node *node)
+lyd_insert_sibling(struct lyd_node *sibling, struct lyd_node *node, struct lyd_node **first)
{
struct lyd_node *iter;
- LY_CHECK_ARG_RET(NULL, sibling, node, LY_EINVAL);
+ LY_CHECK_ARG_RET(NULL, node, LY_EINVAL);
- LY_CHECK_RET(lyd_insert_check_schema(lysc_data_parent(sibling->schema), node->schema));
-
- if (node->schema->flags & LYS_KEY) {
- LOGERR(sibling->schema->module->ctx, LY_EINVAL, "Cannot insert key \"%s\".", node->schema->name);
- return LY_EINVAL;
+ if (sibling) {
+ LY_CHECK_RET(lyd_insert_check_schema(lysc_data_parent(sibling->schema), node->schema));
}
if (node->parent || node->prev->next) {
@@ -1612,56 +1646,22 @@
}
while (node) {
+ if (node->schema->flags & LYS_KEY) {
+ LOGERR(LYD_NODE_CTX(node), LY_EINVAL, "Cannot insert key \"%s\".", node->schema->name);
+ return LY_EINVAL;
+ }
+
iter = node->next;
lyd_unlink_tree(node);
lyd_insert_node(NULL, &sibling, node);
node = iter;
}
- return LY_SUCCESS;
-}
-static LY_ERR
-lyd_insert_after_check_place(struct lyd_node *anchor, struct lyd_node *sibling, struct lyd_node *node)
-{
- if (sibling->parent) {
- /* nested, we do not care for the order */
- return LY_SUCCESS;
- }
-
- if (anchor) {
- if (anchor->next && (lyd_owner_module(anchor) == lyd_owner_module(anchor->next))
- && (lyd_owner_module(node) != lyd_owner_module(anchor))) {
- LOGERR(sibling->schema->module->ctx, LY_EINVAL, "Cannot insert top-level module \"%s\" data into module \"%s\" data.",
- lyd_owner_module(node)->name, lyd_owner_module(anchor)->name);
- return LY_EINVAL;
- }
-
- if ((lyd_owner_module(node) == lyd_owner_module(anchor))
- || (anchor->next && (lyd_owner_module(node) == lyd_owner_module(anchor->next)))) {
- /* inserting before/after its module data */
- return LY_SUCCESS;
- }
- }
-
- /* find first sibling */
- while (sibling->prev->next) {
- sibling = sibling->prev;
- }
-
- if (!anchor) {
- if (lyd_owner_module(node) == lyd_owner_module(sibling)) {
- /* inserting before its module data */
- return LY_SUCCESS;
- }
- }
-
- /* check there are no data of this module */
- LY_LIST_FOR(sibling, sibling) {
- if (lyd_owner_module(node) == lyd_owner_module(sibling)) {
- /* some data of this module found */
- LOGERR(sibling->schema->module->ctx, LY_EINVAL, "Top-level data of module \"%s\" already exist,"
- " they must be directly connected.", lyd_owner_module(node)->name);
- return LY_EINVAL;
+ if (first) {
+ /* find the first sibling */
+ *first = sibling;
+ while ((*first)->prev->next) {
+ *first = (*first)->prev;
}
}
@@ -1677,16 +1677,11 @@
LY_CHECK_RET(lyd_insert_check_schema(lysc_data_parent(sibling->schema), node->schema));
- if (node->schema->flags & LYS_KEY) {
- LOGERR(sibling->schema->module->ctx, LY_EINVAL, "Cannot insert key \"%s\".", node->schema->name);
- return LY_EINVAL;
- } else if (sibling->schema->flags & LYS_KEY) {
- LOGERR(sibling->schema->module->ctx, LY_EINVAL, "Cannot insert into keys.");
+ if (!(node->schema->nodetype & (LYS_LIST | LYS_LEAFLIST)) || !(node->schema->flags & LYS_ORDBY_USER)) {
+ LOGERR(LYD_NODE_CTX(sibling), LY_EINVAL, "Can be used only for user-ordered nodes.");
return LY_EINVAL;
}
- LY_CHECK_RET(lyd_insert_after_check_place(sibling->prev->next ? sibling->prev : NULL, sibling, node));
-
if (node->parent || node->prev->next) {
lyd_unlink_tree(node);
}
@@ -1717,16 +1712,11 @@
LY_CHECK_RET(lyd_insert_check_schema(lysc_data_parent(sibling->schema), node->schema));
- if (node->schema->flags & LYS_KEY) {
- LOGERR(sibling->schema->module->ctx, LY_EINVAL, "Cannot insert key \"%s\".", node->schema->name);
- return LY_EINVAL;
- } else if (sibling->next && (sibling->next->schema->flags & LYS_KEY)) {
- LOGERR(sibling->schema->module->ctx, LY_EINVAL, "Cannot insert into keys.");
+ if (!(node->schema->nodetype & (LYS_LIST | LYS_LEAFLIST)) || !(node->schema->flags & LYS_ORDBY_USER)) {
+ LOGERR(LYD_NODE_CTX(sibling), LY_EINVAL, "Can be used only for user-ordered nodes.");
return LY_EINVAL;
}
- LY_CHECK_RET(lyd_insert_after_check_place(sibling, sibling, node));
-
if (node->parent || node->prev->next) {
lyd_unlink_tree(node);
}
@@ -1755,6 +1745,9 @@
return;
}
+ /* update hashes while still linked into the tree */
+ lyd_unlink_hash(node);
+
/* unlink from siblings */
if (node->prev->next) {
node->prev->next = node->next;
@@ -1782,8 +1775,6 @@
node->parent->child = node->next;
}
- lyd_unlink_hash(node);
-
/* check for keyless list and update its hash */
for (iter = (struct lyd_node *)node->parent; iter; iter = (struct lyd_node *)iter->parent) {
if (iter->schema && (iter->schema->flags & LYS_KEYLESS)) {
@@ -3106,8 +3097,6 @@
val1 = *((struct lysc_node **)val1_p);
val2 = *((struct lyd_node **)val2_p);
- assert(val1->nodetype & (LYD_NODE_INNER | LYS_LEAF));
-
if (val1 == val2->schema) {
/* schema match is enough */
return 1;
@@ -3124,16 +3113,7 @@
uint32_t hash;
values_equal_cb ht_cb;
- assert(siblings && schema && (schema->nodetype & (LYD_NODE_INNER | LYS_LEAF)));
-
- /* find first sibling */
- if (siblings->parent) {
- siblings = siblings->parent->child;
- } else {
- while (siblings->prev->next) {
- siblings = siblings->prev;
- }
- }
+ assert(siblings && schema);
parent = (struct lyd_node_inner *)siblings->parent;
if (parent && parent->children_ht) {
@@ -3156,7 +3136,16 @@
/* set the original hash table compare function back */
lyht_set_cb(parent->children_ht, ht_cb);
} else {
- /* no children hash table */
+ /* find first sibling */
+ if (siblings->parent) {
+ siblings = siblings->parent->child;
+ } else {
+ while (siblings->prev->next) {
+ siblings = siblings->prev;
+ }
+ }
+
+ /* search manually without hashes */
for (; siblings; siblings = siblings->next) {
if (siblings->schema == schema) {
/* schema match is enough */
@@ -3189,9 +3178,6 @@
if ((schema->nodetype == LYS_LIST) && (schema->flags & LYS_KEYLESS)) {
LOGERR(schema->module->ctx, LY_EINVAL, "Invalid arguments - key-less list (%s()).", __func__);
return LY_EINVAL;
- } else if ((schema->nodetype & (LYS_LEAFLIST | LYS_LIST)) && !key_or_value) {
- LOGERR(schema->module->ctx, LY_EINVAL, "Invalid arguments - no value/keys for a (leaf-)list (%s()).", __func__);
- return LY_EINVAL;
} else if (schema->nodetype & (LYS_CHOICE | LYS_CASE)) {
LOGERR(schema->module->ctx, LY_EINVAL, "Invalid arguments - schema type %s (%s()).",
lys_nodetype2str(schema->nodetype), __func__);
@@ -3210,37 +3196,22 @@
val_len = strlen(key_or_value);
}
- /* create data node if needed and find it */
- switch (schema->nodetype) {
- case LYS_CONTAINER:
- case LYS_ANYXML:
- case LYS_ANYDATA:
- case LYS_NOTIF:
- case LYS_RPC:
- case LYS_ACTION:
- case LYS_LEAF:
- /* find it based on schema only, there cannot be more instances */
- rc = lyd_find_sibling_schema(siblings, schema, match);
- break;
- case LYS_LEAFLIST:
- /* target used attributes: schema, hash, value */
- rc = lyd_create_term(schema, key_or_value, val_len, NULL, lydjson_resolve_prefix, NULL, LYD_JSON, &target);
- LY_CHECK_RET(rc && (rc != LY_EINCOMPLETE), rc);
- rc = LY_SUCCESS;
- /* fallthrough */
- case LYS_LIST:
- if (schema->nodetype == LYS_LIST) {
+ if ((schema->nodetype & (LYS_LIST | LYS_LEAFLIST)) && key_or_value) {
+ /* create a data node and find the instance */
+ if (schema->nodetype == LYS_LEAFLIST) {
+ /* target used attributes: schema, hash, value */
+ rc = lyd_create_term(schema, key_or_value, val_len, NULL, lydjson_resolve_prefix, NULL, LYD_JSON, &target);
+ LY_CHECK_RET(rc && (rc != LY_EINCOMPLETE), rc);
+ } else {
/* target used attributes: schema, hash, child (all keys) */
LY_CHECK_RET(lyd_create_list2(schema, key_or_value, val_len, &target));
}
/* find it */
rc = lyd_find_sibling_first(siblings, target, match);
- break;
- default:
- /* unreachable */
- LOGINT(schema->module->ctx);
- return LY_EINT;
+ } else {
+ /* find the first schema node instance */
+ rc = lyd_find_sibling_schema(siblings, schema, match);
}
lyd_free_tree(target);
diff --git a/src/tree_data.h b/src/tree_data.h
index ea44fe7..fd7d421 100644
--- a/src/tree_data.h
+++ b/src/tree_data.h
@@ -690,7 +690,7 @@
LY_ERR lyd_change_meta(struct lyd_meta *meta, const char *val_str);
/**
- * @brief Insert a child into a parent. It is inserted as the last child.
+ * @brief Insert a child into a parent.
*
* - if the node is part of some other tree, it is automatically unlinked.
* - if the node is the first node of a node list (with no parent), all the subsequent nodes are also inserted.
@@ -700,23 +700,24 @@
* @return LY_SUCCESS on success.
* @return LY_ERR error on error.
*/
-LY_ERR lyd_insert(struct lyd_node *parent, struct lyd_node *node);
+LY_ERR lyd_insert_child(struct lyd_node *parent, struct lyd_node *node);
/**
- * @brief Insert a node into siblings. It is inserted as the last sibling.
+ * @brief Insert a node into siblings.
*
* - if the node is part of some other tree, it is automatically unlinked.
* - if the node is the first node of a node list (with no parent), all the subsequent nodes are also inserted.
*
- * @param[in] sibling Siblings to insert into.
+ * @param[in] sibling Siblings to insert into, can even be NULL.
* @param[in] node Node to insert.
+ * @param[out] first Optionally return the first sibling after insertion. Can be the address of @p sibling.
* @return LY_SUCCESS on success.
* @return LY_ERR error on error.
*/
-LY_ERR lyd_insert_sibling(struct lyd_node *sibling, struct lyd_node *node);
+LY_ERR lyd_insert_sibling(struct lyd_node *sibling, struct lyd_node *node, struct lyd_node **first);
/**
- * @brief Insert a node before another node that is its schema sibling.
+ * @brief Insert a node before another node, can be used only for user-ordered nodes.
*
* - if the node is part of some other tree, it is automatically unlinked.
* - if the node is the first node of a node list (with no parent), all the subsequent nodes are also inserted.
@@ -729,7 +730,7 @@
LY_ERR lyd_insert_before(struct lyd_node *sibling, struct lyd_node *node);
/**
- * @brief Insert a node after another node that is its schema sibling.
+ * @brief Insert a node after another node, can be used only for user-ordered nodes.
*
* - if the node is part of some other tree, it is automatically unlinked.
* - if the node is the first node of a node list (with no parent), all the subsequent nodes are also inserted.
@@ -1246,15 +1247,8 @@
*
* @param[in] siblings Siblings to search in including preceding and succeeding nodes.
* @param[in] schema Schema node of the data node to find.
- * @param[in] key_or_value Expected value depends on the type of \p schema:
- * LYS_CONTAINER:
- * LYS_LEAF:
- * LYS_ANYXML:
- * LYS_ANYDATA:
- * LYS_NOTIF:
- * LYS_RPC:
- * LYS_ACTION:
- * NULL should be always set, will be ignored.
+ * @param[in] key_or_value If it is NULL, the first schema node data instance is found. For nodes with many
+ * instances, it can be set based on the type of @p schema:
* LYS_LEAFLIST:
* Searched instance value.
* LYS_LIST:
@@ -1277,7 +1271,7 @@
/**
* @brief Search in the given data for instances of nodes matching the provided XPath.
*
- * The expected format of the expression is JSON (::LYD_JSON) meaning the first node in every path
+ * The expected format of the expression is ::LYD_JSON, meaning the first node in every path
* must have its module name as prefix or be the special `*` value for all the nodes.
*
* If a list instance is being selected with all its key values specified (but not necessarily ordered)
diff --git a/src/tree_data_hash.c b/src/tree_data_hash.c
index 5ebe120..b8a7725 100644
--- a/src/tree_data_hash.c
+++ b/src/tree_data_hash.c
@@ -12,6 +12,7 @@
* https://opensource.org/licenses/BSD-3-Clause
*/
+#include <assert.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
@@ -73,11 +74,10 @@
break;
}
int dynamic = 0;
- struct lysc_type *type = ((struct lysc_node_leaf*)iter->schema)->type;
- const char *value = type->plugin->print(&((struct lyd_node_term*)iter)->value, LYD_JSON, json_print_get_prefix, NULL, &dynamic);
+ const char *value = lyd_value2str((struct lyd_node_term *)iter, &dynamic);
node->hash = dict_hash_multi(node->hash, value, strlen(value));
if (dynamic) {
- free((char*)value);
+ free((char *)value);
}
}
} else {
@@ -85,10 +85,8 @@
lyd_hash_keyless_list_dfs(list->child, &node->hash);
}
} else if (node->schema->nodetype == LYS_LEAFLIST) {
- struct lyd_node_term *llist = (struct lyd_node_term*)node;
int dynamic = 0;
- const char *value = ((struct lysc_node_leaflist*)node->schema)->type->plugin->print(&llist->value, LYD_JSON,
- json_print_get_prefix, NULL, &dynamic);
+ const char *value = lyd_value2str((struct lyd_node_term *)node, &dynamic);
node->hash = dict_hash_multi(node->hash, value, strlen(value));
if (dynamic) {
free((char*)value);
@@ -128,10 +126,58 @@
return 0;
}
+/**
+ * @brief Add single node into children hash table.
+ *
+ * @param[in] ht Children hash table.
+ * @param[in] node Node to insert.
+ * @param[in] empty_ht Whether we started with an empty HT meaning no nodes were inserted yet.
+ * @return LY_ERR value.
+ */
+static LY_ERR
+lyd_insert_hash_add(struct hash_table *ht, struct lyd_node *node, int empty_ht)
+{
+ uint32_t hash;
+
+ assert(ht && node && node->schema);
+
+ /* add node itself */
+ if (lyht_insert(ht, &node, node->hash, NULL)) {
+ LOGINT(LYD_NODE_CTX(node));
+ return LY_EINT;
+ }
+
+ /* add first instance of a (leaf-)list */
+ if ((node->schema->nodetype & (LYS_LIST | LYS_LEAFLIST))
+ && (!node->prev->next || (node->prev->schema != node->schema))) {
+ /* get the simple hash */
+ hash = dict_hash_multi(0, node->schema->module->name, strlen(node->schema->module->name));
+ hash = dict_hash_multi(hash, node->schema->name, strlen(node->schema->name));
+ hash = dict_hash_multi(hash, NULL, 0);
+
+ /* remove any previous stored instance, only if we did not start with an empty HT */
+ if (!empty_ht && node->next && (node->next->schema == node->schema)) {
+ if (lyht_remove(ht, &node->next, hash)) {
+ LOGINT(LYD_NODE_CTX(node));
+ return LY_EINT;
+ }
+ }
+
+ /* insert this instance as the first (leaf-)list instance */
+ if (lyht_insert(ht, &node, hash, NULL)) {
+ LOGINT(LYD_NODE_CTX(node));
+ return LY_EINT;
+ }
+ }
+
+ return LY_SUCCESS;
+}
+
LY_ERR
lyd_insert_hash(struct lyd_node *node)
{
struct lyd_node *iter;
+ uint32_t u;
if (!node->parent || !node->schema || !node->parent->schema) {
/* nothing to do */
@@ -140,27 +186,26 @@
/* create parent hash table if required, otherwise just add the new child */
if (!node->parent->children_ht) {
- unsigned int u;
-
/* the hash table is created only when the number of children in a node exceeds the
* defined minimal limit LYD_HT_MIN_ITEMS
*/
- for (u = 0, iter = node->parent->child; iter; ++u, iter = iter->next);
+ u = 0;
+ LY_LIST_FOR(node->parent->child, iter) {
+ if (iter->schema) {
+ ++u;
+ }
+ }
if (u >= LYD_HT_MIN_ITEMS) {
/* create hash table, insert all the children */
node->parent->children_ht = lyht_new(1, sizeof(struct lyd_node *), lyd_hash_table_val_equal, NULL, 1);
LY_LIST_FOR(node->parent->child, iter) {
- if (lyht_insert(node->parent->children_ht, &iter, iter->hash, NULL)) {
- LOGINT(node->schema->module->ctx);
- return LY_EINT;
+ if (iter->schema) {
+ LY_CHECK_RET(lyd_insert_hash_add(node->parent->children_ht, iter, 1));
}
}
}
} else {
- if (lyht_insert(node->parent->children_ht, &node, node->hash, NULL)) {
- LOGINT(node->schema->module->ctx);
- return LY_EINT;
- }
+ LY_CHECK_RET(lyd_insert_hash_add(node->parent->children_ht, node, 0));
}
return LY_SUCCESS;
@@ -169,7 +214,38 @@
void
lyd_unlink_hash(struct lyd_node *node)
{
- if (node->parent && node->parent->schema && node->parent->children_ht) {
- lyht_remove(node->parent->children_ht, &node, node->hash);
+ uint32_t hash;
+
+ if (!node->parent || !node->schema || !node->parent->schema || !node->parent->children_ht) {
+ /* not in any HT */
+ return;
+ }
+
+ /* remove from the parent HT */
+ if (lyht_remove(node->parent->children_ht, &node, node->hash)) {
+ LOGINT(LYD_NODE_CTX(node));
+ return;
+ }
+
+ /* first instance of the (leaf-)list, needs to be removed from HT */
+ if ((node->schema->nodetype & (LYS_LIST | LYS_LEAFLIST)) && (!node->prev->next || (node->prev->schema != node->schema))) {
+ /* get the simple hash */
+ hash = dict_hash_multi(0, node->schema->module->name, strlen(node->schema->module->name));
+ hash = dict_hash_multi(hash, node->schema->name, strlen(node->schema->name));
+ hash = dict_hash_multi(hash, NULL, 0);
+
+ /* remove the instance */
+ if (lyht_remove(node->parent->children_ht, &node, hash)) {
+ LOGINT(LYD_NODE_CTX(node));
+ return;
+ }
+
+ /* add the next instance */
+ if (node->next && (node->next->schema == node->schema)) {
+ if (lyht_insert(node->parent->children_ht, &node->next, hash, NULL)) {
+ LOGINT(LYD_NODE_CTX(node));
+ return;
+ }
+ }
}
}
diff --git a/src/tree_data_internal.h b/src/tree_data_internal.h
index 97b7790..2271c4b 100644
--- a/src/tree_data_internal.h
+++ b/src/tree_data_internal.h
@@ -173,20 +173,17 @@
const char *ns, struct lyd_node **node);
/**
- * @brief Find the key after which to insert the new key.
+ * @brief Find the next node, before which to insert the new node.
*
- * @param[in] first_sibling List first sibling.
- * @param[in] new_key Key that will be inserted.
- * @return Key to insert after.
- * @return NULL if the new key should be first.
+ * @param[in] first_sibling First sibling of the nodes to consider.
+ * @param[in] new_node Node that will be inserted.
+ * @return Node to insert after.
+ * @return NULL if the new node should be first.
*/
-struct lyd_node *lyd_get_prev_key_anchor(const struct lyd_node *first_sibling, const struct lysc_node *new_key);
+struct lyd_node *lyd_insert_get_next_anchor(const struct lyd_node *first_sibling, const struct lyd_node *new_node);
/**
- * @brief Insert a node into parent/siblings. In case a key is being inserted into a list, the correct position
- * is found, inserted into, and if it is the last key, parent list hash is calculated. Also, in case we are inserting
- * into top-level siblings, insert it as the last sibling of all the module data siblings. Otherwise it is inserted at
- * the very last place.
+ * @brief Insert a node into parent/siblings. Order and hashes are fully handled.
*
* @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.