summaryrefslogtreecommitdiffabout
path: root/src
authorSergey Poznyakoff <gray@gnu.org.ua>2011-05-06 10:57:43 (GMT)
committer Sergey Poznyakoff <gray@gnu.org.ua>2011-05-06 10:57:43 (GMT)
commit352b268186931579ae8dcc6a19aaaa89547555f5 (patch) (side-by-side diff)
tree6b8797f63ee7ca085526ec97c392c5f52d856109 /src
parent52c12573a505bf29a0301a1c9553e88c3270713e (diff)
downloadgrecs-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.
Diffstat (limited to 'src') (more/less context) (ignore whitespace changes)
-rw-r--r--src/Make.am1
-rw-r--r--src/grecs-lex.l2
-rw-r--r--src/grecs.h4
-rw-r--r--src/sort.c132
4 files changed, 138 insertions, 1 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
--- a/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);
+ }
+}
+

Return to:

Send suggestions and report system problems to the System administrator.