diff options
author | René Scharfe <l.s.r@web.de> | 2022-07-16 20:02:38 +0300 |
---|---|---|
committer | Junio C Hamano <gitster@pobox.com> | 2022-07-18 01:20:39 +0300 |
commit | 0f1eb7d6e976c64c0016d4355200660ce2fdf1ec (patch) | |
tree | 6af1dad6c23abda33f8f7329b495d64c807dfefe /mergesort.c | |
parent | 9b9f5f6217a5178e348dc2e18bc6af7158b97c36 (diff) |
mergesort: remove llist_mergesort()
Now that all of its callers are gone, remove llist_mergesort().
Signed-off-by: René Scharfe <l.s.r@web.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Diffstat (limited to 'mergesort.c')
-rw-r--r-- | mergesort.c | 76 |
1 files changed, 0 insertions, 76 deletions
diff --git a/mergesort.c b/mergesort.c deleted file mode 100644 index 6bda3a1c0e..0000000000 --- a/mergesort.c +++ /dev/null @@ -1,76 +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; - int prefer_list = compare_fn(list, other) <= 0; - - if (!prefer_list) { - result = other; - SWAP(list, other); - } - for (;;) { - do { - tail = list; - list = get_next_fn(list); - if (!list) { - set_next_fn(tail, other); - return result; - } - } while (compare_fn(list, other) < prefer_list); - set_next_fn(tail, other); - prefer_list ^= 1; - SWAP(list, other); - } -} - -/* - * 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; - - if (!list) - return NULL; - - for (;;) { - int i; - size_t m; - void *next = get_next_fn(list); - if (next) - set_next_fn(list, NULL); - for (i = 0, m = n;; i++, m >>= 1) { - if (m & 1) - list = llist_merge(ranks[i], list, get_next_fn, - set_next_fn, compare_fn); - else if (next) - break; - else if (!m) - return list; - } - n++; - ranks[i] = list; - list = next; - } -} |