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(_internal_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; \
251 PIXMAN_EXPORT pixman_bool_t
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 *====================================================================*/
1222 #define ExchangeRects(a, b) \
1226 rects[a] = rects[b]; \
1240 /* Always called with numRects > 1 */
1246 if (rects[0].y1 > rects[1].y1 ||
1247 (rects[0].y1 == rects[1].y1 && rects[0].x1 > rects[1].x1))
1248 ExchangeRects(0, 1);
1252 /* Choose partition element, stick in location 0 */
1253 ExchangeRects(0, numRects >> 1);
1257 /* Partition array */
1267 } while (i != numRects &&
1268 (r->y1 < y1 || (r->y1 == y1 && r->x1 < x1)));
1274 } while (y1 < r->y1 || (y1 == r->y1 && x1 < r->x1));
1276 ExchangeRects(i, j);
1279 /* Move partition element back to middle */
1280 ExchangeRects(0, j);
1283 if (numRects-j-1 > 1)
1284 QuickSortRects(&rects[j+1], numRects-j-1);
1286 } while (numRects > 1);
1290 *-----------------------------------------------------------------------
1291 * pixman_region_validate --
1293 * Take a ``region'' which is a non-y-x-banded random collection of
1294 * rectangles, and compute a nice region which is the union of all the
1298 * TRUE if successful.
1301 * The passed-in ``region'' may be modified.
1302 * pOverlap set to TRUE if any retangles overlapped,
1306 * Step 1. Sort the rectangles into ascending order with primary key y1
1307 * and secondary key x1.
1309 * Step 2. Split the rectangles into the minimum number of proper y-x
1310 * banded regions. This may require horizontally merging
1311 * rectangles, and vertically coalescing bands. With any luck,
1312 * this step in an identity transformation (ala the Box widget),
1313 * or a coalescing into 1 box (ala Menus).
1315 * Step 3. Merge the separate regions down to a single region by calling
1316 * pixman_region_union. Maximize the work each pixman_region_union call does by using
1319 *-----------------------------------------------------------------------
1322 static pixman_bool_t
1323 validate (region_type_t * badreg,
1326 /* Descriptor for regions under construction in Step 2. */
1333 int numRects; /* Original numRects for badreg */
1334 RegionInfo *ri; /* Array of current regions */
1335 int numRI; /* Number of entries used in ri */
1336 int sizeRI; /* Number of entries available in ri */
1337 int i; /* Index into rects */
1338 int j; /* Index into ri */
1339 RegionInfo *rit; /* &ri[j] */
1340 region_type_t * reg; /* ri[j].reg */
1341 box_type_t * box; /* Current box in rects */
1342 box_type_t * riBox; /* Last box in ri[j].reg */
1343 region_type_t * hreg; /* ri[j_half].reg */
1344 pixman_bool_t ret = TRUE;
1352 numRects = badreg->data->numRects;
1355 if (PIXREGION_NAR(badreg))
1360 if (badreg->extents.x1 < badreg->extents.x2)
1362 if ((numRects) == 1)
1365 badreg->data = (region_data_type_t *) NULL;
1369 DOWNSIZE(badreg, numRects);
1375 /* Step 1: Sort the rects array into ascending (y1, x1) order */
1376 QuickSortRects(PIXREGION_BOXPTR(badreg), numRects);
1378 /* Step 2: Scatter the sorted array into the minimum number of regions */
1380 /* Set up the first region to be the first rectangle in badreg */
1381 /* Note that step 2 code will never overflow the ri[0].reg rects array */
1382 ri = (RegionInfo *) pixman_malloc_ab (4, sizeof(RegionInfo));
1384 return pixman_break (badreg);
1389 ri[0].reg = *badreg;
1390 box = PIXREGION_BOXPTR(&ri[0].reg);
1391 ri[0].reg.extents = *box;
1392 ri[0].reg.data->numRects = 1;
1393 badreg->extents = *pixman_region_emptyBox;
1394 badreg->data = pixman_region_emptyData;
1396 /* Now scatter rectangles into the minimum set of valid regions. If the
1397 next rectangle to be added to a region would force an existing rectangle
1398 in the region to be split up in order to maintain y-x banding, just
1399 forget it. Try the next region. If it doesn't fit cleanly into any
1400 region, make a new one. */
1402 for (i = numRects; --i > 0;)
1405 /* Look for a region to append box to */
1406 for (j = numRI, rit = ri; --j >= 0; rit++)
1409 riBox = PIXREGION_END(reg);
1411 if (box->y1 == riBox->y1 && box->y2 == riBox->y2)
1413 /* box is in same band as riBox. Merge or append it */
1414 if (box->x1 <= riBox->x2)
1416 /* Merge it with riBox */
1417 if (box->x1 < riBox->x2) *pOverlap = TRUE;
1418 if (box->x2 > riBox->x2) riBox->x2 = box->x2;
1422 RECTALLOC_BAIL(reg, 1, bail);
1423 *PIXREGION_TOP(reg) = *box;
1424 reg->data->numRects++;
1426 goto NextRect; /* So sue me */
1428 else if (box->y1 >= riBox->y2)
1430 /* Put box into new band */
1431 if (reg->extents.x2 < riBox->x2) reg->extents.x2 = riBox->x2;
1432 if (reg->extents.x1 > box->x1) reg->extents.x1 = box->x1;
1433 Coalesce(reg, rit->prevBand, rit->curBand);
1434 rit->curBand = reg->data->numRects;
1435 RECTALLOC_BAIL(reg, 1, bail);
1436 *PIXREGION_TOP(reg) = *box;
1437 reg->data->numRects++;
1440 /* Well, this region was inappropriate. Try the next one. */
1443 /* Uh-oh. No regions were appropriate. Create a new one. */
1444 if (sizeRI == numRI)
1448 /* Oops, allocate space for new region information */
1451 data_size = sizeRI * sizeof(RegionInfo);
1452 if (data_size / sizeRI != sizeof(RegionInfo))
1454 rit = (RegionInfo *) realloc(ri, data_size);
1463 rit->reg.extents = *box;
1464 rit->reg.data = (region_data_type_t *)NULL;
1465 if (!pixman_rect_alloc(&rit->reg, (i+numRI) / numRI)) /* MUST force allocation */
1470 /* Make a final pass over each region in order to Coalesce and set
1471 extents.x2 and extents.y2 */
1473 for (j = numRI, rit = ri; --j >= 0; rit++)
1476 riBox = PIXREGION_END(reg);
1477 reg->extents.y2 = riBox->y2;
1478 if (reg->extents.x2 < riBox->x2) reg->extents.x2 = riBox->x2;
1479 Coalesce(reg, rit->prevBand, rit->curBand);
1480 if (reg->data->numRects == 1) /* keep unions happy below */
1483 reg->data = (region_data_type_t *)NULL;
1487 /* Step 3: Union all regions into a single region */
1491 for (j = numRI & 1; j < (half + (numRI & 1)); j++)
1494 hreg = &ri[j+half].reg;
1495 if (!pixman_op(reg, reg, hreg, pixman_region_unionO, TRUE, TRUE, pOverlap))
1497 if (hreg->extents.x1 < reg->extents.x1)
1498 reg->extents.x1 = hreg->extents.x1;
1499 if (hreg->extents.y1 < reg->extents.y1)
1500 reg->extents.y1 = hreg->extents.y1;
1501 if (hreg->extents.x2 > reg->extents.x2)
1502 reg->extents.x2 = hreg->extents.x2;
1503 if (hreg->extents.y2 > reg->extents.y2)
1504 reg->extents.y2 = hreg->extents.y2;
1511 *badreg = ri[0].reg;
1516 for (i = 0; i < numRI; i++)
1517 freeData(&ri[i].reg);
1520 return pixman_break (badreg);
1523 /*======================================================================
1524 * Region Subtraction
1525 *====================================================================*/
1528 *-----------------------------------------------------------------------
1529 * pixman_region_subtractO --
1530 * Overlapping band subtraction. x1 is the left-most point not yet
1534 * TRUE if successful.
1537 * region may have rectangles added to it.
1539 *-----------------------------------------------------------------------
1542 static pixman_bool_t
1543 pixman_region_subtractO (
1544 region_type_t * region,
1553 box_type_t * pNextRect;
1559 assert(r1 != r1End && r2 != r2End);
1561 pNextRect = PIXREGION_TOP(region);
1568 * Subtrahend entirely to left of minuend: go to next subtrahend.
1572 else if (r2->x1 <= x1)
1575 * Subtrahend preceeds minuend: nuke left edge of minuend.
1581 * Minuend completely covered: advance to next minuend and
1582 * reset left fence to edge of new minuend.
1591 * Subtrahend now used up since it doesn't extend beyond
1597 else if (r2->x1 < r1->x2)
1600 * Left part of subtrahend covers part of minuend: add uncovered
1601 * part of minuend to region and skip to next subtrahend.
1604 NEWRECT(region, pNextRect, x1, y1, r2->x1, y2);
1610 * Minuend used up: advance to new...
1619 * Subtrahend used up
1627 * Minuend used up: add any remaining piece before advancing.
1630 NEWRECT(region, pNextRect, x1, y1, r1->x2, y2);
1635 } while ((r1 != r1End) && (r2 != r2End));
1638 * Add remaining minuend rectangles to region.
1643 NEWRECT(region, pNextRect, x1, y1, r1->x2, y2);
1652 *-----------------------------------------------------------------------
1653 * pixman_region_subtract --
1654 * Subtract regS from regM and leave the result in regD.
1655 * S stands for subtrahend, M for minuend and D for difference.
1658 * TRUE if successful.
1661 * regD is overwritten.
1663 *-----------------------------------------------------------------------
1665 PIXMAN_EXPORT pixman_bool_t
1666 PREFIX(_subtract) (region_type_t * regD,
1667 region_type_t * regM,
1668 region_type_t * regS)
1670 int overlap; /* result ignored */
1675 /* check for trivial rejects */
1676 if (PIXREGION_NIL(regM) || PIXREGION_NIL(regS) ||
1677 !EXTENTCHECK(®M->extents, ®S->extents))
1679 if (PIXREGION_NAR (regS))
1680 return pixman_break (regD);
1681 return PREFIX(_copy) (regD, regM);
1683 else if (regM == regS)
1686 regD->extents.x2 = regD->extents.x1;
1687 regD->extents.y2 = regD->extents.y1;
1688 regD->data = pixman_region_emptyData;
1692 /* Add those rectangles in region 1 that aren't in region 2,
1693 do yucky substraction for overlaps, and
1694 just throw away rectangles in region 2 that aren't in region 1 */
1695 if (!pixman_op(regD, regM, regS, pixman_region_subtractO, TRUE, FALSE, &overlap))
1699 * Can't alter RegD's extents before we call pixman_op because
1700 * it might be one of the source regions and pixman_op depends
1701 * on the extents of those regions being unaltered. Besides, this
1702 * way there's no checking against rectangles that will be nuked
1703 * due to coalescing, so we have to examine fewer rectangles.
1705 pixman_set_extents(regD);
1710 /*======================================================================
1712 *====================================================================*/
1715 *-----------------------------------------------------------------------
1716 * pixman_region_inverse --
1717 * Take a region and a box and return a region that is everything
1718 * in the box but not in the region. The careful reader will note
1719 * that this is the same as subtracting the region from the box...
1725 * newReg is overwritten.
1727 *-----------------------------------------------------------------------
1730 PIXMAN_EXPORT PREFIX(_inverse) (region_type_t * newReg, /* Destination region */
1731 region_type_t * reg1, /* Region to invert */
1732 box_type_t * invRect) /* Bounding box for inversion */
1734 region_type_t invReg; /* Quick and dirty region made from the
1736 int overlap; /* result ignored */
1740 /* check for trivial rejects */
1741 if (PIXREGION_NIL(reg1) || !EXTENTCHECK(invRect, ®1->extents))
1743 if (PIXREGION_NAR(reg1))
1744 return pixman_break (newReg);
1745 newReg->extents = *invRect;
1747 newReg->data = (region_data_type_t *)NULL;
1751 /* Add those rectangles in region 1 that aren't in region 2,
1752 do yucky substraction for overlaps, and
1753 just throw away rectangles in region 2 that aren't in region 1 */
1754 invReg.extents = *invRect;
1755 invReg.data = (region_data_type_t *)NULL;
1756 if (!pixman_op(newReg, &invReg, reg1, pixman_region_subtractO, TRUE, FALSE, &overlap))
1760 * Can't alter newReg's extents before we call pixman_op because
1761 * it might be one of the source regions and pixman_op depends
1762 * on the extents of those regions being unaltered. Besides, this
1763 * way there's no checking against rectangles that will be nuked
1764 * due to coalescing, so we have to examine fewer rectangles.
1766 pixman_set_extents(newReg);
1772 * RectIn(region, rect)
1773 * This routine takes a pointer to a region and a pointer to a box
1774 * and determines if the box is outside/inside/partly inside the region.
1776 * The idea is to travel through the list of rectangles trying to cover the
1777 * passed box with them. Anytime a piece of the rectangle isn't covered
1778 * by a band of rectangles, partOut is set TRUE. Any time a rectangle in
1779 * the region covers part of the box, partIn is set TRUE. The process ends
1780 * when either the box has been completely covered (we reached a band that
1781 * doesn't overlap the box, partIn is TRUE and partOut is false), the
1782 * box has been partially covered (partIn == partOut == TRUE -- because of
1783 * the banding, the first time this is true we know the box is only
1784 * partially in the region) or is outside the region (we reached a band
1785 * that doesn't overlap the box at all and partIn is false)
1788 pixman_region_overlap_t
1789 PIXMAN_EXPORT PREFIX(_contains_rectangle) (region_type_t * region,
1795 box_type_t * pboxEnd;
1796 int partIn, partOut;
1800 numRects = PIXREGION_NUM_RECTS(region);
1801 /* useful optimization */
1802 if (!numRects || !EXTENTCHECK(®ion->extents, prect))
1803 return(PIXMAN_REGION_OUT);
1807 /* We know that it must be PIXMAN_REGION_IN or PIXMAN_REGION_PART */
1808 if (SUBSUMES(®ion->extents, prect))
1809 return(PIXMAN_REGION_IN);
1811 return(PIXMAN_REGION_PART);
1817 /* (x,y) starts at upper left of rect, moving to the right and down */
1821 /* can stop when both partOut and partIn are TRUE, or we reach prect->y2 */
1822 for (pbox = PIXREGION_BOXPTR(region), pboxEnd = pbox + numRects;
1828 continue; /* getting up to speed or skipping remainder of band */
1832 partOut = TRUE; /* missed part of rectangle above */
1833 if (partIn || (pbox->y1 >= prect->y2))
1835 y = pbox->y1; /* x guaranteed to be == prect->x1 */
1839 continue; /* not far enough over yet */
1843 partOut = TRUE; /* missed part of rectangle to left */
1848 if (pbox->x1 < prect->x2)
1850 partIn = TRUE; /* definitely overlap */
1855 if (pbox->x2 >= prect->x2)
1857 y = pbox->y2; /* finished with this band */
1860 x = prect->x1; /* reset x out to left again */
1865 * Because boxes in a band are maximal width, if the first box
1866 * to overlap the rectangle doesn't completely cover it in that
1867 * band, the rectangle must be partially out, since some of it
1868 * will be uncovered in that band. partIn will have been set true
1879 return PIXMAN_REGION_PART;
1881 return PIXMAN_REGION_IN;
1885 return PIXMAN_REGION_OUT;
1889 /* PREFIX(_translate) (region, x, y)
1894 PREFIX(_translate) (region_type_t * region, int x, int y)
1901 region->extents.x1 = x1 = region->extents.x1 + x;
1902 region->extents.y1 = y1 = region->extents.y1 + y;
1903 region->extents.x2 = x2 = region->extents.x2 + x;
1904 region->extents.y2 = y2 = region->extents.y2 + y;
1905 if (((x1 - SHRT_MIN)|(y1 - SHRT_MIN)|(SHRT_MAX - x2)|(SHRT_MAX - y2)) >= 0)
1907 if (region->data && (nbox = region->data->numRects))
1909 for (pbox = PIXREGION_BOXPTR(region); nbox--; pbox++)
1919 if (((x2 - SHRT_MIN)|(y2 - SHRT_MIN)|(SHRT_MAX - x1)|(SHRT_MAX - y1)) <= 0)
1921 region->extents.x2 = region->extents.x1;
1922 region->extents.y2 = region->extents.y1;
1924 region->data = pixman_region_emptyData;
1928 region->extents.x1 = SHRT_MIN;
1929 else if (x2 > SHRT_MAX)
1930 region->extents.x2 = SHRT_MAX;
1932 region->extents.y1 = SHRT_MIN;
1933 else if (y2 > SHRT_MAX)
1934 region->extents.y2 = SHRT_MAX;
1935 if (region->data && (nbox = region->data->numRects))
1937 box_type_t * pboxout;
1939 for (pboxout = pbox = PIXREGION_BOXPTR(region); nbox--; pbox++)
1941 pboxout->x1 = x1 = pbox->x1 + x;
1942 pboxout->y1 = y1 = pbox->y1 + y;
1943 pboxout->x2 = x2 = pbox->x2 + x;
1944 pboxout->y2 = y2 = pbox->y2 + y;
1945 if (((x2 - SHRT_MIN)|(y2 - SHRT_MIN)|
1946 (SHRT_MAX - x1)|(SHRT_MAX - y1)) <= 0)
1948 region->data->numRects--;
1952 pboxout->x1 = SHRT_MIN;
1953 else if (x2 > SHRT_MAX)
1954 pboxout->x2 = SHRT_MAX;
1956 pboxout->y1 = SHRT_MIN;
1957 else if (y2 > SHRT_MAX)
1958 pboxout->y2 = SHRT_MAX;
1961 if (pboxout != pbox)
1963 if (region->data->numRects == 1)
1965 region->extents = *PIXREGION_BOXPTR(region);
1967 region->data = (region_data_type_t *)NULL;
1970 pixman_set_extents(region);
1976 PREFIX(_reset) (region_type_t *region, box_type_t *box)
1979 assert(box->x1<=box->x2);
1980 assert(box->y1<=box->y2);
1981 region->extents = *box;
1983 region->data = (region_data_type_t *)NULL;
1986 /* box is "return" value */
1988 PREFIX(_contains_point) (region_type_t * region,
1992 box_type_t *pbox, *pboxEnd;
1996 numRects = PIXREGION_NUM_RECTS(region);
1997 if (!numRects || !INBOX(®ion->extents, x, y))
2002 *box = region->extents;
2006 for (pbox = PIXREGION_BOXPTR(region), pboxEnd = pbox + numRects;
2011 continue; /* not there yet */
2012 if ((y < pbox->y1) || (x < pbox->x1))
2013 break; /* missed it */
2015 continue; /* not there yet */
2026 PREFIX(_not_empty) (region_type_t * region)
2029 return(!PIXREGION_NIL(region));
2032 PIXMAN_EXPORT box_type_t *
2033 PREFIX(_extents) (region_type_t * region)
2036 return(®ion->extents);
2040 Clip a list of scanlines to a region. The caller has allocated the
2041 space. FSorted is non-zero if the scanline origins are in ascending
2043 returns the number of new, clipped scanlines.
2046 PIXMAN_EXPORT pixman_bool_t
2047 PREFIX(_selfcheck) (reg)
2048 region_type_t * reg;
2052 if ((reg->extents.x1 > reg->extents.x2) ||
2053 (reg->extents.y1 > reg->extents.y2))
2055 numRects = PIXREGION_NUM_RECTS(reg);
2057 return ((reg->extents.x1 == reg->extents.x2) &&
2058 (reg->extents.y1 == reg->extents.y2) &&
2059 (reg->data->size || (reg->data == pixman_region_emptyData)));
2060 else if (numRects == 1)
2061 return (!reg->data);
2064 box_type_t * pboxP, * pboxN;
2067 pboxP = PIXREGION_RECTS(reg);
2069 box.y2 = pboxP[numRects-1].y2;
2071 for (i = numRects; --i > 0; pboxP++, pboxN++)
2073 if ((pboxN->x1 >= pboxN->x2) ||
2074 (pboxN->y1 >= pboxN->y2))
2076 if (pboxN->x1 < box.x1)
2078 if (pboxN->x2 > box.x2)
2080 if ((pboxN->y1 < pboxP->y1) ||
2081 ((pboxN->y1 == pboxP->y1) &&
2082 ((pboxN->x1 < pboxP->x2) || (pboxN->y2 != pboxP->y2))))
2085 return ((box.x1 == reg->extents.x1) &&
2086 (box.x2 == reg->extents.x2) &&
2087 (box.y1 == reg->extents.y1) &&
2088 (box.y2 == reg->extents.y2));
2092 PIXMAN_EXPORT pixman_bool_t
2093 PREFIX(_init_rects) (region_type_t *region,
2094 box_type_t *boxes, int count)
2098 /* if it's 1, then we just want to set the extents, so call
2099 * the existing method. */
2101 PREFIX(_init_rect) (region,
2104 boxes[0].x2 - boxes[0].x1,
2105 boxes[0].y2 - boxes[0].y1);
2109 PREFIX(_init) (region);
2111 /* if it's 0, don't call pixman_rect_alloc -- 0 rectangles is
2112 * a special case, and causing pixman_rect_alloc would cause
2113 * us to leak memory (because the 0-rect case should be the
2114 * static pixman_region_emptyData data).
2119 if (!pixman_rect_alloc(region, count))
2122 /* Copy in the rects */
2123 memcpy (PIXREGION_RECTS(region), boxes, sizeof(box_type_t) * count);
2124 region->data->numRects = count;
2127 region->extents.x1 = region->extents.x2 = 0;
2128 return validate (region, &overlap);