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