| /* |
| * sort_list: a stable sort for lists. |
| * |
| * Time complexity: O(n*log n) |
| * [assuming limited zero-element fragments] |
| * |
| * Space complexity: O(1). |
| * |
| * Stable: yes. |
| */ |
| |
| #include <stdio.h> |
| #include <stdlib.h> |
| #include <string.h> |
| |
| #include "lib.h" |
| #include "allocate.h" |
| |
| #undef PARANOIA |
| #undef COVERAGE |
| |
| #ifdef PARANOIA |
| #include <assert.h> |
| #else |
| #define assert(x) |
| #endif |
| |
| #ifdef COVERAGE |
| static unsigned char been_there[256]; |
| #define BEEN_THERE(_c) \ |
| do { \ |
| if (!been_there[_c]) { \ |
| been_there[_c] = 1; \ |
| printf ("Been there: %c\n", _c); \ |
| } \ |
| } while (0) |
| #else |
| #define BEEN_THERE(_c) do { } while (0) |
| #endif |
| |
| // Sort one fragment. LIST_NODE_NR (==29) is a bit too high for my |
| // taste for something this simple. But, hey, it's O(1). |
| // |
| // I would use libc qsort for this, but its comparison function |
| // gets a pointer indirection extra. |
| static void array_sort(void **ptr, int nr, int (*cmp)(const void *, const void *)) |
| { |
| int i; |
| for (i = 1; i < nr; i++) { |
| void *p = ptr[i]; |
| if (cmp(ptr[i-1],p) > 0) { |
| int j = i; |
| do { |
| ptr[j] = ptr[j-1]; |
| if (!--j) |
| break; |
| } while (cmp(ptr[j-1], p) > 0); |
| ptr[j] = p; |
| } |
| } |
| } |
| |
| #ifdef PARANOIA |
| static void verify_seq_sorted (struct ptr_list *l, int n, |
| int (*cmp)(const void *, const void *)) |
| { |
| int i = 0; |
| const void *a; |
| struct ptr_list *head = l; |
| |
| while (l->nr == 0) { |
| l = l->next; |
| if (--n == 0) |
| return; |
| assert (l != head); |
| } |
| |
| a = l->list[0]; |
| while (n > 0) { |
| const void *b; |
| if (++i >= l->nr) { |
| i = 0; |
| l = l->next; |
| n--; |
| assert (l != head || n == 0); |
| continue; |
| } |
| b = l->list[i]; |
| assert (cmp (a, b) <= 0); |
| a = b; |
| } |
| } |
| #endif |
| |
| |
| #define FLUSH_TO(b) \ |
| do { \ |
| int nr = (b)->nr; \ |
| assert (nbuf >= nr); \ |
| memcpy ((b)->list, buffer, nr * sizeof (void *)); \ |
| nbuf -= nr; \ |
| memmove (buffer, buffer + nr, nbuf * sizeof (void *)); \ |
| } while (0) |
| |
| #define DUMP_TO(b) \ |
| do { \ |
| assert (nbuf <= (b)->nr); \ |
| memcpy ((b)->list, buffer, nbuf * sizeof (void *)); \ |
| } while (0) |
| |
| |
| // Merge two already-sorted sequences of blocks: |
| // (b1_1, ..., b1_n) and (b2_1, ..., b2_m) |
| // Since we may be moving blocks around, we return the new head |
| // of the merged list. |
| static struct ptr_list * |
| merge_block_seqs (struct ptr_list *b1, int n, |
| struct ptr_list *b2, int m, |
| int (*cmp)(const void *, const void *)) |
| { |
| int i1 = 0, i2 = 0; |
| const void *buffer[2 * LIST_NODE_NR]; |
| int nbuf = 0; |
| struct ptr_list *newhead = b1; |
| |
| // printf ("Merging %d blocks at %p with %d blocks at %p\n", n, b1, m, b2); |
| |
| // Skip empty blocks in b2. |
| while (b2->nr == 0) { |
| BEEN_THERE('F'); |
| b2 = b2->next; |
| if (--m == 0) { |
| BEEN_THERE('G'); |
| return newhead; |
| } |
| } |
| |
| // Do a quick skip in case entire blocks from b1 are |
| // already less than smallest element in b2. |
| while (b1->nr == 0 || |
| cmp (PTR_ENTRY_NOTAG(b1, b1->nr - 1), PTR_ENTRY_NOTAG(b2,0)) < 0) { |
| // printf ("Skipping whole block.\n"); |
| BEEN_THERE('H'); |
| b1 = b1->next; |
| if (--n == 0) { |
| BEEN_THERE('I'); |
| return newhead; |
| } |
| } |
| |
| while (1) { |
| const void *d1 = PTR_ENTRY_NOTAG(b1,i1); |
| const void *d2 = PTR_ENTRY_NOTAG(b2,i2); |
| |
| assert (i1 >= 0 && i1 < b1->nr); |
| assert (i2 >= 0 && i2 < b2->nr); |
| assert (b1 != b2); |
| assert (n > 0); |
| assert (m > 0); |
| |
| if (cmp (d1, d2) <= 0) { |
| BEEN_THERE('J'); |
| buffer[nbuf++] = d1; |
| // Element from b1 is smaller |
| if (++i1 >= b1->nr) { |
| BEEN_THERE('L'); |
| FLUSH_TO(b1); |
| do { |
| b1 = b1->next; |
| if (--n == 0) { |
| BEEN_THERE('O'); |
| while (b1 != b2) { |
| BEEN_THERE('P'); |
| FLUSH_TO(b1); |
| b1 = b1->next; |
| } |
| assert (nbuf == i2); |
| DUMP_TO(b2); |
| return newhead; |
| } |
| } while (b1->nr == 0); |
| i1 = 0; |
| } |
| } else { |
| BEEN_THERE('K'); |
| // Element from b2 is smaller |
| buffer[nbuf++] = d2; |
| if (++i2 >= b2->nr) { |
| struct ptr_list *l = b2; |
| BEEN_THERE('M'); |
| // OK, we finished with b2. Pull it out |
| // and plug it in before b1. |
| |
| b2 = b2->next; |
| b2->prev = l->prev; |
| b2->prev->next = b2; |
| l->next = b1; |
| l->prev = b1->prev; |
| l->next->prev = l; |
| l->prev->next = l; |
| |
| if (b1 == newhead) { |
| BEEN_THERE('N'); |
| newhead = l; |
| } |
| |
| FLUSH_TO(l); |
| b2 = b2->prev; |
| do { |
| b2 = b2->next; |
| if (--m == 0) { |
| BEEN_THERE('Q'); |
| assert (nbuf == i1); |
| DUMP_TO(b1); |
| return newhead; |
| } |
| } while (b2->nr == 0); |
| i2 = 0; |
| } |
| } |
| } |
| } |
| |
| |
| void sort_list(struct ptr_list **plist, int (*cmp)(const void *, const void *)) |
| { |
| struct ptr_list *head = *plist, *list = head; |
| int blocks = 1; |
| |
| if (!head) |
| return; |
| |
| // Sort all the sub-lists |
| do { |
| array_sort(list->list, list->nr, cmp); |
| #ifdef PARANOIA |
| verify_seq_sorted (list, 1, cmp); |
| #endif |
| list = list->next; |
| } while (list != head); |
| |
| // Merge the damn things together |
| while (1) { |
| struct ptr_list *block1 = head; |
| |
| do { |
| struct ptr_list *block2 = block1; |
| struct ptr_list *next, *newhead; |
| int i; |
| |
| for (i = 0; i < blocks; i++) { |
| block2 = block2->next; |
| if (block2 == head) { |
| if (block1 == head) { |
| BEEN_THERE('A'); |
| *plist = head; |
| return; |
| } |
| BEEN_THERE('B'); |
| goto next_pass; |
| } |
| } |
| |
| next = block2; |
| for (i = 0; i < blocks; ) { |
| next = next->next; |
| i++; |
| if (next == head) { |
| BEEN_THERE('C'); |
| break; |
| } |
| BEEN_THERE('D'); |
| } |
| |
| newhead = merge_block_seqs (block1, blocks, |
| block2, i, |
| cmp); |
| #ifdef PARANOIA |
| verify_seq_sorted (newhead, blocks + i, cmp); |
| #endif |
| if (block1 == head) { |
| BEEN_THERE('E'); |
| head = newhead; |
| } |
| block1 = next; |
| } while (block1 != head); |
| next_pass: |
| blocks <<= 1; |
| } |
| } |