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 (is_rect_empty( ptr )) 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 (!is_rect_empty( rect ))
 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 = empty_rect;
 635     }
 636 }
 637
 638 /* retrieve the region data for sending to the client */
 639 rectangle_t *get_region_data( const struct region *region, data_size_t max_size, data_size_t *total_size )
 640 {
 641     const rectangle_t *data = region->rects;
 642
 643     if (!(*total_size = region->num_rects * sizeof(rectangle_t)))
 644     {
 645         /* return a single empty rect for empty regions */
 646         *total_size = sizeof(empty_rect);
 647         data = &empty_rect;
 648     }
 649     if (max_size >= *total_size) return memdup( data, *total_size );
 650     set_error( STATUS_BUFFER_OVERFLOW );
 651     return NULL;
 652 }
 653
 654 /* retrieve the region data for sending to the client and free the region at the same time */
 655 rectangle_t *get_region_data_and_free( struct region *region, data_size_t max_size, data_size_t *total_size )
 656 {
 657     rectangle_t *ret = region->rects;
 658
 659     if (!(*total_size = region->num_rects * sizeof(rectangle_t)))
 660     {
 661         /* return a single empty rect for empty regions */
 662         *total_size = sizeof(empty_rect);
 663         if (max_size >= sizeof(empty_rect))
 664         {
 665             ret = memdup( &empty_rect, sizeof(empty_rect) );
 666             free( region->rects );
 667         }
 668     }
 669
 670     if (max_size < *total_size)
 671     {
 672         free( region->rects );
 673         set_error( STATUS_BUFFER_OVERFLOW );
 674         ret = NULL;
 675     }
 676     free( region );
 677     return ret;
 678 }
 679
 680 /* check if a given region is empty */
 681 int is_region_empty( const struct region *region )
 682 {
 683     return region->num_rects == 0;
 684 }
 685
 686
 687 /* checks if two regions are identical */
 688 int is_region_equal( const struct region *region1, const struct region *region2 )
 689 {
 690     int i;
 691
 692     if (region1->num_rects != region2->num_rects) return 0;
 693     if (region1->num_rects == 0) return 1;
 694     if (!is_rect_equal( &region1->extents, &region2->extents )) return 0;
 695     for (i = 0; i < region1->num_rects; i++)
 696     {
 697         if (!is_rect_equal( &region1->rects[i], &region2->rects[i] )) return 0;
 698     }
 699
 700     return 1;
 701 }
 702
 703
 704 /* get the extents rect of a region */
 705 void get_region_extents( const struct region *region, rectangle_t *rect )
 706 {
 707     *rect = region->extents;
 708 }
 709
 710 /* add an offset to a region */
 711 void offset_region( struct region *region, int x, int y )
 712 {
 713     rectangle_t *rect, *end;
 714
 715     if (!region->num_rects) return;
 716     for (rect = region->rects, end = rect + region->num_rects; rect < end; rect++)
 717         offset_rect( rect, x, y );
 718     offset_rect( &region->extents, x, y );
 719 }
 720
 721 /* mirror a region relative to a window client rect */
 722 void mirror_region( const rectangle_t *client_rect, struct region *region )
 723 {
 724     int start, end, i, j;
 725
 726     for (start = 0; start < region->num_rects; start = end + 1)
 727     {
 728         for (end = start; end < region->num_rects - 1; end++)
 729             if (region->rects[end + 1].top != region->rects[end].top) break;
 730         for (i = start, j = end; i < j; i++, j--)
 731         {
 732             rectangle_t rect = region->rects[j];
 733             region->rects[i] = region->rects[j];
 734             region->rects[j] = rect;
 735             mirror_rect( client_rect, &region->rects[j] );
 736             mirror_rect( client_rect, &region->rects[i] );
 737         }
 738         if (i == j) mirror_rect( client_rect, &region->rects[i] );
 739     }
 740     mirror_rect( client_rect, &region->extents );
 741 }
 742
 743
 744 /* scale a region for a given dpi factor */
 745 void scale_region( struct region *region, unsigned int dpi_from, unsigned int dpi_to )
 746 {
 747     rectangle_t *rect, *end;
 748
 749     if (!region->num_rects) return;
 750     for (rect = region->rects, end = rect + region->num_rects; rect < end; rect++)
 751         scale_dpi_rect( rect, dpi_from, dpi_to );
 752     scale_dpi_rect( &region->extents, dpi_from, dpi_to );
 753 }
 754
 755
 756 /* make a copy of a region; returns dst or NULL on error */
 757 struct region *copy_region( struct region *dst, const struct region *src )
 758 {
 759     if (dst == src) return dst;
 760
 761     if (dst->size < src->num_rects)
 762     {
 763         rectangle_t *rect = realloc( dst->rects, src->num_rects * sizeof(*rect) );
 764         if (!rect)
 765         {
 766             set_error( STATUS_NO_MEMORY );
 767             return NULL;
 768         }
 769         dst->rects = rect;
 770         dst->size = src->num_rects;
 771     }
 772     dst->num_rects = src->num_rects;
 773     dst->extents = src->extents;
 774     memcpy( dst->rects, src->rects, src->num_rects * sizeof(*dst->rects) );
 775     return dst;
 776 }
 777
 778 /* compute the intersection of two regions into dst, which can be one of the source regions */
 779 struct region *intersect_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     {
 784         dst->num_rects = 0;
 785         dst->extents.left = 0;
 786         dst->extents.top = 0;
 787         dst->extents.right = 0;
 788         dst->extents.bottom = 0;
 789         return dst;
 790     }
 791     if (!region_op( dst, src1, src2, intersect_overlapping, NULL, NULL )) return NULL;
 792     set_region_extents( dst );
 793     return dst;
 794 }
 795
 796 /* compute the subtraction of two regions into dst, which can be one of the source regions */
 797 struct region *subtract_region( struct region *dst, const struct region *src1,
 798                                 const struct region *src2 )
 799 {
 800     if (!src1->num_rects || !src2->num_rects || !EXTENTCHECK(&src1->extents, &src2->extents))
 801         return copy_region( dst, src1 );
 802
 803     if (!region_op( dst, src1, src2, subtract_overlapping,
 804                     subtract_non_overlapping, NULL )) return NULL;
 805     set_region_extents( dst );
 806     return dst;
 807 }
 808
 809 /* compute the union of two regions into dst, which can be one of the source regions */
 810 struct region *union_region( struct region *dst, const struct region *src1,
 811                              const struct region *src2 )
 812 {
 813     if (src1 == src2) return copy_region( dst, src1 );
 814     if (!src1->num_rects) return copy_region( dst, src2 );
 815     if (!src2->num_rects) return copy_region( dst, src1 );
 816
 817     if ((src1->num_rects == 1) &&
 818         (src1->extents.left <= src2->extents.left) &&
 819         (src1->extents.top <= src2->extents.top) &&
 820         (src1->extents.right >= src2->extents.right) &&
 821         (src1->extents.bottom >= src2->extents.bottom))
 822         return copy_region( dst, src1 );
 823
 824     if ((src2->num_rects == 1) &&
 825         (src2->extents.left <= src1->extents.left) &&
 826         (src2->extents.top <= src1->extents.top) &&
 827         (src2->extents.right >= src1->extents.right) &&
 828         (src2->extents.bottom >= src1->extents.bottom))
 829         return copy_region( dst, src2 );
 830
 831     if (!region_op( dst, src1, src2, union_overlapping,
 832                     union_non_overlapping, union_non_overlapping )) return NULL;
 833
 834     dst->extents.left = min(src1->extents.left, src2->extents.left);
 835     dst->extents.top = min(src1->extents.top, src2->extents.top);
 836     dst->extents.right = max(src1->extents.right, src2->extents.right);
 837     dst->extents.bottom = max(src1->extents.bottom, src2->extents.bottom);
 838     return dst;
 839 }
 840
 841 /* compute the exclusive or of two regions into dst, which can be one of the source regions */
 842 struct region *xor_region( struct region *dst, const struct region *src1,
 843                            const struct region *src2 )
 844 {
 845     struct region *tmp = create_empty_region();
 846
 847     if (!tmp) return NULL;
 848
 849     if (!subtract_region( tmp, src1, src2 ) ||
 850         !subtract_region( dst, src2, src1 ) ||
 851         !union_region( dst, dst, tmp ))
 852         dst = NULL;
 853
 854     free_region( tmp );
 855     return dst;
 856 }
 857
 858 /* check if the given point is inside the region */
 859 int point_in_region( struct region *region, int x, int y )
 860 {
 861     const rectangle_t *ptr, *end;
 862
 863     for (ptr = region->rects, end = region->rects + region->num_rects; ptr < end; ptr++)
 864     {
 865         if (ptr->top > y) return 0;
 866         if (ptr->bottom <= y) continue;
 867         /* now we are in the correct band */
 868         if (ptr->left > x) return 0;
 869         if (ptr->right <= x) continue;
 870         return 1;
 871     }
 872     return 0;
 873 }
 874
 875 /* check if the given rectangle is (at least partially) inside the region */
 876 int rect_in_region( struct region *region, const rectangle_t *rect )
 877 {
 878     const rectangle_t *ptr, *end;
 879
 880     for (ptr = region->rects, end = region->rects + region->num_rects; ptr < end; ptr++)
 881     {
 882         if (ptr->top >= rect->bottom) return 0;
 883         if (ptr->bottom <= rect->top) continue;
 884         if (ptr->left >= rect->right) continue;
 885         if (ptr->right <= rect->left) continue;
 886         return 1;
 887     }
 888     return 0;
 889 }