data tree CHANGE remove lprev and lnext pointers in list and leaflist instances
save memory in cost of some additional time when going through the data tree.
diff --git a/src/parser_xml.c b/src/parser_xml.c
index 68de54c..72c1e1d 100644
--- a/src/parser_xml.c
+++ b/src/parser_xml.c
@@ -890,6 +890,7 @@
switch (schema->nodetype) {
case LYS_CONTAINER:
+ case LYS_LIST:
result = calloc(1, sizeof *result);
havechildren = 1;
break;
@@ -901,10 +902,6 @@
result = calloc(1, sizeof(struct lyd_node_leaflist));
havechildren = 0;
break;
- case LYS_LIST:
- result = calloc(1, sizeof(struct lyd_node_list));
- havechildren = 1;
- break;
case LYS_ANYXML:
result = calloc(1, sizeof(struct lyd_node_anyxml));
havechildren = 0;
@@ -930,36 +927,11 @@
result->schema = schema;
/* type specific processing */
- if (schema->nodetype == LYS_LIST) {
- /* pointers to next and previous instances of the same list */
- for (diter = result->prev; diter != result; diter = diter->prev) {
- if (diter->schema == result->schema) {
- /* instances of the same list */
- ((struct lyd_node_list *)diter)->lnext = (struct lyd_node_list *)result;
- ((struct lyd_node_list *)result)->lprev = (struct lyd_node_list *)diter;
- break;
- }
- }
- } else if (schema->nodetype == LYS_LEAF) {
+ if (schema->nodetype & (LYS_LEAF | LYS_LEAFLIST)) {
/* type detection and assigning the value */
if (xml_get_value(result, xml, options, unres)) {
goto error;
}
- } else if (schema->nodetype == LYS_LEAFLIST) {
- /* type detection and assigning the value */
- if (xml_get_value(result, xml, options, unres)) {
- goto error;
- }
-
- /* pointers to next and previous instances of the same leaflist */
- for (diter = result->prev; diter != result; diter = diter->prev) {
- if (diter->schema == result->schema) {
- /* instances of the same list */
- ((struct lyd_node_leaflist *)diter)->lnext = (struct lyd_node_leaflist *)result;
- ((struct lyd_node_leaflist *)result)->lprev = (struct lyd_node_leaflist *)diter;
- break;
- }
- }
} else if (schema->nodetype == LYS_ANYXML && !(options & LYD_OPT_FILTER)) {
prev_xml = xml->prev;
((struct lyd_node_anyxml *)result)->value = xml;
diff --git a/src/printer_json.c b/src/printer_json.c
index f597bbb..6e2b4c1 100644
--- a/src/printer_json.c
+++ b/src/printer_json.c
@@ -34,7 +34,7 @@
#define INDENT ""
#define LEVEL (level*2)
-void json_print_node(FILE *f, int level, struct lyd_node *node);
+void json_print_nodes(FILE *f, int level, struct lyd_node *root);
/* 0 - same, 1 - different */
static int
@@ -122,9 +122,6 @@
fprintf(f, "\"(!error!)\"");
}
- if (!onlyvalue) {
- fprintf(f, "%s\n", lyd_is_last(node) ? "" : ",");
- }
return;
}
@@ -132,7 +129,6 @@
json_print_container(FILE *f, int level, struct lyd_node *node)
{
const char *schema;
- struct lyd_node *child;
if (!node->parent || nscmp(node, node->parent)) {
/* print "namespace" */
@@ -146,37 +142,15 @@
} else {
fprintf(f, "%*s\"%s\": {\n", LEVEL, INDENT, node->schema->name);
}
- LY_TREE_FOR(node->child, child) {
- json_print_node(f, level + 1, child);
- }
- fprintf(f, "%*s}%s\n", LEVEL, INDENT, lyd_is_last(node) ? "" : ",");
-}
-
-static void
-json_print_list_internal(FILE *f, int level, struct lyd_node_list *list)
-{
- struct lyd_node *child;
-
- fprintf(f, "%*s{\n", LEVEL, INDENT);
-
- LY_TREE_FOR(list->child, child) {
- json_print_node(f, level + 1, child);
- }
-
- fprintf(f, "%*s}%s\n", LEVEL, INDENT, (list->lnext ? "," : ""));
+ json_print_nodes(f, level + 1, node->child);
+ fprintf(f, "%*s}", LEVEL, INDENT);
}
static void
json_print_leaf_list(FILE *f, int level, struct lyd_node *node, int is_list)
{
const char *schema;
- struct lyd_node_list *list = (struct lyd_node_list *)node;
- struct lyd_node_leaflist *llist = (struct lyd_node_leaflist *)node;
-
- if ((is_list && list->lprev) || (!is_list && llist->lprev)) {
- /* this list is already printed */
- return;
- }
+ struct lyd_node *list = node;
if (!node->parent || nscmp(node, node->parent)) {
/* print "namespace" */
@@ -194,70 +168,107 @@
if (!is_list) {
++level;
}
- while ((is_list && list) || (!is_list && llist)) {
+
+ while (list) {
if (is_list) {
- json_print_list_internal(f, level + 1, list);
- list = list->lnext;
+ /* list print */
+ ++level;
+ fprintf(f, "%*s{\n", LEVEL, INDENT);
+ json_print_nodes(f, level + 1, list->child);
+ fprintf(f, "%*s}", LEVEL, INDENT);
+ --level;
} else {
+ /* leaf-list print */
fprintf(f, "%*s", LEVEL, INDENT);
- json_print_leaf(f, level, (struct lyd_node *)llist, 1);
- fprintf(f, "%s\n", (llist->lnext ? "," : ""));
- llist = llist->lnext;
+ json_print_leaf(f, level, list, 1);
+ }
+ for (list = list->next; list && list->schema != node->schema; list = list->next);
+ if (list) {
+ fprintf(f, ",\n");
}
}
+
if (!is_list) {
--level;
}
- fprintf(f, "%*s]%s\n", LEVEL, INDENT, lyd_is_last(node) ? "" : ",");
+ fprintf(f, "\n%*s]", LEVEL, INDENT);
}
static void
json_print_anyxml(FILE *f, int level, struct lyd_node *node)
{
- struct lyd_node_anyxml *axml = (struct lyd_node_anyxml *)node;
-
- fprintf(f, "%*s\"%s\": [null]%s\n", LEVEL, INDENT, axml->value->name, lyd_is_last(node) ? "" : ",");
+ fprintf(f, "%*s\"%s\": [null]", LEVEL, INDENT, node->schema->name);
}
void
-json_print_node(FILE *f, int level, struct lyd_node *node)
+json_print_nodes(FILE *f, int level, struct lyd_node *root)
{
- switch (node->schema->nodetype) {
- case LYS_CONTAINER:
- json_print_container(f, level, node);
- break;
- case LYS_LEAF:
- json_print_leaf(f, level, node, 0);
- break;
- case LYS_LEAFLIST:
- json_print_leaf_list(f, level, node, 0);
- break;
- case LYS_LIST:
- json_print_leaf_list(f, level, node, 1);
- break;
- case LYS_ANYXML:
- json_print_anyxml(f, level, node);
- break;
- default:
- LOGINT;
- break;
+ struct lyd_node *node, *iter;
+
+ LY_TREE_FOR(root, node) {
+ switch (node->schema->nodetype) {
+ case LYS_CONTAINER:
+ if (node->prev->next) {
+ /* print the previous comma */
+ fprintf(f, ",\n");
+ }
+ json_print_container(f, level, node);
+ break;
+ case LYS_LEAF:
+ if (node->prev->next) {
+ /* print the previous comma */
+ fprintf(f, ",\n");
+ }
+ json_print_leaf(f, level, node, 0);
+ break;
+ case LYS_LEAFLIST:
+ case LYS_LIST:
+ /* is it already printed? */
+ for (iter = node; iter->prev->next; iter = iter->prev) {
+ if (iter == node) {
+ continue;
+ }
+ if (iter->schema == node->schema) {
+ /* the list has alread some previous instance and therefore it is already printed */
+ break;
+ }
+ }
+ if (!iter->prev->next) {
+ if (node->prev->next) {
+ /* print the previous comma */
+ fprintf(f, ",\n");
+ }
+
+ /* print the list/leaflist */
+ json_print_leaf_list(f, level, node, node->schema->nodetype == LYS_LIST ? 1 : 0);
+ }
+ break;
+ case LYS_ANYXML:
+ if (node->prev->next) {
+ /* print the previous comma */
+ fprintf(f, ",\n");
+ }
+ json_print_anyxml(f, level, node);
+ break;
+ default:
+ LOGINT;
+ break;
+ }
}
+ fprintf(f, "\n");
}
API int
json_print_data(FILE *f, struct lyd_node *root)
{
int level = 0;
- struct lyd_node *node;
/* start */
fprintf(f, "{\n");
/* content */
- LY_TREE_FOR(root, node) {
- json_print_node(f, level + 1, node);
- }
+ json_print_nodes(f, level + 1, root);
/* end */
fprintf(f, "}\n");
diff --git a/src/printer_xml.c b/src/printer_xml.c
index 3ac09dd..99d5db5 100644
--- a/src/printer_xml.c
+++ b/src/printer_xml.c
@@ -229,39 +229,25 @@
}
static void
-xml_print_leaf_list(FILE *f, int level, struct lyd_node *node, int is_list)
+xml_print_list(FILE *f, int level, struct lyd_node *node, int is_list)
{
struct lyd_node *child;
- struct lyd_node_list *list = (struct lyd_node_list *)node;
- struct lyd_node_leaflist *llist = (struct lyd_node_leaflist *)node;
- if ((is_list && list->lprev) || (!is_list && llist->lprev)) {
- /* this list is already printed */
- return;
- }
-
- /* leaf-list print */
- if (!is_list) {
- while (llist) {
- xml_print_leaf(f, level, (struct lyd_node *)llist);
- llist = llist->lnext;
- }
- return;
- }
-
- /* list print */
- while (list) {
+ if (is_list) {
+ /* list print */
fprintf(f, "%*s<%s", LEVEL, INDENT, node->schema->name);
xml_print_attrs(f, node);
fprintf(f, ">\n");
- LY_TREE_FOR(list->child, child) {
+ LY_TREE_FOR(node->child, child) {
xml_print_node(f, level + 1, child);
}
fprintf(f, "%*s</%s>\n", LEVEL, INDENT, node->schema->name);
- list = list->lnext;
+ } else {
+ /* leaf-list print */
+ xml_print_leaf(f, level, node);
}
}
@@ -301,10 +287,10 @@
xml_print_leaf(f, level, node);
break;
case LYS_LEAFLIST:
- xml_print_leaf_list(f, level, node, 0);
+ xml_print_list(f, level, node, 0);
break;
case LYS_LIST:
- xml_print_leaf_list(f, level, node, 1);
+ xml_print_list(f, level, node, 1);
break;
case LYS_ANYXML:
xml_print_anyxml(f, level, node);
diff --git a/src/tree.c b/src/tree.c
index 90af47a..11902b2 100644
--- a/src/tree.c
+++ b/src/tree.c
@@ -2636,23 +2636,6 @@
return EXIT_FAILURE;
}
- /* unlink from the lists list */
- if (node->schema->nodetype == LYS_LIST) {
- if (((struct lyd_node_list *)node)->lprev) {
- ((struct lyd_node_list *)node)->lprev->lnext = ((struct lyd_node_list *)node)->lnext;
- }
- if (((struct lyd_node_list *)node)->lnext) {
- ((struct lyd_node_list *)node)->lnext->lprev = ((struct lyd_node_list *)node)->lprev;
- }
- } else if (node->schema->nodetype == LYS_LEAFLIST) {
- if (((struct lyd_node_leaflist *)node)->lprev) {
- ((struct lyd_node_leaflist *)node)->lprev->lnext = ((struct lyd_node_leaflist *)node)->lnext;
- }
- if (((struct lyd_node_leaflist *)node)->lnext) {
- ((struct lyd_node_leaflist *)node)->lnext->lprev = ((struct lyd_node_leaflist *)node)->lprev;
- }
- }
-
/* unlink from siblings */
if (node->prev->next) {
node->prev->next = node->next;
@@ -2822,34 +2805,6 @@
}
}
-API int
-lyd_is_last(struct lyd_node *node)
-{
- struct lyd_node *n;
-
- if (!node->next) {
- return 1;
- }
-
- for (n = node->next; n; n = n->next) {
- switch (n->schema->nodetype) {
- case LYS_LIST:
- if (!((struct lyd_node_list *)n)->lprev) {
- return 0;
- }
- break;
- case LYS_LEAFLIST:
- if (!((struct lyd_node_leaflist *)n)->lprev) {
- return 0;
- }
- break;
- default:
- return 0;
- }
- }
- return 1;
-}
-
API struct lyd_set *
lyd_set_new(void)
{
diff --git a/src/tree.h b/src/tree.h
index 0f523aa..ce86c99 100644
--- a/src/tree.h
+++ b/src/tree.h
@@ -1366,7 +1366,7 @@
} lyd_val;
/**
- * @brief Generic structure for a data node, directly applicable to the data nodes defined as #LYS_CONTAINER
+ * @brief Generic structure for a data node, directly applicable to the data nodes defined as #LYS_CONTAINER, #LYS_LIST
* and #LYS_CHOICE.
*
* Completely fits to containers and choices and is compatible (can be used interchangeably except the #child member)
@@ -1395,35 +1395,6 @@
};
/**
- * @brief Structure for data nodes defined as #LYS_LIST.
- *
- * Extension for ::lyd_node structure - adds #lprev and #lnext members to simplify going through the instance nodes
- * of a list. The first six members (#schema, #attr, #next, #prev, #parent and #child) are compatible with the
- * ::lyd_node's members.
- *
- * To traverse through all the child elements or attributes, use #LY_TREE_FOR or #LY_TREE_FOR_SAFE macro.
- */
-struct lyd_node_list {
- struct lys_node *schema; /**< pointer to the schema definition of this node which is ::lys_node_list
- structure */
-
- struct lyd_attr *attr; /**< pointer to the list of attributes of this node */
- struct lyd_node *next; /**< pointer to the next sibling node (NULL if there is no one) */
- struct lyd_node *prev; /**< pointer to the previous sibling node \note Note that this pointer is
- never NULL. If there is no sibling node, pointer points to the node
- itself. In case of the first node, this pointer points to the last
- node in the list. */
- struct lyd_node *parent; /**< pointer to the parent node, NULL in case of root node */
- struct lyd_node *child; /**< pointer to the first child node */
-
- /* list's specific members */
- struct lyd_node_list* lprev; /**< pointer to the previous instance node of the same list,
- NULL in case of the first instance of the list */
- struct lyd_node_list* lnext; /**< pointer to the next instance node of the same list,
- NULL in case of the last instance of the list */
-};
-
-/**
* @brief Structure for data nodes defined as #LYS_LEAF.
*
* Extension for ::lyd_node structure - replaces the ::lyd_node#child member by three new members (#value, #value_str
@@ -1456,7 +1427,7 @@
* @brief Structure for data nodes defined as #LYS_LEAF.
*
* Extension for ::lyd_node structure. It combines ::lyd_node_leaf and :lyd_node_list by replacing the
- * ::lyd_node#child member by five new members (#value, #value_str, #value_type, #lprev and #lnext) to provide
+ * ::lyd_node#child member by five new members (#value, #value_str and #value_type) to provide
* information about the value and other leaf-list's instances. The first five members (#schema, #attr, #next,
* #prev and #parent) are compatible with the ::lyd_node's members.
*
@@ -1480,11 +1451,6 @@
lyd_val value; /**< node's value representation */
const char *value_str; /**< string representation of value (for comparison, printing,...) */
LY_DATA_TYPE value_type; /**< type of the value in the node, mainly for union to avoid repeating of type detection */
-
- struct lyd_node_leaflist* lprev; /**< pointer to the previous instance node of the same leaf-list,
- NULL in case of the first instance of the leaf-list */
- struct lyd_node_leaflist* lnext; /**< pointer to the next instance node of the same leaf-list,
- NULL in case of the last instance of the leaf-list */
};
/**
@@ -1606,21 +1572,6 @@
int lyd_move_after(struct lyd_node *sibling, struct lyd_node *node);
/**
- * @brief Test if the given node is last. Note, that this can be simply checked
- * from the node's next member, but this function differs from this how a
- * list's and leaf-list's instances are considered. If the node is followed
- * only by instances of lists that have their first instance before the given
- * node (or the node itself), this function will mark the node as last even the node's ::lyd_node#next is not empty.
- * This is useful especially when you traverse all siblings and process the
- * list's or leaf-list's instances in once.
- *
- * @param[in] node The data node to be checked.
- * @return 0 if the node has a successor, 1 if the node is last in sense as
- * described above.
- */
-int lyd_is_last(struct lyd_node *node);
-
-/**
* @brief Unlink the specified data subtree.
*
* Note, that the node's connection with the schema tree is kept. Therefore, in case of
diff --git a/src/validation.c b/src/validation.c
index dce0cdf..b964800 100644
--- a/src/validation.c
+++ b/src/validation.c
@@ -27,7 +27,7 @@
#include "common.h"
static struct lys_node_leaf *
-lyv_keys_present(struct lyd_node_list *list)
+lyv_keys_present(struct lyd_node *list)
{
struct lyd_node *aux;
struct lys_node_list *schema;
@@ -308,7 +308,7 @@
/* check presence of all keys in case of list */
if (schema->nodetype == LYS_LIST && !(options & LYD_OPT_FILTER)) {
- siter = (struct lys_node *)lyv_keys_present((struct lyd_node_list *)node);
+ siter = (struct lys_node *)lyv_keys_present(node);
if (siter) {
/* key not found in the data */
LOGVAL(LYE_MISSELEM, line, siter->name, schema->name);
@@ -447,57 +447,25 @@
}
}
}
- } else if (schema->nodetype == LYS_LEAFLIST) {
- /* uniqueness of leaf-list instances */
+ } else if (schema->nodetype & (LYS_LIST | LYS_LEAFLIST)) {
+ /* uniqueness of list/leaflist instances */
- /* get the first leaf-list instance sibling */
- for (start = node;
- ((struct lyd_node_leaflist *)start)->lprev;
- start = (struct lyd_node *)((struct lyd_node_leaflist *)start)->lprev);
-
- /* check uniqueness of the leaf-list instances (compare values) */
- for (diter = start; diter; diter = (struct lyd_node *)((struct lyd_node_leaflist *)diter)->lnext) {
- if (diter == node) {
- continue;
- }
-
- if (!lyd_compare(diter, node, 0)) {
- if (options & LYD_OPT_FILTER) {
- /* optimize filter and do not duplicate the same selection node,
- * so this is not actually error, but the data are silently removed */
- /* failure is returned but no ly_errno is set */
- return EXIT_FAILURE;
- } else {
- LOGVAL(LYE_DUPLEAFLIST, line, schema->name, ((struct lyd_node_leaflist *)node)->value_str);
- return EXIT_FAILURE;
- }
- } else if (options & LYD_OPT_FILTER) {
- /* optimize filter if needed: if one of them is a selection node and the other is
- * content match node, keep only the content match node since it also works as
- * selection node */
- if (!((struct lyd_node_leaflist *)diter)->value_str) {
- /* the other instance is selection node, keep the new one whatever it is */
- lyd_free(diter);
- break;
- } else if (!((struct lyd_node_leaflist *)node)->value_str) {
- /* the new instance is selection node, keep the previous instance which is
- * content match node */
- /* failure is returned but no ly_errno is set */
- return EXIT_FAILURE;
+ /* get the first list/leaflist instance sibling */
+ if (node->parent) {
+ start = node->parent->child;
+ } else {
+ start = NULL;
+ for (diter = node; diter->prev->next; diter = diter->prev) {
+ if (diter->schema == node->schema) {
+ /* the same list instance */
+ start = diter;
}
}
}
- } else if (schema->nodetype == LYS_LIST) {
- /* uniqueness of list instances */
- /* get the first list instance sibling */
- for (start = node;
- ((struct lyd_node_list *)start)->lprev;
- start = (struct lyd_node *)((struct lyd_node_list *)start)->lprev);
-
- /* check uniqueness of the list instances */
- for (diter = start; diter; diter = (struct lyd_node *)((struct lyd_node_list *)diter)->lnext) {
- if (diter == node) {
+ /* check uniqueness of the list/leaflist instances (compare values) */
+ for (diter = start; diter; diter = diter->next) {
+ if (diter->schema != node->schema || diter == node) {
continue;
}
@@ -513,13 +481,25 @@
/* not the error, just return no data */
/* failure is returned but no ly_errno is set */
return EXIT_FAILURE;
+ } else if (node->schema->nodetype == LYS_LEAFLIST) {
+ /* in contrast to lists, leaflists can be still safely optimized if one of them
+ * is selection node. In that case wee need to keep the other node, which is content
+ * match node and it somehow limit the data to be filtered.
+ */
+ if (!((struct lyd_node_leaflist *)diter)->value_str) {
+ /* the other instance is selection node, keep the new one whatever it is */
+ lyd_free(diter);
+ break;
+ } else if (!((struct lyd_node_leaflist *)node)->value_str) {
+ /* the new instance is selection node, keep the previous instance which is
+ * content match node */
+ /* failure is returned but no ly_errno is set */
+ return EXIT_FAILURE;
+ }
}
- } else {
- /* compare keys and unique combinations */
- if (!lyd_compare(diter, node, 1)) {
- LOGVAL(LYE_DUPLIST, line, schema->name);
- return EXIT_FAILURE;
- }
+ } else if (!lyd_compare(diter, node, 1)) { /* comparing keys and unique combinations */
+ LOGVAL(LYE_DUPLIST, line, schema->name);
+ return EXIT_FAILURE;
}
}
}
diff --git a/src/yang_library.c b/src/yang_library.c
index 74d3458..4209252 100644
--- a/src/yang_library.c
+++ b/src/yang_library.c
@@ -148,7 +148,7 @@
int i, j, k;
struct lys_module *target_module;
struct lyd_node *dnode;
- struct lyd_node_list *ret = NULL, *dlist, *dlast;
+ struct lyd_node *ret = NULL, *dlist, *dlast;
struct lys_node *deviation_child;
for (i = 0; i < mod_count; ++i) {
@@ -260,7 +260,7 @@
int i;
struct lys_node *submodule_node, *submodule_child;
struct lyd_node *ret = NULL, *dnode;
- struct lyd_node_list *dlist = NULL;
+ struct lyd_node *dlist = NULL;
ret = calloc(1, sizeof *ret);
ret->prev = ret;
@@ -324,7 +324,7 @@
struct lys_module *mod;
struct lys_node *modules_child, *module_child;
struct lyd_node *root, *dnode;
- struct lyd_node_list *dlist = NULL;
+ struct lyd_node *dlist = NULL;
mod = ly_ctx_get_module(ctx, "ietf-yang-library", NULL);
if (!mod) {