xpath OPTIMIZE removing nodes in chunks
diff --git a/src/xpath.c b/src/xpath.c
index 23fae94..16d1ddc 100644
--- a/src/xpath.c
+++ b/src/xpath.c
@@ -956,6 +956,71 @@
}
/**
+ * @brief Remove a node from a set by setting the node value to NULL.
+ *
+ * @param[in] set Set to use.
+ * @param[in] idx Index from @p set of the node to be removed.
+ */
+static void
+set_remove_node_null(struct lyxp_set *set, uint32_t idx)
+{
+ assert(set && (set->type == LYXP_SET_NODE_SET));
+ assert(idx < set->used);
+
+ set_remove_node_hash(set, set->val.nodes[idx].node, set->val.nodes[idx].type);
+ set->val.nodes[idx].node = NULL;
+}
+
+/**
+ * @brief Remove all NULL nodes from a set. Removing last node changes
+ * set into LYXP_SET_EMPTY. Context position aware.
+ *
+ * @param[in] set Set to consolidate.
+ */
+static void
+set_remove_nodes_null(struct lyxp_set *set)
+{
+ uint16_t i, orig_used, end;
+ int32_t start;
+
+ assert(set && (set->type == LYXP_SET_NODE_SET));
+
+ orig_used = set->used;
+ set->used = 0;
+ for (i = 0; i < orig_used;) {
+ start = -1;
+ do {
+ if (set->val.nodes[i].node && (start == -1)) {
+ start = i;
+ } else if ((start > -1) && !set->val.nodes[i].node) {
+ end = i;
+ ++i;
+ break;
+ }
+
+ ++i;
+ if (i == orig_used) {
+ end = i;
+ }
+ } while (i < orig_used);
+
+ if (start > -1) {
+ /* move the whole chunk of valid nodes together */
+ if (set->used != (unsigned)start) {
+ memmove(&set->val.nodes[set->used], &set->val.nodes[start], (end - start) * sizeof *set->val.nodes);
+ }
+ set->used += end - start;
+ }
+ }
+
+ if (!set->used) {
+ set_free_content(set);
+ /* this changes it to LYXP_SET_EMPTY */
+ memset(set, 0, sizeof *set);
+ }
+}
+
+/**
* @brief Check for duplicates in a node set.
*
* @param[in] set Set to check.
@@ -1574,14 +1639,14 @@
while (i < set->used - 1) {
if ((set->val.nodes[i].node == set->val.nodes[i + 1].node)
&& (set->val.nodes[i].type == set->val.nodes[i + 1].type)) {
- set_remove_node(set, i + 1);
- ret = LY_EEXIST;
- } else {
- ++i;
+ set_remove_node_null(set, i + 1);
+ ret = LY_EEXIST;
}
+ ++i;
}
}
+ set_remove_nodes_null(set);
return ret;
}
@@ -6348,7 +6413,7 @@
root = moveto_get_root(set->ctx_node, options, &root_type);
- for (i = 0; i < set->used; ) {
+ for (i = 0; i < set->used; ++i) {
node = set->val.nodes[i].node;
if (set->val.nodes[i].type == LYXP_NODE_ELEM) {
@@ -6362,7 +6427,7 @@
}
} else {
/* root does not have a parent */
- set_remove_node(set, i);
+ set_remove_node_null(set, i);
continue;
}
@@ -6403,13 +6468,13 @@
assert((new_type == LYXP_NODE_ELEM) || ((new_type == root_type) && (new_node == root)));
if (set_dup_node_check(set, new_node, new_type, -1)) {
- set_remove_node(set, i);
+ set_remove_node_null(set, i);
} else {
set_replace_node(set, new_node, 0, new_type, i);
- ++i;
}
}
+ set_remove_nodes_null(set);
assert(!set_sort(set, options) && !set_sorted_dup_node_clean(set));
return LY_SUCCESS;
@@ -6927,7 +6992,7 @@
eval_predicate(struct lyxp_expr *exp, uint16_t *exp_idx, struct lyxp_set *set, int options, int parent_pos_pred)
{
LY_ERR rc;
- uint16_t i, orig_exp, brack2_exp, open_brack;
+ uint16_t i, orig_exp;
uint32_t orig_pos, orig_size, pred_in_ctx;
struct lyxp_set set2;
struct lyd_node *orig_parent;
@@ -6951,17 +7016,6 @@
}
orig_exp = *exp_idx;
-
- /* find the predicate end */
- open_brack = 0;
- for (brack2_exp = orig_exp; open_brack || (exp->tokens[brack2_exp] != LYXP_TOKEN_BRACK2); ++brack2_exp) {
- if (exp->tokens[brack2_exp] == LYXP_TOKEN_BRACK1) {
- ++open_brack;
- } else if (exp->tokens[brack2_exp] == LYXP_TOKEN_BRACK2) {
- --open_brack;
- }
- }
-
orig_pos = 0;
orig_size = set->used;
orig_parent = NULL;
@@ -6999,12 +7053,11 @@
lyxp_set_cast(&set2, LYXP_SET_BOOLEAN, options);
/* predicate satisfied or not? */
- if (set2.val.bool) {
- ++i;
- } else {
- set_remove_node(set, i);
+ if (!set2.val.bool) {
+ set_remove_node_null(set, i);
}
}
+ set_remove_nodes_null(set);
} else if (set->type == LYXP_SET_SCNODE_SET) {
for (i = 0; i < set->used; ++i) {
@@ -7020,16 +7073,6 @@
orig_exp = *exp_idx;
- /* find the predicate end */
- open_brack = 0;
- for (brack2_exp = orig_exp; open_brack || (exp->tokens[brack2_exp] != LYXP_TOKEN_BRACK2); ++brack2_exp) {
- if (exp->tokens[brack2_exp] == LYXP_TOKEN_BRACK1) {
- ++open_brack;
- } else if (exp->tokens[brack2_exp] == LYXP_TOKEN_BRACK2) {
- --open_brack;
- }
- }
-
/* set special in_ctx to all the valid snodes */
pred_in_ctx = set_scnode_new_in_ctx(set);