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 } 291