[cairo] [PATCH] Reinstate cairo_region_create_rectangles()

[Soeren Sandmann]

See http://lists.cairographics.org/archives/cairo/2009-March/016869.html 

The main question I have is whether to expose this as user-visible
API. Avoiding quadratic behavior seems like it would be useful to
applications as well, although GTK+ has managed to do without it for a
long time..

Soren



cairo_region_union_rectangle() is linear in the number of rectangles
in the region. There is no way to make it significantly faster without
losing the ability to return errors synchronously, so a
cairo_region_create_rectangles() is needed to avoid a large
performance regression.

diff --git a/src/cairo-region.c b/src/cairo-region.c
index 5d1f2c5..f83c512 100644
--- a/src/cairo-region.c
+++ b/src/cairo-region.c
@@ -129,6 +129,50 @@ cairo_region_create (void)
 }
 slim_hidden_def (cairo_region_create);
 
+cairo_region_t *
+cairo_region_create_rectangles (cairo_rectangle_int_t *rects,
+				int count)
+{
+    pixman_box32_t stack_pboxes[CAIRO_STACK_ARRAY_LENGTH (pixman_box32_t)];
+    pixman_box32_t *pboxes = stack_pboxes;
+    cairo_region_t *region;
+    int i;
+
+    region = _cairo_malloc (sizeof (cairo_region_t));
+
+    if (!region)
+	return (cairo_region_t *)&_cairo_region_nil;
+
+    region->status = CAIRO_STATUS_SUCCESS;
+    
+    if (count > ARRAY_LENGTH (stack_pboxes)) {
+	pboxes = _cairo_malloc_ab (count, sizeof (pixman_box32_t));
+
+	if (unlikely (pboxes == NULL)) {
+	    free (region);
+	    return (cairo_region_t *)&_cairo_region_nil;
+	}
+    }
+
+    for (i = 0; i < count; i++) {
+	pboxes[i].x1 = rects[i].x;
+	pboxes[i].y1 = rects[i].y;
+	pboxes[i].x2 = rects[i].x + rects[i].width;
+	pboxes[i].y2 = rects[i].y + rects[i].height;
+    }
+
+    if (! pixman_region32_init_rects (&region->rgn, pboxes, count)) {
+	free (region);
+
+	region = (cairo_region_t *)&_cairo_region_nil;
+    }
+    
+    if (pboxes != stack_pboxes)
+	free (pboxes);
+
+    return region;
+}
+
 /**
  * cairo_region_create_rectangle:
  * @rectangle: a #cairo_rectangle_int_t
diff --git a/src/cairo-traps.c b/src/cairo-traps.c
index fed3f10..2b67e14 100644
--- a/src/cairo-traps.c
+++ b/src/cairo-traps.c
@@ -615,9 +615,10 @@ cairo_int_status_t
 _cairo_traps_extract_region (const cairo_traps_t  *traps,
 			     cairo_region_t      **region)
 {
+    cairo_rectangle_int_t stack_rects[CAIRO_STACK_ARRAY_LENGTH (cairo_rectangle_int_t)];
+    cairo_rectangle_int_t *rects = stack_rects;
     cairo_int_status_t status;
-    cairo_region_t *r;
-    int i;
+    int i, rect_count;
 
     for (i = 0; i < traps->num_traps; i++) {
 	if (traps->traps[i].left.p1.x != traps->traps[i].left.p2.x   ||
@@ -631,13 +632,15 @@ _cairo_traps_extract_region (const cairo_traps_t  *traps,
 	}
     }
 
-    r = cairo_region_create ();
-    if (unlikely (r->status))
-	return r->status;
+    if (traps->num_traps > ARRAY_LENGTH (stack_rects)) {
+	rects = _cairo_malloc_ab (traps->num_traps, sizeof (cairo_rectangle_int_t));
 
-    for (i = 0; i < traps->num_traps; i++) {
-	cairo_rectangle_int_t rect;
+	if (unlikely (rects == NULL))
+	    return _cairo_error (CAIRO_STATUS_NO_MEMORY);
+    }
 
+    rect_count = 0;
+    for (i = 0; i < traps->num_traps; i++) {
 	int x1 = _cairo_fixed_integer_part (traps->traps[i].left.p1.x);
 	int y1 = _cairo_fixed_integer_part (traps->traps[i].top);
 	int x2 = _cairo_fixed_integer_part (traps->traps[i].right.p1.x);
@@ -648,21 +651,27 @@ _cairo_traps_extract_region (const cairo_traps_t  *traps,
 	 */
 	if (x1 == x2 || y1 == y2)
 	    continue;
+	
+	rects[rect_count].x = x1;
+	rects[rect_count].y = y1;
+	rects[rect_count].width = x2 - x1;
+	rects[rect_count].height = y2 - y1;
 
-	rect.x = x1;
-	rect.y = y1;
-	rect.width = x2 - x1;
-	rect.height = y2 - y1;
-
-	status = cairo_region_union_rectangle (r, &rect);
-	if (unlikely (status)) {
-	    cairo_region_destroy (r);
-	    return status;
-	}
+	rect_count++;
     }
+ 
+    *region = cairo_region_create_rectangles (rects, rect_count);
+    status = cairo_region_status (*region);
 
-    *region = r;
-    return CAIRO_STATUS_SUCCESS;
+    if (rects != stack_rects)
+	free (rects);
+
+    if (unlikely (status)) {
+	cairo_region_destroy (*region);
+	*region = NULL;
+    }
+    
+    return status;
 }
 
 /* moves trap points such that they become the actual corners of the trapezoid */
diff --git a/src/cairo.h b/src/cairo.h
index b9c47db..af8887c 100644
--- a/src/cairo.h
+++ b/src/cairo.h
@@ -2374,6 +2374,10 @@ cairo_public cairo_region_t *
 cairo_region_create_rectangle (const cairo_rectangle_int_t *rectangle);
 
 cairo_public cairo_region_t *
+cairo_region_create_rectangles (cairo_rectangle_int_t *rects,
+				int count);
+
+cairo_public cairo_region_t *
 cairo_region_copy (cairo_region_t *original);
 
 cairo_public void
diff --git a/src/cairoint.h b/src/cairoint.h
index d694ae4..9d348c0 100644
--- a/src/cairoint.h
+++ b/src/cairoint.h
@@ -2711,6 +2711,7 @@ slim_hidden_proto (cairo_user_to_device_distance);
 slim_hidden_proto (cairo_version_string);
 slim_hidden_proto (cairo_region_create);
 slim_hidden_proto (cairo_region_create_rectangle);
+slim_hidden_proto (cairo_region_create_rectangles);
 slim_hidden_proto (cairo_region_copy);
 slim_hidden_proto (cairo_region_destroy);
 slim_hidden_proto (cairo_region_status);