1 /*
2 * sort_list: a stable sort for lists.
3 *
4 * Time complexity: O(n*log n)
5 * [assuming limited zero-element fragments]
6 *
7 * Space complexity: O(1).
8 *
9 * Stable: yes.
10 */
11
12 #include <stdio.h>
13 #include <stdlib.h>
14 #include <string.h>
15
16 #include "lib.h"
17 #include "allocate.h"
18
19 #undef PARANOIA
20 #undef COVERAGE
21
22 #ifdef PARANOIA
23 #include <assert.h>
24 #else
25 #define assert(x)
26 #endif
27
28 #ifdef COVERAGE
29 static unsigned char been_there[256];
30 #define BEEN_THERE(_c) \
31 do { \
32 if (!been_there[_c]) { \
33 been_there[_c] = 1; \
34 printf ("Been there: %c\n", _c); \
35 } \
36 } while (0)
37 #else
38 #define BEEN_THERE(_c) do { } while (0)
39 #endif
40
41 // Sort one fragment. LIST_NODE_NR (==29) is a bit too high for my
42 // taste for something this simple. But, hey, it's O(1).
43 //
44 // I would use libc qsort for this, but its comparison function
45 // gets a pointer indirection extra.
46 static void array_sort(void **ptr, int nr, int (*cmp)(const void *, const void *))
47 {
48 int i;
49 for (i = 1; i < nr; i++) {
50 void *p = ptr[i];
51 if (cmp(ptr[i-1],p) > 0) {
52 int j = i;
53 do {
54 ptr[j] = ptr[j-1];
55 if (!--j)
56 break;
57 } while (cmp(ptr[j-1], p) > 0);
58 ptr[j] = p;
59 }
60 }
61 }
62
63 #ifdef PARANOIA
64 static void verify_seq_sorted (struct ptr_list *l, int n,
65 int (*cmp)(const void *, const void *))
66 {
67 int i = 0;
68 const void *a;
69 struct ptr_list *head = l;
70
71 while (l->nr == 0) {
72 l = l->next;
73 if (--n == 0)
74 return;
75 assert (l != head);
76 }
77
78 a = l->list[0];
79 while (n > 0) {
80 const void *b;
81 if (++i >= l->nr) {
82 i = 0;
83 l = l->next;
84 n--;
85 assert (l != head || n == 0);
86 continue;
87 }
88 b = l->list[i];
89 assert (cmp (a, b) <= 0);
90 a = b;
91 }
92 }
93 #endif
94
95
96 #define FLUSH_TO(b) \
97 do { \
98 int nr = (b)->nr; \
99 assert (nbuf >= nr); \
100 memcpy ((b)->list, buffer, nr * sizeof (void *)); \
101 nbuf -= nr; \
102 memmove (buffer, buffer + nr, nbuf * sizeof (void *)); \
103 } while (0)
104
105 #define DUMP_TO(b) \
106 do { \
107 assert (nbuf <= (b)->nr); \
108 memcpy ((b)->list, buffer, nbuf * sizeof (void *)); \
109 } while (0)
110
111
112 // Merge two already-sorted sequences of blocks:
113 // (b1_1, ..., b1_n) and (b2_1, ..., b2_m)
114 // Since we may be moving blocks around, we return the new head
115 // of the merged list.
116 static struct ptr_list *
117 merge_block_seqs (struct ptr_list *b1, int n,
118 struct ptr_list *b2, int m,
119 int (*cmp)(const void *, const void *))
120 {
121 int i1 = 0, i2 = 0;
122 const void *buffer[2 * LIST_NODE_NR];
123 int nbuf = 0;
124 struct ptr_list *newhead = b1;
125
126 // printf ("Merging %d blocks at %p with %d blocks at %p\n", n, b1, m, b2);
127
128 // Skip empty blocks in b2.
129 while (b2->nr == 0) {
130 BEEN_THERE('F');
131 b2 = b2->next;
132 if (--m == 0) {
133 BEEN_THERE('G');
134 return newhead;
135 }
136 }
137
138 // Do a quick skip in case entire blocks from b1 are
139 // already less than smallest element in b2.
140 while (b1->nr == 0 ||
141 cmp (PTR_ENTRY(b1, b1->nr - 1), PTR_ENTRY(b2,0)) < 0) {
142 // printf ("Skipping whole block.\n");
143 BEEN_THERE('H');
144 b1 = b1->next;
145 if (--n == 0) {
146 BEEN_THERE('I');
147 return newhead;
148 }
149 }
150
151 while (1) {
152 const void *d1 = PTR_ENTRY(b1,i1);
153 const void *d2 = PTR_ENTRY(b2,i2);
154
155 assert (i1 >= 0 && i1 < b1->nr);
156 assert (i2 >= 0 && i2 < b2->nr);
157 assert (b1 != b2);
158 assert (n > 0);
159 assert (m > 0);
160
161 if (cmp (d1, d2) <= 0) {
162 BEEN_THERE('J');
163 buffer[nbuf++] = d1;
164 // Element from b1 is smaller
165 if (++i1 >= b1->nr) {
166 BEEN_THERE('L');
167 FLUSH_TO(b1);
168 do {
169 b1 = b1->next;
170 if (--n == 0) {
171 BEEN_THERE('O');
172 while (b1 != b2) {
173 BEEN_THERE('P');
174 FLUSH_TO(b1);
175 b1 = b1->next;
176 }
177 assert (nbuf == i2);
178 DUMP_TO(b2);
179 return newhead;
180 }
181 } while (b1->nr == 0);
182 i1 = 0;
183 }
184 } else {
185 BEEN_THERE('K');
186 // Element from b2 is smaller
187 buffer[nbuf++] = d2;
188 if (++i2 >= b2->nr) {
189 struct ptr_list *l = b2;
190 BEEN_THERE('M');
191 // OK, we finished with b2. Pull it out
192 // and plug it in before b1.
193
194 b2 = b2->next;
195 b2->prev = l->prev;
196 b2->prev->next = b2;
197 l->next = b1;
198 l->prev = b1->prev;
199 l->next->prev = l;
200 l->prev->next = l;
201
202 if (b1 == newhead) {
203 BEEN_THERE('N');
204 newhead = l;
205 }
206
207 FLUSH_TO(l);
208 b2 = b2->prev;
209 do {
210 b2 = b2->next;
211 if (--m == 0) {
212 BEEN_THERE('Q');
213 assert (nbuf == i1);
214 DUMP_TO(b1);
215 return newhead;
216 }
217 } while (b2->nr == 0);
218 i2 = 0;
219 }
220 }
221 }
222 }
223
224
225 void sort_list(struct ptr_list **plist, int (*cmp)(const void *, const void *))
226 {
227 struct ptr_list *head = *plist, *list = head;
228 int blocks = 1;
229
230 if (!head)
231 return;
232
233 // Sort all the sub-lists
234 do {
235 array_sort(list->list, list->nr, cmp);
236 #ifdef PARANOIA
237 verify_seq_sorted (list, 1, cmp);
238 #endif
239 list = list->next;
240 } while (list != head);
241
242 // Merge the damn things together
243 while (1) {
244 struct ptr_list *block1 = head;
245
246 do {
247 struct ptr_list *block2 = block1;
248 struct ptr_list *next, *newhead;
249 int i;
250
251 for (i = 0; i < blocks; i++) {
252 block2 = block2->next;
253 if (block2 == head) {
254 if (block1 == head) {
255 BEEN_THERE('A');
256 *plist = head;
257 return;
258 }
259 BEEN_THERE('B');
260 goto next_pass;
261 }
262 }
263
264 next = block2;
265 for (i = 0; i < blocks; ) {
266 next = next->next;
267 i++;
268 if (next == head) {
269 BEEN_THERE('C');
270 break;
271 }
272 BEEN_THERE('D');
273 }
274
275 newhead = merge_block_seqs (block1, blocks,
276 block2, i,
277 cmp);
278 #ifdef PARANOIA
279 verify_seq_sorted (newhead, blocks + i, cmp);
280 #endif
281 if (block1 == head) {
282 BEEN_THERE('E');
283 head = newhead;
284 }
285 block1 = next;
286 } while (block1 != head);
287 next_pass:
288 blocks <<= 1;
289 }
290 }