1 /* grecs - Gray's Extensible Configuration System
2 Copyright (C) 2007-2016 Sergey Poznyakoff
3
4 Grecs is free software; you can redistribute it and/or modify it
5 under the terms of the GNU General Public License as published by the
6 Free Software Foundation; either version 3 of the License, or (at your
7 option) any later version.
8
9 Grecs is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License along
15 with Grecs. If not, see <http://www.gnu.org/licenses/>. */
16
17 #ifdef HAVE_CONFIG_H
18 # include <config.h>
19 #endif
20 #include <stdlib.h>
21 #include "grecs.h"
22
23 struct node_list {
24 struct grecs_node *head, *tail;
25 };
26
27 static void
node_list_init(struct node_list * list,struct grecs_node * node)28 node_list_init(struct node_list *list, struct grecs_node *node)
29 {
30 if (node) {
31 list->head = node;
32 while (node->next)
33 node = node->next;
34 list->tail = node;
35 } else
36 list->head = list->tail = NULL;
37 }
38
39 static void
node_list_add(struct node_list * list,struct grecs_node * node)40 node_list_add(struct node_list *list, struct grecs_node *node)
41 {
42 node->next = NULL;
43 node->prev = list->tail;
44 if (list->tail)
45 list->tail->next = node;
46 else
47 list->head = node;
48 list->tail = node;
49 }
50
51 static void
node_list_join(struct node_list * a,struct node_list * b)52 node_list_join(struct node_list *a, struct node_list *b)
53 {
54 if (!b->head)
55 return;
56 b->head->prev = a->tail;
57 if (a->tail)
58 a->tail->next = b->head;
59 else
60 a->head = b->head;
61 a->tail = b->tail;
62 }
63
64 static void
_qsort_nodelist(struct node_list * list,int (* compare)(struct grecs_node const *,struct grecs_node const *))65 _qsort_nodelist(struct node_list *list,
66 int (*compare)(struct grecs_node const *,
67 struct grecs_node const *))
68 {
69 struct grecs_node *cur, *middle;
70 struct node_list high_list, low_list;
71 int rc;
72
73 if (!list->head)
74 return;
75 cur = list->head;
76 do {
77 cur = cur->next;
78 if (!cur)
79 return;
80 } while ((rc = compare(list->head, cur)) == 0);
81
82 /* Select the lower of the two as the middle value */
83 middle = (rc > 0) ? cur : list->head;
84
85 /* Split into two sublists */
86 node_list_init(&low_list, NULL);
87 node_list_init(&high_list, NULL);
88 for (cur = list->head; cur; ) {
89 struct grecs_node *next = cur->next;
90 cur->next = NULL;
91 if (compare(middle, cur) < 0)
92 node_list_add(&high_list, cur);
93 else
94 node_list_add(&low_list, cur);
95 cur = next;
96 }
97
98 if (!low_list.head)
99 low_list = high_list;
100 else if (high_list.head) {
101 /* Sort both sublists recursively */
102 _qsort_nodelist(&low_list, compare);
103 _qsort_nodelist(&high_list, compare);
104 /* Join both lists in order */
105 node_list_join(&low_list, &high_list);
106 }
107 /* Return the resulting list */
108 list->head = low_list.head;
109 list->tail = low_list.tail;
110 }
111
112 struct grecs_node *
grecs_nodelist_sort(struct grecs_node * node,int (* compare)(struct grecs_node const *,struct grecs_node const *))113 grecs_nodelist_sort(struct grecs_node *node,
114 int (*compare)(struct grecs_node const *,
115 struct grecs_node const *))
116 {
117 struct node_list list;
118 node_list_init(&list, node);
119 _qsort_nodelist(&list, compare);
120 return list.head;
121 }
122
123 void
grecs_tree_sort(struct grecs_node * node,int (* compare)(struct grecs_node const *,struct grecs_node const *))124 grecs_tree_sort(struct grecs_node *node,
125 int (*compare)(struct grecs_node const *,
126 struct grecs_node const *))
127 {
128 if (node && node->down) {
129 node->down = grecs_nodelist_sort(node->down, compare);
130 for (node = node->down; node; node = node->next)
131 grecs_tree_sort(node, compare);
132 }
133 }
134
135