[tessellator] Use a priority queue for the events

The skip list was suffering from severe overhead, so though the search was
quick, the extra copies during insertion and deletion were slow.

6 files changed, 212 insertions, 661 deletions

diff --git a/src/Makefile.am b/src/Makefile.am
index e461fbde..dce2a08e 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -84,12 +84,9 @@ TESTS += check-link$(EXEEXT)
 endif
 
 EXTRA_DIST += $(TESTS_SH) check-has-hidden-symbols.c
-check_PROGRAMS += check-link check-skiplist
+check_PROGRAMS += check-link
 check_link_LDADD = libcairo.la
 
-check_skiplist_SOURCES = cairo-skiplist.c
-check_skiplist_CPPFLAGS = -DMAIN $(AM_CPPFLAGS)
-
 check: headers-standalone
 
 PREPROCESS_ARGS = $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS)
diff --git a/src/Makefile.sources b/src/Makefile.sources
index ca8d51df..b8404e3d 100644
--- a/src/Makefile.sources
+++ b/src/Makefile.sources
@@ -82,7 +82,6 @@ cairo_private = \
 	cairo-region-private.h \
 	cairo-rtree-private.h \
 	cairo-scaled-font-private.h \
-	cairo-skiplist-private.h \
 	cairo-spans-private.h \
 	cairo-surface-fallback-private.h \
 	cairo-surface-private.h \
@@ -136,7 +135,6 @@ cairo_sources = \
 	cairo-region.c \
 	cairo-rtree.c \
 	cairo-scaled-font.c \
-	cairo-skiplist.c \
 	cairo-slope.c \
 	cairo-spans.c \
 	cairo-spline.c \
diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index 66d1a19c..3d3a3d60 100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -38,7 +38,6 @@
 /* Provide definitions for standalone compilation */
 #include "cairoint.h"
 
-#include "cairo-skiplist-private.h"
 #include "cairo-freelist-private.h"
 #include "cairo-combsort-private.h"
 
@@ -59,7 +58,6 @@ typedef struct _cairo_bo_intersect_point {
 } cairo_bo_intersect_point_t;
 
 typedef struct _cairo_bo_edge cairo_bo_edge_t;
-typedef struct _sweep_line_elt sweep_line_elt_t;
 typedef struct _cairo_bo_trap cairo_bo_trap_t;
 
 /* A deferred trapezoid of an edge */
@@ -73,16 +71,14 @@ struct _cairo_bo_edge {
     cairo_bo_edge_t *prev;
     cairo_bo_edge_t *next;
     cairo_bo_trap_t deferred_trap;
-    sweep_line_elt_t *sweep_line_elt;
 };
 
-struct _sweep_line_elt {
-    cairo_bo_edge_t *edge;
-    skip_elt_t elt;
-};
+/* the parent is always given by index/2 */
+#define PQ_PARENT_INDEX(i) ((i) >> 1)
+#define PQ_FIRST_ENTRY 1
 
-#define SKIP_ELT_TO_EDGE_ELT(elt)	SKIP_LIST_ELT_TO_DATA (sweep_line_elt_t, (elt))
-#define SKIP_ELT_TO_EDGE(elt)		(SKIP_ELT_TO_EDGE_ELT (elt)->edge)
+/* left and right children are index * 2 and (index * 2) +1 respectively */
+#define PQ_LEFT_CHILD_INDEX(i) ((i) << 1)
 
 typedef enum {
     CAIRO_BO_EVENT_TYPE_STOP,
@@ -101,23 +97,26 @@ typedef struct _cairo_bo_start_event {
     cairo_bo_edge_t edge;
 } cairo_bo_start_event_t;
 
-typedef struct _cairo_bo_skiplist_event {
+typedef struct _cairo_bo_queue_event {
     cairo_bo_event_type_t type;
     cairo_point_t point;
     cairo_bo_edge_t *e1;
     cairo_bo_edge_t *e2;
-    skip_elt_t elt;
-} cairo_bo_skiplist_event_t;
+} cairo_bo_queue_event_t;
 
-#define SKIP_ELT_TO_EVENT(elt) ((cairo_bo_event_t *) SKIP_LIST_ELT_TO_DATA (cairo_bo_skiplist_event_t, (elt)))
+typedef struct _pqueue {
+    int size, max_size;
 
-typedef struct _cairo_bo_event_queue {
-    cairo_skip_list_t event_queue;
+    cairo_bo_event_t **elements;
+    cairo_bo_event_t *elements_embedded[1024];
+} pqueue_t;
 
+typedef struct _cairo_bo_event_queue {
+    cairo_freepool_t pool;
+    pqueue_t pqueue;
     cairo_bo_event_t **start_events;
 } cairo_bo_event_queue_t;
 
-/* This structure extends #cairo_skip_list_t, which must come first. */
 typedef struct _cairo_bo_sweep_line {
     cairo_bo_edge_t *head;
     cairo_bo_edge_t *stopped;
@@ -599,44 +598,10 @@ _cairo_bo_sweep_line_compare_edges (cairo_bo_sweep_line_t	*sweep_line,
 	cmp = _slope_compare (a, b);
 	if (cmp)
 	    return cmp;
-
-	/* We've got two collinear edges now. */
-
-	/* Since we're dealing with start events, prefer comparing top
-	 * edges before bottom edges. */
-	cmp = a->edge.top - b->edge.top;
-	if (cmp)
-	    return cmp;
-
-	cmp = a->edge.bottom - b->edge.bottom;
-	if (cmp)
-	    return cmp;
     }
 
-    return 0;
-}
-
-static inline int
-cairo_bo_event_compare (const cairo_bo_event_t *a,
-			const cairo_bo_event_t *b)
-{
-    int cmp;
-
-    cmp = _cairo_bo_point32_compare (&a->point, &b->point);
-    if (cmp)
-	return cmp;
-
-    cmp = a->type - b->type;
-    if (cmp)
-	return cmp;
-
-    return a - b;
-}
-
-static int
-cairo_bo_event_compare_skiplist (void *list, const void *a, const void *b)
-{
-    return cairo_bo_event_compare (a, b);
+    /* We've got two collinear edges now. */
+    return b->edge.bottom - a->edge.bottom;
 }
 
 static inline cairo_int64_t
@@ -687,8 +652,6 @@ intersect_lines (cairo_bo_edge_t		*a,
     cairo_quorem64_t qr;
 
     den_det = det32_64 (dx1, dy1, dx2, dy2);
-    if (_cairo_int64_is_zero (den_det))
-	return FALSE;
 
      /* Q: Can we determine that the lines do not intersect (within range)
       * much more cheaply than computing the intersection point i.e. by
@@ -712,10 +675,6 @@ intersect_lines (cairo_bo_edge_t		*a,
     R = det32_64 (dx2, dy2,
 		  b->edge.line.p1.x - a->edge.line.p1.x,
 		  b->edge.line.p1.y - a->edge.line.p1.y);
-    if (_cairo_int64_is_zero (R))
-	return FALSE;
-    if (_cairo_int64_negative (den_det) ^ _cairo_int64_negative (R))
-	return FALSE;
     if (_cairo_int64_negative (den_det)) {
 	if (_cairo_int64_ge (den_det, R))
 	    return FALSE;
@@ -727,10 +686,6 @@ intersect_lines (cairo_bo_edge_t		*a,
     R = det32_64 (dy1, dx1,
 		  a->edge.line.p1.y - b->edge.line.p1.y,
 		  a->edge.line.p1.x - b->edge.line.p1.x);
-    if (_cairo_int64_is_zero (R))
-	return FALSE;
-    if (_cairo_int64_negative (den_det) ^ _cairo_int64_negative (R))
-	return FALSE;
     if (_cairo_int64_negative (den_det)) {
 	if (_cairo_int64_ge (den_det, R))
 	    return FALSE;
@@ -923,49 +878,161 @@ _cairo_bo_edge_intersect (cairo_bo_edge_t	*a,
     return TRUE;
 }
 
-static void
-_cairo_bo_skiplist_event_init (cairo_bo_skiplist_event_t *event,
-			       cairo_bo_event_type_t	 type,
-			       cairo_bo_edge_t		*e1,
-			       cairo_bo_edge_t		*e2,
-			       const cairo_point_t	 *point)
+static inline int
+cairo_bo_event_compare (const cairo_bo_event_t *a,
+			const cairo_bo_event_t *b)
 {
-    event->type = type;
-    event->e1 = e1;
-    event->e2 = e2;
-    event->point = *point;
+    int cmp;
+
+    cmp = _cairo_bo_point32_compare (&a->point, &b->point);
+    if (cmp)
+	return cmp;
+
+    cmp = a->type - b->type;
+    if (cmp)
+	return cmp;
+
+    return a - b;
+}
+
+static inline void
+_pqueue_init (pqueue_t *pq)
+{
+    pq->max_size = ARRAY_LENGTH (pq->elements_embedded);
+    pq->size = 0;
+
+    pq->elements = pq->elements_embedded;
+}
+
+static inline void
+_pqueue_fini (pqueue_t *pq)
+{
+    if (pq->elements != pq->elements_embedded)
+	free (pq->elements);
 }
 
 static cairo_status_t
-_cairo_bo_event_queue_insert (cairo_bo_event_queue_t *queue,
-			      cairo_bo_skiplist_event_t *event)
+_pqueue_grow (pqueue_t *pq)
 {
-    cairo_status_t status = CAIRO_STATUS_SUCCESS;
+    cairo_bo_event_t **new_elements;
+    pq->max_size *= 2;
 
-    /* Only insert if there is no prior identical intersection event. */
-    if (unlikely (_cairo_skip_list_insert (&queue->event_queue, event) == NULL))
-	status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
+    if (pq->elements == pq->elements_embedded) {
+	new_elements = _cairo_malloc_ab (pq->max_size,
+					 sizeof (cairo_bo_event_t *));
+	if (unlikely (new_elements == NULL))
+	    return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 
-    return status;
+	memcpy (new_elements, pq->elements_embedded,
+		sizeof (pq->elements_embedded));
+    } else {
+	new_elements = _cairo_realloc_ab (pq->elements,
+					  pq->max_size,
+					  sizeof (cairo_bo_event_t *));
+	if (unlikely (new_elements == NULL))
+	    return _cairo_error (CAIRO_STATUS_NO_MEMORY);
+    }
+
+    pq->elements = new_elements;
+    return CAIRO_STATUS_SUCCESS;
+}
+
+static inline cairo_status_t
+_pqueue_push (pqueue_t *pq, cairo_bo_event_t *event)
+{
+    cairo_bo_event_t **elements;
+    int i, parent;
+
+    if (unlikely (pq->size + 1 == pq->max_size)) {
+	cairo_status_t status;
+
+	status = _pqueue_grow (pq);
+	if (unlikely (status))
+	    return status;
+    }
+
+    elements = pq->elements;
+
+    for (i = ++pq->size;
+	 i != PQ_FIRST_ENTRY &&
+	 cairo_bo_event_compare (event,
+				 elements[parent = PQ_PARENT_INDEX (i)]) < 0;
+	 i = parent)
+    {
+	elements[i] = elements[parent];
+    }
+
+    elements[i] = event;
+
+    return CAIRO_STATUS_SUCCESS;
+}
+
+static inline void
+_pqueue_pop (pqueue_t *pq)
+{
+    cairo_bo_event_t **elements = pq->elements;
+    cairo_bo_event_t *tail;
+    int child, i;
+
+    tail = elements[pq->size--];
+    if (pq->size == 0) {
+	elements[PQ_FIRST_ENTRY] = NULL;
+	return;
+    }
+
+    for (i = PQ_FIRST_ENTRY;
+	 (child = PQ_LEFT_CHILD_INDEX (i)) <= pq->size;
+	 i = child)
+    {
+	if (child != pq->size &&
+	    cairo_bo_event_compare (elements[child+1],
+				    elements[child]) < 0)
+	{
+	    child++;
+	}
+
+	if (cairo_bo_event_compare (elements[child], tail) >= 0)
+	    break;
+
+	elements[i] = elements[child];
+    }
+    elements[i] = tail;
+}
+
+static inline cairo_status_t
+_cairo_bo_event_queue_insert (cairo_bo_event_queue_t	*queue,
+			      cairo_bo_event_type_t	 type,
+			      cairo_bo_edge_t		*e1,
+			      cairo_bo_edge_t		*e2,
+			      const cairo_point_t	 *point)
+{
+    cairo_bo_queue_event_t *event;
+
+    event = _cairo_freepool_alloc (&queue->pool);
+    if (unlikely (event == NULL))
+	return _cairo_error (CAIRO_STATUS_NO_MEMORY);
+
+    event->type = type;
+    event->e1 = e1;
+    event->e2 = e2;
+    event->point = *point;
+
+    return _pqueue_push (&queue->pqueue, (cairo_bo_event_t *) event);
 }
 
 static void
 _cairo_bo_event_queue_delete (cairo_bo_event_queue_t *queue,
 			      cairo_bo_event_t	     *event)
 {
-    _cairo_skip_list_delete_given (&queue->event_queue,
-				   &((cairo_bo_skiplist_event_t *) event)->elt);
+    _cairo_freepool_free (&queue->pool, event);
 }
 
-#define NEXT_EVENT(Q) \
-    ((Q)->chains[0] ?  SKIP_ELT_TO_EVENT ((Q)->chains[0]) : NULL)
 static cairo_bo_event_t *
 _cairo_bo_event_dequeue (cairo_bo_event_queue_t *event_queue)
 {
     cairo_bo_event_t *event, *cmp;
 
-    event = NEXT_EVENT (&event_queue->event_queue);
-
+    event = event_queue->pqueue.elements[PQ_FIRST_ENTRY];
     cmp = *event_queue->start_events;
     if (event == NULL ||
 	(cmp != NULL && cairo_bo_event_compare (cmp, event) < 0))
@@ -973,6 +1040,10 @@ _cairo_bo_event_dequeue (cairo_bo_event_queue_t *event_queue)
 	event = cmp;
 	event_queue->start_events++;
     }
+    else
+    {
+	_pqueue_pop (&event_queue->pqueue);
+    }
 
     return event;
 }
@@ -991,9 +1062,10 @@ _cairo_bo_event_queue_init (cairo_bo_event_queue_t	 *event_queue,
 
     event_queue->start_events = start_events;
 
-    _cairo_skip_list_init (&event_queue->event_queue,
-			   cairo_bo_event_compare_skiplist,
-			   sizeof (cairo_bo_skiplist_event_t));
+    _cairo_freepool_init (&event_queue->pool,
+			  sizeof (cairo_bo_queue_event_t));
+    _pqueue_init (&event_queue->pqueue);
+    event_queue->pqueue.elements[PQ_FIRST_ENTRY] = NULL;
 }
 
 static cairo_status_t
@@ -1001,23 +1073,21 @@ _cairo_bo_event_queue_insert_stop (cairo_bo_event_queue_t	*event_queue,
 				   cairo_bo_edge_t		*edge)
 {
     cairo_bo_point32_t point;
-    cairo_bo_skiplist_event_t event;
 
     point.y = edge->edge.bottom;
     point.x = _line_compute_intersection_x_for_y (&edge->edge.line,
 						  point.y);
-    _cairo_bo_skiplist_event_init (&event,
-				   CAIRO_BO_EVENT_TYPE_STOP,
-				   edge, NULL,
-				   &point);
-
-    return _cairo_bo_event_queue_insert (event_queue, &event);
+    return _cairo_bo_event_queue_insert (event_queue,
+					 CAIRO_BO_EVENT_TYPE_STOP,
+					 edge, NULL,
+					 &point);
 }
 
 static void
 _cairo_bo_event_queue_fini (cairo_bo_event_queue_t *event_queue)
 {
-    _cairo_skip_list_fini (&event_queue->event_queue);
+    _pqueue_fini (&event_queue->pqueue);
+    _cairo_freepool_fini (&event_queue->pool);
 }
 
 static inline cairo_status_t
@@ -1026,10 +1096,6 @@ _cairo_bo_event_queue_insert_if_intersect_below_current_y (cairo_bo_event_queue_
 							   cairo_bo_edge_t *right)
 {
     cairo_bo_point32_t intersection;
-    cairo_bo_skiplist_event_t event;
-
-    if (left == NULL || right == NULL)
-	return CAIRO_STATUS_SUCCESS;
 
     if (_line_equal (&left->edge.line, &right->edge.line))
 	return CAIRO_STATUS_SUCCESS;
@@ -1045,12 +1111,10 @@ _cairo_bo_event_queue_insert_if_intersect_below_current_y (cairo_bo_event_queue_
     if (! _cairo_bo_edge_intersect (left, right, &intersection))
 	return CAIRO_STATUS_SUCCESS;
 
-    _cairo_bo_skiplist_event_init (&event,
-				   CAIRO_BO_EVENT_TYPE_INTERSECTION,
-				   left, right,
-				   &intersection);
-
-    return _cairo_bo_event_queue_insert (event_queue, &event);
+    return _cairo_bo_event_queue_insert (event_queue,
+					 CAIRO_BO_EVENT_TYPE_INTERSECTION,
+					 left, right,
+					 &intersection);
 }
 
 static void
@@ -1088,7 +1152,7 @@ _cairo_bo_sweep_line_insert (cairo_bo_sweep_line_t	*sweep_line,
 	    edge->next = next;
 	    if (next != NULL)
 		next->prev = edge;
-	} else {
+	} else if (cmp > 0) {
 	    next = sweep_line->current_edge;
 	    prev = next->prev;
 	    while (prev != NULL &&
@@ -1105,6 +1169,13 @@ _cairo_bo_sweep_line_insert (cairo_bo_sweep_line_t	*sweep_line,
 		prev->next = edge;
 	    else
 		sweep_line->head = edge;
+	} else {
+	    prev = sweep_line->current_edge;
+	    edge->prev = prev;
+	    edge->next = prev->next;
+	    if (prev->next != NULL)
+		prev->next->prev = edge;
+	    prev->next = edge;
 	}
     } else {
 	sweep_line->head = edge;
@@ -1186,22 +1257,14 @@ _cairo_bo_event_print (cairo_bo_event_t *event)
 static void
 _cairo_bo_event_queue_print (cairo_bo_event_queue_t *event_queue)
 {
-    skip_elt_t *elt;
-
     /* XXX: fixme to print the start/stop array too. */
-    cairo_skip_list_t *queue = &event_queue->event_queue;
-
     printf ("Event queue:\n");
-
-    for (elt = queue->chains[0]; elt; elt = elt->next[0])
-	_cairo_bo_event_print (SKIP_ELT_TO_EVENT (elt));
 }
 
 static void
 _cairo_bo_sweep_line_print (cairo_bo_sweep_line_t *sweep_line)
 {
     cairo_bool_t first = TRUE;
-    skip_elt_t *elt;
     cairo_bo_edge_t *edge;
 
     printf ("Sweep line from edge list: ");
@@ -1578,18 +1641,22 @@ _cairo_bentley_ottmann_tessellate_bo_edges (cairo_bo_event_t   **start_events,
 	    left = e1->prev;
 	    right = e1->next;
 
-	    status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, left, e1);
-	    if (unlikely (status))
-		goto unwind;
+	    if (left != NULL) {
+		status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, left, e1);
+		if (unlikely (status))
+		    goto unwind;
+	    }
 
-	    status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, e1, right);
-	    if (unlikely (status))
-		goto unwind;
+	    if (right != NULL) {
+		status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, e1, right);
+		if (unlikely (status))
+		    goto unwind;
+	    }
 
 	    break;
 
 	case CAIRO_BO_EVENT_TYPE_STOP:
-	    e1 = ((cairo_bo_skiplist_event_t *) event)->e1;
+	    e1 = ((cairo_bo_queue_event_t *) event)->e1;
 	    _cairo_bo_event_queue_delete (&event_queue, event);
 
 	    left = e1->prev;
@@ -1606,15 +1673,17 @@ _cairo_bentley_ottmann_tessellate_bo_edges (cairo_bo_event_t   **start_events,
 		e1->prev = NULL;
 	    }
 
-	    status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, left, right);
-	    if (unlikely (status))
-		goto unwind;
+	    if (left != NULL && right != NULL) {
+		status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, left, right);
+		if (unlikely (status))
+		    goto unwind;
+	    }
 
 	    break;
 
 	case CAIRO_BO_EVENT_TYPE_INTERSECTION:
-	    e1 = ((cairo_bo_skiplist_event_t *) event)->e1;
-	    e2 = ((cairo_bo_skiplist_event_t *) event)->e2;
+	    e1 = ((cairo_bo_queue_event_t *) event)->e1;
+	    e2 = ((cairo_bo_queue_event_t *) event)->e2;
 	    _cairo_bo_event_queue_delete (&event_queue, event);
 
 	    /* skip this intersection if its edges are not adjacent */
@@ -1630,13 +1699,17 @@ _cairo_bentley_ottmann_tessellate_bo_edges (cairo_bo_event_t   **start_events,
 
 	    /* after the swap e2 is left of e1 */
 
-	    status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, left, e2);
-	    if (unlikely (status))
-		goto unwind;
+	    if (left != NULL) {
+		status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, left, e2);
+		if (unlikely (status))
+		    goto unwind;
+	    }
 
-	    status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, e1, right);
-	    if (unlikely (status))
-		goto unwind;
+	    if (right != NULL) {
+		status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, e1, right);
+		if (unlikely (status))
+		    goto unwind;
+	    }
 
 	    break;
 	}
@@ -1704,7 +1777,6 @@ _cairo_bentley_ottmann_tessellate_polygon (cairo_traps_t	 *traps,
 	events[i].edge.deferred_trap.right = NULL;
 	events[i].edge.prev = NULL;
 	events[i].edge.next = NULL;
-	events[i].edge.sweep_line_elt = NULL;
     }
 
 #if DEBUG_TRAPS
@@ -1765,7 +1837,6 @@ _add_event (const cairo_line_t *line,
     event->edge.deferred_trap.right = NULL;
     event->edge.prev = NULL;
     event->edge.next = NULL;
-    event->edge.sweep_line_elt = NULL;
 
     return 1;
 }
diff --git a/src/cairo-freelist.c b/src/cairo-freelist.c
index 83647f20..6bbee844 100644
--- a/src/cairo-freelist.c
+++ b/src/cairo-freelist.c
@@ -104,8 +104,9 @@ _cairo_freepool_init (cairo_freepool_t *freepool, unsigned nodesize)
 
 	node->next = freepool->first_free_node;
 	freepool->first_free_node = node;
-	VG (VALGRIND_MAKE_MEM_NOACCESS (node, freepool->nodesize));
     }
+    VG (VALGRIND_MAKE_MEM_NOACCESS (freepool->embedded_pool,
+				    sizeof (freepool->embedded_pool)));
 }
 
 void
@@ -133,7 +134,7 @@ _cairo_freepool_alloc_from_new_pool (cairo_freepool_t *freepool)
 
     poolsize = (128 * freepool->nodesize + 8191) & -8192;
     node = malloc (poolsize);
-    if (node == NULL)
+    if (unlikely (node == NULL))
 	return node;
 
     node->next = freepool->pools;
@@ -150,8 +151,9 @@ _cairo_freepool_alloc_from_new_pool (cairo_freepool_t *freepool)
 
 	node->next = freepool->first_free_node;
 	freepool->first_free_node = node;
-	VG (VALGRIND_MAKE_MEM_NOACCESS (node, freepool->nodesize));
     }
+    VG (VALGRIND_MAKE_MEM_NOACCESS (freepool->pools,
+				    (128 * freepool->nodesize + 8191) & -8192));
 
     return ptr;
 }
diff --git a/src/cairo-skiplist-private.h b/src/cairo-skiplist-private.h
deleted file mode 100644
index c0e5bce5..00000000
--- a/src/cairo-skiplist-private.h
+++ /dev/null
@@ -1,118 +0,0 @@
-/*
- * Copyright © 2006 Keith Packard
- * Copyright © 2006 Carl Worth
- *
- * Permission to use, copy, modify, distribute, and sell this software and its
- * documentation for any purpose is hereby granted without fee, provided that
- * the above copyright notice appear in all copies and that both that copyright
- * notice and this permission notice appear in supporting documentation, and
- * that the name of the copyright holders not be used in advertising or
- * publicity pertaining to distribution of the software without specific,
- * written prior permission.  The copyright holders make no representations
- * about the suitability of this software for any purpose.  It is provided "as
- * is" without express or implied warranty.
- *
- * THE COPYRIGHT HOLDERS DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
- * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
- * EVENT SHALL THE COPYRIGHT HOLDERS BE LIABLE FOR ANY SPECIAL, INDIRECT OR
- * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
- * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
- * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE
- * OF THIS SOFTWARE.
- */
-
-#ifndef SKIPLIST_H
-#define SKIPLIST_H
-
-#include "cairoint.h"
-
-/*
- * Skip lists are described in detail here:
- *
- *   http://citeseer.ist.psu.edu/pugh90skip.html
- */
-
-/* Note that random_level() called from alloc_node_for_level() depends on
- * this being not more than 16.
- */
-#define MAX_LEVEL   15
-
-/* Returns the index of the free-list to use for a node at level 'level' */
-#define FREELIST_FOR_LEVEL(level) (((level) - 1) / 2)
-
-/* Returns the maximum level that uses the same free-list as 'level' does */
-#define FREELIST_MAX_LEVEL_FOR(level) (((level) + 1) & ~1)
-
-#define MAX_FREELIST_LEVEL (FREELIST_FOR_LEVEL (MAX_LEVEL - 1) + 1)
-
-/*
- * Skip list element. In order to use the skip list, the caller must
- * generate a structure for list elements that has as its final member
- * a skip_elt_t, (which will be allocated with variable size).
- *
- * The caller must also pass the size of the structure to
- * _cairo_skip_list_init.
- */
-typedef struct _skip_elt {
-    int prev_index;
-    struct _skip_elt *prev;
-    struct _skip_elt *next[1];
-} skip_elt_t;
-
-#define SKIP_LIST_ELT_TO_DATA(type, elt) ((type *) ((char *) (elt) - (sizeof (type) - sizeof (skip_elt_t))))
-
-typedef int
-(*cairo_skip_list_compare_t) (void *list, const void *a, const void *b);
-
-typedef struct _skip_list {
-    cairo_skip_list_compare_t compare;
-    size_t elt_size;
-    size_t data_size;
-    skip_elt_t *chains[MAX_LEVEL];
-    skip_elt_t *freelists[MAX_FREELIST_LEVEL];
-    int		max_level;
-    struct pool *pool;
-    char pool_embedded[1024];
-} cairo_skip_list_t;
-
-/* Initialize a new skip list. The compare function accepts a pointer
- * to the list as well as pointers to two elements. The function must
- * return a value greater than zero, zero, or less then 0 if the first
- * element is considered respectively greater than, equal to, or less
- * than the second element. The size of each object, (as computed by
- * sizeof) is passed for elt_size. Note that the structure used for
- * list elements must have as its final member a skip_elt_t
- */
-cairo_private void
-_cairo_skip_list_init (cairo_skip_list_t		*list,
-		       cairo_skip_list_compare_t	 compare,
-		       size_t			 elt_size);
-
-
-/* Deallocate resources associated with a skip list and all elements
- * in it. (XXX: currently this simply deletes all elements.)
- */
-cairo_private void
-_cairo_skip_list_fini (cairo_skip_list_t		*list);
-
-/* Insert a new element into the list at the correct sort order as
- * determined by compare. If unique is true, then duplicate elements
- * are ignored and the already inserted element is returned.
- * Otherwise data will be copied (elt_size bytes from <data> via
- * memcpy) and the new element is returned. */
-cairo_private void *
-_cairo_skip_list_insert (cairo_skip_list_t *list, void *data);
-
-/* Find an element which compare considers equal to <data> */
-cairo_private void *
-_cairo_skip_list_find (cairo_skip_list_t *list, void *data);
-
-/* Delete an element which compare considers equal to <data> */
-cairo_private void
-_cairo_skip_list_delete (cairo_skip_list_t *list, void *data);
-
-/* Delete the given element from the list. */
-cairo_private void
-_cairo_skip_list_delete_given (cairo_skip_list_t *list, skip_elt_t *given);
-
-#endif
diff --git a/src/cairo-skiplist.c b/src/cairo-skiplist.c
deleted file mode 100644
index 8d8c8d1f..00000000
--- a/src/cairo-skiplist.c
+++ /dev/null
@@ -1,399 +0,0 @@
-/*
- * Copyright © 2006 Keith Packard
- * Copyright © 2006 Carl Worth
- *
- * Permission to use, copy, modify, distribute, and sell this software and its
- * documentation for any purpose is hereby granted without fee, provided that
- * the above copyright notice appear in all copies and that both that copyright
- * notice and this permission notice appear in supporting documentation, and
- * that the name of the copyright holders not be used in advertising or
- * publicity pertaining to distribution of the software without specific,
- * written prior permission.  The copyright holders make no representations
- * about the suitability of this software for any purpose.  It is provided "as
- * is" without express or implied warranty.
- *
- * THE COPYRIGHT HOLDERS DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
- * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
- * EVENT SHALL THE COPYRIGHT HOLDERS BE LIABLE FOR ANY SPECIAL, INDIRECT OR
- * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
- * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
- * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE
- * OF THIS SOFTWARE.
- */
-
-#include "cairoint.h"
-
-#include "cairo-skiplist-private.h"
-
-#if HAVE_FFS
-#include <strings.h> /* ffs() */
-#endif
-
-#define ELT_DATA(elt) (void *)	((char*) (elt) - list->data_size)
-#define NEXT_TO_ELT(next)	(skip_elt_t *) ((char *) (next) - offsetof (skip_elt_t, next))
-
-static uint32_t
-hars_petruska_f54_1_random (void)
-{
-#  define rol(x,k) ((x << k) | (x >> (32-k)))
-    static uint32_t x = 0;
-    x = (x ^ rol(x, 5) ^ rol(x, 24)) + 0x37798849;
-    return x;
-#  undef rol
-}
-
-struct pool {
-    struct pool *next;
-    char *ptr;
-    unsigned int rem;
-};
-
-static struct pool *
-pool_new (void)
-{
-    struct pool *pool;
-
-    pool = malloc (8192 - 8);
-    if (unlikely (pool == NULL))
-	return NULL;
-
-    pool->next = NULL;
-    pool->rem = 8192 - 8 - sizeof (struct pool);
-    pool->ptr = (char *) (pool + 1);
-
-    return pool;
-}
-
-static void
-pools_destroy (struct pool *pool)
-{
-    while (pool->next != NULL) {
-	struct pool *next = pool->next;
-	free (pool);
-	pool = next;
-    }
-}
-
-/*
- * Initialize an empty skip list
- */
-void
-_cairo_skip_list_init (cairo_skip_list_t	*list,
-                       cairo_skip_list_compare_t compare,
-                       size_t			 elt_size)
-{
-    int i;
-
-    list->compare = compare;
-    list->elt_size = elt_size;
-    list->data_size = elt_size - sizeof (skip_elt_t);
-    list->pool = (struct pool *) list->pool_embedded;
-    list->pool->next = NULL;
-    list->pool->rem = sizeof (list->pool_embedded) - sizeof (struct pool);
-    list->pool->ptr = list->pool_embedded + sizeof (struct pool);
-
-    for (i = 0; i < MAX_LEVEL; i++) {
-	list->chains[i] = NULL;
-    }
-
-    for (i = 0; i < MAX_FREELIST_LEVEL; i++) {
-	list->freelists[i] = NULL;
-    }
-
-    list->max_level = 0;
-}
-
-void
-_cairo_skip_list_fini (cairo_skip_list_t *list)
-{
-    pools_destroy (list->pool);
-}
-
-/*
- * Generate a random level number, distributed
- * so that each level is 1/4 as likely as the one before
- *
- * Note that level numbers run 1 <= level < MAX_LEVEL
- */
-static int
-random_level (void)
-{
-    /* tricky bit -- each bit is '1' 75% of the time.
-     * This works because we only use the lower MAX_LEVEL
-     * bits, and MAX_LEVEL < 16 */
-    uint32_t bits = hars_petruska_f54_1_random ();
-#if HAVE_FFS
-    return ffs (-(1<<MAX_LEVEL) | bits | bits >> 16);
-#else
-    int level = 1;
-
-    bits |= -(1<<MAX_LEVEL) | bits >> 16;
-    while ((bits & 1) == 0) {
-	level++;
-	bits >>= 1;
-    }
-    return level;
-#endif
-}
-
-static void *
-pool_alloc (cairo_skip_list_t *list,
-	    unsigned int level)
-{
-    unsigned int size;
-    struct pool *pool;
-    void *ptr;
-
-    size = list->elt_size +
-	(FREELIST_MAX_LEVEL_FOR (level) - 1) * sizeof (skip_elt_t *);
-
-    pool = list->pool;
-    if (size > pool->rem) {
-	pool = pool_new ();
-	if (unlikely (pool == NULL))
-	    return NULL;
-
-	pool->next = list->pool;
-	list->pool = pool;
-    }
-
-    ptr = pool->ptr;
-    pool->ptr += size;
-    pool->rem -= size;
-
-    return ptr;
-}
-
-static void *
-alloc_node_for_level (cairo_skip_list_t *list, unsigned level)
-{
-    int freelist_level = FREELIST_FOR_LEVEL (level);
-    if (list->freelists[freelist_level]) {
-	skip_elt_t *elt = list->freelists[freelist_level];
-	list->freelists[freelist_level] = elt->prev;
-	return ELT_DATA(elt);
-    }
-    return pool_alloc (list, level);
-}
-
-static void
-free_elt (cairo_skip_list_t *list, skip_elt_t *elt)
-{
-    int level = elt->prev_index + 1;
-    int freelist_level = FREELIST_FOR_LEVEL (level);
-    elt->prev = list->freelists[freelist_level];
-    list->freelists[freelist_level] = elt;
-}
-
-/*
- * Insert 'data' into the list
- */
-void *
-_cairo_skip_list_insert (cairo_skip_list_t *list, void *data)
-{
-    skip_elt_t **update[MAX_LEVEL];
-    skip_elt_t *prev[MAX_LEVEL];
-    char *data_and_elt;
-    skip_elt_t *elt, **next;
-    int	    i, level, prev_index;
-
-    /*
-     * Find links along each chain
-     */
-    elt = NULL;
-    next = list->chains;
-    for (i = list->max_level; --i >= 0; )
-    {
-	if (elt != next[i])
-	{
-	    for (; (elt = next[i]); next = elt->next)
-	    {
-		int cmp = list->compare (list, ELT_DATA(elt), data);
-		if (0 == cmp)
-		    return ELT_DATA(elt);
-		if (cmp > 0)
-		    break;
-	    }
-	}
-        update[i] = next;
-	if (next != list->chains)
-	    prev[i] = NEXT_TO_ELT (next);
-	else
-	    prev[i] = NULL;
-    }
-    level = random_level ();
-    prev_index = level - 1;
-
-    /*
-     * Create new list element
-     */
-    if (level > list->max_level)
-    {
-	level = list->max_level + 1;
-	prev_index = level - 1;
-	prev[prev_index] = NULL;
-	update[list->max_level] = list->chains;
-	list->max_level = level;
-    }
-
-    data_and_elt = alloc_node_for_level (list, level);
-    if (unlikely (data_and_elt == NULL)) {
-	_cairo_error_throw (CAIRO_STATUS_NO_MEMORY);
-	return NULL;
-    }
-
-    memcpy (data_and_elt, data, list->data_size);
-    elt = (skip_elt_t *) (data_and_elt + list->data_size);
-
-    elt->prev_index = prev_index;
-    elt->prev = prev[prev_index];
-
-    /*
-     * Insert into all chains
-     */
-    for (i = 0; i < level; i++)
-    {
-	elt->next[i] = update[i][i];
-	if (elt->next[i] && elt->next[i]->prev_index == i)
-	    elt->next[i]->prev = elt;
-	update[i][i] = elt;
-    }
-
-    return data_and_elt;
-}
-
-void *
-_cairo_skip_list_find (cairo_skip_list_t *list, void *data)
-{
-    int i;
-    skip_elt_t **next = list->chains;
-    skip_elt_t *elt;
-
-    /*
-     * Walk chain pointers one level at a time
-     */
-    for (i = list->max_level; --i >= 0;)
-	while (next[i] && list->compare (list, data, ELT_DATA(next[i])) > 0)
-	{
-	    next = next[i]->next;
-	}
-    /*
-     * Here we are
-     */
-    elt = next[0];
-    if (elt && list->compare (list, data, ELT_DATA (elt)) == 0)
-	return ELT_DATA (elt);
-
-    return NULL;
-}
-
-void
-_cairo_skip_list_delete (cairo_skip_list_t *list, void *data)
-{
-    skip_elt_t **update[MAX_LEVEL], *prev[MAX_LEVEL];
-    skip_elt_t *elt, **next;
-    int	i;
-
-    /*
-     * Find links along each chain
-     */
-    next = list->chains;
-    for (i = list->max_level; --i >= 0; )
-    {
-	for (; (elt = next[i]); next = elt->next)
-	{
-	    if (list->compare (list, ELT_DATA (elt), data) >= 0)
-		break;
-	}
-        update[i] = &next[i];
-	if (next == list->chains)
-	    prev[i] = NULL;
-	else
-	    prev[i] = NEXT_TO_ELT (next);
-    }
-    elt = next[0];
-    assert (list->compare (list, ELT_DATA (elt), data) == 0);
-    for (i = 0; i < list->max_level && *update[i] == elt; i++) {
-	*update[i] = elt->next[i];
-	if (elt->next[i] && elt->next[i]->prev_index == i)
-	    elt->next[i]->prev = prev[i];
-    }
-    while (list->max_level > 0 && list->chains[list->max_level - 1] == NULL)
-	list->max_level--;
-    free_elt (list, elt);
-}
-
-void
-_cairo_skip_list_delete_given (cairo_skip_list_t *list, skip_elt_t *given)
-{
-    skip_elt_t **update[MAX_LEVEL], *prev[MAX_LEVEL];
-    skip_elt_t *elt, **next;
-    int	i;
-
-    /*
-     * Find links along each chain
-     */
-    if (given->prev)
-	next = given->prev->next;
-    else
-	next = list->chains;
-    for (i = given->prev_index + 1; --i >= 0; )
-    {
-	for (; (elt = next[i]); next = elt->next)
-	{
-	    if (elt == given)
-		break;
-	}
-        update[i] = &next[i];
-	if (next == list->chains)
-	    prev[i] = NULL;
-	else
-	    prev[i] = NEXT_TO_ELT (next);
-    }
-    elt = next[0];
-    assert (elt == given);
-    for (i = 0; i < (given->prev_index + 1) && *update[i] == elt; i++) {
-	*update[i] = elt->next[i];
-	if (elt->next[i] && elt->next[i]->prev_index == i)
-	    elt->next[i]->prev = prev[i];
-    }
-    while (list->max_level > 0 && list->chains[list->max_level - 1] == NULL)
-	list->max_level--;
-    free_elt (list, elt);
-}
-
-#if MAIN
-typedef struct {
-    int n;
-    skip_elt_t elt;
-} test_elt_t;
-
-static int
-test_cmp (void *list, const void *A, const void *B)
-{
-    const test_elt_t *a = A, *b = B;
-    return a->n - b->n;
-}
-
-int
-main (void)
-{
-    cairo_skip_list_t list;
-    test_elt_t elt;
-    int n;
-
-    _cairo_skip_list_init (&list, test_cmp, sizeof (test_elt_t));
-    for (n = 0; n < 10000000; n++) {
-	void *elt_and_data;
-	elt.n = n;
-	elt_and_data = _cairo_skip_list_insert (&list, &elt);
-	assert (elt_and_data != NULL);
-    }
-    _cairo_skip_list_fini (&list);
-
-    return 0;
-}
-
-/* required supporting stubs */
-cairo_status_t _cairo_error (cairo_status_t status) { return status; }
-#endif