diff options
| -rw-r--r-- | pixman/pixman-region32.c | 250 |
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; } |