Make sure sort does not degenerate.

1 files changed, 256 insertions, 68 deletions

diff --git a/sort.c b/sort.c
index 590fcab..9cd446a 100644
--- a/sort.c
+++ b/sort.c
@@ -1,101 +1,289 @@
 /*
- * This is a horribly stupid list sort. We
- * use it to sort C initializers into ascending
- * order.
+ * sort_list: a stable sort for lists.
  *
- * These things tend to be sorted already, so we
- * should optimize for that case and not really
- * care about the other ones.
+ * Time complexity: O(n*log n)
+ *   [assuming limited zero-element fragments]
+ *
+ * Space complexity: O(1).
+ *
+ * Stable: yes.
  */
-#include <stdio.h>
+
 #include "lib.h"
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#undef PARANOIA
+#undef COVERAGE
 
+#ifdef PARANOIA
+#include <assert.h>
+#else
+#define assert(x)
+#endif
+
+#ifdef COVERAGE
+static unsigned char been_there[256];
+#define BEEN_THERE(_c)					\
+  do {							\
+	if (!been_there[_c]) {				\
+		been_there[_c] = 1;			\
+		printf ("Been there: %c\n", _c);	\
+	}						\
+  } while (0)
+#else
+#define BEEN_THERE(_c) do { } while (0)
+#endif
+
+// Sort one fragment.  LIST_NODE_NR (==29) is a bit too high for my
+// taste for something this simple.  But, hey, it's O(1).
+//
+// I would use libc qsort for this, but its comparison function
+// gets a pointer indirection extra.
 static void array_sort(void **ptr, int nr, int (*cmp)(const void *, const void *))
 {
 	int i;
 	for (i = 1; i < nr; i++) {
 		void *p = ptr[i];
-		if (cmp(ptr[i-1],p) < 0) {
+		if (cmp(ptr[i-1],p) > 0) {
 			int j = i;
 			do {
 				ptr[j] = ptr[j-1];
 				if (!--j)
 					break;
-			} while (cmp(ptr[j-1], p) < 0);
+			} while (cmp(ptr[j-1], p) > 0);
 			ptr[j] = p;
 		}
 	}
 }
 
-static int merge_array(void **arr1, int nr1, void **arr2, int nr2, int (*cmp)(const void *, const void *))
+#ifdef PARANOIA
+static void verify_seq_sorted (struct ptr_list *l, int n,
+			       int (*cmp)(const void *, const void *))
 {
-	int i, j;
-	void *a, *b;
-
-	if (!nr1 || !nr2)
-		return 0;
-
-	i = nr1-1;
-	j = 0;
-	a = arr1[i];	/* last entry of first array */
-	b = arr2[j];	/* first entry of last array */
-
-	/* If they are already sorted, don't do anything else */
-	if (cmp(a, b) >= 0)
-		return 0;
-
-	/*
-	 * Remember: we don't care. The above was
-	 * the speedpath. This is a joke. Although
-	 * it happens to be a joke that gets the
-	 * reverse sorted case right, I think.
-	 *
-	 * Damn, it's been _ages_ since I did sort
-	 * routines. I feel like a first-year CS
-	 * student again.
-	 */
-	do {
-		arr2[j] = a;
-		arr1[i] = b;
-		if (--i < 0)
-			break;
-		if (++j == nr2)
-			break;
-		a = arr1[i];
-		b = arr2[j];
-	} while (cmp(a, b) < 0);
-
-	array_sort(arr1, nr1, cmp);
-	array_sort(arr2, nr2, cmp);
-
-	return 1;
+	int i = 0;
+	const void *a;
+	struct ptr_list *head = l;
+
+	while (l->nr == 0) {
+		l = l->next;
+		if (--n == 0)
+			return;
+		assert (l != head);
+	}
+
+	a = l->list[0];
+	while (n > 0) {
+		const void *b;
+		if (++i >= l->nr) {
+			i = 0;
+			l = l->next;
+			n--;
+			assert (l != head || n == 0);
+			continue;
+		}
+		b = l->list[i];
+		assert (cmp (a, b) <= 0);
+		a = b;
+	}
 }
+#endif
+
+
+#define FLUSH_TO(b)						\
+  do {								\
+	int nr = (b)->nr;					\
+	assert (nbuf >= nr);					\
+	memcpy ((b)->list, buffer, nr * sizeof (void *));	\
+	nbuf -= nr;						\
+	memcpy (buffer, buffer + nr, nbuf * sizeof (void *));	\
+  } while (0)
+
+#define DUMP_TO(b)						\
+  do {								\
+        assert (nbuf <= (b)->nr);				\
+	memcpy ((b)->list, buffer, nbuf * sizeof (void *));	\
+  } while (0)
+
 
-void sort_list(struct ptr_list **list, int (*cmp)(const void *, const void *))
+// Merge two already-sorted sequences of blocks:
+//   (b1_1, ..., b1_n)  and  (b2_1, ..., b2_m)
+// Since we may be moving blocks around, we return the new head
+// of the merged list.
+static struct ptr_list *
+merge_block_seqs (struct ptr_list *b1, int n,
+		  struct ptr_list *b2, int m,
+		  int (*cmp)(const void *, const void *))
 {
-	struct ptr_list *head = *list;
+	int i1 = 0, i2 = 0;
+	const void *buffer[2 * LIST_NODE_NR];
+	int nbuf = 0;
+	struct ptr_list *newhead = b1;
 
-	if (head) {
-		int repeat;
+	// printf ("Merging %d blocks at %p with %d blocks at %p\n", n, b1, m, b2);
 
-		/* Sort all the sub-lists */
-		struct ptr_list *list = head, *next;
-		do {
-			array_sort(list->list, list->nr, cmp);
-			list = list->next;
-		} while (list != head);
+	// Skip empty blocks in b2.
+	while (b2->nr == 0) {
+		BEEN_THERE('F');
+		b2 = b2->next;
+		if (--m == 0) {
+			BEEN_THERE('G');
+			return newhead;
+		}
+	}
+
+	// Do a quick skip in case entire blocks from b1 are
+	// already less than smallest element in b2.
+	while (b1->nr == 0 ||
+	       cmp (b1->list[b1->nr - 1], b2->list[0]) < 0) {
+		// printf ("Skipping whole block.\n");
+		BEEN_THERE('H');
+		b1 = b1->next;
+		if (--n == 0) {
+			BEEN_THERE('I');
+			return newhead;	
+		}
+	}
+
+	while (1) {
+		const void *d1 = b1->list[i1];
+		const void *d2 = b2->list[i2];
+
+		assert (i1 >= 0 && i1 < b1->nr);
+		assert (i2 >= 0 && i2 < b2->nr);
+		assert (b1 != b2);
+		assert (n > 0);
+		assert (m > 0);
+
+		if (cmp (d1, d2) <= 0) {
+			BEEN_THERE('J');
+			buffer[nbuf++] = d1;
+			// Element from b1 is smaller
+			if (++i1 >= b1->nr) {
+				BEEN_THERE('L');
+				FLUSH_TO(b1);
+				do {
+					b1 = b1->next;
+					if (--n == 0) {
+						BEEN_THERE('O');
+						while (b1 != b2) {
+							BEEN_THERE('P');
+							FLUSH_TO(b1);
+							b1 = b1->next;
+						}
+						assert (nbuf == i2);
+						DUMP_TO(b2);
+						return newhead;
+					}
+				} while (b1->nr == 0);
+				i1 = 0;
+			}
+		} else {
+			BEEN_THERE('K');
+			// Element from b2 is smaller
+			buffer[nbuf++] = d2;
+			if (++i2 >= b2->nr) {
+				BEEN_THERE('M');
+				// Ok, we finished with b2.  Pull it out
+				// and plug it in before b1.
+				struct ptr_list *l = b2;
+
+				b2 = b2->next;
+				b2->prev = l->prev;
+				b2->prev->next = b2;
+				l->next = b1;
+				l->prev = b1->prev;
+				l->next->prev = l;
+				l->prev->next = l;
+
+				if (b1 == newhead) {
+					BEEN_THERE('N');
+					newhead = l;
+				}
+
+				FLUSH_TO(l);
+				b2 = b2->prev;
+				do {
+					b2 = b2->next;
+					if (--m == 0) {
+						BEEN_THERE('Q');
+						assert (nbuf == i1);
+						DUMP_TO(b1);
+						return newhead;
+					}
+				} while (b2->nr == 0);
+				i2 = 0;
+			}
+		}
+	}
+}
+
+
+void sort_list(struct ptr_list **plist, int (*cmp)(const void *, const void *))
+{
+	struct ptr_list *head = *plist;
+	int blocks = 1;
+
+	if (!head)
+		return;
+
+	// Sort all the sub-lists
+	struct ptr_list *list = head;
+	do {
+		array_sort(list->list, list->nr, cmp);
+#ifdef PARANOIA
+		verify_seq_sorted (list, 1, cmp);
+#endif
+		list = list->next;
+	} while (list != head);
+
+	// Merge the damn things together
+	while (1) {
+		struct ptr_list *block1 = head;
 
-		/* Merge the damn things together .. */
 		do {
-			repeat = 0;
+			struct ptr_list *block2 = block1;
+			struct ptr_list *next, *newhead;
+			int i;
 
-			list = head;
-			next = list->next;
-			while (next != head) {
-				repeat |= merge_array(list->list, list->nr, next->list, next->nr, cmp);
-				list = next;
+			for (i = 0; i < blocks; i++) {
+				block2 = block2->next;
+				if (block2 == head) {
+					if (block1 == head) {
+						BEEN_THERE('A');
+						*plist = head;
+						return;
+					}
+					BEEN_THERE('B');
+					goto next_pass;
+				}						
+			}
+
+			next = block2;
+			for (i = 0; i < blocks; ) {
 				next = next->next;
+				i++;
+				if (next == head) {
+					BEEN_THERE('C');
+					break;
+				}
+				BEEN_THERE('D');
+			}
+
+			newhead = merge_block_seqs (block1, blocks,
+						    block2, i,
+						    cmp);
+#ifdef PARANOIA
+			verify_seq_sorted (newhead, blocks + i, cmp);
+#endif
+			if (block1 == head) {
+				BEEN_THERE('E');
+				head = newhead;
 			}
-		} while (repeat);
+			block1 = next;
+		} while (block1 != head);
+	next_pass:
+		blocks <<= 1;
 	}
 }