From 0f834b91a4768673833ab4917e87d86c237bb1a6 Mon Sep 17 00:00:00 2001 From: marha Date: Fri, 23 Mar 2012 10:05:55 +0100 Subject: libX11 xserver fontconfig mesa pixman xkbcomp xkeyboard-config git update 23 Mar 2012 --- xorg-server/dix/region.c | 1166 ++++++++++++++++++++++------------------------ 1 file changed, 553 insertions(+), 613 deletions(-) (limited to 'xorg-server/dix/region.c') diff --git a/xorg-server/dix/region.c b/xorg-server/dix/region.c index 6820c1eac..737d2a861 100644 --- a/xorg-server/dix/region.c +++ b/xorg-server/dix/region.c @@ -202,7 +202,6 @@ if (!(pReg)->data || (((pReg)->data->numRects + (n)) > (pReg)->data->size)) \ assert(pReg->data->numRects<=pReg->data->size); \ } - #define DOWNSIZE(reg,numRects) \ if (((numRects) < ((reg)->data->size >> 1)) && ((reg)->data->size > 50)) \ { \ @@ -215,17 +214,17 @@ if (((numRects) < ((reg)->data->size >> 1)) && ((reg)->data->size > 50)) \ } \ } +BoxRec RegionEmptyBox = { 0, 0, 0, 0 }; +RegDataRec RegionEmptyData = { 0, 0 }; -BoxRec RegionEmptyBox = {0, 0, 0, 0}; -RegDataRec RegionEmptyData = {0, 0}; - -RegDataRec RegionBrokenData = {0, 0}; -static RegionRec RegionBrokenRegion = { { 0, 0, 0, 0 }, &RegionBrokenData }; +RegDataRec RegionBrokenData = { 0, 0 }; +static RegionRec RegionBrokenRegion = { {0, 0, 0, 0}, &RegionBrokenData }; void -InitRegions (void) +InitRegions(void) { - pixman_region_set_static_pointers (&RegionEmptyBox, &RegionEmptyData, &RegionBrokenData); + pixman_region_set_static_pointers(&RegionEmptyBox, &RegionEmptyData, + &RegionBrokenData); } /***************************************************************** @@ -238,22 +237,22 @@ RegionPtr RegionCreate(BoxPtr rect, int size) { RegionPtr pReg; - - pReg = (RegionPtr)malloc(sizeof(RegionRec)); + + pReg = (RegionPtr) malloc(sizeof(RegionRec)); if (!pReg) - return &RegionBrokenRegion; + return &RegionBrokenRegion; + + RegionInit(pReg, rect, size); - RegionInit (pReg, rect, size); - return pReg; } void RegionDestroy(RegionPtr pReg) { - pixman_region_fini (pReg); + pixman_region_fini(pReg); if (pReg != &RegionBrokenRegion) - free(pReg); + free(pReg); } void @@ -268,10 +267,10 @@ RegionPrint(RegionPtr 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); + 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] %d %d %d %d \n", + rects[i].x1, rects[i].y1, rects[i].x2, rects[i].y2); ErrorF("[mi] \n"); } @@ -280,52 +279,48 @@ Bool RegionIsValid(RegionPtr reg) { int i, numRects; - + if ((reg->extents.x1 > reg->extents.x2) || - (reg->extents.y1 > reg->extents.y2)) - return FALSE; + (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))); + 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)); + 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 */ +#endif /* DEBUG */ Bool -RegionBreak (RegionPtr pReg) +RegionBreak(RegionPtr pReg) { - xfreeData (pReg); + xfreeData(pReg); pReg->extents = RegionEmptyBox; pReg->data = &RegionBrokenData; return FALSE; @@ -334,37 +329,33 @@ RegionBreak (RegionPtr pReg) 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; + 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 (!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; + 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; @@ -393,22 +384,23 @@ RegionRectAlloc(RegionPtr pRgn, int n) *----------------------------------------------------------------------- */ _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 */ +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; + if (!numRects) + return curStart; /* * The bands may only be coalesced if the bottom of the previous @@ -416,7 +408,8 @@ RegionCoalesce ( */ pPrevBox = RegionBox(pReg, prevStart); pCurBox = RegionBox(pReg, curStart); - if (pPrevBox->y2 != pCurBox->y1) return curStart; + if (pPrevBox->y2 != pCurBox->y1) + return curStart; /* * Make sure the bands have boxes in the same places. This @@ -427,12 +420,12 @@ RegionCoalesce ( y2 = pCurBox->y2; do { - if ((pPrevBox->x1 != pCurBox->x1) || (pPrevBox->x2 != pCurBox->x2)) { - return curStart; - } - pPrevBox++; - pCurBox++; - numRects--; + if ((pPrevBox->x1 != pCurBox->x1) || (pPrevBox->x2 != pCurBox->x2)) { + return curStart; + } + pPrevBox++; + pCurBox++; + numRects--; } while (numRects); /* @@ -442,14 +435,13 @@ RegionCoalesce ( numRects = curStart - prevStart; pReg->data->numRects -= numRects; do { - pPrevBox--; - pPrevBox->y2 = y2; - numRects--; + pPrevBox--; + pPrevBox->y2 = y2; + numRects--; } while (numRects); return prevStart; } - /* Quicky macro to avoid trivial reject procedure calls to RegionCoalesce */ #define Coalesce(newReg, prevBand, curBand) \ @@ -477,15 +469,10 @@ RegionCoalesce ( */ _X_INLINE static Bool -RegionAppendNonO ( - RegionPtr pReg, - BoxPtr r, - BoxPtr rEnd, - int y1, - int y2) +RegionAppendNonO(RegionPtr pReg, BoxPtr r, BoxPtr rEnd, int y1, int y2) { - BoxPtr pNextRect; - int newRects; + BoxPtr pNextRect; + int newRects; newRects = rEnd - r; @@ -497,9 +484,9 @@ RegionAppendNonO ( pNextRect = RegionTop(pReg); pReg->data->numRects += newRects; do { - assert(r->x1 < r->x2); - ADDRECT(pNextRect, r->x1, y1, r->x2, y2); - r++; + assert(r->x1 < r->x2); + ADDRECT(pNextRect, r->x1, y1, r->x2, y2); + r++; } while (r != rEnd); return TRUE; @@ -554,58 +541,54 @@ RegionAppendNonO ( *----------------------------------------------------------------------- */ -typedef Bool (*OverlapProcPtr)( - RegionPtr pReg, - BoxPtr r1, - BoxPtr r1End, - BoxPtr r2, - BoxPtr r2End, - short y1, - short y2, - Bool *pOverlap); +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) +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; + 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); - + if (RegionNar(reg1) || RegionNar(reg2)) + return RegionBreak(newReg); + /* * Initialization: - * set r1, r2, r1End and r2End appropriately, save the rectangles + * 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. @@ -622,39 +605,38 @@ RegionOp( oldData = NULL; if (((newReg == reg1) && (newSize > 1)) || - ((newReg == reg2) && (numRects > 1))) - { - oldData = newReg->data; - newReg->data = &RegionEmptyData; + ((newReg == reg2) && (numRects > 1))) { + oldData = newReg->data; + newReg->data = &RegionEmptyData; } /* guess at new size */ if (numRects > newSize) - newSize = numRects; + newSize = numRects; newSize <<= 1; if (!newReg->data) - newReg->data = &RegionEmptyData; + newReg->data = &RegionEmptyData; else if (newReg->data->size) - newReg->data->numRects = 0; + newReg->data->numRects = 0; if (newSize > newReg->data->size) - if (!RegionRectAlloc(newReg, newSize)) - return FALSE; + 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 + * 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 + * 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. @@ -665,73 +647,77 @@ RegionOp( * 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; + /* + * 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); @@ -744,40 +730,38 @@ RegionOp( */ 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); + /* 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; + if (!(numRects = newReg->data->numRects)) { + xfreeData(newReg); + newReg->data = &RegionEmptyData; } - else if (numRects == 1) - { - newReg->extents = *RegionBoxptr(newReg); - xfreeData(newReg); - newReg->data = NULL; + else if (numRects == 1) { + newReg->extents = *RegionBoxptr(newReg); + xfreeData(newReg); + newReg->data = NULL; } - else - { - DOWNSIZE(newReg, numRects); + else { + DOWNSIZE(newReg, numRects); } return TRUE; @@ -799,17 +783,16 @@ RegionOp( *----------------------------------------------------------------------- */ static void -RegionSetExtents (RegionPtr pReg) +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; + return; + if (!pReg->data->size) { + pReg->extents.x2 = pReg->extents.x1; + pReg->extents.y2 = pReg->extents.y1; + return; } pBox = RegionBoxptr(pReg); @@ -829,11 +812,11 @@ RegionSetExtents (RegionPtr pReg) 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++; + 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); @@ -855,8 +838,7 @@ RegionSetExtents (RegionPtr pReg) * *----------------------------------------------------------------------- */ -/*ARGSUSED*/ - + /*ARGSUSED*/ #define MERGERECT(r) \ { \ if (r->x1 <= x2) { \ @@ -871,11 +853,9 @@ RegionSetExtents (RegionPtr pReg) } \ r++; \ } - /*====================================================================== * Region Union *====================================================================*/ - /*- *----------------------------------------------------------------------- * RegionUnionO -- @@ -891,60 +871,51 @@ RegionSetExtents (RegionPtr pReg) * *----------------------------------------------------------------------- */ -static Bool -RegionUnionO ( - RegionPtr pReg, - BoxPtr r1, - BoxPtr r1End, - BoxPtr r2, - BoxPtr r2End, - short y1, - short y2, - Bool *pOverlap) + 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; + BoxPtr pNextRect; + int x1; /* left and right side of current union */ + int x2; - assert (y1 < y2); + 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++; + if (r1->x1 < r2->x1) { + x1 = r1->x1; + x2 = r1->x2; + r1++; } - else - { - x1 = r2->x1; - x2 = r2->x2; - r2++; + else { + x1 = r2->x1; + x2 = r2->x2; + r2++; } - while (r1 != r1End && r2 != r2End) - { - if (r1->x1 < r2->x1) MERGERECT(r1) else MERGERECT(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); + if (r1 != r1End) { + do { + MERGERECT(r1); + } while (r1 != r1End); } - else if (r2 != r2End) - { - do - { - MERGERECT(r2); - } while (r2 != r2End); + else if (r2 != r2End) { + do { + MERGERECT(r2); + } while (r2 != r2End); } - + /* Add current rectangle */ NEWRECT(pReg, pNextRect, x1, y1, x2, y2); @@ -980,83 +951,76 @@ RegionAppend(RegionPtr dstrgn, RegionPtr rgn) Bool prepend; if (RegionNar(rgn)) - return RegionBreak (dstrgn); - - if (!rgn->data && (dstrgn->data == &RegionEmptyData)) - { - dstrgn->extents = rgn->extents; - dstrgn->data = NULL; - return TRUE; + 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; + return TRUE; prepend = FALSE; size = numRects; dnumRects = RegionNumRects(dstrgn); if (!dnumRects && (size < 200)) - size = 200; /* XXX pick numbers out of a hat */ + 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; - } + 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); + 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; + new = RegionBoxptr(dstrgn) + dnumRects; if (numRects == 1) - *new = *old; + *new = *old; else - memmove((char *)new, (char *)old, numRects * sizeof(BoxRec)); + memmove((char *) new, (char *) old, numRects * sizeof(BoxRec)); dstrgn->data->numRects += numRects; return TRUE; } - #define ExchangeRects(a, b) \ { \ BoxRec t; \ @@ -1066,60 +1030,53 @@ RegionAppend(RegionPtr dstrgn, RegionPtr rgn) } static void -QuickSortRects( - BoxRec rects[], - int numRects) +QuickSortRects(BoxRec rects[], int numRects) { - int y1; - int x1; - int i, j; - BoxPtr r; + 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 */ + 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; + y1 = rects[0].y1; + x1 = rects[0].x1; /* Partition array */ i = 0; j = numRects; - do - { - r = &(rects[i]); - do - { - r++; - i++; + 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--; + (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); + 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); + /* Recurse */ + if (numRects - j - 1 > 1) + QuickSortRects(&rects[j + 1], numRects - j - 1); numRects = j; } while (numRects > 1); } @@ -1161,51 +1118,46 @@ RegionValidate(RegionPtr badreg, Bool *pOverlap) { /* Descriptor for regions under construction in Step 2. */ typedef struct { - RegionRec reg; - int prevBand; - int curBand; + 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; + 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; + if (!badreg->data) { + good(badreg); + return TRUE; } numRects = badreg->data->numRects; - if (!numRects) - { - if (RegionNar(badreg)) - return FALSE; - good(badreg); - return TRUE; + 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; + 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 */ @@ -1217,7 +1169,7 @@ RegionValidate(RegionPtr badreg, Bool *pOverlap) /* 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); + return RegionBreak(badreg); sizeRI = 4; numRI = 1; ri[0].prevBand = 0; @@ -1233,193 +1185,181 @@ RegionValidate(RegionPtr badreg, Bool *pOverlap) 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 */ + 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; - } + 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; + 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: + bail: for (i = 0; i < numRI; i++) - xfreeData(&ri[i].reg); + xfreeData(&ri[i].reg); free(ri); - return RegionBreak (badreg); + return RegionBreak(badreg); } RegionPtr RegionFromRects(int nrects, xRectangle *prect, int ctype) { - - RegionPtr pRgn; - RegDataPtr pData; - BoxPtr pBox; - int i; - int x1, y1, x2, y2; + + RegionPtr pRgn; + RegDataPtr pData; + BoxPtr pBox; + int i; + int x1, y1, x2, y2; pRgn = RegionCreate(NullBox, 0); - if (RegionNar (pRgn)) - return pRgn; + 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; + 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; + 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++; - } + 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); + 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); + else { + free(pData); } return pRgn; } -- cgit v1.2.3