1 /***********************************************************
3 Copyright 1987, 1988, 1989, 1998 The Open Group
5 Permission to use, copy, modify, distribute, and sell this software and its
6 documentation for any purpose is hereby granted without fee, provided that
7 the above copyright notice appear in all copies and that both that
8 copyright notice and this permission notice appear in supporting
11 The above copyright notice and this permission notice shall be included in
12 all copies or substantial portions of the Software.
14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
18 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
19 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
21 Except as contained in this notice, the name of The Open Group shall not be
22 used in advertising or otherwise to promote the sale, use or other dealings
23 in this Software without prior written authorization from The Open Group.
25 Copyright 1987, 1988, 1989 by
26 Digital Equipment Corporation, Maynard, Massachusetts.
30 Permission to use, copy, modify, and distribute this software and its
31 documentation for any purpose and without fee is hereby granted,
32 provided that the above copyright notice appear in all copies and that
33 both that copyright notice and this permission notice appear in
34 supporting documentation, and that the name of Digital not be
35 used in advertising or publicity pertaining to distribution of the
36 software without specific, written prior permission.
38 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
39 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
40 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
41 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
42 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
43 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
46 ******************************************************************/
53 #define PIXREGION_NIL(reg) ((reg)->data && !(reg)->data->numRects)
55 #define PIXREGION_NAR(reg) ((reg)->data == pixman_brokendata)
56 #define PIXREGION_NUM_RECTS(reg) ((reg)->data ? (reg)->data->numRects : 1)
57 #define PIXREGION_SIZE(reg) ((reg)->data ? (reg)->data->size : 0)
58 #define PIXREGION_RECTS(reg) ((reg)->data ? (box_type_t *)((reg)->data + 1) \
60 #define PIXREGION_BOXPTR(reg) ((box_type_t *)((reg)->data + 1))
61 #define PIXREGION_BOX(reg,i) (&PIXREGION_BOXPTR(reg)[i])
62 #define PIXREGION_TOP(reg) PIXREGION_BOX(reg, (reg)->data->numRects)
63 #define PIXREGION_END(reg) PIXREGION_BOX(reg, (reg)->data->numRects - 1)
67 #ifdef DEBUG_PIXREGION
68 #define assert(expr) {if (!(expr)) \
69 FatalError("Assertion failed file %s, line %d: expr\n", \
70 __FILE__, __LINE__); }
75 #define good(reg) assert(PREFIX(_selfcheck) (reg))
78 #define MIN(a,b) ((a) < (b) ? (a) : (b))
80 #define MAX(a,b) ((a) > (b) ? (a) : (b))
82 static const box_type_t PREFIX(_emptyBox_) = {0, 0, 0, 0};
83 static const region_data_type_t PREFIX(_emptyData_) = {0, 0};
84 static const region_data_type_t PREFIX(_brokendata_) = {0, 0};
86 static box_type_t *pixman_region_emptyBox = (box_type_t *)&PREFIX(_emptyBox_);
87 static region_data_type_t *pixman_region_emptyData = (region_data_type_t *)&PREFIX(_emptyData_);
88 static region_data_type_t *pixman_brokendata = (region_data_type_t *)&PREFIX(_brokendata_);
90 /* This function exists only to make it possible to preserve the X ABI - it should
91 * go away at first opportunity.
93 * The problem is that the X ABI exports the three structs and has used
94 * them through macros. So the X server calls this function with
95 * the addresses of those structs which makes the existing code continue to
99 PREFIX(_set_static_pointers) (box_type_t *empty_box,
100 region_data_type_t *empty_data,
101 region_data_type_t *broken_data)
103 pixman_region_emptyBox = empty_box;
104 pixman_region_emptyData = empty_data;
105 pixman_brokendata = broken_data;
109 pixman_break (region_type_t *pReg);
112 * The functions in this file implement the Region abstraction used extensively
113 * throughout the X11 sample server. A Region is simply a set of disjoint
114 * (non-overlapping) rectangles, plus an "extent" rectangle which is the
115 * smallest single rectangle that contains all the non-overlapping rectangles.
117 * A Region is implemented as a "y-x-banded" array of rectangles. This array
118 * imposes two degrees of order. First, all rectangles are sorted by top side
119 * y coordinate first (y1), and then by left side x coordinate (x1).
121 * Furthermore, the rectangles are grouped into "bands". Each rectangle in a
122 * band has the same top y coordinate (y1), and each has the same bottom y
123 * coordinate (y2). Thus all rectangles in a band differ only in their left
124 * and right side (x1 and x2). Bands are implicit in the array of rectangles:
125 * there is no separate list of band start pointers.
127 * The y-x band representation does not minimize rectangles. In particular,
128 * if a rectangle vertically crosses a band (the rectangle has scanlines in
129 * the y1 to y2 area spanned by the band), then the rectangle may be broken
130 * down into two or more smaller rectangles stacked one atop the other.
132 * ----------- -----------
134 * | | -------- ----------- --------
135 * | | | | in y-x banded | | | | band 1
136 * | | | | form is | | | |
137 * ----------- | | ----------- --------
141 * An added constraint on the rectangles is that they must cover as much
142 * horizontal area as possible: no two rectangles within a band are allowed
145 * Whenever possible, bands will be merged together to cover a greater vertical
146 * distance (and thus reduce the number of rectangles). Two bands can be merged
147 * only if the bottom of one touches the top of the other and they have
148 * rectangles in the same places (of the same width, of course).
150 * Adam de Boor wrote most of the original region code. Joel McCormack
151 * substantially modified or rewrote most of the core arithmetic routines, and
152 * added pixman_region_validate in order to support several speed improvements to
153 * pixman_region_validateTree. Bob Scheifler changed the representation to be more
154 * compact when empty or a single rectangle, and did a bunch of gratuitous
155 * reformatting. Carl Worth did further gratuitous reformatting while re-merging
156 * the server and client region code into libpixregion.
159 /* true iff two Boxes overlap */
160 #define EXTENTCHECK(r1,r2) \
161 (!( ((r1)->x2 <= (r2)->x1) || \
162 ((r1)->x1 >= (r2)->x2) || \
163 ((r1)->y2 <= (r2)->y1) || \
164 ((r1)->y1 >= (r2)->y2) ) )
166 /* true iff (x,y) is in Box */
167 #define INBOX(r,x,y) \
173 /* true iff Box r1 contains Box r2 */
174 #define SUBSUMES(r1,r2) \
175 ( ((r1)->x1 <= (r2)->x1) && \
176 ((r1)->x2 >= (r2)->x2) && \
177 ((r1)->y1 <= (r2)->y1) && \
178 ((r1)->y2 >= (r2)->y2) )
181 PIXREGION_SZOF(size_t n)
183 size_t size = n * sizeof(box_type_t);
184 if (n > UINT32_MAX / sizeof(box_type_t))
187 if (sizeof(region_data_type_t) > UINT32_MAX - size)
190 return size + sizeof(region_data_type_t);
196 size_t sz = PIXREGION_SZOF(n);
203 #define freeData(reg) if ((reg)->data && (reg)->data->size) free((reg)->data)
205 #define RECTALLOC_BAIL(pReg,n,bail) \
206 if (!(pReg)->data || (((pReg)->data->numRects + (n)) > (pReg)->data->size)) \
207 if (!pixman_rect_alloc(pReg, n)) { goto bail; }
209 #define RECTALLOC(pReg,n) \
210 if (!(pReg)->data || (((pReg)->data->numRects + (n)) > (pReg)->data->size)) \
211 if (!pixman_rect_alloc(pReg, n)) { return FALSE; }
213 #define ADDRECT(pNextRect,nx1,ny1,nx2,ny2) \
215 pNextRect->x1 = nx1; \
216 pNextRect->y1 = ny1; \
217 pNextRect->x2 = nx2; \
218 pNextRect->y2 = ny2; \
222 #define NEWRECT(pReg,pNextRect,nx1,ny1,nx2,ny2) \
224 if (!(pReg)->data || ((pReg)->data->numRects == (pReg)->data->size))\
226 if (!pixman_rect_alloc(pReg, 1)) \
228 pNextRect = PIXREGION_TOP(pReg); \
230 ADDRECT(pNextRect,nx1,ny1,nx2,ny2); \
231 pReg->data->numRects++; \
232 assert(pReg->data->numRects<=pReg->data->size); \
235 #define DOWNSIZE(reg,numRects) \
236 if (((numRects) < ((reg)->data->size >> 1)) && ((reg)->data->size > 50)) \
238 region_data_type_t * NewData; \
239 size_t data_size = PIXREGION_SZOF(numRects); \
243 NewData = (region_data_type_t *)realloc((reg)->data, data_size); \
246 NewData->size = (numRects); \
247 (reg)->data = NewData; \
252 PREFIX(_equal) (reg1, reg2)
253 region_type_t * reg1;
254 region_type_t * reg2;
260 if (reg1->extents.x1 != reg2->extents.x1) return FALSE;
261 if (reg1->extents.x2 != reg2->extents.x2) return FALSE;
262 if (reg1->extents.y1 != reg2->extents.y1) return FALSE;
263 if (reg1->extents.y2 != reg2->extents.y2) return FALSE;
264 if (PIXREGION_NUM_RECTS(reg1) != PIXREGION_NUM_RECTS(reg2)) return FALSE;
266 rects1 = PIXREGION_RECTS(reg1);
267 rects2 = PIXREGION_RECTS(reg2);
268 for (i = 0; i != PIXREGION_NUM_RECTS(reg1); i++) {
269 if (rects1[i].x1 != rects2[i].x1) return FALSE;
270 if (rects1[i].x2 != rects2[i].x2) return FALSE;
271 if (rects1[i].y1 != rects2[i].y1) return FALSE;
272 if (rects1[i].y2 != rects2[i].y2) return FALSE;
285 num = PIXREGION_NUM_RECTS(rgn);
286 size = PIXREGION_SIZE(rgn);
287 rects = PIXREGION_RECTS(rgn);
288 fprintf(stderr, "num: %d size: %d\n", num, size);
289 fprintf(stderr, "extents: %d %d %d %d\n",
290 rgn->extents.x1, rgn->extents.y1, rgn->extents.x2, rgn->extents.y2);
291 for (i = 0; i < num; i++)
292 fprintf(stderr, "%d %d %d %d \n",
293 rects[i].x1, rects[i].y1, rects[i].x2, rects[i].y2);
294 fprintf(stderr, "\n");
300 PREFIX(_init) (region_type_t *region)
302 region->extents = *pixman_region_emptyBox;
303 region->data = pixman_region_emptyData;
307 PREFIX(_init_rect) (region_type_t *region,
308 int x, int y, unsigned int width, unsigned int height)
310 region->extents.x1 = x;
311 region->extents.y1 = y;
312 region->extents.x2 = x + width;
313 region->extents.y2 = y + height;
318 PREFIX(_init_with_extents) (region_type_t *region, box_type_t *extents)
320 region->extents = *extents;
325 PREFIX(_fini) (region_type_t *region)
332 PREFIX(_n_rects) (region_type_t *region)
334 return PIXREGION_NUM_RECTS (region);
337 PIXMAN_EXPORT box_type_t *
338 PREFIX(_rectangles) (region_type_t *region,
342 *n_rects = PIXREGION_NUM_RECTS (region);
344 return PIXREGION_RECTS (region);
348 pixman_break (region_type_t *region)
351 region->extents = *pixman_region_emptyBox;
352 region->data = pixman_brokendata;
357 pixman_rect_alloc (region_type_t * region, int n)
359 region_data_type_t *data;
364 region->data = allocData(n);
366 return pixman_break (region);
367 region->data->numRects = 1;
368 *PIXREGION_BOXPTR(region) = region->extents;
370 else if (!region->data->size)
372 region->data = allocData(n);
374 return pixman_break (region);
375 region->data->numRects = 0;
382 n = region->data->numRects;
383 if (n > 500) /* XXX pick numbers out of a hat */
386 n += region->data->numRects;
387 data_size = PIXREGION_SZOF(n);
391 data = (region_data_type_t *)realloc(region->data, PIXREGION_SZOF(n));
393 return pixman_break (region);
396 region->data->size = n;
400 PIXMAN_EXPORT pixman_bool_t
401 PREFIX(_copy) (region_type_t *dst, region_type_t *src)
407 dst->extents = src->extents;
408 if (!src->data || !src->data->size)
411 dst->data = src->data;
414 if (!dst->data || (dst->data->size < src->data->numRects))
417 dst->data = allocData(src->data->numRects);
419 return pixman_break (dst);
420 dst->data->size = src->data->numRects;
422 dst->data->numRects = src->data->numRects;
423 memmove((char *)PIXREGION_BOXPTR(dst),(char *)PIXREGION_BOXPTR(src),
424 dst->data->numRects * sizeof(box_type_t));
428 /*======================================================================
429 * Generic Region Operator
430 *====================================================================*/
433 *-----------------------------------------------------------------------
435 * Attempt to merge the boxes in the current band with those in the
436 * previous one. We are guaranteed that the current band extends to
437 * the end of the rects array. Used only by pixman_op.
440 * The new index for the previous band.
443 * If coalescing takes place:
444 * - rectangles in the previous band will have their y2 fields
446 * - region->data->numRects will be decreased.
448 *-----------------------------------------------------------------------
452 region_type_t * region, /* Region to coalesce */
453 int prevStart, /* Index of start of previous band */
454 int curStart) /* Index of start of current band */
456 box_type_t * pPrevBox; /* Current box in previous band */
457 box_type_t * pCurBox; /* Current box in current band */
458 int numRects; /* Number rectangles in both bands */
459 int y2; /* Bottom of current band */
461 * Figure out how many rectangles are in the band.
463 numRects = curStart - prevStart;
464 assert(numRects == region->data->numRects - curStart);
466 if (!numRects) return curStart;
469 * The bands may only be coalesced if the bottom of the previous
470 * matches the top scanline of the current.
472 pPrevBox = PIXREGION_BOX(region, prevStart);
473 pCurBox = PIXREGION_BOX(region, curStart);
474 if (pPrevBox->y2 != pCurBox->y1) return curStart;
477 * Make sure the bands have boxes in the same places. This
478 * assumes that boxes have been added in such a way that they
479 * cover the most area possible. I.e. two boxes in a band must
480 * have some horizontal space between them.
485 if ((pPrevBox->x1 != pCurBox->x1) || (pPrevBox->x2 != pCurBox->x2)) {
494 * The bands may be merged, so set the bottom y of each box
495 * in the previous band to the bottom y of the current band.
497 numRects = curStart - prevStart;
498 region->data->numRects -= numRects;
507 /* Quicky macro to avoid trivial reject procedure calls to pixman_coalesce */
509 #define Coalesce(newReg, prevBand, curBand) \
510 if (curBand - prevBand == newReg->data->numRects - curBand) { \
511 prevBand = pixman_coalesce(newReg, prevBand, curBand); \
513 prevBand = curBand; \
517 *-----------------------------------------------------------------------
518 * pixman_region_appendNonO --
519 * Handle a non-overlapping band for the union and subtract operations.
520 * Just adds the (top/bottom-clipped) rectangles into the region.
521 * Doesn't have to check for subsumption or anything.
527 * region->data->numRects is incremented and the rectangles overwritten
528 * with the rectangles we're passed.
530 *-----------------------------------------------------------------------
533 static inline pixman_bool_t
534 pixman_region_appendNonO (
535 region_type_t * region,
541 box_type_t * pNextRect;
547 assert(newRects != 0);
549 /* Make sure we have enough space for all rectangles to be added */
550 RECTALLOC(region, newRects);
551 pNextRect = PIXREGION_TOP(region);
552 region->data->numRects += newRects;
554 assert(r->x1 < r->x2);
555 ADDRECT(pNextRect, r->x1, y1, r->x2, y2);
562 #define FindBand(r, rBandEnd, rEnd, ry1) \
566 while ((rBandEnd != rEnd) && (rBandEnd->y1 == ry1)) { \
571 #define AppendRegions(newReg, r, rEnd) \
574 if ((newRects = rEnd - r)) { \
575 RECTALLOC(newReg, newRects); \
576 memmove((char *)PIXREGION_TOP(newReg),(char *)r, \
577 newRects * sizeof(box_type_t)); \
578 newReg->data->numRects += newRects; \
583 *-----------------------------------------------------------------------
585 * Apply an operation to two regions. Called by pixman_region_union, pixman_region_inverse,
586 * pixman_region_subtract, pixman_region_intersect.... Both regions MUST have at least one
587 * rectangle, and cannot be the same object.
590 * TRUE if successful.
593 * The new region is overwritten.
594 * pOverlap set to TRUE if overlapFunc ever returns TRUE.
597 * The idea behind this function is to view the two regions as sets.
598 * Together they cover a rectangle of area that this function divides
599 * into horizontal bands where points are covered only by one region
600 * or by both. For the first case, the nonOverlapFunc is called with
601 * each the band and the band's upper and lower extents. For the
602 * second, the overlapFunc is called to process the entire band. It
603 * is responsible for clipping the rectangles in the band, though
604 * this function provides the boundaries.
605 * At the end of each band, the new region is coalesced, if possible,
606 * to reduce the number of rectangles in the region.
608 *-----------------------------------------------------------------------
611 typedef pixman_bool_t (*OverlapProcPtr)(
612 region_type_t *region,
623 region_type_t *newReg, /* Place to store result */
624 region_type_t * reg1, /* First region in operation */
625 region_type_t * reg2, /* 2d region in operation */
626 OverlapProcPtr overlapFunc, /* Function to call for over-
628 int appendNon1, /* Append non-overlapping bands */
630 int appendNon2, /* Append non-overlapping bands */
634 box_type_t * r1; /* Pointer into first region */
635 box_type_t * r2; /* Pointer into 2d region */
636 box_type_t * r1End; /* End of 1st region */
637 box_type_t * r2End; /* End of 2d region */
638 int ybot; /* Bottom of intersection */
639 int ytop; /* Top of intersection */
640 region_data_type_t * oldData; /* Old data for newReg */
641 int prevBand; /* Index of start of
642 * previous band in newReg */
643 int curBand; /* Index of start of current
645 box_type_t * r1BandEnd; /* End of current band in r1 */
646 box_type_t * r2BandEnd; /* End of current band in r2 */
647 int top; /* Top of non-overlapping band */
648 int bot; /* Bottom of non-overlapping band*/
649 int r1y1; /* Temps for r1->y1 and r2->y1 */
655 * Break any region computed from a broken region
657 if (PIXREGION_NAR (reg1) || PIXREGION_NAR(reg2))
658 return pixman_break (newReg);
662 * set r1, r2, r1End and r2End appropriately, save the rectangles
663 * of the destination region until the end in case it's one of
664 * the two source regions, then mark the "new" region empty, allocating
665 * another array of rectangles for it to use.
668 r1 = PIXREGION_RECTS(reg1);
669 newSize = PIXREGION_NUM_RECTS(reg1);
670 r1End = r1 + newSize;
671 numRects = PIXREGION_NUM_RECTS(reg2);
672 r2 = PIXREGION_RECTS(reg2);
673 r2End = r2 + numRects;
677 oldData = (region_data_type_t *)NULL;
678 if (((newReg == reg1) && (newSize > 1)) ||
679 ((newReg == reg2) && (numRects > 1)))
681 oldData = newReg->data;
682 newReg->data = pixman_region_emptyData;
684 /* guess at new size */
685 if (numRects > newSize)
689 newReg->data = pixman_region_emptyData;
690 else if (newReg->data->size)
691 newReg->data->numRects = 0;
692 if (newSize > newReg->data->size) {
693 if (!pixman_rect_alloc(newReg, newSize)) {
702 * In the upcoming loop, ybot and ytop serve different functions depending
703 * on whether the band being handled is an overlapping or non-overlapping
705 * In the case of a non-overlapping band (only one of the regions
706 * has points in the band), ybot is the bottom of the most recent
707 * intersection and thus clips the top of the rectangles in that band.
708 * ytop is the top of the next intersection between the two regions and
709 * serves to clip the bottom of the rectangles in the current band.
710 * For an overlapping band (where the two regions intersect), ytop clips
711 * the top of the rectangles of both regions and ybot clips the bottoms.
714 ybot = MIN(r1->y1, r2->y1);
717 * prevBand serves to mark the start of the previous band so rectangles
718 * can be coalesced into larger rectangles. qv. pixman_coalesce, above.
719 * In the beginning, there is no previous band, so prevBand == curBand
720 * (curBand is set later on, of course, but the first band will always
721 * start at index 0). prevBand and curBand must be indices because of
722 * the possible expansion, and resultant moving, of the new region's
723 * array of rectangles.
729 * This algorithm proceeds one source-band (as opposed to a
730 * destination band, which is determined by where the two regions
731 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
732 * rectangle after the last one in the current band for their
733 * respective regions.
738 FindBand(r1, r1BandEnd, r1End, r1y1);
739 FindBand(r2, r2BandEnd, r2End, r2y1);
742 * First handle the band that doesn't intersect, if any.
744 * Note that attention is restricted to one band in the
745 * non-intersecting region at once, so if a region has n
746 * bands between the current position and the next place it overlaps
747 * the other, this entire loop will be passed through n times.
751 top = MAX(r1y1, ybot);
752 bot = MIN(r1->y2, r2y1);
754 curBand = newReg->data->numRects;
755 pixman_region_appendNonO(newReg, r1, r1BandEnd, top, bot);
756 Coalesce(newReg, prevBand, curBand);
760 } else if (r2y1 < r1y1) {
762 top = MAX(r2y1, ybot);
763 bot = MIN(r2->y2, r1y1);
765 curBand = newReg->data->numRects;
766 pixman_region_appendNonO(newReg, r2, r2BandEnd, top, bot);
767 Coalesce(newReg, prevBand, curBand);
776 * Now see if we've hit an intersecting band. The two bands only
777 * intersect if ybot > ytop
779 ybot = MIN(r1->y2, r2->y2);
781 curBand = newReg->data->numRects;
782 (* overlapFunc)(newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot,
784 Coalesce(newReg, prevBand, curBand);
788 * If we've finished with a band (y2 == ybot) we skip forward
789 * in the region to the next band.
791 if (r1->y2 == ybot) r1 = r1BandEnd;
792 if (r2->y2 == ybot) r2 = r2BandEnd;
794 } while (r1 != r1End && r2 != r2End);
797 * Deal with whichever region (if any) still has rectangles left.
799 * We only need to worry about banding and coalescing for the very first
800 * band left. After that, we can just group all remaining boxes,
801 * regardless of how many bands, into one final append to the list.
804 if ((r1 != r1End) && appendNon1) {
805 /* Do first nonOverlap1Func call, which may be able to coalesce */
806 FindBand(r1, r1BandEnd, r1End, r1y1);
807 curBand = newReg->data->numRects;
808 pixman_region_appendNonO(newReg, r1, r1BandEnd, MAX(r1y1, ybot), r1->y2);
809 Coalesce(newReg, prevBand, curBand);
810 /* Just append the rest of the boxes */
811 AppendRegions(newReg, r1BandEnd, r1End);
813 } else if ((r2 != r2End) && appendNon2) {
814 /* Do first nonOverlap2Func call, which may be able to coalesce */
815 FindBand(r2, r2BandEnd, r2End, r2y1);
816 curBand = newReg->data->numRects;
817 pixman_region_appendNonO(newReg, r2, r2BandEnd, MAX(r2y1, ybot), r2->y2);
818 Coalesce(newReg, prevBand, curBand);
819 /* Append rest of boxes */
820 AppendRegions(newReg, r2BandEnd, r2End);
826 if (!(numRects = newReg->data->numRects))
829 newReg->data = pixman_region_emptyData;
831 else if (numRects == 1)
833 newReg->extents = *PIXREGION_BOXPTR(newReg);
835 newReg->data = (region_data_type_t *)NULL;
839 DOWNSIZE(newReg, numRects);
846 *-----------------------------------------------------------------------
847 * pixman_set_extents --
848 * Reset the extents of a region to what they should be. Called by
849 * pixman_region_subtract and pixman_region_intersect as they can't figure it out along the
850 * way or do so easily, as pixman_region_union can.
856 * The region's 'extents' structure is overwritten.
858 *-----------------------------------------------------------------------
861 pixman_set_extents (region_type_t *region)
863 box_type_t *box, *boxEnd;
867 if (!region->data->size)
869 region->extents.x2 = region->extents.x1;
870 region->extents.y2 = region->extents.y1;
874 box = PIXREGION_BOXPTR(region);
875 boxEnd = PIXREGION_END(region);
878 * Since box is the first rectangle in the region, it must have the
879 * smallest y1 and since boxEnd is the last rectangle in the region,
880 * it must have the largest y2, because of banding. Initialize x1 and
881 * x2 from box and boxEnd, resp., as good things to initialize them
884 region->extents.x1 = box->x1;
885 region->extents.y1 = box->y1;
886 region->extents.x2 = boxEnd->x2;
887 region->extents.y2 = boxEnd->y2;
889 assert(region->extents.y1 < region->extents.y2);
890 while (box <= boxEnd) {
891 if (box->x1 < region->extents.x1)
892 region->extents.x1 = box->x1;
893 if (box->x2 > region->extents.x2)
894 region->extents.x2 = box->x2;
898 assert(region->extents.x1 < region->extents.x2);
901 /*======================================================================
902 * Region Intersection
903 *====================================================================*/
905 *-----------------------------------------------------------------------
906 * pixman_region_intersectO --
907 * Handle an overlapping band for pixman_region_intersect.
910 * TRUE if successful.
913 * Rectangles may be added to the region.
915 *-----------------------------------------------------------------------
919 pixman_region_intersectO (region_type_t *region,
930 box_type_t * pNextRect;
932 pNextRect = PIXREGION_TOP(region);
935 assert(r1 != r1End && r2 != r2End);
938 x1 = MAX(r1->x1, r2->x1);
939 x2 = MIN(r1->x2, r2->x2);
942 * If there's any overlap between the two rectangles, add that
943 * overlap to the new region.
946 NEWRECT(region, pNextRect, x1, y1, x2, y2);
949 * Advance the pointer(s) with the leftmost right side, since the next
950 * rectangle on that list may still overlap the other region's
959 } while ((r1 != r1End) && (r2 != r2End));
964 PIXMAN_EXPORT pixman_bool_t
965 PREFIX(_intersect) (region_type_t * newReg,
966 region_type_t * reg1,
967 region_type_t * reg2)
972 /* check for trivial reject */
973 if (PIXREGION_NIL(reg1) || PIXREGION_NIL(reg2) ||
974 !EXTENTCHECK(®1->extents, ®2->extents))
976 /* Covers about 20% of all cases */
978 newReg->extents.x2 = newReg->extents.x1;
979 newReg->extents.y2 = newReg->extents.y1;
980 if (PIXREGION_NAR(reg1) || PIXREGION_NAR(reg2))
982 newReg->data = pixman_brokendata;
986 newReg->data = pixman_region_emptyData;
988 else if (!reg1->data && !reg2->data)
990 /* Covers about 80% of cases that aren't trivially rejected */
991 newReg->extents.x1 = MAX(reg1->extents.x1, reg2->extents.x1);
992 newReg->extents.y1 = MAX(reg1->extents.y1, reg2->extents.y1);
993 newReg->extents.x2 = MIN(reg1->extents.x2, reg2->extents.x2);
994 newReg->extents.y2 = MIN(reg1->extents.y2, reg2->extents.y2);
996 newReg->data = (region_data_type_t *)NULL;
998 else if (!reg2->data && SUBSUMES(®2->extents, ®1->extents))
1000 return PREFIX(_copy) (newReg, reg1);
1002 else if (!reg1->data && SUBSUMES(®1->extents, ®2->extents))
1004 return PREFIX(_copy) (newReg, reg2);
1006 else if (reg1 == reg2)
1008 return PREFIX(_copy) (newReg, reg1);
1012 /* General purpose intersection */
1013 int overlap; /* result ignored */
1014 if (!pixman_op(newReg, reg1, reg2, pixman_region_intersectO, FALSE, FALSE,
1017 pixman_set_extents(newReg);
1024 #define MERGERECT(r) \
1026 if (r->x1 <= x2) { \
1027 /* Merge with current rectangle */ \
1028 if (r->x1 < x2) *pOverlap = TRUE; \
1029 if (x2 < r->x2) x2 = r->x2; \
1031 /* Add current rectangle, start new one */ \
1032 NEWRECT(region, pNextRect, x1, y1, x2, y2); \
1039 /*======================================================================
1041 *====================================================================*/
1044 *-----------------------------------------------------------------------
1045 * pixman_region_unionO --
1046 * Handle an overlapping band for the union operation. Picks the
1047 * left-most rectangle each time and merges it into the region.
1050 * TRUE if successful.
1053 * region is overwritten.
1054 * pOverlap is set to TRUE if any boxes overlap.
1056 *-----------------------------------------------------------------------
1058 static pixman_bool_t
1059 pixman_region_unionO (
1060 region_type_t *region,
1069 box_type_t * pNextRect;
1070 int x1; /* left and right side of current union */
1074 assert(r1 != r1End && r2 != r2End);
1076 pNextRect = PIXREGION_TOP(region);
1078 /* Start off current rectangle */
1079 if (r1->x1 < r2->x1)
1091 while (r1 != r1End && r2 != r2End)
1093 if (r1->x1 < r2->x1) MERGERECT(r1) else MERGERECT(r2);
1096 /* Finish off whoever (if any) is left */
1102 } while (r1 != r1End);
1104 else if (r2 != r2End)
1109 } while (r2 != r2End);
1112 /* Add current rectangle */
1113 NEWRECT(region, pNextRect, x1, y1, x2, y2);
1118 /* Convenience function for performing union of region with a
1121 PIXMAN_EXPORT pixman_bool_t
1122 PREFIX(_union_rect) (region_type_t *dest,
1123 region_type_t *source,
1125 unsigned int width, unsigned int height)
1127 region_type_t region;
1129 if (!width || !height)
1130 return PREFIX(_copy) (dest, source);
1132 region.extents.x1 = x;
1133 region.extents.y1 = y;
1134 region.extents.x2 = x + width;
1135 region.extents.y2 = y + height;
1137 return PREFIX(_union) (dest, source, ®ion);
1140 PIXMAN_EXPORT pixman_bool_t
1141 PREFIX(_union) (region_type_t *newReg,
1142 region_type_t *reg1,
1143 region_type_t *reg2)
1145 int overlap; /* result ignored */
1147 /* Return TRUE if some overlap
1148 * between reg1, reg2
1153 /* checks all the simple cases */
1156 * Region 1 and 2 are the same
1160 return PREFIX(_copy) (newReg, reg1);
1166 if (PIXREGION_NIL(reg1))
1168 if (PIXREGION_NAR(reg1))
1169 return pixman_break (newReg);
1171 return PREFIX(_copy) (newReg, reg2);
1178 if (PIXREGION_NIL(reg2))
1180 if (PIXREGION_NAR(reg2))
1181 return pixman_break (newReg);
1183 return PREFIX(_copy) (newReg, reg1);
1188 * Region 1 completely subsumes region 2
1190 if (!reg1->data && SUBSUMES(®1->extents, ®2->extents))
1193 return PREFIX(_copy) (newReg, reg1);
1198 * Region 2 completely subsumes region 1
1200 if (!reg2->data && SUBSUMES(®2->extents, ®1->extents))
1203 return PREFIX(_copy) (newReg, reg2);
1207 if (!pixman_op(newReg, reg1, reg2, pixman_region_unionO, TRUE, TRUE, &overlap))
1210 newReg->extents.x1 = MIN(reg1->extents.x1, reg2->extents.x1);
1211 newReg->extents.y1 = MIN(reg1->extents.y1, reg2->extents.y1);
1212 newReg->extents.x2 = MAX(reg1->extents.x2, reg2->extents.x2);
1213 newReg->extents.y2 = MAX(reg1->extents.y2, reg2->extents.y2);
1218 /*======================================================================
1219 * Batch Rectangle Union
1220 *====================================================================*/
1223 *-----------------------------------------------------------------------
1224 * pixman_region_append --
1226 * "Append" the rgn rectangles onto the end of dstrgn, maintaining
1227 * knowledge of YX-banding when it's easy. Otherwise, dstrgn just
1228 * becomes a non-y-x-banded random collection of rectangles, and not
1229 * yet a true region. After a sequence of appends, the caller must
1230 * call pixman_region_validate to ensure that a valid region is
1234 * TRUE if successful.
1237 * dstrgn is modified if rgn has rectangles.
1240 PIXMAN_EXPORT pixman_bool_t
1241 PREFIX(_append) (region_type_t * dstrgn,
1242 region_type_t * rgn)
1244 int numRects, dnumRects, size;
1245 box_type_t *new, *old;
1248 if (PIXREGION_NAR(rgn))
1249 return pixman_break (dstrgn);
1251 if (!rgn->data && (dstrgn->data == pixman_region_emptyData))
1253 dstrgn->extents = rgn->extents;
1254 dstrgn->data = (region_data_type_t *)NULL;
1258 numRects = PIXREGION_NUM_RECTS(rgn);
1263 dnumRects = PIXREGION_NUM_RECTS(dstrgn);
1264 if (!dnumRects && (size < 200))
1265 size = 200; /* XXX pick numbers out of a hat */
1266 RECTALLOC(dstrgn, size);
1267 old = PIXREGION_RECTS(rgn);
1269 dstrgn->extents = rgn->extents;
1270 else if (dstrgn->extents.x2 > dstrgn->extents.x1)
1272 box_type_t *first, *last;
1275 last = PIXREGION_BOXPTR(dstrgn) + (dnumRects - 1);
1276 if ((first->y1 > last->y2) ||
1277 ((first->y1 == last->y1) && (first->y2 == last->y2) &&
1278 (first->x1 > last->x2)))
1280 if (rgn->extents.x1 < dstrgn->extents.x1)
1281 dstrgn->extents.x1 = rgn->extents.x1;
1282 if (rgn->extents.x2 > dstrgn->extents.x2)
1283 dstrgn->extents.x2 = rgn->extents.x2;
1284 dstrgn->extents.y2 = rgn->extents.y2;
1288 first = PIXREGION_BOXPTR(dstrgn);
1289 last = old + (numRects - 1);
1290 if ((first->y1 > last->y2) ||
1291 ((first->y1 == last->y1) && (first->y2 == last->y2) &&
1292 (first->x1 > last->x2)))
1295 if (rgn->extents.x1 < dstrgn->extents.x1)
1296 dstrgn->extents.x1 = rgn->extents.x1;
1297 if (rgn->extents.x2 > dstrgn->extents.x2)
1298 dstrgn->extents.x2 = rgn->extents.x2;
1299 dstrgn->extents.y1 = rgn->extents.y1;
1302 dstrgn->extents.x2 = dstrgn->extents.x1;
1307 new = PIXREGION_BOX(dstrgn, numRects);
1309 *new = *PIXREGION_BOXPTR(dstrgn);
1311 memmove((char *)new,(char *)PIXREGION_BOXPTR(dstrgn),
1312 dnumRects * sizeof(box_type_t));
1313 new = PIXREGION_BOXPTR(dstrgn);
1316 new = PIXREGION_BOXPTR(dstrgn) + dnumRects;
1320 memmove((char *)new, (char *)old, numRects * sizeof(box_type_t));
1321 dstrgn->data->numRects += numRects;
1325 #define ExchangeRects(a, b) \
1329 rects[a] = rects[b]; \
1343 /* Always called with numRects > 1 */
1349 if (rects[0].y1 > rects[1].y1 ||
1350 (rects[0].y1 == rects[1].y1 && rects[0].x1 > rects[1].x1))
1351 ExchangeRects(0, 1);
1355 /* Choose partition element, stick in location 0 */
1356 ExchangeRects(0, numRects >> 1);
1360 /* Partition array */
1370 } while (i != numRects &&
1371 (r->y1 < y1 || (r->y1 == y1 && r->x1 < x1)));
1377 } while (y1 < r->y1 || (y1 == r->y1 && x1 < r->x1));
1379 ExchangeRects(i, j);
1382 /* Move partition element back to middle */
1383 ExchangeRects(0, j);
1386 if (numRects-j-1 > 1)
1387 QuickSortRects(&rects[j+1], numRects-j-1);
1389 } while (numRects > 1);
1393 *-----------------------------------------------------------------------
1394 * pixman_region_validate --
1396 * Take a ``region'' which is a non-y-x-banded random collection of
1397 * rectangles, and compute a nice region which is the union of all the
1401 * TRUE if successful.
1404 * The passed-in ``region'' may be modified.
1405 * pOverlap set to TRUE if any retangles overlapped,
1409 * Step 1. Sort the rectangles into ascending order with primary key y1
1410 * and secondary key x1.
1412 * Step 2. Split the rectangles into the minimum number of proper y-x
1413 * banded regions. This may require horizontally merging
1414 * rectangles, and vertically coalescing bands. With any luck,
1415 * this step in an identity transformation (ala the Box widget),
1416 * or a coalescing into 1 box (ala Menus).
1418 * Step 3. Merge the separate regions down to a single region by calling
1419 * pixman_region_union. Maximize the work each pixman_region_union call does by using
1422 *-----------------------------------------------------------------------
1425 PIXMAN_EXPORT pixman_bool_t
1426 PREFIX(_validate) (region_type_t * badreg,
1429 /* Descriptor for regions under construction in Step 2. */
1436 int numRects; /* Original numRects for badreg */
1437 RegionInfo *ri; /* Array of current regions */
1438 int numRI; /* Number of entries used in ri */
1439 int sizeRI; /* Number of entries available in ri */
1440 int i; /* Index into rects */
1441 int j; /* Index into ri */
1442 RegionInfo *rit; /* &ri[j] */
1443 region_type_t * reg; /* ri[j].reg */
1444 box_type_t * box; /* Current box in rects */
1445 box_type_t * riBox; /* Last box in ri[j].reg */
1446 region_type_t * hreg; /* ri[j_half].reg */
1447 pixman_bool_t ret = TRUE;
1455 numRects = badreg->data->numRects;
1458 if (PIXREGION_NAR(badreg))
1463 if (badreg->extents.x1 < badreg->extents.x2)
1465 if ((numRects) == 1)
1468 badreg->data = (region_data_type_t *) NULL;
1472 DOWNSIZE(badreg, numRects);
1478 /* Step 1: Sort the rects array into ascending (y1, x1) order */
1479 QuickSortRects(PIXREGION_BOXPTR(badreg), numRects);
1481 /* Step 2: Scatter the sorted array into the minimum number of regions */
1483 /* Set up the first region to be the first rectangle in badreg */
1484 /* Note that step 2 code will never overflow the ri[0].reg rects array */
1485 ri = (RegionInfo *) pixman_malloc_ab (4, sizeof(RegionInfo));
1487 return pixman_break (badreg);
1492 ri[0].reg = *badreg;
1493 box = PIXREGION_BOXPTR(&ri[0].reg);
1494 ri[0].reg.extents = *box;
1495 ri[0].reg.data->numRects = 1;
1496 badreg->extents = *pixman_region_emptyBox;
1497 badreg->data = pixman_region_emptyData;
1499 /* Now scatter rectangles into the minimum set of valid regions. If the
1500 next rectangle to be added to a region would force an existing rectangle
1501 in the region to be split up in order to maintain y-x banding, just
1502 forget it. Try the next region. If it doesn't fit cleanly into any
1503 region, make a new one. */
1505 for (i = numRects; --i > 0;)
1508 /* Look for a region to append box to */
1509 for (j = numRI, rit = ri; --j >= 0; rit++)
1512 riBox = PIXREGION_END(reg);
1514 if (box->y1 == riBox->y1 && box->y2 == riBox->y2)
1516 /* box is in same band as riBox. Merge or append it */
1517 if (box->x1 <= riBox->x2)
1519 /* Merge it with riBox */
1520 if (box->x1 < riBox->x2) *pOverlap = TRUE;
1521 if (box->x2 > riBox->x2) riBox->x2 = box->x2;
1525 RECTALLOC_BAIL(reg, 1, bail);
1526 *PIXREGION_TOP(reg) = *box;
1527 reg->data->numRects++;
1529 goto NextRect; /* So sue me */
1531 else if (box->y1 >= riBox->y2)
1533 /* Put box into new band */
1534 if (reg->extents.x2 < riBox->x2) reg->extents.x2 = riBox->x2;
1535 if (reg->extents.x1 > box->x1) reg->extents.x1 = box->x1;
1536 Coalesce(reg, rit->prevBand, rit->curBand);
1537 rit->curBand = reg->data->numRects;
1538 RECTALLOC_BAIL(reg, 1, bail);
1539 *PIXREGION_TOP(reg) = *box;
1540 reg->data->numRects++;
1543 /* Well, this region was inappropriate. Try the next one. */
1546 /* Uh-oh. No regions were appropriate. Create a new one. */
1547 if (sizeRI == numRI)
1551 /* Oops, allocate space for new region information */
1554 data_size = sizeRI * sizeof(RegionInfo);
1555 if (data_size / sizeRI != sizeof(RegionInfo))
1557 rit = (RegionInfo *) realloc(ri, data_size);
1566 rit->reg.extents = *box;
1567 rit->reg.data = (region_data_type_t *)NULL;
1568 if (!pixman_rect_alloc(&rit->reg, (i+numRI) / numRI)) /* MUST force allocation */
1573 /* Make a final pass over each region in order to Coalesce and set
1574 extents.x2 and extents.y2 */
1576 for (j = numRI, rit = ri; --j >= 0; rit++)
1579 riBox = PIXREGION_END(reg);
1580 reg->extents.y2 = riBox->y2;
1581 if (reg->extents.x2 < riBox->x2) reg->extents.x2 = riBox->x2;
1582 Coalesce(reg, rit->prevBand, rit->curBand);
1583 if (reg->data->numRects == 1) /* keep unions happy below */
1586 reg->data = (region_data_type_t *)NULL;
1590 /* Step 3: Union all regions into a single region */
1594 for (j = numRI & 1; j < (half + (numRI & 1)); j++)
1597 hreg = &ri[j+half].reg;
1598 if (!pixman_op(reg, reg, hreg, pixman_region_unionO, TRUE, TRUE, pOverlap))
1600 if (hreg->extents.x1 < reg->extents.x1)
1601 reg->extents.x1 = hreg->extents.x1;
1602 if (hreg->extents.y1 < reg->extents.y1)
1603 reg->extents.y1 = hreg->extents.y1;
1604 if (hreg->extents.x2 > reg->extents.x2)
1605 reg->extents.x2 = hreg->extents.x2;
1606 if (hreg->extents.y2 > reg->extents.y2)
1607 reg->extents.y2 = hreg->extents.y2;
1614 *badreg = ri[0].reg;
1619 for (i = 0; i < numRI; i++)
1620 freeData(&ri[i].reg);
1623 return pixman_break (badreg);
1626 /*======================================================================
1627 * Region Subtraction
1628 *====================================================================*/
1631 *-----------------------------------------------------------------------
1632 * pixman_region_subtractO --
1633 * Overlapping band subtraction. x1 is the left-most point not yet
1637 * TRUE if successful.
1640 * region may have rectangles added to it.
1642 *-----------------------------------------------------------------------
1645 static pixman_bool_t
1646 pixman_region_subtractO (
1647 region_type_t * region,
1656 box_type_t * pNextRect;
1662 assert(r1 != r1End && r2 != r2End);
1664 pNextRect = PIXREGION_TOP(region);
1671 * Subtrahend entirely to left of minuend: go to next subtrahend.
1675 else if (r2->x1 <= x1)
1678 * Subtrahend preceeds minuend: nuke left edge of minuend.
1684 * Minuend completely covered: advance to next minuend and
1685 * reset left fence to edge of new minuend.
1694 * Subtrahend now used up since it doesn't extend beyond
1700 else if (r2->x1 < r1->x2)
1703 * Left part of subtrahend covers part of minuend: add uncovered
1704 * part of minuend to region and skip to next subtrahend.
1707 NEWRECT(region, pNextRect, x1, y1, r2->x1, y2);
1713 * Minuend used up: advance to new...
1722 * Subtrahend used up
1730 * Minuend used up: add any remaining piece before advancing.
1733 NEWRECT(region, pNextRect, x1, y1, r1->x2, y2);
1738 } while ((r1 != r1End) && (r2 != r2End));
1741 * Add remaining minuend rectangles to region.
1746 NEWRECT(region, pNextRect, x1, y1, r1->x2, y2);
1755 *-----------------------------------------------------------------------
1756 * pixman_region_subtract --
1757 * Subtract regS from regM and leave the result in regD.
1758 * S stands for subtrahend, M for minuend and D for difference.
1761 * TRUE if successful.
1764 * regD is overwritten.
1766 *-----------------------------------------------------------------------
1768 PIXMAN_EXPORT pixman_bool_t
1769 PREFIX(_subtract) (region_type_t * regD,
1770 region_type_t * regM,
1771 region_type_t * regS)
1773 int overlap; /* result ignored */
1778 /* check for trivial rejects */
1779 if (PIXREGION_NIL(regM) || PIXREGION_NIL(regS) ||
1780 !EXTENTCHECK(®M->extents, ®S->extents))
1782 if (PIXREGION_NAR (regS))
1783 return pixman_break (regD);
1784 return PREFIX(_copy) (regD, regM);
1786 else if (regM == regS)
1789 regD->extents.x2 = regD->extents.x1;
1790 regD->extents.y2 = regD->extents.y1;
1791 regD->data = pixman_region_emptyData;
1795 /* Add those rectangles in region 1 that aren't in region 2,
1796 do yucky substraction for overlaps, and
1797 just throw away rectangles in region 2 that aren't in region 1 */
1798 if (!pixman_op(regD, regM, regS, pixman_region_subtractO, TRUE, FALSE, &overlap))
1802 * Can't alter RegD's extents before we call pixman_op because
1803 * it might be one of the source regions and pixman_op depends
1804 * on the extents of those regions being unaltered. Besides, this
1805 * way there's no checking against rectangles that will be nuked
1806 * due to coalescing, so we have to examine fewer rectangles.
1808 pixman_set_extents(regD);
1813 /*======================================================================
1815 *====================================================================*/
1818 *-----------------------------------------------------------------------
1819 * pixman_region_inverse --
1820 * Take a region and a box and return a region that is everything
1821 * in the box but not in the region. The careful reader will note
1822 * that this is the same as subtracting the region from the box...
1828 * newReg is overwritten.
1830 *-----------------------------------------------------------------------
1833 PIXMAN_EXPORT PREFIX(_inverse) (region_type_t * newReg, /* Destination region */
1834 region_type_t * reg1, /* Region to invert */
1835 box_type_t * invRect) /* Bounding box for inversion */
1837 region_type_t invReg; /* Quick and dirty region made from the
1839 int overlap; /* result ignored */
1843 /* check for trivial rejects */
1844 if (PIXREGION_NIL(reg1) || !EXTENTCHECK(invRect, ®1->extents))
1846 if (PIXREGION_NAR(reg1))
1847 return pixman_break (newReg);
1848 newReg->extents = *invRect;
1850 newReg->data = (region_data_type_t *)NULL;
1854 /* Add those rectangles in region 1 that aren't in region 2,
1855 do yucky substraction for overlaps, and
1856 just throw away rectangles in region 2 that aren't in region 1 */
1857 invReg.extents = *invRect;
1858 invReg.data = (region_data_type_t *)NULL;
1859 if (!pixman_op(newReg, &invReg, reg1, pixman_region_subtractO, TRUE, FALSE, &overlap))
1863 * Can't alter newReg's extents before we call pixman_op because
1864 * it might be one of the source regions and pixman_op depends
1865 * on the extents of those regions being unaltered. Besides, this
1866 * way there's no checking against rectangles that will be nuked
1867 * due to coalescing, so we have to examine fewer rectangles.
1869 pixman_set_extents(newReg);
1875 * RectIn(region, rect)
1876 * This routine takes a pointer to a region and a pointer to a box
1877 * and determines if the box is outside/inside/partly inside the region.
1879 * The idea is to travel through the list of rectangles trying to cover the
1880 * passed box with them. Anytime a piece of the rectangle isn't covered
1881 * by a band of rectangles, partOut is set TRUE. Any time a rectangle in
1882 * the region covers part of the box, partIn is set TRUE. The process ends
1883 * when either the box has been completely covered (we reached a band that
1884 * doesn't overlap the box, partIn is TRUE and partOut is false), the
1885 * box has been partially covered (partIn == partOut == TRUE -- because of
1886 * the banding, the first time this is true we know the box is only
1887 * partially in the region) or is outside the region (we reached a band
1888 * that doesn't overlap the box at all and partIn is false)
1891 pixman_region_overlap_t
1892 PIXMAN_EXPORT PREFIX(_contains_rectangle) (region_type_t * region,
1898 box_type_t * pboxEnd;
1899 int partIn, partOut;
1903 numRects = PIXREGION_NUM_RECTS(region);
1904 /* useful optimization */
1905 if (!numRects || !EXTENTCHECK(®ion->extents, prect))
1906 return(PIXMAN_REGION_OUT);
1910 /* We know that it must be PIXMAN_REGION_IN or PIXMAN_REGION_PART */
1911 if (SUBSUMES(®ion->extents, prect))
1912 return(PIXMAN_REGION_IN);
1914 return(PIXMAN_REGION_PART);
1920 /* (x,y) starts at upper left of rect, moving to the right and down */
1924 /* can stop when both partOut and partIn are TRUE, or we reach prect->y2 */
1925 for (pbox = PIXREGION_BOXPTR(region), pboxEnd = pbox + numRects;
1931 continue; /* getting up to speed or skipping remainder of band */
1935 partOut = TRUE; /* missed part of rectangle above */
1936 if (partIn || (pbox->y1 >= prect->y2))
1938 y = pbox->y1; /* x guaranteed to be == prect->x1 */
1942 continue; /* not far enough over yet */
1946 partOut = TRUE; /* missed part of rectangle to left */
1951 if (pbox->x1 < prect->x2)
1953 partIn = TRUE; /* definitely overlap */
1958 if (pbox->x2 >= prect->x2)
1960 y = pbox->y2; /* finished with this band */
1963 x = prect->x1; /* reset x out to left again */
1968 * Because boxes in a band are maximal width, if the first box
1969 * to overlap the rectangle doesn't completely cover it in that
1970 * band, the rectangle must be partially out, since some of it
1971 * will be uncovered in that band. partIn will have been set true
1982 return PIXMAN_REGION_PART;
1984 return PIXMAN_REGION_IN;
1988 return PIXMAN_REGION_OUT;
1992 /* PREFIX(_translate) (region, x, y)
1997 PREFIX(_translate) (region_type_t * region, int x, int y)
2004 region->extents.x1 = x1 = region->extents.x1 + x;
2005 region->extents.y1 = y1 = region->extents.y1 + y;
2006 region->extents.x2 = x2 = region->extents.x2 + x;
2007 region->extents.y2 = y2 = region->extents.y2 + y;
2008 if (((x1 - SHRT_MIN)|(y1 - SHRT_MIN)|(SHRT_MAX - x2)|(SHRT_MAX - y2)) >= 0)
2010 if (region->data && (nbox = region->data->numRects))
2012 for (pbox = PIXREGION_BOXPTR(region); nbox--; pbox++)
2022 if (((x2 - SHRT_MIN)|(y2 - SHRT_MIN)|(SHRT_MAX - x1)|(SHRT_MAX - y1)) <= 0)
2024 region->extents.x2 = region->extents.x1;
2025 region->extents.y2 = region->extents.y1;
2027 region->data = pixman_region_emptyData;
2031 region->extents.x1 = SHRT_MIN;
2032 else if (x2 > SHRT_MAX)
2033 region->extents.x2 = SHRT_MAX;
2035 region->extents.y1 = SHRT_MIN;
2036 else if (y2 > SHRT_MAX)
2037 region->extents.y2 = SHRT_MAX;
2038 if (region->data && (nbox = region->data->numRects))
2040 box_type_t * pboxout;
2042 for (pboxout = pbox = PIXREGION_BOXPTR(region); nbox--; pbox++)
2044 pboxout->x1 = x1 = pbox->x1 + x;
2045 pboxout->y1 = y1 = pbox->y1 + y;
2046 pboxout->x2 = x2 = pbox->x2 + x;
2047 pboxout->y2 = y2 = pbox->y2 + y;
2048 if (((x2 - SHRT_MIN)|(y2 - SHRT_MIN)|
2049 (SHRT_MAX - x1)|(SHRT_MAX - y1)) <= 0)
2051 region->data->numRects--;
2055 pboxout->x1 = SHRT_MIN;
2056 else if (x2 > SHRT_MAX)
2057 pboxout->x2 = SHRT_MAX;
2059 pboxout->y1 = SHRT_MIN;
2060 else if (y2 > SHRT_MAX)
2061 pboxout->y2 = SHRT_MAX;
2064 if (pboxout != pbox)
2066 if (region->data->numRects == 1)
2068 region->extents = *PIXREGION_BOXPTR(region);
2070 region->data = (region_data_type_t *)NULL;
2073 pixman_set_extents(region);
2079 PREFIX(_reset) (region_type_t *region, box_type_t *box)
2082 assert(box->x1<=box->x2);
2083 assert(box->y1<=box->y2);
2084 region->extents = *box;
2086 region->data = (region_data_type_t *)NULL;
2089 /* box is "return" value */
2091 PREFIX(_contains_point) (region_type_t * region,
2095 box_type_t *pbox, *pboxEnd;
2099 numRects = PIXREGION_NUM_RECTS(region);
2100 if (!numRects || !INBOX(®ion->extents, x, y))
2104 *box = region->extents;
2107 for (pbox = PIXREGION_BOXPTR(region), pboxEnd = pbox + numRects;
2112 continue; /* not there yet */
2113 if ((y < pbox->y1) || (x < pbox->x1))
2114 break; /* missed it */
2116 continue; /* not there yet */
2124 PREFIX(_not_empty) (region_type_t * region)
2127 return(!PIXREGION_NIL(region));
2131 PREFIX(_empty) (region_type_t * region)
2135 region->extents.x2 = region->extents.x1;
2136 region->extents.y2 = region->extents.y1;
2137 region->data = pixman_region_emptyData;
2140 PIXMAN_EXPORT box_type_t *
2141 PREFIX(_extents) (region_type_t * region)
2144 return(®ion->extents);
2148 Clip a list of scanlines to a region. The caller has allocated the
2149 space. FSorted is non-zero if the scanline origins are in ascending
2151 returns the number of new, clipped scanlines.
2154 PIXMAN_EXPORT pixman_bool_t
2155 PREFIX(_selfcheck) (reg)
2156 region_type_t * reg;
2160 if ((reg->extents.x1 > reg->extents.x2) ||
2161 (reg->extents.y1 > reg->extents.y2))
2163 numRects = PIXREGION_NUM_RECTS(reg);
2165 return ((reg->extents.x1 == reg->extents.x2) &&
2166 (reg->extents.y1 == reg->extents.y2) &&
2167 (reg->data->size || (reg->data == pixman_region_emptyData)));
2168 else if (numRects == 1)
2169 return (!reg->data);
2172 box_type_t * pboxP, * pboxN;
2175 pboxP = PIXREGION_RECTS(reg);
2177 box.y2 = pboxP[numRects-1].y2;
2179 for (i = numRects; --i > 0; pboxP++, pboxN++)
2181 if ((pboxN->x1 >= pboxN->x2) ||
2182 (pboxN->y1 >= pboxN->y2))
2184 if (pboxN->x1 < box.x1)
2186 if (pboxN->x2 > box.x2)
2188 if ((pboxN->y1 < pboxP->y1) ||
2189 ((pboxN->y1 == pboxP->y1) &&
2190 ((pboxN->x1 < pboxP->x2) || (pboxN->y2 != pboxP->y2))))
2193 return ((box.x1 == reg->extents.x1) &&
2194 (box.x2 == reg->extents.x2) &&
2195 (box.y1 == reg->extents.y1) &&
2196 (box.y2 == reg->extents.y2));
2200 PIXMAN_EXPORT pixman_bool_t
2201 PREFIX(_init_rects) (region_type_t *region,
2202 box_type_t *boxes, int count)
2206 /* if it's 1, then we just want to set the extents, so call
2207 * the existing method. */
2209 PREFIX(_init_rect) (region,
2212 boxes[0].x2 - boxes[0].x1,
2213 boxes[0].y2 - boxes[0].y1);
2217 PREFIX(_init) (region);
2219 /* if it's 0, don't call pixman_rect_alloc -- 0 rectangles is
2220 * a special case, and causing pixman_rect_alloc would cause
2221 * us to leak memory (because the 0-rect case should be the
2222 * static pixman_region_emptyData data).
2227 if (!pixman_rect_alloc(region, count))
2230 /* Copy in the rects */
2231 memcpy (PIXREGION_RECTS(region), boxes, sizeof(box_type_t) * count);
2232 region->data->numRects = count;
2235 region->extents.x1 = region->extents.x2 = 0;
2236 return PREFIX(_validate) (region, &overlap);