#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; \
} \
}
#else
#define assert(expr)
#endif
#define good(reg) assert(RegionIsValid(reg))
#define EXTENTCHECK(r1,r2) \
(!( ((r1)->x2 <= (r2)->x1) || \
((r1)->x1 >= (r2)->x2) || \
((r1)->y2 <= (r2)->y1) || \
((r1)->y1 >= (r2)->y2) ) )
#define INBOX(r,x,y) \
( ((r)->x2 > x) && \
((r)->x1 <= x) && \
((r)->y2 > y) && \
((r)->y1 <= y) )
#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);
}
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
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)
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;
}
_X_INLINE static int
RegionCoalesce (
RegionPtr pReg,
int prevStart,
int curStart)
{
BoxPtr pPrevBox;
BoxPtr pCurBox;
int numRects;
int y2;
numRects = curStart - prevStart;
assert(numRects == pReg->data->numRects - curStart);
if (!numRects) return curStart;
pPrevBox = RegionBox(pReg, prevStart);
pCurBox = RegionBox(pReg, curStart);
if (pPrevBox->y2 != pCurBox->y1) return curStart;
y2 = pCurBox->y2;
do {
if ((pPrevBox->x1 != pCurBox->x1) || (pPrevBox->x2 != pCurBox->x2)) {
return curStart;
}
pPrevBox++;
pCurBox++;
numRects--;
} while (numRects);
numRects = curStart - prevStart;
pReg->data->numRects -= numRects;
do {
pPrevBox--;
pPrevBox->y2 = y2;
numRects--;
} while (numRects);
return prevStart;
}
#define Coalesce(newReg, prevBand, curBand) \
if (curBand - prevBand == newReg->data->numRects - curBand) { \
prevBand = RegionCoalesce(newReg, prevBand, curBand); \
} else { \
prevBand = curBand; \
}
_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);
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; \
} \
}
typedef Bool (*OverlapProcPtr)(
RegionPtr pReg,
BoxPtr r1,
BoxPtr r1End,
BoxPtr r2,
BoxPtr r2End,
short y1,
short y2,
Bool *pOverlap);
static Bool
RegionOp(
RegionPtr newReg,
RegionPtr reg1,
RegionPtr reg2,
OverlapProcPtr overlapFunc,
Bool appendNon1,
Bool appendNon2,
Bool *pOverlap)
{
BoxPtr r1;
BoxPtr r2;
BoxPtr r1End;
BoxPtr r2End;
short ybot;
short ytop;
RegDataPtr oldData;
int prevBand;
int curBand;
BoxPtr r1BandEnd;
BoxPtr r2BandEnd;
short top;
short bot;
int r1y1;
int r2y1;
int newSize;
int numRects;
if (RegionNar (reg1) || RegionNar(reg2))
return RegionBreak (newReg);
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;
}
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;
ybot = min(r1->y1, r2->y1);
prevBand = 0;
do {
assert(r1 != r1End);
assert(r2 != r2End);
FindBand(r1, r1BandEnd, r1End, r1y1);
FindBand(r2, r2BandEnd, r2End, r2y1);
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;
}
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 (r1->y2 == ybot) r1 = r1BandEnd;
if (r2->y2 == ybot) r2 = r2BandEnd;
} while (r1 != r1End && r2 != r2End);
if ((r1 != r1End) && appendNon1) {
FindBand(r1, r1BandEnd, r1End, r1y1);
curBand = newReg->data->numRects;
RegionAppendNonO(newReg, r1, r1BandEnd, max(r1y1, ybot), r1->y2);
Coalesce(newReg, prevBand, curBand);
AppendRegions(newReg, r1BandEnd, r1End);
} else if ((r2 != r2End) && appendNon2) {
FindBand(r2, r2BandEnd, r2End, r2y1);
curBand = newReg->data->numRects;
RegionAppendNonO(newReg, r2, r2BandEnd, max(r2y1, ybot), r2->y2);
Coalesce(newReg, prevBand, curBand);
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;
}
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);
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);
}
#define MERGERECT(r) \
{ \
if (r->x1 <= x2) { \
\
if (r->x1 < x2) *pOverlap = TRUE; \
if (x2 < r->x2) x2 = r->x2; \
} else { \
\
NEWRECT(pReg, pNextRect, x1, y1, x2, y2); \
x1 = r->x1; \
x2 = r->x2; \
} \
r++; \
}
static Bool
RegionUnionO (
RegionPtr pReg,
BoxPtr r1,
BoxPtr r1End,
BoxPtr r2,
BoxPtr r2End,
short y1,
short y2,
Bool *pOverlap)
{
BoxPtr pNextRect;
int x1;
int x2;
assert (y1 < y2);
assert(r1 != r1End && r2 != r2End);
pNextRect = RegionTop(pReg);
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);
}
if (r1 != r1End)
{
do
{
MERGERECT(r1);
} while (r1 != r1End);
}
else if (r2 != r2End)
{
do
{
MERGERECT(r2);
} while (r2 != r2End);
}
NEWRECT(pReg, pNextRect, x1, y1, x2, y2);
return TRUE;
}
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;
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;
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;
}
ExchangeRects(0, numRects >> 1);
y1 = rects[0].y1;
x1 = rects[0].x1;
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);
ExchangeRects(0, j);
if (numRects-j-1 > 1)
QuickSortRects(&rects[j+1], numRects-j-1);
numRects = j;
} while (numRects > 1);
}
Bool
RegionValidate(RegionPtr badreg, Bool *pOverlap)
{
typedef struct {
RegionRec reg;
int prevBand;
int curBand;
} RegionInfo;
int numRects;
RegionInfo *ri;
int numRI;
int sizeRI;
int i;
int j;
RegionInfo *rit;
RegionPtr reg;
BoxPtr box;
BoxPtr riBox;
RegionPtr hreg;
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;
}
QuickSortRects(RegionBoxptr(badreg), numRects);
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;
for (i = numRects; --i > 0;)
{
box++;
for (j = numRI, rit = ri; --j >= 0; rit++)
{
reg = &rit->reg;
riBox = RegionEnd(reg);
if (box->y1 == riBox->y1 && box->y2 == riBox->y2)
{
if (box->x1 <= riBox->x2)
{
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;
}
else if (box->y1 >= riBox->y2)
{
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;
}
}
if (sizeRI == numRI)
{
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))
goto bail;
NextRect: ;
}
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)
{
xfreeData(reg);
reg->data = NULL;
}
}
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;
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; \
}
static void QuickSortSpans(
DDXPointRec spans[],
int widths[],
int numSpans)
{
int y;
int i, j, m;
DDXPointPtr r;
do
{
if (numSpans < 9)
{
int yprev;
yprev = spans[0].y;
i = 1;
do
{
y = spans[i].y;
if (yprev > y)
{
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;
}
yprev = y;
i++;
} while (i != numSpans);
return;
}
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;
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);
ExchangeSpans(0, j);
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++) {} \
}
int
RegionClipSpans(
RegionPtr prgnDst,
DDXPointPtr ppt,
int *pwidth,
int nspans,
DDXPointPtr pptNew,
int *pwidthNew,
int fSorted)
{
DDXPointPtr pptLast;
int *pwidthNewStart;
int y, x1, x2;
int numRects;
good(prgnDst);
pptLast = ppt + nspans;
pwidthNewStart = pwidthNew;
if (!prgnDst->data)
{
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)
{
pptNew->x = x1;
pptNew->y = y;
*pwidthNew = x2 - x1;
pptNew++;
pwidthNew++;
}
}
}
}
else if ((numRects = prgnDst->data->numRects))
{
BoxPtr pboxBandStart, pboxBandEnd;
BoxPtr pbox;
BoxPtr pboxLast;
int clipy1, clipy2;
if ((! fSorted) && (nspans > 1))
QuickSortSpans(ppt, pwidth, nspans);
pboxBandStart = RegionBoxptr(prgnDst);
pboxLast = pboxBandStart + numRects;
NextBand();
for (; ppt != pptLast; )
{
y = ppt->y;
if (y < clipy2)
{
pbox = pboxBandStart;
x1 = ppt->x;
x2 = x1 + *pwidth;
do
{
int newx1, newx2;
newx1 = x1;
newx2 = x2;
if (newx1 < pbox->x1) newx1 = pbox->x1;
if (newx2 > pbox->x2) newx2 = pbox->x2;
if (newx1 < newx2)
{
pptNew->x = newx1;
pptNew->y = y;
*pwidthNew = newx2 - newx1;
pptNew++;
pwidthNew++;
}
pbox++;
} while (pbox != pboxBandEnd);
ppt++;
pwidth++;
}
else
{
pboxBandStart = pboxBandEnd;
if (pboxBandStart == pboxLast)
break;
NextBand();
}
}
}
return pwidthNew - pwidthNewStart;
}