diff options
author | 2004-09-26 15:07:09 -0700 | |
---|---|---|
committer | 2005-04-07 21:03:23 -0700 | |
commit | 1c849c0c3a50b115a58975431cd3dd876265bed6 (patch) | |
tree | 1ccafd0d2ef957fa6ba595e170bd4af9d57b25e1 /sort.c | |
parent | This file uses NULL, so include stdlib.h (diff) | |
download | sparse-1c849c0c3a50b115a58975431cd3dd876265bed6.tar.gz sparse-1c849c0c3a50b115a58975431cd3dd876265bed6.tar.bz2 sparse-1c849c0c3a50b115a58975431cd3dd876265bed6.zip |
Make sure sort does not degenerate.
Diffstat (limited to 'sort.c')
-rw-r--r-- | sort.c | 324 |
1 files changed, 256 insertions, 68 deletions
@@ -1,101 +1,289 @@ /* - * This is a horribly stupid list sort. We - * use it to sort C initializers into ascending - * order. + * sort_list: a stable sort for lists. * - * These things tend to be sorted already, so we - * should optimize for that case and not really - * care about the other ones. + * Time complexity: O(n*log n) + * [assuming limited zero-element fragments] + * + * Space complexity: O(1). + * + * Stable: yes. */ -#include <stdio.h> + #include "lib.h" +#include <stdio.h> +#include <stdlib.h> +#include <string.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) { + 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); + } while (cmp(ptr[j-1], p) > 0); ptr[j] = p; } } } -static int merge_array(void **arr1, int nr1, void **arr2, int nr2, int (*cmp)(const void *, const void *)) +#ifdef PARANOIA +static void verify_seq_sorted (struct ptr_list *l, int n, + int (*cmp)(const void *, const void *)) { - int i, j; - void *a, *b; - - if (!nr1 || !nr2) - return 0; - - i = nr1-1; - j = 0; - a = arr1[i]; /* last entry of first array */ - b = arr2[j]; /* first entry of last array */ - - /* If they are already sorted, don't do anything else */ - if (cmp(a, b) >= 0) - return 0; - - /* - * Remember: we don't care. The above was - * the speedpath. This is a joke. Although - * it happens to be a joke that gets the - * reverse sorted case right, I think. - * - * Damn, it's been _ages_ since I did sort - * routines. I feel like a first-year CS - * student again. - */ - do { - arr2[j] = a; - arr1[i] = b; - if (--i < 0) - break; - if (++j == nr2) - break; - a = arr1[i]; - b = arr2[j]; - } while (cmp(a, b) < 0); - - array_sort(arr1, nr1, cmp); - array_sort(arr2, nr2, cmp); - - return 1; + 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; \ + memcpy (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) + -void sort_list(struct ptr_list **list, int (*cmp)(const void *, const void *)) +// 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 *)) { - struct ptr_list *head = *list; + int i1 = 0, i2 = 0; + const void *buffer[2 * LIST_NODE_NR]; + int nbuf = 0; + struct ptr_list *newhead = b1; - if (head) { - int repeat; + // printf ("Merging %d blocks at %p with %d blocks at %p\n", n, b1, m, b2); - /* Sort all the sub-lists */ - struct ptr_list *list = head, *next; - do { - array_sort(list->list, list->nr, cmp); - list = list->next; - } while (list != head); + // 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 (b1->list[b1->nr - 1], b2->list[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 = b1->list[i1]; + const void *d2 = b2->list[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) { + BEEN_THERE('M'); + // Ok, we finished with b2. Pull it out + // and plug it in before b1. + struct ptr_list *l = b2; + + 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; + int blocks = 1; + + if (!head) + return; + + // Sort all the sub-lists + struct ptr_list *list = head; + 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; - /* Merge the damn things together .. */ do { - repeat = 0; + struct ptr_list *block2 = block1; + struct ptr_list *next, *newhead; + int i; - list = head; - next = list->next; - while (next != head) { - repeat |= merge_array(list->list, list->nr, next->list, next->nr, cmp); - list = next; + 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; } - } while (repeat); + block1 = next; + } while (block1 != head); + next_pass: + blocks <<= 1; } } |