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
  80 struct region
  81 {
  82     int size;
  83     int num_rects;
  84     rectangle_t *rects;
  85     rectangle_t extents;
  86 };
  87
  88
  89 #define RGN_DEFAULT_RECTS 2
  90
  91 #define EXTENTCHECK(r1, r2) \
  92     ((r1)->right > (r2)->left && \
  93     (r1)->left < (r2)->right && \
  94     (r1)->bottom > (r2)->top && \
  95     (r1)->top < (r2)->bottom)
  96
  97 typedef int (*overlap_func_t)( struct region *reg, const rectangle_t *r1, const rectangle_t *r1End,
  98                                const rectangle_t *r2, const rectangle_t *r2End, int top, int bottom );
  99 typedef int (*non_overlap_func_t)( struct region *reg, const rectangle_t *r,
 100                                    const rectangle_t *rEnd, int top, int bottom );
 101
 102 static const rectangle_t empty_rect;  /* all-zero rectangle for empty regions */
 103
 104 /* add a rectangle to a region */
 105 static inline rectangle_t *add_rect( struct region *reg )
 106 {
 107     if (reg->num_rects >= reg->size - 1)
 108     {
 109         rectangle_t *new_rect = realloc( reg->rects, 2 * sizeof(rectangle_t) * reg->size );
 110         if (!new_rect)
 111         {
 112             set_error( STATUS_NO_MEMORY );
 113             return 0;
 114         }
 115         reg->rects = new_rect;
 116         reg->size *= 2;
 117     }
 118     return reg->rects + reg->num_rects++;
 119 }
 120
 121 /* make sure all the rectangles are valid and that the region is properly y-x-banded */
 122 static inline int validate_rectangles( const rectangle_t *rects, unsigned int nb_rects )
 123 {
 124     const rectangle_t *ptr, *end;
 125
 126     for (ptr = rects, end = rects + nb_rects; ptr < end; ptr++)
 127     {
 128         if (ptr->left >= ptr->right || ptr->top >= ptr->bottom) return 0;  /* empty rectangle */
 129         if (ptr == end - 1) break;
 130         if (ptr[0].top == ptr[1].top)  /* same band */
 131         {
 132             if (ptr[0].bottom != ptr[1].bottom) return 0;  /* not same y extent */
 133             if (ptr[0].right >= ptr[1].left) return 0;  /* not properly x ordered */
 134         }
 135         else  /* new band */
 136         {
 137             if (ptr[0].bottom > ptr[1].top) return 0;  /* not properly y ordered */
 138         }
 139     }
 140     return 1;
 141 }
 142
 143 /* attempt to merge the rects in the current band with those in the */
 144 /* previous one. Used only by region_op. */
 145 static int coalesce_region( struct region *pReg, int prevStart, int curStart )
 146 {
 147     int curNumRects;
 148     rectangle_t *pRegEnd = &pReg->rects[pReg->num_rects];
 149     rectangle_t *pPrevRect = &pReg->rects[prevStart];
 150     rectangle_t *pCurRect = &pReg->rects[curStart];
 151     int prevNumRects = curStart - prevStart;
 152     int bandtop = pCurRect->top;
 153
 154     for (curNumRects = 0;
 155          (pCurRect != pRegEnd) && (pCurRect->top == bandtop);
 156          curNumRects++)
 157     {
 158         pCurRect++;
 159     }
 160
 161     if (pCurRect != pRegEnd)
 162     {
 163         pRegEnd--;
 164         while (pRegEnd[-1].top == pRegEnd->top) pRegEnd--;
 165         curStart = pRegEnd - pReg->rects;
 166         pRegEnd = pReg->rects + pReg->num_rects;
 167     }
 168
 169     if ((curNumRects == prevNumRects) && (curNumRects != 0))
 170     {
 171         pCurRect -= curNumRects;
 172         if (pPrevRect->bottom == pCurRect->top)
 173         {
 174             do
 175             {
 176                 if ((pPrevRect->left != pCurRect->left) ||
 177                     (pPrevRect->right != pCurRect->right)) return curStart;
 178                 pPrevRect++;
 179                 pCurRect++;
 180                 prevNumRects -= 1;
 181             } while (prevNumRects != 0);
 182
 183             pReg->num_rects -= curNumRects;
 184             pCurRect -= curNumRects;
 185             pPrevRect -= curNumRects;
 186
 187             do
 188             {
 189                 pPrevRect->bottom = pCurRect->bottom;
 190                 pPrevRect++;
 191                 pCurRect++;
 192                 curNumRects -= 1;
 193             } while (curNumRects != 0);
 194
 195             if (pCurRect == pRegEnd) curStart = prevStart;
 196             else do { *pPrevRect++ = *pCurRect++; } while (pCurRect != pRegEnd);
 197
 198         }
 199     }
 200     return curStart;
 201 }
 202
 203 /* apply an operation to two regions */
 204 /* check the GDI version of the code for explanations */
 205 static int region_op( struct region *newReg, const struct region *reg1, const struct region *reg2,
 206                       overlap_func_t overlap_func,
 207                       non_overlap_func_t non_overlap1_func,
 208                       non_overlap_func_t non_overlap2_func )
 209 {
 210     int ybot, ytop, top, bot, prevBand, curBand;
 211     const rectangle_t *r1BandEnd, *r2BandEnd;
 212
 213     const rectangle_t *r1 = reg1->rects;
 214     const rectangle_t *r2 = reg2->rects;
 215     const rectangle_t *r1End = r1 + reg1->num_rects;
 216     const rectangle_t *r2End = r2 + reg2->num_rects;
 217
 218     rectangle_t *new_rects, *old_rects = newReg->rects;
 219     int new_size, ret = 0;
 220
 221     new_size = max( reg1->num_rects, reg2->num_rects ) * 2;
 222     if (!(new_rects = mem_alloc( new_size * sizeof(*newReg->rects) ))) return 0;
 223
 224     newReg->size = new_size;
 225     newReg->rects = new_rects;
 226     newReg->num_rects = 0;
 227
 228     if (reg1->extents.top < reg2->extents.top)
 229         ybot = reg1->extents.top;
 230     else
 231         ybot = reg2->extents.top;
 232
 233     prevBand = 0;
 234
 235     do
 236     {
 237         curBand = newReg->num_rects;
 238
 239         r1BandEnd = r1;
 240         while ((r1BandEnd != r1End) && (r1BandEnd->top == r1->top)) r1BandEnd++;
 241
 242         r2BandEnd = r2;
 243         while ((r2BandEnd != r2End) && (r2BandEnd->top == r2->top)) r2BandEnd++;
 244
 245         if (r1->top < r2->top)
 246         {
 247             top = max(r1->top,ybot);
 248             bot = min(r1->bottom,r2->top);
 249
 250             if ((top != bot) && non_overlap1_func)
 251             {
 252                 if (!non_overlap1_func( newReg, r1, r1BandEnd, top, bot )) goto done;
 253             }
 254
 255             ytop = r2->top;
 256         }
 257         else if (r2->top < r1->top)
 258         {
 259             top = max(r2->top,ybot);
 260             bot = min(r2->bottom,r1->top);
 261
 262             if ((top != bot) && non_overlap2_func)
 263             {
 264                 if (!non_overlap2_func( newReg, r2, r2BandEnd, top, bot )) goto done;
 265             }
 266
 267             ytop = r1->top;
 268         }
 269         else
 270         {
 271             ytop = r1->top;
 272         }
 273
 274         if (newReg->num_rects != curBand)
 275             prevBand = coalesce_region(newReg, prevBand, curBand);
 276
 277         ybot = min(r1->bottom, r2->bottom);
 278         curBand = newReg->num_rects;
 279         if (ybot > ytop)
 280         {
 281             if (!overlap_func( newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot )) goto done;
 282         }
 283
 284         if (newReg->num_rects != curBand)
 285             prevBand = coalesce_region(newReg, prevBand, curBand);
 286
 287         if (r1->bottom == ybot) r1 = r1BandEnd;
 288         if (r2->bottom == ybot) r2 = r2BandEnd;
 289     } while ((r1 != r1End) && (r2 != r2End));
 290
 291     curBand = newReg->num_rects;
 292     if (r1 != r1End)
 293     {
 294         if (non_overlap1_func)
 295         {
 296             do
 297             {
 298                 r1BandEnd = r1;
 299                 while ((r1BandEnd < r1End) && (r1BandEnd->top == r1->top)) r1BandEnd++;
 300                 if (!non_overlap1_func( newReg, r1, r1BandEnd, max(r1->top,ybot), r1->bottom ))
 301                     goto done;
 302                 r1 = r1BandEnd;
 303             } while (r1 != r1End);
 304         }
 305     }
 306     else if ((r2 != r2End) && non_overlap2_func)
 307     {
 308         do
 309         {
 310             r2BandEnd = r2;
 311             while ((r2BandEnd < r2End) && (r2BandEnd->top == r2->top)) r2BandEnd++;
 312             if (!non_overlap2_func( newReg, r2, r2BandEnd, max(r2->top,ybot), r2->bottom ))
 313                 goto done;
 314             r2 = r2BandEnd;
 315         } while (r2 != r2End);
 316     }
 317
 318     if (newReg->num_rects != curBand) coalesce_region(newReg, prevBand, curBand);
 319
 320     if ((newReg->num_rects < (newReg->size / 2)) && (newReg->size > 2))
 321     {
 322         new_size = max( newReg->num_rects, RGN_DEFAULT_RECTS );
 323         if ((new_rects = realloc( newReg->rects, sizeof(*newReg->rects) * new_size )))
 324         {
 325             newReg->rects = new_rects;
 326             newReg->size = new_size;
 327         }
 328     }
 329     ret = 1;
 330 done:
 331     free( old_rects );
 332     return ret;
 333 }
 334
 335 /* recalculate the extents of a region */
 336 static void set_region_extents( struct region *region )
 337 {
 338     rectangle_t *pRect, *pRectEnd;
 339
 340     if (region->num_rects == 0)
 341     {
 342         region->extents.left = 0;
 343         region->extents.top = 0;
 344         region->extents.right = 0;
 345         region->extents.bottom = 0;
 346         return;
 347     }
 348
 349     pRect = region->rects;
 350     pRectEnd = &pRect[region->num_rects - 1];
 351
 352     region->extents.left = pRect->left;
 353     region->extents.top = pRect->top;
 354     region->extents.right = pRectEnd->right;
 355     region->extents.bottom = pRectEnd->bottom;
 356
 357     while (pRect <= pRectEnd)
 358     {
 359         if (pRect->left < region->extents.left) region->extents.left = pRect->left;
 360         if (pRect->right > region->extents.right) region->extents.right = pRect->right;
 361         pRect++;
 362     }
 363 }
 364
 365 /* handle an overlapping band for intersect_region */
 366 static int intersect_overlapping( struct region *pReg,
 367                                   const rectangle_t *r1, const rectangle_t *r1End,
 368                                   const rectangle_t *r2, const rectangle_t *r2End,
 369                                   int top, int bottom )
 370
 371 {
 372     int left, right;
 373
 374     while ((r1 != r1End) && (r2 != r2End))
 375     {
 376         left = max(r1->left, r2->left);
 377         right = min(r1->right, r2->right);
 378
 379         if (left < right)
 380         {
 381             rectangle_t *rect = add_rect( pReg );
 382             if (!rect) return 0;
 383             rect->left = left;
 384             rect->top = top;
 385             rect->right = right;
 386             rect->bottom = bottom;
 387         }
 388
 389         if (r1->right < r2->right) r1++;
 390         else if (r2->right < r1->right) r2++;
 391         else
 392         {
 393             r1++;
 394             r2++;
 395         }
 396     }
 397     return 1;
 398 }
 399
 400 /* handle a non-overlapping band for subtract_region */
 401 static int subtract_non_overlapping( struct region *pReg, const rectangle_t *r,
 402                                   const rectangle_t *rEnd, int top, int bottom )
 403 {
 404     while (r != rEnd)
 405     {
 406         rectangle_t *rect = add_rect( pReg );
 407         if (!rect) return 0;
 408         rect->left = r->left;
 409         rect->top = top;
 410         rect->right = r->right;
 411         rect->bottom = bottom;
 412         r++;
 413     }
 414     return 1;
 415 }
 416
 417 /* handle an overlapping band for subtract_region */
 418 static int subtract_overlapping( struct region *pReg,
 419                                  const rectangle_t *r1, const rectangle_t *r1End,
 420                                  const rectangle_t *r2, const rectangle_t *r2End,
 421                                  int top, int bottom )
 422 {
 423     int left = r1->left;
 424
 425     while ((r1 != r1End) && (r2 != r2End))
 426     {
 427         if (r2->right <= left) r2++;
 428         else if (r2->left <= left)
 429         {
 430             left = r2->right;
 431             if (left >= r1->right)
 432             {
 433                 r1++;
 434                 if (r1 != r1End)
 435                     left = r1->left;
 436             }
 437             else r2++;
 438         }
 439         else if (r2->left < r1->right)
 440         {
 441             rectangle_t *rect = add_rect( pReg );
 442             if (!rect) return 0;
 443             rect->left = left;
 444             rect->top = top;
 445             rect->right = r2->left;
 446             rect->bottom = bottom;
 447             left = r2->right;
 448             if (left >= r1->right)
 449             {
 450                 r1++;
 451                 if (r1 != r1End)
 452                     left = r1->left;
 453             }
 454             else r2++;
 455         }
 456         else
 457         {
 458             if (r1->right > left)
 459             {
 460                 rectangle_t *rect = add_rect( pReg );
 461                 if (!rect) return 0;
 462                 rect->left = left;
 463                 rect->top = top;
 464                 rect->right = r1->right;
 465                 rect->bottom = bottom;
 466             }
 467             r1++;
 468             left = r1->left;
 469         }
 470     }
 471
 472     while (r1 != r1End)
 473     {
 474         rectangle_t *rect = add_rect( pReg );
 475         if (!rect) return 0;
 476         rect->left = left;
 477         rect->top = top;
 478         rect->right = r1->right;
 479         rect->bottom = bottom;
 480         r1++;
 481         if (r1 != r1End) left = r1->left;
 482     }
 483     return 1;
 484 }
 485
 486 /* handle a non-overlapping band for union_region */
 487 static int union_non_overlapping( struct region *pReg, const rectangle_t *r,
 488                                   const rectangle_t *rEnd, int top, int bottom )
 489 {
 490     while (r != rEnd)
 491     {
 492         rectangle_t *rect = add_rect( pReg );
 493         if (!rect) return 0;
 494         rect->left = r->left;
 495         rect->top = top;
 496         rect->right = r->right;
 497         rect->bottom = bottom;
 498         r++;
 499     }
 500     return 1;
 501 }
 502
 503 /* handle an overlapping band for union_region */
 504 static int union_overlapping( struct region *pReg,
 505                               const rectangle_t *r1, const rectangle_t *r1End,
 506                               const rectangle_t *r2, const rectangle_t *r2End,
 507                               int top, int bottom )
 508 {
 509 #define MERGERECT(r) \
 510     if ((pReg->num_rects != 0) &&  \
 511         (pReg->rects[pReg->num_rects-1].top == top) &&  \
 512         (pReg->rects[pReg->num_rects-1].bottom == bottom) &&  \
 513         (pReg->rects[pReg->num_rects-1].right >= r->left))  \
 514     {  \
 515         if (pReg->rects[pReg->num_rects-1].right < r->right)  \
 516         {  \
 517             pReg->rects[pReg->num_rects-1].right = r->right;  \
 518         }  \
 519     }  \
 520     else  \
 521     {  \
 522         rectangle_t *rect = add_rect( pReg ); \
 523         if (!rect) return 0; \
 524         rect->top = top;  \
 525         rect->bottom = bottom;  \
 526         rect->left = r->left;  \
 527         rect->right = r->right;  \
 528     }  \
 529     r++;
 530
 531     while ((r1 != r1End) && (r2 != r2End))
 532     {
 533         if (r1->left < r2->left)
 534         {
 535             MERGERECT(r1);
 536         }
 537         else
 538         {
 539             MERGERECT(r2);
 540         }
 541     }
 542
 543     if (r1 != r1End)
 544     {
 545         do
 546         {
 547             MERGERECT(r1);
 548         } while (r1 != r1End);
 549     }
 550     else while (r2 != r2End)
 551     {
 552         MERGERECT(r2);
 553     }
 554     return 1;
 555 #undef MERGERECT
 556 }
 557
 558
 559 /* create a region from an array of rectangles */
 560 struct region *create_region( const rectangle_t *rects, unsigned int nb_rects )
 561 {
 562     struct region *region;
 563     unsigned int size = max( nb_rects, RGN_DEFAULT_RECTS );
 564
 565     if (!validate_rectangles( rects, nb_rects ))
 566     {
 567         set_error( STATUS_INVALID_PARAMETER );
 568         return NULL;
 569     }
 570     if (!(region = mem_alloc( sizeof(*region) ))) return NULL;
 571     if (!(region->rects = mem_alloc( size * sizeof(*region->rects) )))
 572     {
 573         free( region );
 574         return NULL;
 575     }
 576     region->size = size;
 577     region->num_rects = nb_rects;
 578     memcpy( region->rects, rects, nb_rects * sizeof(*rects) );
 579     set_region_extents( region );
 580     return region;
 581 }
 582
 583 /* create a region from request data */
 584 struct region *create_region_from_req_data( const void *data, size_t size )
 585 {
 586     const rectangle_t *rects = data;
 587     int nb_rects = size / sizeof(rectangle_t);
 588
 589     /* special case: empty region can be specified by a single all-zero rectangle */
 590     if (nb_rects == 1 && !memcmp( rects, &empty_rect, sizeof(empty_rect) )) nb_rects = 0;
 591     return create_region( rects, nb_rects );
 592 }
 593
 594 /* free a region */
 595 void free_region( struct region *region )
 596 {
 597     free( region->rects );
 598     free( region );
 599 }
 600
 601 /* set region to a simple rectangle */
 602 void set_region_rect( struct region *region, const rectangle_t *rect )
 603 {
 604     if (rect->left < rect->right && rect->top < rect->bottom)
 605     {
 606         region->num_rects = 1;
 607         region->rects[0] = region->extents = *rect;
 608     }
 609     else
 610     {
 611         region->num_rects = 0;
 612         region->extents.left = 0;
 613         region->extents.top = 0;
 614         region->extents.right = 0;
 615         region->extents.bottom = 0;
 616     }
 617 }
 618
 619 /* retrieve the region data for sending to the client */
 620 rectangle_t *get_region_data( const struct region *region, size_t *total_size )
 621 {
 622     if (!(*total_size = region->num_rects * sizeof(rectangle_t)))
 623     {
 624         /* return a single empty rect for empty regions */
 625         *total_size = sizeof(empty_rect);
 626         return memdup( &empty_rect, sizeof(empty_rect) );
 627     }
 628     return memdup( region->rects, *total_size );
 629 }
 630
 631 /* retrieve the region data for sending to the client and free the region at the same time */
 632 rectangle_t *get_region_data_and_free( struct region *region, size_t *total_size )
 633 {
 634     rectangle_t *ret = region->rects;
 635
 636     if (!(*total_size = region->num_rects * sizeof(rectangle_t)))
 637     {
 638         /* return a single empty rect for empty regions */
 639         *total_size = sizeof(empty_rect);
 640         ret = memdup( &empty_rect, sizeof(empty_rect) );
 641     }
 642     free( region );
 643     return ret;
 644 }
 645
 646 /* check if a given region is empty */
 647 int is_region_empty( const struct region *region )
 648 {
 649     return region->num_rects == 0;
 650 }
 651
 652
 653 /* get the extents rect of a region */
 654 void get_region_extents( const struct region *region, rectangle_t *rect )
 655 {
 656     *rect = region->extents;
 657 }
 658
 659 /* add an offset to a region */
 660 void offset_region( struct region *region, int x, int y )
 661 {
 662     rectangle_t *rect, *end;
 663
 664     for (rect = region->rects, end = rect + region->num_rects; rect < end; rect++)
 665     {
 666         rect->left += x;
 667         rect->right += x;
 668         rect->top += y;
 669         rect->bottom += y;
 670     }
 671     region->extents.left += x;
 672     region->extents.right += x;
 673     region->extents.top += y;
 674     region->extents.bottom += y;
 675 }
 676
 677 /* make a copy of a region; returns dst or NULL on error */
 678 struct region *copy_region( struct region *dst, const struct region *src )
 679 {
 680     if (dst == src) return dst;
 681
 682     if (dst->size < src->num_rects)
 683     {
 684         rectangle_t *rect = realloc( dst->rects, src->num_rects * sizeof(*rect) );
 685         if (!rect)
 686         {
 687             set_error( STATUS_NO_MEMORY );
 688             return NULL;
 689         }
 690         dst->rects = rect;
 691         dst->size = src->num_rects;
 692     }
 693     dst->num_rects = src->num_rects;
 694     dst->extents = src->extents;
 695     memcpy( dst->rects, src->rects, src->num_rects * sizeof(*dst->rects) );
 696     return dst;
 697 }
 698
 699 /* compute the intersection of two regions into dst, which can be one of the source regions */
 700 struct region *intersect_region( struct region *dst, const struct region *src1,
 701                                  const struct region *src2 )
 702 {
 703     if (!src1->num_rects || !src2->num_rects || !EXTENTCHECK(&src1->extents, &src2->extents))
 704     {
 705         dst->num_rects = 0;
 706         dst->extents.left = 0;
 707         dst->extents.top = 0;
 708         dst->extents.right = 0;
 709         dst->extents.bottom = 0;
 710         return dst;
 711     }
 712     if (!region_op( dst, src1, src2, intersect_overlapping, NULL, NULL )) return NULL;
 713     set_region_extents( dst );
 714     return dst;
 715 }
 716
 717 /* compute the subtraction of two regions into dst, which can be one of the source regions */
 718 struct region *subtract_region( struct region *dst, const struct region *src1,
 719                                 const struct region *src2 )
 720 {
 721     if (!src1->num_rects || !src2->num_rects || !EXTENTCHECK(&src1->extents, &src2->extents))
 722         return copy_region( dst, src1 );
 723
 724     if (!region_op( dst, src1, src2, subtract_overlapping,
 725                     subtract_non_overlapping, NULL )) return NULL;
 726     set_region_extents( dst );
 727     return dst;
 728 }
 729
 730 /* compute the union of two regions into dst, which can be one of the source regions */
 731 struct region *union_region( struct region *dst, const struct region *src1,
 732                              const struct region *src2 )
 733 {
 734     if (src1 == src2) return copy_region( dst, src1 );
 735     if (!src1->num_rects) return copy_region( dst, src2 );
 736     if (!src2->num_rects) return copy_region( dst, src1 );
 737
 738     if ((src1->num_rects == 1) &&
 739         (src1->extents.left <= src2->extents.left) &&
 740         (src1->extents.top <= src2->extents.top) &&
 741         (src1->extents.right >= src2->extents.right) &&
 742         (src1->extents.bottom >= src2->extents.bottom))
 743         return copy_region( dst, src1 );
 744
 745     if ((src2->num_rects == 1) &&
 746         (src2->extents.left <= src1->extents.left) &&
 747         (src2->extents.top <= src1->extents.top) &&
 748         (src2->extents.right >= src1->extents.right) &&
 749         (src2->extents.bottom >= src1->extents.bottom))
 750         return copy_region( dst, src2 );
 751
 752     if (!region_op( dst, src1, src2, union_overlapping,
 753                     union_non_overlapping, union_non_overlapping )) return NULL;
 754
 755     dst->extents.left = min(src1->extents.left, src2->extents.left);
 756     dst->extents.top = min(src1->extents.top, src2->extents.top);
 757     dst->extents.right = max(src1->extents.right, src2->extents.right);
 758     dst->extents.bottom = max(src1->extents.bottom, src2->extents.bottom);
 759     return dst;
 760 }
 761
 762 /* check if the given point is inside the region */
 763 int point_in_region( struct region *region, int x, int y )
 764 {
 765     const rectangle_t *ptr, *end;
 766
 767     for (ptr = region->rects, end = region->rects + region->num_rects; ptr < end; ptr++)
 768     {
 769         if (ptr->top > y) return 0;
 770         if (ptr->bottom <= y) continue;
 771         /* now we are in the correct band */
 772         if (ptr->left > x) return 0;
 773         if (ptr->right <= x) continue;
 774         return 1;
 775     }
 776     return 0;
 777 }