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
29static 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.
46static 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
64static 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.
116static struct ptr_list *
117merge_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_NOTAG(b1, b1->nr - 1), PTR_ENTRY_NOTAG(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_NOTAG(b1,i1);
153		const void *d2 = PTR_ENTRY_NOTAG(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
225void 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}
291