[skiplist] Provide an initial stack allocated pool.

Since we only need to allocate elts for intersection events and edges, the
number of elts in flight at any one time is actually quite small and can
usually be accommodated from an embedded pool.

3 files changed, 21 insertions, 34 deletions

diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index 4096b9ad..f1f2f838 100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -968,12 +968,6 @@ _cairo_bo_event_queue_init (cairo_bo_event_queue_t	*event_queue,
     unsigned num_events = 2*num_edges;
     cairo_status_t status;
 
-    status = _cairo_skip_list_init (&event_queue->intersection_queue,
-				    cairo_bo_event_compare_abstract,
-				    sizeof (cairo_bo_event_t));
-    if (unlikely (status))
-	return status;
-
     /* The skip_elt_t field of a cairo_bo_event_t isn't used for start
      * or stop events, so this allocation is safe.  XXX: make the
      * event type a union so it doesn't always contain the skip
@@ -982,10 +976,8 @@ _cairo_bo_event_queue_init (cairo_bo_event_queue_t	*event_queue,
 				      sizeof (cairo_bo_event_t) +
 				      sizeof (cairo_bo_event_t *),
 				      sizeof (cairo_bo_event_t *));
-    if (unlikely (events == NULL)) {
-	_cairo_skip_list_fini (&event_queue->intersection_queue);
+    if (unlikely (events == NULL))
 	return _cairo_error (CAIRO_STATUS_NO_MEMORY);
-    }
 
     sorted_event_ptrs = (cairo_bo_event_t **) (events + num_events);
     event_queue->startstop_events = events;
@@ -1012,6 +1004,10 @@ _cairo_bo_event_queue_init (cairo_bo_event_queue_t	*event_queue,
     _cairo_bo_event_queue_sort (sorted_event_ptrs, num_events);
     event_queue->sorted_startstop_event_ptrs[num_events] = NULL;
 
+    _cairo_skip_list_init (&event_queue->intersection_queue,
+			   cairo_bo_event_compare_abstract,
+			   sizeof (cairo_bo_event_t));
+
     return CAIRO_STATUS_SUCCESS;
 }
 
@@ -1058,22 +1054,16 @@ _cairo_bo_event_queue_insert_if_intersect_below_current_y (cairo_bo_event_queue_
     return _cairo_bo_event_queue_insert (event_queue, &event);
 }
 
-static cairo_status_t
+static void
 _cairo_bo_sweep_line_init (cairo_bo_sweep_line_t *sweep_line)
 {
-    cairo_status_t status;
-
-    status = _cairo_skip_list_init (&sweep_line->active_edges,
-				    _sweep_line_elt_compare,
-				    sizeof (sweep_line_elt_t));
-    if (unlikely (status))
-	return status;
+    _cairo_skip_list_init (&sweep_line->active_edges,
+			   _sweep_line_elt_compare,
+			   sizeof (sweep_line_elt_t));
 
     sweep_line->head = NULL;
     sweep_line->tail = NULL;
     sweep_line->current_y = 0;
-
-    return CAIRO_STATUS_SUCCESS;
 }
 
 static void
@@ -1508,9 +1498,7 @@ _cairo_bentley_ottmann_tessellate_bo_edges (cairo_bo_edge_t	*edges,
     if (status)
 	return status;
 
-    status = _cairo_bo_sweep_line_init (&sweep_line);
-    if (unlikely (status))
-	goto CLEANUP_EVENT_QUEUE;
+    _cairo_bo_sweep_line_init (&sweep_line);
 
     _cairo_bo_traps_init (&bo_traps, traps, xmin, ymin, xmax, ymax);
 
@@ -1637,7 +1625,6 @@ _cairo_bentley_ottmann_tessellate_bo_edges (cairo_bo_edge_t	*edges,
     }
     _cairo_bo_traps_fini (&bo_traps);
     _cairo_bo_sweep_line_fini (&sweep_line);
-  CLEANUP_EVENT_QUEUE:
     _cairo_bo_event_queue_fini (&event_queue);
     return status;
 }
diff --git a/src/cairo-skiplist-private.h b/src/cairo-skiplist-private.h
index 8c7dc977..250b5a26 100644
--- a/src/cairo-skiplist-private.h
+++ b/src/cairo-skiplist-private.h
@@ -70,8 +70,9 @@ typedef struct _skip_list {
     size_t data_size;
     skip_elt_t *chains[MAX_LEVEL];
     skip_elt_t *freelists[MAX_FREELIST_LEVEL];
-    struct pool *pool;
     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
@@ -82,10 +83,10 @@ typedef struct _skip_list {
  * 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 cairo_status_t
+cairo_private void
 _cairo_skip_list_init (cairo_skip_list_t		*list,
-		cairo_skip_list_compare_t	 compare,
-		size_t			 elt_size);
+		       cairo_skip_list_compare_t	 compare,
+		       size_t			 elt_size);
 
 
 /* Deallocate resources associated with a skip list and all elements
diff --git a/src/cairo-skiplist.c b/src/cairo-skiplist.c
index 5fe2bd0c..5c2c477e 100644
--- a/src/cairo-skiplist.c
+++ b/src/cairo-skiplist.c
@@ -63,7 +63,7 @@ pool_new (void)
 static void
 pools_destroy (struct pool *pool)
 {
-    while (pool != NULL) {
+    while (pool->next != NULL) {
 	struct pool *next = pool->next;
 	free (pool);
 	pool = next;
@@ -73,7 +73,7 @@ pools_destroy (struct pool *pool)
 /*
  * Initialize an empty skip list
  */
-cairo_status_t
+void
 _cairo_skip_list_init (cairo_skip_list_t	*list,
                        cairo_skip_list_compare_t compare,
                        size_t			 elt_size)
@@ -83,9 +83,10 @@ _cairo_skip_list_init (cairo_skip_list_t	*list,
     list->compare = compare;
     list->elt_size = elt_size;
     list->data_size = elt_size - sizeof (skip_elt_t);
-    list->pool = pool_new ();
-    if (unlikely (list->pool == NULL))
-	return _cairo_error (CAIRO_STATUS_NO_MEMORY);
+    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;
@@ -96,8 +97,6 @@ _cairo_skip_list_init (cairo_skip_list_t	*list,
     }
 
     list->max_level = 0;
-
-    return CAIRO_STATUS_SUCCESS;
 }
 
 void