1 files changed, 98 insertions, 10 deletions

diff --git a/mergesort.h b/mergesort.h
index 644cff1..7c36f08 100644
--- a/mergesort.h
+++ b/mergesort.h
@@ -1,17 +1,105 @@
 #ifndef MERGESORT_H
 #define MERGESORT_H
 
+/* 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);					\
+	}								\
+}
+
 /*
- * 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.
+ * 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 *));
+#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