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_);
91 pixman_break (region_type_t *pReg);
94 * The functions in this file implement the Region abstraction used extensively
95 * throughout the X11 sample server. A Region is simply a set of disjoint
96 * (non-overlapping) rectangles, plus an "extent" rectangle which is the
97 * smallest single rectangle that contains all the non-overlapping rectangles.
99 * A Region is implemented as a "y-x-banded" array of rectangles. This array
100 * imposes two degrees of order. First, all rectangles are sorted by top side
101 * y coordinate first (y1), and then by left side x coordinate (x1).
103 * Furthermore, the rectangles are grouped into "bands". Each rectangle in a
104 * band has the same top y coordinate (y1), and each has the same bottom y
105 * coordinate (y2). Thus all rectangles in a band differ only in their left
106 * and right side (x1 and x2). Bands are implicit in the array of rectangles:
107 * there is no separate list of band start pointers.
109 * The y-x band representation does not minimize rectangles. In particular,
110 * if a rectangle vertically crosses a band (the rectangle has scanlines in
111 * the y1 to y2 area spanned by the band), then the rectangle may be broken
112 * down into two or more smaller rectangles stacked one atop the other.
114 * ----------- -----------
116 * | | -------- ----------- --------
117 * | | | | in y-x banded | | | | band 1
118 * | | | | form is | | | |
119 * ----------- | | ----------- --------
123 * An added constraint on the rectangles is that they must cover as much
124 * horizontal area as possible: no two rectangles within a band are allowed
127 * Whenever possible, bands will be merged together to cover a greater vertical
128 * distance (and thus reduce the number of rectangles). Two bands can be merged
129 * only if the bottom of one touches the top of the other and they have
130 * rectangles in the same places (of the same width, of course).
132 * Adam de Boor wrote most of the original region code. Joel McCormack
133 * substantially modified or rewrote most of the core arithmetic routines, and
134 * added pixman_region_validate in order to support several speed improvements to
135 * pixman_region_validateTree. Bob Scheifler changed the representation to be more
136 * compact when empty or a single rectangle, and did a bunch of gratuitous
137 * reformatting. Carl Worth did further gratuitous reformatting while re-merging
138 * the server and client region code into libpixregion.
141 /* true iff two Boxes overlap */
142 #define EXTENTCHECK(r1,r2) \
143 (!( ((r1)->x2 <= (r2)->x1) || \
144 ((r1)->x1 >= (r2)->x2) || \
145 ((r1)->y2 <= (r2)->y1) || \
146 ((r1)->y1 >= (r2)->y2) ) )
148 /* true iff (x,y) is in Box */
149 #define INBOX(r,x,y) \
155 /* true iff Box r1 contains Box r2 */
156 #define SUBSUMES(r1,r2) \
157 ( ((r1)->x1 <= (r2)->x1) && \
158 ((r1)->x2 >= (r2)->x2) && \
159 ((r1)->y1 <= (r2)->y1) && \
160 ((r1)->y2 >= (r2)->y2) )
163 PIXREGION_SZOF(size_t n)
165 size_t size = n * sizeof(box_type_t);
166 if (n > UINT32_MAX / sizeof(box_type_t))
169 if (sizeof(region_data_type_t) > UINT32_MAX - size)
172 return size + sizeof(region_data_type_t);
178 size_t sz = PIXREGION_SZOF(n);
185 #define freeData(reg) if ((reg)->data && (reg)->data->size) free((reg)->data)
187 #define RECTALLOC_BAIL(pReg,n,bail) \
188 if (!(pReg)->data || (((pReg)->data->numRects + (n)) > (pReg)->data->size)) \
189 if (!pixman_rect_alloc(pReg, n)) { goto bail; }
191 #define RECTALLOC(pReg,n) \
192 if (!(pReg)->data || (((pReg)->data->numRects + (n)) > (pReg)->data->size)) \
193 if (!pixman_rect_alloc(pReg, n)) { return FALSE; }
195 #define ADDRECT(pNextRect,nx1,ny1,nx2,ny2) \
197 pNextRect->x1 = nx1; \
198 pNextRect->y1 = ny1; \
199 pNextRect->x2 = nx2; \
200 pNextRect->y2 = ny2; \
204 #define NEWRECT(pReg,pNextRect,nx1,ny1,nx2,ny2) \
206 if (!(pReg)->data || ((pReg)->data->numRects == (pReg)->data->size))\
208 if (!pixman_rect_alloc(pReg, 1)) \
210 pNextRect = PIXREGION_TOP(pReg); \
212 ADDRECT(pNextRect,nx1,ny1,nx2,ny2); \
213 pReg->data->numRects++; \
214 assert(pReg->data->numRects<=pReg->data->size); \
217 #define DOWNSIZE(reg,numRects) \
218 if (((numRects) < ((reg)->data->size >> 1)) && ((reg)->data->size > 50)) \
220 region_data_type_t * NewData; \
221 size_t data_size = PIXREGION_SZOF(numRects); \
225 NewData = (region_data_type_t *)realloc((reg)->data, data_size); \
228 NewData->size = (numRects); \
229 (reg)->data = NewData; \
233 PIXMAN_EXPORT pixman_bool_t
234 PREFIX(_equal) (reg1, reg2)
235 region_type_t * reg1;
236 region_type_t * reg2;
242 if (reg1->extents.x1 != reg2->extents.x1) return FALSE;
243 if (reg1->extents.x2 != reg2->extents.x2) return FALSE;
244 if (reg1->extents.y1 != reg2->extents.y1) return FALSE;
245 if (reg1->extents.y2 != reg2->extents.y2) return FALSE;
246 if (PIXREGION_NUM_RECTS(reg1) != PIXREGION_NUM_RECTS(reg2)) return FALSE;
248 rects1 = PIXREGION_RECTS(reg1);
249 rects2 = PIXREGION_RECTS(reg2);
250 for (i = 0; i != PIXREGION_NUM_RECTS(reg1); i++) {
251 if (rects1[i].x1 != rects2[i].x1) return FALSE;
252 if (rects1[i].x2 != rects2[i].x2) return FALSE;
253 if (rects1[i].y1 != rects2[i].y1) return FALSE;
254 if (rects1[i].y2 != rects2[i].y2) return FALSE;
267 num = PIXREGION_NUM_RECTS(rgn);
268 size = PIXREGION_SIZE(rgn);
269 rects = PIXREGION_RECTS(rgn);
270 fprintf(stderr, "num: %d size: %d\n", num, size);
271 fprintf(stderr, "extents: %d %d %d %d\n",
272 rgn->extents.x1, rgn->extents.y1, rgn->extents.x2, rgn->extents.y2);
273 for (i = 0; i < num; i++)
274 fprintf(stderr, "%d %d %d %d \n",
275 rects[i].x1, rects[i].y1, rects[i].x2, rects[i].y2);
276 fprintf(stderr, "\n");
282 PREFIX(_init) (region_type_t *region)
284 region->extents = *pixman_region_emptyBox;
285 region->data = pixman_region_emptyData;
289 PREFIX(_init_rect) (region_type_t *region,
290 int x, int y, unsigned int width, unsigned int height)
292 region->extents.x1 = x;
293 region->extents.y1 = y;
294 region->extents.x2 = x + width;
295 region->extents.y2 = y + height;
300 PREFIX(_init_with_extents) (region_type_t *region, box_type_t *extents)
302 region->extents = *extents;
307 PREFIX(_fini) (region_type_t *region)
314 PREFIX(_n_rects) (region_type_t *region)
316 return PIXREGION_NUM_RECTS (region);
319 PIXMAN_EXPORT box_type_t *
320 PREFIX(_rectangles) (region_type_t *region,
324 *n_rects = PIXREGION_NUM_RECTS (region);
326 return PIXREGION_RECTS (region);
330 pixman_break (region_type_t *region)
333 region->extents = *pixman_region_emptyBox;
334 region->data = pixman_brokendata;
339 pixman_rect_alloc (region_type_t * region, int n)
341 region_data_type_t *data;
346 region->data = allocData(n);
348 return pixman_break (region);
349 region->data->numRects = 1;
350 *PIXREGION_BOXPTR(region) = region->extents;
352 else if (!region->data->size)
354 region->data = allocData(n);
356 return pixman_break (region);
357 region->data->numRects = 0;
364 n = region->data->numRects;
365 if (n > 500) /* XXX pick numbers out of a hat */
368 n += region->data->numRects;
369 data_size = PIXREGION_SZOF(n);
373 data = (region_data_type_t *)realloc(region->data, PIXREGION_SZOF(n));
375 return pixman_break (region);
378 region->data->size = n;
382 PIXMAN_EXPORT pixman_bool_t
383 PREFIX(_copy) (region_type_t *dst, region_type_t *src)
389 dst->extents = src->extents;
390 if (!src->data || !src->data->size)
393 dst->data = src->data;
396 if (!dst->data || (dst->data->size < src->data->numRects))
399 dst->data = allocData(src->data->numRects);
401 return pixman_break (dst);
402 dst->data->size = src->data->numRects;
404 dst->data->numRects = src->data->numRects;
405 memmove((char *)PIXREGION_BOXPTR(dst),(char *)PIXREGION_BOXPTR(src),
406 dst->data->numRects * sizeof(box_type_t));
410 /*======================================================================
411 * Generic Region Operator
412 *====================================================================*/
415 *-----------------------------------------------------------------------
417 * Attempt to merge the boxes in the current band with those in the
418 * previous one. We are guaranteed that the current band extends to
419 * the end of the rects array. Used only by pixman_op.
422 * The new index for the previous band.
425 * If coalescing takes place:
426 * - rectangles in the previous band will have their y2 fields
428 * - region->data->numRects will be decreased.
430 *-----------------------------------------------------------------------
434 region_type_t * region, /* Region to coalesce */
435 int prevStart, /* Index of start of previous band */
436 int curStart) /* Index of start of current band */
438 box_type_t * pPrevBox; /* Current box in previous band */
439 box_type_t * pCurBox; /* Current box in current band */
440 int numRects; /* Number rectangles in both bands */
441 int y2; /* Bottom of current band */
443 * Figure out how many rectangles are in the band.
445 numRects = curStart - prevStart;
446 assert(numRects == region->data->numRects - curStart);
448 if (!numRects) return curStart;
451 * The bands may only be coalesced if the bottom of the previous
452 * matches the top scanline of the current.
454 pPrevBox = PIXREGION_BOX(region, prevStart);
455 pCurBox = PIXREGION_BOX(region, curStart);
456 if (pPrevBox->y2 != pCurBox->y1) return curStart;
459 * Make sure the bands have boxes in the same places. This
460 * assumes that boxes have been added in such a way that they
461 * cover the most area possible. I.e. two boxes in a band must
462 * have some horizontal space between them.
467 if ((pPrevBox->x1 != pCurBox->x1) || (pPrevBox->x2 != pCurBox->x2)) {
476 * The bands may be merged, so set the bottom y of each box
477 * in the previous band to the bottom y of the current band.
479 numRects = curStart - prevStart;
480 region->data->numRects -= numRects;
489 /* Quicky macro to avoid trivial reject procedure calls to pixman_coalesce */
491 #define Coalesce(newReg, prevBand, curBand) \
492 if (curBand - prevBand == newReg->data->numRects - curBand) { \
493 prevBand = pixman_coalesce(newReg, prevBand, curBand); \
495 prevBand = curBand; \
499 *-----------------------------------------------------------------------
500 * pixman_region_appendNonO --
501 * Handle a non-overlapping band for the union and subtract operations.
502 * Just adds the (top/bottom-clipped) rectangles into the region.
503 * Doesn't have to check for subsumption or anything.
509 * region->data->numRects is incremented and the rectangles overwritten
510 * with the rectangles we're passed.
512 *-----------------------------------------------------------------------
515 static inline pixman_bool_t
516 pixman_region_appendNonO (
517 region_type_t * region,
523 box_type_t * pNextRect;
529 assert(newRects != 0);
531 /* Make sure we have enough space for all rectangles to be added */
532 RECTALLOC(region, newRects);
533 pNextRect = PIXREGION_TOP(region);
534 region->data->numRects += newRects;
536 assert(r->x1 < r->x2);
537 ADDRECT(pNextRect, r->x1, y1, r->x2, y2);
544 #define FindBand(r, rBandEnd, rEnd, ry1) \
548 while ((rBandEnd != rEnd) && (rBandEnd->y1 == ry1)) { \
553 #define AppendRegions(newReg, r, rEnd) \
556 if ((newRects = rEnd - r)) { \
557 RECTALLOC_BAIL(newReg, newRects, bail); \
558 memmove((char *)PIXREGION_TOP(newReg),(char *)r, \
559 newRects * sizeof(box_type_t)); \
560 newReg->data->numRects += newRects; \
565 *-----------------------------------------------------------------------
567 * Apply an operation to two regions. Called by pixman_region_union, pixman_region_inverse,
568 * pixman_region_subtract, pixman_region_intersect.... Both regions MUST have at least one
569 * rectangle, and cannot be the same object.
572 * TRUE if successful.
575 * The new region is overwritten.
576 * pOverlap set to TRUE if overlapFunc ever returns TRUE.
579 * The idea behind this function is to view the two regions as sets.
580 * Together they cover a rectangle of area that this function divides
581 * into horizontal bands where points are covered only by one region
582 * or by both. For the first case, the nonOverlapFunc is called with
583 * each the band and the band's upper and lower extents. For the
584 * second, the overlapFunc is called to process the entire band. It
585 * is responsible for clipping the rectangles in the band, though
586 * this function provides the boundaries.
587 * At the end of each band, the new region is coalesced, if possible,
588 * to reduce the number of rectangles in the region.
590 *-----------------------------------------------------------------------
593 typedef pixman_bool_t (*OverlapProcPtr)(
594 region_type_t *region,
605 region_type_t *newReg, /* Place to store result */
606 region_type_t * reg1, /* First region in operation */
607 region_type_t * reg2, /* 2d region in operation */
608 OverlapProcPtr overlapFunc, /* Function to call for over-
610 int appendNon1, /* Append non-overlapping bands */
612 int appendNon2, /* Append non-overlapping bands */
616 box_type_t * r1; /* Pointer into first region */
617 box_type_t * r2; /* Pointer into 2d region */
618 box_type_t * r1End; /* End of 1st region */
619 box_type_t * r2End; /* End of 2d region */
620 int ybot; /* Bottom of intersection */
621 int ytop; /* Top of intersection */
622 region_data_type_t * oldData; /* Old data for newReg */
623 int prevBand; /* Index of start of
624 * previous band in newReg */
625 int curBand; /* Index of start of current
627 box_type_t * r1BandEnd; /* End of current band in r1 */
628 box_type_t * r2BandEnd; /* End of current band in r2 */
629 int top; /* Top of non-overlapping band */
630 int bot; /* Bottom of non-overlapping band*/
631 int r1y1; /* Temps for r1->y1 and r2->y1 */
637 * Break any region computed from a broken region
639 if (PIXREGION_NAR (reg1) || PIXREGION_NAR(reg2))
640 return pixman_break (newReg);
644 * set r1, r2, r1End and r2End appropriately, save the rectangles
645 * of the destination region until the end in case it's one of
646 * the two source regions, then mark the "new" region empty, allocating
647 * another array of rectangles for it to use.
650 r1 = PIXREGION_RECTS(reg1);
651 newSize = PIXREGION_NUM_RECTS(reg1);
652 r1End = r1 + newSize;
653 numRects = PIXREGION_NUM_RECTS(reg2);
654 r2 = PIXREGION_RECTS(reg2);
655 r2End = r2 + numRects;
659 oldData = (region_data_type_t *)NULL;
660 if (((newReg == reg1) && (newSize > 1)) ||
661 ((newReg == reg2) && (numRects > 1)))
663 oldData = newReg->data;
664 newReg->data = pixman_region_emptyData;
666 /* guess at new size */
667 if (numRects > newSize)
671 newReg->data = pixman_region_emptyData;
672 else if (newReg->data->size)
673 newReg->data->numRects = 0;
674 if (newSize > newReg->data->size) {
675 if (!pixman_rect_alloc(newReg, newSize)) {
684 * In the upcoming loop, ybot and ytop serve different functions depending
685 * on whether the band being handled is an overlapping or non-overlapping
687 * In the case of a non-overlapping band (only one of the regions
688 * has points in the band), ybot is the bottom of the most recent
689 * intersection and thus clips the top of the rectangles in that band.
690 * ytop is the top of the next intersection between the two regions and
691 * serves to clip the bottom of the rectangles in the current band.
692 * For an overlapping band (where the two regions intersect), ytop clips
693 * the top of the rectangles of both regions and ybot clips the bottoms.
696 ybot = MIN(r1->y1, r2->y1);
699 * prevBand serves to mark the start of the previous band so rectangles
700 * can be coalesced into larger rectangles. qv. pixman_coalesce, above.
701 * In the beginning, there is no previous band, so prevBand == curBand
702 * (curBand is set later on, of course, but the first band will always
703 * start at index 0). prevBand and curBand must be indices because of
704 * the possible expansion, and resultant moving, of the new region's
705 * array of rectangles.
711 * This algorithm proceeds one source-band (as opposed to a
712 * destination band, which is determined by where the two regions
713 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
714 * rectangle after the last one in the current band for their
715 * respective regions.
720 FindBand(r1, r1BandEnd, r1End, r1y1);
721 FindBand(r2, r2BandEnd, r2End, r2y1);
724 * First handle the band that doesn't intersect, if any.
726 * Note that attention is restricted to one band in the
727 * non-intersecting region at once, so if a region has n
728 * bands between the current position and the next place it overlaps
729 * the other, this entire loop will be passed through n times.
733 top = MAX(r1y1, ybot);
734 bot = MIN(r1->y2, r2y1);
736 curBand = newReg->data->numRects;
737 if (!pixman_region_appendNonO(newReg, r1, r1BandEnd, top, bot))
739 Coalesce(newReg, prevBand, curBand);
743 } else if (r2y1 < r1y1) {
745 top = MAX(r2y1, ybot);
746 bot = MIN(r2->y2, r1y1);
748 curBand = newReg->data->numRects;
749 if (!pixman_region_appendNonO(newReg, r2, r2BandEnd, top, bot))
751 Coalesce(newReg, prevBand, curBand);
760 * Now see if we've hit an intersecting band. The two bands only
761 * intersect if ybot > ytop
763 ybot = MIN(r1->y2, r2->y2);
765 curBand = newReg->data->numRects;
766 if (!(* overlapFunc)(newReg,
772 Coalesce(newReg, prevBand, curBand);
776 * If we've finished with a band (y2 == ybot) we skip forward
777 * in the region to the next band.
779 if (r1->y2 == ybot) r1 = r1BandEnd;
780 if (r2->y2 == ybot) r2 = r2BandEnd;
782 } while (r1 != r1End && r2 != r2End);
785 * Deal with whichever region (if any) still has rectangles left.
787 * We only need to worry about banding and coalescing for the very first
788 * band left. After that, we can just group all remaining boxes,
789 * regardless of how many bands, into one final append to the list.
792 if ((r1 != r1End) && appendNon1) {
793 /* Do first nonOverlap1Func call, which may be able to coalesce */
794 FindBand(r1, r1BandEnd, r1End, r1y1);
795 curBand = newReg->data->numRects;
796 if (!pixman_region_appendNonO(newReg,
798 MAX(r1y1, ybot), r1->y2))
800 Coalesce(newReg, prevBand, curBand);
801 /* Just append the rest of the boxes */
802 AppendRegions(newReg, r1BandEnd, r1End);
804 } else if ((r2 != r2End) && appendNon2) {
805 /* Do first nonOverlap2Func call, which may be able to coalesce */
806 FindBand(r2, r2BandEnd, r2End, r2y1);
807 curBand = newReg->data->numRects;
808 if (!pixman_region_appendNonO(newReg,
810 MAX(r2y1, ybot), r2->y2))
812 Coalesce(newReg, prevBand, curBand);
813 /* Append rest of boxes */
814 AppendRegions(newReg, r2BandEnd, r2End);
820 if (!(numRects = newReg->data->numRects))
823 newReg->data = pixman_region_emptyData;
825 else if (numRects == 1)
827 newReg->extents = *PIXREGION_BOXPTR(newReg);
829 newReg->data = (region_data_type_t *)NULL;
833 DOWNSIZE(newReg, numRects);
841 return pixman_break (newReg);
845 *-----------------------------------------------------------------------
846 * pixman_set_extents --
847 * Reset the extents of a region to what they should be. Called by
848 * pixman_region_subtract and pixman_region_intersect as they can't figure it out along the
849 * way or do so easily, as pixman_region_union can.
855 * The region's 'extents' structure is overwritten.
857 *-----------------------------------------------------------------------
860 pixman_set_extents (region_type_t *region)
862 box_type_t *box, *boxEnd;
866 if (!region->data->size)
868 region->extents.x2 = region->extents.x1;
869 region->extents.y2 = region->extents.y1;
873 box = PIXREGION_BOXPTR(region);
874 boxEnd = PIXREGION_END(region);
877 * Since box is the first rectangle in the region, it must have the
878 * smallest y1 and since boxEnd is the last rectangle in the region,
879 * it must have the largest y2, because of banding. Initialize x1 and
880 * x2 from box and boxEnd, resp., as good things to initialize them
883 region->extents.x1 = box->x1;
884 region->extents.y1 = box->y1;
885 region->extents.x2 = boxEnd->x2;
886 region->extents.y2 = boxEnd->y2;
888 assert(region->extents.y1 < region->extents.y2);
889 while (box <= boxEnd) {
890 if (box->x1 < region->extents.x1)
891 region->extents.x1 = box->x1;
892 if (box->x2 > region->extents.x2)
893 region->extents.x2 = box->x2;
897 assert(region->extents.x1 < region->extents.x2);
900 /*======================================================================
901 * Region Intersection
902 *====================================================================*/
904 *-----------------------------------------------------------------------
905 * pixman_region_intersectO --
906 * Handle an overlapping band for pixman_region_intersect.
909 * TRUE if successful.
912 * Rectangles may be added to the region.
914 *-----------------------------------------------------------------------
918 pixman_region_intersectO (region_type_t *region,
929 box_type_t * pNextRect;
931 pNextRect = PIXREGION_TOP(region);
934 assert(r1 != r1End && r2 != r2End);
937 x1 = MAX(r1->x1, r2->x1);
938 x2 = MIN(r1->x2, r2->x2);
941 * If there's any overlap between the two rectangles, add that
942 * overlap to the new region.
945 NEWRECT(region, pNextRect, x1, y1, x2, y2);
948 * Advance the pointer(s) with the leftmost right side, since the next
949 * rectangle on that list may still overlap the other region's
958 } while ((r1 != r1End) && (r2 != r2End));
963 PIXMAN_EXPORT pixman_bool_t
964 PREFIX(_intersect) (region_type_t * newReg,
965 region_type_t * reg1,
966 region_type_t * reg2)
971 /* check for trivial reject */
972 if (PIXREGION_NIL(reg1) || PIXREGION_NIL(reg2) ||
973 !EXTENTCHECK(®1->extents, ®2->extents))
975 /* Covers about 20% of all cases */
977 newReg->extents.x2 = newReg->extents.x1;
978 newReg->extents.y2 = newReg->extents.y1;
979 if (PIXREGION_NAR(reg1) || PIXREGION_NAR(reg2))
981 newReg->data = pixman_brokendata;
985 newReg->data = pixman_region_emptyData;
987 else if (!reg1->data && !reg2->data)
989 /* Covers about 80% of cases that aren't trivially rejected */
990 newReg->extents.x1 = MAX(reg1->extents.x1, reg2->extents.x1);
991 newReg->extents.y1 = MAX(reg1->extents.y1, reg2->extents.y1);
992 newReg->extents.x2 = MIN(reg1->extents.x2, reg2->extents.x2);
993 newReg->extents.y2 = MIN(reg1->extents.y2, reg2->extents.y2);
995 newReg->data = (region_data_type_t *)NULL;
997 else if (!reg2->data && SUBSUMES(®2->extents, ®1->extents))
999 return PREFIX(_copy) (newReg, reg1);
1001 else if (!reg1->data && SUBSUMES(®1->extents, ®2->extents))
1003 return PREFIX(_copy) (newReg, reg2);
1005 else if (reg1 == reg2)
1007 return PREFIX(_copy) (newReg, reg1);
1011 /* General purpose intersection */
1012 int overlap; /* result ignored */
1013 if (!pixman_op(newReg, reg1, reg2, pixman_region_intersectO, FALSE, FALSE,
1016 pixman_set_extents(newReg);
1023 #define MERGERECT(r) \
1025 if (r->x1 <= x2) { \
1026 /* Merge with current rectangle */ \
1027 if (r->x1 < x2) *pOverlap = TRUE; \
1028 if (x2 < r->x2) x2 = r->x2; \
1030 /* Add current rectangle, start new one */ \
1031 NEWRECT(region, pNextRect, x1, y1, x2, y2); \
1038 /*======================================================================
1040 *====================================================================*/
1043 *-----------------------------------------------------------------------
1044 * pixman_region_unionO --
1045 * Handle an overlapping band for the union operation. Picks the
1046 * left-most rectangle each time and merges it into the region.
1049 * TRUE if successful.
1052 * region is overwritten.
1053 * pOverlap is set to TRUE if any boxes overlap.
1055 *-----------------------------------------------------------------------
1057 static pixman_bool_t
1058 pixman_region_unionO (
1059 region_type_t *region,
1068 box_type_t * pNextRect;
1069 int x1; /* left and right side of current union */
1073 assert(r1 != r1End && r2 != r2End);
1075 pNextRect = PIXREGION_TOP(region);
1077 /* Start off current rectangle */
1078 if (r1->x1 < r2->x1)
1090 while (r1 != r1End && r2 != r2End)
1092 if (r1->x1 < r2->x1) MERGERECT(r1) else MERGERECT(r2);
1095 /* Finish off whoever (if any) is left */
1101 } while (r1 != r1End);
1103 else if (r2 != r2End)
1108 } while (r2 != r2End);
1111 /* Add current rectangle */
1112 NEWRECT(region, pNextRect, x1, y1, x2, y2);
1117 /* Convenience function for performing union of region with a
1120 PIXMAN_EXPORT pixman_bool_t
1121 PREFIX(_union_rect) (region_type_t *dest,
1122 region_type_t *source,
1124 unsigned int width, unsigned int height)
1126 region_type_t region;
1128 if (!width || !height)
1129 return PREFIX(_copy) (dest, source);
1131 region.extents.x1 = x;
1132 region.extents.y1 = y;
1133 region.extents.x2 = x + width;
1134 region.extents.y2 = y + height;
1136 return PREFIX(_union) (dest, source, ®ion);
1139 PIXMAN_EXPORT pixman_bool_t
1140 PREFIX(_union) (region_type_t *newReg,
1141 region_type_t *reg1,
1142 region_type_t *reg2)
1144 int overlap; /* result ignored */
1146 /* Return TRUE if some overlap
1147 * between reg1, reg2
1152 /* checks all the simple cases */
1155 * Region 1 and 2 are the same
1159 return PREFIX(_copy) (newReg, reg1);
1165 if (PIXREGION_NIL(reg1))
1167 if (PIXREGION_NAR(reg1))
1168 return pixman_break (newReg);
1170 return PREFIX(_copy) (newReg, reg2);
1177 if (PIXREGION_NIL(reg2))
1179 if (PIXREGION_NAR(reg2))
1180 return pixman_break (newReg);
1182 return PREFIX(_copy) (newReg, reg1);
1187 * Region 1 completely subsumes region 2
1189 if (!reg1->data && SUBSUMES(®1->extents, ®2->extents))
1192 return PREFIX(_copy) (newReg, reg1);
1197 * Region 2 completely subsumes region 1
1199 if (!reg2->data && SUBSUMES(®2->extents, ®1->extents))
1202 return PREFIX(_copy) (newReg, reg2);
1206 if (!pixman_op(newReg, reg1, reg2, pixman_region_unionO, TRUE, TRUE, &overlap))
1209 newReg->extents.x1 = MIN(reg1->extents.x1, reg2->extents.x1);
1210 newReg->extents.y1 = MIN(reg1->extents.y1, reg2->extents.y1);
1211 newReg->extents.x2 = MAX(reg1->extents.x2, reg2->extents.x2);
1212 newReg->extents.y2 = MAX(reg1->extents.y2, reg2->extents.y2);
1217 /*======================================================================
1218 * Batch Rectangle Union
1219 *====================================================================*/
1221 #define ExchangeRects(a, b) \
1225 rects[a] = rects[b]; \
1239 /* Always called with numRects > 1 */
1245 if (rects[0].y1 > rects[1].y1 ||
1246 (rects[0].y1 == rects[1].y1 && rects[0].x1 > rects[1].x1))
1247 ExchangeRects(0, 1);
1251 /* Choose partition element, stick in location 0 */
1252 ExchangeRects(0, numRects >> 1);
1256 /* Partition array */
1266 } while (i != numRects &&
1267 (r->y1 < y1 || (r->y1 == y1 && r->x1 < x1)));
1273 } while (y1 < r->y1 || (y1 == r->y1 && x1 < r->x1));
1275 ExchangeRects(i, j);
1278 /* Move partition element back to middle */
1279 ExchangeRects(0, j);
1282 if (numRects-j-1 > 1)
1283 QuickSortRects(&rects[j+1], numRects-j-1);
1285 } while (numRects > 1);
1289 *-----------------------------------------------------------------------
1290 * pixman_region_validate --
1292 * Take a ``region'' which is a non-y-x-banded random collection of
1293 * rectangles, and compute a nice region which is the union of all the
1297 * TRUE if successful.
1300 * The passed-in ``region'' may be modified.
1301 * pOverlap set to TRUE if any retangles overlapped,
1305 * Step 1. Sort the rectangles into ascending order with primary key y1
1306 * and secondary key x1.
1308 * Step 2. Split the rectangles into the minimum number of proper y-x
1309 * banded regions. This may require horizontally merging
1310 * rectangles, and vertically coalescing bands. With any luck,
1311 * this step in an identity transformation (ala the Box widget),
1312 * or a coalescing into 1 box (ala Menus).
1314 * Step 3. Merge the separate regions down to a single region by calling
1315 * pixman_region_union. Maximize the work each pixman_region_union call does by using
1318 *-----------------------------------------------------------------------
1321 static pixman_bool_t
1322 validate (region_type_t * badreg,
1325 /* Descriptor for regions under construction in Step 2. */
1332 RegionInfo stack_regions[64];
1334 int numRects; /* Original numRects for badreg */
1335 RegionInfo *ri; /* Array of current regions */
1336 int numRI; /* Number of entries used in ri */
1337 int sizeRI; /* Number of entries available in ri */
1338 int i; /* Index into rects */
1339 int j; /* Index into ri */
1340 RegionInfo *rit; /* &ri[j] */
1341 region_type_t * reg; /* ri[j].reg */
1342 box_type_t * box; /* Current box in rects */
1343 box_type_t * riBox; /* Last box in ri[j].reg */
1344 region_type_t * hreg; /* ri[j_half].reg */
1345 pixman_bool_t ret = TRUE;
1353 numRects = badreg->data->numRects;
1356 if (PIXREGION_NAR(badreg))
1361 if (badreg->extents.x1 < badreg->extents.x2)
1363 if ((numRects) == 1)
1366 badreg->data = (region_data_type_t *) NULL;
1370 DOWNSIZE(badreg, numRects);
1376 /* Step 1: Sort the rects array into ascending (y1, x1) order */
1377 QuickSortRects(PIXREGION_BOXPTR(badreg), numRects);
1379 /* Step 2: Scatter the sorted array into the minimum number of regions */
1381 /* Set up the first region to be the first rectangle in badreg */
1382 /* Note that step 2 code will never overflow the ri[0].reg rects array */
1384 sizeRI = sizeof (stack_regions) / sizeof (stack_regions[0]);
1388 ri[0].reg = *badreg;
1389 box = PIXREGION_BOXPTR(&ri[0].reg);
1390 ri[0].reg.extents = *box;
1391 ri[0].reg.data->numRects = 1;
1392 badreg->extents = *pixman_region_emptyBox;
1393 badreg->data = pixman_region_emptyData;
1395 /* Now scatter rectangles into the minimum set of valid regions. If the
1396 next rectangle to be added to a region would force an existing rectangle
1397 in the region to be split up in order to maintain y-x banding, just
1398 forget it. Try the next region. If it doesn't fit cleanly into any
1399 region, make a new one. */
1401 for (i = numRects; --i > 0;)
1404 /* Look for a region to append box to */
1405 for (j = numRI, rit = ri; --j >= 0; rit++)
1408 riBox = PIXREGION_END(reg);
1410 if (box->y1 == riBox->y1 && box->y2 == riBox->y2)
1412 /* box is in same band as riBox. Merge or append it */
1413 if (box->x1 <= riBox->x2)
1415 /* Merge it with riBox */
1416 if (box->x1 < riBox->x2) *pOverlap = TRUE;
1417 if (box->x2 > riBox->x2) riBox->x2 = box->x2;
1421 RECTALLOC_BAIL(reg, 1, bail);
1422 *PIXREGION_TOP(reg) = *box;
1423 reg->data->numRects++;
1425 goto NextRect; /* So sue me */
1427 else if (box->y1 >= riBox->y2)
1429 /* Put box into new band */
1430 if (reg->extents.x2 < riBox->x2) reg->extents.x2 = riBox->x2;
1431 if (reg->extents.x1 > box->x1) reg->extents.x1 = box->x1;
1432 Coalesce(reg, rit->prevBand, rit->curBand);
1433 rit->curBand = reg->data->numRects;
1434 RECTALLOC_BAIL(reg, 1, bail);
1435 *PIXREGION_TOP(reg) = *box;
1436 reg->data->numRects++;
1439 /* Well, this region was inappropriate. Try the next one. */
1442 /* Uh-oh. No regions were appropriate. Create a new one. */
1443 if (sizeRI == numRI)
1447 /* Oops, allocate space for new region information */
1450 data_size = sizeRI * sizeof(RegionInfo);
1451 if (data_size / sizeRI != sizeof(RegionInfo))
1453 if (ri == stack_regions) {
1454 rit = malloc (data_size);
1457 memcpy (rit, ri, numRI * sizeof (RegionInfo));
1459 rit = (RegionInfo *) realloc(ri, data_size);
1469 rit->reg.extents = *box;
1470 rit->reg.data = (region_data_type_t *)NULL;
1471 if (!pixman_rect_alloc(&rit->reg, (i+numRI) / numRI)) /* MUST force allocation */
1476 /* Make a final pass over each region in order to Coalesce and set
1477 extents.x2 and extents.y2 */
1479 for (j = numRI, rit = ri; --j >= 0; rit++)
1482 riBox = PIXREGION_END(reg);
1483 reg->extents.y2 = riBox->y2;
1484 if (reg->extents.x2 < riBox->x2) reg->extents.x2 = riBox->x2;
1485 Coalesce(reg, rit->prevBand, rit->curBand);
1486 if (reg->data->numRects == 1) /* keep unions happy below */
1489 reg->data = (region_data_type_t *)NULL;
1493 /* Step 3: Union all regions into a single region */
1497 for (j = numRI & 1; j < (half + (numRI & 1)); j++)
1500 hreg = &ri[j+half].reg;
1501 if (!pixman_op(reg, reg, hreg, pixman_region_unionO, TRUE, TRUE, pOverlap))
1503 if (hreg->extents.x1 < reg->extents.x1)
1504 reg->extents.x1 = hreg->extents.x1;
1505 if (hreg->extents.y1 < reg->extents.y1)
1506 reg->extents.y1 = hreg->extents.y1;
1507 if (hreg->extents.x2 > reg->extents.x2)
1508 reg->extents.x2 = hreg->extents.x2;
1509 if (hreg->extents.y2 > reg->extents.y2)
1510 reg->extents.y2 = hreg->extents.y2;
1517 *badreg = ri[0].reg;
1518 if (ri != stack_regions)
1523 for (i = 0; i < numRI; i++)
1524 freeData(&ri[i].reg);
1525 if (ri != stack_regions)
1528 return pixman_break (badreg);
1531 /*======================================================================
1532 * Region Subtraction
1533 *====================================================================*/
1536 *-----------------------------------------------------------------------
1537 * pixman_region_subtractO --
1538 * Overlapping band subtraction. x1 is the left-most point not yet
1542 * TRUE if successful.
1545 * region may have rectangles added to it.
1547 *-----------------------------------------------------------------------
1550 static pixman_bool_t
1551 pixman_region_subtractO (
1552 region_type_t * region,
1561 box_type_t * pNextRect;
1567 assert(r1 != r1End && r2 != r2End);
1569 pNextRect = PIXREGION_TOP(region);
1576 * Subtrahend entirely to left of minuend: go to next subtrahend.
1580 else if (r2->x1 <= x1)
1583 * Subtrahend preceeds minuend: nuke left edge of minuend.
1589 * Minuend completely covered: advance to next minuend and
1590 * reset left fence to edge of new minuend.
1599 * Subtrahend now used up since it doesn't extend beyond
1605 else if (r2->x1 < r1->x2)
1608 * Left part of subtrahend covers part of minuend: add uncovered
1609 * part of minuend to region and skip to next subtrahend.
1612 NEWRECT(region, pNextRect, x1, y1, r2->x1, y2);
1618 * Minuend used up: advance to new...
1627 * Subtrahend used up
1635 * Minuend used up: add any remaining piece before advancing.
1638 NEWRECT(region, pNextRect, x1, y1, r1->x2, y2);
1643 } while ((r1 != r1End) && (r2 != r2End));
1646 * Add remaining minuend rectangles to region.
1651 NEWRECT(region, pNextRect, x1, y1, r1->x2, y2);
1660 *-----------------------------------------------------------------------
1661 * pixman_region_subtract --
1662 * Subtract regS from regM and leave the result in regD.
1663 * S stands for subtrahend, M for minuend and D for difference.
1666 * TRUE if successful.
1669 * regD is overwritten.
1671 *-----------------------------------------------------------------------
1673 PIXMAN_EXPORT pixman_bool_t
1674 PREFIX(_subtract) (region_type_t * regD,
1675 region_type_t * regM,
1676 region_type_t * regS)
1678 int overlap; /* result ignored */
1683 /* check for trivial rejects */
1684 if (PIXREGION_NIL(regM) || PIXREGION_NIL(regS) ||
1685 !EXTENTCHECK(®M->extents, ®S->extents))
1687 if (PIXREGION_NAR (regS))
1688 return pixman_break (regD);
1689 return PREFIX(_copy) (regD, regM);
1691 else if (regM == regS)
1694 regD->extents.x2 = regD->extents.x1;
1695 regD->extents.y2 = regD->extents.y1;
1696 regD->data = pixman_region_emptyData;
1700 /* Add those rectangles in region 1 that aren't in region 2,
1701 do yucky substraction for overlaps, and
1702 just throw away rectangles in region 2 that aren't in region 1 */
1703 if (!pixman_op(regD, regM, regS, pixman_region_subtractO, TRUE, FALSE, &overlap))
1707 * Can't alter RegD's extents before we call pixman_op because
1708 * it might be one of the source regions and pixman_op depends
1709 * on the extents of those regions being unaltered. Besides, this
1710 * way there's no checking against rectangles that will be nuked
1711 * due to coalescing, so we have to examine fewer rectangles.
1713 pixman_set_extents(regD);
1718 /*======================================================================
1720 *====================================================================*/
1723 *-----------------------------------------------------------------------
1724 * pixman_region_inverse --
1725 * Take a region and a box and return a region that is everything
1726 * in the box but not in the region. The careful reader will note
1727 * that this is the same as subtracting the region from the box...
1733 * newReg is overwritten.
1735 *-----------------------------------------------------------------------
1738 PIXMAN_EXPORT PREFIX(_inverse) (region_type_t * newReg, /* Destination region */
1739 region_type_t * reg1, /* Region to invert */
1740 box_type_t * invRect) /* Bounding box for inversion */
1742 region_type_t invReg; /* Quick and dirty region made from the
1744 int overlap; /* result ignored */
1748 /* check for trivial rejects */
1749 if (PIXREGION_NIL(reg1) || !EXTENTCHECK(invRect, ®1->extents))
1751 if (PIXREGION_NAR(reg1))
1752 return pixman_break (newReg);
1753 newReg->extents = *invRect;
1755 newReg->data = (region_data_type_t *)NULL;
1759 /* Add those rectangles in region 1 that aren't in region 2,
1760 do yucky substraction for overlaps, and
1761 just throw away rectangles in region 2 that aren't in region 1 */
1762 invReg.extents = *invRect;
1763 invReg.data = (region_data_type_t *)NULL;
1764 if (!pixman_op(newReg, &invReg, reg1, pixman_region_subtractO, TRUE, FALSE, &overlap))
1768 * Can't alter newReg's extents before we call pixman_op because
1769 * it might be one of the source regions and pixman_op depends
1770 * on the extents of those regions being unaltered. Besides, this
1771 * way there's no checking against rectangles that will be nuked
1772 * due to coalescing, so we have to examine fewer rectangles.
1774 pixman_set_extents(newReg);
1780 * RectIn(region, rect)
1781 * This routine takes a pointer to a region and a pointer to a box
1782 * and determines if the box is outside/inside/partly inside the region.
1784 * The idea is to travel through the list of rectangles trying to cover the
1785 * passed box with them. Anytime a piece of the rectangle isn't covered
1786 * by a band of rectangles, partOut is set TRUE. Any time a rectangle in
1787 * the region covers part of the box, partIn is set TRUE. The process ends
1788 * when either the box has been completely covered (we reached a band that
1789 * doesn't overlap the box, partIn is TRUE and partOut is false), the
1790 * box has been partially covered (partIn == partOut == TRUE -- because of
1791 * the banding, the first time this is true we know the box is only
1792 * partially in the region) or is outside the region (we reached a band
1793 * that doesn't overlap the box at all and partIn is false)
1796 pixman_region_overlap_t
1797 PIXMAN_EXPORT PREFIX(_contains_rectangle) (region_type_t * region,
1803 box_type_t * pboxEnd;
1804 int partIn, partOut;
1808 numRects = PIXREGION_NUM_RECTS(region);
1809 /* useful optimization */
1810 if (!numRects || !EXTENTCHECK(®ion->extents, prect))
1811 return(PIXMAN_REGION_OUT);
1815 /* We know that it must be PIXMAN_REGION_IN or PIXMAN_REGION_PART */
1816 if (SUBSUMES(®ion->extents, prect))
1817 return(PIXMAN_REGION_IN);
1819 return(PIXMAN_REGION_PART);
1825 /* (x,y) starts at upper left of rect, moving to the right and down */
1829 /* can stop when both partOut and partIn are TRUE, or we reach prect->y2 */
1830 for (pbox = PIXREGION_BOXPTR(region), pboxEnd = pbox + numRects;
1836 continue; /* getting up to speed or skipping remainder of band */
1840 partOut = TRUE; /* missed part of rectangle above */
1841 if (partIn || (pbox->y1 >= prect->y2))
1843 y = pbox->y1; /* x guaranteed to be == prect->x1 */
1847 continue; /* not far enough over yet */
1851 partOut = TRUE; /* missed part of rectangle to left */
1856 if (pbox->x1 < prect->x2)
1858 partIn = TRUE; /* definitely overlap */
1863 if (pbox->x2 >= prect->x2)
1865 y = pbox->y2; /* finished with this band */
1868 x = prect->x1; /* reset x out to left again */
1873 * Because boxes in a band are maximal width, if the first box
1874 * to overlap the rectangle doesn't completely cover it in that
1875 * band, the rectangle must be partially out, since some of it
1876 * will be uncovered in that band. partIn will have been set true
1887 return PIXMAN_REGION_PART;
1889 return PIXMAN_REGION_IN;
1893 return PIXMAN_REGION_OUT;
1897 /* PREFIX(_translate) (region, x, y)
1902 PREFIX(_translate) (region_type_t * region, int x, int y)
1909 region->extents.x1 = x1 = region->extents.x1 + x;
1910 region->extents.y1 = y1 = region->extents.y1 + y;
1911 region->extents.x2 = x2 = region->extents.x2 + x;
1912 region->extents.y2 = y2 = region->extents.y2 + y;
1913 if (((x1 - SHRT_MIN)|(y1 - SHRT_MIN)|(SHRT_MAX - x2)|(SHRT_MAX - y2)) >= 0)
1915 if (region->data && (nbox = region->data->numRects))
1917 for (pbox = PIXREGION_BOXPTR(region); nbox--; pbox++)
1927 if (((x2 - SHRT_MIN)|(y2 - SHRT_MIN)|(SHRT_MAX - x1)|(SHRT_MAX - y1)) <= 0)
1929 region->extents.x2 = region->extents.x1;
1930 region->extents.y2 = region->extents.y1;
1932 region->data = pixman_region_emptyData;
1936 region->extents.x1 = SHRT_MIN;
1937 else if (x2 > SHRT_MAX)
1938 region->extents.x2 = SHRT_MAX;
1940 region->extents.y1 = SHRT_MIN;
1941 else if (y2 > SHRT_MAX)
1942 region->extents.y2 = SHRT_MAX;
1943 if (region->data && (nbox = region->data->numRects))
1945 box_type_t * pboxout;
1947 for (pboxout = pbox = PIXREGION_BOXPTR(region); nbox--; pbox++)
1949 pboxout->x1 = x1 = pbox->x1 + x;
1950 pboxout->y1 = y1 = pbox->y1 + y;
1951 pboxout->x2 = x2 = pbox->x2 + x;
1952 pboxout->y2 = y2 = pbox->y2 + y;
1953 if (((x2 - SHRT_MIN)|(y2 - SHRT_MIN)|
1954 (SHRT_MAX - x1)|(SHRT_MAX - y1)) <= 0)
1956 region->data->numRects--;
1960 pboxout->x1 = SHRT_MIN;
1961 else if (x2 > SHRT_MAX)
1962 pboxout->x2 = SHRT_MAX;
1964 pboxout->y1 = SHRT_MIN;
1965 else if (y2 > SHRT_MAX)
1966 pboxout->y2 = SHRT_MAX;
1969 if (pboxout != pbox)
1971 if (region->data->numRects == 1)
1973 region->extents = *PIXREGION_BOXPTR(region);
1975 region->data = (region_data_type_t *)NULL;
1978 pixman_set_extents(region);
1984 PREFIX(_reset) (region_type_t *region, box_type_t *box)
1987 assert(box->x1<=box->x2);
1988 assert(box->y1<=box->y2);
1989 region->extents = *box;
1991 region->data = (region_data_type_t *)NULL;
1994 /* box is "return" value */
1996 PREFIX(_contains_point) (region_type_t * region,
2000 box_type_t *pbox, *pboxEnd;
2004 numRects = PIXREGION_NUM_RECTS(region);
2005 if (!numRects || !INBOX(®ion->extents, x, y))
2010 *box = region->extents;
2014 for (pbox = PIXREGION_BOXPTR(region), pboxEnd = pbox + numRects;
2019 continue; /* not there yet */
2020 if ((y < pbox->y1) || (x < pbox->x1))
2021 break; /* missed it */
2023 continue; /* not there yet */
2034 PREFIX(_not_empty) (region_type_t * region)
2037 return(!PIXREGION_NIL(region));
2040 PIXMAN_EXPORT box_type_t *
2041 PREFIX(_extents) (region_type_t * region)
2044 return(®ion->extents);
2048 Clip a list of scanlines to a region. The caller has allocated the
2049 space. FSorted is non-zero if the scanline origins are in ascending
2051 returns the number of new, clipped scanlines.
2054 PIXMAN_EXPORT pixman_bool_t
2055 PREFIX(_selfcheck) (reg)
2056 region_type_t * reg;
2060 if ((reg->extents.x1 > reg->extents.x2) ||
2061 (reg->extents.y1 > reg->extents.y2))
2063 numRects = PIXREGION_NUM_RECTS(reg);
2065 return ((reg->extents.x1 == reg->extents.x2) &&
2066 (reg->extents.y1 == reg->extents.y2) &&
2067 (reg->data->size || (reg->data == pixman_region_emptyData)));
2068 else if (numRects == 1)
2069 return (!reg->data);
2072 box_type_t * pboxP, * pboxN;
2075 pboxP = PIXREGION_RECTS(reg);
2077 box.y2 = pboxP[numRects-1].y2;
2079 for (i = numRects; --i > 0; pboxP++, pboxN++)
2081 if ((pboxN->x1 >= pboxN->x2) ||
2082 (pboxN->y1 >= pboxN->y2))
2084 if (pboxN->x1 < box.x1)
2086 if (pboxN->x2 > box.x2)
2088 if ((pboxN->y1 < pboxP->y1) ||
2089 ((pboxN->y1 == pboxP->y1) &&
2090 ((pboxN->x1 < pboxP->x2) || (pboxN->y2 != pboxP->y2))))
2093 return ((box.x1 == reg->extents.x1) &&
2094 (box.x2 == reg->extents.x2) &&
2095 (box.y1 == reg->extents.y1) &&
2096 (box.y2 == reg->extents.y2));
2100 PIXMAN_EXPORT pixman_bool_t
2101 PREFIX(_init_rects) (region_type_t *region,
2102 box_type_t *boxes, int count)
2106 /* if it's 1, then we just want to set the extents, so call
2107 * the existing method. */
2109 PREFIX(_init_rect) (region,
2112 boxes[0].x2 - boxes[0].x1,
2113 boxes[0].y2 - boxes[0].y1);
2117 PREFIX(_init) (region);
2119 /* if it's 0, don't call pixman_rect_alloc -- 0 rectangles is
2120 * a special case, and causing pixman_rect_alloc would cause
2121 * us to leak memory (because the 0-rect case should be the
2122 * static pixman_region_emptyData data).
2127 if (!pixman_rect_alloc(region, count))
2130 /* Copy in the rects */
2131 memcpy (PIXREGION_RECTS(region), boxes, sizeof(box_type_t) * count);
2132 region->data->numRects = count;
2135 region->extents.x1 = region->extents.x2 = 0;
2136 return validate (region, &overlap);