svn merge ^/branches/released .

1 files changed, 1659 insertions, 0 deletions

diff --git a/xorg-server/dix/region.c b/xorg-server/dix/region.c
new file mode 100644
index 000000000..c0add6ca9
--- /dev/null
+++ b/xorg-server/dix/region.c
@@ -0,0 +1,1659 @@
+/***********************************************************

+

+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(RegionIsValid(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 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(RegionSizeof(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 (!RegionRectAlloc(pReg, n)) { goto bail; }

+

+#define RECTALLOC(pReg,n) \

+if (!(pReg)->data || (((pReg)->data->numRects + (n)) > (pReg)->data->size)) \

+    if (!RegionRectAlloc(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 (!RegionRectAlloc(pReg, 1))					\

+	    return FALSE;						\

+	pNextRect = RegionTop(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, RegionSizeof(numRects));	 \

+    if (NewData)							 \

+    {									 \

+	NewData->size = (numRects);					 \

+	(reg)->data = NewData;						 \

+    }									 \

+}

+

+

+BoxRec RegionEmptyBox = {0, 0, 0, 0};

+RegDataRec RegionEmptyData = {0, 0};

+

+RegDataRec  RegionBrokenData = {0, 0};

+static RegionRec   RegionBrokenRegion = { { 0, 0, 0, 0 }, &RegionBrokenData };

+

+void

+InitRegions (void)

+{

+    pixman_region_set_static_pointers (&RegionEmptyBox, &RegionEmptyData, &RegionBrokenData);

+}

+

+/*****************************************************************

+ *   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 &RegionBrokenRegion;

+

+    RegionInit (pReg, rect, size);

+    

+    return pReg;

+}

+

+void

+RegionDestroy(RegionPtr pReg)

+{

+    pixman_region_fini (pReg);

+    if (pReg != &RegionBrokenRegion)

+	free(pReg);

+}

+

+void

+RegionPrint(RegionPtr rgn)

+{

+    int num, size;

+    int i;

+    BoxPtr rects;

+

+    num = RegionNumRects(rgn);

+    size = RegionSize(rgn);

+    rects = RegionRects(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");

+}

+

+#ifdef DEBUG

+Bool

+RegionIsValid(RegionPtr reg)

+{

+    int i, numRects;

+    

+    if ((reg->extents.x1 > reg->extents.x2) ||

+	(reg->extents.y1 > reg->extents.y2))

+	return FALSE;

+    numRects = RegionNumRects(reg);

+    if (!numRects)

+	return ((reg->extents.x1 == reg->extents.x2) &&

+		(reg->extents.y1 == reg->extents.y2) &&

+		(reg->data->size || (reg->data == &RegionEmptyData)));

+    else if (numRects == 1)

+	return !reg->data;

+    else

+    {

+	BoxPtr pboxP, pboxN;

+	BoxRec box;

+	

+	pboxP = RegionRects(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 */

+

+Bool

+RegionBreak (RegionPtr pReg)

+{

+    xfreeData (pReg);

+    pReg->extents = RegionEmptyBox;

+    pReg->data = &RegionBrokenData;

+    return FALSE;

+}

+

+Bool

+RegionRectAlloc(RegionPtr pRgn, int n)

+{

+    RegDataPtr	data;

+    

+    if (!pRgn->data)

+    {

+	n++;

+	pRgn->data = xallocData(n);

+	if (!pRgn->data)

+	    return RegionBreak (pRgn);

+	pRgn->data->numRects = 1;

+	*RegionBoxptr(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, RegionSizeof(n));

+	if (!data)

+	    return RegionBreak (pRgn);

+	pRgn->data = data;

+    }

+    pRgn->data->size = n;

+    return TRUE;

+}

+

+/*======================================================================

+ *	    Generic Region Operator

+ *====================================================================*/

+

+/*-

+ *-----------------------------------------------------------------------

+ * RegionCoalesce --

+ *	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

+RegionCoalesce (

+    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 = RegionBox(pReg, prevStart);

+    pCurBox = RegionBox(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 RegionCoalesce */

+

+#define Coalesce(newReg, prevBand, curBand)				\

+    if (curBand - prevBand == newReg->data->numRects - curBand) {	\

+	prevBand = RegionCoalesce(newReg, prevBand, curBand);		\

+    } else {								\

+	prevBand = curBand;						\

+    }

+

+/*-

+ *-----------------------------------------------------------------------

+ * RegionAppendNonO --

+ *	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

+RegionAppendNonO (

+    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 = RegionTop(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 *)RegionTop(newReg),(char *)r, 			\

+              newRects * sizeof(BoxRec));				\

+	newReg->data->numRects += newRects;				\

+    }									\

+}

+

+/*-

+ *-----------------------------------------------------------------------

+ * RegionOp --

+ *	Apply an operation to two regions. Called by RegionUnion, RegionInverse,

+ *	RegionSubtract, RegionIntersect....  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 (RegionNar (reg1) || RegionNar(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 = RegionRects(reg1);

+    newSize = RegionNumRects(reg1);

+    r1End = r1 + newSize;

+    numRects = RegionNumRects(reg2);

+    r2 = RegionRects(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 = &RegionEmptyData;

+    }

+    /* guess at new size */

+    if (numRects > newSize)

+	newSize = numRects;

+    newSize <<= 1;

+    if (!newReg->data)

+	newReg->data = &RegionEmptyData;

+    else if (newReg->data->size)

+	newReg->data->numRects = 0;

+    if (newSize > newReg->data->size)

+	if (!RegionRectAlloc(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. RegionCoalesce, 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;

+		    RegionAppendNonO(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;

+		    RegionAppendNonO(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;

+	RegionAppendNonO(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;

+	RegionAppendNonO(newReg, r2, r2BandEnd, max(r2y1, ybot), r2->y2);

+	Coalesce(newReg, prevBand, curBand);

+	/* Append rest of boxes */

+	AppendRegions(newReg, r2BandEnd, r2End);

+    }

+

+    free(oldData);

+

+    if (!(numRects = newReg->data->numRects))

+    {

+	xfreeData(newReg);

+	newReg->data = &RegionEmptyData;

+    }

+    else if (numRects == 1)

+    {

+	newReg->extents = *RegionBoxptr(newReg);

+	xfreeData(newReg);

+	newReg->data = NULL;

+    }

+    else

+    {

+	DOWNSIZE(newReg, numRects);

+    }

+

+    return TRUE;

+}

+

+/*-

+ *-----------------------------------------------------------------------

+ * RegionSetExtents --

+ *	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

+RegionSetExtents (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 = RegionBoxptr(pReg);

+    pBoxEnd = RegionEnd(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

+ *====================================================================*/

+/*-

+ *-----------------------------------------------------------------------

+ * RegionIntersectO --

+ *	Handle an overlapping band for RegionIntersect.

+ *

+ * Results:

+ *	TRUE if successful.

+ *

+ * Side Effects:

+ *	Rectangles may be added to the region.

+ *

+ *-----------------------------------------------------------------------

+ */

+/*ARGSUSED*/

+

+#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

+ *====================================================================*/

+

+/*-

+ *-----------------------------------------------------------------------

+ * RegionUnionO --

+ *	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

+RegionUnionO (

+    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 = RegionTop(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;

+}

+

+/*======================================================================

+ *	    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 (RegionNar(rgn))

+	return RegionBreak (dstrgn);

+    

+    if (!rgn->data && (dstrgn->data == &RegionEmptyData))

+    {

+	dstrgn->extents = rgn->extents;

+	dstrgn->data = NULL;

+	return TRUE;

+    }

+

+    numRects = RegionNumRects(rgn);

+    if (!numRects)

+	return TRUE;

+    prepend = FALSE;

+    size = numRects;

+    dnumRects = RegionNumRects(dstrgn);

+    if (!dnumRects && (size < 200))

+	size = 200; /* XXX pick numbers out of a hat */

+    RECTALLOC(dstrgn, size);

+    old = RegionRects(rgn);

+    if (!dnumRects)

+	dstrgn->extents = rgn->extents;

+    else if (dstrgn->extents.x2 > dstrgn->extents.x1)

+    {

+	BoxPtr first, last;

+

+	first = old;

+	last = RegionBoxptr(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 = RegionBoxptr(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 = RegionBox(dstrgn, numRects);

+	if (dnumRects == 1)

+	    *new = *RegionBoxptr(dstrgn);

+	else

+	    memmove((char *)new,(char *)RegionBoxptr(dstrgn),

+		  dnumRects * sizeof(BoxRec));

+	new = RegionBoxptr(dstrgn);

+    }

+    else

+	new = RegionBoxptr(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 (RegionNar(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(RegionBoxptr(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 = RegionBoxptr(&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 = RegionEnd(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);

+		    *RegionTop(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);

+		*RegionTop(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 (!RegionRectAlloc(&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 = RegionEnd(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, RegionUnionO, 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

+RegionFromRects(int nrects, xRectangle *prect, int ctype)

+{

+    

+    RegionPtr		pRgn;

+    RegDataPtr		pData;

+    BoxPtr		pBox;

+    int        		i;

+    int			x1, y1, x2, y2;

+

+    pRgn = RegionCreate(NullBox, 0);

+    if (RegionNar (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

+	    RegionSetExtents(pRgn);

+    	good(pRgn);

+    }

+    else

+    {

+	free(pData);

+    }

+    return pRgn;

+}

+

+#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

+RegionClipSpans(

+    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 = RegionBoxptr(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;

+}