[augeas-devel] [PATCH 2 of 4] Avoid O(n^2) runtime by appending to lists in constant time
David Lutterkort
dlutter at redhat.com
Fri Aug 8 22:46:24 UTC 2008
2 files changed, 43 insertions(+), 21 deletions(-)
src/get.c | 45 ++++++++++++++++++++++++++++++++-------------
src/put.c | 19 +++++++++++--------
# HG changeset patch
# User David Lutterkort <dlutter at redhat.com>
# Date 1218235423 25200
# Node ID cf27e53b0a9213ddf03e45603617b09418285474
# Parent 30fe26d31d9e9f7bd24539870f47727a8677ddd2
Avoid O(n^2) runtime by appending to lists in constant time
The data structure used to keep track of successive matches of an iterated
lens, a split list, was being appended to by traversing the list for each
new element. Now, we remember the last element on the list and append in
constant time.
The same was true in a few other places: the building of a tree and of
skeletons suffered from the same problem.
Dicts still have that problem - they need to be changed to hash tables to
address this issue.
diff -r 30fe26d31d9e -r cf27e53b0a92 src/get.c
--- a/src/get.c Fri Aug 08 15:38:38 2008 -0700
+++ b/src/get.c Fri Aug 08 15:43:43 2008 -0700
@@ -267,14 +267,17 @@
return strndup(split->start, split->size);
}
-static void split_append(struct split **split,
- const char *text, int start, int end) {
+static struct split *split_append(struct split **split, struct split *tail,
+ const char *text, int start, int end) {
struct split *sp;
- if (ALLOC(sp) >= 0) {
- sp->start = text + start;
- sp->size = end - start;
- list_append(*split, sp);
- }
+
+ if (ALLOC(sp) < 0)
+ return NULL;
+
+ sp->start = text + start;
+ sp->size = end - start;
+ list_tail_cons(*split, tail, sp);
+ return tail;
}
static struct split *next_split(struct state *state) {
@@ -318,16 +321,24 @@
}
int reg = 1;
+ struct split *tail = NULL;
for (int i=0; i < lens->nchildren; i++) {
assert(reg < regs.num_regs);
assert(regs.start[reg] != -1);
- split_append(&split, outer->start, regs.start[reg], regs.end[reg]);
+ tail = split_append(&split, tail,
+ outer->start, regs.start[reg], regs.end[reg]);
+ if (tail == NULL)
+ goto error;
reg += 1 + regexp_nsub(lens->children[i]->ctype);
}
assert(reg < regs.num_regs);
+ done:
free(regs.start);
free(regs.end);
return split;
+ error:
+ list_free(split);
+ goto done;
}
static struct split *split_iter(struct lens *lens, struct split *outer) {
@@ -350,6 +361,7 @@
const int reg = 0;
int pos = 0;
+ struct split *tail = NULL;
while (pos < outer->size) {
count = regexp_match(ctype, outer->start, outer->size, pos, ®s);
if (count == -2) {
@@ -358,12 +370,19 @@
} else if (count == -1) {
break;
}
- split_append(&split, outer->start, regs.start[reg], regs.end[reg]);
+ tail = split_append(&split, tail,
+ outer->start, regs.start[reg], regs.end[reg]);
+ if (tail == NULL)
+ goto error;
pos = regs.end[reg];
}
+ done:
free(regs.start);
free(regs.end);
return split;
+ error:
+ list_free(split);
+ goto done;
}
static int applies(struct lens *lens, struct split *split) {
@@ -586,7 +605,7 @@
static struct tree *get_quant_star(struct lens *lens, struct state *state) {
assert(lens->tag == L_STAR);
- struct tree *tree = NULL;
+ struct tree *tree = NULL, *tail = NULL;
struct split *oldsplit = state->split;
struct split *split = split_iter(lens, state->split);
@@ -594,7 +613,7 @@
while (state->split != NULL) {
struct tree *t = NULL;
t = get_lens(lens->child, state);
- list_append(tree, t);
+ list_tail_cons(tree, tail, t);
next_split(state);
}
if (state->pos != oldsplit->start + oldsplit->size) {
@@ -610,7 +629,7 @@
assert(lens->tag == L_STAR);
struct split *oldsplit = state->split;
struct split *split = split_iter(lens, state->split);
- struct skel *skel = make_skel(lens);
+ struct skel *skel = make_skel(lens), *tail = NULL;
*dict = NULL;
set_split(state, split);
@@ -618,7 +637,7 @@
struct skel *sk;
struct dict *di = NULL;
sk = parse_lens(lens->child, state, &di);
- list_append(skel->skels, sk);
+ list_tail_cons(skel->skels, tail, sk);
dict_append(dict, di);
next_split(state);
}
diff -r 30fe26d31d9e -r cf27e53b0a92 src/put.c
--- a/src/put.c Fri Aug 08 15:38:38 2008 -0700
+++ b/src/put.c Fri Aug 08 15:43:43 2008 -0700
@@ -137,9 +137,9 @@
free(split);
}
-static void split_append(struct split **split,
- struct tree *tree, struct tree *follow,
- char *labels, size_t start, size_t end) {
+static struct split *split_append(struct split **split, struct split *tail,
+ struct tree *tree, struct tree *follow,
+ char *labels, size_t start, size_t end) {
struct split *sp;
CALLOC(sp, 1);
sp->tree = tree;
@@ -147,7 +147,8 @@
sp->labels = labels;
sp->start = start;
sp->end = end;
- list_append(*split, sp);
+ list_tail_cons(*split, tail, sp);
+ return tail;
}
static struct split *next_split(struct state *state) {
@@ -195,6 +196,7 @@
struct tree *cur = outer->tree;
int reg = 1;
+ struct split *tail = NULL;
for (int i=0; i < lens->nchildren; i++) {
assert(reg < regs.num_regs);
assert(regs.start[reg] != -1);
@@ -203,8 +205,8 @@
if (outer->labels[j] == '/')
follow = follow->next;
}
- split_append(&split, cur, follow,
- outer->labels, regs.start[reg], regs.end[reg]);
+ tail = split_append(&split, tail, cur, follow,
+ outer->labels, regs.start[reg], regs.end[reg]);
cur = follow;
reg += 1 + regexp_nsub(lens->children[i]->atype);
}
@@ -236,6 +238,7 @@
struct tree *cur = outer->tree;
const int reg = 0;
int pos = outer->start;
+ struct split *tail = NULL;
while (pos < outer->end) {
count = regexp_match(atype, outer->labels,
outer->end, pos, ®s);
@@ -250,8 +253,8 @@
if (outer->labels[j] == '/')
follow = follow->next;
}
- split_append(&split, cur, follow,
- outer->labels, regs.start[reg], regs.end[reg]);
+ tail = split_append(&split, tail, cur, follow,
+ outer->labels, regs.start[reg], regs.end[reg]);
cur = follow;
pos = regs.end[reg];
}
More information about the augeas-devel
mailing list