[XXX] use merge sort as a fallback for complex geometry.wip/master-tor-merge-sort

1 files changed, 88 insertions, 1 deletions

diff --git a/src/cairo-tor-scan-converter.c b/src/cairo-tor-scan-converter.c
index 1f8160ec..41cb52bc 100644
--- a/src/cairo-tor-scan-converter.c
+++ b/src/cairo-tor-scan-converter.c
@@ -1182,12 +1182,92 @@ active_list_init(struct active_list *active)
     active_list_reset(active);
 }
 
+/* Given two lists A and B in descending order, return
+ * a merged list of A and B in ascending order. */
+static struct edge *
+revmerge_sorted_edges (struct edge *a,
+		       struct edge *b,
+		       int dir)
+{
+    struct edge *c = NULL;
+    while (a && b) {
+	int cmp = a->x.quo > b->x.quo ? dir : -dir;
+	if (cmp > 0) {
+	    struct edge *tmp = a->next;
+	    a->next = c;
+	    c = a;
+	    a = tmp;
+	}
+	else {
+	    struct edge *tmp = b->next;
+	    b->next = c;
+	    c = b;
+	    b = tmp;
+	}
+    }
+    while (a) {
+	struct edge *tmp = a->next;
+	a->next = c;
+	c = a;
+	a = tmp;
+    }
+    while (b) {
+	struct edge *tmp = b->next;
+	b->next = c;
+	c = b;
+	b = tmp;
+    }
+    return c;
+}
+
+static struct edge *
+merge_sort_edges (struct edge *c, int dir)
+{
+    if (c != NULL && c->next != NULL) {
+	struct edge *a = c;
+	struct edge *b = c;
+	b = b->next;
+	while (b) {
+	    b = b->next;
+	    if (b) {
+		b = b->next;
+		c = c->next;
+	    }
+	}
+	b = c->next;
+	c->next = NULL;
+
+	a = merge_sort_edges (a, -dir);
+	b = merge_sort_edges (b, -dir);
+
+	if (dir < 0) {
+	    c = a; a = b; b = c;
+	}
+	return revmerge_sorted_edges(a, b, dir);
+    }
+    return c;
+}
+
+static void
+assert_sorted_edges (struct edge *head)
+{
+#if 0
+    int x = -0x80000000;
+    while (head) {
+	assert(head->x.quo >= x);
+	x = head->x.quo;
+	head = head->next;
+    }
+#endif
+}
+
 /* Merge the edges in an unsorted list of edges into a sorted
  * list. The sort order is edges ascending by edge->x.quo.  Returns
  * the new head of the sorted list. */
 static struct edge *
 merge_unsorted_edges(struct edge *sorted_head, struct edge *unsorted_head)
 {
+    unsigned inversions_until_merge_sort = 2;
     struct edge **cursor = &sorted_head;
     int x;
 
@@ -1204,8 +1284,14 @@ merge_unsorted_edges(struct edge *sorted_head, struct edge *unsorted_head)
 	struct edge *prev = *cursor;
 
 	x = unsorted_head->x.quo;
-	if (x < prev->x.quo)
+	if (x < prev->x.quo) {
+	    if (inversions_until_merge_sort-- == 0) {
+		unsorted_head = merge_sort_edges (unsorted_head, +1);
+		assert_sorted_edges(unsorted_head);
+		continue;
+	    }
 	    cursor = &sorted_head;
+	}
 
 	while (1) {
 	    UNROLL3({
@@ -1221,6 +1307,7 @@ merge_unsorted_edges(struct edge *sorted_head, struct edge *unsorted_head)
 	unsorted_head = next;
     } while (unsorted_head != NULL);
 
+    assert_sorted_edges(sorted_head);
     return sorted_head;
 }