Pileus Git - ~andy/gtk/blob - gdk/gdkregion-generic.c

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