switch to region builder

1 files changed, 211 insertions, 39 deletions

diff --git a/pixman/pixman-region32.c b/pixman/pixman-region32.c
index f172bc2e..3b20e33a 100644
--- a/pixman/pixman-region32.c
+++ b/pixman/pixman-region32.c
@@ -46,33 +46,6 @@ typedef struct {
 
 #include "pixman-region.c"
 
-static pixman_bool_t
-emit_box (pixman_box32_t **boxes, int *n_boxes,
-	  int32_t x1, int32_t y1, int32_t x2, int32_t y2)
-{
-    pixman_box32_t *box;
-
-    (*n_boxes)++;
-
-    if (((*n_boxes) & ((*n_boxes) - 1)) == 0)
-    {
-	if (!(*boxes = pixman_realloc_ab (
-		  *boxes, 2 * (*n_boxes), sizeof (pixman_box32_t))))
-	{
-	    return FALSE;
-	}
-    }
-
-    box = ((*boxes) + (*n_boxes) - 1);
-
-    box->x1 = x1;
-    box->y1 = y1;
-    box->x2 = x2;
-    box->y2 = y2;
-
-    return TRUE;
-}
-
 static void
 merge (const pixman_vspan32_t **dst,
        const pixman_vspan32_t **s1, int n1,
@@ -138,6 +111,206 @@ merge_sort (const pixman_vspan32_t *spans,
     merge (destination, tmp, n_left, tmp + n_left, n_right, offset);
 }
 
+#define BROKEN_DATA  ((pixman_region32_data_t *)0x01)
+
+typedef struct region_builder_t region_builder_t;
+
+struct region_builder_t
+{
+    pixman_region32_data_t *	data;
+    int				second_last_row;
+    int				last_row;
+};
+
+static size_t
+next_power (size_t n)
+{
+    size_t r = 1;
+
+    while (r < n)
+	r <<= 1;
+
+    return r;
+}
+
+static pixman_region32_data_t *
+region_data_append (pixman_region32_data_t *data, int n)
+{
+    size_t new_size, n_rects;
+
+    n_rects = data? data->numRects : 0;
+    new_size = next_power (n_rects + n);
+
+    if (data && data->size == new_size)
+	return data;
+
+    if ((data = pixman_realloc_ab_plus_c (
+	     data, new_size, sizeof (pixman_box32_t),
+	     sizeof (pixman_region32_data_t))))
+    {
+	data->numRects = n_rects;
+	data->size = new_size;
+    }
+
+    return data;
+}
+
+static void
+region_builder_init (region_builder_t *builder)
+{
+    builder->data = NULL;
+    builder->second_last_row = -1;
+    builder->last_row = 0;
+}
+
+static void
+region_builder_coalesce_rows (region_builder_t *builder)
+{
+    pixman_region32_data_t *data = builder->data;
+    pixman_box32_t *old, *new;
+    pixman_bool_t coalesce;
+    int i, n;
+
+    if (!data)
+	return;
+
+    n = builder->last_row - builder->second_last_row;
+    if (builder->second_last_row == -1 ||
+	data->numRects - builder->last_row != n)
+    {
+	coalesce = FALSE;
+    }
+    else
+    {
+	old = (pixman_box32_t *)(data + 1) + builder->second_last_row;
+	new = (pixman_box32_t *)(data + 1) + builder->last_row;
+
+	coalesce = TRUE;
+	for (i = 0; i < n; ++i)
+	{
+	    if (new[i].y1 != old[i].y2 ||
+		new[i].x1 != old[i].x1 ||
+		new[i].x2 != old[i].x2)
+	    {
+		coalesce = FALSE;
+		break;
+	    }
+	}
+    }
+
+    if (coalesce)
+    {
+	for (i = 0; i < n; ++i)
+	    old[i].y2 = new[i].y2;
+
+	data->numRects -= n;
+    }
+    else
+    {
+	builder->second_last_row = builder->last_row;
+	builder->last_row = data->numRects;
+    }
+}
+
+static pixman_bool_t
+region_builder_add_box (region_builder_t *builder,
+			int x1, int y1, int x2, int y2)
+{
+    pixman_box32_t *last_box;
+    pixman_region32_data_t *data;
+
+    if (builder->data == BROKEN_DATA)
+	return FALSE;
+
+    if (x1 == x2 || y1 == y2)
+	return TRUE;
+    
+    if (!(data = region_data_append (builder->data, 1)))
+    {
+	free (builder->data);
+	builder->data = BROKEN_DATA;
+	return FALSE;
+    }
+
+    builder->data = data;
+
+    if (data->numRects == 0)
+	last_box = NULL;
+    else
+	last_box = ((pixman_box32_t *)(data + 1)) + data->numRects - 1;
+
+    if (last_box)
+    {
+	if (y1 != last_box->y1)
+	{
+	    region_builder_coalesce_rows (builder);
+	}
+	else if (x1 == last_box->x2)
+	{
+	    last_box->x2 = x2;
+	    return TRUE;
+	}
+    }
+
+    last_box = (pixman_box32_t *)(data + 1) + data->numRects++;
+    last_box->x1 = x1;
+    last_box->y1 = y1;
+    last_box->x2 = x2;
+    last_box->y2 = y2;
+
+    return TRUE;
+}
+
+static pixman_bool_t
+region_builder_finish (region_builder_t *builder, pixman_region32_t *region)
+{
+    if (builder->data == BROKEN_DATA)
+	return FALSE;
+
+    region_builder_coalesce_rows (builder);
+
+    if (!builder->data || builder->data->numRects == 0)
+    {
+	pixman_region32_init (region);
+	return TRUE;
+    }
+    else if (builder->data->numRects == 1)
+    {
+	pixman_box32_t *b = (pixman_box32_t *)(builder->data + 1);
+
+	pixman_region32_init_rect (
+	    region, b->x1, b->y1, b->x2 - b->x1, b->y2 - b->y1);
+    }
+    else
+    {
+	pixman_box32_t *extents = &(region->extents);
+	int i;
+
+	extents->x1 = INT32_MAX;
+	extents->y1 = INT32_MAX;
+	extents->x2 = INT32_MIN;
+	extents->y2 = INT32_MIN;
+
+	for (i = 0; i < builder->data->numRects; ++i)
+	{
+	    pixman_box32_t *b = (pixman_box32_t *)(builder->data + 1 + i);
+
+	    if (b->x1 < extents->x1)
+		extents->x1 = b->x1;
+	    if (b->y1 < extents->y1)
+		extents->y1 = b->y1;
+	    if (b->x2 > extents->x2)
+		extents->x2 = b->x2;
+	    if (b->y2 > extents->y2)
+		extents->y2 = b->y2;
+	}
+
+	region->data = builder->data;
+    }
+
+    return TRUE;
+}
+
 PIXMAN_EXPORT pixman_bool_t
 pixman_region32_init_vspans (pixman_region32_t *region,
 			     pixman_fill_rule_t fill_rule,
@@ -160,10 +333,9 @@ pixman_region32_init_vspans (pixman_region32_t *region,
     const pixman_vspan32_t **first_bottom;
     const pixman_vspan32_t **last_bottom;
     const pixman_vspan32_t **tmp;
+    region_builder_t builder;
     pixman_bool_t result;
     int winding_mask;
-    pixman_box32_t *boxes = NULL;
-    int n_boxes = 0;
     int32_t y;
 
     result = FALSE;
@@ -192,8 +364,10 @@ pixman_region32_init_vspans (pixman_region32_t *region,
     if (!(tmp = pixman_malloc_ab (n_vspans + 2, sizeof (pixman_vspan32_t *))))
 	goto out;
 
-    merge_sort (vspans, top + 2, tmp, n_vspans, offsetof (pixman_vspan32_t, top));
-    merge_sort (vspans, bottom, tmp, n_vspans, offsetof (pixman_vspan32_t, bottom));
+    merge_sort (vspans, top + 2, tmp, n_vspans,
+		offsetof (pixman_vspan32_t, top));
+    merge_sort (vspans, bottom, tmp, n_vspans,
+		offsetof (pixman_vspan32_t, bottom));
 
     free (tmp);
     
@@ -203,6 +377,8 @@ pixman_region32_init_vspans (pixman_region32_t *region,
     last_top = top + n_vspans + 2;
 
     y = INT32_MIN;
+
+    region_builder_init (&builder);
     
     while (first_bottom < last_bottom)
     {
@@ -233,8 +409,8 @@ pixman_region32_init_vspans (pixman_region32_t *region,
 
 		if (winding & winding_mask)
 		{
-		    if (!emit_box (
-			    &boxes, &n_boxes, (*span)->x, y, (*(span + 1))->x, new_y))
+		    if (!region_builder_add_box (
+			    &builder, (*span)->x, y, (*(span + 1))->x, new_y))
 		    {
 			goto out;
 		    }
@@ -270,15 +446,11 @@ pixman_region32_init_vspans (pixman_region32_t *region,
 	}
     }
 
-    /* FIXME: we can do better than init_rects since we know all the boxes
-     * are XY banded and non-overlapping
-     */
-    result = pixman_region32_init_rects (region, boxes, n_boxes);
+    result = region_builder_finish (&builder, region);
     
 out:
-    free (boxes);
     free (top);
     free (bottom);
-
+    
     return result;
 }