diff options
Diffstat (limited to 'android/skin/region.c')
| -rw-r--r-- | android/skin/region.c | 1448 |
1 files changed, 0 insertions, 1448 deletions
diff --git a/android/skin/region.c b/android/skin/region.c deleted file mode 100644 index a5f26a5..0000000 --- a/android/skin/region.c +++ /dev/null @@ -1,1448 +0,0 @@ -/* Copyright (C) 2007-2008 The Android Open Source Project -** -** This software is licensed under the terms of the GNU General Public -** License version 2, as published by the Free Software Foundation, and -** may be copied, distributed, and modified under those terms. -** -** This program is distributed in the hope that it will be useful, -** but WITHOUT ANY WARRANTY; without even the implied warranty of -** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -** GNU General Public License for more details. -*/ -#include "android/skin/region.h" -#include <limits.h> -#include <string.h> -#include <stdlib.h> /* malloc/free */ - -/************************************************************************* - ************************************************************************* - **** - **** ASSERTION SUPPORT - **** - **** - ****/ - -#ifdef UNIT_TEST -#include <stdlib.h> -#include <stdio.h> -static void -_rpanic(void) -{ - *((char*)(void*)0) = 1; /* should SEGFAULT */ - /* put a breakpoint here */ - exit(1); -} - -#define RASSERT(cond) \ - ({ if (!(cond)) { fprintf(stderr, "%s:%d:%s: assertion failed: %s", \ - __FILE__, __LINE__, __FUNCTION__, #cond ); _rpanic(); } }) - -#else -#define RASSERT(cond) ((void)0) -#endif - - -/************************************************************************* - ************************************************************************* - **** - **** IMPLEMENTATION DETAILS - **** - **** - ****/ - -/* this implementation of regions encodes the the region's spans with the - following format: - - region ::= yband+ YSENTINEL - yband ::= YTOP YBOTTOM scanline - scanline ::= span+ XSENTINEL - span ::= XLEFT XRIGHT - - XSENTINEL ::= 0x7fff - YSENTINEL := 0x7fff - - all values are sorted in increasing order, which means that: - - - YTOP1 < YBOTTOM1 <= YTOP2 < YBOTTOM2 <= .... < YSENTINEL - - XLEFT1 < XRIGHT1 < XLEFT2 < XRIGHT2 < .... < XSENTINEL - (in a given scanline) -*/ - -/* convenience shortbuts */ -typedef SkinRegionRun Run; -typedef SkinRegion Region; - -#define RUNS_RECT_COUNT 6 /* YTOP YBOT XLEFT XRIGHT XSENTINEL YSENTINEL */ - -#define XSENTINEL SKIN_REGION_SENTINEL -#define YSENTINEL SKIN_REGION_SENTINEL - -#define RUNS_EMPTY ((Run*)(void*)(-1)) -#define RUNS_RECT ((Run*)(void*)(0)) - -static __inline__ int -region_isEmpty( Region* r ) -{ - return r->runs == RUNS_EMPTY; -} - -static __inline__ int -region_isRect( Region* r ) -{ - return r->runs == RUNS_RECT; -} - -static __inline__ int -region_isComplex( Region* r ) -{ - return r->runs != RUNS_EMPTY && r->runs != RUNS_RECT; -} - -/** RunStore: ref-counted storage for runs - **/ - -typedef struct { - int refcount; - int count; -} RunStore; - -static void -runstore_free( RunStore* s ) -{ - free(s); -} - -static RunStore* -runstore_alloc( int count ) -{ - RunStore* s = malloc( sizeof(*s) + sizeof(Run)*count ); - RASSERT(s != NULL); - s->count = count; - s->refcount = 1; - return s; -} - -static RunStore* -runstore_edit( RunStore* s ) -{ - RunStore* s2; - - if (s->refcount == 1) - return s; - - s2 = runstore_alloc( s->count ); - if (s2) { - memcpy( s2, s, sizeof(*s) + s->count*sizeof(Run) ); - s->refcount -= 1; - s2->refcount = 1; - } - return s2; -} - -static void -runstore_unrefp( RunStore* *ps ) -{ - RunStore* s = *ps; - if (s != NULL) { - if (s->refcount <= 0) - runstore_free(s); - *ps = NULL; - } -} - -static RunStore* -runstore_ref( RunStore* s ) -{ - if (s) s->refcount += 1; - return s; -} - -static __inline__ RunStore* -runstore_from_runs( Run* runs ) -{ - RASSERT(runs != RUNS_EMPTY); - RASSERT(runs != RUNS_RECT); - return (RunStore*)runs - 1; -} - -static __inline__ Run* -runstore_to_runs( RunStore* s ) -{ - RASSERT(s != NULL); - return (Run*)(s + 1); -} - -static Run* -region_edit( Region* r ) -{ - RunStore* s; - - RASSERT(region_isComplex(r)); - - s = runstore_from_runs(r->runs); - s = runstore_edit(s); - r->runs = runstore_to_runs(s); - return r->runs; -} - -/** Run parsing - **/ - -static Run* -runs_next_scanline( Run* runs ) -{ - RASSERT(runs[0] != YSENTINEL && runs[1] != YSENTINEL ); - runs += 2; - do { runs += 1; } while (runs[-1] != XSENTINEL); - return runs; -} - -static Run* -runs_find_y( Run* runs, int y ) -{ - do { - int ybot, ytop = runs[0]; - - if (y < ytop) - return NULL; - - ybot = runs[1]; - if (y < ybot) - return runs; - - runs = runs_next_scanline( runs ); - } while (runs[0] != YSENTINEL); - - return NULL; -} - -static void -runs_set_rect( Run* runs, SkinRect* rect ) -{ - runs[0] = rect->pos.y; - runs[1] = rect->pos.y + rect->size.h; - runs[2] = rect->pos.x; - runs[3] = rect->pos.x + rect->size.w; - runs[4] = XSENTINEL; - runs[5] = YSENTINEL; -} - -static Run* -runs_copy_scanline( Run* dst, Run* src ) -{ - RASSERT(src[0] != YSENTINEL); - RASSERT(src[1] != YSENTINEL); - dst[0] = src[0]; - dst[1] = src[1]; - src += 2; - dst += 2; - do { *dst++ = *src++; } while (src[-1] != XSENTINEL); - return dst; -} - -static Run* -runs_copy_scanline_adj( Run* dst, Run* src, int ytop, int ybot ) -{ - Run* runs2 = runs_copy_scanline( dst, src ); - dst[0] = (Run) ytop; - dst[1] = (Run) ybot; - return runs2; -} - -static __inline__ Run* -runs_add_span( Run* dst, int left, int right ) -{ - dst[0] = (Run) left; - dst[1] = (Run) right; - return dst + 2; -} - -static __inline__ int -runs_get_count( Run* runs ) -{ - RunStore* s = runstore_from_runs(runs); - return s->count; -} - - -static void -runs_coalesce_band( Run* *psrc_spans, Run* *pdst_spans, SkinBox* minmax ) -{ - Run* sspan = *psrc_spans; - Run* dspan = *pdst_spans; - int pleft = sspan[0]; - int pright = sspan[1]; - int xleft, xright; - - RASSERT(pleft != XSENTINEL); - RASSERT(pright != XSENTINEL); - RASSERT(pleft < pright); - - if (pleft < minmax->x1) minmax->x1 = pleft; - - sspan += 2; - xleft = sspan[0]; - - while (xleft != XSENTINEL) - { - xright = sspan[1]; - RASSERT(xright != XSENTINEL); - RASSERT(xleft < xright); - - if (xleft == pright) { - pright = xright; - } else { - dspan[0] = (Run) pleft; - dspan[1] = (Run) pright; - dspan += 2; - } - sspan += 2; - xleft = sspan[0]; - } - dspan[0] = (Run) pleft; - dspan[1] = (Run) pright; - dspan[2] = XSENTINEL; - dspan += 3; - sspan += 1; /* skip XSENTINEL */ - - if (pright > minmax->x2) minmax->x2 = pright; - - *psrc_spans = sspan; - *pdst_spans = dspan; -} - - -static int -runs_coalesce( Run* dst, Run* src, SkinBox* minmax ) -{ - Run* prev = NULL; - Run* dst0 = dst; - int ytop = src[0]; - int ybot; - - while (ytop != YSENTINEL) - { - Run* sspan = src + 2; - Run* dspan = dst + 2; - - ybot = src[1]; - RASSERT( ytop < ybot ); - RASSERT( ybot != YSENTINEL ); - RASSERT( src[2] != XSENTINEL ); - - if (ytop < minmax->y1) minmax->y1 = ytop; - if (ybot > minmax->y2) minmax->y2 = ybot; - - dst[0] = (Run) ytop; - dst[1] = (Run) ybot; - - runs_coalesce_band( &sspan, &dspan, minmax ); - - if (prev && prev[1] == dst[0] && (dst-prev) == (dspan-dst) && - !memcmp(prev+2, dst+2, (dspan-dst-2)*sizeof(Run))) - { - /* coalesce two identical bands */ - prev[1] = dst[1]; - } - else - { - prev = dst; - dst = dspan; - } - src = sspan; - ytop = src[0]; - } - dst[0] = YSENTINEL; - return (dst + 1 - dst0); -} - -/************************************************************************* - ************************************************************************* - **** - **** PUBLIC API - **** - ****/ - -void -skin_region_init_empty( SkinRegion* r ) -{ - /* empty region */ - r->bounds.pos.x = r->bounds.pos.y = 0; - r->bounds.size.w = r->bounds.size.h = 0; - r->runs = RUNS_EMPTY; -} - -void -skin_region_init( SkinRegion* r, int x1, int y1, int x2, int y2 ) -{ - if (x1 >= x2 || y1 >= y2) { - skin_region_init_empty(r); - return; - } - r->bounds.pos.x = x1; - r->bounds.pos.y = y1; - r->bounds.size.w = x2 - x1; - r->bounds.size.h = y2 - y1; - r->runs = RUNS_RECT; -} - -void -skin_region_init_rect( SkinRegion* r, SkinRect* rect ) -{ - if (rect == NULL || rect->size.w <= 0 || rect->size.h <= 0) { - skin_region_init_empty(r); - return; - } - r->bounds = rect[0]; - r->runs = RUNS_RECT; -} - -void -skin_region_init_box( SkinRegion* r, SkinBox* box ) -{ - if (box == NULL || box->x1 >= box->x2 || box->y1 >= box->y2) { - skin_region_init_empty(r); - return; - } - r->bounds.pos.x = box->x1; - r->bounds.pos.y = box->y1; - r->bounds.size.w = box->x2 - box->x1; - r->bounds.size.h = box->y2 - box->y1; - r->runs = RUNS_RECT; -} - -void -skin_region_init_copy( SkinRegion* r, SkinRegion* src ) -{ - if (src == NULL || region_isEmpty(src)) - skin_region_init_empty(r); - else { - r[0] = src[0]; - if (region_isComplex(src)) { - RunStore* s = runstore_from_runs(r->runs); - runstore_ref(s); - } - } -} - - -void -skin_region_reset( SkinRegion* r ) -{ - if (r != NULL) { - if (region_isComplex(r)) { - RunStore* s = runstore_from_runs(r->runs); - runstore_unrefp( &s ); - } - skin_region_init_empty(r); - } -} - - - -void -skin_region_copy( SkinRegion* r, SkinRegion* src ) -{ - skin_region_reset(r); - skin_region_init_copy(r, src); -} - - -int -skin_region_equals( SkinRegion* r1, SkinRegion* r2 ) -{ - Run *runs1, *runs2; - RunStore *store1, *store2; - - if (r1 == r2) - return 1; - - if (!skin_rect_equals( &r1->bounds, &r2->bounds )) - return 0; - - runs1 = r1->runs; - runs2 = r2->runs; - - if (runs1 == runs2) /* empties and rects */ - return 1; - - if ( !region_isComplex(r1) || !region_isComplex(r2) ) - return 0; - - store1 = runstore_from_runs(runs1); - store2 = runstore_from_runs(runs2); - - if (store1->count == store2->count && - !memcmp( (char*)runs1, (char*)runs2, store1->count*sizeof(Run) ) ) - return 1; - - return 0; -} - -void -skin_region_translate( SkinRegion* r, int dx, int dy ) -{ - Run* runs; - - if (region_isEmpty(r)) - return; - - skin_rect_translate( &r->bounds, dx, dy ); - if (region_isRect(r)) - return; - - runs = region_edit(r); - while (runs[0] != YSENTINEL) { - int ytop = runs[0]; - int ybot = runs[1]; - - RASSERT(ybot != YSENTINEL); - runs[0] = (Run)(ytop + dy); - runs[1] = (Run)(ybot + dy); - runs += 2; - while (runs[0] != XSENTINEL) { - int xleft = runs[0]; - int xright = runs[1]; - RASSERT(xright != YSENTINEL); - runs[0] = (Run)(xleft + dx); - runs[1] = (Run)(xright + dx); - runs += 2; - } - runs += 1; - } -} - -void -skin_region_get_bounds( SkinRegion* r, SkinRect* bounds ) -{ - if (r != NULL) { - bounds[0] = r->bounds; - } else { - bounds->pos.x = bounds->pos.y = 0; - bounds->size.w = bounds->size.h = 0; - } -} - -int -skin_region_is_empty( SkinRegion* r ) -{ - return region_isEmpty(r); -} - -int -skin_region_is_rect( SkinRegion* r ) -{ - return region_isRect(r); -} - -int -skin_region_is_complex( SkinRegion* r ) -{ - return region_isComplex(r); -} - -void -skin_region_swap( SkinRegion* r, SkinRegion* r2 ) -{ - SkinRegion tmp; - tmp = r[0]; - r[0] = r2[0]; - r2[0] = tmp; -} - - -SkinOverlap -skin_region_contains( SkinRegion* r, int x, int y ) -{ - if (region_isEmpty(r)) - return SKIN_OUTSIDE; - if (region_isRect(r)) { - return skin_rect_contains(&r->bounds,x,y); - } else { - Run* runs = runs_find_y( r->runs, y ); - if (runs != NULL) { - runs += 2; - do { - int xright, xleft = runs[0]; - - if (x < xleft) // also x < xleft == XSENTINEL - break; - xright = runs[1]; - if (xright == XSENTINEL) - break; - if (x < xright) - return SKIN_INSIDE; - runs += 2; - } while (runs[0] != XSENTINEL); - } - return SKIN_OUTSIDE; - } -} - - -SkinOverlap -skin_region_contains_rect( SkinRegion* r, SkinRect* rect ) -{ - SkinRegion r2[1]; - skin_region_init_rect( r2, rect ); - return skin_region_test_intersect( r, r2 ); -} - - -SkinOverlap -skin_region_contains_box( SkinRegion* r, SkinBox* b ) -{ - SkinRegion r2[1]; - - skin_region_init_box( r2, b ); - return skin_region_test_intersect( r, r2 ); -} - - - -#define FLAG_REGION_1 (1 << 0) -#define FLAG_REGION_2 (1 << 1) -#define FLAG_REGION_BOTH (1 << 2) - -SkinOverlap -skin_region_test_intersect( SkinRegion* r1, - SkinRegion* r2 ) -{ - Run *runs1, *runs2; - Run run2_tmp[ RUNS_RECT_COUNT ]; - SkinRect r; - - if (region_isEmpty(r1) || region_isEmpty(r2)) - return SKIN_OUTSIDE; - - if ( !skin_rect_intersect( &r, &r1->bounds, &r2->bounds) ) - return SKIN_OUTSIDE; - - if (region_isRect(r1)) { - if (region_isRect(r2)) { - return skin_rect_contains_rect(&r1->bounds, &r2->bounds); - } else { - SkinRegion* tmp = r1; - r1 = r2; - r2 = tmp; - } - } - /* here r1 is guaranteed to be complex, r2 is either rect of complex */ - runs1 = r1->runs; - if (region_isRect(r2)) { - runs2 = run2_tmp; - runs_set_rect(runs2, &r2->bounds); - } - else { - runs2 = r2->runs; - } - - { - int flags = 0; - - while (runs1[0] != YSENTINEL && runs2[0] != YSENTINEL) - { - int ytop1 = runs1[0]; - int ybot1 = runs1[1]; - int ytop2 = runs2[0]; - int ybot2 = runs2[1]; - - if (ybot1 <= ytop2) - { - /* band1 over band2 */ - flags |= FLAG_REGION_1; - runs1 = runs_next_scanline( runs1 ); - } - else if (ybot2 <= ytop1) - { - /* band2 over band1 */ - flags |= FLAG_REGION_2; - runs2 = runs_next_scanline( runs2 ); - } - else /* band1 and band2 overlap */ - { - Run* span1; - Run* span2; - int ybot; - - if (ytop1 < ytop2) { - flags |= FLAG_REGION_1; - ytop1 = ytop2; - } else if (ytop2 < ytop1) { - flags |= FLAG_REGION_2; - ytop2 = ytop1; - } - - ybot = (ybot1 < ybot2) ? ybot1 : ybot2; - - span1 = runs1 + 2; - span2 = runs2 + 2; - - while (span1[0] != XSENTINEL && span2[0] != XSENTINEL) - { - int xleft1 = span1[0]; - int xright1 = span1[1]; - int xleft2 = span2[0]; - int xright2 = span2[1]; - - RASSERT(xright1 != XSENTINEL); - RASSERT(xright2 != XSENTINEL); - - if (xright1 <= xleft2) { - flags |= FLAG_REGION_1; - span1 += 2; - } - else if (xright2 <= xleft1) { - flags |= FLAG_REGION_2; - span2 += 2; - } - else { - int xright; - - if (xleft1 < xleft2) { - flags |= FLAG_REGION_1; - xleft1 = xleft2; - } else if (xleft2 < xleft1) { - flags |= FLAG_REGION_2; - xleft2 = xleft1; - } - - xright = (xright1 < xright2) ? xright1 : xright2; - - flags |= FLAG_REGION_BOTH; - - if (xright == xright1) - span1 += 2; - if (xright == xright2) - span2 += 2; - } - } - - if (span1[0] != XSENTINEL) { - flags |= FLAG_REGION_1; - } - - if (span2[0] != XSENTINEL) { - flags |= FLAG_REGION_2; - } - - if (ybot == ybot1) - runs1 = runs_next_scanline( runs1 ); - - if (ybot == ybot2) - runs2 = runs_next_scanline( runs2 ); - } - } - - if (runs1[0] != YSENTINEL) { - flags |= FLAG_REGION_1; - } - - if (runs2[0] != YSENTINEL) { - flags |= FLAG_REGION_2; - } - - if ( !(flags & FLAG_REGION_BOTH) ) { - /* no intersection at all */ - return SKIN_OUTSIDE; - } - - if ( (flags & FLAG_REGION_2) != 0 ) { - /* intersection + overlap */ - return SKIN_OVERLAP; - } - - return SKIN_INSIDE; - } -} - -typedef struct { - Run* runs1; - Run* runs2; - Run* runs_base; - Run* runs; - RunStore* store; - Region result[1]; - Run runs1_rect[ RUNS_RECT_COUNT ]; - Run runs2_rect[ RUNS_RECT_COUNT ]; -} RegionOperator; - - -static void -region_operator_init( RegionOperator* o, - Region* r1, - Region* r2 ) -{ - int run1_count, run2_count; - int maxruns; - - RASSERT( !region_isEmpty(r1) ); - RASSERT( !region_isEmpty(r2) ); - - if (region_isRect(r1)) { - run1_count = RUNS_RECT_COUNT; - o->runs1 = o->runs1_rect; - runs_set_rect( o->runs1, &r1->bounds ); - } else { - o->runs1 = r1->runs; - run1_count = runs_get_count(r1->runs); - } - - if (region_isRect(r2)) { - run2_count = RUNS_RECT_COUNT; - o->runs2 = o->runs2_rect; - runs_set_rect( o->runs2, &r2->bounds ); - } else { - o->runs2 = r2->runs; - run2_count = runs_get_count(r2->runs); - } - - maxruns = run1_count < run2_count ? run2_count : run1_count; - o->store = runstore_alloc( 3*maxruns ); - o->runs_base = runstore_to_runs(o->store); -} - - -static void -region_operator_do( RegionOperator* o, int wanted ) -{ - Run* runs1 = o->runs1; - Run* runs2 = o->runs2; - Run* runs = o->runs_base; - int ytop1 = runs1[0]; - int ytop2 = runs2[0]; - - if (ytop1 != YSENTINEL && ytop2 != YSENTINEL) - { - int ybot1, ybot2; - - while (ytop1 != YSENTINEL && ytop2 != YSENTINEL) - { - int ybot; - - ybot1 = runs1[1]; - ybot2 = runs2[1]; - - RASSERT(ybot1 != YSENTINEL); - RASSERT(ybot2 != YSENTINEL); - - if (ybot1 <= ytop2) { - if (wanted & FLAG_REGION_1) - runs = runs_copy_scanline_adj( runs, runs1, ytop1, ybot1 ); - runs1 = runs_next_scanline( runs1 ); - ytop1 = runs1[0]; - continue; - } - - if (ybot2 <= ytop1) { - if (wanted & FLAG_REGION_2) - runs = runs_copy_scanline_adj( runs, runs2, ytop2, ybot2 ); - runs2 = runs_next_scanline(runs2); - ytop2 = runs2[0]; - continue; - } - - if (ytop1 < ytop2) { - if (wanted & FLAG_REGION_1) - runs = runs_copy_scanline_adj( runs, runs1, ytop1, ytop2 ); - ytop1 = ytop2; - } - else if (ytop2 < ytop1) { - if (wanted & FLAG_REGION_2) - runs = runs_copy_scanline_adj( runs, runs2, ytop2, ytop1 ); - ytop2 = ytop1; - } - - ybot = (ybot1 <= ybot2) ? ybot1 : ybot2; - - runs[0] = (Run) ytop1; - runs[1] = (Run) ybot; - - /* do the common band */ - { - Run* span1 = runs1 + 2; - Run* span2 = runs2 + 2; - Run* span = runs + 2; - int xleft1 = span1[0]; - int xleft2 = span2[0]; - int xright1, xright2; - - while (xleft1 != XSENTINEL && xleft2 != XSENTINEL) - { - int xright; - - xright1 = span1[1]; - xright2 = span2[1]; - - RASSERT(xright1 != XSENTINEL); - RASSERT(xright2 != XSENTINEL); - - if (xright1 <= xleft2) { - if (wanted & FLAG_REGION_1) - span = runs_add_span( span, xleft1, xright1 ); - span1 += 2; - xleft1 = span1[0]; - continue; - } - - if (xright2 <= xleft1) { - if (wanted & FLAG_REGION_2) - span = runs_add_span( span, xleft2, xright2 ); - span2 += 2; - xleft2 = span2[0]; - continue; - } - - if (xleft1 < xleft2) { - if (wanted & FLAG_REGION_1) - span = runs_add_span( span, xleft1, xleft2 ); - xleft1 = xleft2; - } - - else if (xleft2 < xleft1) { - if (wanted & FLAG_REGION_2) - span = runs_add_span( span, xleft2, xleft1 ); - xleft2 = xleft1; - } - - xright = (xright1 <= xright2) ? xright1 : xright2; - - if (wanted & FLAG_REGION_BOTH) - span = runs_add_span( span, xleft1, xright ); - - xleft1 = xleft2 = xright; - - if (xright == xright1) { - span1 += 2; - xleft1 = span1[0]; - } - if (xright == xright2) { - span2 += 2; - xleft2 = span2[0]; - } - } - - if (wanted & FLAG_REGION_1) { - while (xleft1 != XSENTINEL) { - RASSERT(span1[1] != XSENTINEL); - span[0] = (Run) xleft1; - span[1] = span1[1]; - span += 2; - span1 += 2; - xleft1 = span1[0]; - } - } - - if (wanted & FLAG_REGION_2) { - while (xleft2 != XSENTINEL) { - RASSERT(span2[1] != XSENTINEL); - span[0] = (Run) xleft2; - span[1] = span2[1]; - span += 2; - span2 += 2; - xleft2 = span2[0]; - } - } - - if (span > runs + 2) { - span[0] = XSENTINEL; - runs = span + 1; - } - } - - ytop1 = ytop2 = ybot; - - if (ybot == ybot1) { - runs1 = runs_next_scanline( runs1 ); - ytop1 = runs1[0]; - } - if (ybot == ybot2) { - runs2 = runs_next_scanline( runs2 ); - ytop2 = runs2[0]; - } - } - } - - if ((wanted & FLAG_REGION_1) != 0) { - while (ytop1 != YSENTINEL) { - runs = runs_copy_scanline_adj( runs, runs1, ytop1, runs1[1] ); - runs1 = runs_next_scanline(runs1); - ytop1 = runs1[0]; - } - } - - if ((wanted & FLAG_REGION_2) != 0) { - while (ytop2 != YSENTINEL) { - runs = runs_copy_scanline_adj( runs, runs2, ytop2, runs2[1] ); - runs2 = runs_next_scanline(runs2); - ytop2 = runs2[0]; - } - } - - runs[0] = YSENTINEL; - o->runs = runs + 1; -} - -/* returns 1 if the result is not empty */ -static int -region_operator_done( RegionOperator* o ) -{ - Run* src = o->runs; - int count; - SkinBox minmax; - RunStore* store; - - if (src <= o->runs_base + 1) { - /* result is empty */ - skin_region_init_empty( o->result ); - return 0; - } - - /* coalesce the temp runs in-place and compute the corresponding bounds */ - minmax.x1 = minmax.y1 = INT_MAX; - minmax.x2 = minmax.y2 = INT_MIN; - - count = runs_coalesce( o->runs_base, o->runs_base, &minmax ); - if (count == 1) { - /* result is empty */ - skin_region_init_empty( o->result ); - } - else - { - skin_box_to_rect( &minmax, &o->result->bounds ); - if (count == RUNS_RECT_COUNT) { - o->result->runs = RUNS_RECT; - } - else - { - /* result is complex */ - store = runstore_alloc( count ); - o->result->runs = runstore_to_runs(store); - memcpy( o->result->runs, o->runs_base, count*sizeof(Run) ); - } - } - - /* release temporary runstore */ - runstore_unrefp( &o->store ); - - return region_isEmpty(o->result); -} - - - -int -skin_region_intersect( SkinRegion* r, SkinRegion* r2 ) -{ - RegionOperator oper[1]; - - if (region_isEmpty(r)) - return 0; - - if (region_isEmpty(r2)) - return 1; - - if ( skin_rect_contains_rect( &r->bounds, &r2->bounds ) == SKIN_OUTSIDE ) { - skin_region_init_empty(r); - return 0; - } - - region_operator_init( oper, r, r2 ); - region_operator_do( oper, FLAG_REGION_BOTH ); - region_operator_done( oper ); - - skin_region_swap( r, oper->result ); - skin_region_reset( oper->result ); - - return region_isEmpty( r ); -} - - -/* performs r = (intersect r (region+_from_rect rect)), returns true iff - the resulting region is not empty */ -int -skin_region_intersect_rect( SkinRegion* r, SkinRect* rect ) -{ - Region r2[1]; - - skin_region_init_rect( r2, rect ); - return skin_region_intersect( r, r2 ); -} - -/* performs r = (union r r2) */ -void -skin_region_union( SkinRegion* r, SkinRegion* r2 ) -{ - RegionOperator oper[1]; - - if (region_isEmpty(r)) { - skin_region_copy(r, r2); - return; - } - - if (region_isEmpty(r2)) - return; - - region_operator_init( oper, r, r2 ); - region_operator_do( oper, FLAG_REGION_1|FLAG_REGION_2|FLAG_REGION_BOTH ); - region_operator_done( oper ); - - skin_region_swap( r, oper->result ); - skin_region_reset( oper->result ); -} - -void -skin_region_union_rect( SkinRegion* r, SkinRect* rect ) -{ - Region r2[1]; - - skin_region_init_rect(r2, rect); - return skin_region_union( r, r2 ); -} - -/* performs r = (difference r r2) */ -void -skin_region_substract( SkinRegion* r, SkinRegion* r2 ) -{ - RegionOperator oper[1]; - - if (region_isEmpty(r) || region_isEmpty(r2)) - return; - - if ( skin_rect_contains_rect( &r->bounds, &r2->bounds ) == SKIN_OUTSIDE ) { - skin_region_init_empty(r); - return; - } - - region_operator_init( oper, r, r2 ); - region_operator_do( oper, FLAG_REGION_1 ); - region_operator_done( oper ); - - skin_region_swap( r, oper->result ); - skin_region_reset( oper->result ); -} - -void -skin_region_substract_rect( SkinRegion* r, SkinRect* rect ) -{ - Region r2[1]; - - skin_region_init_rect(r2, rect); - return skin_region_substract( r, r2 ); -} - -/* performs r = (xor r r2) */ -void -skin_region_xor( SkinRegion* r, SkinRegion* r2 ) -{ - RegionOperator oper[1]; - - if (region_isEmpty(r)) { - skin_region_copy(r, r2); - return; - } - - if (region_isEmpty(r2)) - return; - - if ( skin_rect_contains_rect( &r->bounds, &r2->bounds ) == SKIN_OUTSIDE ) { - skin_region_init_empty(r); - return; - } - - region_operator_init( oper, r, r2 ); - region_operator_do( oper, FLAG_REGION_1 ); - region_operator_done( oper ); - - skin_region_swap( r, oper->result ); - skin_region_reset( oper->result ); -} - - -void -skin_region_iterator_init( SkinRegionIterator* iter, - SkinRegion* region ) -{ - iter->region = region; - iter->band = NULL; - iter->span = NULL; -} - -int -skin_region_iterator_next( SkinRegionIterator* iter, SkinRect *rect ) -{ - static const Run dummy[ 2 ] = { XSENTINEL, YSENTINEL }; - - Run* span = iter->span; - Run* band = iter->band; - - if (span == NULL) { - Region* r = iter->region; - if (region_isEmpty(r)) - return 0; - if (region_isRect(r)) { - rect[0] = r->bounds; - iter->span = (Run*) dummy; - return 1; - } - iter->band = band = r->runs; - iter->span = span = r->runs + 2; - } - else if (band == NULL) - return 0; - - while (span[0] == XSENTINEL) { - band = span + 1; - if (band[0] == YSENTINEL || band[1] == YSENTINEL) - return 0; - - iter->band = band; - iter->span = span = band + 2; - } - - if (span[1] == XSENTINEL) - return 0; - - rect->pos.y = band[0]; - rect->pos.x = span[0]; - rect->size.h = band[1] - band[0]; - rect->size.w = span[1] - span[0]; - - iter->span = span + 2; - return 1; -} - -int -skin_region_iterator_next_box( SkinRegionIterator* iter, SkinBox *box ) -{ - SkinRect rect; - int result = skin_region_iterator_next( iter, &rect ); - - if (result) - skin_box_from_rect( box, &rect ); - - return result; -} - -#ifdef UNIT_TEST - -#include <stdio.h> -#include <stdlib.h> -#include "skin_rect.c" - -static void -panic(void) -{ - *((char*)0) = 1; - exit(0); -} - -static void -_expectCompare( Region* r, const SkinBox* boxes, int count ) -{ - if (count == 0) { - if ( !skin_region_is_empty(r) ) { - printf( " result is not empty\n" ); - panic(); - } - } - else if (count == 1) { - SkinRect rect1, rect2; - if ( !skin_region_is_rect(r) ) { - printf( " result is not a rectangle\n" ); - panic(); - } - skin_region_get_bounds( r, &rect1 ); - skin_box_to_rect( (SkinBox*)boxes, &rect2 ); - if ( !skin_rect_equals( &rect1, &rect2 ) ) { - printf( " result is (%d,%d,%d,%d), expected (%d,%d,%d,%d)\n", - rect1.pos.x, rect1.pos.y, - rect1.pos.x + rect1.size.w, rect1.pos.y + rect1.size.h, - rect2.pos.x, rect2.pos.y, - rect2.pos.x + rect2.size.w, rect2.pos.y + rect2.size.h ); - panic(); - } - } - else { - SkinRegionIterator iter; - SkinBox b; - int n; - - skin_region_iterator_init( &iter, r ); - n = 0; - while (n < count) { - if ( !skin_region_iterator_next_box( &iter, &b ) ) { - printf( "missing region box (%d, %d, %d, %d)\n", - boxes->x1, boxes->y1, boxes->x2, boxes->y2 ); - panic(); - } - - if (b.x1 != boxes->x1 || b.x2 != boxes->x2|| - b.y1 != boxes->y1 || b.y2 != boxes->y2) - { - printf( "invalid region box (%d,%d,%d,%d) expecting (%d,%d,%d,%d)\n", - b.x1, b.y1, b.x2, b.y2, - boxes->x1, boxes->y1, boxes->x2, boxes->y2 ); - panic(); - } - boxes += 1; - n += 1; - } - - if ( skin_region_iterator_next_box( &iter, &b ) ) { - printf( "excess region box (%d,%d,%d,%d)\n", - b.x1, b.y1, b.x2, b.y2 ); - panic(); - } - } -} - - -static void -expectEmptyRegion( Region* r ) -{ - printf( "expectEmptyRegion: " ); - if (!skin_region_is_empty(r)) { - printf( "region not empty !!\n" ); - panic(); - } - printf( "ok\n" ); -} - -static void -expectTestIntersect( Region* r1, Region* r2, SkinOverlap overlap ) -{ - SkinOverlap result; - printf( "expectTestIntersect(%d): ", overlap ); - result = skin_region_test_intersect(r1, r2); - if (result != overlap) { - printf( "bad result %d, expected %d\n", result, overlap ); - panic(); - } - printf( "ok\n" ); -} - -static void -expectRectRegion( Region* r, int x1, int y1, int x2, int y2 ) -{ - SkinRect rect; - SkinBox b; - - printf( "expectRectRegion(%d,%d,%d,%d): ",x1,y1,x2,y2 ); - if (!skin_region_is_rect(r)) { - printf( "region not rect !!\n" ); - panic(); - } - - skin_region_get_bounds( r, &rect ); - skin_box_from_rect( &b, &rect ); - - if (b.x1 != x1 || b.x2 != x2 || b.y1 != y1 || b.y2 != y2) { - printf( "rect region bounds are (%d,%d,%d,%d), expecting (%d,%d,%d,%d)\n", - b.x1, b.y1, b.x2, b.y2, x1, y1, x2, y2 ); - panic(); - } - printf( "ok\n" ); -} - -static void -expectComplexRegion( Region* r, const SkinBox* boxes, int count ) -{ - SkinRegionIterator iter; - SkinBox b; - int n; - - printf( "expectComplexRegion(): " ); - if (!skin_region_is_complex(r)) { - printf( "region is not complex !!\n" ); - panic(); - } - _expectCompare( r, boxes, count ); - printf( "ok\n" ); -} - -static void -expectIntersect( Region* r1, Region* r2, const SkinBox* boxes, int count ) -{ - SkinRegion r[1]; - - printf( "expectIntersect(%d): ", count ); - skin_region_init_copy( r, r1 ); - skin_region_intersect( r, r2 ); - _expectCompare( r, boxes, count ); - printf( "ok\n" ); -} - -static void -expectUnion( Region* r1, Region* r2, const SkinBox* boxes, int count ) -{ - SkinRegion r[1]; - - printf( "expectUnion(%d): ", count ); - skin_region_init_copy( r, r1 ); - skin_region_union( r, r2 ); - _expectCompare( r, boxes, count ); - printf( "ok\n" ); -} - - -static void -expectSubstract( Region* r1, Region* r2, const SkinBox* boxes, int count ) -{ - SkinRegion r[1]; - - printf( "expectSubstract(%d): ", count ); - skin_region_init_copy( r, r1 ); - skin_region_substract( r, r2 ); - _expectCompare( r, boxes, count ); - printf( "ok\n" ); -} - - -int main( void ) -{ - SkinRegion r[1], r2[1]; - - skin_region_init_empty( r ); - expectEmptyRegion( r ); - - skin_region_init( r, 10, 20, 110, 120 ); - expectRectRegion( r, 10, 20, 110, 120 ); - - skin_region_translate( r, 50, 80 ); - expectRectRegion( r, 60, 100, 160, 200 ); - - skin_region_init( r, 10, 10, 40, 40 ); - skin_region_init( r2, 20, 20, 50, 50 ); - expectTestIntersect( r, r2, SKIN_OVERLAP ); - - skin_region_translate(r2, +20, + 20 ); - expectTestIntersect( r, r2, SKIN_OUTSIDE ); - - skin_region_translate(r2, -30, -30 ); - expectTestIntersect( r, r2, SKIN_INSIDE ); - - { - static const SkinBox result1[1] = { - { 20, 20, 40, 40 } - }; - static const SkinBox result2[3] = { - { 10, 10, 40, 20 }, - { 10, 20, 50, 40 }, - { 20, 40, 50, 50 }, - }; - static const SkinBox result3[2] = { - { 10, 10, 40, 20 }, - { 10, 20, 20, 40 }, - }; - - skin_region_init( r, 10, 10, 40, 40 ); - skin_region_init( r2, 20, 20, 50, 50 ); - expectIntersect( r, r2, result1, 1 ); - expectUnion( r, r2, result2, 3 ); - expectSubstract( r, r2, result3, 2 ); - } - - return 0; -} - -#endif /* UNIT_TEST */ |