summaryrefslogtreecommitdiffabout
path: root/src
authorSergey Poznyakoff <gray@gnu.org.ua>2011-05-06 08:58:47 (GMT)
committer Sergey Poznyakoff <gray@gnu.org.ua>2011-05-06 10:00:06 (GMT)
commit52c12573a505bf29a0301a1c9553e88c3270713e (patch) (side-by-side diff)
tree642047e5b3de469199b68a76064f756990a3b249 /src
parent8465fa7066d3c922b738346335f801cf9ea2243f (diff)
downloadgrecs-52c12573a505bf29a0301a1c9553e88c3270713e.tar.gz
grecs-52c12573a505bf29a0301a1c9553e88c3270713e.tar.bz2
Rewrite list support to keep doubly-linked lists. Implement tree reduction.
* src/format.c (grecs_format_node) (grecs_format_node_path): Handle grecs_node_root. * src/grecs-gram.y (input production): Create root node. * src/grecs.h (grecs_list_entry)<prev>: New member. (grecs_node_root): New node type. (grecs_node_eq): New proto. (grecs_list_add,grecs_tree_reduce): New protos. * src/list.c: Rewrite as a doubly-linked list. * src/tree.c (grecs_node_bind): Bugfix. (grecs_node_unlink): New function. (_tree_recurse): Allow for removal of the current node. (grecs_node_eq): New function. (grecs_tree_reduce): New function. (grecs_tree_process): Descend into the first subnode at once. * src/lookup.c (node_finder): Handle grecs_node_root. * tests/reduce00.at: New testcase. * tests/reduce01.at: New testcase. * tests/reduce02.at: New testcase. * tests/testsuite.at (GRECS_TEST): New macro. Include reduce0[0-2].at. * tests/gcffmt.c: New option -reduce. * tests/gcfpeek.c: Likewise. * tests/gcfset.c: Likewise.
Diffstat (limited to 'src') (more/less context) (ignore whitespace changes)
-rw-r--r--src/format.c3
-rw-r--r--src/grecs-gram.y4
-rw-r--r--src/grecs.h6
-rw-r--r--src/list.c128
-rw-r--r--src/lookup.c2
-rw-r--r--src/tree.c174
6 files changed, 273 insertions, 44 deletions
diff --git a/src/format.c b/src/format.c
index 6e33521..4d4c126 100644
--- a/src/format.c
+++ b/src/format.c
@@ -197,6 +197,8 @@ grecs_format_node_path(struct grecs_node *node, int flags, FILE *fp)
int delim = flags & 0xff;
if (node->up)
grecs_format_node_path(node->up, flags, fp);
+ if (node->type == grecs_node_root)
+ return;
fputc(delim ? delim : '.', fp);
fprintf(fp, "%s", node->ident);
if (node->type == grecs_node_block &&
@@ -264,6 +266,7 @@ grecs_format_node(struct grecs_node *node, int flags, FILE *fp)
if (!flags)
flags = GRECS_NODE_FLAG_DEFAULT;
switch (node->type) {
+ case grecs_node_root:
case grecs_node_block:
for (node = node->down; node; node = node->next) {
grecs_format_node(node, flags, fp);
diff --git a/src/grecs-gram.y b/src/grecs-gram.y
index c2429a4..f31305e 100644
--- a/src/grecs-gram.y
+++ b/src/grecs-gram.y
@@ -52,7 +52,9 @@ int grecs_default_port = 0;
input : stmtlist
{
- parse_tree = $1.head;
+ parse_tree = grecs_node_create(grecs_node_root,
+ &grecs_current_locus);
+ grecs_node_bind(parse_tree, $1.head, 1);
}
;
diff --git a/src/grecs.h b/src/grecs.h
index b6ac85c..6dc3cda 100644
--- a/src/grecs.h
+++ b/src/grecs.h
@@ -90,7 +90,7 @@ enum grecs_callback_command {
#define GRECS_TYPE_ARRAY 2
struct grecs_list_entry {
- struct grecs_list_entry *next;
+ struct grecs_list_entry *next, *prev;
void *data;
};
@@ -118,6 +118,7 @@ typedef struct grecs_value {
((val)->type == GRECS_TYPE_STRING && (val)->v.string == NULL))
enum grecs_node_type {
+ grecs_node_root,
grecs_node_stmt,
grecs_node_block
};
@@ -204,6 +205,7 @@ struct grecs_node *grecs_node_create(enum grecs_node_type type,
grecs_locus_t *loc);
void grecs_node_bind(struct grecs_node *master, struct grecs_node *node,
int dn);
+int grecs_node_eq(struct grecs_node *a, struct grecs_node *b);
extern grecs_locus_t grecs_current_locus;
@@ -264,6 +266,7 @@ void *grecs_list_index(struct grecs_list *lp, size_t idx);
void *grecs_list_remove_tail(struct grecs_list *lp);
void grecs_list_clear(struct grecs_list *lp);
void grecs_list_free(struct grecs_list *lp);
+void grecs_list_add(struct grecs_list *dst, struct grecs_list *src);
int grecs_vasprintf(char **pbuf, size_t *psize, const char *fmt, va_list ap);
int grecs_asprintf(char **pbuf, size_t *psize, const char *fmt, ...);
@@ -326,5 +329,6 @@ int grecs_tree_process(struct grecs_node *node, struct grecs_keyword *kwd);
int grecs_value_eq(struct grecs_value *a, struct grecs_value *b);
struct grecs_node *grecs_find_node(struct grecs_node *node, const char *path);
struct grecs_node *grecs_node_from_path(const char *path, const char *value);
+int grecs_tree_reduce(struct grecs_node *node, struct grecs_keyword *kwd);
#endif
diff --git a/src/list.c b/src/list.c
index 7d7f934..2bd9797 100644
--- a/src/list.c
+++ b/src/list.c
@@ -37,17 +37,78 @@ grecs_list_size(struct grecs_list *lp)
}
void
+grecs_list_insert_entry(struct grecs_list *lp,
+ struct grecs_list_entry *anchor,
+ struct grecs_list_entry *ent, int before)
+{
+ struct grecs_list_entry *p;
+
+ if (!anchor) {
+ ent->prev = NULL;
+ ent->next = lp->head;
+ if (lp->head)
+ lp->head->prev = ent;
+ else
+ lp->tail = ent;
+ lp->head = ent;
+ lp->count++;
+ return;
+ }
+
+ if (before) {
+ grecs_list_insert_entry(lp, anchor->prev, ent, 0);
+ return;
+ }
+
+ ent->prev = anchor;
+ if (p = anchor->next)
+ p->prev = ent;
+ else
+ lp->tail = ent;
+ ent->next = p;
+ anchor->next = ent;
+ lp->count++;
+}
+
+void
+grecs_list_remove_entry(struct grecs_list *lp, struct grecs_list_entry *ent)
+{
+ struct grecs_list_entry *p;
+ if (p = ent->prev)
+ p->next = ent->next;
+ else
+ lp->head = ent->next;
+ if (p = ent->next)
+ p->prev = ent->prev;
+ else
+ lp->tail = ent->prev;
+ ent->next = ent->prev = NULL;
+ lp->count--;
+}
+
+void
grecs_list_append(struct grecs_list *lp, void *val)
{
struct grecs_list_entry *ep = grecs_malloc(sizeof(*ep));
ep->data = val;
- ep->next = NULL;
- if (lp->tail)
- lp->tail->next = ep;
+ grecs_list_insert_entry(lp, lp->tail, ep, 0);
+}
+
+void
+grecs_list_add(struct grecs_list *dst, struct grecs_list *src)
+{
+ if (!src->head)
+ return;
+
+ src->head->prev = dst->tail;
+ if (dst->tail)
+ dst->tail->next = src->head;
else
- lp->head = ep;
- lp->tail = ep;
- lp->count++;
+ dst->head = src->head;
+ dst->tail = src->tail;
+ dst->count += src->count;
+ src->head = src->tail = NULL;
+ src->count = 0;
}
void
@@ -55,9 +116,7 @@ grecs_list_push(struct grecs_list *lp, void *val)
{
struct grecs_list_entry *ep = grecs_malloc(sizeof(*ep));
ep->data = val;
- ep->next = lp->head;
- lp->head = ep;
- lp->count++;
+ grecs_list_insert_entry(lp, NULL, ep, 0);
}
void *
@@ -67,16 +126,28 @@ grecs_list_pop(struct grecs_list *lp)
struct grecs_list_entry *ep = lp->head;
if (ep) {
data = ep->data;
- lp->head = ep->next;
- if (!lp->head)
- lp->tail = NULL;
- lp->count--;
- free (ep);
+ grecs_list_remove_entry(lp, ep);
+ free(ep);
} else
data = NULL;
return data;
}
+void *
+grecs_list_remove_tail(struct grecs_list *lp)
+{
+ void *data;
+ struct grecs_list_entry *ep;
+
+ if (!lp->tail)
+ return NULL;
+ ep = lp->tail;
+ data = lp->tail->data;
+ grecs_list_remove_entry(lp, ep);
+ free(ep);
+ return data;
+}
+
void
grecs_list_clear(struct grecs_list *lp)
{
@@ -96,8 +167,10 @@ grecs_list_clear(struct grecs_list *lp)
void
grecs_list_free(struct grecs_list *lp)
{
- grecs_list_clear(lp);
- free(lp);
+ if (lp) {
+ grecs_list_clear(lp);
+ free(lp);
+ }
}
static int
@@ -129,26 +202,3 @@ grecs_list_index(struct grecs_list *lp, size_t idx)
return ep ? ep->data : NULL;
}
-void *
-grecs_list_remove_tail(struct grecs_list *lp)
-{
- void *data;
-
- if (!lp->head)
- return NULL;
- data = lp->tail;
- if (lp->head == lp->tail) {
- free(lp->tail);
- lp->head = lp->tail = NULL;
- lp->count = 0;
- } else {
- struct grecs_list_entry *ep;
-
- for (ep = lp->head; ep->next != lp->tail; ep = ep->next)
- ;
- free(lp->tail);
- ep->next = NULL;
- lp->tail = ep;
- }
- return data;
-}
diff --git a/src/lookup.c b/src/lookup.c
index 7795274..b2621da 100644
--- a/src/lookup.c
+++ b/src/lookup.c
@@ -231,7 +231,7 @@ node_finder(enum grecs_tree_recurse_op op, struct grecs_node *node, void *data)
{
struct find_closure *fdptr = data;
- if (op == grecs_tree_recurse_post)
+ if (op == grecs_tree_recurse_post || node->type == grecs_node_root)
return grecs_tree_recurse_ok;
if (strcmp(fdptr->argv[fdptr->tag], node->ident) == 0
diff --git a/src/tree.c b/src/tree.c
index 1a2bba5..6b3d555 100644
--- a/src/tree.c
+++ b/src/tree.c
@@ -57,7 +57,7 @@ grecs_node_bind(struct grecs_node *master, struct grecs_node *node, int dn)
} else {
if (!master->next) {
master->next = node;
- node->prev = NULL;
+ node->prev = master;
} else {
for (np = master->next; np->next; np = np->next)
;
@@ -67,6 +67,21 @@ grecs_node_bind(struct grecs_node *master, struct grecs_node *node, int dn)
node->up = master->up;
}
}
+
+int
+grecs_node_unlink(struct grecs_node *node)
+{
+ if (node->prev)
+ node->prev->next = node->next;
+ else if (node->up)
+ node->up->down = node->next;
+ else
+ return 1;
+ if (node->next)
+ node->next->prev = node->prev;
+ return 0;
+}
+
static enum grecs_tree_recurse_res
@@ -83,7 +98,8 @@ _tree_recurse(struct grecs_node *node, grecs_tree_recursor_t recfun,
break; \
}
- for (; node; node = node->next) {
+ while (node) {
+ struct grecs_node *next = node->next;
if (node->type == grecs_node_stmt) {
res = recfun(grecs_tree_recurse_set, node, data);
CKRES();
@@ -104,6 +120,7 @@ _tree_recurse(struct grecs_node *node, grecs_tree_recursor_t recfun,
break;
}
}
+ node = next;
}
return grecs_tree_recurse_ok;
#undef CKRES
@@ -771,8 +788,161 @@ grecs_tree_process(struct grecs_node *node, struct grecs_keyword *kwd)
config_keywords.kwd = kwd;
clos.cursect = &config_keywords;
clos.sections = grecs_list_create();
+ if (node->type == grecs_node_root)
+ node = node->down;
rc = grecs_tree_recurse(node, nodeproc, &clos);
grecs_list_free(clos.sections);
return rc;
}
+
+int
+grecs_node_eq(struct grecs_node *a, struct grecs_node *b)
+{
+ if (a->type != b->type)
+ return 1;
+ if (a->type == grecs_node_root)
+ return 0;
+ if (strcmp(a->ident, b->ident))
+ return 1;
+ if (a->type == grecs_node_block &&
+ !grecs_value_eq(&a->value, &b->value))
+ return 1;
+ return 0;
+}
+
+static void
+value_to_list(struct grecs_value *val)
+{
+ struct grecs_list *list;
+ int i;
+
+ if (val->type != GRECS_TYPE_LIST)
+ return;
+ list = _grecs_simple_list_create(0);/* FIXME: this relies on
+ grecs_value_dup registering its
+ return in string_list */
+ switch (val->type) {
+ case GRECS_TYPE_STRING:
+ grecs_list_append(list, grecs_value_dup(val));
+ break;
+
+ case GRECS_TYPE_ARRAY:
+ for (i = 0; i < val->v.arg.c; i++)
+ grecs_list_append(list,
+ grecs_value_dup(&val->v.arg.v[i]));
+ }
+ val->type = GRECS_TYPE_LIST;
+ val->v.list = list;
+}
+
+static void
+node_aggregate_stmt(struct grecs_node *dst, struct grecs_node *src, int type)
+{
+ value_to_list(&dst->value);
+ value_to_list(&src->value);
+ grecs_list_add(dst->value.v.list, src->value.v.list);
+}
+
+static void
+node_merge_stmt(struct grecs_node *to_node, struct grecs_node *from_node,
+ struct grecs_keyword *kwp)
+{
+ if (kwp && GRECS_IS_LIST(kwp->type) && (kwp->type & GRECS_AGGR))
+ node_aggregate_stmt(to_node, from_node, kwp->type);
+ else {
+ /*FIXME: grecs_value_free(from_node->value) */
+ from_node->value.type = GRECS_TYPE_STRING;
+ from_node->value.v.string = NULL;
+ }
+}
+
+static void
+node_merge_block(struct grecs_node *to_node, struct grecs_node *from_node,
+ struct grecs_keyword *kwp)
+{
+ struct grecs_node *sp;
+
+ if (!from_node->down)
+ return;
+ for (sp = from_node->down; ; sp = sp->next) {
+ sp->up = to_node;
+ if (!sp->next)
+ break;
+ }
+ sp->next = to_node->down;
+ to_node->down = from_node->down;
+ from_node->down = NULL;
+}
+
+static void
+node_reduce(struct grecs_node *node, struct grecs_keyword *kwp)
+{
+ struct grecs_node *p;
+
+ for (p = node->next; p; p = p->next)
+ if (grecs_node_eq(p, node) == 0)
+ break;
+ if (p) {
+ switch (node->type) {
+ case grecs_node_root:
+ return;
+ case grecs_node_stmt:
+ node_merge_stmt(p, node, kwp);
+ break;
+ case grecs_node_block:
+ node_merge_block(p, node, kwp);
+ break;
+ }
+ grecs_node_unlink(node);
+ grecs_node_free(node);
+ }
+}
+
+static enum grecs_tree_recurse_res
+reduceproc(enum grecs_tree_recurse_op op, struct grecs_node *node, void *data)
+{
+ struct nodeproc_closure *clos = data;
+
+ if (op == grecs_tree_recurse_post) {
+ if (clos->sections)
+ grecs_list_pop(clos->sections);
+ } else {
+ struct grecs_keyword *kwp = NULL;
+ if (clos->cursect) {
+ kwp = find_keyword(clos->cursect, node->ident);
+ if (!kwp) {
+ grecs_error(&node->locus, 0,
+ _("Unknown keyword"));
+ return grecs_tree_recurse_skip;
+ }
+ if (op == grecs_tree_recurse_pre) {
+ grecs_list_push(clos->sections, clos->cursect);
+ clos->cursect = kwp;
+ }
+ }
+ node_reduce(node, kwp);
+ }
+ return grecs_tree_recurse_ok;
+}
+
+int
+grecs_tree_reduce(struct grecs_node *node, struct grecs_keyword *kwd)
+{
+ int rc;
+ struct nodeproc_closure clos;
+ struct grecs_keyword config_keywords;
+
+ config_keywords.kwd = kwd;
+ if (kwd) {
+ clos.cursect = &config_keywords;
+ clos.sections = grecs_list_create();
+ } else {
+ clos.cursect = NULL;
+ clos.sections = NULL;
+ }
+ rc = grecs_tree_recurse(node->down, reduceproc, &clos);
+ grecs_list_free(clos.sections);
+ return rc;
+}
+

Return to:

Send suggestions and report system problems to the System administrator.