server/region.c

   1 /*
   2  * Server-side region objects. Based on the X11 implementation.
   3  *
   4  * Copyright 1993, 1994, 1995, 2004 Alexandre Julliard
   5  * Modifications and additions: Copyright 1998 Huw Davies
   6  *                                        1999 Alex Korobka
   7  *
   8  * This library is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Lesser General Public
  10  * License as published by the Free Software Foundation; either
  11  * version 2.1 of the License, or (at your option) any later version.
  12  *
  13  * This library is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16  * Lesser General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with this library; if not, write to the Free Software
  20  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  21  *
  22  * Note:
  23  *  This is a simplified version of the code, without all the explanations.
  24  *  Check the equivalent GDI code to make sense of it.
  25  */
  26
  27 /************************************************************************
  28
  29 Copyright (c) 1987, 1988  X Consortium
  30
  31 Permission is hereby granted, free of charge, to any person obtaining a copy
  32 of this software and associated documentation files (the "Software"), to deal
  33 in the Software without restriction, including without limitation the rights
  34 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  35 copies of the Software, and to permit persons to whom the Software is
  36 furnished to do so, subject to the following conditions:
  37
  38 The above copyright notice and this permission notice shall be included in
  39 all copies or substantial portions of the Software.
  40
  41 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  42 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  43 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
  44 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
  45 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  46 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  47
  48 Except as contained in this notice, the name of the X Consortium shall not be
  49 used in advertising or otherwise to promote the sale, use or other dealings
  50 in this Software without prior written authorization from the X Consortium.
  51
  52
  53 Copyright 1987, 1988 by Digital Equipment Corporation, Maynard, Massachusetts.
  54
  55                         All Rights Reserved
  56
  57 Permission to use, copy, modify, and distribute this software and its
  58 documentation for any purpose and without fee is hereby granted,
  59 provided that the above copyright notice appear in all copies and that
  60 both that copyright notice and this permission notice appear in
  61 supporting documentation, and that the name of Digital not be
  62 used in advertising or publicity pertaining to distribution of the
  63 software without specific, written prior permission.
  64
  65 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
  66 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
  67 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
  68 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
  69 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
  70 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
  71 SOFTWARE.
  72
  73 ************************************************************************/
  74
  75 #include <stdarg.h>
  76 #include <stdlib.h>
  77 #include <string.h>
  78 #include "request.h"
  79 #include "user.h"
  80
  81 struct region
  82 {
  83     int size;
  84     int num_rects;
  85     rectangle_t *rects;
  86     rectangle_t extents;
  87 };
  88
  89
  90 #define RGN_DEFAULT_RECTS 2
  91
  92 #define EXTENTCHECK(r1, r2) \
  93     ((r1)->right > (r2)->left && \
  94     (r1)->left < (r2)->right && \
  95     (r1)->bottom > (r2)->top && \
  96     (r1)->top < (r2)->bottom)
  97
  98 typedef int (*overlap_func_t)( struct region *reg, const rectangle_t *r1, const rectangle_t *r1End,
  99                                const rectangle_t *r2, const rectangle_t *r2End, int top, int bottom );
 100 typedef int (*non_overlap_func_t)( struct region *reg, const rectangle_t *r,
 101                                    const rectangle_t *rEnd, int top, int bottom );
 102
 103 static const rectangle_t empty_rect;  /* all-zero rectangle for empty regions */
 104
 105 /* add a rectangle to a region */
 106 static inline rectangle_t *add_rect( struct region *reg )
 107 {
 108     if (reg->num_rects >= reg->size - 1)
 109     {
 110         rectangle_t *new_rect = realloc( reg->rects, 2 * sizeof(rectangle_t) * reg->size );
 111         if (!new_rect)
 112         {
 113             set_error( STATUS_NO_MEMORY );
 114             return 0;
 115         }
 116         reg->rects = new_rect;
 117         reg->size *= 2;
 118     }
 119     return reg->rects + reg->num_rects++;
 120 }
 121
 122 /* make sure all the rectangles are valid and that the region is properly y-x-banded */
 123 static inline int validate_rectangles( const rectangle_t *rects, unsigned int nb_rects )
 124 {
 125     const rectangle_t *ptr, *end;
 126
 127     for (ptr = rects, end = rects + nb_rects; ptr < end; ptr++)
 128     {
 129         if (ptr->left >= ptr->right || ptr->top >= ptr->bottom) return 0;  /* empty rectangle */
 130         if (ptr == end - 1) break;
 131         if (ptr[0].top == ptr[1].top)  /* same band */
 132         {
 133             if (ptr[0].bottom != ptr[1].bottom) return 0;  /* not same y extent */
 134             if (ptr[0].right >= ptr[1].left) return 0;  /* not properly x ordered */
 135         }
 136         else  /* new band */
 137         {
 138             if (ptr[0].bottom > ptr[1].top) return 0;  /* not properly y ordered */
 139         }
 140     }
 141     return 1;
 142 }
 143
 144 /* attempt to merge the rects in the current band with those in the */
 145 /* previous one. Used only by region_op. */
 146 static int coalesce_region( struct region *pReg, int prevStart, int curStart )
 147 {
 148     int curNumRects;
 149     rectangle_t *pRegEnd = &pReg->rects[pReg->num_rects];
 150     rectangle_t *pPrevRect = &pReg->rects[prevStart];
 151     rectangle_t *pCurRect = &pReg->rects[curStart];
 152     int prevNumRects = curStart - prevStart;
 153     int bandtop = pCurRect->top;
 154
 155     for (curNumRects = 0;
 156          (pCurRect != pRegEnd) && (pCurRect->top == bandtop);
 157          curNumRects++)
 158     {
 159         pCurRect++;
 160     }
 161
 162     if (pCurRect != pRegEnd)
 163     {
 164         pRegEnd--;
 165         while (pRegEnd[-1].top == pRegEnd->top) pRegEnd--;
 166         curStart = pRegEnd - pReg->rects;
 167         pRegEnd = pReg->rects + pReg->num_rects;
 168     }
 169
 170     if ((curNumRects == prevNumRects) && (curNumRects != 0))
 171     {
 172         pCurRect -= curNumRects;
 173         if (pPrevRect->bottom == pCurRect->top)
 174         {
 175             do
 176             {
 177                 if ((pPrevRect->left != pCurRect->left) ||
 178                     (pPrevRect->right != pCurRect->right)) return curStart;
 179                 pPrevRect++;
 180                 pCurRect++;
 181                 prevNumRects -= 1;
 182             } while (prevNumRects != 0);
 183
 184             pReg->num_rects -= curNumRects;
 185             pCurRect -= curNumRects;
 186             pPrevRect -= curNumRects;
 187
 188             do
 189             {
 190                 pPrevRect->bottom = pCurRect->bottom;
 191                 pPrevRect++;
 192                 pCurRect++;
 193                 curNumRects -= 1;
 194             } while (curNumRects != 0);
 195
 196             if (pCurRect == pRegEnd) curStart = prevStart;
 197             else do { *pPrevRect++ = *pCurRect++; } while (pCurRect != pRegEnd);
 198
 199         }
 200     }
 201     return curStart;
 202 }
 203
 204 /* apply an operation to two regions */
 205 /* check the GDI version of the code for explanations */
 206 static int region_op( struct region *newReg, const struct region *reg1, const struct region *reg2,
 207                       overlap_func_t overlap_func,
 208                       non_overlap_func_t non_overlap1_func,
 209                       non_overlap_func_t non_overlap2_func )
 210 {
 211     int ybot, ytop, top, bot, prevBand, curBand;
 212     const rectangle_t *r1BandEnd, *r2BandEnd;
 213
 214     const rectangle_t *r1 = reg1->rects;
 215     const rectangle_t *r2 = reg2->rects;
 216     const rectangle_t *r1End = r1 + reg1->num_rects;
 217     const rectangle_t *r2End = r2 + reg2->num_rects;
 218
 219     rectangle_t *new_rects, *old_rects = newReg->rects;
 220     int new_size, ret = 0;
 221
 222     new_size = max( reg1->num_rects, reg2->num_rects ) * 2;
 223     if (!(new_rects = mem_alloc( new_size * sizeof(*newReg->rects) ))) return 0;
 224
 225     newReg->size = new_size;
 226     newReg->rects = new_rects;
 227     newReg->num_rects = 0;
 228
 229     if (reg1->extents.top < reg2->extents.top)
 230         ybot = reg1->extents.top;
 231     else
 232         ybot = reg2->extents.top;
 233
 234     prevBand = 0;
 235
 236     do
 237     {
 238         curBand = newReg->num_rects;
 239
 240         r1BandEnd = r1;
 241         while ((r1BandEnd != r1End) && (r1BandEnd->top == r1->top)) r1BandEnd++;
 242
 243         r2BandEnd = r2;
 244         while ((r2BandEnd != r2End) && (r2BandEnd->top == r2->top)) r2BandEnd++;
 245
 246         if (r1->top < r2->top)
 247         {
 248             top = max(r1->top,ybot);
 249             bot = min(r1->bottom,r2->top);
 250
 251             if ((top != bot) && non_overlap1_func)
 252             {
 253                 if (!non_overlap1_func( newReg, r1, r1BandEnd, top, bot )) goto done;
 254             }
 255
 256             ytop = r2->top;
 257         }
 258         else if (r2->top < r1->top)
 259         {
 260             top = max(r2->top,ybot);
 261             bot = min(r2->bottom,r1->top);
 262
 263             if ((top != bot) && non_overlap2_func)
 264             {
 265                 if (!non_overlap2_func( newReg, r2, r2BandEnd, top, bot )) goto done;
 266             }
 267
 268             ytop = r1->top;
 269         }
 270         else
 271         {
 272             ytop = r1->top;
 273         }
 274
 275         if (newReg->num_rects != curBand)
 276             prevBand = coalesce_region(newReg, prevBand, curBand);
 277
 278         ybot = min(r1->bottom, r2->bottom);
 279         curBand = newReg->num_rects;
 280         if (ybot > ytop)
 281         {
 282             if (!overlap_func( newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot )) goto done;
 283         }
 284
 285         if (newReg->num_rects != curBand)
 286             prevBand = coalesce_region(newReg, prevBand, curBand);
 287
 288         if (r1->bottom == ybot) r1 = r1BandEnd;
 289         if (r2->bottom == ybot) r2 = r2BandEnd;
 290     } while ((r1 != r1End) && (r2 != r2End));
 291
 292     curBand = newReg->num_rects;
 293     if (r1 != r1End)
 294     {
 295         if (non_overlap1_func)
 296         {
 297             do
 298             {
 299                 r1BandEnd = r1;
 300                 while ((r1BandEnd < r1End) && (r1BandEnd->top == r1->top)) r1BandEnd++;
 301                 if (!non_overlap1_func( newReg, r1, r1BandEnd, max(r1->top,ybot), r1->bottom ))
 302                     goto done;
 303                 r1 = r1BandEnd;
 304             } while (r1 != r1End);
 305         }
 306     }
 307     else if ((r2 != r2End) && non_overlap2_func)
 308     {
 309         do
 310         {
 311             r2BandEnd = r2;
 312             while ((r2BandEnd < r2End) && (r2BandEnd->top == r2->top)) r2BandEnd++;
 313             if (!non_overlap2_func( newReg, r2, r2BandEnd, max(r2->top,ybot), r2->bottom ))
 314                 goto done;
 315             r2 = r2BandEnd;
 316         } while (r2 != r2End);
 317     }
 318
 319     if (newReg->num_rects != curBand) coalesce_region(newReg, prevBand, curBand);
 320
 321     if ((newReg->num_rects < (newReg->size / 2)) && (newReg->size > 2))
 322     {
 323         new_size = max( newReg->num_rects, RGN_DEFAULT_RECTS );
 324         if ((new_rects = realloc( newReg->rects, sizeof(*newReg->rects) * new_size )))
 325         {
 326             newReg->rects = new_rects;
 327             newReg->size = new_size;
 328         }
 329     }
 330     ret = 1;
 331 done:
 332     free( old_rects );
 333     return ret;
 334 }
 335
 336 /* recalculate the extents of a region */
 337 static void set_region_extents( struct region *region )
 338 {
 339     rectangle_t *pRect, *pRectEnd;
 340
 341     if (region->num_rects == 0)
 342     {
 343         region->extents.left = 0;
 344         region->extents.top = 0;
 345         region->extents.right = 0;
 346         region->extents.bottom = 0;
 347         return;
 348     }
 349
 350     pRect = region->rects;
 351     pRectEnd = &pRect[region->num_rects - 1];
 352
 353     region->extents.left = pRect->left;
 354     region->extents.top = pRect->top;
 355     region->extents.right = pRectEnd->right;
 356     region->extents.bottom = pRectEnd->bottom;
 357
 358     while (pRect <= pRectEnd)
 359     {
 360         if (pRect->left < region->extents.left) region->extents.left = pRect->left;
 361         if (pRect->right > region->extents.right) region->extents.right = pRect->right;
 362         pRect++;
 363     }
 364 }
 365
 366 /* handle an overlapping band for intersect_region */
 367 static int intersect_overlapping( struct region *pReg,
 368                                   const rectangle_t *r1, const rectangle_t *r1End,
 369                                   const rectangle_t *r2, const rectangle_t *r2End,
 370                                   int top, int bottom )
 371
 372 {
 373     int left, right;
 374
 375     while ((r1 != r1End) && (r2 != r2End))
 376     {
 377         left = max(r1->left, r2->left);
 378         right = min(r1->right, r2->right);
 379
 380         if (left < right)
 381         {
 382             rectangle_t *rect = add_rect( pReg );
 383             if (!rect) return 0;
 384             rect->left = left;
 385             rect->top = top;
 386             rect->right = right;
 387             rect->bottom = bottom;
 388         }
 389
 390         if (r1->right < r2->right) r1++;
 391         else if (r2->right < r1->right) r2++;
 392         else
 393         {
 394             r1++;
 395             r2++;
 396         }
 397     }
 398     return 1;
 399 }
 400
 401 /* handle a non-overlapping band for subtract_region */
 402 static int subtract_non_overlapping( struct region *pReg, const rectangle_t *r,
 403                                   const rectangle_t *rEnd, int top, int bottom )
 404 {
 405     while (r != rEnd)
 406     {
 407         rectangle_t *rect = add_rect( pReg );
 408         if (!rect) return 0;
 409         rect->left = r->left;
 410         rect->top = top;
 411         rect->right = r->right;
 412         rect->bottom = bottom;
 413         r++;
 414     }
 415     return 1;
 416 }
 417
 418 /* handle an overlapping band for subtract_region */
 419 static int subtract_overlapping( struct region *pReg,
 420                                  const rectangle_t *r1, const rectangle_t *r1End,
 421                                  const rectangle_t *r2, const rectangle_t *r2End,
 422                                  int top, int bottom )
 423 {
 424     int left = r1->left;
 425
 426     while ((r1 != r1End) && (r2 != r2End))
 427     {
 428         if (r2->right <= left) r2++;
 429         else if (r2->left <= left)
 430         {
 431             left = r2->right;
 432             if (left >= r1->right)
 433             {
 434                 r1++;
 435                 if (r1 != r1End)
 436                     left = r1->left;
 437             }
 438             else r2++;
 439         }
 440         else if (r2->left < r1->right)
 441         {
 442             rectangle_t *rect = add_rect( pReg );
 443             if (!rect) return 0;
 444             rect->left = left;
 445             rect->top = top;
 446             rect->right = r2->left;
 447             rect->bottom = bottom;
 448             left = r2->right;
 449             if (left >= r1->right)
 450             {
 451                 r1++;
 452                 if (r1 != r1End)
 453                     left = r1->left;
 454             }
 455             else r2++;
 456         }
 457         else
 458         {
 459             if (r1->right > left)
 460             {
 461                 rectangle_t *rect = add_rect( pReg );
 462                 if (!rect) return 0;
 463                 rect->left = left;
 464                 rect->top = top;
 465                 rect->right = r1->right;
 466                 rect->bottom = bottom;
 467             }
 468             r1++;
 469             left = r1->left;
 470         }
 471     }
 472
 473     while (r1 != r1End)
 474     {
 475         rectangle_t *rect = add_rect( pReg );
 476         if (!rect) return 0;
 477         rect->left = left;
 478         rect->top = top;
 479         rect->right = r1->right;
 480         rect->bottom = bottom;
 481         r1++;
 482         if (r1 != r1End) left = r1->left;
 483     }
 484     return 1;
 485 }
 486
 487 /* handle a non-overlapping band for union_region */
 488 static int union_non_overlapping( struct region *pReg, const rectangle_t *r,
 489                                   const rectangle_t *rEnd, int top, int bottom )
 490 {
 491     while (r != rEnd)
 492     {
 493         rectangle_t *rect = add_rect( pReg );
 494         if (!rect) return 0;
 495         rect->left = r->left;
 496         rect->top = top;
 497         rect->right = r->right;
 498         rect->bottom = bottom;
 499         r++;
 500     }
 501     return 1;
 502 }
 503
 504 /* handle an overlapping band for union_region */
 505 static int union_overlapping( struct region *pReg,
 506                               const rectangle_t *r1, const rectangle_t *r1End,
 507                               const rectangle_t *r2, const rectangle_t *r2End,
 508                               int top, int bottom )
 509 {
 510 #define MERGERECT(r) \
 511     if ((pReg->num_rects != 0) &&  \
 512         (pReg->rects[pReg->num_rects-1].top == top) &&  \
 513         (pReg->rects[pReg->num_rects-1].bottom == bottom) &&  \
 514         (pReg->rects[pReg->num_rects-1].right >= r->left))  \
 515     {  \
 516         if (pReg->rects[pReg->num_rects-1].right < r->right)  \
 517         {  \
 518             pReg->rects[pReg->num_rects-1].right = r->right;  \
 519         }  \
 520     }  \
 521     else  \
 522     {  \
 523         rectangle_t *rect = add_rect( pReg ); \
 524         if (!rect) return 0; \
 525         rect->top = top;  \
 526         rect->bottom = bottom;  \
 527         rect->left = r->left;  \
 528         rect->right = r->right;  \
 529     }  \
 530     r++;
 531
 532     while ((r1 != r1End) && (r2 != r2End))
 533     {
 534         if (r1->left < r2->left)
 535         {
 536             MERGERECT(r1);
 537         }
 538         else
 539         {
 540             MERGERECT(r2);
 541         }
 542     }
 543
 544     if (r1 != r1End)
 545     {
 546         do
 547         {
 548             MERGERECT(r1);
 549         } while (r1 != r1End);
 550     }
 551     else while (r2 != r2End)
 552     {
 553         MERGERECT(r2);
 554     }
 555     return 1;
 556 #undef MERGERECT
 557 }
 558
 559
 560 /* create a region from an array of rectangles */
 561 struct region *create_region( const rectangle_t *rects, unsigned int nb_rects )
 562 {
 563     struct region *region;
 564     unsigned int size = max( nb_rects, RGN_DEFAULT_RECTS );
 565
 566     if (!validate_rectangles( rects, nb_rects ))
 567     {
 568         set_error( STATUS_INVALID_PARAMETER );
 569         return NULL;
 570     }
 571     if (!(region = mem_alloc( sizeof(*region) ))) return NULL;
 572     if (!(region->rects = mem_alloc( size * sizeof(*region->rects) )))
 573     {
 574         free( region );
 575         return NULL;
 576     }
 577     region->size = size;
 578     region->num_rects = nb_rects;
 579     memcpy( region->rects, rects, nb_rects * sizeof(*rects) );
 580     set_region_extents( region );
 581     return region;
 582 }
 583
 584 /* create a region from request data */
 585 struct region *create_region_from_req_data( const void *data, size_t size )
 586 {
 587     const rectangle_t *rects = data;
 588     int nb_rects = size / sizeof(rectangle_t);
 589
 590     /* special case: empty region can be specified by a single all-zero rectangle */
 591     if (nb_rects == 1 && !memcmp( rects, &empty_rect, sizeof(empty_rect) )) nb_rects = 0;
 592     return create_region( rects, nb_rects );
 593 }
 594
 595 /* free a region */
 596 void free_region( struct region *region )
 597 {
 598     free( region->rects );
 599     free( region );
 600 }
 601
 602 /* set region to a simple rectangle */
 603 void set_region_rect( struct region *region, const rectangle_t *rect )
 604 {
 605     if (rect->left < rect->right && rect->top < rect->bottom)
 606     {
 607         region->num_rects = 1;
 608         region->rects[0] = region->extents = *rect;
 609     }
 610     else
 611     {
 612         region->num_rects = 0;
 613         region->extents.left = 0;
 614         region->extents.top = 0;
 615         region->extents.right = 0;
 616         region->extents.bottom = 0;
 617     }
 618 }
 619
 620 /* retrieve the region data for sending to the client */
 621 rectangle_t *get_region_data( const struct region *region, size_t max_size, size_t *total_size )
 622 {
 623     const rectangle_t *data = region->rects;
 624
 625     if (!(*total_size = region->num_rects * sizeof(rectangle_t)))
 626     {
 627         /* return a single empty rect for empty regions */
 628         *total_size = sizeof(empty_rect);
 629         data = &empty_rect;
 630     }
 631     if (max_size >= *total_size) return memdup( data, *total_size );
 632     set_error( STATUS_BUFFER_OVERFLOW );
 633     return NULL;
 634 }
 635
 636 /* retrieve the region data for sending to the client and free the region at the same time */
 637 rectangle_t *get_region_data_and_free( struct region *region, size_t max_size, size_t *total_size )
 638 {
 639     rectangle_t *ret = region->rects;
 640
 641     if (!(*total_size = region->num_rects * sizeof(rectangle_t)))
 642     {
 643         /* return a single empty rect for empty regions */
 644         *total_size = sizeof(empty_rect);
 645         if (max_size >= sizeof(empty_rect))
 646         {
 647             ret = memdup( &empty_rect, sizeof(empty_rect) );
 648             free( region->rects );
 649         }
 650     }
 651
 652     if (max_size < *total_size)
 653     {
 654         free( region->rects );
 655         set_error( STATUS_BUFFER_OVERFLOW );
 656         ret = NULL;
 657     }
 658     free( region );
 659     return ret;
 660 }
 661
 662 /* check if a given region is empty */
 663 int is_region_empty( const struct region *region )
 664 {
 665     return region->num_rects == 0;
 666 }
 667
 668
 669 /* get the extents rect of a region */
 670 void get_region_extents( const struct region *region, rectangle_t *rect )
 671 {
 672     *rect = region->extents;
 673 }
 674
 675 /* add an offset to a region */
 676 void offset_region( struct region *region, int x, int y )
 677 {
 678     rectangle_t *rect, *end;
 679
 680     for (rect = region->rects, end = rect + region->num_rects; rect < end; rect++)
 681     {
 682         rect->left += x;
 683         rect->right += x;
 684         rect->top += y;
 685         rect->bottom += y;
 686     }
 687     region->extents.left += x;
 688     region->extents.right += x;
 689     region->extents.top += y;
 690     region->extents.bottom += y;
 691 }
 692
 693 /* make a copy of a region; returns dst or NULL on error */
 694 struct region *copy_region( struct region *dst, const struct region *src )
 695 {
 696     if (dst == src) return dst;
 697
 698     if (dst->size < src->num_rects)
 699     {
 700         rectangle_t *rect = realloc( dst->rects, src->num_rects * sizeof(*rect) );
 701         if (!rect)
 702         {
 703             set_error( STATUS_NO_MEMORY );
 704             return NULL;
 705         }
 706         dst->rects = rect;
 707         dst->size = src->num_rects;
 708     }
 709     dst->num_rects = src->num_rects;
 710     dst->extents = src->extents;
 711     memcpy( dst->rects, src->rects, src->num_rects * sizeof(*dst->rects) );
 712     return dst;
 713 }
 714
 715 /* compute the intersection of two regions into dst, which can be one of the source regions */
 716 struct region *intersect_region( struct region *dst, const struct region *src1,
 717                                  const struct region *src2 )
 718 {
 719     if (!src1->num_rects || !src2->num_rects || !EXTENTCHECK(&src1->extents, &src2->extents))
 720     {
 721         dst->num_rects = 0;
 722         dst->extents.left = 0;
 723         dst->extents.top = 0;
 724         dst->extents.right = 0;
 725         dst->extents.bottom = 0;
 726         return dst;
 727     }
 728     if (!region_op( dst, src1, src2, intersect_overlapping, NULL, NULL )) return NULL;
 729     set_region_extents( dst );
 730     return dst;
 731 }
 732
 733 /* compute the subtraction of two regions into dst, which can be one of the source regions */
 734 struct region *subtract_region( struct region *dst, const struct region *src1,
 735                                 const struct region *src2 )
 736 {
 737     if (!src1->num_rects || !src2->num_rects || !EXTENTCHECK(&src1->extents, &src2->extents))
 738         return copy_region( dst, src1 );
 739
 740     if (!region_op( dst, src1, src2, subtract_overlapping,
 741                     subtract_non_overlapping, NULL )) return NULL;
 742     set_region_extents( dst );
 743     return dst;
 744 }
 745
 746 /* compute the union of two regions into dst, which can be one of the source regions */
 747 struct region *union_region( struct region *dst, const struct region *src1,
 748                              const struct region *src2 )
 749 {
 750     if (src1 == src2) return copy_region( dst, src1 );
 751     if (!src1->num_rects) return copy_region( dst, src2 );
 752     if (!src2->num_rects) return copy_region( dst, src1 );
 753
 754     if ((src1->num_rects == 1) &&
 755         (src1->extents.left <= src2->extents.left) &&
 756         (src1->extents.top <= src2->extents.top) &&
 757         (src1->extents.right >= src2->extents.right) &&
 758         (src1->extents.bottom >= src2->extents.bottom))
 759         return copy_region( dst, src1 );
 760
 761     if ((src2->num_rects == 1) &&
 762         (src2->extents.left <= src1->extents.left) &&
 763         (src2->extents.top <= src1->extents.top) &&
 764         (src2->extents.right >= src1->extents.right) &&
 765         (src2->extents.bottom >= src1->extents.bottom))
 766         return copy_region( dst, src2 );
 767
 768     if (!region_op( dst, src1, src2, union_overlapping,
 769                     union_non_overlapping, union_non_overlapping )) return NULL;
 770
 771     dst->extents.left = min(src1->extents.left, src2->extents.left);
 772     dst->extents.top = min(src1->extents.top, src2->extents.top);
 773     dst->extents.right = max(src1->extents.right, src2->extents.right);
 774     dst->extents.bottom = max(src1->extents.bottom, src2->extents.bottom);
 775     return dst;
 776 }
 777
 778 /* compute the exclusive or of two regions into dst, which can be one of the source regions */
 779 struct region *xor_region( struct region *dst, const struct region *src1,
 780                            const struct region *src2 )
 781 {
 782     struct region *tmp = create_empty_region();
 783
 784     if (!tmp) return NULL;
 785
 786     if (!subtract_region( tmp, src1, src2 ) ||
 787         !subtract_region( dst, src2, src1 ) ||
 788         !union_region( dst, dst, tmp ))
 789         dst = NULL;
 790
 791     free_region( tmp );
 792     return dst;
 793 }
 794
 795 /* check if the given point is inside the region */
 796 int point_in_region( struct region *region, int x, int y )
 797 {
 798     const rectangle_t *ptr, *end;
 799
 800     for (ptr = region->rects, end = region->rects + region->num_rects; ptr < end; ptr++)
 801     {
 802         if (ptr->top > y) return 0;
 803         if (ptr->bottom <= y) continue;
 804         /* now we are in the correct band */
 805         if (ptr->left > x) return 0;
 806         if (ptr->right <= x) continue;
 807         return 1;
 808     }
 809     return 0;
 810 }
 811
 812 /* check if the given rectangle is (at least partially) inside the region */
 813 int rect_in_region( struct region *region, const rectangle_t *rect )
 814 {
 815     const rectangle_t *ptr, *end;
 816
 817     for (ptr = region->rects, end = region->rects + region->num_rects; ptr < end; ptr++)
 818     {
 819         if (ptr->top >= rect->bottom) return 0;
 820         if (ptr->bottom <= rect->top) continue;
 821         if (ptr->left >= rect->right) continue;
 822         if (ptr->right <= rect->left) continue;
 823         return 1;
 824     }
 825     return 0;
 826 }