From 1c94119ae26b94a60bb2c2b33494ed43c3b8a52f Mon Sep 17 00:00:00 2001 From: marha Date: Sun, 16 May 2010 20:50:58 +0000 Subject: svn merge -r588:HEAD ^/branches/released . --- xorg-server/mi/miregion.c | 3690 ++++++++++++++++++++++----------------------- 1 file changed, 1845 insertions(+), 1845 deletions(-) (limited to 'xorg-server/mi/miregion.c') diff --git a/xorg-server/mi/miregion.c b/xorg-server/mi/miregion.c index c48befc6f..ff58c0372 100644 --- a/xorg-server/mi/miregion.c +++ b/xorg-server/mi/miregion.c @@ -1,1845 +1,1845 @@ -/*********************************************************** - -Copyright 1987, 1988, 1989, 1998 The Open Group - -Permission to use, copy, modify, distribute, and sell this software and its -documentation for any purpose is hereby granted without fee, provided that -the above copyright notice appear in all copies and that both that -copyright notice and this permission notice appear in supporting -documentation. - -The above copyright notice and this permission notice shall be included in -all copies or substantial portions of the Software. - -THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR -IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, -FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE -OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN -AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN -CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. - -Except as contained in this notice, the name of The Open Group shall not be -used in advertising or otherwise to promote the sale, use or other dealings -in this Software without prior written authorization from The Open Group. - - -Copyright 1987, 1988, 1989 by -Digital Equipment Corporation, Maynard, Massachusetts. - - All Rights Reserved - -Permission to use, copy, modify, and distribute this software and its -documentation for any purpose and without fee is hereby granted, -provided that the above copyright notice appear in all copies and that -both that copyright notice and this permission notice appear in -supporting documentation, and that the name of Digital not be -used in advertising or publicity pertaining to distribution of the -software without specific, written prior permission. - -DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING -ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL -DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR -ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, -WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, -ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS -SOFTWARE. - -******************************************************************/ - -/* The panoramix components contained the following notice */ -/***************************************************************** - -Copyright (c) 1991, 1997 Digital Equipment Corporation, Maynard, Massachusetts. - -Permission is hereby granted, free of charge, to any person obtaining a copy -of this software and associated documentation files (the "Software"), to deal -in the Software without restriction, including without limitation the rights -to use, copy, modify, merge, publish, distribute, sublicense, and/or sell -copies of the Software. - -The above copyright notice and this permission notice shall be included in -all copies or substantial portions of the Software. - -THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR -IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, -FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL -DIGITAL EQUIPMENT CORPORATION BE LIABLE FOR ANY CLAIM, DAMAGES, INCLUDING, -BUT NOT LIMITED TO CONSEQUENTIAL OR INCIDENTAL DAMAGES, OR OTHER LIABILITY, -WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR -IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. - -Except as contained in this notice, the name of Digital Equipment Corporation -shall not be used in advertising or otherwise to promote the sale, use or other -dealings in this Software without prior written authorization from Digital -Equipment Corporation. - -******************************************************************/ - -#ifdef HAVE_DIX_CONFIG_H -#include -#endif - -#include "regionstr.h" -#include -#include -#include "gc.h" -#include "mi.h" -#include "mispans.h" -#include - -#undef assert -#ifdef REGION_DEBUG -#define assert(expr) { \ - CARD32 *foo = NULL; \ - if (!(expr)) { \ - ErrorF("Assertion failed file %s, line %d: %s\n", \ - __FILE__, __LINE__, #expr); \ - *foo = 0xdeadbeef; /* to get a backtrace */ \ - } \ - } -#else -#define assert(expr) -#endif - -#define good(reg) assert(miValidRegion(reg)) - -/* - * The functions in this file implement the Region abstraction used extensively - * throughout the X11 sample server. A Region is simply a set of disjoint - * (non-overlapping) rectangles, plus an "extent" rectangle which is the - * smallest single rectangle that contains all the non-overlapping rectangles. - * - * A Region is implemented as a "y-x-banded" array of rectangles. This array - * imposes two degrees of order. First, all rectangles are sorted by top side - * y coordinate first (y1), and then by left side x coordinate (x1). - * - * Furthermore, the rectangles are grouped into "bands". Each rectangle in a - * band has the same top y coordinate (y1), and each has the same bottom y - * coordinate (y2). Thus all rectangles in a band differ only in their left - * and right side (x1 and x2). Bands are implicit in the array of rectangles: - * there is no separate list of band start pointers. - * - * The y-x band representation does not minimize rectangles. In particular, - * if a rectangle vertically crosses a band (the rectangle has scanlines in - * the y1 to y2 area spanned by the band), then the rectangle may be broken - * down into two or more smaller rectangles stacked one atop the other. - * - * ----------- ----------- - * | | | | band 0 - * | | -------- ----------- -------- - * | | | | in y-x banded | | | | band 1 - * | | | | form is | | | | - * ----------- | | ----------- -------- - * | | | | band 2 - * -------- -------- - * - * An added constraint on the rectangles is that they must cover as much - * horizontal area as possible: no two rectangles within a band are allowed - * to touch. - * - * Whenever possible, bands will be merged together to cover a greater vertical - * distance (and thus reduce the number of rectangles). Two bands can be merged - * only if the bottom of one touches the top of the other and they have - * rectangles in the same places (of the same width, of course). - * - * Adam de Boor wrote most of the original region code. Joel McCormack - * substantially modified or rewrote most of the core arithmetic routines, - * and added miRegionValidate in order to support several speed improvements - * to miValidateTree. Bob Scheifler changed the representation to be more - * compact when empty or a single rectangle, and did a bunch of gratuitous - * reformatting. - */ - -/* true iff two Boxes overlap */ -#define EXTENTCHECK(r1,r2) \ - (!( ((r1)->x2 <= (r2)->x1) || \ - ((r1)->x1 >= (r2)->x2) || \ - ((r1)->y2 <= (r2)->y1) || \ - ((r1)->y1 >= (r2)->y2) ) ) - -/* true iff (x,y) is in Box */ -#define INBOX(r,x,y) \ - ( ((r)->x2 > x) && \ - ((r)->x1 <= x) && \ - ((r)->y2 > y) && \ - ((r)->y1 <= y) ) - -/* true iff Box r1 contains Box r2 */ -#define SUBSUMES(r1,r2) \ - ( ((r1)->x1 <= (r2)->x1) && \ - ((r1)->x2 >= (r2)->x2) && \ - ((r1)->y1 <= (r2)->y1) && \ - ((r1)->y2 >= (r2)->y2) ) - -#define xallocData(n) xalloc(REGION_SZOF(n)) -#define xfreeData(reg) if ((reg)->data && (reg)->data->size) xfree((reg)->data) - -#define RECTALLOC_BAIL(pReg,n,bail) \ -if (!(pReg)->data || (((pReg)->data->numRects + (n)) > (pReg)->data->size)) \ - if (!miRectAlloc(pReg, n)) { goto bail; } - -#define RECTALLOC(pReg,n) \ -if (!(pReg)->data || (((pReg)->data->numRects + (n)) > (pReg)->data->size)) \ - if (!miRectAlloc(pReg, n)) { return FALSE; } - -#define ADDRECT(pNextRect,nx1,ny1,nx2,ny2) \ -{ \ - pNextRect->x1 = nx1; \ - pNextRect->y1 = ny1; \ - pNextRect->x2 = nx2; \ - pNextRect->y2 = ny2; \ - pNextRect++; \ -} - -#define NEWRECT(pReg,pNextRect,nx1,ny1,nx2,ny2) \ -{ \ - if (!(pReg)->data || ((pReg)->data->numRects == (pReg)->data->size))\ - { \ - if (!miRectAlloc(pReg, 1)) \ - return FALSE; \ - pNextRect = REGION_TOP(pReg); \ - } \ - ADDRECT(pNextRect,nx1,ny1,nx2,ny2); \ - pReg->data->numRects++; \ - assert(pReg->data->numRects<=pReg->data->size); \ -} - - -#define DOWNSIZE(reg,numRects) \ -if (((numRects) < ((reg)->data->size >> 1)) && ((reg)->data->size > 50)) \ -{ \ - RegDataPtr NewData; \ - NewData = (RegDataPtr)xrealloc((reg)->data, REGION_SZOF(numRects)); \ - if (NewData) \ - { \ - NewData->size = (numRects); \ - (reg)->data = NewData; \ - } \ -} - - -BoxRec miEmptyBox = {0, 0, 0, 0}; -RegDataRec miEmptyData = {0, 0}; - -RegDataRec miBrokenData = {0, 0}; -static RegionRec miBrokenRegion = { { 0, 0, 0, 0 }, &miBrokenData }; - -void -InitRegions (void) -{ - pixman_region_set_static_pointers (&miEmptyBox, &miEmptyData, &miBrokenData); -} - -/***************************************************************** - * RegionCreate(rect, size) - * This routine does a simple malloc to make a structure of - * REGION of "size" number of rectangles. - *****************************************************************/ - -RegionPtr -miRegionCreate(BoxPtr rect, int size) -{ - RegionPtr pReg; - - pReg = (RegionPtr)xalloc(sizeof(RegionRec)); - if (!pReg) - return &miBrokenRegion; - - miRegionInit (pReg, rect, size); - - return(pReg); -} - -void -miRegionDestroy(RegionPtr pReg) -{ - pixman_region_fini (pReg); - if (pReg != &miBrokenRegion) - xfree(pReg); -} - -void -miPrintRegion(RegionPtr rgn) -{ - int num, size; - int i; - BoxPtr rects; - - num = REGION_NUM_RECTS(rgn); - size = REGION_SIZE(rgn); - rects = REGION_RECTS(rgn); - ErrorF("[mi] num: %d size: %d\n", num, size); - ErrorF("[mi] extents: %d %d %d %d\n", - rgn->extents.x1, rgn->extents.y1, rgn->extents.x2, rgn->extents.y2); - for (i = 0; i < num; i++) - ErrorF("[mi] %d %d %d %d \n", - rects[i].x1, rects[i].y1, rects[i].x2, rects[i].y2); - ErrorF("[mi] \n"); -} - -Bool -miRegionEqual(RegionPtr reg1, RegionPtr reg2) -{ - return pixman_region_equal (reg1, reg2); -} - -#ifdef DEBUG -Bool -miValidRegion(RegionPtr reg) -{ - int i, numRects; - - if ((reg->extents.x1 > reg->extents.x2) || - (reg->extents.y1 > reg->extents.y2)) - return FALSE; - numRects = REGION_NUM_RECTS(reg); - if (!numRects) - return ((reg->extents.x1 == reg->extents.x2) && - (reg->extents.y1 == reg->extents.y2) && - (reg->data->size || (reg->data == &miEmptyData))); - else if (numRects == 1) - return (!reg->data); - else - { - BoxPtr pboxP, pboxN; - BoxRec box; - - pboxP = REGION_RECTS(reg); - box = *pboxP; - box.y2 = pboxP[numRects-1].y2; - pboxN = pboxP + 1; - for (i = numRects; --i > 0; pboxP++, pboxN++) - { - if ((pboxN->x1 >= pboxN->x2) || - (pboxN->y1 >= pboxN->y2)) - return FALSE; - if (pboxN->x1 < box.x1) - box.x1 = pboxN->x1; - if (pboxN->x2 > box.x2) - box.x2 = pboxN->x2; - if ((pboxN->y1 < pboxP->y1) || - ((pboxN->y1 == pboxP->y1) && - ((pboxN->x1 < pboxP->x2) || (pboxN->y2 != pboxP->y2)))) - return FALSE; - } - return ((box.x1 == reg->extents.x1) && - (box.x2 == reg->extents.x2) && - (box.y1 == reg->extents.y1) && - (box.y2 == reg->extents.y2)); - } -} -#endif /* DEBUG */ - -/***************************************************************** - * RegionInit(pReg, rect, size) - * Outer region rect is statically allocated. - *****************************************************************/ - -void -miRegionInit(RegionPtr pReg, BoxPtr rect, int size) -{ - if (rect) - pixman_region_init_with_extents (pReg, rect); - else - pixman_region_init (pReg); -} - -void -miRegionUninit(RegionPtr pReg) -{ - pixman_region_fini (pReg); -} - -Bool -miRegionBreak (RegionPtr pReg) -{ - xfreeData (pReg); - pReg->extents = miEmptyBox; - pReg->data = &miBrokenData; - return FALSE; -} - -Bool -miRectAlloc(RegionPtr pRgn, int n) -{ - RegDataPtr data; - - if (!pRgn->data) - { - n++; - pRgn->data = xallocData(n); - if (!pRgn->data) - return miRegionBreak (pRgn); - pRgn->data->numRects = 1; - *REGION_BOXPTR(pRgn) = pRgn->extents; - } - else if (!pRgn->data->size) - { - pRgn->data = xallocData(n); - if (!pRgn->data) - return miRegionBreak (pRgn); - pRgn->data->numRects = 0; - } - else - { - if (n == 1) - { - n = pRgn->data->numRects; - if (n > 500) /* XXX pick numbers out of a hat */ - n = 250; - } - n += pRgn->data->numRects; - data = (RegDataPtr)xrealloc(pRgn->data, REGION_SZOF(n)); - if (!data) - return miRegionBreak (pRgn); - pRgn->data = data; - } - pRgn->data->size = n; - return TRUE; -} - -Bool -miRegionCopy(RegionPtr dst, RegionPtr src) -{ - return pixman_region_copy (dst, src); -} - -/*====================================================================== - * Generic Region Operator - *====================================================================*/ - -/*- - *----------------------------------------------------------------------- - * miCoalesce -- - * Attempt to merge the boxes in the current band with those in the - * previous one. We are guaranteed that the current band extends to - * the end of the rects array. Used only by miRegionOp. - * - * Results: - * The new index for the previous band. - * - * Side Effects: - * If coalescing takes place: - * - rectangles in the previous band will have their y2 fields - * altered. - * - pReg->data->numRects will be decreased. - * - *----------------------------------------------------------------------- - */ -_X_INLINE static int -miCoalesce ( - RegionPtr pReg, /* Region to coalesce */ - int prevStart, /* Index of start of previous band */ - int curStart) /* Index of start of current band */ -{ - BoxPtr pPrevBox; /* Current box in previous band */ - BoxPtr pCurBox; /* Current box in current band */ - int numRects; /* Number rectangles in both bands */ - int y2; /* Bottom of current band */ - /* - * Figure out how many rectangles are in the band. - */ - numRects = curStart - prevStart; - assert(numRects == pReg->data->numRects - curStart); - - if (!numRects) return curStart; - - /* - * The bands may only be coalesced if the bottom of the previous - * matches the top scanline of the current. - */ - pPrevBox = REGION_BOX(pReg, prevStart); - pCurBox = REGION_BOX(pReg, curStart); - if (pPrevBox->y2 != pCurBox->y1) return curStart; - - /* - * Make sure the bands have boxes in the same places. This - * assumes that boxes have been added in such a way that they - * cover the most area possible. I.e. two boxes in a band must - * have some horizontal space between them. - */ - y2 = pCurBox->y2; - - do { - if ((pPrevBox->x1 != pCurBox->x1) || (pPrevBox->x2 != pCurBox->x2)) { - return (curStart); - } - pPrevBox++; - pCurBox++; - numRects--; - } while (numRects); - - /* - * The bands may be merged, so set the bottom y of each box - * in the previous band to the bottom y of the current band. - */ - numRects = curStart - prevStart; - pReg->data->numRects -= numRects; - do { - pPrevBox--; - pPrevBox->y2 = y2; - numRects--; - } while (numRects); - return prevStart; -} - - -/* Quicky macro to avoid trivial reject procedure calls to miCoalesce */ - -#define Coalesce(newReg, prevBand, curBand) \ - if (curBand - prevBand == newReg->data->numRects - curBand) { \ - prevBand = miCoalesce(newReg, prevBand, curBand); \ - } else { \ - prevBand = curBand; \ - } - -/*- - *----------------------------------------------------------------------- - * miAppendNonO -- - * Handle a non-overlapping band for the union and subtract operations. - * Just adds the (top/bottom-clipped) rectangles into the region. - * Doesn't have to check for subsumption or anything. - * - * Results: - * None. - * - * Side Effects: - * pReg->data->numRects is incremented and the rectangles overwritten - * with the rectangles we're passed. - * - *----------------------------------------------------------------------- - */ - -_X_INLINE static Bool -miAppendNonO ( - RegionPtr pReg, - BoxPtr r, - BoxPtr rEnd, - int y1, - int y2) -{ - BoxPtr pNextRect; - int newRects; - - newRects = rEnd - r; - - assert(y1 < y2); - assert(newRects != 0); - - /* Make sure we have enough space for all rectangles to be added */ - RECTALLOC(pReg, newRects); - pNextRect = REGION_TOP(pReg); - pReg->data->numRects += newRects; - do { - assert(r->x1 < r->x2); - ADDRECT(pNextRect, r->x1, y1, r->x2, y2); - r++; - } while (r != rEnd); - - return TRUE; -} - -#define FindBand(r, rBandEnd, rEnd, ry1) \ -{ \ - ry1 = r->y1; \ - rBandEnd = r+1; \ - while ((rBandEnd != rEnd) && (rBandEnd->y1 == ry1)) { \ - rBandEnd++; \ - } \ -} - -#define AppendRegions(newReg, r, rEnd) \ -{ \ - int newRects; \ - if ((newRects = rEnd - r)) { \ - RECTALLOC(newReg, newRects); \ - memmove((char *)REGION_TOP(newReg),(char *)r, \ - newRects * sizeof(BoxRec)); \ - newReg->data->numRects += newRects; \ - } \ -} - -/*- - *----------------------------------------------------------------------- - * miRegionOp -- - * Apply an operation to two regions. Called by miUnion, miInverse, - * miSubtract, miIntersect.... Both regions MUST have at least one - * rectangle, and cannot be the same object. - * - * Results: - * TRUE if successful. - * - * Side Effects: - * The new region is overwritten. - * pOverlap set to TRUE if overlapFunc ever returns TRUE. - * - * Notes: - * The idea behind this function is to view the two regions as sets. - * Together they cover a rectangle of area that this function divides - * into horizontal bands where points are covered only by one region - * or by both. For the first case, the nonOverlapFunc is called with - * each the band and the band's upper and lower extents. For the - * second, the overlapFunc is called to process the entire band. It - * is responsible for clipping the rectangles in the band, though - * this function provides the boundaries. - * At the end of each band, the new region is coalesced, if possible, - * to reduce the number of rectangles in the region. - * - *----------------------------------------------------------------------- - */ - -typedef Bool (*OverlapProcPtr)( - RegionPtr pReg, - BoxPtr r1, - BoxPtr r1End, - BoxPtr r2, - BoxPtr r2End, - short y1, - short y2, - Bool *pOverlap); - -static Bool -miRegionOp( - RegionPtr newReg, /* Place to store result */ - RegionPtr reg1, /* First region in operation */ - RegionPtr reg2, /* 2d region in operation */ - OverlapProcPtr overlapFunc, /* Function to call for over- - * lapping bands */ - Bool appendNon1, /* Append non-overlapping bands */ - /* in region 1 ? */ - Bool appendNon2, /* Append non-overlapping bands */ - /* in region 2 ? */ - Bool *pOverlap) -{ - BoxPtr r1; /* Pointer into first region */ - BoxPtr r2; /* Pointer into 2d region */ - BoxPtr r1End; /* End of 1st region */ - BoxPtr r2End; /* End of 2d region */ - short ybot; /* Bottom of intersection */ - short ytop; /* Top of intersection */ - RegDataPtr oldData; /* Old data for newReg */ - int prevBand; /* Index of start of - * previous band in newReg */ - int curBand; /* Index of start of current - * band in newReg */ - BoxPtr r1BandEnd; /* End of current band in r1 */ - BoxPtr r2BandEnd; /* End of current band in r2 */ - short top; /* Top of non-overlapping band */ - short bot; /* Bottom of non-overlapping band*/ - int r1y1; /* Temps for r1->y1 and r2->y1 */ - int r2y1; - int newSize; - int numRects; - - /* - * Break any region computed from a broken region - */ - if (REGION_NAR (reg1) || REGION_NAR(reg2)) - return miRegionBreak (newReg); - - /* - * Initialization: - * set r1, r2, r1End and r2End appropriately, save the rectangles - * of the destination region until the end in case it's one of - * the two source regions, then mark the "new" region empty, allocating - * another array of rectangles for it to use. - */ - - r1 = REGION_RECTS(reg1); - newSize = REGION_NUM_RECTS(reg1); - r1End = r1 + newSize; - numRects = REGION_NUM_RECTS(reg2); - r2 = REGION_RECTS(reg2); - r2End = r2 + numRects; - assert(r1 != r1End); - assert(r2 != r2End); - - oldData = NULL; - if (((newReg == reg1) && (newSize > 1)) || - ((newReg == reg2) && (numRects > 1))) - { - oldData = newReg->data; - newReg->data = &miEmptyData; - } - /* guess at new size */ - if (numRects > newSize) - newSize = numRects; - newSize <<= 1; - if (!newReg->data) - newReg->data = &miEmptyData; - else if (newReg->data->size) - newReg->data->numRects = 0; - if (newSize > newReg->data->size) - if (!miRectAlloc(newReg, newSize)) - return FALSE; - - /* - * Initialize ybot. - * In the upcoming loop, ybot and ytop serve different functions depending - * on whether the band being handled is an overlapping or non-overlapping - * band. - * In the case of a non-overlapping band (only one of the regions - * has points in the band), ybot is the bottom of the most recent - * intersection and thus clips the top of the rectangles in that band. - * ytop is the top of the next intersection between the two regions and - * serves to clip the bottom of the rectangles in the current band. - * For an overlapping band (where the two regions intersect), ytop clips - * the top of the rectangles of both regions and ybot clips the bottoms. - */ - - ybot = min(r1->y1, r2->y1); - - /* - * prevBand serves to mark the start of the previous band so rectangles - * can be coalesced into larger rectangles. qv. miCoalesce, above. - * In the beginning, there is no previous band, so prevBand == curBand - * (curBand is set later on, of course, but the first band will always - * start at index 0). prevBand and curBand must be indices because of - * the possible expansion, and resultant moving, of the new region's - * array of rectangles. - */ - prevBand = 0; - - do { - /* - * This algorithm proceeds one source-band (as opposed to a - * destination band, which is determined by where the two regions - * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the - * rectangle after the last one in the current band for their - * respective regions. - */ - assert(r1 != r1End); - assert(r2 != r2End); - - FindBand(r1, r1BandEnd, r1End, r1y1); - FindBand(r2, r2BandEnd, r2End, r2y1); - - /* - * First handle the band that doesn't intersect, if any. - * - * Note that attention is restricted to one band in the - * non-intersecting region at once, so if a region has n - * bands between the current position and the next place it overlaps - * the other, this entire loop will be passed through n times. - */ - if (r1y1 < r2y1) { - if (appendNon1) { - top = max(r1y1, ybot); - bot = min(r1->y2, r2y1); - if (top != bot) { - curBand = newReg->data->numRects; - miAppendNonO(newReg, r1, r1BandEnd, top, bot); - Coalesce(newReg, prevBand, curBand); - } - } - ytop = r2y1; - } else if (r2y1 < r1y1) { - if (appendNon2) { - top = max(r2y1, ybot); - bot = min(r2->y2, r1y1); - if (top != bot) { - curBand = newReg->data->numRects; - miAppendNonO(newReg, r2, r2BandEnd, top, bot); - Coalesce(newReg, prevBand, curBand); - } - } - ytop = r1y1; - } else { - ytop = r1y1; - } - - /* - * Now see if we've hit an intersecting band. The two bands only - * intersect if ybot > ytop - */ - ybot = min(r1->y2, r2->y2); - if (ybot > ytop) { - curBand = newReg->data->numRects; - (* overlapFunc)(newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot, - pOverlap); - Coalesce(newReg, prevBand, curBand); - } - - /* - * If we've finished with a band (y2 == ybot) we skip forward - * in the region to the next band. - */ - if (r1->y2 == ybot) r1 = r1BandEnd; - if (r2->y2 == ybot) r2 = r2BandEnd; - - } while (r1 != r1End && r2 != r2End); - - /* - * Deal with whichever region (if any) still has rectangles left. - * - * We only need to worry about banding and coalescing for the very first - * band left. After that, we can just group all remaining boxes, - * regardless of how many bands, into one final append to the list. - */ - - if ((r1 != r1End) && appendNon1) { - /* Do first nonOverlap1Func call, which may be able to coalesce */ - FindBand(r1, r1BandEnd, r1End, r1y1); - curBand = newReg->data->numRects; - miAppendNonO(newReg, r1, r1BandEnd, max(r1y1, ybot), r1->y2); - Coalesce(newReg, prevBand, curBand); - /* Just append the rest of the boxes */ - AppendRegions(newReg, r1BandEnd, r1End); - - } else if ((r2 != r2End) && appendNon2) { - /* Do first nonOverlap2Func call, which may be able to coalesce */ - FindBand(r2, r2BandEnd, r2End, r2y1); - curBand = newReg->data->numRects; - miAppendNonO(newReg, r2, r2BandEnd, max(r2y1, ybot), r2->y2); - Coalesce(newReg, prevBand, curBand); - /* Append rest of boxes */ - AppendRegions(newReg, r2BandEnd, r2End); - } - - if (oldData) - xfree(oldData); - - if (!(numRects = newReg->data->numRects)) - { - xfreeData(newReg); - newReg->data = &miEmptyData; - } - else if (numRects == 1) - { - newReg->extents = *REGION_BOXPTR(newReg); - xfreeData(newReg); - newReg->data = NULL; - } - else - { - DOWNSIZE(newReg, numRects); - } - - return TRUE; -} - -/*- - *----------------------------------------------------------------------- - * miSetExtents -- - * Reset the extents of a region to what they should be. Called by - * miSubtract and miIntersect as they can't figure it out along the - * way or do so easily, as miUnion can. - * - * Results: - * None. - * - * Side Effects: - * The region's 'extents' structure is overwritten. - * - *----------------------------------------------------------------------- - */ -static void -miSetExtents (RegionPtr pReg) -{ - BoxPtr pBox, pBoxEnd; - - if (!pReg->data) - return; - if (!pReg->data->size) - { - pReg->extents.x2 = pReg->extents.x1; - pReg->extents.y2 = pReg->extents.y1; - return; - } - - pBox = REGION_BOXPTR(pReg); - pBoxEnd = REGION_END(pReg); - - /* - * Since pBox is the first rectangle in the region, it must have the - * smallest y1 and since pBoxEnd is the last rectangle in the region, - * it must have the largest y2, because of banding. Initialize x1 and - * x2 from pBox and pBoxEnd, resp., as good things to initialize them - * to... - */ - pReg->extents.x1 = pBox->x1; - pReg->extents.y1 = pBox->y1; - pReg->extents.x2 = pBoxEnd->x2; - pReg->extents.y2 = pBoxEnd->y2; - - assert(pReg->extents.y1 < pReg->extents.y2); - while (pBox <= pBoxEnd) { - if (pBox->x1 < pReg->extents.x1) - pReg->extents.x1 = pBox->x1; - if (pBox->x2 > pReg->extents.x2) - pReg->extents.x2 = pBox->x2; - pBox++; - }; - - assert(pReg->extents.x1 < pReg->extents.x2); -} - -/*====================================================================== - * Region Intersection - *====================================================================*/ -/*- - *----------------------------------------------------------------------- - * miIntersectO -- - * Handle an overlapping band for miIntersect. - * - * Results: - * TRUE if successful. - * - * Side Effects: - * Rectangles may be added to the region. - * - *----------------------------------------------------------------------- - */ -/*ARGSUSED*/ -Bool -miIntersect( - RegionPtr newReg, /* destination Region */ - RegionPtr reg1, - RegionPtr reg2 /* source regions */ - ) -{ - return pixman_region_intersect (newReg, reg1, reg2); -} - -#define MERGERECT(r) \ -{ \ - if (r->x1 <= x2) { \ - /* Merge with current rectangle */ \ - if (r->x1 < x2) *pOverlap = TRUE; \ - if (x2 < r->x2) x2 = r->x2; \ - } else { \ - /* Add current rectangle, start new one */ \ - NEWRECT(pReg, pNextRect, x1, y1, x2, y2); \ - x1 = r->x1; \ - x2 = r->x2; \ - } \ - r++; \ -} - -/*====================================================================== - * Region Union - *====================================================================*/ - -/*- - *----------------------------------------------------------------------- - * miUnionO -- - * Handle an overlapping band for the union operation. Picks the - * left-most rectangle each time and merges it into the region. - * - * Results: - * TRUE if successful. - * - * Side Effects: - * pReg is overwritten. - * pOverlap is set to TRUE if any boxes overlap. - * - *----------------------------------------------------------------------- - */ -static Bool -miUnionO ( - RegionPtr pReg, - BoxPtr r1, - BoxPtr r1End, - BoxPtr r2, - BoxPtr r2End, - short y1, - short y2, - Bool *pOverlap) -{ - BoxPtr pNextRect; - int x1; /* left and right side of current union */ - int x2; - - assert (y1 < y2); - assert(r1 != r1End && r2 != r2End); - - pNextRect = REGION_TOP(pReg); - - /* Start off current rectangle */ - if (r1->x1 < r2->x1) - { - x1 = r1->x1; - x2 = r1->x2; - r1++; - } - else - { - x1 = r2->x1; - x2 = r2->x2; - r2++; - } - while (r1 != r1End && r2 != r2End) - { - if (r1->x1 < r2->x1) MERGERECT(r1) else MERGERECT(r2); - } - - /* Finish off whoever (if any) is left */ - if (r1 != r1End) - { - do - { - MERGERECT(r1); - } while (r1 != r1End); - } - else if (r2 != r2End) - { - do - { - MERGERECT(r2); - } while (r2 != r2End); - } - - /* Add current rectangle */ - NEWRECT(pReg, pNextRect, x1, y1, x2, y2); - - return TRUE; -} - -Bool -miUnion( - RegionPtr newReg, /* destination Region */ - RegionPtr reg1, - RegionPtr reg2 /* source regions */ - ) -{ - return pixman_region_union (newReg, reg1, reg2); -} - -/*====================================================================== - * Batch Rectangle Union - *====================================================================*/ - -/*- - *----------------------------------------------------------------------- - * miRegionAppend -- - * - * "Append" the rgn rectangles onto the end of dstrgn, maintaining - * knowledge of YX-banding when it's easy. Otherwise, dstrgn just - * becomes a non-y-x-banded random collection of rectangles, and not - * yet a true region. After a sequence of appends, the caller must - * call miRegionValidate to ensure that a valid region is constructed. - * - * Results: - * TRUE if successful. - * - * Side Effects: - * dstrgn is modified if rgn has rectangles. - * - */ -Bool -miRegionAppend(RegionPtr dstrgn, RegionPtr rgn) -{ - int numRects, dnumRects, size; - BoxPtr new, old; - Bool prepend; - - if (REGION_NAR(rgn)) - return miRegionBreak (dstrgn); - - if (!rgn->data && (dstrgn->data == &miEmptyData)) - { - dstrgn->extents = rgn->extents; - dstrgn->data = NULL; - return TRUE; - } - - numRects = REGION_NUM_RECTS(rgn); - if (!numRects) - return TRUE; - prepend = FALSE; - size = numRects; - dnumRects = REGION_NUM_RECTS(dstrgn); - if (!dnumRects && (size < 200)) - size = 200; /* XXX pick numbers out of a hat */ - RECTALLOC(dstrgn, size); - old = REGION_RECTS(rgn); - if (!dnumRects) - dstrgn->extents = rgn->extents; - else if (dstrgn->extents.x2 > dstrgn->extents.x1) - { - BoxPtr first, last; - - first = old; - last = REGION_BOXPTR(dstrgn) + (dnumRects - 1); - if ((first->y1 > last->y2) || - ((first->y1 == last->y1) && (first->y2 == last->y2) && - (first->x1 > last->x2))) - { - if (rgn->extents.x1 < dstrgn->extents.x1) - dstrgn->extents.x1 = rgn->extents.x1; - if (rgn->extents.x2 > dstrgn->extents.x2) - dstrgn->extents.x2 = rgn->extents.x2; - dstrgn->extents.y2 = rgn->extents.y2; - } - else - { - first = REGION_BOXPTR(dstrgn); - last = old + (numRects - 1); - if ((first->y1 > last->y2) || - ((first->y1 == last->y1) && (first->y2 == last->y2) && - (first->x1 > last->x2))) - { - prepend = TRUE; - if (rgn->extents.x1 < dstrgn->extents.x1) - dstrgn->extents.x1 = rgn->extents.x1; - if (rgn->extents.x2 > dstrgn->extents.x2) - dstrgn->extents.x2 = rgn->extents.x2; - dstrgn->extents.y1 = rgn->extents.y1; - } - else - dstrgn->extents.x2 = dstrgn->extents.x1; - } - } - if (prepend) - { - new = REGION_BOX(dstrgn, numRects); - if (dnumRects == 1) - *new = *REGION_BOXPTR(dstrgn); - else - memmove((char *)new,(char *)REGION_BOXPTR(dstrgn), - dnumRects * sizeof(BoxRec)); - new = REGION_BOXPTR(dstrgn); - } - else - new = REGION_BOXPTR(dstrgn) + dnumRects; - if (numRects == 1) - *new = *old; - else - memmove((char *)new, (char *)old, numRects * sizeof(BoxRec)); - dstrgn->data->numRects += numRects; - return TRUE; -} - - -#define ExchangeRects(a, b) \ -{ \ - BoxRec t; \ - t = rects[a]; \ - rects[a] = rects[b]; \ - rects[b] = t; \ -} - -static void -QuickSortRects( - BoxRec rects[], - int numRects) -{ - int y1; - int x1; - int i, j; - BoxPtr r; - - /* Always called with numRects > 1 */ - - do - { - if (numRects == 2) - { - if (rects[0].y1 > rects[1].y1 || - (rects[0].y1 == rects[1].y1 && rects[0].x1 > rects[1].x1)) - ExchangeRects(0, 1); - return; - } - - /* Choose partition element, stick in location 0 */ - ExchangeRects(0, numRects >> 1); - y1 = rects[0].y1; - x1 = rects[0].x1; - - /* Partition array */ - i = 0; - j = numRects; - do - { - r = &(rects[i]); - do - { - r++; - i++; - } while (i != numRects && - (r->y1 < y1 || (r->y1 == y1 && r->x1 < x1))); - r = &(rects[j]); - do - { - r--; - j--; - } while (y1 < r->y1 || (y1 == r->y1 && x1 < r->x1)); - if (i < j) - ExchangeRects(i, j); - } while (i < j); - - /* Move partition element back to middle */ - ExchangeRects(0, j); - - /* Recurse */ - if (numRects-j-1 > 1) - QuickSortRects(&rects[j+1], numRects-j-1); - numRects = j; - } while (numRects > 1); -} - -/*- - *----------------------------------------------------------------------- - * miRegionValidate -- - * - * Take a ``region'' which is a non-y-x-banded random collection of - * rectangles, and compute a nice region which is the union of all the - * rectangles. - * - * Results: - * TRUE if successful. - * - * Side Effects: - * The passed-in ``region'' may be modified. - * pOverlap set to TRUE if any retangles overlapped, else FALSE; - * - * Strategy: - * Step 1. Sort the rectangles into ascending order with primary key y1 - * and secondary key x1. - * - * Step 2. Split the rectangles into the minimum number of proper y-x - * banded regions. This may require horizontally merging - * rectangles, and vertically coalescing bands. With any luck, - * this step in an identity tranformation (ala the Box widget), - * or a coalescing into 1 box (ala Menus). - * - * Step 3. Merge the separate regions down to a single region by calling - * miUnion. Maximize the work each miUnion call does by using - * a binary merge. - * - *----------------------------------------------------------------------- - */ - -Bool -miRegionValidate(RegionPtr badreg, Bool *pOverlap) -{ - /* Descriptor for regions under construction in Step 2. */ - typedef struct { - RegionRec reg; - int prevBand; - int curBand; - } RegionInfo; - - int numRects; /* Original numRects for badreg */ - RegionInfo *ri; /* Array of current regions */ - int numRI; /* Number of entries used in ri */ - int sizeRI; /* Number of entries available in ri */ - int i; /* Index into rects */ - int j; /* Index into ri */ - RegionInfo *rit; /* &ri[j] */ - RegionPtr reg; /* ri[j].reg */ - BoxPtr box; /* Current box in rects */ - BoxPtr riBox; /* Last box in ri[j].reg */ - RegionPtr hreg; /* ri[j_half].reg */ - Bool ret = TRUE; - - *pOverlap = FALSE; - if (!badreg->data) - { - good(badreg); - return TRUE; - } - numRects = badreg->data->numRects; - if (!numRects) - { - if (REGION_NAR(badreg)) - return FALSE; - good(badreg); - return TRUE; - } - if (badreg->extents.x1 < badreg->extents.x2) - { - if ((numRects) == 1) - { - xfreeData(badreg); - badreg->data = (RegDataPtr) NULL; - } - else - { - DOWNSIZE(badreg, numRects); - } - good(badreg); - return TRUE; - } - - /* Step 1: Sort the rects array into ascending (y1, x1) order */ - QuickSortRects(REGION_BOXPTR(badreg), numRects); - - /* Step 2: Scatter the sorted array into the minimum number of regions */ - - /* Set up the first region to be the first rectangle in badreg */ - /* Note that step 2 code will never overflow the ri[0].reg rects array */ - ri = (RegionInfo *) xalloc(4 * sizeof(RegionInfo)); - if (!ri) - return miRegionBreak (badreg); - sizeRI = 4; - numRI = 1; - ri[0].prevBand = 0; - ri[0].curBand = 0; - ri[0].reg = *badreg; - box = REGION_BOXPTR(&ri[0].reg); - ri[0].reg.extents = *box; - ri[0].reg.data->numRects = 1; - - /* Now scatter rectangles into the minimum set of valid regions. If the - next rectangle to be added to a region would force an existing rectangle - in the region to be split up in order to maintain y-x banding, just - forget it. Try the next region. If it doesn't fit cleanly into any - region, make a new one. */ - - for (i = numRects; --i > 0;) - { - box++; - /* Look for a region to append box to */ - for (j = numRI, rit = ri; --j >= 0; rit++) - { - reg = &rit->reg; - riBox = REGION_END(reg); - - if (box->y1 == riBox->y1 && box->y2 == riBox->y2) - { - /* box is in same band as riBox. Merge or append it */ - if (box->x1 <= riBox->x2) - { - /* Merge it with riBox */ - if (box->x1 < riBox->x2) *pOverlap = TRUE; - if (box->x2 > riBox->x2) riBox->x2 = box->x2; - } - else - { - RECTALLOC_BAIL(reg, 1, bail); - *REGION_TOP(reg) = *box; - reg->data->numRects++; - } - goto NextRect; /* So sue me */ - } - else if (box->y1 >= riBox->y2) - { - /* Put box into new band */ - if (reg->extents.x2 < riBox->x2) reg->extents.x2 = riBox->x2; - if (reg->extents.x1 > box->x1) reg->extents.x1 = box->x1; - Coalesce(reg, rit->prevBand, rit->curBand); - rit->curBand = reg->data->numRects; - RECTALLOC_BAIL(reg, 1, bail); - *REGION_TOP(reg) = *box; - reg->data->numRects++; - goto NextRect; - } - /* Well, this region was inappropriate. Try the next one. */ - } /* for j */ - - /* Uh-oh. No regions were appropriate. Create a new one. */ - if (sizeRI == numRI) - { - /* Oops, allocate space for new region information */ - sizeRI <<= 1; - rit = (RegionInfo *) xrealloc(ri, sizeRI * sizeof(RegionInfo)); - if (!rit) - goto bail; - ri = rit; - rit = &ri[numRI]; - } - numRI++; - rit->prevBand = 0; - rit->curBand = 0; - rit->reg.extents = *box; - rit->reg.data = NULL; - if (!miRectAlloc(&rit->reg, (i+numRI) / numRI)) /* MUST force allocation */ - goto bail; -NextRect: ; - } /* for i */ - - /* Make a final pass over each region in order to Coalesce and set - extents.x2 and extents.y2 */ - - for (j = numRI, rit = ri; --j >= 0; rit++) - { - reg = &rit->reg; - riBox = REGION_END(reg); - reg->extents.y2 = riBox->y2; - if (reg->extents.x2 < riBox->x2) reg->extents.x2 = riBox->x2; - Coalesce(reg, rit->prevBand, rit->curBand); - if (reg->data->numRects == 1) /* keep unions happy below */ - { - xfreeData(reg); - reg->data = NULL; - } - } - - /* Step 3: Union all regions into a single region */ - while (numRI > 1) - { - int half = numRI/2; - for (j = numRI & 1; j < (half + (numRI & 1)); j++) - { - reg = &ri[j].reg; - hreg = &ri[j+half].reg; - if (!miRegionOp(reg, reg, hreg, miUnionO, TRUE, TRUE, pOverlap)) - ret = FALSE; - if (hreg->extents.x1 < reg->extents.x1) - reg->extents.x1 = hreg->extents.x1; - if (hreg->extents.y1 < reg->extents.y1) - reg->extents.y1 = hreg->extents.y1; - if (hreg->extents.x2 > reg->extents.x2) - reg->extents.x2 = hreg->extents.x2; - if (hreg->extents.y2 > reg->extents.y2) - reg->extents.y2 = hreg->extents.y2; - xfreeData(hreg); - } - numRI -= half; - } - *badreg = ri[0].reg; - xfree(ri); - good(badreg); - return ret; -bail: - for (i = 0; i < numRI; i++) - xfreeData(&ri[i].reg); - xfree (ri); - return miRegionBreak (badreg); -} - -RegionPtr -miRectsToRegion(int nrects, xRectangle *prect, int ctype) -{ - - RegionPtr pRgn; - RegDataPtr pData; - BoxPtr pBox; - int i; - int x1, y1, x2, y2; - - pRgn = miRegionCreate(NullBox, 0); - if (REGION_NAR (pRgn)) - return pRgn; - if (!nrects) - return pRgn; - if (nrects == 1) - { - x1 = prect->x; - y1 = prect->y; - if ((x2 = x1 + (int) prect->width) > MAXSHORT) - x2 = MAXSHORT; - if ((y2 = y1 + (int) prect->height) > MAXSHORT) - y2 = MAXSHORT; - if (x1 != x2 && y1 != y2) - { - pRgn->extents.x1 = x1; - pRgn->extents.y1 = y1; - pRgn->extents.x2 = x2; - pRgn->extents.y2 = y2; - pRgn->data = NULL; - } - return pRgn; - } - pData = xallocData(nrects); - if (!pData) - { - miRegionBreak (pRgn); - return pRgn; - } - pBox = (BoxPtr) (pData + 1); - for (i = nrects; --i >= 0; prect++) - { - x1 = prect->x; - y1 = prect->y; - if ((x2 = x1 + (int) prect->width) > MAXSHORT) - x2 = MAXSHORT; - if ((y2 = y1 + (int) prect->height) > MAXSHORT) - y2 = MAXSHORT; - if (x1 != x2 && y1 != y2) - { - pBox->x1 = x1; - pBox->y1 = y1; - pBox->x2 = x2; - pBox->y2 = y2; - pBox++; - } - } - if (pBox != (BoxPtr) (pData + 1)) - { - pData->size = nrects; - pData->numRects = pBox - (BoxPtr) (pData + 1); - pRgn->data = pData; - if (ctype != CT_YXBANDED) - { - Bool overlap; /* result ignored */ - pRgn->extents.x1 = pRgn->extents.x2 = 0; - miRegionValidate(pRgn, &overlap); - } - else - miSetExtents(pRgn); - good(pRgn); - } - else - { - xfree (pData); - } - return pRgn; -} - -/*====================================================================== - * Region Subtraction - *====================================================================*/ - - -/*- - *----------------------------------------------------------------------- - * miSubtractO -- - * Overlapping band subtraction. x1 is the left-most point not yet - * checked. - * - * Results: - * TRUE if successful. - * - * Side Effects: - * pReg may have rectangles added to it. - * - *----------------------------------------------------------------------- - */ -/*ARGSUSED*/ - -/*- - *----------------------------------------------------------------------- - * miSubtract -- - * Subtract regS from regM and leave the result in regD. - * S stands for subtrahend, M for minuend and D for difference. - * - * Results: - * TRUE if successful. - * - * Side Effects: - * regD is overwritten. - * - *----------------------------------------------------------------------- - */ -Bool -miSubtract(RegionPtr regD, RegionPtr regM, RegionPtr regS) -{ - return pixman_region_subtract (regD, regM, regS); -} - -/*====================================================================== - * Region Inversion - *====================================================================*/ - -/*- - *----------------------------------------------------------------------- - * miInverse -- - * Take a region and a box and return a region that is everything - * in the box but not in the region. The careful reader will note - * that this is the same as subtracting the region from the box... - * - * Results: - * TRUE. - * - * Side Effects: - * newReg is overwritten. - * - *----------------------------------------------------------------------- - */ -Bool -miInverse( - RegionPtr newReg, /* Destination region */ - RegionPtr reg1, /* Region to invert */ - BoxPtr invRect /* Bounding box for inversion */ - ) -{ - return pixman_region_inverse (newReg, reg1, invRect); -} -int -miRectIn(RegionPtr region, BoxPtr prect) -{ - return pixman_region_contains_rectangle (region, prect); -} - -/* TranslateRegion(pReg, x, y) - translates in place -*/ - -void -miTranslateRegion(RegionPtr pReg, int x, int y) -{ - pixman_region_translate (pReg, x, y); -} - -void -miRegionReset(RegionPtr pReg, BoxPtr pBox) -{ - pixman_region_reset (pReg, pBox); -} - -Bool -miPointInRegion( - RegionPtr pReg, - int x, - int y, - BoxPtr box /* "return" value */ - ) -{ - return pixman_region_contains_point (pReg, x, y, box); -} - -Bool -miRegionNotEmpty(RegionPtr pReg) -{ - return pixman_region_not_empty (pReg); -} - -Bool -miRegionBroken(RegionPtr pReg) -{ - good(pReg); - return (REGION_NAR(pReg)); -} - -void -miRegionEmpty(RegionPtr pReg) -{ - good(pReg); - xfreeData(pReg); - pReg->extents.x2 = pReg->extents.x1; - pReg->extents.y2 = pReg->extents.y1; - pReg->data = &miEmptyData; -} - -BoxPtr -miRegionExtents(RegionPtr pReg) -{ - good(pReg); - return(&pReg->extents); -} - -#define ExchangeSpans(a, b) \ -{ \ - DDXPointRec tpt; \ - int tw; \ - \ - tpt = spans[a]; spans[a] = spans[b]; spans[b] = tpt; \ - tw = widths[a]; widths[a] = widths[b]; widths[b] = tw; \ -} - -/* ||| I should apply the merge sort code to rectangle sorting above, and see - if mapping time can be improved. But right now I've been at work 12 hours, - so forget it. -*/ - -static void QuickSortSpans( - DDXPointRec spans[], - int widths[], - int numSpans) -{ - int y; - int i, j, m; - DDXPointPtr r; - - /* Always called with numSpans > 1 */ - /* Sorts only by y, doesn't bother to sort by x */ - - do - { - if (numSpans < 9) - { - /* Do insertion sort */ - int yprev; - - yprev = spans[0].y; - i = 1; - do - { /* while i != numSpans */ - y = spans[i].y; - if (yprev > y) - { - /* spans[i] is out of order. Move into proper location. */ - DDXPointRec tpt; - int tw, k; - - for (j = 0; y >= spans[j].y; j++) {} - tpt = spans[i]; - tw = widths[i]; - for (k = i; k != j; k--) - { - spans[k] = spans[k-1]; - widths[k] = widths[k-1]; - } - spans[j] = tpt; - widths[j] = tw; - y = spans[i].y; - } /* if out of order */ - yprev = y; - i++; - } while (i != numSpans); - return; - } - - /* Choose partition element, stick in location 0 */ - m = numSpans / 2; - if (spans[m].y > spans[0].y) ExchangeSpans(m, 0); - if (spans[m].y > spans[numSpans-1].y) ExchangeSpans(m, numSpans-1); - if (spans[m].y > spans[0].y) ExchangeSpans(m, 0); - y = spans[0].y; - - /* Partition array */ - i = 0; - j = numSpans; - do - { - r = &(spans[i]); - do - { - r++; - i++; - } while (i != numSpans && r->y < y); - r = &(spans[j]); - do - { - r--; - j--; - } while (y < r->y); - if (i < j) - ExchangeSpans(i, j); - } while (i < j); - - /* Move partition element back to middle */ - ExchangeSpans(0, j); - - /* Recurse */ - if (numSpans-j-1 > 1) - QuickSortSpans(&spans[j+1], &widths[j+1], numSpans-j-1); - numSpans = j; - } while (numSpans > 1); -} - -#define NextBand() \ -{ \ - clipy1 = pboxBandStart->y1; \ - clipy2 = pboxBandStart->y2; \ - pboxBandEnd = pboxBandStart + 1; \ - while (pboxBandEnd != pboxLast && pboxBandEnd->y1 == clipy1) { \ - pboxBandEnd++; \ - } \ - for (; ppt != pptLast && ppt->y < clipy1; ppt++, pwidth++) {} \ -} - -/* - Clip a list of scanlines to a region. The caller has allocated the - space. FSorted is non-zero if the scanline origins are in ascending - order. - returns the number of new, clipped scanlines. -*/ - -int -miClipSpans( - RegionPtr prgnDst, - DDXPointPtr ppt, - int *pwidth, - int nspans, - DDXPointPtr pptNew, - int *pwidthNew, - int fSorted) -{ - DDXPointPtr pptLast; - int *pwidthNewStart; /* the vengeance of Xerox! */ - int y, x1, x2; - int numRects; - - good(prgnDst); - pptLast = ppt + nspans; - pwidthNewStart = pwidthNew; - - if (!prgnDst->data) - { - /* Do special fast code with clip boundaries in registers(?) */ - /* It doesn't pay much to make use of fSorted in this case, - so we lump everything together. */ - - int clipx1, clipx2, clipy1, clipy2; - - clipx1 = prgnDst->extents.x1; - clipy1 = prgnDst->extents.y1; - clipx2 = prgnDst->extents.x2; - clipy2 = prgnDst->extents.y2; - - for (; ppt != pptLast; ppt++, pwidth++) - { - y = ppt->y; - x1 = ppt->x; - if (clipy1 <= y && y < clipy2) - { - x2 = x1 + *pwidth; - if (x1 < clipx1) x1 = clipx1; - if (x2 > clipx2) x2 = clipx2; - if (x1 < x2) - { - /* part of span in clip rectangle */ - pptNew->x = x1; - pptNew->y = y; - *pwidthNew = x2 - x1; - pptNew++; - pwidthNew++; - } - } - } /* end for */ - - } - else if ((numRects = prgnDst->data->numRects)) - { - /* Have to clip against many boxes */ - BoxPtr pboxBandStart, pboxBandEnd; - BoxPtr pbox; - BoxPtr pboxLast; - int clipy1, clipy2; - - /* In this case, taking advantage of sorted spans gains more than - the sorting costs. */ - if ((! fSorted) && (nspans > 1)) - QuickSortSpans(ppt, pwidth, nspans); - - pboxBandStart = REGION_BOXPTR(prgnDst); - pboxLast = pboxBandStart + numRects; - - NextBand(); - - for (; ppt != pptLast; ) - { - y = ppt->y; - if (y < clipy2) - { - /* span is in the current band */ - pbox = pboxBandStart; - x1 = ppt->x; - x2 = x1 + *pwidth; - do - { /* For each box in band */ - int newx1, newx2; - - newx1 = x1; - newx2 = x2; - if (newx1 < pbox->x1) newx1 = pbox->x1; - if (newx2 > pbox->x2) newx2 = pbox->x2; - if (newx1 < newx2) - { - /* Part of span in clip rectangle */ - pptNew->x = newx1; - pptNew->y = y; - *pwidthNew = newx2 - newx1; - pptNew++; - pwidthNew++; - } - pbox++; - } while (pbox != pboxBandEnd); - ppt++; - pwidth++; - } - else - { - /* Move to next band, adjust ppt as needed */ - pboxBandStart = pboxBandEnd; - if (pboxBandStart == pboxLast) - break; /* We're completely done */ - NextBand(); - } - } - } - return (pwidthNew - pwidthNewStart); -} +/*********************************************************** + +Copyright 1987, 1988, 1989, 1998 The Open Group + +Permission to use, copy, modify, distribute, and sell this software and its +documentation for any purpose is hereby granted without fee, provided that +the above copyright notice appear in all copies and that both that +copyright notice and this permission notice appear in supporting +documentation. + +The above copyright notice and this permission notice shall be included in +all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN +AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN +CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + +Except as contained in this notice, the name of The Open Group shall not be +used in advertising or otherwise to promote the sale, use or other dealings +in this Software without prior written authorization from The Open Group. + + +Copyright 1987, 1988, 1989 by +Digital Equipment Corporation, Maynard, Massachusetts. + + All Rights Reserved + +Permission to use, copy, modify, and distribute this software and its +documentation for any purpose and without fee is hereby granted, +provided that the above copyright notice appear in all copies and that +both that copyright notice and this permission notice appear in +supporting documentation, and that the name of Digital not be +used in advertising or publicity pertaining to distribution of the +software without specific, written prior permission. + +DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING +ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL +DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR +ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, +WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, +ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS +SOFTWARE. + +******************************************************************/ + +/* The panoramix components contained the following notice */ +/***************************************************************** + +Copyright (c) 1991, 1997 Digital Equipment Corporation, Maynard, Massachusetts. + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software. + +The above copyright notice and this permission notice shall be included in +all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL +DIGITAL EQUIPMENT CORPORATION BE LIABLE FOR ANY CLAIM, DAMAGES, INCLUDING, +BUT NOT LIMITED TO CONSEQUENTIAL OR INCIDENTAL DAMAGES, OR OTHER LIABILITY, +WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR +IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + +Except as contained in this notice, the name of Digital Equipment Corporation +shall not be used in advertising or otherwise to promote the sale, use or other +dealings in this Software without prior written authorization from Digital +Equipment Corporation. + +******************************************************************/ + +#ifdef HAVE_DIX_CONFIG_H +#include +#endif + +#include "regionstr.h" +#include +#include +#include "gc.h" +#include "mi.h" +#include "mispans.h" +#include + +#undef assert +#ifdef REGION_DEBUG +#define assert(expr) { \ + CARD32 *foo = NULL; \ + if (!(expr)) { \ + ErrorF("Assertion failed file %s, line %d: %s\n", \ + __FILE__, __LINE__, #expr); \ + *foo = 0xdeadbeef; /* to get a backtrace */ \ + } \ + } +#else +#define assert(expr) +#endif + +#define good(reg) assert(miValidRegion(reg)) + +/* + * The functions in this file implement the Region abstraction used extensively + * throughout the X11 sample server. A Region is simply a set of disjoint + * (non-overlapping) rectangles, plus an "extent" rectangle which is the + * smallest single rectangle that contains all the non-overlapping rectangles. + * + * A Region is implemented as a "y-x-banded" array of rectangles. This array + * imposes two degrees of order. First, all rectangles are sorted by top side + * y coordinate first (y1), and then by left side x coordinate (x1). + * + * Furthermore, the rectangles are grouped into "bands". Each rectangle in a + * band has the same top y coordinate (y1), and each has the same bottom y + * coordinate (y2). Thus all rectangles in a band differ only in their left + * and right side (x1 and x2). Bands are implicit in the array of rectangles: + * there is no separate list of band start pointers. + * + * The y-x band representation does not minimize rectangles. In particular, + * if a rectangle vertically crosses a band (the rectangle has scanlines in + * the y1 to y2 area spanned by the band), then the rectangle may be broken + * down into two or more smaller rectangles stacked one atop the other. + * + * ----------- ----------- + * | | | | band 0 + * | | -------- ----------- -------- + * | | | | in y-x banded | | | | band 1 + * | | | | form is | | | | + * ----------- | | ----------- -------- + * | | | | band 2 + * -------- -------- + * + * An added constraint on the rectangles is that they must cover as much + * horizontal area as possible: no two rectangles within a band are allowed + * to touch. + * + * Whenever possible, bands will be merged together to cover a greater vertical + * distance (and thus reduce the number of rectangles). Two bands can be merged + * only if the bottom of one touches the top of the other and they have + * rectangles in the same places (of the same width, of course). + * + * Adam de Boor wrote most of the original region code. Joel McCormack + * substantially modified or rewrote most of the core arithmetic routines, + * and added miRegionValidate in order to support several speed improvements + * to miValidateTree. Bob Scheifler changed the representation to be more + * compact when empty or a single rectangle, and did a bunch of gratuitous + * reformatting. + */ + +/* true iff two Boxes overlap */ +#define EXTENTCHECK(r1,r2) \ + (!( ((r1)->x2 <= (r2)->x1) || \ + ((r1)->x1 >= (r2)->x2) || \ + ((r1)->y2 <= (r2)->y1) || \ + ((r1)->y1 >= (r2)->y2) ) ) + +/* true iff (x,y) is in Box */ +#define INBOX(r,x,y) \ + ( ((r)->x2 > x) && \ + ((r)->x1 <= x) && \ + ((r)->y2 > y) && \ + ((r)->y1 <= y) ) + +/* true iff Box r1 contains Box r2 */ +#define SUBSUMES(r1,r2) \ + ( ((r1)->x1 <= (r2)->x1) && \ + ((r1)->x2 >= (r2)->x2) && \ + ((r1)->y1 <= (r2)->y1) && \ + ((r1)->y2 >= (r2)->y2) ) + +#define xallocData(n) malloc(REGION_SZOF(n)) +#define xfreeData(reg) if ((reg)->data && (reg)->data->size) free((reg)->data) + +#define RECTALLOC_BAIL(pReg,n,bail) \ +if (!(pReg)->data || (((pReg)->data->numRects + (n)) > (pReg)->data->size)) \ + if (!miRectAlloc(pReg, n)) { goto bail; } + +#define RECTALLOC(pReg,n) \ +if (!(pReg)->data || (((pReg)->data->numRects + (n)) > (pReg)->data->size)) \ + if (!miRectAlloc(pReg, n)) { return FALSE; } + +#define ADDRECT(pNextRect,nx1,ny1,nx2,ny2) \ +{ \ + pNextRect->x1 = nx1; \ + pNextRect->y1 = ny1; \ + pNextRect->x2 = nx2; \ + pNextRect->y2 = ny2; \ + pNextRect++; \ +} + +#define NEWRECT(pReg,pNextRect,nx1,ny1,nx2,ny2) \ +{ \ + if (!(pReg)->data || ((pReg)->data->numRects == (pReg)->data->size))\ + { \ + if (!miRectAlloc(pReg, 1)) \ + return FALSE; \ + pNextRect = REGION_TOP(pReg); \ + } \ + ADDRECT(pNextRect,nx1,ny1,nx2,ny2); \ + pReg->data->numRects++; \ + assert(pReg->data->numRects<=pReg->data->size); \ +} + + +#define DOWNSIZE(reg,numRects) \ +if (((numRects) < ((reg)->data->size >> 1)) && ((reg)->data->size > 50)) \ +{ \ + RegDataPtr NewData; \ + NewData = (RegDataPtr)realloc((reg)->data, REGION_SZOF(numRects)); \ + if (NewData) \ + { \ + NewData->size = (numRects); \ + (reg)->data = NewData; \ + } \ +} + + +BoxRec miEmptyBox = {0, 0, 0, 0}; +RegDataRec miEmptyData = {0, 0}; + +RegDataRec miBrokenData = {0, 0}; +static RegionRec miBrokenRegion = { { 0, 0, 0, 0 }, &miBrokenData }; + +void +InitRegions (void) +{ + pixman_region_set_static_pointers (&miEmptyBox, &miEmptyData, &miBrokenData); +} + +/***************************************************************** + * RegionCreate(rect, size) + * This routine does a simple malloc to make a structure of + * REGION of "size" number of rectangles. + *****************************************************************/ + +RegionPtr +miRegionCreate(BoxPtr rect, int size) +{ + RegionPtr pReg; + + pReg = (RegionPtr)malloc(sizeof(RegionRec)); + if (!pReg) + return &miBrokenRegion; + + miRegionInit (pReg, rect, size); + + return(pReg); +} + +void +miRegionDestroy(RegionPtr pReg) +{ + pixman_region_fini (pReg); + if (pReg != &miBrokenRegion) + free(pReg); +} + +void +miPrintRegion(RegionPtr rgn) +{ + int num, size; + int i; + BoxPtr rects; + + num = REGION_NUM_RECTS(rgn); + size = REGION_SIZE(rgn); + rects = REGION_RECTS(rgn); + ErrorF("[mi] num: %d size: %d\n", num, size); + ErrorF("[mi] extents: %d %d %d %d\n", + rgn->extents.x1, rgn->extents.y1, rgn->extents.x2, rgn->extents.y2); + for (i = 0; i < num; i++) + ErrorF("[mi] %d %d %d %d \n", + rects[i].x1, rects[i].y1, rects[i].x2, rects[i].y2); + ErrorF("[mi] \n"); +} + +Bool +miRegionEqual(RegionPtr reg1, RegionPtr reg2) +{ + return pixman_region_equal (reg1, reg2); +} + +#ifdef DEBUG +Bool +miValidRegion(RegionPtr reg) +{ + int i, numRects; + + if ((reg->extents.x1 > reg->extents.x2) || + (reg->extents.y1 > reg->extents.y2)) + return FALSE; + numRects = REGION_NUM_RECTS(reg); + if (!numRects) + return ((reg->extents.x1 == reg->extents.x2) && + (reg->extents.y1 == reg->extents.y2) && + (reg->data->size || (reg->data == &miEmptyData))); + else if (numRects == 1) + return (!reg->data); + else + { + BoxPtr pboxP, pboxN; + BoxRec box; + + pboxP = REGION_RECTS(reg); + box = *pboxP; + box.y2 = pboxP[numRects-1].y2; + pboxN = pboxP + 1; + for (i = numRects; --i > 0; pboxP++, pboxN++) + { + if ((pboxN->x1 >= pboxN->x2) || + (pboxN->y1 >= pboxN->y2)) + return FALSE; + if (pboxN->x1 < box.x1) + box.x1 = pboxN->x1; + if (pboxN->x2 > box.x2) + box.x2 = pboxN->x2; + if ((pboxN->y1 < pboxP->y1) || + ((pboxN->y1 == pboxP->y1) && + ((pboxN->x1 < pboxP->x2) || (pboxN->y2 != pboxP->y2)))) + return FALSE; + } + return ((box.x1 == reg->extents.x1) && + (box.x2 == reg->extents.x2) && + (box.y1 == reg->extents.y1) && + (box.y2 == reg->extents.y2)); + } +} +#endif /* DEBUG */ + +/***************************************************************** + * RegionInit(pReg, rect, size) + * Outer region rect is statically allocated. + *****************************************************************/ + +void +miRegionInit(RegionPtr pReg, BoxPtr rect, int size) +{ + if (rect) + pixman_region_init_with_extents (pReg, rect); + else + pixman_region_init (pReg); +} + +void +miRegionUninit(RegionPtr pReg) +{ + pixman_region_fini (pReg); +} + +Bool +miRegionBreak (RegionPtr pReg) +{ + xfreeData (pReg); + pReg->extents = miEmptyBox; + pReg->data = &miBrokenData; + return FALSE; +} + +Bool +miRectAlloc(RegionPtr pRgn, int n) +{ + RegDataPtr data; + + if (!pRgn->data) + { + n++; + pRgn->data = xallocData(n); + if (!pRgn->data) + return miRegionBreak (pRgn); + pRgn->data->numRects = 1; + *REGION_BOXPTR(pRgn) = pRgn->extents; + } + else if (!pRgn->data->size) + { + pRgn->data = xallocData(n); + if (!pRgn->data) + return miRegionBreak (pRgn); + pRgn->data->numRects = 0; + } + else + { + if (n == 1) + { + n = pRgn->data->numRects; + if (n > 500) /* XXX pick numbers out of a hat */ + n = 250; + } + n += pRgn->data->numRects; + data = (RegDataPtr)realloc(pRgn->data, REGION_SZOF(n)); + if (!data) + return miRegionBreak (pRgn); + pRgn->data = data; + } + pRgn->data->size = n; + return TRUE; +} + +Bool +miRegionCopy(RegionPtr dst, RegionPtr src) +{ + return pixman_region_copy (dst, src); +} + +/*====================================================================== + * Generic Region Operator + *====================================================================*/ + +/*- + *----------------------------------------------------------------------- + * miCoalesce -- + * Attempt to merge the boxes in the current band with those in the + * previous one. We are guaranteed that the current band extends to + * the end of the rects array. Used only by miRegionOp. + * + * Results: + * The new index for the previous band. + * + * Side Effects: + * If coalescing takes place: + * - rectangles in the previous band will have their y2 fields + * altered. + * - pReg->data->numRects will be decreased. + * + *----------------------------------------------------------------------- + */ +_X_INLINE static int +miCoalesce ( + RegionPtr pReg, /* Region to coalesce */ + int prevStart, /* Index of start of previous band */ + int curStart) /* Index of start of current band */ +{ + BoxPtr pPrevBox; /* Current box in previous band */ + BoxPtr pCurBox; /* Current box in current band */ + int numRects; /* Number rectangles in both bands */ + int y2; /* Bottom of current band */ + /* + * Figure out how many rectangles are in the band. + */ + numRects = curStart - prevStart; + assert(numRects == pReg->data->numRects - curStart); + + if (!numRects) return curStart; + + /* + * The bands may only be coalesced if the bottom of the previous + * matches the top scanline of the current. + */ + pPrevBox = REGION_BOX(pReg, prevStart); + pCurBox = REGION_BOX(pReg, curStart); + if (pPrevBox->y2 != pCurBox->y1) return curStart; + + /* + * Make sure the bands have boxes in the same places. This + * assumes that boxes have been added in such a way that they + * cover the most area possible. I.e. two boxes in a band must + * have some horizontal space between them. + */ + y2 = pCurBox->y2; + + do { + if ((pPrevBox->x1 != pCurBox->x1) || (pPrevBox->x2 != pCurBox->x2)) { + return (curStart); + } + pPrevBox++; + pCurBox++; + numRects--; + } while (numRects); + + /* + * The bands may be merged, so set the bottom y of each box + * in the previous band to the bottom y of the current band. + */ + numRects = curStart - prevStart; + pReg->data->numRects -= numRects; + do { + pPrevBox--; + pPrevBox->y2 = y2; + numRects--; + } while (numRects); + return prevStart; +} + + +/* Quicky macro to avoid trivial reject procedure calls to miCoalesce */ + +#define Coalesce(newReg, prevBand, curBand) \ + if (curBand - prevBand == newReg->data->numRects - curBand) { \ + prevBand = miCoalesce(newReg, prevBand, curBand); \ + } else { \ + prevBand = curBand; \ + } + +/*- + *----------------------------------------------------------------------- + * miAppendNonO -- + * Handle a non-overlapping band for the union and subtract operations. + * Just adds the (top/bottom-clipped) rectangles into the region. + * Doesn't have to check for subsumption or anything. + * + * Results: + * None. + * + * Side Effects: + * pReg->data->numRects is incremented and the rectangles overwritten + * with the rectangles we're passed. + * + *----------------------------------------------------------------------- + */ + +_X_INLINE static Bool +miAppendNonO ( + RegionPtr pReg, + BoxPtr r, + BoxPtr rEnd, + int y1, + int y2) +{ + BoxPtr pNextRect; + int newRects; + + newRects = rEnd - r; + + assert(y1 < y2); + assert(newRects != 0); + + /* Make sure we have enough space for all rectangles to be added */ + RECTALLOC(pReg, newRects); + pNextRect = REGION_TOP(pReg); + pReg->data->numRects += newRects; + do { + assert(r->x1 < r->x2); + ADDRECT(pNextRect, r->x1, y1, r->x2, y2); + r++; + } while (r != rEnd); + + return TRUE; +} + +#define FindBand(r, rBandEnd, rEnd, ry1) \ +{ \ + ry1 = r->y1; \ + rBandEnd = r+1; \ + while ((rBandEnd != rEnd) && (rBandEnd->y1 == ry1)) { \ + rBandEnd++; \ + } \ +} + +#define AppendRegions(newReg, r, rEnd) \ +{ \ + int newRects; \ + if ((newRects = rEnd - r)) { \ + RECTALLOC(newReg, newRects); \ + memmove((char *)REGION_TOP(newReg),(char *)r, \ + newRects * sizeof(BoxRec)); \ + newReg->data->numRects += newRects; \ + } \ +} + +/*- + *----------------------------------------------------------------------- + * miRegionOp -- + * Apply an operation to two regions. Called by miUnion, miInverse, + * miSubtract, miIntersect.... Both regions MUST have at least one + * rectangle, and cannot be the same object. + * + * Results: + * TRUE if successful. + * + * Side Effects: + * The new region is overwritten. + * pOverlap set to TRUE if overlapFunc ever returns TRUE. + * + * Notes: + * The idea behind this function is to view the two regions as sets. + * Together they cover a rectangle of area that this function divides + * into horizontal bands where points are covered only by one region + * or by both. For the first case, the nonOverlapFunc is called with + * each the band and the band's upper and lower extents. For the + * second, the overlapFunc is called to process the entire band. It + * is responsible for clipping the rectangles in the band, though + * this function provides the boundaries. + * At the end of each band, the new region is coalesced, if possible, + * to reduce the number of rectangles in the region. + * + *----------------------------------------------------------------------- + */ + +typedef Bool (*OverlapProcPtr)( + RegionPtr pReg, + BoxPtr r1, + BoxPtr r1End, + BoxPtr r2, + BoxPtr r2End, + short y1, + short y2, + Bool *pOverlap); + +static Bool +miRegionOp( + RegionPtr newReg, /* Place to store result */ + RegionPtr reg1, /* First region in operation */ + RegionPtr reg2, /* 2d region in operation */ + OverlapProcPtr overlapFunc, /* Function to call for over- + * lapping bands */ + Bool appendNon1, /* Append non-overlapping bands */ + /* in region 1 ? */ + Bool appendNon2, /* Append non-overlapping bands */ + /* in region 2 ? */ + Bool *pOverlap) +{ + BoxPtr r1; /* Pointer into first region */ + BoxPtr r2; /* Pointer into 2d region */ + BoxPtr r1End; /* End of 1st region */ + BoxPtr r2End; /* End of 2d region */ + short ybot; /* Bottom of intersection */ + short ytop; /* Top of intersection */ + RegDataPtr oldData; /* Old data for newReg */ + int prevBand; /* Index of start of + * previous band in newReg */ + int curBand; /* Index of start of current + * band in newReg */ + BoxPtr r1BandEnd; /* End of current band in r1 */ + BoxPtr r2BandEnd; /* End of current band in r2 */ + short top; /* Top of non-overlapping band */ + short bot; /* Bottom of non-overlapping band*/ + int r1y1; /* Temps for r1->y1 and r2->y1 */ + int r2y1; + int newSize; + int numRects; + + /* + * Break any region computed from a broken region + */ + if (REGION_NAR (reg1) || REGION_NAR(reg2)) + return miRegionBreak (newReg); + + /* + * Initialization: + * set r1, r2, r1End and r2End appropriately, save the rectangles + * of the destination region until the end in case it's one of + * the two source regions, then mark the "new" region empty, allocating + * another array of rectangles for it to use. + */ + + r1 = REGION_RECTS(reg1); + newSize = REGION_NUM_RECTS(reg1); + r1End = r1 + newSize; + numRects = REGION_NUM_RECTS(reg2); + r2 = REGION_RECTS(reg2); + r2End = r2 + numRects; + assert(r1 != r1End); + assert(r2 != r2End); + + oldData = NULL; + if (((newReg == reg1) && (newSize > 1)) || + ((newReg == reg2) && (numRects > 1))) + { + oldData = newReg->data; + newReg->data = &miEmptyData; + } + /* guess at new size */ + if (numRects > newSize) + newSize = numRects; + newSize <<= 1; + if (!newReg->data) + newReg->data = &miEmptyData; + else if (newReg->data->size) + newReg->data->numRects = 0; + if (newSize > newReg->data->size) + if (!miRectAlloc(newReg, newSize)) + return FALSE; + + /* + * Initialize ybot. + * In the upcoming loop, ybot and ytop serve different functions depending + * on whether the band being handled is an overlapping or non-overlapping + * band. + * In the case of a non-overlapping band (only one of the regions + * has points in the band), ybot is the bottom of the most recent + * intersection and thus clips the top of the rectangles in that band. + * ytop is the top of the next intersection between the two regions and + * serves to clip the bottom of the rectangles in the current band. + * For an overlapping band (where the two regions intersect), ytop clips + * the top of the rectangles of both regions and ybot clips the bottoms. + */ + + ybot = min(r1->y1, r2->y1); + + /* + * prevBand serves to mark the start of the previous band so rectangles + * can be coalesced into larger rectangles. qv. miCoalesce, above. + * In the beginning, there is no previous band, so prevBand == curBand + * (curBand is set later on, of course, but the first band will always + * start at index 0). prevBand and curBand must be indices because of + * the possible expansion, and resultant moving, of the new region's + * array of rectangles. + */ + prevBand = 0; + + do { + /* + * This algorithm proceeds one source-band (as opposed to a + * destination band, which is determined by where the two regions + * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the + * rectangle after the last one in the current band for their + * respective regions. + */ + assert(r1 != r1End); + assert(r2 != r2End); + + FindBand(r1, r1BandEnd, r1End, r1y1); + FindBand(r2, r2BandEnd, r2End, r2y1); + + /* + * First handle the band that doesn't intersect, if any. + * + * Note that attention is restricted to one band in the + * non-intersecting region at once, so if a region has n + * bands between the current position and the next place it overlaps + * the other, this entire loop will be passed through n times. + */ + if (r1y1 < r2y1) { + if (appendNon1) { + top = max(r1y1, ybot); + bot = min(r1->y2, r2y1); + if (top != bot) { + curBand = newReg->data->numRects; + miAppendNonO(newReg, r1, r1BandEnd, top, bot); + Coalesce(newReg, prevBand, curBand); + } + } + ytop = r2y1; + } else if (r2y1 < r1y1) { + if (appendNon2) { + top = max(r2y1, ybot); + bot = min(r2->y2, r1y1); + if (top != bot) { + curBand = newReg->data->numRects; + miAppendNonO(newReg, r2, r2BandEnd, top, bot); + Coalesce(newReg, prevBand, curBand); + } + } + ytop = r1y1; + } else { + ytop = r1y1; + } + + /* + * Now see if we've hit an intersecting band. The two bands only + * intersect if ybot > ytop + */ + ybot = min(r1->y2, r2->y2); + if (ybot > ytop) { + curBand = newReg->data->numRects; + (* overlapFunc)(newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot, + pOverlap); + Coalesce(newReg, prevBand, curBand); + } + + /* + * If we've finished with a band (y2 == ybot) we skip forward + * in the region to the next band. + */ + if (r1->y2 == ybot) r1 = r1BandEnd; + if (r2->y2 == ybot) r2 = r2BandEnd; + + } while (r1 != r1End && r2 != r2End); + + /* + * Deal with whichever region (if any) still has rectangles left. + * + * We only need to worry about banding and coalescing for the very first + * band left. After that, we can just group all remaining boxes, + * regardless of how many bands, into one final append to the list. + */ + + if ((r1 != r1End) && appendNon1) { + /* Do first nonOverlap1Func call, which may be able to coalesce */ + FindBand(r1, r1BandEnd, r1End, r1y1); + curBand = newReg->data->numRects; + miAppendNonO(newReg, r1, r1BandEnd, max(r1y1, ybot), r1->y2); + Coalesce(newReg, prevBand, curBand); + /* Just append the rest of the boxes */ + AppendRegions(newReg, r1BandEnd, r1End); + + } else if ((r2 != r2End) && appendNon2) { + /* Do first nonOverlap2Func call, which may be able to coalesce */ + FindBand(r2, r2BandEnd, r2End, r2y1); + curBand = newReg->data->numRects; + miAppendNonO(newReg, r2, r2BandEnd, max(r2y1, ybot), r2->y2); + Coalesce(newReg, prevBand, curBand); + /* Append rest of boxes */ + AppendRegions(newReg, r2BandEnd, r2End); + } + + if (oldData) + free(oldData); + + if (!(numRects = newReg->data->numRects)) + { + xfreeData(newReg); + newReg->data = &miEmptyData; + } + else if (numRects == 1) + { + newReg->extents = *REGION_BOXPTR(newReg); + xfreeData(newReg); + newReg->data = NULL; + } + else + { + DOWNSIZE(newReg, numRects); + } + + return TRUE; +} + +/*- + *----------------------------------------------------------------------- + * miSetExtents -- + * Reset the extents of a region to what they should be. Called by + * miSubtract and miIntersect as they can't figure it out along the + * way or do so easily, as miUnion can. + * + * Results: + * None. + * + * Side Effects: + * The region's 'extents' structure is overwritten. + * + *----------------------------------------------------------------------- + */ +static void +miSetExtents (RegionPtr pReg) +{ + BoxPtr pBox, pBoxEnd; + + if (!pReg->data) + return; + if (!pReg->data->size) + { + pReg->extents.x2 = pReg->extents.x1; + pReg->extents.y2 = pReg->extents.y1; + return; + } + + pBox = REGION_BOXPTR(pReg); + pBoxEnd = REGION_END(pReg); + + /* + * Since pBox is the first rectangle in the region, it must have the + * smallest y1 and since pBoxEnd is the last rectangle in the region, + * it must have the largest y2, because of banding. Initialize x1 and + * x2 from pBox and pBoxEnd, resp., as good things to initialize them + * to... + */ + pReg->extents.x1 = pBox->x1; + pReg->extents.y1 = pBox->y1; + pReg->extents.x2 = pBoxEnd->x2; + pReg->extents.y2 = pBoxEnd->y2; + + assert(pReg->extents.y1 < pReg->extents.y2); + while (pBox <= pBoxEnd) { + if (pBox->x1 < pReg->extents.x1) + pReg->extents.x1 = pBox->x1; + if (pBox->x2 > pReg->extents.x2) + pReg->extents.x2 = pBox->x2; + pBox++; + }; + + assert(pReg->extents.x1 < pReg->extents.x2); +} + +/*====================================================================== + * Region Intersection + *====================================================================*/ +/*- + *----------------------------------------------------------------------- + * miIntersectO -- + * Handle an overlapping band for miIntersect. + * + * Results: + * TRUE if successful. + * + * Side Effects: + * Rectangles may be added to the region. + * + *----------------------------------------------------------------------- + */ +/*ARGSUSED*/ +Bool +miIntersect( + RegionPtr newReg, /* destination Region */ + RegionPtr reg1, + RegionPtr reg2 /* source regions */ + ) +{ + return pixman_region_intersect (newReg, reg1, reg2); +} + +#define MERGERECT(r) \ +{ \ + if (r->x1 <= x2) { \ + /* Merge with current rectangle */ \ + if (r->x1 < x2) *pOverlap = TRUE; \ + if (x2 < r->x2) x2 = r->x2; \ + } else { \ + /* Add current rectangle, start new one */ \ + NEWRECT(pReg, pNextRect, x1, y1, x2, y2); \ + x1 = r->x1; \ + x2 = r->x2; \ + } \ + r++; \ +} + +/*====================================================================== + * Region Union + *====================================================================*/ + +/*- + *----------------------------------------------------------------------- + * miUnionO -- + * Handle an overlapping band for the union operation. Picks the + * left-most rectangle each time and merges it into the region. + * + * Results: + * TRUE if successful. + * + * Side Effects: + * pReg is overwritten. + * pOverlap is set to TRUE if any boxes overlap. + * + *----------------------------------------------------------------------- + */ +static Bool +miUnionO ( + RegionPtr pReg, + BoxPtr r1, + BoxPtr r1End, + BoxPtr r2, + BoxPtr r2End, + short y1, + short y2, + Bool *pOverlap) +{ + BoxPtr pNextRect; + int x1; /* left and right side of current union */ + int x2; + + assert (y1 < y2); + assert(r1 != r1End && r2 != r2End); + + pNextRect = REGION_TOP(pReg); + + /* Start off current rectangle */ + if (r1->x1 < r2->x1) + { + x1 = r1->x1; + x2 = r1->x2; + r1++; + } + else + { + x1 = r2->x1; + x2 = r2->x2; + r2++; + } + while (r1 != r1End && r2 != r2End) + { + if (r1->x1 < r2->x1) MERGERECT(r1) else MERGERECT(r2); + } + + /* Finish off whoever (if any) is left */ + if (r1 != r1End) + { + do + { + MERGERECT(r1); + } while (r1 != r1End); + } + else if (r2 != r2End) + { + do + { + MERGERECT(r2); + } while (r2 != r2End); + } + + /* Add current rectangle */ + NEWRECT(pReg, pNextRect, x1, y1, x2, y2); + + return TRUE; +} + +Bool +miUnion( + RegionPtr newReg, /* destination Region */ + RegionPtr reg1, + RegionPtr reg2 /* source regions */ + ) +{ + return pixman_region_union (newReg, reg1, reg2); +} + +/*====================================================================== + * Batch Rectangle Union + *====================================================================*/ + +/*- + *----------------------------------------------------------------------- + * miRegionAppend -- + * + * "Append" the rgn rectangles onto the end of dstrgn, maintaining + * knowledge of YX-banding when it's easy. Otherwise, dstrgn just + * becomes a non-y-x-banded random collection of rectangles, and not + * yet a true region. After a sequence of appends, the caller must + * call miRegionValidate to ensure that a valid region is constructed. + * + * Results: + * TRUE if successful. + * + * Side Effects: + * dstrgn is modified if rgn has rectangles. + * + */ +Bool +miRegionAppend(RegionPtr dstrgn, RegionPtr rgn) +{ + int numRects, dnumRects, size; + BoxPtr new, old; + Bool prepend; + + if (REGION_NAR(rgn)) + return miRegionBreak (dstrgn); + + if (!rgn->data && (dstrgn->data == &miEmptyData)) + { + dstrgn->extents = rgn->extents; + dstrgn->data = NULL; + return TRUE; + } + + numRects = REGION_NUM_RECTS(rgn); + if (!numRects) + return TRUE; + prepend = FALSE; + size = numRects; + dnumRects = REGION_NUM_RECTS(dstrgn); + if (!dnumRects && (size < 200)) + size = 200; /* XXX pick numbers out of a hat */ + RECTALLOC(dstrgn, size); + old = REGION_RECTS(rgn); + if (!dnumRects) + dstrgn->extents = rgn->extents; + else if (dstrgn->extents.x2 > dstrgn->extents.x1) + { + BoxPtr first, last; + + first = old; + last = REGION_BOXPTR(dstrgn) + (dnumRects - 1); + if ((first->y1 > last->y2) || + ((first->y1 == last->y1) && (first->y2 == last->y2) && + (first->x1 > last->x2))) + { + if (rgn->extents.x1 < dstrgn->extents.x1) + dstrgn->extents.x1 = rgn->extents.x1; + if (rgn->extents.x2 > dstrgn->extents.x2) + dstrgn->extents.x2 = rgn->extents.x2; + dstrgn->extents.y2 = rgn->extents.y2; + } + else + { + first = REGION_BOXPTR(dstrgn); + last = old + (numRects - 1); + if ((first->y1 > last->y2) || + ((first->y1 == last->y1) && (first->y2 == last->y2) && + (first->x1 > last->x2))) + { + prepend = TRUE; + if (rgn->extents.x1 < dstrgn->extents.x1) + dstrgn->extents.x1 = rgn->extents.x1; + if (rgn->extents.x2 > dstrgn->extents.x2) + dstrgn->extents.x2 = rgn->extents.x2; + dstrgn->extents.y1 = rgn->extents.y1; + } + else + dstrgn->extents.x2 = dstrgn->extents.x1; + } + } + if (prepend) + { + new = REGION_BOX(dstrgn, numRects); + if (dnumRects == 1) + *new = *REGION_BOXPTR(dstrgn); + else + memmove((char *)new,(char *)REGION_BOXPTR(dstrgn), + dnumRects * sizeof(BoxRec)); + new = REGION_BOXPTR(dstrgn); + } + else + new = REGION_BOXPTR(dstrgn) + dnumRects; + if (numRects == 1) + *new = *old; + else + memmove((char *)new, (char *)old, numRects * sizeof(BoxRec)); + dstrgn->data->numRects += numRects; + return TRUE; +} + + +#define ExchangeRects(a, b) \ +{ \ + BoxRec t; \ + t = rects[a]; \ + rects[a] = rects[b]; \ + rects[b] = t; \ +} + +static void +QuickSortRects( + BoxRec rects[], + int numRects) +{ + int y1; + int x1; + int i, j; + BoxPtr r; + + /* Always called with numRects > 1 */ + + do + { + if (numRects == 2) + { + if (rects[0].y1 > rects[1].y1 || + (rects[0].y1 == rects[1].y1 && rects[0].x1 > rects[1].x1)) + ExchangeRects(0, 1); + return; + } + + /* Choose partition element, stick in location 0 */ + ExchangeRects(0, numRects >> 1); + y1 = rects[0].y1; + x1 = rects[0].x1; + + /* Partition array */ + i = 0; + j = numRects; + do + { + r = &(rects[i]); + do + { + r++; + i++; + } while (i != numRects && + (r->y1 < y1 || (r->y1 == y1 && r->x1 < x1))); + r = &(rects[j]); + do + { + r--; + j--; + } while (y1 < r->y1 || (y1 == r->y1 && x1 < r->x1)); + if (i < j) + ExchangeRects(i, j); + } while (i < j); + + /* Move partition element back to middle */ + ExchangeRects(0, j); + + /* Recurse */ + if (numRects-j-1 > 1) + QuickSortRects(&rects[j+1], numRects-j-1); + numRects = j; + } while (numRects > 1); +} + +/*- + *----------------------------------------------------------------------- + * miRegionValidate -- + * + * Take a ``region'' which is a non-y-x-banded random collection of + * rectangles, and compute a nice region which is the union of all the + * rectangles. + * + * Results: + * TRUE if successful. + * + * Side Effects: + * The passed-in ``region'' may be modified. + * pOverlap set to TRUE if any retangles overlapped, else FALSE; + * + * Strategy: + * Step 1. Sort the rectangles into ascending order with primary key y1 + * and secondary key x1. + * + * Step 2. Split the rectangles into the minimum number of proper y-x + * banded regions. This may require horizontally merging + * rectangles, and vertically coalescing bands. With any luck, + * this step in an identity tranformation (ala the Box widget), + * or a coalescing into 1 box (ala Menus). + * + * Step 3. Merge the separate regions down to a single region by calling + * miUnion. Maximize the work each miUnion call does by using + * a binary merge. + * + *----------------------------------------------------------------------- + */ + +Bool +miRegionValidate(RegionPtr badreg, Bool *pOverlap) +{ + /* Descriptor for regions under construction in Step 2. */ + typedef struct { + RegionRec reg; + int prevBand; + int curBand; + } RegionInfo; + + int numRects; /* Original numRects for badreg */ + RegionInfo *ri; /* Array of current regions */ + int numRI; /* Number of entries used in ri */ + int sizeRI; /* Number of entries available in ri */ + int i; /* Index into rects */ + int j; /* Index into ri */ + RegionInfo *rit; /* &ri[j] */ + RegionPtr reg; /* ri[j].reg */ + BoxPtr box; /* Current box in rects */ + BoxPtr riBox; /* Last box in ri[j].reg */ + RegionPtr hreg; /* ri[j_half].reg */ + Bool ret = TRUE; + + *pOverlap = FALSE; + if (!badreg->data) + { + good(badreg); + return TRUE; + } + numRects = badreg->data->numRects; + if (!numRects) + { + if (REGION_NAR(badreg)) + return FALSE; + good(badreg); + return TRUE; + } + if (badreg->extents.x1 < badreg->extents.x2) + { + if ((numRects) == 1) + { + xfreeData(badreg); + badreg->data = (RegDataPtr) NULL; + } + else + { + DOWNSIZE(badreg, numRects); + } + good(badreg); + return TRUE; + } + + /* Step 1: Sort the rects array into ascending (y1, x1) order */ + QuickSortRects(REGION_BOXPTR(badreg), numRects); + + /* Step 2: Scatter the sorted array into the minimum number of regions */ + + /* Set up the first region to be the first rectangle in badreg */ + /* Note that step 2 code will never overflow the ri[0].reg rects array */ + ri = (RegionInfo *) malloc(4 * sizeof(RegionInfo)); + if (!ri) + return miRegionBreak (badreg); + sizeRI = 4; + numRI = 1; + ri[0].prevBand = 0; + ri[0].curBand = 0; + ri[0].reg = *badreg; + box = REGION_BOXPTR(&ri[0].reg); + ri[0].reg.extents = *box; + ri[0].reg.data->numRects = 1; + + /* Now scatter rectangles into the minimum set of valid regions. If the + next rectangle to be added to a region would force an existing rectangle + in the region to be split up in order to maintain y-x banding, just + forget it. Try the next region. If it doesn't fit cleanly into any + region, make a new one. */ + + for (i = numRects; --i > 0;) + { + box++; + /* Look for a region to append box to */ + for (j = numRI, rit = ri; --j >= 0; rit++) + { + reg = &rit->reg; + riBox = REGION_END(reg); + + if (box->y1 == riBox->y1 && box->y2 == riBox->y2) + { + /* box is in same band as riBox. Merge or append it */ + if (box->x1 <= riBox->x2) + { + /* Merge it with riBox */ + if (box->x1 < riBox->x2) *pOverlap = TRUE; + if (box->x2 > riBox->x2) riBox->x2 = box->x2; + } + else + { + RECTALLOC_BAIL(reg, 1, bail); + *REGION_TOP(reg) = *box; + reg->data->numRects++; + } + goto NextRect; /* So sue me */ + } + else if (box->y1 >= riBox->y2) + { + /* Put box into new band */ + if (reg->extents.x2 < riBox->x2) reg->extents.x2 = riBox->x2; + if (reg->extents.x1 > box->x1) reg->extents.x1 = box->x1; + Coalesce(reg, rit->prevBand, rit->curBand); + rit->curBand = reg->data->numRects; + RECTALLOC_BAIL(reg, 1, bail); + *REGION_TOP(reg) = *box; + reg->data->numRects++; + goto NextRect; + } + /* Well, this region was inappropriate. Try the next one. */ + } /* for j */ + + /* Uh-oh. No regions were appropriate. Create a new one. */ + if (sizeRI == numRI) + { + /* Oops, allocate space for new region information */ + sizeRI <<= 1; + rit = (RegionInfo *) realloc(ri, sizeRI * sizeof(RegionInfo)); + if (!rit) + goto bail; + ri = rit; + rit = &ri[numRI]; + } + numRI++; + rit->prevBand = 0; + rit->curBand = 0; + rit->reg.extents = *box; + rit->reg.data = NULL; + if (!miRectAlloc(&rit->reg, (i+numRI) / numRI)) /* MUST force allocation */ + goto bail; +NextRect: ; + } /* for i */ + + /* Make a final pass over each region in order to Coalesce and set + extents.x2 and extents.y2 */ + + for (j = numRI, rit = ri; --j >= 0; rit++) + { + reg = &rit->reg; + riBox = REGION_END(reg); + reg->extents.y2 = riBox->y2; + if (reg->extents.x2 < riBox->x2) reg->extents.x2 = riBox->x2; + Coalesce(reg, rit->prevBand, rit->curBand); + if (reg->data->numRects == 1) /* keep unions happy below */ + { + xfreeData(reg); + reg->data = NULL; + } + } + + /* Step 3: Union all regions into a single region */ + while (numRI > 1) + { + int half = numRI/2; + for (j = numRI & 1; j < (half + (numRI & 1)); j++) + { + reg = &ri[j].reg; + hreg = &ri[j+half].reg; + if (!miRegionOp(reg, reg, hreg, miUnionO, TRUE, TRUE, pOverlap)) + ret = FALSE; + if (hreg->extents.x1 < reg->extents.x1) + reg->extents.x1 = hreg->extents.x1; + if (hreg->extents.y1 < reg->extents.y1) + reg->extents.y1 = hreg->extents.y1; + if (hreg->extents.x2 > reg->extents.x2) + reg->extents.x2 = hreg->extents.x2; + if (hreg->extents.y2 > reg->extents.y2) + reg->extents.y2 = hreg->extents.y2; + xfreeData(hreg); + } + numRI -= half; + } + *badreg = ri[0].reg; + free(ri); + good(badreg); + return ret; +bail: + for (i = 0; i < numRI; i++) + xfreeData(&ri[i].reg); + free(ri); + return miRegionBreak (badreg); +} + +RegionPtr +miRectsToRegion(int nrects, xRectangle *prect, int ctype) +{ + + RegionPtr pRgn; + RegDataPtr pData; + BoxPtr pBox; + int i; + int x1, y1, x2, y2; + + pRgn = miRegionCreate(NullBox, 0); + if (REGION_NAR (pRgn)) + return pRgn; + if (!nrects) + return pRgn; + if (nrects == 1) + { + x1 = prect->x; + y1 = prect->y; + if ((x2 = x1 + (int) prect->width) > MAXSHORT) + x2 = MAXSHORT; + if ((y2 = y1 + (int) prect->height) > MAXSHORT) + y2 = MAXSHORT; + if (x1 != x2 && y1 != y2) + { + pRgn->extents.x1 = x1; + pRgn->extents.y1 = y1; + pRgn->extents.x2 = x2; + pRgn->extents.y2 = y2; + pRgn->data = NULL; + } + return pRgn; + } + pData = xallocData(nrects); + if (!pData) + { + miRegionBreak (pRgn); + return pRgn; + } + pBox = (BoxPtr) (pData + 1); + for (i = nrects; --i >= 0; prect++) + { + x1 = prect->x; + y1 = prect->y; + if ((x2 = x1 + (int) prect->width) > MAXSHORT) + x2 = MAXSHORT; + if ((y2 = y1 + (int) prect->height) > MAXSHORT) + y2 = MAXSHORT; + if (x1 != x2 && y1 != y2) + { + pBox->x1 = x1; + pBox->y1 = y1; + pBox->x2 = x2; + pBox->y2 = y2; + pBox++; + } + } + if (pBox != (BoxPtr) (pData + 1)) + { + pData->size = nrects; + pData->numRects = pBox - (BoxPtr) (pData + 1); + pRgn->data = pData; + if (ctype != CT_YXBANDED) + { + Bool overlap; /* result ignored */ + pRgn->extents.x1 = pRgn->extents.x2 = 0; + miRegionValidate(pRgn, &overlap); + } + else + miSetExtents(pRgn); + good(pRgn); + } + else + { + free(pData); + } + return pRgn; +} + +/*====================================================================== + * Region Subtraction + *====================================================================*/ + + +/*- + *----------------------------------------------------------------------- + * miSubtractO -- + * Overlapping band subtraction. x1 is the left-most point not yet + * checked. + * + * Results: + * TRUE if successful. + * + * Side Effects: + * pReg may have rectangles added to it. + * + *----------------------------------------------------------------------- + */ +/*ARGSUSED*/ + +/*- + *----------------------------------------------------------------------- + * miSubtract -- + * Subtract regS from regM and leave the result in regD. + * S stands for subtrahend, M for minuend and D for difference. + * + * Results: + * TRUE if successful. + * + * Side Effects: + * regD is overwritten. + * + *----------------------------------------------------------------------- + */ +Bool +miSubtract(RegionPtr regD, RegionPtr regM, RegionPtr regS) +{ + return pixman_region_subtract (regD, regM, regS); +} + +/*====================================================================== + * Region Inversion + *====================================================================*/ + +/*- + *----------------------------------------------------------------------- + * miInverse -- + * Take a region and a box and return a region that is everything + * in the box but not in the region. The careful reader will note + * that this is the same as subtracting the region from the box... + * + * Results: + * TRUE. + * + * Side Effects: + * newReg is overwritten. + * + *----------------------------------------------------------------------- + */ +Bool +miInverse( + RegionPtr newReg, /* Destination region */ + RegionPtr reg1, /* Region to invert */ + BoxPtr invRect /* Bounding box for inversion */ + ) +{ + return pixman_region_inverse (newReg, reg1, invRect); +} +int +miRectIn(RegionPtr region, BoxPtr prect) +{ + return pixman_region_contains_rectangle (region, prect); +} + +/* TranslateRegion(pReg, x, y) + translates in place +*/ + +void +miTranslateRegion(RegionPtr pReg, int x, int y) +{ + pixman_region_translate (pReg, x, y); +} + +void +miRegionReset(RegionPtr pReg, BoxPtr pBox) +{ + pixman_region_reset (pReg, pBox); +} + +Bool +miPointInRegion( + RegionPtr pReg, + int x, + int y, + BoxPtr box /* "return" value */ + ) +{ + return pixman_region_contains_point (pReg, x, y, box); +} + +Bool +miRegionNotEmpty(RegionPtr pReg) +{ + return pixman_region_not_empty (pReg); +} + +Bool +miRegionBroken(RegionPtr pReg) +{ + good(pReg); + return (REGION_NAR(pReg)); +} + +void +miRegionEmpty(RegionPtr pReg) +{ + good(pReg); + xfreeData(pReg); + pReg->extents.x2 = pReg->extents.x1; + pReg->extents.y2 = pReg->extents.y1; + pReg->data = &miEmptyData; +} + +BoxPtr +miRegionExtents(RegionPtr pReg) +{ + good(pReg); + return(&pReg->extents); +} + +#define ExchangeSpans(a, b) \ +{ \ + DDXPointRec tpt; \ + int tw; \ + \ + tpt = spans[a]; spans[a] = spans[b]; spans[b] = tpt; \ + tw = widths[a]; widths[a] = widths[b]; widths[b] = tw; \ +} + +/* ||| I should apply the merge sort code to rectangle sorting above, and see + if mapping time can be improved. But right now I've been at work 12 hours, + so forget it. +*/ + +static void QuickSortSpans( + DDXPointRec spans[], + int widths[], + int numSpans) +{ + int y; + int i, j, m; + DDXPointPtr r; + + /* Always called with numSpans > 1 */ + /* Sorts only by y, doesn't bother to sort by x */ + + do + { + if (numSpans < 9) + { + /* Do insertion sort */ + int yprev; + + yprev = spans[0].y; + i = 1; + do + { /* while i != numSpans */ + y = spans[i].y; + if (yprev > y) + { + /* spans[i] is out of order. Move into proper location. */ + DDXPointRec tpt; + int tw, k; + + for (j = 0; y >= spans[j].y; j++) {} + tpt = spans[i]; + tw = widths[i]; + for (k = i; k != j; k--) + { + spans[k] = spans[k-1]; + widths[k] = widths[k-1]; + } + spans[j] = tpt; + widths[j] = tw; + y = spans[i].y; + } /* if out of order */ + yprev = y; + i++; + } while (i != numSpans); + return; + } + + /* Choose partition element, stick in location 0 */ + m = numSpans / 2; + if (spans[m].y > spans[0].y) ExchangeSpans(m, 0); + if (spans[m].y > spans[numSpans-1].y) ExchangeSpans(m, numSpans-1); + if (spans[m].y > spans[0].y) ExchangeSpans(m, 0); + y = spans[0].y; + + /* Partition array */ + i = 0; + j = numSpans; + do + { + r = &(spans[i]); + do + { + r++; + i++; + } while (i != numSpans && r->y < y); + r = &(spans[j]); + do + { + r--; + j--; + } while (y < r->y); + if (i < j) + ExchangeSpans(i, j); + } while (i < j); + + /* Move partition element back to middle */ + ExchangeSpans(0, j); + + /* Recurse */ + if (numSpans-j-1 > 1) + QuickSortSpans(&spans[j+1], &widths[j+1], numSpans-j-1); + numSpans = j; + } while (numSpans > 1); +} + +#define NextBand() \ +{ \ + clipy1 = pboxBandStart->y1; \ + clipy2 = pboxBandStart->y2; \ + pboxBandEnd = pboxBandStart + 1; \ + while (pboxBandEnd != pboxLast && pboxBandEnd->y1 == clipy1) { \ + pboxBandEnd++; \ + } \ + for (; ppt != pptLast && ppt->y < clipy1; ppt++, pwidth++) {} \ +} + +/* + Clip a list of scanlines to a region. The caller has allocated the + space. FSorted is non-zero if the scanline origins are in ascending + order. + returns the number of new, clipped scanlines. +*/ + +int +miClipSpans( + RegionPtr prgnDst, + DDXPointPtr ppt, + int *pwidth, + int nspans, + DDXPointPtr pptNew, + int *pwidthNew, + int fSorted) +{ + DDXPointPtr pptLast; + int *pwidthNewStart; /* the vengeance of Xerox! */ + int y, x1, x2; + int numRects; + + good(prgnDst); + pptLast = ppt + nspans; + pwidthNewStart = pwidthNew; + + if (!prgnDst->data) + { + /* Do special fast code with clip boundaries in registers(?) */ + /* It doesn't pay much to make use of fSorted in this case, + so we lump everything together. */ + + int clipx1, clipx2, clipy1, clipy2; + + clipx1 = prgnDst->extents.x1; + clipy1 = prgnDst->extents.y1; + clipx2 = prgnDst->extents.x2; + clipy2 = prgnDst->extents.y2; + + for (; ppt != pptLast; ppt++, pwidth++) + { + y = ppt->y; + x1 = ppt->x; + if (clipy1 <= y && y < clipy2) + { + x2 = x1 + *pwidth; + if (x1 < clipx1) x1 = clipx1; + if (x2 > clipx2) x2 = clipx2; + if (x1 < x2) + { + /* part of span in clip rectangle */ + pptNew->x = x1; + pptNew->y = y; + *pwidthNew = x2 - x1; + pptNew++; + pwidthNew++; + } + } + } /* end for */ + + } + else if ((numRects = prgnDst->data->numRects)) + { + /* Have to clip against many boxes */ + BoxPtr pboxBandStart, pboxBandEnd; + BoxPtr pbox; + BoxPtr pboxLast; + int clipy1, clipy2; + + /* In this case, taking advantage of sorted spans gains more than + the sorting costs. */ + if ((! fSorted) && (nspans > 1)) + QuickSortSpans(ppt, pwidth, nspans); + + pboxBandStart = REGION_BOXPTR(prgnDst); + pboxLast = pboxBandStart + numRects; + + NextBand(); + + for (; ppt != pptLast; ) + { + y = ppt->y; + if (y < clipy2) + { + /* span is in the current band */ + pbox = pboxBandStart; + x1 = ppt->x; + x2 = x1 + *pwidth; + do + { /* For each box in band */ + int newx1, newx2; + + newx1 = x1; + newx2 = x2; + if (newx1 < pbox->x1) newx1 = pbox->x1; + if (newx2 > pbox->x2) newx2 = pbox->x2; + if (newx1 < newx2) + { + /* Part of span in clip rectangle */ + pptNew->x = newx1; + pptNew->y = y; + *pwidthNew = newx2 - newx1; + pptNew++; + pwidthNew++; + } + pbox++; + } while (pbox != pboxBandEnd); + ppt++; + pwidth++; + } + else + { + /* Move to next band, adjust ppt as needed */ + pboxBandStart = pboxBandEnd; + if (pboxBandStart == pboxLast) + break; /* We're completely done */ + NextBand(); + } + } + } + return (pwidthNew - pwidthNewStart); +} -- cgit v1.2.3