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
--- /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);
+	}
+}
+