summaryrefslogtreecommitdiff
path: root/mergesort.c
diff options
context:
space:
mode:
Diffstat (limited to 'mergesort.c')
-rw-r--r--mergesort.c84
1 files changed, 0 insertions, 84 deletions
diff --git a/mergesort.c b/mergesort.c
deleted file mode 100644
index bd9c6ef..0000000
--- 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;
-}