1
2 /*----------------------------------------------------------------*/
3 /*! \file
4 * Linked list sorting code taken from
5 * http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
6 * and hacked to serve in gattrib by SDB.
7 *
8 */
9
10 /*
11 * Demonstration code for sorting a linked list.
12 *
13 * The algorithm used is Mergesort, because that works really well
14 * on linked lists, without requiring the O(N) extra space it needs
15 * when you do it on arrays.
16 *
17 * This code can handle singly and doubly linked lists, and
18 * circular and linear lists too. For any serious application,
19 * you'll probably want to remove the conditionals on `is_circular'
20 * and `is_double' to adapt the code to your own purpose.
21 *
22 */
23
24 /*
25 * This file is copyright 2001 Simon Tatham.
26 *
27 * Permission is hereby granted, free of charge, to any person
28 * obtaining a copy of this software and associated documentation
29 * files (the "Software"), to deal in the Software without
30 * restriction, including without limitation the rights to use,
31 * copy, modify, merge, publish, distribute, sublicense, and/or
32 * sell copies of the Software, and to permit persons to whom the
33 * Software is furnished to do so, subject to the following
34 * conditions:
35 *
36 * The above copyright notice and this permission notice shall be
37 * included in all copies or substantial portions of the Software.
38 *
39 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
40 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
41 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
42 * NONINFRINGEMENT. IN NO EVENT SHALL SIMON TATHAM BE LIABLE FOR
43 * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
44 * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
45 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
46 * SOFTWARE.
47 */
48
49 /* --- We don't need these 'cause they are already defined elsewhere ---
50 * #define FALSE 0
51 * #define TRUE 1
52 */
53
54 #ifdef HAVE_CONFIG_H
55 #include "config.h"
56 #endif
57
58 #include <stdio.h>
59 #include <ctype.h>
60
61 #ifdef HAVE_STRING_H
62 #include <string.h>
63 #endif
64
65 /*------------------------------------------------------------------
66 * Gattrib specific includes
67 *------------------------------------------------------------------*/
68 #include <libgeda/libgeda.h> /* geda library fcns */
69 #include "../include/struct.h" /* typdef and struct declarations */
70 #include "../include/prototype.h" /* function prototypes */
71 #include "../include/globals.h"
72
73 #ifdef HAVE_LIBDMALLOC
74 #include <dmalloc.h>
75 #endif
76
77
78 /*----------------------------------------------------------------*/
79 /*! \brief Compare values of string data
80 *
81 * Comparison function -- compare values of string data.
82 * \param al pointer to first STRING_LIST item to be compared
83 * \param bl pointer to second STRING_LIST item to be compared
84 * \returns +ve if al > bl, -ve if al < bl, 0 if al = bl
85 */
86 /*----------------------------------------------------------------*/
cmp(STRING_LIST * al,STRING_LIST * bl)87 int cmp(STRING_LIST *al, STRING_LIST *bl) {
88 char *a = al->data;
89 char *b = bl->data;
90
91 if (al->pos != bl->pos)
92 return al->pos - bl->pos;
93
94 while (*a && *b)
95 {
96 if (isdigit ((int) *a) && isdigit ((int) *b))
97 {
98 int ia = atoi (a);
99 int ib = atoi (b);
100 if (ia != ib)
101 return ia - ib;
102 while (isdigit ((int) *a))
103 a++;
104 while (isdigit ((int) *b))
105 b++;
106 }
107 else if (tolower ((int) *a) != tolower ((int) *b))
108 return tolower ((int) *a) - tolower ((int) *b);
109 a++;
110 b++;
111 }
112 if (*a)
113 return 1;
114 if (*b)
115 return -1;
116 return 0;
117 }
118
119 /*----------------------------------------------------------------*/
120 /*! \brief Sort the linked list
121 *
122 * This is the actual sort function. Notice that it returns the new
123 * head of the list. (It has to, because the head will not
124 * generally be the same element after the sort.) So unlike sorting
125 * an array, where you can do
126 *
127 * - sort(myarray);
128 *
129 * you now have to do
130 *
131 * - list = listsort(mylist);
132 *
133 * \param list The linked STRING_LIST to be sorted
134 * \param is_circular TRUE if this is a circularly linked list
135 * \param is_double TRUE if this is a doubly-linked list
136 * \returns a pointer to the new head of the list
137 */
138 /*----------------------------------------------------------------*/
listsort(STRING_LIST * list,int is_circular,int is_double)139 STRING_LIST *listsort(STRING_LIST *list, int is_circular, int is_double) {
140 STRING_LIST *p, *q, *e, *tail, *oldhead;
141 int insize, nmerges, psize, qsize, i;
142
143 /*
144 * Silly special case: if `list' was passed in as NULL, return
145 * NULL immediately.
146 */
147 if (!list)
148 return NULL;
149
150 insize = 1;
151
152 while (1) {
153 p = list;
154 oldhead = list; /* only used for circular linkage */
155 list = NULL;
156 tail = NULL;
157
158 nmerges = 0; /* count number of merges we do in this pass */
159
160 while (p) {
161 nmerges++; /* there exists a merge to be done */
162 /* step `insize' places along from p */
163 q = p;
164 psize = 0;
165 for (i = 0; i < insize; i++) {
166 psize++;
167 if (is_circular)
168 q = (q->next == oldhead ? NULL : q->next);
169 else
170 q = q->next;
171 if (!q) break;
172 }
173
174 /* if q hasn't fallen off end, we have two lists to merge */
175 qsize = insize;
176
177 /* now we have two lists; merge them */
178 while (psize > 0 || (qsize > 0 && q)) {
179
180 /* decide whether next element of merge comes from p or q */
181 if (psize == 0) {
182 /* p is empty; e must come from q. */
183 e = q; q = q->next; qsize--;
184 if (is_circular && q == oldhead) q = NULL;
185 } else if (qsize == 0 || !q) {
186 /* q is empty; e must come from p. */
187 e = p; p = p->next; psize--;
188 if (is_circular && p == oldhead) p = NULL;
189 } else if (cmp(p,q) <= 0) {
190 /* First element of p is lower (or same);
191 * e must come from p. */
192 e = p; p = p->next; psize--;
193 if (is_circular && p == oldhead) p = NULL;
194 } else {
195 /* First element of q is lower; e must come from q. */
196 e = q; q = q->next; qsize--;
197 if (is_circular && q == oldhead) q = NULL;
198 }
199
200 /* add the next element to the merged list */
201 if (tail) {
202 tail->next = e;
203 } else {
204 list = e;
205 }
206 if (is_double) {
207 /* Maintain reverse pointers in a doubly linked list. */
208 e->prev = tail;
209 }
210 tail = e;
211 }
212
213 /* now p has stepped `insize' places along, and q has too */
214 p = q;
215 }
216 if (is_circular) {
217 tail->next = list;
218 if (is_double)
219 list->prev = tail;
220 } else
221 tail->next = NULL;
222
223 /* If we have done only one merge, we're finished. */
224 if (nmerges <= 1) /* allow for nmerges==0, the empty list case */
225 return list;
226
227 /* Otherwise repeat, merging lists twice the size */
228 insize *= 2;
229 }
230 }
231
232