blob: 604ecded3d6117804f7d254fff4908a3d1003fe3 [file] [log] [blame]
syuri843bf672008-09-19 09:55:50 +00001/* $Xorg: Region.c,v 1.6 2001/02/09 02:03:35 xorgcvs Exp $ */
2/************************************************************************
3
4Copyright 1987, 1988, 1998 The Open Group
5
6Permission to use, copy, modify, distribute, and sell this software and its
7documentation for any purpose is hereby granted without fee, provided that
8the above copyright notice appear in all copies and that both that
9copyright notice and this permission notice appear in supporting
10documentation.
11
12The above copyright notice and this permission notice shall be included in
13all copies or substantial portions of the Software.
14
15THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
19AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
20CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
21
22Except as contained in this notice, the name of The Open Group shall not be
23used in advertising or otherwise to promote the sale, use or other dealings
24in this Software without prior written authorization from The Open Group.
25
26
27Copyright 1987, 1988 by Digital Equipment Corporation, Maynard, Massachusetts.
28
29 All Rights Reserved
30
31Permission to use, copy, modify, and distribute this software and its
32documentation for any purpose and without fee is hereby granted,
33provided that the above copyright notice appear in all copies and that
34both that copyright notice and this permission notice appear in
35supporting documentation, and that the name of Digital not be
36used in advertising or publicity pertaining to distribution of the
37software without specific, written prior permission.
38
39DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
40ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
41DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
42ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
43WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
44ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
45SOFTWARE.
46
47************************************************************************/
48/* $XFree86: xc/lib/X11/Region.c,v 1.8 2001/12/14 19:54:05 dawes Exp $ */
49/*
50 * The functions in this file implement the Region abstraction, similar to one
51 * used in the X11 sample server. A Region is simply an area, as the name
52 * implies, and is implemented as a "y-x-banded" array of rectangles. To
53 * explain: Each Region is made up of a certain number of rectangles sorted
54 * by y coordinate first, and then by x coordinate.
55 *
56 * Furthermore, the rectangles are banded such that every rectangle with a
57 * given upper-left y coordinate (y1) will have the same lower-right y
58 * coordinate (y2) and vice versa. If a rectangle has scanlines in a band, it
59 * will span the entire vertical distance of the band. This means that some
60 * areas that could be merged into a taller rectangle will be represented as
61 * several shorter rectangles to account for shorter rectangles to its left
62 * or right but within its "vertical scope".
63 *
64 * An added constraint on the rectangles is that they must cover as much
65 * horizontal area as possible. E.g. no two rectangles in a band are allowed
66 * to touch.
67 *
68 * Whenever possible, bands will be merged together to cover a greater vertical
69 * distance (and thus reduce the number of rectangles). Two bands can be merged
70 * only if the bottom of one touches the top of the other and they have
71 * rectangles in the same places (of the same width, of course). This maintains
72 * the y-x-banding that's so nice to have...
73 */
74
75#include "Xregion.h"
syuri843bf672008-09-19 09:55:50 +000076#include "region.h"
syuri843bf672008-09-19 09:55:50 +000077
78#ifndef min
79#define min(a,b) (((a) < (b)) ? (a) : (b))
80#endif
81#ifndef max
82#define max(a,b) (((a) > (b)) ? (a) : (b))
83#endif
84
85#ifdef DEBUG
86#include <stdio.h>
87#define assert(expr) {if (!(expr)) fprintf(stderr,\
88"Assertion failed file %s, line %d: expr\n", __FILE__, __LINE__); }
89#else
90#define assert(expr)
91#endif
92
93typedef void (*voidProcp)();
94
95static void miRegionOp();
96/* Create a new empty region */
97Region
98XCreateRegion()
99{
100 Region temp;
101
102 if (! (temp = ( Region )Xmalloc( (unsigned) sizeof( REGION ))))
103 return (Region) NULL;
104 if (! (temp->rects = ( BOX * )Xmalloc( (unsigned) sizeof( BOX )))) {
105 Xfree((char *) temp);
106 return (Region) NULL;
107 }
108 temp->numRects = 0;
109 temp->extents.x1 = 0;
110 temp->extents.y1 = 0;
111 temp->extents.x2 = 0;
112 temp->extents.y2 = 0;
113 temp->size = 1;
114 return( temp );
115}
116
117int
118XClipBox( r, rect )
119 Region r;
120 XRectangle *rect;
121{
122 rect->x = r->extents.x1;
123 rect->y = r->extents.y1;
124 rect->width = r->extents.x2 - r->extents.x1;
125 rect->height = r->extents.y2 - r->extents.y1;
126 return 1;
127}
128
129int
130XUnionRectWithRegion(rect, source, dest)
131 register XRectangle *rect;
132 Region source, dest;
133{
134 REGION region;
135
136 if (!rect->width || !rect->height)
137 return 0;
138 region.rects = &region.extents;
139 region.numRects = 1;
140 region.extents.x1 = rect->x;
141 region.extents.y1 = rect->y;
142 region.extents.x2 = rect->x + rect->width;
143 region.extents.y2 = rect->y + rect->height;
144 region.size = 1;
145
146 return XUnionRegion(&region, source, dest);
147}
148
149/*-
150 *-----------------------------------------------------------------------
151 * miSetExtents --
152 * Reset the extents of a region to what they should be. Called by
153 * miSubtract and miIntersect b/c they can't figure it out along the
154 * way or do so easily, as miUnion can.
155 *
156 * Results:
157 * None.
158 *
159 * Side Effects:
160 * The region's 'extents' structure is overwritten.
161 *
162 *-----------------------------------------------------------------------
163 */
164static void
165miSetExtents (pReg)
166 Region pReg;
167{
168 register BoxPtr pBox,
169 pBoxEnd,
170 pExtents;
171
172 if (pReg->numRects == 0)
173 {
174 pReg->extents.x1 = 0;
175 pReg->extents.y1 = 0;
176 pReg->extents.x2 = 0;
177 pReg->extents.y2 = 0;
178 return;
179 }
180
181 pExtents = &pReg->extents;
182 pBox = pReg->rects;
183 pBoxEnd = &pBox[pReg->numRects - 1];
184
185 /*
186 * Since pBox is the first rectangle in the region, it must have the
187 * smallest y1 and since pBoxEnd is the last rectangle in the region,
188 * it must have the largest y2, because of banding. Initialize x1 and
189 * x2 from pBox and pBoxEnd, resp., as good things to initialize them
190 * to...
191 */
192 pExtents->x1 = pBox->x1;
193 pExtents->y1 = pBox->y1;
194 pExtents->x2 = pBoxEnd->x2;
195 pExtents->y2 = pBoxEnd->y2;
196
197 assert(pExtents->y1 < pExtents->y2);
198 while (pBox <= pBoxEnd)
199 {
200 if (pBox->x1 < pExtents->x1)
201 {
202 pExtents->x1 = pBox->x1;
203 }
204 if (pBox->x2 > pExtents->x2)
205 {
206 pExtents->x2 = pBox->x2;
207 }
208 pBox++;
209 }
210 assert(pExtents->x1 < pExtents->x2);
211}
212
213extern void _XSetClipRectangles();
214
215#if 0
216int
217XSetRegion( dpy, gc, r )
218 Display *dpy;
219 GC gc;
220 register Region r;
221{
222 register int i;
223 register XRectangle *xr, *pr;
224 register BOX *pb;
225 unsigned long total;
226
227 LockDisplay (dpy);
228 total = r->numRects * sizeof (XRectangle);
229 if ((xr = (XRectangle *) _XAllocTemp(dpy, total))) {
230 for (pr = xr, pb = r->rects, i = r->numRects; --i >= 0; pr++, pb++) {
231 pr->x = pb->x1;
232 pr->y = pb->y1;
233 pr->width = pb->x2 - pb->x1;
234 pr->height = pb->y2 - pb->y1;
235 }
236 }
237 if (xr || !r->numRects)
238 _XSetClipRectangles(dpy, gc, 0, 0, xr, r->numRects, YXBanded);
239 if (xr)
240 _XFreeTemp(dpy, (char *)xr, total);
241 UnlockDisplay(dpy);
242 SyncHandle();
243 return 1;
244}
245#endif
246
247int
248XDestroyRegion( r )
249 Region r;
250{
251 Xfree( (char *) r->rects );
252 Xfree( (char *) r );
253 return 1;
254}
255
256
257/* TranslateRegion(pRegion, x, y)
258 translates in place
259 added by raymond
260*/
261
262int
263XOffsetRegion(pRegion, x, y)
264 register Region pRegion;
265 register int x;
266 register int y;
267{
268 register int nbox;
269 register BOX *pbox;
270
271 pbox = pRegion->rects;
272 nbox = pRegion->numRects;
273
274 while(nbox--)
275 {
276 pbox->x1 += x;
277 pbox->x2 += x;
278 pbox->y1 += y;
279 pbox->y2 += y;
280 pbox++;
281 }
282 pRegion->extents.x1 += x;
283 pRegion->extents.x2 += x;
284 pRegion->extents.y1 += y;
285 pRegion->extents.y2 += y;
286 return 1;
287}
288
289/*
290 Utility procedure Compress:
291 Replace r by the region r', where
292 p in r' iff (Quantifer m <= dx) (p + m in r), and
293 Quantifier is Exists if grow is TRUE, For all if grow is FALSE, and
294 (x,y) + m = (x+m,y) if xdir is TRUE; (x,y+m) if xdir is FALSE.
295
296 Thus, if xdir is TRUE and grow is FALSE, r is replaced by the region
297 of all points p such that p and the next dx points on the same
298 horizontal scan line are all in r. We do this using by noting
299 that p is the head of a run of length 2^i + k iff p is the head
300 of a run of length 2^i and p+2^i is the head of a run of length
301 k. Thus, the loop invariant: s contains the region corresponding
302 to the runs of length shift. r contains the region corresponding
303 to the runs of length 1 + dxo & (shift-1), where dxo is the original
304 value of dx. dx = dxo & ~(shift-1). As parameters, s and t are
305 scratch regions, so that we don't have to allocate them on every
306 call.
307*/
308
309#define ZOpRegion(a,b,c) if (grow) XUnionRegion(a,b,c); \
310 else XIntersectRegion(a,b,c)
311#define ZShiftRegion(a,b) if (xdir) XOffsetRegion(a,b,0); \
312 else XOffsetRegion(a,0,b)
313#define ZCopyRegion(a,b) XUnionRegion(a,a,b)
314
315static void
316Compress(r, s, t, dx, xdir, grow)
317 Region r, s, t;
318 register unsigned dx;
319 register int xdir, grow;
320{
321 register unsigned shift = 1;
322
323 ZCopyRegion(r, s);
324 while (dx) {
325 if (dx & shift) {
326 ZShiftRegion(r, -(int)shift);
327 ZOpRegion(r, s, r);
328 dx -= shift;
329 if (!dx) break;
330 }
331 ZCopyRegion(s, t);
332 ZShiftRegion(s, -(int)shift);
333 ZOpRegion(s, t, s);
334 shift <<= 1;
335 }
336}
337
338#undef ZOpRegion
339#undef ZShiftRegion
340#undef ZCopyRegion
341
342int
343XShrinkRegion(r, dx, dy)
344 Region r;
345 int dx, dy;
346{
347 Region s, t;
348 int grow;
349
350 if (!dx && !dy) return 0;
351 if ((! (s = XCreateRegion())) || (! (t = XCreateRegion()))) return 0;
352 if ((grow = (dx < 0))) dx = -dx;
353 if (dx) Compress(r, s, t, (unsigned) 2*dx, TRUE, grow);
354 if ((grow = (dy < 0))) dy = -dy;
355 if (dy) Compress(r, s, t, (unsigned) 2*dy, FALSE, grow);
356 XOffsetRegion(r, dx, dy);
357 XDestroyRegion(s);
358 XDestroyRegion(t);
359 return 0;
360}
361
362#ifdef notdef
363/***********************************************************
364 * Bop down the array of rects until we have passed
365 * scanline y. numRects is the size of the array.
366 ***********************************************************/
367
368static BOX
369*IndexRects(rects, numRects, y)
370 register BOX *rects;
371 register int numRects;
372 register int y;
373{
374 while ((numRects--) && (rects->y2 <= y))
375 rects++;
376 return(rects);
377}
378#endif
379
380/*======================================================================
381 * Region Intersection
382 *====================================================================*/
383/*-
384 *-----------------------------------------------------------------------
385 * miIntersectO --
386 * Handle an overlapping band for miIntersect.
387 *
388 * Results:
389 * None.
390 *
391 * Side Effects:
392 * Rectangles may be added to the region.
393 *
394 *-----------------------------------------------------------------------
395 */
396/* static void*/
397static int
398miIntersectO (pReg, r1, r1End, r2, r2End, y1, y2)
399 register Region pReg;
400 register BoxPtr r1;
401 BoxPtr r1End;
402 register BoxPtr r2;
403 BoxPtr r2End;
404 short y1;
405 short y2;
406{
407 register short x1;
408 register short x2;
409 register BoxPtr pNextRect;
410
411 pNextRect = &pReg->rects[pReg->numRects];
412
413 while ((r1 != r1End) && (r2 != r2End))
414 {
415 x1 = max(r1->x1,r2->x1);
416 x2 = min(r1->x2,r2->x2);
417
418 /*
419 * If there's any overlap between the two rectangles, add that
420 * overlap to the new region.
421 * There's no need to check for subsumption because the only way
422 * such a need could arise is if some region has two rectangles
423 * right next to each other. Since that should never happen...
424 */
425 if (x1 < x2)
426 {
427 assert(y1<y2);
428
429 MEMCHECK(pReg, pNextRect, pReg->rects);
430 pNextRect->x1 = x1;
431 pNextRect->y1 = y1;
432 pNextRect->x2 = x2;
433 pNextRect->y2 = y2;
434 pReg->numRects += 1;
435 pNextRect++;
436 assert(pReg->numRects <= pReg->size);
437 }
438
439 /*
440 * Need to advance the pointers. Shift the one that extends
441 * to the right the least, since the other still has a chance to
442 * overlap with that region's next rectangle, if you see what I mean.
443 */
444 if (r1->x2 < r2->x2)
445 {
446 r1++;
447 }
448 else if (r2->x2 < r1->x2)
449 {
450 r2++;
451 }
452 else
453 {
454 r1++;
455 r2++;
456 }
457 }
458 return 0; /* lint */
459}
460
461int
462XIntersectRegion(reg1, reg2, newReg)
463 Region reg1;
464 Region reg2; /* source regions */
465 register Region newReg; /* destination Region */
466{
467 /* check for trivial reject */
468 if ( (!(reg1->numRects)) || (!(reg2->numRects)) ||
469 (!EXTENTCHECK(&reg1->extents, &reg2->extents)))
470 newReg->numRects = 0;
471 else
472 miRegionOp (newReg, reg1, reg2,
473 (voidProcp) miIntersectO, (voidProcp) NULL, (voidProcp) NULL);
474
475 /*
476 * Can't alter newReg's extents before we call miRegionOp because
477 * it might be one of the source regions and miRegionOp depends
478 * on the extents of those regions being the same. Besides, this
479 * way there's no checking against rectangles that will be nuked
480 * due to coalescing, so we have to examine fewer rectangles.
481 */
482 miSetExtents(newReg);
483 return 1;
484}
485
486static void
487miRegionCopy(dstrgn, rgn)
488 register Region dstrgn;
489 register Region rgn;
490
491{
492 if (dstrgn != rgn) /* don't want to copy to itself */
493 {
494 if (dstrgn->size < rgn->numRects)
495 {
496 if (dstrgn->rects)
497 {
498 BOX *prevRects = dstrgn->rects;
499
500 if (! (dstrgn->rects = (BOX *)
501 Xrealloc((char *) dstrgn->rects,
502 (unsigned) rgn->numRects * (sizeof(BOX))))) {
503 Xfree(prevRects);
504 return;
505 }
506 }
507 dstrgn->size = rgn->numRects;
508 }
509 dstrgn->numRects = rgn->numRects;
510 dstrgn->extents.x1 = rgn->extents.x1;
511 dstrgn->extents.y1 = rgn->extents.y1;
512 dstrgn->extents.x2 = rgn->extents.x2;
513 dstrgn->extents.y2 = rgn->extents.y2;
514
515 memcpy((char *) dstrgn->rects, (char *) rgn->rects,
516 (int) (rgn->numRects * sizeof(BOX)));
517 }
518}
519
520#ifdef notdef
521
522/*
523 * combinRegs(newReg, reg1, reg2)
524 * if one region is above or below the other.
525*/
526
527static void
528combineRegs(newReg, reg1, reg2)
529 register Region newReg;
530 Region reg1;
531 Region reg2;
532{
533 register Region tempReg;
534 register BOX *rects;
535 register BOX *rects1;
536 register BOX *rects2;
537 register int total;
538
539 rects1 = reg1->rects;
540 rects2 = reg2->rects;
541
542 total = reg1->numRects + reg2->numRects;
543 if (! (tempReg = XCreateRegion()))
544 return;
545 tempReg->size = total;
546 /* region 1 is below region 2 */
547 if (reg1->extents.y1 > reg2->extents.y1)
548 {
549 miRegionCopy(tempReg, reg2);
550 rects = &tempReg->rects[tempReg->numRects];
551 total -= tempReg->numRects;
552 while (total--)
553 *rects++ = *rects1++;
554 }
555 else
556 {
557 miRegionCopy(tempReg, reg1);
558 rects = &tempReg->rects[tempReg->numRects];
559 total -= tempReg->numRects;
560 while (total--)
561 *rects++ = *rects2++;
562 }
563 tempReg->extents = reg1->extents;
564 tempReg->numRects = reg1->numRects + reg2->numRects;
565 EXTENTS(&reg2->extents, tempReg);
566 miRegionCopy(newReg, tempReg);
567 Xfree((char *)tempReg);
568}
569
570/*
571 * QuickCheck checks to see if it does not have to go through all the
572 * the ugly code for the region call. It returns 1 if it did all
573 * the work for Union, otherwise 0 - still work to be done.
574*/
575
576static int
577QuickCheck(newReg, reg1, reg2)
578 Region newReg, reg1, reg2;
579{
580
581 /* if unioning with itself or no rects to union with */
582 if ( (reg1 == reg2) || (!(reg1->numRects)) )
583 {
584 miRegionCopy(newReg, reg2);
585 return TRUE;
586 }
587
588 /* if nothing to union */
589 if (!(reg2->numRects))
590 {
591 miRegionCopy(newReg, reg1);
592 return TRUE;
593 }
594
595 /* could put an extent check to see if add above or below */
596
597 if ((reg1->extents.y1 >= reg2->extents.y2) ||
598 (reg2->extents.y1 >= reg1->extents.y2) )
599 {
600 combineRegs(newReg, reg1, reg2);
601 return TRUE;
602 }
603 return FALSE;
604}
605
606/* TopRects(rects, reg1, reg2)
607 * N.B. We now assume that reg1 and reg2 intersect. Therefore we are
608 * NOT checking in the two while loops for stepping off the end of the
609 * region.
610 */
611
612static int
613TopRects(newReg, rects, reg1, reg2, FirstRect)
614 register Region newReg;
615 register BOX *rects;
616 register Region reg1;
617 register Region reg2;
618 BOX *FirstRect;
619{
620 register BOX *tempRects;
621
622 /* need to add some rects from region 1 */
623 if (reg1->extents.y1 < reg2->extents.y1)
624 {
625 tempRects = reg1->rects;
626 while(tempRects->y1 < reg2->extents.y1)
627 {
628 MEMCHECK(newReg, rects, FirstRect);
629 ADDRECTNOX(newReg,rects, tempRects->x1, tempRects->y1,
630 tempRects->x2, MIN(tempRects->y2, reg2->extents.y1));
631 tempRects++;
632 }
633 }
634 /* need to add some rects from region 2 */
635 if (reg2->extents.y1 < reg1->extents.y1)
636 {
637 tempRects = reg2->rects;
638 while (tempRects->y1 < reg1->extents.y1)
639 {
640 MEMCHECK(newReg, rects, FirstRect);
641 ADDRECTNOX(newReg, rects, tempRects->x1,tempRects->y1,
642 tempRects->x2, MIN(tempRects->y2, reg1->extents.y1));
643 tempRects++;
644 }
645 }
646 return 1;
647}
648#endif
649
650/*======================================================================
651 * Generic Region Operator
652 *====================================================================*/
653
654/*-
655 *-----------------------------------------------------------------------
656 * miCoalesce --
657 * Attempt to merge the boxes in the current band with those in the
658 * previous one. Used only by miRegionOp.
659 *
660 * Results:
661 * The new index for the previous band.
662 *
663 * Side Effects:
664 * If coalescing takes place:
665 * - rectangles in the previous band will have their y2 fields
666 * altered.
667 * - pReg->numRects will be decreased.
668 *
669 *-----------------------------------------------------------------------
670 */
671/* static int*/
672static int
673miCoalesce (pReg, prevStart, curStart)
674 register Region pReg; /* Region to coalesce */
675 int prevStart; /* Index of start of previous band */
676 int curStart; /* Index of start of current band */
677{
678 register BoxPtr pPrevBox; /* Current box in previous band */
679 register BoxPtr pCurBox; /* Current box in current band */
680 register BoxPtr pRegEnd; /* End of region */
681 int curNumRects; /* Number of rectangles in current
682 * band */
683 int prevNumRects; /* Number of rectangles in previous
684 * band */
685 int bandY1; /* Y1 coordinate for current band */
686
687 pRegEnd = &pReg->rects[pReg->numRects];
688
689 pPrevBox = &pReg->rects[prevStart];
690 prevNumRects = curStart - prevStart;
691
692 /*
693 * Figure out how many rectangles are in the current band. Have to do
694 * this because multiple bands could have been added in miRegionOp
695 * at the end when one region has been exhausted.
696 */
697 pCurBox = &pReg->rects[curStart];
698 bandY1 = pCurBox->y1;
699 for (curNumRects = 0;
700 (pCurBox != pRegEnd) && (pCurBox->y1 == bandY1);
701 curNumRects++)
702 {
703 pCurBox++;
704 }
705
706 if (pCurBox != pRegEnd)
707 {
708 /*
709 * If more than one band was added, we have to find the start
710 * of the last band added so the next coalescing job can start
711 * at the right place... (given when multiple bands are added,
712 * this may be pointless -- see above).
713 */
714 pRegEnd--;
715 while (pRegEnd[-1].y1 == pRegEnd->y1)
716 {
717 pRegEnd--;
718 }
719 curStart = pRegEnd - pReg->rects;
720 pRegEnd = pReg->rects + pReg->numRects;
721 }
722
723 if ((curNumRects == prevNumRects) && (curNumRects != 0)) {
724 pCurBox -= curNumRects;
725 /*
726 * The bands may only be coalesced if the bottom of the previous
727 * matches the top scanline of the current.
728 */
729 if (pPrevBox->y2 == pCurBox->y1)
730 {
731 /*
732 * Make sure the bands have boxes in the same places. This
733 * assumes that boxes have been added in such a way that they
734 * cover the most area possible. I.e. two boxes in a band must
735 * have some horizontal space between them.
736 */
737 do
738 {
739 if ((pPrevBox->x1 != pCurBox->x1) ||
740 (pPrevBox->x2 != pCurBox->x2))
741 {
742 /*
743 * The bands don't line up so they can't be coalesced.
744 */
745 return (curStart);
746 }
747 pPrevBox++;
748 pCurBox++;
749 prevNumRects -= 1;
750 } while (prevNumRects != 0);
751
752 pReg->numRects -= curNumRects;
753 pCurBox -= curNumRects;
754 pPrevBox -= curNumRects;
755
756 /*
757 * The bands may be merged, so set the bottom y of each box
758 * in the previous band to that of the corresponding box in
759 * the current band.
760 */
761 do
762 {
763 pPrevBox->y2 = pCurBox->y2;
764 pPrevBox++;
765 pCurBox++;
766 curNumRects -= 1;
767 } while (curNumRects != 0);
768
769 /*
770 * If only one band was added to the region, we have to backup
771 * curStart to the start of the previous band.
772 *
773 * If more than one band was added to the region, copy the
774 * other bands down. The assumption here is that the other bands
775 * came from the same region as the current one and no further
776 * coalescing can be done on them since it's all been done
777 * already... curStart is already in the right place.
778 */
779 if (pCurBox == pRegEnd)
780 {
781 curStart = prevStart;
782 }
783 else
784 {
785 do
786 {
787 *pPrevBox++ = *pCurBox++;
788 } while (pCurBox != pRegEnd);
789 }
790
791 }
792 }
793 return (curStart);
794}
795
796/*-
797 *-----------------------------------------------------------------------
798 * miRegionOp --
799 * Apply an operation to two regions. Called by miUnion, miInverse,
800 * miSubtract, miIntersect...
801 *
802 * Results:
803 * None.
804 *
805 * Side Effects:
806 * The new region is overwritten.
807 *
808 * Notes:
809 * The idea behind this function is to view the two regions as sets.
810 * Together they cover a rectangle of area that this function divides
811 * into horizontal bands where points are covered only by one region
812 * or by both. For the first case, the nonOverlapFunc is called with
813 * each the band and the band's upper and lower extents. For the
814 * second, the overlapFunc is called to process the entire band. It
815 * is responsible for clipping the rectangles in the band, though
816 * this function provides the boundaries.
817 * At the end of each band, the new region is coalesced, if possible,
818 * to reduce the number of rectangles in the region.
819 *
820 *-----------------------------------------------------------------------
821 */
822/* static void*/
823static void
824miRegionOp(newReg, reg1, reg2, overlapFunc, nonOverlap1Func, nonOverlap2Func)
825 register Region newReg; /* Place to store result */
826 Region reg1; /* First region in operation */
827 Region reg2; /* 2d region in operation */
828 void (*overlapFunc)(); /* Function to call for over-
829 * lapping bands */
830 void (*nonOverlap1Func)(); /* Function to call for non-
831 * overlapping bands in region
832 * 1 */
833 void (*nonOverlap2Func)(); /* Function to call for non-
834 * overlapping bands in region
835 * 2 */
836{
837 register BoxPtr r1; /* Pointer into first region */
838 register BoxPtr r2; /* Pointer into 2d region */
839 BoxPtr r1End; /* End of 1st region */
840 BoxPtr r2End; /* End of 2d region */
841 register short ybot; /* Bottom of intersection */
842 register short ytop; /* Top of intersection */
843 BoxPtr oldRects; /* Old rects for newReg */
844 int prevBand; /* Index of start of
845 * previous band in newReg */
846 int curBand; /* Index of start of current
847 * band in newReg */
848 register BoxPtr r1BandEnd; /* End of current band in r1 */
849 register BoxPtr r2BandEnd; /* End of current band in r2 */
850 short top; /* Top of non-overlapping
851 * band */
852 short bot; /* Bottom of non-overlapping
853 * band */
854
855 /*
856 * Initialization:
857 * set r1, r2, r1End and r2End appropriately, preserve the important
858 * parts of the destination region until the end in case it's one of
859 * the two source regions, then mark the "new" region empty, allocating
860 * another array of rectangles for it to use.
861 */
862 r1 = reg1->rects;
863 r2 = reg2->rects;
864 r1End = r1 + reg1->numRects;
865 r2End = r2 + reg2->numRects;
866
867 oldRects = newReg->rects;
868
869 EMPTY_REGION(newReg);
870
871 /*
872 * Allocate a reasonable number of rectangles for the new region. The idea
873 * is to allocate enough so the individual functions don't need to
874 * reallocate and copy the array, which is time consuming, yet we don't
875 * have to worry about using too much memory. I hope to be able to
876 * nuke the Xrealloc() at the end of this function eventually.
877 */
878 newReg->size = max(reg1->numRects,reg2->numRects) * 2;
879
880 if (! (newReg->rects = (BoxPtr)
881 Xmalloc ((unsigned) (sizeof(BoxRec) * newReg->size)))) {
882 newReg->size = 0;
883 return;
884 }
885
886 /*
887 * Initialize ybot and ytop.
888 * In the upcoming loop, ybot and ytop serve different functions depending
889 * on whether the band being handled is an overlapping or non-overlapping
890 * band.
891 * In the case of a non-overlapping band (only one of the regions
892 * has points in the band), ybot is the bottom of the most recent
893 * intersection and thus clips the top of the rectangles in that band.
894 * ytop is the top of the next intersection between the two regions and
895 * serves to clip the bottom of the rectangles in the current band.
896 * For an overlapping band (where the two regions intersect), ytop clips
897 * the top of the rectangles of both regions and ybot clips the bottoms.
898 */
899 if (reg1->extents.y1 < reg2->extents.y1)
900 ybot = reg1->extents.y1;
901 else
902 ybot = reg2->extents.y1;
903
904 /*
905 * prevBand serves to mark the start of the previous band so rectangles
906 * can be coalesced into larger rectangles. qv. miCoalesce, above.
907 * In the beginning, there is no previous band, so prevBand == curBand
908 * (curBand is set later on, of course, but the first band will always
909 * start at index 0). prevBand and curBand must be indices because of
910 * the possible expansion, and resultant moving, of the new region's
911 * array of rectangles.
912 */
913 prevBand = 0;
914
915 do
916 {
917 curBand = newReg->numRects;
918
919 /*
920 * This algorithm proceeds one source-band (as opposed to a
921 * destination band, which is determined by where the two regions
922 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
923 * rectangle after the last one in the current band for their
924 * respective regions.
925 */
926 r1BandEnd = r1;
927 while ((r1BandEnd != r1End) && (r1BandEnd->y1 == r1->y1))
928 {
929 r1BandEnd++;
930 }
931
932 r2BandEnd = r2;
933 while ((r2BandEnd != r2End) && (r2BandEnd->y1 == r2->y1))
934 {
935 r2BandEnd++;
936 }
937
938 /*
939 * First handle the band that doesn't intersect, if any.
940 *
941 * Note that attention is restricted to one band in the
942 * non-intersecting region at once, so if a region has n
943 * bands between the current position and the next place it overlaps
944 * the other, this entire loop will be passed through n times.
945 */
946 if (r1->y1 < r2->y1)
947 {
948 top = max(r1->y1,ybot);
949 bot = min(r1->y2,r2->y1);
950
951 if ((top != bot) && (nonOverlap1Func != (void (*)())NULL))
952 {
953 (* nonOverlap1Func) (newReg, r1, r1BandEnd, top, bot);
954 }
955
956 ytop = r2->y1;
957 }
958 else if (r2->y1 < r1->y1)
959 {
960 top = max(r2->y1,ybot);
961 bot = min(r2->y2,r1->y1);
962
963 if ((top != bot) && (nonOverlap2Func != (void (*)())NULL))
964 {
965 (* nonOverlap2Func) (newReg, r2, r2BandEnd, top, bot);
966 }
967
968 ytop = r1->y1;
969 }
970 else
971 {
972 ytop = r1->y1;
973 }
974
975 /*
976 * If any rectangles got added to the region, try and coalesce them
977 * with rectangles from the previous band. Note we could just do
978 * this test in miCoalesce, but some machines incur a not
979 * inconsiderable cost for function calls, so...
980 */
981 if (newReg->numRects != curBand)
982 {
983 prevBand = miCoalesce (newReg, prevBand, curBand);
984 }
985
986 /*
987 * Now see if we've hit an intersecting band. The two bands only
988 * intersect if ybot > ytop
989 */
990 ybot = min(r1->y2, r2->y2);
991 curBand = newReg->numRects;
992 if (ybot > ytop)
993 {
994 (* overlapFunc) (newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);
995
996 }
997
998 if (newReg->numRects != curBand)
999 {
1000 prevBand = miCoalesce (newReg, prevBand, curBand);
1001 }
1002
1003 /*
1004 * If we've finished with a band (y2 == ybot) we skip forward
1005 * in the region to the next band.
1006 */
1007 if (r1->y2 == ybot)
1008 {
1009 r1 = r1BandEnd;
1010 }
1011 if (r2->y2 == ybot)
1012 {
1013 r2 = r2BandEnd;
1014 }
1015 } while ((r1 != r1End) && (r2 != r2End));
1016
1017 /*
1018 * Deal with whichever region still has rectangles left.
1019 */
1020 curBand = newReg->numRects;
1021 if (r1 != r1End)
1022 {
1023 if (nonOverlap1Func != (void (*)())NULL)
1024 {
1025 do
1026 {
1027 r1BandEnd = r1;
1028 while ((r1BandEnd < r1End) && (r1BandEnd->y1 == r1->y1))
1029 {
1030 r1BandEnd++;
1031 }
1032 (* nonOverlap1Func) (newReg, r1, r1BandEnd,
1033 max(r1->y1,ybot), r1->y2);
1034 r1 = r1BandEnd;
1035 } while (r1 != r1End);
1036 }
1037 }
1038 else if ((r2 != r2End) && (nonOverlap2Func != (void (*)())NULL))
1039 {
1040 do
1041 {
1042 r2BandEnd = r2;
1043 while ((r2BandEnd < r2End) && (r2BandEnd->y1 == r2->y1))
1044 {
1045 r2BandEnd++;
1046 }
1047 (* nonOverlap2Func) (newReg, r2, r2BandEnd,
1048 max(r2->y1,ybot), r2->y2);
1049 r2 = r2BandEnd;
1050 } while (r2 != r2End);
1051 }
1052
1053 if (newReg->numRects != curBand)
1054 {
1055 (void) miCoalesce (newReg, prevBand, curBand);
1056 }
1057
1058 /*
1059 * A bit of cleanup. To keep regions from growing without bound,
1060 * we shrink the array of rectangles to match the new number of
1061 * rectangles in the region. This never goes to 0, however...
1062 *
1063 * Only do this stuff if the number of rectangles allocated is more than
1064 * twice the number of rectangles in the region (a simple optimization...).
1065 */
1066 if (newReg->numRects < (newReg->size >> 1))
1067 {
1068 if (REGION_NOT_EMPTY(newReg))
1069 {
1070 BoxPtr prev_rects = newReg->rects;
1071 newReg->size = newReg->numRects;
1072 newReg->rects = (BoxPtr) Xrealloc ((char *) newReg->rects,
1073 (unsigned) (sizeof(BoxRec) * newReg->size));
1074 if (! newReg->rects)
1075 newReg->rects = prev_rects;
1076 }
1077 else
1078 {
1079 /*
1080 * No point in doing the extra work involved in an Xrealloc if
1081 * the region is empty
1082 */
1083 newReg->size = 1;
1084 Xfree((char *) newReg->rects);
1085 newReg->rects = (BoxPtr) Xmalloc(sizeof(BoxRec));
1086 }
1087 }
1088 Xfree ((char *) oldRects);
1089 return;
1090}
1091
1092
1093/*======================================================================
1094 * Region Union
1095 *====================================================================*/
1096
1097/*-
1098 *-----------------------------------------------------------------------
1099 * miUnionNonO --
1100 * Handle a non-overlapping band for the union operation. Just
1101 * Adds the rectangles into the region. Doesn't have to check for
1102 * subsumption or anything.
1103 *
1104 * Results:
1105 * None.
1106 *
1107 * Side Effects:
1108 * pReg->numRects is incremented and the final rectangles overwritten
1109 * with the rectangles we're passed.
1110 *
1111 *-----------------------------------------------------------------------
1112 */
1113/* static void*/
1114static int
1115miUnionNonO (pReg, r, rEnd, y1, y2)
1116 register Region pReg;
1117 register BoxPtr r;
1118 BoxPtr rEnd;
1119 register short y1;
1120 register short y2;
1121{
1122 register BoxPtr pNextRect;
1123
1124 pNextRect = &pReg->rects[pReg->numRects];
1125
1126 assert(y1 < y2);
1127
1128 while (r != rEnd)
1129 {
1130 assert(r->x1 < r->x2);
1131 MEMCHECK(pReg, pNextRect, pReg->rects);
1132 pNextRect->x1 = r->x1;
1133 pNextRect->y1 = y1;
1134 pNextRect->x2 = r->x2;
1135 pNextRect->y2 = y2;
1136 pReg->numRects += 1;
1137 pNextRect++;
1138
1139 assert(pReg->numRects<=pReg->size);
1140 r++;
1141 }
1142 return 0; /* lint */
1143}
1144
1145
1146/*-
1147 *-----------------------------------------------------------------------
1148 * miUnionO --
1149 * Handle an overlapping band for the union operation. Picks the
1150 * left-most rectangle each time and merges it into the region.
1151 *
1152 * Results:
1153 * None.
1154 *
1155 * Side Effects:
1156 * Rectangles are overwritten in pReg->rects and pReg->numRects will
1157 * be changed.
1158 *
1159 *-----------------------------------------------------------------------
1160 */
1161
1162/* static void*/
1163static int
1164miUnionO (pReg, r1, r1End, r2, r2End, y1, y2)
1165 register Region pReg;
1166 register BoxPtr r1;
1167 BoxPtr r1End;
1168 register BoxPtr r2;
1169 BoxPtr r2End;
1170 register short y1;
1171 register short y2;
1172{
1173 register BoxPtr pNextRect;
1174
1175 pNextRect = &pReg->rects[pReg->numRects];
1176
1177#define MERGERECT(r) \
1178 if ((pReg->numRects != 0) && \
1179 (pNextRect[-1].y1 == y1) && \
1180 (pNextRect[-1].y2 == y2) && \
1181 (pNextRect[-1].x2 >= r->x1)) \
1182 { \
1183 if (pNextRect[-1].x2 < r->x2) \
1184 { \
1185 pNextRect[-1].x2 = r->x2; \
1186 assert(pNextRect[-1].x1<pNextRect[-1].x2); \
1187 } \
1188 } \
1189 else \
1190 { \
1191 MEMCHECK(pReg, pNextRect, pReg->rects); \
1192 pNextRect->y1 = y1; \
1193 pNextRect->y2 = y2; \
1194 pNextRect->x1 = r->x1; \
1195 pNextRect->x2 = r->x2; \
1196 pReg->numRects += 1; \
1197 pNextRect += 1; \
1198 } \
1199 assert(pReg->numRects<=pReg->size);\
1200 r++;
1201
1202 assert (y1<y2);
1203 while ((r1 != r1End) && (r2 != r2End))
1204 {
1205 if (r1->x1 < r2->x1)
1206 {
1207 MERGERECT(r1);
1208 }
1209 else
1210 {
1211 MERGERECT(r2);
1212 }
1213 }
1214
1215 if (r1 != r1End)
1216 {
1217 do
1218 {
1219 MERGERECT(r1);
1220 } while (r1 != r1End);
1221 }
1222 else while (r2 != r2End)
1223 {
1224 MERGERECT(r2);
1225 }
1226 return 0; /* lint */
1227}
1228
1229int
1230XUnionRegion(reg1, reg2, newReg)
1231 Region reg1;
1232 Region reg2; /* source regions */
1233 Region newReg; /* destination Region */
1234{
1235 /* checks all the simple cases */
1236
1237 /*
1238 * Region 1 and 2 are the same or region 1 is empty
1239 */
1240 if ( (reg1 == reg2) || (!(reg1->numRects)) )
1241 {
1242 if (newReg != reg2)
1243 miRegionCopy(newReg, reg2);
1244 return 1;
1245 }
1246
1247 /*
1248 * if nothing to union (region 2 empty)
1249 */
1250 if (!(reg2->numRects))
1251 {
1252 if (newReg != reg1)
1253 miRegionCopy(newReg, reg1);
1254 return 1;
1255 }
1256
1257 /*
1258 * Region 1 completely subsumes region 2
1259 */
1260 if ((reg1->numRects == 1) &&
1261 (reg1->extents.x1 <= reg2->extents.x1) &&
1262 (reg1->extents.y1 <= reg2->extents.y1) &&
1263 (reg1->extents.x2 >= reg2->extents.x2) &&
1264 (reg1->extents.y2 >= reg2->extents.y2))
1265 {
1266 if (newReg != reg1)
1267 miRegionCopy(newReg, reg1);
1268 return 1;
1269 }
1270
1271 /*
1272 * Region 2 completely subsumes region 1
1273 */
1274 if ((reg2->numRects == 1) &&
1275 (reg2->extents.x1 <= reg1->extents.x1) &&
1276 (reg2->extents.y1 <= reg1->extents.y1) &&
1277 (reg2->extents.x2 >= reg1->extents.x2) &&
1278 (reg2->extents.y2 >= reg1->extents.y2))
1279 {
1280 if (newReg != reg2)
1281 miRegionCopy(newReg, reg2);
1282 return 1;
1283 }
1284
1285 miRegionOp (newReg, reg1, reg2, (voidProcp) miUnionO,
1286 (voidProcp) miUnionNonO, (voidProcp) miUnionNonO);
1287
1288 newReg->extents.x1 = min(reg1->extents.x1, reg2->extents.x1);
1289 newReg->extents.y1 = min(reg1->extents.y1, reg2->extents.y1);
1290 newReg->extents.x2 = max(reg1->extents.x2, reg2->extents.x2);
1291 newReg->extents.y2 = max(reg1->extents.y2, reg2->extents.y2);
1292
1293 return 1;
1294}
1295
1296
1297/*======================================================================
1298 * Region Subtraction
1299 *====================================================================*/
1300
1301/*-
1302 *-----------------------------------------------------------------------
1303 * miSubtractNonO --
1304 * Deal with non-overlapping band for subtraction. Any parts from
1305 * region 2 we discard. Anything from region 1 we add to the region.
1306 *
1307 * Results:
1308 * None.
1309 *
1310 * Side Effects:
1311 * pReg may be affected.
1312 *
1313 *-----------------------------------------------------------------------
1314 */
1315/* static void*/
1316static int
1317miSubtractNonO1 (pReg, r, rEnd, y1, y2)
1318 register Region pReg;
1319 register BoxPtr r;
1320 BoxPtr rEnd;
1321 register short y1;
1322 register short y2;
1323{
1324 register BoxPtr pNextRect;
1325
1326 pNextRect = &pReg->rects[pReg->numRects];
1327
1328 assert(y1<y2);
1329
1330 while (r != rEnd)
1331 {
1332 assert(r->x1<r->x2);
1333 MEMCHECK(pReg, pNextRect, pReg->rects);
1334 pNextRect->x1 = r->x1;
1335 pNextRect->y1 = y1;
1336 pNextRect->x2 = r->x2;
1337 pNextRect->y2 = y2;
1338 pReg->numRects += 1;
1339 pNextRect++;
1340
1341 assert(pReg->numRects <= pReg->size);
1342
1343 r++;
1344 }
1345 return 0; /* lint */
1346}
1347
1348/*-
1349 *-----------------------------------------------------------------------
1350 * miSubtractO --
1351 * Overlapping band subtraction. x1 is the left-most point not yet
1352 * checked.
1353 *
1354 * Results:
1355 * None.
1356 *
1357 * Side Effects:
1358 * pReg may have rectangles added to it.
1359 *
1360 *-----------------------------------------------------------------------
1361 */
1362/* static void*/
1363static int
1364miSubtractO (pReg, r1, r1End, r2, r2End, y1, y2)
1365 register Region pReg;
1366 register BoxPtr r1;
1367 BoxPtr r1End;
1368 register BoxPtr r2;
1369 BoxPtr r2End;
1370 register short y1;
1371 register short y2;
1372{
1373 register BoxPtr pNextRect;
1374 register int x1;
1375
1376 x1 = r1->x1;
1377
1378 assert(y1<y2);
1379 pNextRect = &pReg->rects[pReg->numRects];
1380
1381 while ((r1 != r1End) && (r2 != r2End))
1382 {
1383 if (r2->x2 <= x1)
1384 {
1385 /*
1386 * Subtrahend missed the boat: go to next subtrahend.
1387 */
1388 r2++;
1389 }
1390 else if (r2->x1 <= x1)
1391 {
1392 /*
1393 * Subtrahend preceeds minuend: nuke left edge of minuend.
1394 */
1395 x1 = r2->x2;
1396 if (x1 >= r1->x2)
1397 {
1398 /*
1399 * Minuend completely covered: advance to next minuend and
1400 * reset left fence to edge of new minuend.
1401 */
1402 r1++;
1403 if (r1 != r1End)
1404 x1 = r1->x1;
1405 }
1406 else
1407 {
1408 /*
1409 * Subtrahend now used up since it doesn't extend beyond
1410 * minuend
1411 */
1412 r2++;
1413 }
1414 }
1415 else if (r2->x1 < r1->x2)
1416 {
1417 /*
1418 * Left part of subtrahend covers part of minuend: add uncovered
1419 * part of minuend to region and skip to next subtrahend.
1420 */
1421 assert(x1<r2->x1);
1422 MEMCHECK(pReg, pNextRect, pReg->rects);
1423 pNextRect->x1 = x1;
1424 pNextRect->y1 = y1;
1425 pNextRect->x2 = r2->x1;
1426 pNextRect->y2 = y2;
1427 pReg->numRects += 1;
1428 pNextRect++;
1429
1430 assert(pReg->numRects<=pReg->size);
1431
1432 x1 = r2->x2;
1433 if (x1 >= r1->x2)
1434 {
1435 /*
1436 * Minuend used up: advance to new...
1437 */
1438 r1++;
1439 if (r1 != r1End)
1440 x1 = r1->x1;
1441 }
1442 else
1443 {
1444 /*
1445 * Subtrahend used up
1446 */
1447 r2++;
1448 }
1449 }
1450 else
1451 {
1452 /*
1453 * Minuend used up: add any remaining piece before advancing.
1454 */
1455 if (r1->x2 > x1)
1456 {
1457 MEMCHECK(pReg, pNextRect, pReg->rects);
1458 pNextRect->x1 = x1;
1459 pNextRect->y1 = y1;
1460 pNextRect->x2 = r1->x2;
1461 pNextRect->y2 = y2;
1462 pReg->numRects += 1;
1463 pNextRect++;
1464 assert(pReg->numRects<=pReg->size);
1465 }
1466 r1++;
1467 if (r1 != r1End)
1468 x1 = r1->x1;
1469 }
1470 }
1471
1472 /*
1473 * Add remaining minuend rectangles to region.
1474 */
1475 while (r1 != r1End)
1476 {
1477 assert(x1<r1->x2);
1478 MEMCHECK(pReg, pNextRect, pReg->rects);
1479 pNextRect->x1 = x1;
1480 pNextRect->y1 = y1;
1481 pNextRect->x2 = r1->x2;
1482 pNextRect->y2 = y2;
1483 pReg->numRects += 1;
1484 pNextRect++;
1485
1486 assert(pReg->numRects<=pReg->size);
1487
1488 r1++;
1489 if (r1 != r1End)
1490 {
1491 x1 = r1->x1;
1492 }
1493 }
1494 return 0; /* lint */
1495}
1496
1497/*-
1498 *-----------------------------------------------------------------------
1499 * miSubtract --
1500 * Subtract regS from regM and leave the result in regD.
1501 * S stands for subtrahend, M for minuend and D for difference.
1502 *
1503 * Results:
1504 * TRUE.
1505 *
1506 * Side Effects:
1507 * regD is overwritten.
1508 *
1509 *-----------------------------------------------------------------------
1510 */
1511
1512int
1513XSubtractRegion(regM, regS, regD)
1514 Region regM;
1515 Region regS;
1516 register Region regD;
1517{
1518 /* check for trivial reject */
1519 if ( (!(regM->numRects)) || (!(regS->numRects)) ||
1520 (!EXTENTCHECK(&regM->extents, &regS->extents)) )
1521 {
1522 miRegionCopy(regD, regM);
1523 return 1;
1524 }
1525
1526 miRegionOp (regD, regM, regS, (voidProcp) miSubtractO,
1527 (voidProcp) miSubtractNonO1, (voidProcp) NULL);
1528
1529 /*
1530 * Can't alter newReg's extents before we call miRegionOp because
1531 * it might be one of the source regions and miRegionOp depends
1532 * on the extents of those regions being the unaltered. Besides, this
1533 * way there's no checking against rectangles that will be nuked
1534 * due to coalescing, so we have to examine fewer rectangles.
1535 */
1536 miSetExtents (regD);
1537 return 1;
1538}
1539
1540int
1541XXorRegion( sra, srb, dr )
1542 Region sra, srb, dr;
1543{
1544 Region tra, trb;
1545
1546 if ((! (tra = XCreateRegion())) || (! (trb = XCreateRegion())))
1547 return 0;
1548 (void) XSubtractRegion(sra,srb,tra);
1549 (void) XSubtractRegion(srb,sra,trb);
1550 (void) XUnionRegion(tra,trb,dr);
1551 XDestroyRegion(tra);
1552 XDestroyRegion(trb);
1553 return 0;
1554}
1555
1556/*
1557 * Check to see if the region is empty. Assumes a region is passed
1558 * as a parameter
1559 */
1560int
1561XEmptyRegion( r )
1562 Region r;
1563{
1564 if( r->numRects == 0 ) return TRUE;
1565 else return FALSE;
1566}
1567
1568/*
1569 * Check to see if two regions are equal
1570 */
1571int
1572XEqualRegion( r1, r2 )
1573 Region r1, r2;
1574{
1575 int i;
1576
1577 if( r1->numRects != r2->numRects ) return FALSE;
1578 else if( r1->numRects == 0 ) return TRUE;
1579 else if ( r1->extents.x1 != r2->extents.x1 ) return FALSE;
1580 else if ( r1->extents.x2 != r2->extents.x2 ) return FALSE;
1581 else if ( r1->extents.y1 != r2->extents.y1 ) return FALSE;
1582 else if ( r1->extents.y2 != r2->extents.y2 ) return FALSE;
1583 else for( i=0; i < r1->numRects; i++ ) {
1584 if ( r1->rects[i].x1 != r2->rects[i].x1 ) return FALSE;
1585 else if ( r1->rects[i].x2 != r2->rects[i].x2 ) return FALSE;
1586 else if ( r1->rects[i].y1 != r2->rects[i].y1 ) return FALSE;
1587 else if ( r1->rects[i].y2 != r2->rects[i].y2 ) return FALSE;
1588 }
1589 return TRUE;
1590}
1591
1592int
1593XPointInRegion( pRegion, x, y )
1594 Region pRegion;
1595 int x, y;
1596{
1597 int i;
1598
1599 if (pRegion->numRects == 0)
1600 return FALSE;
1601 if (!INBOX(pRegion->extents, x, y))
1602 return FALSE;
1603 for (i=0; i<pRegion->numRects; i++)
1604 {
1605 if (INBOX (pRegion->rects[i], x, y))
1606 return TRUE;
1607 }
1608 return FALSE;
1609}
1610
1611int
1612XRectInRegion(region, rx, ry, rwidth, rheight)
1613 register Region region;
1614 int rx, ry;
1615 unsigned int rwidth, rheight;
1616{
1617 register BoxPtr pbox;
1618 register BoxPtr pboxEnd;
1619 Box rect;
1620 register BoxPtr prect = &rect;
1621 int partIn, partOut;
1622
1623 prect->x1 = rx;
1624 prect->y1 = ry;
1625 prect->x2 = rwidth + rx;
1626 prect->y2 = rheight + ry;
1627
1628 /* this is (just) a useful optimization */
1629 if ((region->numRects == 0) || !EXTENTCHECK(&region->extents, prect))
1630 return(RectangleOut);
1631
1632 partOut = FALSE;
1633 partIn = FALSE;
1634
1635 /* can stop when both partOut and partIn are TRUE, or we reach prect->y2 */
1636 for (pbox = region->rects, pboxEnd = pbox + region->numRects;
1637 pbox < pboxEnd;
1638 pbox++)
1639 {
1640
1641 if (pbox->y2 <= ry)
1642 continue; /* getting up to speed or skipping remainder of band */
1643
1644 if (pbox->y1 > ry)
1645 {
1646 partOut = TRUE; /* missed part of rectangle above */
1647 if (partIn || (pbox->y1 >= prect->y2))
1648 break;
1649 ry = pbox->y1; /* x guaranteed to be == prect->x1 */
1650 }
1651
1652 if (pbox->x2 <= rx)
1653 continue; /* not far enough over yet */
1654
1655 if (pbox->x1 > rx)
1656 {
1657 partOut = TRUE; /* missed part of rectangle to left */
1658 if (partIn)
1659 break;
1660 }
1661
1662 if (pbox->x1 < prect->x2)
1663 {
1664 partIn = TRUE; /* definitely overlap */
1665 if (partOut)
1666 break;
1667 }
1668
1669 if (pbox->x2 >= prect->x2)
1670 {
1671 ry = pbox->y2; /* finished with this band */
1672 if (ry >= prect->y2)
1673 break;
1674 rx = prect->x1; /* reset x out to left again */
1675 } else
1676 {
1677 /*
1678 * Because boxes in a band are maximal width, if the first box
1679 * to overlap the rectangle doesn't completely cover it in that
1680 * band, the rectangle must be partially out, since some of it
1681 * will be uncovered in that band. partIn will have been set true
1682 * by now...
1683 */
1684 break;
1685 }
1686
1687 }
1688
1689 return(partIn ? ((ry < prect->y2) ? RectanglePart : RectangleIn) :
1690 RectangleOut);
1691}