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 *total_size )
 622 {
 623     if (!(*total_size = region->num_rects * sizeof(rectangle_t)))
 624     {
 625         /* return a single empty rect for empty regions */
 626         *total_size = sizeof(empty_rect);
 627         return memdup( &empty_rect, sizeof(empty_rect) );
 628     }
 629     return memdup( region->rects, *total_size );
 630 }
 631
 632 /* retrieve the region data for sending to the client and free the region at the same time */
 633 rectangle_t *get_region_data_and_free( struct region *region, size_t *total_size )
 634 {
 635     rectangle_t *ret = region->rects;
 636
 637     if (!(*total_size = region->num_rects * sizeof(rectangle_t)))
 638     {
 639         /* return a single empty rect for empty regions */
 640         *total_size = sizeof(empty_rect);
 641         ret = memdup( &empty_rect, sizeof(empty_rect) );
 642     }
 643     free( region );
 644     return ret;
 645 }
 646
 647 /* check if a given region is empty */
 648 int is_region_empty( const struct region *region )
 649 {
 650     return region->num_rects == 0;
 651 }
 652
 653
 654 /* get the extents rect of a region */
 655 void get_region_extents( const struct region *region, rectangle_t *rect )
 656 {
 657     *rect = region->extents;
 658 }
 659
 660 /* add an offset to a region */
 661 void offset_region( struct region *region, int x, int y )
 662 {
 663     rectangle_t *rect, *end;
 664
 665     for (rect = region->rects, end = rect + region->num_rects; rect < end; rect++)
 666     {
 667         rect->left += x;
 668         rect->right += x;
 669         rect->top += y;
 670         rect->bottom += y;
 671     }
 672     region->extents.left += x;
 673     region->extents.right += x;
 674     region->extents.top += y;
 675     region->extents.bottom += y;
 676 }
 677
 678 /* make a copy of a region; returns dst or NULL on error */
 679 struct region *copy_region( struct region *dst, const struct region *src )
 680 {
 681     if (dst == src) return dst;
 682
 683     if (dst->size < src->num_rects)
 684     {
 685         rectangle_t *rect = realloc( dst->rects, src->num_rects * sizeof(*rect) );
 686         if (!rect)
 687         {
 688             set_error( STATUS_NO_MEMORY );
 689             return NULL;
 690         }
 691         dst->rects = rect;
 692         dst->size = src->num_rects;
 693     }
 694     dst->num_rects = src->num_rects;
 695     dst->extents = src->extents;
 696     memcpy( dst->rects, src->rects, src->num_rects * sizeof(*dst->rects) );
 697     return dst;
 698 }
 699
 700 /* compute the intersection of two regions into dst, which can be one of the source regions */
 701 struct region *intersect_region( struct region *dst, const struct region *src1,
 702                                  const struct region *src2 )
 703 {
 704     if (!src1->num_rects || !src2->num_rects || !EXTENTCHECK(&src1->extents, &src2->extents))
 705     {
 706         dst->num_rects = 0;
 707         dst->extents.left = 0;
 708         dst->extents.top = 0;
 709         dst->extents.right = 0;
 710         dst->extents.bottom = 0;
 711         return dst;
 712     }
 713     if (!region_op( dst, src1, src2, intersect_overlapping, NULL, NULL )) return NULL;
 714     set_region_extents( dst );
 715     return dst;
 716 }
 717
 718 /* compute the subtraction of two regions into dst, which can be one of the source regions */
 719 struct region *subtract_region( struct region *dst, const struct region *src1,
 720                                 const struct region *src2 )
 721 {
 722     if (!src1->num_rects || !src2->num_rects || !EXTENTCHECK(&src1->extents, &src2->extents))
 723         return copy_region( dst, src1 );
 724
 725     if (!region_op( dst, src1, src2, subtract_overlapping,
 726                     subtract_non_overlapping, NULL )) return NULL;
 727     set_region_extents( dst );
 728     return dst;
 729 }
 730
 731 /* compute the union of two regions into dst, which can be one of the source regions */
 732 struct region *union_region( struct region *dst, const struct region *src1,
 733                              const struct region *src2 )
 734 {
 735     if (src1 == src2) return copy_region( dst, src1 );
 736     if (!src1->num_rects) return copy_region( dst, src2 );
 737     if (!src2->num_rects) return copy_region( dst, src1 );
 738
 739     if ((src1->num_rects == 1) &&
 740         (src1->extents.left <= src2->extents.left) &&
 741         (src1->extents.top <= src2->extents.top) &&
 742         (src1->extents.right >= src2->extents.right) &&
 743         (src1->extents.bottom >= src2->extents.bottom))
 744         return copy_region( dst, src1 );
 745
 746     if ((src2->num_rects == 1) &&
 747         (src2->extents.left <= src1->extents.left) &&
 748         (src2->extents.top <= src1->extents.top) &&
 749         (src2->extents.right >= src1->extents.right) &&
 750         (src2->extents.bottom >= src1->extents.bottom))
 751         return copy_region( dst, src2 );
 752
 753     if (!region_op( dst, src1, src2, union_overlapping,
 754                     union_non_overlapping, union_non_overlapping )) return NULL;
 755
 756     dst->extents.left = min(src1->extents.left, src2->extents.left);
 757     dst->extents.top = min(src1->extents.top, src2->extents.top);
 758     dst->extents.right = max(src1->extents.right, src2->extents.right);
 759     dst->extents.bottom = max(src1->extents.bottom, src2->extents.bottom);
 760     return dst;
 761 }
 762
 763 /* compute the exclusive or of two regions into dst, which can be one of the source regions */
 764 struct region *xor_region( struct region *dst, const struct region *src1,
 765                            const struct region *src2 )
 766 {
 767     struct region *tmp = create_empty_region();
 768
 769     if (!tmp) return NULL;
 770
 771     if (!subtract_region( tmp, src1, src2 ) ||
 772         !subtract_region( dst, src2, src1 ) ||
 773         !union_region( dst, dst, tmp ))
 774         dst = NULL;
 775
 776     free_region( tmp );
 777     return dst;
 778 }
 779
 780 /* check if the given point is inside the region */
 781 int point_in_region( struct region *region, int x, int y )
 782 {
 783     const rectangle_t *ptr, *end;
 784
 785     for (ptr = region->rects, end = region->rects + region->num_rects; ptr < end; ptr++)
 786     {
 787         if (ptr->top > y) return 0;
 788         if (ptr->bottom <= y) continue;
 789         /* now we are in the correct band */
 790         if (ptr->left > x) return 0;
 791         if (ptr->right <= x) continue;
 792         return 1;
 793     }
 794     return 0;
 795 }
 796
 797 /* check if the given rectangle is (at least partially) inside the region */
 798 int rect_in_region( struct region *region, const rectangle_t *rect )
 799 {
 800     const rectangle_t *ptr, *end;
 801
 802     for (ptr = region->rects, end = region->rects + region->num_rects; ptr < end; ptr++)
 803     {
 804         if (ptr->top >= rect->bottom) return 0;
 805         if (ptr->bottom <= rect->top) continue;
 806         if (ptr->left >= rect->right) continue;
 807         if (ptr->right <= rect->left) continue;
 808         return 1;
 809     }
 810     return 0;
 811 }