diff options
| -rw-r--r-- | region-iter.c | 381 |
1 files changed, 262 insertions, 119 deletions
diff --git a/region-iter.c b/region-iter.c index 3d2a460..7901db8 100644 --- a/region-iter.c +++ b/region-iter.c @@ -45,6 +45,27 @@ typedef struct region_iter_t region_iter_t; typedef struct row_t row_t; +typedef struct box32_t box32_t; +typedef struct region32_t region32_t; +typedef struct region32_data_t region32_data_t; + +struct box32_t +{ + int32_t x1, y1, x2, y2; +}; + +struct region32_data_t +{ + long size; + long numRects; +/* box32_t rects[size]; in memory but not explicitly declared */ +}; + +struct region32_t +{ + box32_t extents; + region32_data_t *data; +}; typedef enum { @@ -63,12 +84,12 @@ struct region_iter_t { struct { - pixman_region32_t * region; + region32_t * region; } first; struct { - pixman_box32_t * first; - pixman_box32_t * last; + box32_t * first; + box32_t * last; } middle; struct { @@ -79,23 +100,23 @@ struct region_iter_t struct row_t { - const pixman_box32_t * first; - const pixman_box32_t * last; + const box32_t * first; + const box32_t * last; int y1; int y2; }; /* region_data manipulation */ -#define BROKEN_DATA ((pixman_region32_data_t *)0x01) +#define BROKEN_DATA ((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; + region32_data_t * data; + int second_last_row; + int last_row; }; static size_t @@ -121,8 +142,8 @@ realloc_ab_plus_c (void *m, unsigned int a, unsigned int b, unsigned int c) return realloc (m, a * b + c); } -static pixman_region32_data_t * -region_data_append (pixman_region32_data_t *data, int n) +static region32_data_t * +region_data_append (region32_data_t *data, int n) { size_t new_size, n_rects; @@ -133,8 +154,8 @@ region_data_append (pixman_region32_data_t *data, int n) return data; if ((data = realloc_ab_plus_c ( - data, new_size, sizeof (pixman_box32_t), - sizeof (pixman_region32_data_t)))) + data, new_size, sizeof (box32_t), + sizeof (region32_data_t)))) { data->numRects = n_rects; data->size = new_size; @@ -154,8 +175,8 @@ region_builder_init (region_builder_t *builder) static void region_builder_coalesce_rows (region_builder_t *builder) { - pixman_region32_data_t *data = builder->data; - pixman_box32_t *old, *new; + region32_data_t *data = builder->data; + box32_t *old, *new; pixman_bool_t coalesce; int i, n; @@ -170,8 +191,8 @@ region_builder_coalesce_rows (region_builder_t *builder) } else { - old = (pixman_box32_t *)(data + 1) + builder->second_last_row; - new = (pixman_box32_t *)(data + 1) + builder->last_row; + old = (box32_t *)(data + 1) + builder->second_last_row; + new = (box32_t *)(data + 1) + builder->last_row; coalesce = TRUE; for (i = 0; i < n; ++i) @@ -204,8 +225,8 @@ 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; + box32_t *last_box; + region32_data_t *data; if (builder->data == BROKEN_DATA) return FALSE; @@ -222,7 +243,7 @@ region_builder_add_box (region_builder_t *builder, if (data->numRects == 0) last_box = NULL; else - last_box = ((pixman_box32_t *)(data + 1)) + data->numRects - 1; + last_box = ((box32_t *)(data + 1)) + data->numRects - 1; if (last_box) { @@ -237,7 +258,7 @@ region_builder_add_box (region_builder_t *builder, } } - last_box = (pixman_box32_t *)(data + 1) + data->numRects++; + last_box = (box32_t *)(data + 1) + data->numRects++; last_box->x1 = x1; last_box->y1 = y1; last_box->x2 = x2; @@ -249,9 +270,9 @@ region_builder_add_box (region_builder_t *builder, static pixman_bool_t region_builder_add_row (region_builder_t *builder, const row_t *row) { - pixman_box32_t *last_box; - const pixman_box32_t *first; - pixman_region32_data_t *data; + box32_t *last_box; + const box32_t *first; + region32_data_t *data; int n_boxes; if (builder->data == BROKEN_DATA) @@ -271,7 +292,7 @@ region_builder_add_row (region_builder_t *builder, const row_t *row) if (data->numRects == 0) last_box = NULL; else - last_box = ((pixman_box32_t *)(data + 1)) + data->numRects - 1; + last_box = ((box32_t *)(data + 1)) + data->numRects - 1; first = row->first; if (last_box) @@ -290,7 +311,7 @@ region_builder_add_row (region_builder_t *builder, const row_t *row) while (first != row->last) { - pixman_box32_t *box = (pixman_box32_t *)(data + 1) + data->numRects++; + box32_t *box = (box32_t *)(data + 1) + data->numRects++; box->x1 = first->x1; box->x2 = first->x2; @@ -303,8 +324,63 @@ region_builder_add_row (region_builder_t *builder, const row_t *row) return TRUE; } +static const box32_t region32_empty_box_ = { 0, 0, 0, 0 }; +static const region32_data_t region32_empty_data_ = { 0, 0 }; +#if defined (__llvm__) && !defined (__clang__) +static const volatile region_data32_t region32_broken_data_ = { 0, 0 }; +#else +static const region32_data_t region32_broken_data_ = { 0, 0 }; +#endif + +static box32_t *region32_empty_box = + (box32_t *)®ion32_empty_box_; +static region32_data_t *region32_empty_data = + (region32_data_t *)®ion32_empty_data_; +static region32_data_t *region32_broken_data = + (region32_data_t *)®ion32_broken_data_; + +void +region32_init (region32_t *region) +{ + region->extents = *region32_empty_box; + region->data = region32_empty_data; +} + +void +region32_fini (region32_t *region) +{ + GOOD (region); + FREE_DATA (region); +} + +#warning FIXME: this used to be pixman_log_error +#define log_error(s) + +void +region32_init_rect (region32_t * region, + int x, + int y, + unsigned int width, + unsigned int height) +{ + region->extents.x1 = x; + region->extents.y1 = y; + region->extents.x2 = x + width; + region->extents.y2 = y + height; + + if (!GOOD_RECT (®ion->extents)) + { + if (BAD_RECT (®ion->extents)) + log_error ("Invalid rectangle passed"); + region32_init (region); + return; + } + + region->data = NULL; +} + static pixman_bool_t -region_builder_finish (region_builder_t *builder, pixman_region32_t *region) +region_builder_finish (region_builder_t *builder, region32_t *region) { if (builder->data == BROKEN_DATA) return FALSE; @@ -313,26 +389,26 @@ region_builder_finish (region_builder_t *builder, pixman_region32_t *region) if (!builder->data || builder->data->numRects == 0) { - pixman_region32_init (region); + region32_init (region); return TRUE; } else if (builder->data->numRects == 1) { - pixman_box32_t *b = (pixman_box32_t *)(builder->data + 1); + box32_t *b = (box32_t *)(builder->data + 1); - pixman_region32_init_rect ( + region32_init_rect ( region, b->x1, b->y1, b->x2 - b->x1, b->y2 - b->y1); return TRUE; } else { - pixman_box32_t extents = { INT32_MAX, INT32_MAX, INT32_MIN, INT32_MIN }; + box32_t extents = { INT32_MAX, INT32_MAX, INT32_MIN, INT32_MIN }; int i; for (i = 0; i < builder->data->numRects; ++i) { - pixman_box32_t *b = (pixman_box32_t *)(builder->data + 1 + i); + box32_t *b = (box32_t *)(builder->data + 1 + i); if (b->x1 < extents.x1) extents.x1 = b->x1; @@ -353,7 +429,7 @@ region_builder_finish (region_builder_t *builder, pixman_region32_t *region) /* Region iterator */ static void -region_iter_init (region_iter_t *iter, pixman_region32_t *region) +region_iter_init (region_iter_t *iter, region32_t *region) { iter->state = FIRST; iter->u.first.region = region; @@ -362,9 +438,9 @@ region_iter_init (region_iter_t *iter, pixman_region32_t *region) static pixman_bool_t region_iter_get_row (region_iter_t *iter, row_t *row) { - pixman_box32_t *first; - pixman_box32_t *last; - pixman_box32_t *box; + box32_t *first; + box32_t *last; + box32_t *box; switch (iter->state) { @@ -387,7 +463,7 @@ region_iter_get_row (region_iter_t *iter, row_t *row) else { iter->state = MIDDLE; - first = (pixman_box32_t *)(iter->u.first.region->data + 1); + first = (box32_t *)(iter->u.first.region->data + 1); last = first + iter->u.first.region->data->numRects; } @@ -454,12 +530,12 @@ region_iter_get_row (region_iter_t *iter, row_t *row) /* In time O(log n), locate the first box whose y2 is greater than y. * Return @end if no such box exists. */ -static pixman_box32_t * -find_box_for_y (pixman_box32_t *begin, pixman_box32_t *end, int y) +static box32_t * +find_box_for_y (box32_t *begin, box32_t *end, int y) { while (end - begin > 0) { - pixman_box32_t *mid = begin + (end - begin) / 2; + box32_t *mid = begin + (end - begin) / 2; if (mid->y2 > y) end = mid; @@ -474,7 +550,7 @@ find_box_for_y (pixman_box32_t *begin, pixman_box32_t *end, int y) static pixman_bool_t region_iter_get_row_for_y (region_iter_t *iter, int y, row_t *row) { - pixman_box32_t *box; + box32_t *box; while (iter->state != MIDDLE) { @@ -516,7 +592,7 @@ struct overlapped_iter_t static void overlapped_iter_init (overlapped_iter_t *iter, - pixman_region32_t *region1, pixman_region32_t *region2) + region32_t *region1, region32_t *region2) { region_iter_init (&iter->iter1, region1); region_iter_init (&iter->iter2, region2); @@ -592,8 +668,8 @@ struct row_iter_t struct { - const pixman_box32_t *first; - const pixman_box32_t *last; + const box32_t *first; + const box32_t *last; } middle; struct @@ -622,7 +698,7 @@ row_iter_get_segment (row_iter_t *iter, segment_t *segment) if (iter->u.first.row->first) { - const pixman_box32_t *first, *last; + const box32_t *first, *last; segment->x2 = iter->u.first.row->first->x1; @@ -728,10 +804,10 @@ segment_iter_get_segment (segment_iter_t *iter, segment_t *segment) pixman_bool_t -region_contains_point (pixman_region32_t *region, +region_contains_point (region32_t *region, int x, int y, - pixman_box32_t *box) + box32_t *box) { region_iter_t iter; row_t row; @@ -739,7 +815,7 @@ region_contains_point (pixman_region32_t *region, region_iter_init (&iter, region); if (region_iter_get_row_for_y (&iter, y, &row) && row.y1 < y) { - const pixman_box32_t *b; + const box32_t *b; for (b = row.first; b != row.last && b->x1 <= x; ++b) { @@ -757,8 +833,8 @@ region_contains_point (pixman_region32_t *region, } pixman_region_overlap_t -region_contains_rectangle (pixman_region32_t *region, - pixman_box32_t *prect) +region_contains_rectangle (region32_t *region, + box32_t *prect) { pixman_bool_t part_in = FALSE; pixman_bool_t part_out = FALSE; @@ -811,9 +887,9 @@ typedef enum static pixman_bool_t region_op (ops_t op, - pixman_region32_t *dst, - pixman_region32_t *src1, - pixman_region32_t *src2) + region32_t *dst, + region32_t *src1, + region32_t *src2) { overlapped_iter_t iter; region_builder_t builder; @@ -858,24 +934,24 @@ region_op (ops_t op, } } - pixman_region32_fini (dst); + region32_fini (dst); return region_builder_finish (&builder, dst); } static pixman_bool_t -make_region_from_sorted (pixman_region32_t *region, - const pixman_box32_t *boxes, int n_boxes) +make_region_from_sorted (region32_t *region, + const box32_t *boxes, int n_boxes) { if (n_boxes == 1) { - pixman_region32_init_rect (region, - boxes[0].x1, boxes[0].y1, - boxes[0].x2, boxes[0].y2); + region32_init_rect (region, + boxes[0].x1, boxes[0].y1, + boxes[0].x2, boxes[0].y2); } else { - pixman_region32_t tmp; + region32_t tmp; int n_left = n_boxes / 2; int n_right = n_boxes - n_left; @@ -884,14 +960,14 @@ make_region_from_sorted (pixman_region32_t *region, if (!make_region_from_sorted (&tmp, boxes + n_left, n_right)) { - pixman_region32_fini (region); + region32_fini (region); return FALSE; } if (!region_op (UNION, region, region, &tmp)) { - pixman_region32_fini (region); - pixman_region32_fini (&tmp); + region32_fini (region); + region32_fini (&tmp); return FALSE; } @@ -903,8 +979,8 @@ make_region_from_sorted (pixman_region32_t *region, static int compare_boxes (const void *box1v, const void *box2v) { - const pixman_box32_t *box1 = box1v; - const pixman_box32_t *box2 = box2v; + const box32_t *box1 = box1v; + const box32_t *box2 = box2v; if (box1->y1 == box2->y1) return 0; @@ -915,17 +991,17 @@ compare_boxes (const void *box1v, const void *box2v) } pixman_bool_t -region_from_boxes (pixman_region32_t *region, - const pixman_box32_t *boxes, int n_boxes) +region_from_boxes (region32_t *region, + const box32_t *boxes, int n_boxes) { if (n_boxes == 0) { - pixman_region32_init (region); + region32_init (region); return TRUE; } else { - pixman_box32_t *copy = malloc (sizeof (pixman_box32_t) * n_boxes); + box32_t *copy = malloc (sizeof (box32_t) * n_boxes); int displacement, i; pixman_bool_t ret; @@ -935,7 +1011,7 @@ region_from_boxes (pixman_region32_t *region, displacement = 0; for (i = 0; i < n_boxes; ++i) { - const pixman_box32_t *box = boxes + i; + const box32_t *box = boxes + i; if (box->x1 >= box->x2 || box->y1 >= box->y2) displacement++; @@ -943,7 +1019,7 @@ region_from_boxes (pixman_region32_t *region, copy[i - displacement] = boxes[i]; } - qsort (copy, i - displacement, sizeof (pixman_box32_t), compare_boxes); + qsort (copy, i - displacement, sizeof (box32_t), compare_boxes); ret = make_region_from_sorted (region, copy, i - displacement); @@ -985,7 +1061,7 @@ add_corners (corner_t *corners, int *n_corners, int *new1, int *new2) } static corner_t * -region_path (pixman_region32_t *region, int *n) +region_path (region32_t *region, int *n) { region_iter_t iter; row_t row1, row2; @@ -1092,7 +1168,7 @@ region_path (pixman_region32_t *region, int *n) } static void -dump_region (const char *title, pixman_region32_t *region) +dump_region (const char *title, region32_t *region) { region_iter_t iter; row_t row; @@ -1131,107 +1207,174 @@ dump_corners (corner_t *corners, int n_corners) } } +/* Convenience function for performing union of region with a + * single rectangle + */ +pixman_bool_t +region32_union_rect (region32_t * dest, + region32_t * source, + int x, + int y, + unsigned int width, + unsigned int height) +{ + region32_t region; + + region.extents.x1 = x; + region.extents.y1 = y; + region.extents.x2 = x + width; + region.extents.y2 = y + height; + + if (!GOOD_RECT (®ion.extents)) + { + if (BAD_RECT (®ion.extents)) + log_error ("Invalid rectangle passed"); + return region32_copy (dest, source); + } + + region.data = NULL; + + return region_op (UNION, dest, source, ®ion); +} + +pixman_bool_t +region32_copy (region32_t *dst, region32_t *src) +{ + GOOD (dst); + GOOD (src); + + if (dst == src) + return TRUE; + + dst->extents = src->extents; + + if (!src->data || !src->data->size) + { + FREE_DATA (dst); + dst->data = src->data; + return TRUE; + } + + if (!dst->data || (dst->data->size < src->data->numRects)) + { + FREE_DATA (dst); + + dst->data = alloc_data (src->data->numRects); + + if (!dst->data) + return pixman_break (dst); + + dst->data->size = src->data->numRects; + } + + dst->data->numRects = src->data->numRects; + + memmove ((char *)PIXREGION_BOXPTR (dst), (char *)PIXREGION_BOXPTR (src), + dst->data->numRects * sizeof(box_type_t)); + + return TRUE; +} #ifndef NO_MAIN int main () { - pixman_region32_t region; - pixman_region32_t region1, region2; + region32_t region; + region32_t region1, region2; corner_t *corners; int n_corners; /* empty region */ - pixman_region32_init (®ion); + region32_init (®ion); dump_region ("empty region", ®ion); /* one box */ - pixman_region32_init_rect (®ion, -50, -50, 100, 100); + region32_init_rect (®ion, -50, -50, 100, 100); dump_region ("one box", ®ion); /* Slightly more complex region */ - pixman_region32_init_rect (®ion, 0, 0, 100, 100); - pixman_region32_union_rect (®ion, ®ion, 50, 50, 100, 100); + region32_init_rect (®ion, 0, 0, 100, 100); + region32_union_rect (®ion, ®ion, 50, 50, 100, 100); dump_region ("slightly more complex", ®ion); /* INT_MAX box */ - pixman_region32_init_rect (®ion, + region32_init_rect (®ion, 100, 100, INT_MAX - 100, INT_MAX - 100); dump_region ("giant box", ®ion); /* full region */ - pixman_region32_init_rect (®ion, + region32_init_rect (®ion, INT_MIN, INT_MIN, INT_MAX, INT_MAX); dump_region ("full", ®ion); /* Even fuller */ - pixman_region32_init_rect (®ion, - INT_MIN, INT_MIN, INT_MAX, INT_MAX); - pixman_region32_union_rect (®ion, ®ion, - -1, -1, INT_MAX, INT_MAX); - pixman_region32_union_rect (®ion, ®ion, - INT_MIN, -1, INT_MAX, INT_MAX); - pixman_region32_union_rect (®ion, ®ion, - -1, INT_MIN, INT_MAX, INT_MAX); + region32_init_rect (®ion, + INT_MIN, INT_MIN, INT_MAX, INT_MAX); + region32_union_rect (®ion, ®ion, + -1, -1, INT_MAX, INT_MAX); + region32_union_rect (®ion, ®ion, + INT_MIN, -1, INT_MAX, INT_MAX); + region32_union_rect (®ion, ®ion, + -1, INT_MIN, INT_MAX, INT_MAX); dump_region ("fuller", ®ion); /* Covering all */ - pixman_region32_init_rect (®ion, - 0, INT_MIN, 10, INT_MAX); - pixman_region32_union_rect (®ion, ®ion, - 20, -234, 10, INT_MAX); - pixman_region32_union_rect (®ion, ®ion, - 50, INT_MAX - 234, 10, 234); + region32_init_rect (®ion, + 0, INT_MIN, 10, INT_MAX); + region32_union_rect (®ion, ®ion, + 20, -234, 10, INT_MAX); + region32_union_rect (®ion, ®ion, + 50, INT_MAX - 234, 10, 234); dump_region ("all of the y axis", ®ion); /* two rows */ - pixman_region32_init_rect (®ion, - 100, 100, 200, 50); - pixman_region32_union_rect (®ion, ®ion, - 100, 200, 200, 50); + region32_init_rect (®ion, + 100, 100, 200, 50); + region32_union_rect (®ion, ®ion, + 100, 200, 200, 50); dump_region ("two rows", ®ion); /* op */ printf ("-=- op\n"); - pixman_region32_init_rect (®ion1, 100, 100, 200, 200); - pixman_region32_init_rect (®ion2, 200, 200, 200, 200); + region32_init_rect (®ion1, 100, 100, 200, 200); + region32_init_rect (®ion2, 200, 200, 200, 200); region_op (UNION, ®ion, ®ion1, ®ion2); dump_region ("union: ", ®ion); printf ("-=- op2\n"); - pixman_region32_init_rect (®ion1, 100, 100, 200, 200); - pixman_region32_union_rect (®ion1, ®ion1, 100, 400, 200, 50); + region32_init_rect (®ion1, 100, 100, 200, 200); + region32_union_rect (®ion1, ®ion1, 100, 400, 200, 50); dump_region ("input: ", ®ion1); - pixman_region32_init_rect (®ion2, 150, 50, 10, 520); + region32_init_rect (®ion2, 150, 50, 10, 520); region_op (INTERSECT, ®ion, ®ion1, ®ion2); printf ("-=- op2\n"); - pixman_region32_init_rect (®ion1, 100, 100, 200, 200); - pixman_region32_union_rect (®ion1, ®ion1, 100, 400, 200, 50); + region32_init_rect (®ion1, 100, 100, 200, 200); + region32_union_rect (®ion1, ®ion1, 100, 400, 200, 50); - pixman_region32_init_rect (®ion2, 150, 50, 10, 520); - pixman_region32_union_rect (®ion2, ®ion2, 10, 10, 342, 23); + region32_init_rect (®ion2, 150, 50, 10, 520); + region32_union_rect (®ion2, ®ion2, 10, 10, 342, 23); region_op (XOR, ®ion, ®ion1, ®ion2); printf ("-=- path\n"); - pixman_region32_init_rect (®ion1, 100, 100, 200, 200); + region32_init_rect (®ion1, 100, 100, 200, 200); corners = region_path (®ion1, &n_corners); dump_corners (corners, n_corners); /* Slightly more complex region */ - pixman_region32_init_rect (®ion, 0, 0, 100, 100); - pixman_region32_union_rect (®ion, ®ion, 50, 50, 100, 100); + region32_init_rect (®ion, 0, 0, 100, 100); + region32_union_rect (®ion, ®ion, 50, 50, 100, 100); assert (region_contains_point (®ion, 75, 75, NULL)); assert (!region_contains_point (®ion, 25, 125, NULL)); @@ -1243,9 +1386,9 @@ main () dump_corners (corners, n_corners); /* even more complex region */ - pixman_region32_init_rect (®ion, 0, 0, 100, 100); - pixman_region32_union_rect (®ion, ®ion, 50, 50, 100, 100); - pixman_region32_union_rect (®ion, ®ion, 200, 0, 50, 50); + region32_init_rect (®ion, 0, 0, 100, 100); + region32_union_rect (®ion, ®ion, 50, 50, 100, 100); + region32_union_rect (®ion, ®ion, 200, 0, 50, 50); printf ("-=- more complex path\n"); @@ -1254,11 +1397,11 @@ main () dump_corners (corners, n_corners); /* even more complex region */ - pixman_region32_init_rect (®ion, 0, 0, 100, 100); - pixman_region32_union_rect (®ion, ®ion, 50, 50, 100, 100); - pixman_region32_union_rect (®ion, ®ion, 150, 0, 50, 50); - pixman_region32_init_rect (®ion2, 75, 75, 50, 50); - pixman_region32_subtract (®ion, ®ion, ®ion2); + region32_init_rect (®ion, 0, 0, 100, 100); + region32_union_rect (®ion, ®ion, 50, 50, 100, 100); + region32_union_rect (®ion, ®ion, 150, 0, 50, 50); + region32_init_rect (®ion2, 75, 75, 50, 50); + region32_subtract (®ion, ®ion, ®ion2); printf ("-=- more complex path\n"); |