src/Region.c

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