summaryrefslogtreecommitdiff
path: root/dix/region.c
diff options
context:
space:
mode:
Diffstat (limited to 'dix/region.c')
-rw-r--r--dix/region.c578
1 files changed, 0 insertions, 578 deletions
diff --git a/dix/region.c b/dix/region.c
index 5ba345773..79420822d 100644
--- a/dix/region.c
+++ b/dix/region.c
@@ -564,225 +564,6 @@ typedef Bool (*OverlapProcPtr)(
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 --
@@ -873,85 +654,6 @@ RegionSetExtents (RegionPtr pReg)
}
/*======================================================================
- * 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
*====================================================================*/
@@ -1065,286 +767,6 @@ RegionAppend(RegionPtr dstrgn, RegionPtr rgn)
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)
{
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-22 07:31:06 +0000