data tree CHANGE improve lyd_insert(), lyd_insert_after() and lyd_insert_before()
Make the functions more smarter to be able to replace the implicit default
nodes instead of just adding the new nodes next to the previously automaticaly
created implicit default nodes.
lyd_insert() also supports smart inserting of a key into a list - it is able to
put the key into a correct position.
diff --git a/src/parser_json.c b/src/parser_json.c
index 3216ef6..8371e9f 100644
--- a/src/parser_json.c
+++ b/src/parser_json.c
@@ -1119,7 +1119,7 @@
ly_errno = 0;
if (!(options & LYD_OPT_TRUSTED) &&
(lyv_data_content(list, options, unres) ||
- lyv_multicases(list, NULL, first_sibling == list ? NULL : first_sibling, 0, NULL))) {
+ lyv_multicases(list, NULL, first_sibling == list ? NULL : &first_sibling, 0, NULL))) {
if (ly_errno) {
goto error;
}
@@ -1161,7 +1161,7 @@
ly_errno = 0;
if (!(options & LYD_OPT_TRUSTED) &&
(lyv_data_content(result, options, unres) ||
- lyv_multicases(result, NULL, first_sibling == result ? NULL : first_sibling, 0, NULL))) {
+ lyv_multicases(result, NULL, first_sibling == result ? NULL : &first_sibling, 0, NULL))) {
if (ly_errno) {
goto error;
}
diff --git a/src/parser_xml.c b/src/parser_xml.c
index 9eadb05..3ecdc82 100644
--- a/src/parser_xml.c
+++ b/src/parser_xml.c
@@ -478,7 +478,7 @@
ly_errno = 0;
if (!(options & LYD_OPT_TRUSTED) &&
(lyv_data_content(*result, options, unres) ||
- lyv_multicases(*result, NULL, first_sibling == *result ? NULL : first_sibling, 0, NULL))) {
+ lyv_multicases(*result, NULL, first_sibling == *result ? NULL : &first_sibling, 0, NULL))) {
if (ly_errno) {
goto error;
} else {
diff --git a/src/tree_data.c b/src/tree_data.c
index 1bc9ba0..dbc34a4 100644
--- a/src/tree_data.c
+++ b/src/tree_data.c
@@ -2665,6 +2665,10 @@
}
if (elem->schema->nodetype & (LYS_LEAF | LYS_LEAFLIST | LYS_ANYDATA)) {
+ if (elem == node) {
+ /* stop the loop */
+ break;
+ }
goto nextsibling;
}
@@ -2685,6 +2689,7 @@
}
/* go back to parents */
while (!next) {
+ elem = elem->parent;
if (elem->parent == node) {
/* we are done, back in start node */
break;
@@ -2711,7 +2716,7 @@
}
int
-lyv_multicases(struct lyd_node *node, struct lys_node *schemanode, struct lyd_node *first_sibling,
+lyv_multicases(struct lyd_node *node, struct lys_node *schemanode, struct lyd_node **first_sibling,
int autodelete, struct lyd_node *nodel)
{
struct lys_node *sparent, *schoice, *scase, *saux;
@@ -2726,7 +2731,7 @@
if (!sparent || !(sparent->nodetype & (LYS_CHOICE | LYS_CASE))) {
/* node is not under any choice */
return EXIT_SUCCESS;
- } else if (!first_sibling) {
+ } else if (!first_sibling || !(*first_sibling)) {
/* nothing to check */
return EXIT_SUCCESS;
}
@@ -2742,7 +2747,7 @@
autodelete:
/* remove all nodes from other cases than 'sparent' */
- LY_TREE_FOR_SAFE(first_sibling, next, iter) {
+ LY_TREE_FOR_SAFE(*first_sibling, next, iter) {
if (schemanode == iter->schema) {
continue;
}
@@ -2756,8 +2761,8 @@
LOGVAL(LYE_MCASEDATA, LY_VLOG_LYD, iter, schoice->name);
return 2;
}
- if (iter == first_sibling) {
- first_sibling = next;
+ if (iter == *first_sibling) {
+ *first_sibling = next;
}
lyd_free(iter);
} else {
@@ -2767,7 +2772,7 @@
}
}
- if (first_sibling && (saux = lys_parent(schoice)) && (saux->nodetype & LYS_CASE)) {
+ if (*first_sibling && (saux = lys_parent(schoice)) && (saux->nodetype & LYS_CASE)) {
/* go recursively in case of nested choices */
schoice = lys_parent(saux);
scase = saux;
@@ -2777,12 +2782,61 @@
return EXIT_SUCCESS;
}
+static int
+lyd_replace(struct lyd_node *old, struct lyd_node *new)
+{
+ assert(old);
+
+ if (!new) {
+ /* remove the old one */
+ goto finish;
+ }
+
+ /* isolate new (just for sure) */
+ new->next = NULL;
+ new->prev = new;
+
+ /* parent */
+ new->parent = old->parent;
+ if (old->parent) {
+ if (old->parent->child == old) {
+ old->parent->child = new;
+ }
+ old->parent = NULL;
+ }
+
+ /* predecessor */
+ if (old->prev == old) {
+ /* the old was alone */
+ goto finish;
+ }
+ if (old->prev->next) {
+ old->prev->next = new;
+ }
+ new->prev = old->prev;
+ old->prev = old;
+
+ /* successor */
+ if (old->next) {
+ old->next->prev = new;
+ new->next = old->next;
+ old->next = NULL;
+ }
+
+finish:
+ /* remove the old one */
+ lyd_free(old);
+ return EXIT_SUCCESS;
+}
+
+
API int
lyd_insert(struct lyd_node *parent, struct lyd_node *node)
{
struct lys_node *sparent;
- struct lyd_node *iter;
+ struct lyd_node *iter, *ins, *next1, *next2;
int invalid = 0, clrdflt = 0;
+ int pos, i;
if (!node || !parent) {
ly_errno = LY_EINVAL;
@@ -2803,39 +2857,87 @@
invalid++;
}
- /* unlink only if it is not a list of siblings without a parent and node is the first sibling */
+ /* unlink only if it is not a list of siblings without a parent and node is not the first sibling */
if (node->parent || node->prev->next) {
lyd_unlink_internal(node, invalid);
}
- if (invalid == 1) {
- /* auto delete nodes from other cases, if any */
- lyv_multicases(node, NULL, parent->child, 1, NULL);
- }
-
- if (!parent->child) {
- /* add as the only child of the parent */
- parent->child = node;
- } else {
- /* add as the last child of the parent */
- parent->child->prev->next = node;
- node->prev = parent->child->prev;
- for (iter = node; iter->next; iter = iter->next);
- parent->child->prev = iter;
- }
-
- LY_TREE_FOR(node, iter) {
- iter->parent = parent;
- if (invalid) {
- lyd_insert_setinvalid(iter);
+ /* process the nodes to insert one by one */
+ LY_TREE_FOR_SAFE(node, next1, ins) {
+ if (invalid == 1) {
+ /* auto delete nodes from other cases, if any;
+ * this is done only if node->parent != parent */
+ iter = parent->child;
+ lyv_multicases(node, NULL, &iter, 1, NULL);
}
- if (!iter->dflt) {
+
+ /* isolate the node to be handled separately */
+ ins->prev = ins;
+ ins->next = NULL;
+
+ iter = NULL;
+ if (!ins->dflt) {
+ /* are we inserting list key? */
+ if (parent->schema->nodetype == LYS_LIST && ins->schema->nodetype == LYS_LEAF &&
+ (pos = lys_is_key((struct lys_node_list *)parent->schema, (struct lys_node_leaf *)ins->schema))) {
+ /* yes, we have a key, get know its position */
+ for (i = 0, iter = parent->child;
+ iter && i < (pos - 1) && iter->schema->nodetype == LYS_LEAF;
+ i++, iter = iter->next);
+ if (iter) {
+ /* insert list's key to the correct position - before the iter */
+ if (parent->child == iter) {
+ parent->child = ins;
+ }
+ if (iter->prev->next) {
+ iter->prev->next = ins;
+ }
+ ins->prev = iter->prev;
+ iter->prev = ins;
+ ins->next = iter;
+ }
+
+ /* try to find previously present default instance to replace */
+ } else if (ins->schema->nodetype == LYS_LEAFLIST) {
+ LY_TREE_FOR_SAFE(parent->child, next2, iter) {
+ if (iter->schema == ins->schema && iter->dflt) {
+ lyd_free(iter);
+ }
+ }
+ } else if (ins->schema->nodetype == LYS_LEAF ||
+ (ins->schema->nodetype == LYS_CONTAINER && !((struct lys_node_container *)ins->schema)->presence)) {
+ LY_TREE_FOR(parent->child, iter) {
+ if (iter->schema == ins->schema && iter->dflt) {
+ /* replace */
+ lyd_replace(iter, ins);
+ break;
+ }
+ }
+ }
+ }
+ if (!iter) {
+ if (!parent->child) {
+ /* add as the only child of the parent */
+ parent->child = ins;
+ } else {
+ /* add as the last child of the parent */
+ parent->child->prev->next = ins;
+ ins->prev = parent->child->prev;
+ parent->child->prev = ins;
+ }
+ }
+ ins->parent = parent;
+
+ if (invalid) {
+ lyd_insert_setinvalid(ins);
+ }
+ if (!ins->dflt) {
clrdflt = 1;
}
}
if (clrdflt) {
- /* remove the flag from parents */
+ /* remove the dflt flag from parents */
for (iter = parent; iter && iter->dflt; iter = iter->parent) {
iter->dflt = 0;
}
@@ -2848,8 +2950,12 @@
lyd_insert_sibling(struct lyd_node *sibling, struct lyd_node *node, int before)
{
struct lys_node *par1, *par2;
- struct lyd_node *iter,*start = NULL;
+ struct lyd_node *iter, *start = NULL, *ins, *next1, *next2, *last;
int invalid = 0;
+ char *str;
+
+ assert(sibling);
+ assert(node);
if (sibling == node) {
return EXIT_SUCCESS;
@@ -2888,58 +2994,95 @@
}
}
- if (invalid == 1) {
- /* auto delete nodes from other cases */
-
- /* find first sibling node */
- if (sibling->parent) {
- start = sibling->parent->child;
- } else {
- for (start = sibling; start->prev->next; start = start->prev);
- }
-
- if (lyv_multicases(node, NULL, start, 1, sibling) == 2) {
- LOGVAL(LYE_SPEC, LY_VLOG_LYD, sibling, "Insert request refers node (%s) that is going to be auto-deleted.",
- ly_errpath());
- return EXIT_FAILURE;
- }
- /* start could be autodeleted, so we cannot use it */
- start = NULL;
- }
-
- if (node->parent || (node->prev != node)) {
+ /* unlink only if it is not a list of siblings without a parent and node is not the first sibling */
+ if (node->parent || node->prev->next) {
lyd_unlink_internal(node, invalid);
}
- node->parent = sibling->parent;
- if (invalid) {
- lyd_insert_setinvalid(node);
+ /* find first sibling node */
+ if (sibling->parent) {
+ start = sibling->parent->child;
+ } else {
+ for (start = sibling; start->prev->next; start = start->prev);
}
+ /* process the nodes one by one to clean the current tree */
+ LY_TREE_FOR_SAFE(node, next1, ins) {
+ ins->parent = sibling->parent;
+ last = ins;
+
+ if (invalid) {
+ lyd_insert_setinvalid(ins);
+ }
+
+ if (invalid == 1) {
+ /* auto delete nodes from other cases */
+ if (lyv_multicases(ins, NULL, &start, 1, sibling) == 2) {
+ LOGVAL(LYE_SPEC, LY_VLOG_LYD, sibling, "Insert request refers node (%s) that is going to be auto-deleted.",
+ ly_errpath());
+ return EXIT_FAILURE;
+ }
+ }
+
+ /* try to find previously present default instance to remove because of
+ * inserting the specified node */
+ if (ins->schema->nodetype == LYS_LEAFLIST) {
+ LY_TREE_FOR_SAFE(start, next2, iter) {
+ if (iter->schema == ins->schema && iter->dflt) {
+ if (iter == sibling) {
+ ly_errno = LY_EINVAL;
+ LOGERR(LY_EINVAL, "Insert request refers node (%s) that is going to be auto-deleted.",
+ str = lyd_path(sibling));
+ free(str);
+ return EXIT_FAILURE;
+ }
+ if (iter == start) {
+ start = next2;
+ }
+ lyd_free(iter);
+ }
+ }
+ } else if (ins->schema->nodetype == LYS_LEAF ||
+ (ins->schema->nodetype == LYS_CONTAINER && !((struct lys_node_container *)ins->schema)->presence)) {
+ LY_TREE_FOR(start, iter) {
+ if (iter->schema == ins->schema && iter->dflt) {
+ if (iter == sibling) {
+ ly_errno = LY_EINVAL;
+ LOGERR(LY_EINVAL, "Insert request refers node (%s) that is going to be auto-deleted.",
+ str = lyd_path(sibling));
+ free(str);
+ return EXIT_FAILURE;
+ }
+ if (iter == start) {
+ start = iter->next;
+ }
+ lyd_free(iter);
+ break;
+ }
+ }
+ }
+ }
+
+ /* insert the (list of) node(s) to the specified position */
if (before) {
if (sibling->prev->next) {
- /* adding into the list */
+ /* adding into a middle */
sibling->prev->next = node;
} else if (sibling->parent) {
/* at the beginning */
sibling->parent->child = node;
}
node->prev = sibling->prev;
- sibling->prev = node;
- node->next = sibling;
- } else {
+ sibling->prev = last;
+ last->next = sibling;
+ } else { /* after */
if (sibling->next) {
/* adding into a middle - fix the prev pointer of the node after inserted nodes */
- node->next = sibling->next;
- sibling->next->prev = node;
+ last->next = sibling->next;
+ sibling->next->prev = last;
} else {
/* at the end - fix the prev pointer of the first node */
- if (sibling->parent) {
- sibling->parent->child->prev = node;
- } else {
- for (start = sibling; start->prev->next; start = start->prev);
- start->prev = node;
- }
+ start->prev = last;
}
sibling->next = node;
node->prev = sibling;
@@ -3394,7 +3537,7 @@
for (parent = node->parent; parent; parent = node->parent) {
if (parent->dflt || parent->schema->nodetype != LYS_CONTAINER ||
((struct lys_node_container *)parent->schema)->presence) {
- /* parent is alreade default and there is nothing to update or
+ /* parent is already default and there is nothing to update or
* it is not a non-presence container -> stop the loop */
break;
}
@@ -3877,7 +4020,7 @@
const struct lys_node *parent;
const struct lys_node_leaf *sleaf = NULL;
struct lys_tpdf *tpdf;
- struct lyd_node *last;
+ struct lyd_node *last, *node;
const char *dflt = NULL;
struct ly_set *s, *r;
unsigned int i;
@@ -3961,7 +4104,8 @@
} else {
parent = s->set.s[i + 1];
}
- if (lyv_multicases(NULL, (struct lys_node *)parent, last->child, 0, NULL)) {
+ node = last->child;
+ if (lyv_multicases(NULL, (struct lys_node *)parent, &node, 0, NULL)) {
/* another case is present */
ly_errno = LY_SUCCESS;
dflt = NULL;
@@ -4716,17 +4860,14 @@
if (!(dummy = lyd_new_dummy(*tree, last_parent, (struct lys_node*)llist, dflt[i], 1))) {
goto error;
}
- if (!dummy->parent && (*tree)) {
- /* connect dummy nodes into the data tree (at the end of top level nodes) */
- if (lyd_insert_after((*tree)->prev, dummy)) {
- goto error;
- }
- }
+
if (!first) {
first = dummy;
- if (!(*tree)) {
- *tree = first;
- }
+ } else if (!dummy->parent) {
+ /* interconnect with the rest of leaf-lists */
+ first->prev->next = dummy;
+ dummy->prev = first->prev;
+ first->prev = dummy;
}
for (current = dummy; ; current = current->child) {
@@ -4758,20 +4899,23 @@
}
}
+ /* insert into the tree */
+ if (first && !first->parent && (*tree)) {
+ /* connect dummy nodes into the data tree (at the end of top level nodes) */
+ if (lyd_insert_after((*tree)->prev, first)) {
+ goto error;
+ }
+ } else if (!(*tree)) {
+ *tree = first;
+ }
+
/* update parent's default flag if needed */
lyd_wd_update_parents(first);
return EXIT_SUCCESS;
error:
- if ((*tree) == first) {
- (*tree) = NULL;
- }
- LY_TREE_FOR_SAFE(first, dummy, current) {
- if (current->schema == (struct lys_node *)llist) {
- lyd_free(current);
- }
- }
+ lyd_free_withsiblings(first);
return EXIT_FAILURE;
}
diff --git a/src/tree_data.h b/src/tree_data.h
index 1904384..edcd020 100644
--- a/src/tree_data.h
+++ b/src/tree_data.h
@@ -726,8 +726,9 @@
* \p 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.
+ * If the node is the first node of a node list (with no parent), all the subsequent nodes are also inserted.
+ * If the key of a list is being inserted, it is placed into a correct position instead of being placed as the last
+ * element.
*
* @param[in] parent Parent node for the \p node being inserted.
* @param[in] node The node being inserted.
diff --git a/src/tree_internal.h b/src/tree_internal.h
index b532538..edc7cce 100644
--- a/src/tree_internal.h
+++ b/src/tree_internal.h
@@ -427,4 +427,10 @@
void lys_submodule_module_data_free(struct lys_submodule *submodule);
+/**
+ * @brief Get know if the \p leaf is a key of the \p list
+ * @return 0 for false, position of the key otherwise
+ */
+int lys_is_key(struct lys_node_list *list, struct lys_node_leaf *leaf);
+
#endif /* LY_TREE_INTERNAL_H_ */
diff --git a/src/tree_schema.c b/src/tree_schema.c
index 83f73eb..8a63062 100644
--- a/src/tree_schema.c
+++ b/src/tree_schema.c
@@ -3195,3 +3195,17 @@
}
}
}
+
+int
+lys_is_key(struct lys_node_list *list, struct lys_node_leaf *leaf)
+{
+ uint8_t i;
+
+ for (i = 0; i < list->keys_size; i++) {
+ if (list->keys[i] == leaf) {
+ return i + 1;
+ }
+ }
+
+ return 0;
+}
diff --git a/src/validation.h b/src/validation.h
index bab2d12..dfa72e9 100644
--- a/src/validation.h
+++ b/src/validation.h
@@ -69,12 +69,13 @@
*
* @param[in] node Data tree node to be checked.
* @param[in] schemanode Alternative to \p node (node is preferred), schema of the (potential) node
- * @param[in] first_sibling The first sibling of the node where the searching will always start.
+ * @param[in,out] first_sibling The first sibling of the node where the searching will always start. It is updated
+ * when the first_sibling is (even repeatedly) autodeleted
* @param[in] autodelete Flag to select if the conflicting nodes are supposed to be removed or reported
* @param[in] nodel Exception for autodelete, if the \p nodel node would be removed, error is reported instead.
* @return EXIT_SUCCESS or EXIT_FAILURE with set ly_errno.
*/
-int lyv_multicases(struct lyd_node *node, struct lys_node *schemanode, struct lyd_node *first_sibling, int autodelete,
+int lyv_multicases(struct lyd_node *node, struct lys_node *schemanode, struct lyd_node **first_sibling, int autodelete,
struct lyd_node *nodel);
#endif /* LY_VALIDATION_H_ */
diff --git a/tests/data/test_keys.c b/tests/data/test_keys.c
index e578f4c..7e7b4af 100644
--- a/tests/data/test_keys.c
+++ b/tests/data/test_keys.c
@@ -157,30 +157,29 @@
{
struct state *st = (*state);
struct lyd_node *node;
- int rc;
st->dt = lyd_new(NULL, ly_ctx_get_module(st->ctx, "keys", NULL), "l");
assert_ptr_not_equal(st->dt, NULL);
+ /* libyang is able to put the keys into a correct order */
node = lyd_new_leaf(st->dt, NULL, "key2", "2");
assert_ptr_not_equal(node, NULL);
node = lyd_new_leaf(st->dt, NULL, "key1", "1");
assert_ptr_not_equal(node, NULL);
- rc = lyd_validate(&(st->dt), LYD_OPT_CONFIG);
- assert_int_not_equal(rc, 0);
+ assert_int_equal(lyd_validate(&(st->dt), LYD_OPT_CONFIG), 0);
- lyd_free(st->dt->child);
+ lyd_free_withsiblings(st->dt->child);
- node = lyd_new_leaf(st->dt, NULL, "value", "a");
- assert_ptr_not_equal(node, NULL);
+ /* libyang is able to put the keys into a correct order */
node = lyd_new_leaf(st->dt, NULL, "key2", "2");
assert_ptr_not_equal(node, NULL);
+ node = lyd_new_leaf(st->dt, NULL, "value", "a");
+ assert_ptr_not_equal(node, NULL);
+ node = lyd_new_leaf(st->dt, NULL, "key1", "1");
+ assert_ptr_not_equal(node, NULL);
- rc = lyd_validate(&(st->dt), LYD_OPT_CONFIG);
- assert_int_not_equal(rc, 0);
- assert_string_equal(ly_errmsg(), "Invalid position of the key element.");
- assert_string_equal(ly_errpath(), "/keys:l[key1='1'][key2='2']/key2");
+ assert_int_equal(lyd_validate(&(st->dt), LYD_OPT_CONFIG), 0);
}
int main(void)