[PATCH 1/4] Move region implementation from mi to dix.
Keith Packard
keithp at keithp.com
Fri May 21 12:43:23 PDT 2010
There isn't any reason to have this in mi. Everything except the file
rename was done with the included script 'fix-miregion'.
Signed-off-by: Keith Packard <keithp at keithp.com>
---
dix/Makefile.am | 1 +
dix/region.c | 1843 ++++++++++++++++++++++++++++++++++++++++++++++++++
dix/window.c | 4 +-
exa/exa_accel.c | 2 +-
fb/fbpixmap.c | 4 +-
fix-miregion | 29 +
include/regionstr.h | 115 ++--
mi/Makefile.am | 1 -
mi/mi.h | 17 -
mi/miregion.c | 1845 ---------------------------------------------------
mi/mispans.c | 4 +-
mi/mispans.h | 10 -
mi/misprite.c | 4 +-
13 files changed, 1951 insertions(+), 1928 deletions(-)
create mode 100644 dix/region.c
create mode 100755 fix-miregion
delete mode 100644 mi/miregion.c
diff --git a/dix/Makefile.am b/dix/Makefile.am
index 42b5121..5e2dad7 100644
--- a/dix/Makefile.am
+++ b/dix/Makefile.am
@@ -32,6 +32,7 @@ libdix_la_SOURCES = \
privates.c \
property.c \
ptrveloc.c \
+ region.c \
registry.c \
resource.c \
selection.c \
diff --git a/dix/region.c b/dix/region.c
new file mode 100644
index 0000000..6ed2c1b
--- /dev/null
+++ b/dix/region.c
@@ -0,0 +1,1843 @@
+/***********************************************************
+
+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 <dix-config.h>
+#endif
+
+#include "regionstr.h"
+#include <X11/Xprotostr.h>
+#include <X11/Xfuncproto.h>
+#include "gc.h"
+#include <pixman.h>
+
+#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(ValidRegion(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 RegionValidate in order to support several speed improvements
+ * to ValidateTree. 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 (!RectAlloc(pReg, n)) { goto bail; }
+
+#define RECTALLOC(pReg,n) \
+if (!(pReg)->data || (((pReg)->data->numRects + (n)) > (pReg)->data->size)) \
+ if (!RectAlloc(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 (!RectAlloc(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 EmptyBox = {0, 0, 0, 0};
+RegDataRec EmptyData = {0, 0};
+
+RegDataRec BrokenData = {0, 0};
+static RegionRec BrokenRegion = { { 0, 0, 0, 0 }, &BrokenData };
+
+void
+InitRegions (void)
+{
+ pixman_region_set_static_pointers (&EmptyBox, &EmptyData, &BrokenData);
+}
+
+/*****************************************************************
+ * RegionCreate(rect, size)
+ * This routine does a simple malloc to make a structure of
+ * REGION of "size" number of rectangles.
+ *****************************************************************/
+
+RegionPtr
+RegionCreate(BoxPtr rect, int size)
+{
+ RegionPtr pReg;
+
+ pReg = (RegionPtr)malloc(sizeof(RegionRec));
+ if (!pReg)
+ return &BrokenRegion;
+
+ RegionInit (pReg, rect, size);
+
+ return(pReg);
+}
+
+void
+RegionDestroy(RegionPtr pReg)
+{
+ pixman_region_fini (pReg);
+ if (pReg != &BrokenRegion)
+ free(pReg);
+}
+
+void
+PrintRegion(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
+RegionEqual(RegionPtr reg1, RegionPtr reg2)
+{
+ return pixman_region_equal (reg1, reg2);
+}
+
+#ifdef DEBUG
+Bool
+ValidRegion(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 == &EmptyData)));
+ 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
+RegionInit(RegionPtr pReg, BoxPtr rect, int size)
+{
+ if (rect)
+ pixman_region_init_with_extents (pReg, rect);
+ else
+ pixman_region_init (pReg);
+}
+
+void
+RegionUninit(RegionPtr pReg)
+{
+ pixman_region_fini (pReg);
+}
+
+Bool
+RegionBreak (RegionPtr pReg)
+{
+ xfreeData (pReg);
+ pReg->extents = EmptyBox;
+ pReg->data = &BrokenData;
+ return FALSE;
+}
+
+Bool
+RectAlloc(RegionPtr pRgn, int n)
+{
+ RegDataPtr data;
+
+ if (!pRgn->data)
+ {
+ n++;
+ pRgn->data = xallocData(n);
+ if (!pRgn->data)
+ return RegionBreak (pRgn);
+ pRgn->data->numRects = 1;
+ *REGION_BOXPTR(pRgn) = pRgn->extents;
+ }
+ else if (!pRgn->data->size)
+ {
+ pRgn->data = xallocData(n);
+ if (!pRgn->data)
+ return RegionBreak (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 RegionBreak (pRgn);
+ pRgn->data = data;
+ }
+ pRgn->data->size = n;
+ return TRUE;
+}
+
+Bool
+RegionCopy(RegionPtr dst, RegionPtr src)
+{
+ return pixman_region_copy (dst, src);
+}
+
+/*======================================================================
+ * Generic Region Operator
+ *====================================================================*/
+
+/*-
+ *-----------------------------------------------------------------------
+ * Coalesce --
+ * 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 RegionOp.
+ *
+ * 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
+Coalesce (
+ 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 Coalesce */
+
+#define Coalesce(newReg, prevBand, curBand) \
+ if (curBand - prevBand == newReg->data->numRects - curBand) { \
+ prevBand = Coalesce(newReg, prevBand, curBand); \
+ } else { \
+ prevBand = curBand; \
+ }
+
+/*-
+ *-----------------------------------------------------------------------
+ * AppendNonO --
+ * 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
+AppendNonO (
+ 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; \
+ } \
+}
+
+/*-
+ *-----------------------------------------------------------------------
+ * RegionOp --
+ * Apply an operation to two regions. Called by Union, Inverse,
+ * Subtract, Intersect.... 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
+RegionOp(
+ 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 RegionBreak (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 = &EmptyData;
+ }
+ /* guess at new size */
+ if (numRects > newSize)
+ newSize = numRects;
+ newSize <<= 1;
+ if (!newReg->data)
+ newReg->data = &EmptyData;
+ else if (newReg->data->size)
+ newReg->data->numRects = 0;
+ if (newSize > newReg->data->size)
+ if (!RectAlloc(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. Coalesce, 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;
+ AppendNonO(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;
+ AppendNonO(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;
+ AppendNonO(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;
+ AppendNonO(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 = &EmptyData;
+ }
+ else if (numRects == 1)
+ {
+ newReg->extents = *REGION_BOXPTR(newReg);
+ xfreeData(newReg);
+ newReg->data = NULL;
+ }
+ else
+ {
+ DOWNSIZE(newReg, numRects);
+ }
+
+ return TRUE;
+}
+
+/*-
+ *-----------------------------------------------------------------------
+ * SetExtents --
+ * Reset the extents of a region to what they should be. Called by
+ * Subtract and Intersect as they can't figure it out along the
+ * way or do so easily, as Union can.
+ *
+ * Results:
+ * None.
+ *
+ * Side Effects:
+ * The region's 'extents' structure is overwritten.
+ *
+ *-----------------------------------------------------------------------
+ */
+static void
+SetExtents (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
+ *====================================================================*/
+/*-
+ *-----------------------------------------------------------------------
+ * IntersectO --
+ * Handle an overlapping band for Intersect.
+ *
+ * Results:
+ * TRUE if successful.
+ *
+ * Side Effects:
+ * Rectangles may be added to the region.
+ *
+ *-----------------------------------------------------------------------
+ */
+/*ARGSUSED*/
+Bool
+Intersect(
+ 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
+ *====================================================================*/
+
+/*-
+ *-----------------------------------------------------------------------
+ * UnionO --
+ * 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
+UnionO (
+ 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
+Union(
+ RegionPtr newReg, /* destination Region */
+ RegionPtr reg1,
+ RegionPtr reg2 /* source regions */
+ )
+{
+ return pixman_region_union (newReg, reg1, reg2);
+}
+
+/*======================================================================
+ * Batch Rectangle Union
+ *====================================================================*/
+
+/*-
+ *-----------------------------------------------------------------------
+ * RegionAppend --
+ *
+ * "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 RegionValidate to ensure that a valid region is constructed.
+ *
+ * Results:
+ * TRUE if successful.
+ *
+ * Side Effects:
+ * dstrgn is modified if rgn has rectangles.
+ *
+ */
+Bool
+RegionAppend(RegionPtr dstrgn, RegionPtr rgn)
+{
+ int numRects, dnumRects, size;
+ BoxPtr new, old;
+ Bool prepend;
+
+ if (REGION_NAR(rgn))
+ return RegionBreak (dstrgn);
+
+ if (!rgn->data && (dstrgn->data == &EmptyData))
+ {
+ 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);
+}
+
+/*-
+ *-----------------------------------------------------------------------
+ * RegionValidate --
+ *
+ * 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
+ * Union. Maximize the work each Union call does by using
+ * a binary merge.
+ *
+ *-----------------------------------------------------------------------
+ */
+
+Bool
+RegionValidate(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 RegionBreak (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 (!RectAlloc(&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 (!RegionOp(reg, reg, hreg, UnionO, 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 RegionBreak (badreg);
+}
+
+RegionPtr
+RectsToRegion(int nrects, xRectangle *prect, int ctype)
+{
+
+ RegionPtr pRgn;
+ RegDataPtr pData;
+ BoxPtr pBox;
+ int i;
+ int x1, y1, x2, y2;
+
+ pRgn = RegionCreate(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)
+ {
+ RegionBreak (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;
+ RegionValidate(pRgn, &overlap);
+ }
+ else
+ SetExtents(pRgn);
+ good(pRgn);
+ }
+ else
+ {
+ free(pData);
+ }
+ return pRgn;
+}
+
+/*======================================================================
+ * Region Subtraction
+ *====================================================================*/
+
+
+/*-
+ *-----------------------------------------------------------------------
+ * SubtractO --
+ * 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*/
+
+/*-
+ *-----------------------------------------------------------------------
+ * Subtract --
+ * 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
+Subtract(RegionPtr regD, RegionPtr regM, RegionPtr regS)
+{
+ return pixman_region_subtract (regD, regM, regS);
+}
+
+/*======================================================================
+ * Region Inversion
+ *====================================================================*/
+
+/*-
+ *-----------------------------------------------------------------------
+ * Inverse --
+ * 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
+Inverse(
+ RegionPtr newReg, /* Destination region */
+ RegionPtr reg1, /* Region to invert */
+ BoxPtr invRect /* Bounding box for inversion */
+ )
+{
+ return pixman_region_inverse (newReg, reg1, invRect);
+}
+int
+RectIn(RegionPtr region, BoxPtr prect)
+{
+ return pixman_region_contains_rectangle (region, prect);
+}
+
+/* TranslateRegion(pReg, x, y)
+ translates in place
+*/
+
+void
+TranslateRegion(RegionPtr pReg, int x, int y)
+{
+ pixman_region_translate (pReg, x, y);
+}
+
+void
+RegionReset(RegionPtr pReg, BoxPtr pBox)
+{
+ pixman_region_reset (pReg, pBox);
+}
+
+Bool
+PointInRegion(
+ RegionPtr pReg,
+ int x,
+ int y,
+ BoxPtr box /* "return" value */
+ )
+{
+ return pixman_region_contains_point (pReg, x, y, box);
+}
+
+Bool
+RegionNotEmpty(RegionPtr pReg)
+{
+ return pixman_region_not_empty (pReg);
+}
+
+Bool
+RegionBroken(RegionPtr pReg)
+{
+ good(pReg);
+ return (REGION_NAR(pReg));
+}
+
+void
+RegionEmpty(RegionPtr pReg)
+{
+ good(pReg);
+ xfreeData(pReg);
+ pReg->extents.x2 = pReg->extents.x1;
+ pReg->extents.y2 = pReg->extents.y1;
+ pReg->data = &EmptyData;
+}
+
+BoxPtr
+RegionExtents(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
+ClipSpans(
+ 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);
+}
diff --git a/dix/window.c b/dix/window.c
index 00854c6..4ffd8b8 100644
--- a/dix/window.c
+++ b/dix/window.c
@@ -197,7 +197,7 @@ PrintChildren(WindowPtr p1, int indent)
ErrorF("[dix] ");
for (i=0; i<indent; i++) ErrorF(" ");
ErrorF("%lx\n", p1->drawable.id);
- miPrintRegion(&p1->clipList);
+ PrintRegion(&p1->clipList);
PrintChildren(p2, indent+4);
p1 = p1->nextSib;
}
@@ -213,7 +213,7 @@ PrintWindowTree(void)
{
ErrorF("[dix] WINDOW %d\n", i);
pWin = WindowTable[i];
- miPrintRegion(&pWin->clipList);
+ PrintRegion(&pWin->clipList);
p1 = pWin->firstChild;
PrintChildren(p1, 4);
}
diff --git a/exa/exa_accel.c b/exa/exa_accel.c
index 4164ff7..cf48ecd 100644
--- a/exa/exa_accel.c
+++ b/exa/exa_accel.c
@@ -407,7 +407,7 @@ exaHWCopyNtoN (DrawablePtr pSrcDrawable,
rects[i].height = pbox[i].y2 - pbox[i].y1;
}
- /* This must match the miRegionCopy() logic for reversing rect order */
+ /* This must match the RegionCopy() logic for reversing rect order */
if (nbox == 1 || (dx > 0 && dy > 0) ||
(pDstDrawable != pSrcDrawable &&
(pDstDrawable->type != DRAWABLE_WINDOW ||
diff --git a/fb/fbpixmap.c b/fb/fbpixmap.c
index c73f9f4..da876a4 100644
--- a/fb/fbpixmap.c
+++ b/fb/fbpixmap.c
@@ -115,7 +115,7 @@ if (((rx1) < (rx2)) && ((ry1) < (ry2)) && \
{ \
if ((reg)->data->numRects == (reg)->data->size) \
{ \
- miRectAlloc(reg, 1); \
+ RectAlloc(reg, 1); \
fr = REGION_BOXPTR(reg); \
r = fr + (reg)->data->numRects; \
} \
@@ -315,7 +315,7 @@ fbPixmapToRegion(PixmapPtr pPix)
fbFinishAccess(&pPix->drawable);
#ifdef DEBUG
- if (!miValidRegion(pReg))
+ if (!ValidRegion(pReg))
FatalError("Assertion failed file %s, line %d: expr\n", __FILE__, __LINE__);
#endif
return(pReg);
diff --git a/fix-miregion b/fix-miregion
new file mode 100755
index 0000000..9605409
--- /dev/null
+++ b/fix-miregion
@@ -0,0 +1,29 @@
+#!/bin/sh
+sed -i \
+-e 's/miRegionCreate/RegionCreate/g' \
+-e 's/miRegionInit/RegionInit/g' \
+-e 's/miRegionDestroy/RegionDestroy/g' \
+-e 's/miRegionUninit/RegionUninit/g' \
+-e 's/miRegionCopy/RegionCopy/g' \
+-e 's/miIntersect/Intersect/g' \
+-e 's/miUnion/Union/g' \
+-e 's/miRegionAppend/RegionAppend/g' \
+-e 's/miRegionValidate/RegionValidate/g' \
+-e 's/miRectsToRegion/RectsToRegion/g' \
+-e 's/miSubtract/Subtract/g' \
+-e 's/miInverse/Inverse/g' \
+-e 's/miRectIn/RectIn/g' \
+-e 's/miTranslateRegion/TranslateRegion/g' \
+-e 's/miRegionReset/RegionReset/g' \
+-e 's/miRegionBreak/RegionBreak/g' \
+-e 's/miPointInRegion/PointInRegion/g' \
+-e 's/miRegionEqual/RegionEqual/g' \
+-e 's/miRegionNotEmpty/RegionNotEmpty/g' \
+-e 's/miRegionEmpty/RegionEmpty/g' \
+-e 's/miRegionExtents/RegionExtents/g' \
+-e 's/miPrintRegion/PrintRegion/g' \
+-e 's/miRectAlloc/RectAlloc/g' \
+-e 's/miValidRegion/ValidRegion/g' \
+-e 's/miRegionBroken/RegionBroken/g' \
+-e 's/miClipSpans/ClipSpans/g' \
+"$@"
diff --git a/include/regionstr.h b/include/regionstr.h
index 6a5c98c..d6b3776 100644
--- a/include/regionstr.h
+++ b/include/regionstr.h
@@ -66,13 +66,13 @@ typedef struct pixman_region16 RegionRec, *RegionPtr;
typedef struct pixman_region16_data RegDataRec, *RegDataPtr;
-extern _X_EXPORT BoxRec miEmptyBox;
-extern _X_EXPORT RegDataRec miEmptyData;
-extern _X_EXPORT RegDataRec miBrokenData;
+extern _X_EXPORT BoxRec EmptyBox;
+extern _X_EXPORT RegDataRec EmptyData;
+extern _X_EXPORT RegDataRec BrokenData;
#define REGION_NIL(reg) ((reg)->data && !(reg)->data->numRects)
/* not a region */
-#define REGION_NAR(reg) ((reg)->data == &miBrokenData)
+#define REGION_NAR(reg) ((reg)->data == &BrokenData)
#define REGION_NUM_RECTS(reg) ((reg)->data ? (reg)->data->numRects : 1)
#define REGION_SIZE(reg) ((reg)->data ? (reg)->data->size : 0)
#define REGION_RECTS(reg) ((reg)->data ? (BoxPtr)((reg)->data + 1) \
@@ -84,52 +84,52 @@ extern _X_EXPORT RegDataRec miBrokenData;
#define REGION_SZOF(n) (sizeof(RegDataRec) + ((n) * sizeof(BoxRec)))
#define REGION_CREATE(_pScreen, _rect, _size) \
- miRegionCreate(_rect, _size)
+ RegionCreate(_rect, _size)
#define REGION_COPY(_pScreen, dst, src) \
- miRegionCopy(dst, src)
+ RegionCopy(dst, src)
#define REGION_DESTROY(_pScreen, _pReg) \
- miRegionDestroy(_pReg)
+ RegionDestroy(_pReg)
#define REGION_INTERSECT(_pScreen, newReg, reg1, reg2) \
- miIntersect(newReg, reg1, reg2)
+ Intersect(newReg, reg1, reg2)
#define REGION_UNION(_pScreen, newReg, reg1, reg2) \
- miUnion(newReg, reg1, reg2)
+ Union(newReg, reg1, reg2)
#define REGION_SUBTRACT(_pScreen, newReg, reg1, reg2) \
- miSubtract(newReg, reg1, reg2)
+ Subtract(newReg, reg1, reg2)
#define REGION_INVERSE(_pScreen, newReg, reg1, invRect) \
- miInverse(newReg, reg1, invRect)
+ Inverse(newReg, reg1, invRect)
#define REGION_TRANSLATE(_pScreen, _pReg, _x, _y) \
- miTranslateRegion(_pReg, _x, _y)
+ TranslateRegion(_pReg, _x, _y)
#define RECT_IN_REGION(_pScreen, _pReg, prect) \
- miRectIn(_pReg, prect)
+ RectIn(_pReg, prect)
#define POINT_IN_REGION(_pScreen, _pReg, _x, _y, prect) \
- miPointInRegion(_pReg, _x, _y, prect)
+ PointInRegion(_pReg, _x, _y, prect)
#define REGION_APPEND(_pScreen, dstrgn, rgn) \
- miRegionAppend(dstrgn, rgn)
+ RegionAppend(dstrgn, rgn)
#define REGION_VALIDATE(_pScreen, badreg, pOverlap) \
- miRegionValidate(badreg, pOverlap)
+ RegionValidate(badreg, pOverlap)
#define BITMAP_TO_REGION(_pScreen, pPix) \
(*(_pScreen)->BitmapToRegion)(pPix) /* no mi version?! */
#define RECTS_TO_REGION(_pScreen, nrects, prect, ctype) \
- miRectsToRegion(nrects, prect, ctype)
+ RectsToRegion(nrects, prect, ctype)
#define REGION_EQUAL(_pScreen, _pReg1, _pReg2) \
- miRegionEqual(_pReg1, _pReg2)
+ RegionEqual(_pReg1, _pReg2)
#define REGION_BREAK(_pScreen, _pReg) \
- miRegionBreak(_pReg)
+ RegionBreak(_pReg)
#define REGION_INIT(_pScreen, _pReg, _rect, _size) \
{ \
@@ -140,7 +140,7 @@ extern _X_EXPORT RegDataRec miBrokenData;
} \
else \
{ \
- (_pReg)->extents = miEmptyBox; \
+ (_pReg)->extents = EmptyBox; \
if (((_size) > 1) && ((_pReg)->data = \
(RegDataPtr)malloc(REGION_SZOF(_size)))) \
{ \
@@ -148,7 +148,7 @@ extern _X_EXPORT RegDataRec miBrokenData;
(_pReg)->data->numRects = 0; \
} \
else \
- (_pReg)->data = &miEmptyData; \
+ (_pReg)->data = &EmptyData; \
} \
}
@@ -179,7 +179,7 @@ extern _X_EXPORT RegDataRec miBrokenData;
REGION_UNINIT(_pScreen, _pReg); \
(_pReg)->extents.x2 = (_pReg)->extents.x1; \
(_pReg)->extents.y2 = (_pReg)->extents.y1; \
- (_pReg)->data = &miEmptyData; \
+ (_pReg)->data = &EmptyData; \
}
#define REGION_EXTENTS(_pScreen, _pReg) \
@@ -187,8 +187,8 @@ extern _X_EXPORT RegDataRec miBrokenData;
#define REGION_NULL(_pScreen, _pReg) \
{ \
- (_pReg)->extents = miEmptyBox; \
- (_pReg)->data = &miEmptyData; \
+ (_pReg)->extents = EmptyBox; \
+ (_pReg)->data = &EmptyData; \
}
#ifndef REGION_NULL
@@ -200,94 +200,117 @@ extern _X_EXPORT RegDataRec miBrokenData;
extern _X_EXPORT void InitRegions (void);
-extern _X_EXPORT RegionPtr miRegionCreate(
+extern _X_EXPORT RegionPtr RegionCreate(
BoxPtr /*rect*/,
int /*size*/);
-extern _X_EXPORT void miRegionInit(
+extern _X_EXPORT void RegionInit(
RegionPtr /*pReg*/,
BoxPtr /*rect*/,
int /*size*/);
-extern _X_EXPORT void miRegionDestroy(
+extern _X_EXPORT void RegionDestroy(
RegionPtr /*pReg*/);
-extern _X_EXPORT void miRegionUninit(
+extern _X_EXPORT void RegionUninit(
RegionPtr /*pReg*/);
-extern _X_EXPORT Bool miRegionCopy(
+extern _X_EXPORT Bool RegionCopy(
RegionPtr /*dst*/,
RegionPtr /*src*/);
-extern _X_EXPORT Bool miIntersect(
+extern _X_EXPORT Bool Intersect(
RegionPtr /*newReg*/,
RegionPtr /*reg1*/,
RegionPtr /*reg2*/);
-extern _X_EXPORT Bool miUnion(
+extern _X_EXPORT Bool Union(
RegionPtr /*newReg*/,
RegionPtr /*reg1*/,
RegionPtr /*reg2*/);
-extern _X_EXPORT Bool miRegionAppend(
+extern _X_EXPORT Bool RegionAppend(
RegionPtr /*dstrgn*/,
RegionPtr /*rgn*/);
-extern _X_EXPORT Bool miRegionValidate(
+extern _X_EXPORT Bool RegionValidate(
RegionPtr /*badreg*/,
Bool * /*pOverlap*/);
-extern _X_EXPORT RegionPtr miRectsToRegion(
+extern _X_EXPORT RegionPtr RectsToRegion(
int /*nrects*/,
xRectanglePtr /*prect*/,
int /*ctype*/);
-extern _X_EXPORT Bool miSubtract(
+extern _X_EXPORT Bool Subtract(
RegionPtr /*regD*/,
RegionPtr /*regM*/,
RegionPtr /*regS*/);
-extern _X_EXPORT Bool miInverse(
+extern _X_EXPORT Bool Inverse(
RegionPtr /*newReg*/,
RegionPtr /*reg1*/,
BoxPtr /*invRect*/);
-extern _X_EXPORT int miRectIn(
+extern _X_EXPORT int RectIn(
RegionPtr /*region*/,
BoxPtr /*prect*/);
-extern _X_EXPORT void miTranslateRegion(
+extern _X_EXPORT void TranslateRegion(
RegionPtr /*pReg*/,
int /*x*/,
int /*y*/);
-extern _X_EXPORT void miRegionReset(
+extern _X_EXPORT void RegionReset(
RegionPtr /*pReg*/,
BoxPtr /*pBox*/);
-extern _X_EXPORT Bool miRegionBreak(
+extern _X_EXPORT Bool RegionBreak(
RegionPtr /*pReg*/);
-extern _X_EXPORT Bool miPointInRegion(
+extern _X_EXPORT Bool PointInRegion(
RegionPtr /*pReg*/,
int /*x*/,
int /*y*/,
BoxPtr /*box*/);
-extern _X_EXPORT Bool miRegionEqual(
+extern _X_EXPORT Bool RegionEqual(
RegionPtr /*pReg1*/,
RegionPtr /*pReg2*/);
-extern _X_EXPORT Bool miRegionNotEmpty(
+extern _X_EXPORT Bool RegionNotEmpty(
RegionPtr /*pReg*/);
-extern _X_EXPORT void miRegionEmpty(
+extern _X_EXPORT void RegionEmpty(
RegionPtr /*pReg*/);
-extern _X_EXPORT BoxPtr miRegionExtents(
+extern _X_EXPORT BoxPtr RegionExtents(
RegionPtr /*pReg*/);
-extern _X_EXPORT void miPrintRegion(
+extern _X_EXPORT void PrintRegion(
RegionPtr /*pReg*/);
+extern _X_EXPORT Bool RectAlloc(
+ RegionPtr /*pRgn*/,
+ int /*n*/
+);
+
+#ifdef DEBUG
+extern _X_EXPORT Bool ValidRegion(
+ RegionPtr /*prgn*/
+);
+#endif
+
+extern _X_EXPORT Bool RegionBroken(RegionPtr pReg);
+
+extern _X_EXPORT int ClipSpans(
+ RegionPtr /*prgnDst*/,
+ DDXPointPtr /*ppt*/,
+ int * /*pwidth*/,
+ int /*nspans*/,
+ DDXPointPtr /*pptNew*/,
+ int * /*pwidthNew*/,
+ int /*fSorted*/
+);
+
#endif /* REGIONSTRUCT_H */
diff --git a/mi/Makefile.am b/mi/Makefile.am
index f22dde9..f6dabda 100644
--- a/mi/Makefile.am
+++ b/mi/Makefile.am
@@ -48,7 +48,6 @@ libmi_la_SOURCES = \
mipolytext.c \
mipolyutil.c \
mipushpxl.c \
- miregion.c \
miscanfill.h \
miscrinit.c \
mispans.c \
diff --git a/mi/mi.h b/mi/mi.h
index 812edce..94ad5fa 100644
--- a/mi/mi.h
+++ b/mi/mi.h
@@ -418,23 +418,6 @@ extern _X_EXPORT void miPushPixels(
int /*yOrg*/
);
-/* miregion.c */
-
-/* see also region.h */
-
-extern _X_EXPORT Bool miRectAlloc(
- RegionPtr /*pRgn*/,
- int /*n*/
-);
-
-#ifdef DEBUG
-extern _X_EXPORT Bool miValidRegion(
- RegionPtr /*prgn*/
-);
-#endif
-
-extern _X_EXPORT Bool miRegionBroken(RegionPtr pReg);
-
/* miscrinit.c */
extern _X_EXPORT Bool miModifyPixmapHeader(
diff --git a/mi/miregion.c b/mi/miregion.c
deleted file mode 100644
index 59aaa85..0000000
--- a/mi/miregion.c
+++ /dev/null
@@ -1,1845 +0,0 @@
-/***********************************************************
-
-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 <dix-config.h>
-#endif
-
-#include "regionstr.h"
-#include <X11/Xprotostr.h>
-#include <X11/Xfuncproto.h>
-#include "gc.h"
-#include "mi.h"
-#include "mispans.h"
-#include <pixman.h>
-
-#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);
-}
diff --git a/mi/mispans.c b/mi/mispans.c
index 8ac66cc..88d6003 100644
--- a/mi/mispans.c
+++ b/mi/mispans.c
@@ -77,7 +77,7 @@ void miInitSpanGroup(SpanGroup *spanGroup)
#define YMIN(spans) (spans->points[0].y)
#define YMAX(spans) (spans->points[spans->count-1].y)
-static void miSubtractSpans (SpanGroup *spanGroup, Spans *sub)
+static void SubtractSpans (SpanGroup *spanGroup, Spans *sub)
{
int i, subCount, spansCount;
int ymin, ymax, xmin, xmax;
@@ -203,7 +203,7 @@ void miAppendSpans(SpanGroup *spanGroup, SpanGroup *otherGroup, Spans *spans)
otherGroup->ymin < ymax &&
ymin < otherGroup->ymax)
{
- miSubtractSpans (otherGroup, spans);
+ SubtractSpans (otherGroup, spans);
}
}
else
diff --git a/mi/mispans.h b/mi/mispans.h
index 8151415..c3a3e67 100644
--- a/mi/mispans.h
+++ b/mi/mispans.h
@@ -85,16 +85,6 @@ extern _X_EXPORT void miFreeSpanGroup(
SpanGroup * /*spanGroup*/
);
-extern _X_EXPORT int miClipSpans(
- RegionPtr /*prgnDst*/,
- DDXPointPtr /*ppt*/,
- int * /*pwidth*/,
- int /*nspans*/,
- DDXPointPtr /*pptNew*/,
- int * /*pwidthNew*/,
- int /*fSorted*/
-);
-
/* Rops which must use span groups */
#define miSpansCarefulRop(rop) (((rop) & 0xc) == 0x8 || ((rop) & 0x3) == 0x2)
#define miSpansEasyRop(rop) (!miSpansCarefulRop(rop))
diff --git a/mi/misprite.c b/mi/misprite.c
index 3d10bc8..c232879 100644
--- a/mi/misprite.c
+++ b/mi/misprite.c
@@ -268,7 +268,7 @@ miSpriteReportDamage (DamagePtr pDamage, RegionPtr pRegion, void *closure)
if (pCursorInfo->isUp &&
pCursorInfo->pScreen == pScreen &&
- miRectIn(pRegion, &pCursorInfo->saved) != rgnOUT)
+ RectIn(pRegion, &pCursorInfo->saved) != rgnOUT)
{
SPRITE_DEBUG(("Damage remove\n"));
miSpriteRemoveCursor (pDev, pScreen);
@@ -523,7 +523,7 @@ miSpriteCopyWindow (WindowPtr pWindow, DDXPointRec ptOldOrg, RegionPtr prgnSrc)
* Damage will take care of destination check
*/
if (pCursorInfo->isUp && pCursorInfo->pScreen == pScreen &&
- miRectIn(prgnSrc, &pCursorInfo->saved) != rgnOUT)
+ RectIn(prgnSrc, &pCursorInfo->saved) != rgnOUT)
{
SPRITE_DEBUG (("CopyWindow remove\n"));
miSpriteRemoveCursor (pDev, pScreen);
--
1.7.1
More information about the xorg-devel
mailing list