mergesort: add macros for typed sort of linked lists

[thirdparty/git.git] / mergesort.h

#ifndef MERGESORT_H
#define MERGESORT_H

/*
 * Sort linked list in place.
 * - get_next_fn() returns the next element given an element of a linked list.
 * - set_next_fn() takes two elements A and B, and makes B the "next" element
 *   of A on the list.
 * - compare_fn() takes two elements A and B, and returns negative, 0, positive
 *   as the same sign as "subtracting" B from A.
 */
void *llist_mergesort(void *list,
		      void *(*get_next_fn)(const void *),
		      void (*set_next_fn)(void *, void *),
		      int (*compare_fn)(const void *, const void *));

/* Combine two sorted lists.  Take from `list` on equality. */
#define DEFINE_LIST_MERGE_INTERNAL(name, type)				\
static type *name##__merge(type *list, type *other,			\
			   int (*compare_fn)(const type *, const type *))\
{									\
	type *result = list, *tail;					\
	int prefer_list = compare_fn(list, other) <= 0;			\
									\
	if (!prefer_list) {						\
		result = other;						\
		SWAP(list, other);					\
	}								\
	for (;;) {							\
		do {							\
			tail = list;					\
			list = name##__get_next(list);			\
			if (!list) {					\
				name##__set_next(tail, other);		\
				return result;				\
			}						\
		} while (compare_fn(list, other) < prefer_list);	\
		name##__set_next(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.
 */
#define DEFINE_LIST_SORT_INTERNAL(scope, name, type)			\
scope void name(type **listp,						\
		int (*compare_fn)(const type *, const type *))		\
{									\
	type *list = *listp;						\
	type *ranks[bitsizeof(type *)];					\
	size_t n = 0;							\
									\
	if (!list)							\
		return;							\
									\
	for (;;) {							\
		int i;							\
		size_t m;						\
		type *next = name##__get_next(list);			\
		if (next)						\
			name##__set_next(list, NULL);			\
		for (i = 0, m = n;; i++, m >>= 1) {			\
			if (m & 1) {					\
				list = name##__merge(ranks[i], list,	\
						    compare_fn);	\
			} else if (next) {				\
				break;					\
			} else if (!m) {				\
				*listp = list;				\
				return;					\
			}						\
		}							\
		n++;							\
		ranks[i] = list;					\
		list = next;						\
	}								\
}

#define DECLARE_LIST_SORT(scope, name, type)			\
scope void name(type **listp,					\
		int (*compare_fn)(const type *, const type *))

#define DEFINE_LIST_SORT_DEBUG(scope, name, type, next_member,	\
			       on_get_next, on_set_next)	\
								\
static inline type *name##__get_next(const type *elem)		\
{								\
	on_get_next;						\
	return elem->next_member;				\
}								\
								\
static inline void name##__set_next(type *elem, type *next)	\
{								\
	on_set_next;						\
	elem->next_member = next;				\
}								\
								\
DEFINE_LIST_MERGE_INTERNAL(name, type)				\
DEFINE_LIST_SORT_INTERNAL(scope, name, type)			\
DECLARE_LIST_SORT(scope, name, type)

#define DEFINE_LIST_SORT(scope, name, type, next_member) \
DEFINE_LIST_SORT_DEBUG(scope, name, type, next_member, (void)0, (void)0)

#endif