mergesort.c

#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;
}