diff options
Diffstat (limited to 'mergesort.c')
-rw-r--r-- | mergesort.c | 84 |
1 files changed, 0 insertions, 84 deletions
diff --git a/mergesort.c b/mergesort.c deleted file mode 100644 index bd9c6ef8ee..0000000000 --- a/mergesort.c +++ /dev/null @@ -1,84 +0,0 @@ -#include "cache.h" -#include "mergesort.h" - -/* Combine two sorted lists. Take from `list` on equality. */ -static void *llist_merge(void *list, void *other, - void *(*get_next_fn)(const void *), - void (*set_next_fn)(void *, void *), - int (*compare_fn)(const void *, const void *)) -{ - void *result = list, *tail; - - if (compare_fn(list, other) > 0) { - result = other; - goto other; - } - for (;;) { - do { - tail = list; - list = get_next_fn(list); - if (!list) { - set_next_fn(tail, other); - return result; - } - } while (compare_fn(list, other) <= 0); - set_next_fn(tail, other); - other: - do { - tail = other; - other = get_next_fn(other); - if (!other) { - set_next_fn(tail, list); - return result; - } - } while (compare_fn(list, other) > 0); - set_next_fn(tail, list); - } -} - -/* - * Perform an iterative mergesort using an array of sublists. - * - * n is the number of items. - * ranks[i] is undefined if n & 2^i == 0, and assumed empty. - * ranks[i] contains a sublist of length 2^i otherwise. - * - * The number of bits in a void pointer limits the number of objects - * that can be created, and thus the number of array elements necessary - * to be able to sort any valid list. - * - * Adding an item to this array is like incrementing a binary number; - * positional values for set bits correspond to sublist lengths. - */ -void *llist_mergesort(void *list, - void *(*get_next_fn)(const void *), - void (*set_next_fn)(void *, void *), - int (*compare_fn)(const void *, const void *)) -{ - void *ranks[bitsizeof(void *)]; - size_t n = 0; - int i; - - while (list) { - void *next = get_next_fn(list); - if (next) - set_next_fn(list, NULL); - for (i = 0; n & ((size_t)1 << i); i++) - list = llist_merge(ranks[i], list, get_next_fn, - set_next_fn, compare_fn); - n++; - ranks[i] = list; - list = next; - } - - for (i = 0; n; i++, n >>= 1) { - if (!(n & 1)) - continue; - if (list) - list = llist_merge(ranks[i], list, get_next_fn, - set_next_fn, compare_fn); - else - list = ranks[i]; - } - return list; -} |