/*
* pathx.c: handling path expressions
*
- * Copyright (C) 2007-2011 David Lutterkort
+ * Copyright (C) 2007-2015 David Lutterkort
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
enum type tag;
union {
struct nodeset *nodeset; /* T_NODESET */
- int number; /* T_NUMBER */
+ int64_t number; /* T_NUMBER */
char *string; /* T_STRING */
bool boolval; /* T_BOOLEAN */
struct regexp *regexp; /* T_REGEXP */
return result;
}
+/* Add NODE to NS if it is not in NS yet. This relies on the flag
+ * NODE->ADDED and care must be taken that NS_CLEAR_ADDED is called on NS
+ * as soon as we are done adding nodes to it.
+ */
static void ns_add(struct nodeset *ns, struct tree *node,
struct state *state) {
- for (int i=0; i < ns->used; i++)
- if (ns->nodes[i] == node)
- return;
+ if (node->added)
+ return;
if (ns->used >= ns->size) {
size_t size = 2 * ns->size;
if (size < 10) size = 10;
ns->size = size;
}
ns->nodes[ns->used] = node;
+ node->added = 1;
ns->used += 1;
}
+static void ns_clear_added(struct nodeset *ns) {
+ for (int i=0; i < ns->used; i++)
+ ns->nodes[i]->added = 0;
+}
+
static struct nodeset *
clone_nodeset(struct nodeset *ns, struct state *state)
{
RET_ON_ERROR;
for (int i=0; i < r->nodeset->used; i++) {
ns_add(res, r->nodeset->nodes[i], state);
- RET_ON_ERROR;
+ if (HAS_ERROR(state))
+ goto error;
}
state->value_pool[vind].nodeset = res;
push_value(vind, state);
+ error:
+ ns_clear_added(res);
}
static void eval_concat_string(struct state *state) {
}
}
-static void ns_remove(struct nodeset *ns, int ind) {
- memmove(ns->nodes + ind, ns->nodes + ind+1,
- sizeof(ns->nodes[0]) * (ns->used - (ind+1)));
- ns->used -= 1;
+/* Remove COUNT successive entries from NS. The first entry to remove is at
+ IND */
+static void ns_remove(struct nodeset *ns, int ind, int count) {
+ if (count < 1)
+ return;
+ memmove(ns->nodes + ind, ns->nodes + ind+count,
+ sizeof(ns->nodes[0]) * (ns->used - (ind+count)));
+ ns->used -= count;
}
/*
uint old_ctx_pos = state->ctx_pos;
for (int p=0; p < predicates->nexpr; p++) {
+ int first_bad = -1; /* The index of the first non-matching node */
state->ctx_len = ns->used;
state->ctx_pos = 1;
for (int i=0; i < ns->used; state->ctx_pos++) {
state->ctx = ns->nodes[i];
bool match = eval_pred(predicates->exprs[p], state);
RET_ON_ERROR;
+ /* We remove non-matching nodes from NS in batches; this logic
+ * makes sure that we only call ns_remove at the end of a run
+ * of non-matching nodes
+ */
if (match) {
- i+=1;
+ if (first_bad >= 0) {
+ ns_remove(ns, first_bad, i - first_bad);
+ i = first_bad + 1;
+ } else {
+ i += 1;
+ }
+ first_bad = -1;
} else {
- ns_remove(ns, i);
+ if (first_bad == -1)
+ first_bad = i;
+ i += 1;
}
}
+ if (first_bad >= 0) {
+ ns_remove(ns, first_bad, ns->used - first_bad);
+ }
}
state->ctx = old_ctx;
state->ctx_len = old_ctx_len;
}
+/* Return true if PRED is solely the predicate '[n]' as in 'foo[17]' */
+static bool position_pred(struct pred *pred) {
+ return pred != NULL &&
+ pred->nexpr == 1 &&
+ pred->exprs[0]->tag == E_VALUE &&
+ pred->exprs[0]->type == T_NUMBER;
+}
+
+/* Return the tree node at the position implied by STEP->PREDICATES. It is
+ assumed and required that STEP->PREDICATES is actually a
+ POSITION_PRED.
+
+ This method hand-optimizes the important case of a path expression like
+ 'service[42]'
+*/
+static struct tree *position_filter(struct nodeset *ns,
+ struct step *step,
+ struct state *state) {
+ int value_ind = step->predicates->exprs[0]->value_ind;
+ int number = state->value_pool[value_ind].number;
+
+ int pos = 1;
+ for (int i=0; i < ns->used; i++) {
+ for (struct tree *node = step_first(step, ns->nodes[i]);
+ node != NULL;
+ node = step_next(step, ns->nodes[i], node), pos++) {
+ if (pos == number)
+ return node;
+ }
+ }
+
+ return NULL;
+}
+
/* Return an array of nodesets, one for each step in the locpath.
*
* On return, (*NS)[0] will contain state->ctx, and (*NS)[*MAXNS] will
struct tree *root_tree;
root_tree = step_root(first_step, state->ctx, state->root_ctx);
ns_add((*ns)[0], root_tree, state);
+ ns_clear_added((*ns)[0]);
} else {
for (int i=0; i < root->used; i++)
ns_add((*ns)[0], root->nodes[i], state);
+ ns_clear_added((*ns)[0]);
}
if (HAS_ERROR(state))
list_for_each(step, lp->steps) {
struct nodeset *work = (*ns)[cur_ns];
struct nodeset *next = (*ns)[cur_ns + 1];
- for (int i=0; i < work->used; i++) {
- for (struct tree *node = step_first(step, work->nodes[i]);
- node != NULL;
- node = step_next(step, work->nodes[i], node))
+ if (position_pred(step->predicates)) {
+ struct tree *node = position_filter(work, step, state);
+ if (node) {
ns_add(next, node, state);
+ ns_clear_added(next);
+ }
+ } else {
+ for (int i=0; i < work->used; i++) {
+ for (struct tree *node = step_first(step, work->nodes[i]);
+ node != NULL;
+ node = step_next(step, work->nodes[i], node)) {
+ ns_add(next, node, state);
+ }
+ }
+ ns_clear_added(next);
+ ns_filter(next, step->predicates, state);
+ if (HAS_ERROR(state))
+ goto error;
}
- ns_filter(next, step->predicates, state);
- if (HAS_ERROR(state))
- goto error;
cur_ns += 1;
}
*************************************************************************/
static bool step_matches(struct step *step, struct tree *tree) {
- return (step->name == NULL || streqx(step->name, tree->label));
+ if (step->name == NULL) {
+ return step->axis == ROOT || tree->label != NULL;
+ } else {
+ return streqx(step->name, tree->label);
+ }
}
static struct tree *tree_prev(struct tree *pos) {
while (t != t->parent && t != tree)
t = t->parent;
if (t == tree)
- ns_remove(ns, i);
+ ns_remove(ns, i, 1);
else
i += 1;
}
projects / platform / upstream / augeas.git / blobdiff