diff options
author | Sergey Poznyakoff <gray@gnu.org.ua> | 2011-05-06 13:57:43 +0300 |
---|---|---|
committer | Sergey Poznyakoff <gray@gnu.org.ua> | 2011-05-06 13:57:43 +0300 |
commit | 352b268186931579ae8dcc6a19aaaa89547555f5 (patch) | |
tree | 6b8797f63ee7ca085526ec97c392c5f52d856109 | |
parent | 52c12573a505bf29a0301a1c9553e88c3270713e (diff) | |
download | grecs-352b268186931579ae8dcc6a19aaaa89547555f5.tar.gz grecs-352b268186931579ae8dcc6a19aaaa89547555f5.tar.bz2 |
Implement tree sorting.
* src/sort.c: New file.
* src/Make.am: Add sort.c.
* tests/gcffmt.c: New option -sort.
* src/grecs-lex.l (ID): Allow for single-character identifiers.
-rw-r--r-- | src/Make.am | 1 | ||||
-rw-r--r-- | src/grecs-lex.l | 2 | ||||
-rw-r--r-- | src/grecs.h | 4 | ||||
-rw-r--r-- | src/sort.c | 132 | ||||
-rw-r--r-- | tests/gcffmt.c | 14 |
5 files changed, 151 insertions, 2 deletions
diff --git a/src/Make.am b/src/Make.am index fb3b80b..531e2ef 100644 --- a/src/Make.am +++ b/src/Make.am @@ -23,6 +23,7 @@ GRECS_SRC = \ lookup.c\ mem.c\ preproc.c\ + sort.c\ symtab.c\ text.c\ tree.c\ diff --git a/src/grecs-lex.l b/src/grecs-lex.l index 9c01e0d..97571e6 100644 --- a/src/grecs-lex.l +++ b/src/grecs-lex.l @@ -77,7 +77,7 @@ static void parse_line_cpp(char *text, grecs_locus_t *ploc, size_t *pxlines); %x COMMENT ML STR WS [ \t\f][ \t\f]* -ID [a-zA-Z_][a-zA-Z_0-9-]+ +ID [a-zA-Z_][a-zA-Z_0-9-]* P [1-9][0-9]* %% diff --git a/src/grecs.h b/src/grecs.h index 6dc3cda..41f88d9 100644 --- a/src/grecs.h +++ b/src/grecs.h @@ -331,4 +331,8 @@ 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); +void grecs_tree_sort(struct grecs_node *node, + int (*compare)(struct grecs_node const *, + struct grecs_node const *)); + #endif diff --git a/src/sort.c b/src/sort.c new file mode 100644 index 0000000..d793a3e --- /dev/null +++ b/src/sort.c @@ -0,0 +1,132 @@ +/* grecs - Gray's Extensible Configuration System + Copyright (C) 2007-2011 Sergey Poznyakoff + + Grecs is free software; you can redistribute it and/or modify it + under the terms of the GNU General Public License as published by the + Free Software Foundation; either version 3 of the License, or (at your + option) any later version. + + Grecs is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License along + with Grecs. If not, see <http://www.gnu.org/licenses/>. */ + +#ifdef HAVE_CONFIG_H +# include <config.h> +#endif +#include <stdlib.h> +#include "grecs.h" + +struct node_list { + struct grecs_node *head, *tail; +}; + +static void +node_list_init(struct node_list *list, struct grecs_node *node) +{ + if (node) { + list->head = node; + while (node->next) + node = node->next; + list->tail = node; + } else + list->head = list->tail = NULL; +} + +static void +node_list_add(struct node_list *list, struct grecs_node *node) +{ + node->next = NULL; + node->prev = list->tail; + if (list->tail) + list->tail->next = node; + else + list->head = node; + list->tail = node; +} + +static void +node_list_join(struct node_list *a, struct node_list *b) +{ + if (!b->head) + return; + b->head->prev = a->tail; + if (a->tail) + a->tail->next = b->head; + else + a->head = b->head; + a->tail = b->tail; +} + +static void +_qsort_nodelist(struct node_list *list, + int (*compare)(struct grecs_node const *, + struct grecs_node const *)) +{ + struct grecs_node *cur, *middle; + struct node_list high_list, low_list; + int rc; + + if (!list->head) + return; + cur = list->head; + do { + cur = cur->next; + if (!cur) + return; + } while ((rc = compare(list->head, cur)) == 0); + + /* Select the lower of the two as the middle value */ + middle = (rc > 0) ? cur : list->head; + + /* Split into two sublists */ + node_list_init(&low_list, NULL); + node_list_init(&high_list, NULL); + for (cur = list->head; cur; ) { + struct grecs_node *next = cur->next; + cur->next = NULL; + if (compare(middle, cur) < 0) + node_list_add(&high_list, cur); + else + node_list_add(&low_list, cur); + cur = next; + } + + /* Sort both sublists recursively */ + _qsort_nodelist(&low_list, compare); + _qsort_nodelist(&high_list, compare); + + /* Join both lists in order */ + node_list_join(&low_list, &high_list); + + /* Return the resulting list */ + list->head = low_list.head; + list->tail = low_list.tail; +} + +struct grecs_node * +grecs_nodelist_sort(struct grecs_node *node, + int (*compare)(struct grecs_node const *, + struct grecs_node const *)) +{ + struct node_list list; + node_list_init(&list, node); + _qsort_nodelist(&list, compare); + return list.head; +} + +void +grecs_tree_sort(struct grecs_node *node, + int (*compare)(struct grecs_node const *, + struct grecs_node const *)) +{ + if (node && node->down) { + node->down = grecs_nodelist_sort(node->down, compare); + for (node = node->down; node; node = node->next) + grecs_tree_sort(node, compare); + } +} + diff --git a/tests/gcffmt.c b/tests/gcffmt.c index cacf7d2..29aa69a 100644 --- a/tests/gcffmt.c +++ b/tests/gcffmt.c @@ -24,11 +24,18 @@ static void usage(const char *arg, FILE *fp, int code) { - fprintf(fp, "usage: %s [-h] [-locus] [-delim=char] [-reduce] file\n", + fprintf(fp, + "usage: %s [-h] [-locus] [-delim=char] [-reduce] [-sort] file\n", arg); exit(code); } +static int +node_ident_cmp(struct grecs_node const *a, struct grecs_node const *b) +{ + return strcmp(a->ident, b->ident); +} + int main(int argc, char **argv) { @@ -37,6 +44,7 @@ main(int argc, char **argv) struct grecs_node *tree, *node; int flags = GRECS_NODE_FLAG_DEFAULT; int reduce = 0; + int sort = 0; while (--argc) { char *arg = *++argv; @@ -46,6 +54,8 @@ main(int argc, char **argv) flags |= arg[7]; else if (strcmp(arg, "-reduce") == 0) reduce = 1; + else if (strcmp(arg, "-sort") == 0) + sort = 1; else if (strcmp(arg, "-h") == 0) usage(progname, stdout, 0); else if (arg[0] == '-') @@ -64,6 +74,8 @@ main(int argc, char **argv) exit(1); if (reduce) grecs_tree_reduce(tree, NULL); + if (sort) + grecs_tree_sort(tree, node_ident_cmp); for (node = tree; node; node = node->next) { grecs_format_node(node, flags, stdout); fputc('\n', stdout); |