2 * sort_list: a stable sort for lists.
4 * Time complexity: O(n*log n)
5 * [assuming limited zero-element fragments]
7 * Space complexity: O(1).
27 static unsigned char been_there
[256];
28 #define BEEN_THERE(_c) \
30 if (!been_there[_c]) { \
32 printf ("Been there: %c\n", _c); \
36 #define BEEN_THERE(_c) do { } while (0)
39 // Sort one fragment. LIST_NODE_NR (==29) is a bit too high for my
40 // taste for something this simple. But, hey, it's O(1).
42 // I would use libc qsort for this, but its comparison function
43 // gets a pointer indirection extra.
44 static void array_sort(void **ptr
, int nr
, int (*cmp
)(const void *, const void *))
47 for (i
= 1; i
< nr
; i
++) {
49 if (cmp(ptr
[i
-1],p
) > 0) {
55 } while (cmp(ptr
[j
-1], p
) > 0);
62 static void verify_seq_sorted (struct ptr_list
*l
, int n
,
63 int (*cmp
)(const void *, const void *))
67 struct ptr_list
*head
= l
;
83 assert (l
!= head
|| n
== 0);
87 assert (cmp (a
, b
) <= 0);
97 assert (nbuf >= nr); \
98 memcpy ((b)->list, buffer, nr * sizeof (void *)); \
100 memcpy (buffer, buffer + nr, nbuf * sizeof (void *)); \
105 assert (nbuf <= (b)->nr); \
106 memcpy ((b)->list, buffer, nbuf * sizeof (void *)); \
110 // Merge two already-sorted sequences of blocks:
111 // (b1_1, ..., b1_n) and (b2_1, ..., b2_m)
112 // Since we may be moving blocks around, we return the new head
113 // of the merged list.
114 static struct ptr_list
*
115 merge_block_seqs (struct ptr_list
*b1
, int n
,
116 struct ptr_list
*b2
, int m
,
117 int (*cmp
)(const void *, const void *))
120 const void *buffer
[2 * LIST_NODE_NR
];
122 struct ptr_list
*newhead
= b1
;
124 // printf ("Merging %d blocks at %p with %d blocks at %p\n", n, b1, m, b2);
126 // Skip empty blocks in b2.
127 while (b2
->nr
== 0) {
136 // Do a quick skip in case entire blocks from b1 are
137 // already less than smallest element in b2.
138 while (b1
->nr
== 0 ||
139 cmp (b1
->list
[b1
->nr
- 1], b2
->list
[0]) < 0) {
140 // printf ("Skipping whole block.\n");
150 const void *d1
= b1
->list
[i1
];
151 const void *d2
= b2
->list
[i2
];
153 assert (i1
>= 0 && i1
< b1
->nr
);
154 assert (i2
>= 0 && i2
< b2
->nr
);
159 if (cmp (d1
, d2
) <= 0) {
162 // Element from b1 is smaller
163 if (++i1
>= b1
->nr
) {
179 } while (b1
->nr
== 0);
184 // Element from b2 is smaller
186 if (++i2
>= b2
->nr
) {
188 // Ok, we finished with b2. Pull it out
189 // and plug it in before b1.
190 struct ptr_list
*l
= b2
;
215 } while (b2
->nr
== 0);
223 void sort_list(struct ptr_list
**plist
, int (*cmp
)(const void *, const void *))
225 struct ptr_list
*head
= *plist
;
231 // Sort all the sub-lists
232 struct ptr_list
*list
= head
;
234 array_sort(list
->list
, list
->nr
, cmp
);
236 verify_seq_sorted (list
, 1, cmp
);
239 } while (list
!= head
);
241 // Merge the damn things together
243 struct ptr_list
*block1
= head
;
246 struct ptr_list
*block2
= block1
;
247 struct ptr_list
*next
, *newhead
;
250 for (i
= 0; i
< blocks
; i
++) {
251 block2
= block2
->next
;
252 if (block2
== head
) {
253 if (block1
== head
) {
264 for (i
= 0; i
< blocks
; ) {
274 newhead
= merge_block_seqs (block1
, blocks
,
278 verify_seq_sorted (newhead
, blocks
+ i
, cmp
);
280 if (block1
== head
) {
285 } while (block1
!= head
);