blob: bd9c6ef8eec5bc23f8c83fe8d373be946b8b2f48 [file] [log] [blame]
 #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; }