Make sure to build the def file after a make clean in a module
[wine] / 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 NULL;
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 an empty region */
561 struct region *create_empty_region(void)
562 {
563     struct region *region;
564
565     if (!(region = mem_alloc( sizeof(*region) ))) return NULL;
566     if (!(region->rects = mem_alloc( RGN_DEFAULT_RECTS * sizeof(*region->rects) )))
567     {
568         free( region );
569         return NULL;
570     }
571     region->size = RGN_DEFAULT_RECTS;
572     region->num_rects = 0;
573     region->extents.left = 0;
574     region->extents.top = 0;
575     region->extents.right = 0;
576     region->extents.bottom = 0;
577     return region;
578 }
579
580 /* create a region from request data */
581 struct region *create_region_from_req_data( const void *data, size_t size )
582 {
583     unsigned int alloc_rects;
584     struct region *region;
585     const rectangle_t *rects = data;
586     int nb_rects = size / sizeof(rectangle_t);
587
588     /* special case: empty region can be specified by a single all-zero rectangle */
589     if (nb_rects == 1 && !memcmp( rects, &empty_rect, sizeof(empty_rect) )) nb_rects = 0;
590
591     if (!validate_rectangles( rects, nb_rects ))
592     {
593         set_error( STATUS_INVALID_PARAMETER );
594         return NULL;
595     }
596
597     if (!(region = mem_alloc( sizeof(*region) ))) return NULL;
598
599     alloc_rects = max( nb_rects, RGN_DEFAULT_RECTS );
600     if (!(region->rects = mem_alloc( alloc_rects * sizeof(*region->rects) )))
601     {
602         free( region );
603         return NULL;
604     }
605     region->size = alloc_rects;
606     region->num_rects = nb_rects;
607     memcpy( region->rects, rects, nb_rects * sizeof(*rects) );
608     set_region_extents( region );
609     return region;
610 }
611
612 /* free a region */
613 void free_region( struct region *region )
614 {
615     free( region->rects );
616     free( region );
617 }
618
619 /* set region to a simple rectangle */
620 void set_region_rect( struct region *region, const rectangle_t *rect )
621 {
622     if (rect->left < rect->right && rect->top < rect->bottom)
623     {
624         region->num_rects = 1;
625         region->rects[0] = region->extents = *rect;
626     }
627     else
628     {
629         region->num_rects = 0;
630         region->extents.left = 0;
631         region->extents.top = 0;
632         region->extents.right = 0;
633         region->extents.bottom = 0;
634     }
635 }
636
637 /* retrieve the region data for sending to the client */
638 rectangle_t *get_region_data( const struct region *region, size_t max_size, size_t *total_size )
639 {
640     const rectangle_t *data = region->rects;
641
642     if (!(*total_size = region->num_rects * sizeof(rectangle_t)))
643     {
644         /* return a single empty rect for empty regions */
645         *total_size = sizeof(empty_rect);
646         data = &empty_rect;
647     }
648     if (max_size >= *total_size) return memdup( data, *total_size );
649     set_error( STATUS_BUFFER_OVERFLOW );
650     return NULL;
651 }
652
653 /* retrieve the region data for sending to the client and free the region at the same time */
654 rectangle_t *get_region_data_and_free( struct region *region, size_t max_size, size_t *total_size )
655 {
656     rectangle_t *ret = region->rects;
657
658     if (!(*total_size = region->num_rects * sizeof(rectangle_t)))
659     {
660         /* return a single empty rect for empty regions */
661         *total_size = sizeof(empty_rect);
662         if (max_size >= sizeof(empty_rect))
663         {
664             ret = memdup( &empty_rect, sizeof(empty_rect) );
665             free( region->rects );
666         }
667     }
668
669     if (max_size < *total_size)
670     {
671         free( region->rects );
672         set_error( STATUS_BUFFER_OVERFLOW );
673         ret = NULL;
674     }
675     free( region );
676     return ret;
677 }
678
679 /* check if a given region is empty */
680 int is_region_empty( const struct region *region )
681 {
682     return region->num_rects == 0;
683 }
684
685
686 /* get the extents rect of a region */
687 void get_region_extents( const struct region *region, rectangle_t *rect )
688 {
689     *rect = region->extents;
690 }
691
692 /* add an offset to a region */
693 void offset_region( struct region *region, int x, int y )
694 {
695     rectangle_t *rect, *end;
696
697     if (!region->num_rects) return;
698     for (rect = region->rects, end = rect + region->num_rects; rect < end; rect++)
699     {
700         rect->left += x;
701         rect->right += x;
702         rect->top += y;
703         rect->bottom += y;
704     }
705     region->extents.left += x;
706     region->extents.right += x;
707     region->extents.top += y;
708     region->extents.bottom += y;
709 }
710
711 /* make a copy of a region; returns dst or NULL on error */
712 struct region *copy_region( struct region *dst, const struct region *src )
713 {
714     if (dst == src) return dst;
715
716     if (dst->size < src->num_rects)
717     {
718         rectangle_t *rect = realloc( dst->rects, src->num_rects * sizeof(*rect) );
719         if (!rect)
720         {
721             set_error( STATUS_NO_MEMORY );
722             return NULL;
723         }
724         dst->rects = rect;
725         dst->size = src->num_rects;
726     }
727     dst->num_rects = src->num_rects;
728     dst->extents = src->extents;
729     memcpy( dst->rects, src->rects, src->num_rects * sizeof(*dst->rects) );
730     return dst;
731 }
732
733 /* compute the intersection of two regions into dst, which can be one of the source regions */
734 struct region *intersect_region( struct region *dst, const struct region *src1,
735                                  const struct region *src2 )
736 {
737     if (!src1->num_rects || !src2->num_rects || !EXTENTCHECK(&src1->extents, &src2->extents))
738     {
739         dst->num_rects = 0;
740         dst->extents.left = 0;
741         dst->extents.top = 0;
742         dst->extents.right = 0;
743         dst->extents.bottom = 0;
744         return dst;
745     }
746     if (!region_op( dst, src1, src2, intersect_overlapping, NULL, NULL )) return NULL;
747     set_region_extents( dst );
748     return dst;
749 }
750
751 /* compute the subtraction of two regions into dst, which can be one of the source regions */
752 struct region *subtract_region( struct region *dst, const struct region *src1,
753                                 const struct region *src2 )
754 {
755     if (!src1->num_rects || !src2->num_rects || !EXTENTCHECK(&src1->extents, &src2->extents))
756         return copy_region( dst, src1 );
757
758     if (!region_op( dst, src1, src2, subtract_overlapping,
759                     subtract_non_overlapping, NULL )) return NULL;
760     set_region_extents( dst );
761     return dst;
762 }
763
764 /* compute the union of two regions into dst, which can be one of the source regions */
765 struct region *union_region( struct region *dst, const struct region *src1,
766                              const struct region *src2 )
767 {
768     if (src1 == src2) return copy_region( dst, src1 );
769     if (!src1->num_rects) return copy_region( dst, src2 );
770     if (!src2->num_rects) return copy_region( dst, src1 );
771
772     if ((src1->num_rects == 1) &&
773         (src1->extents.left <= src2->extents.left) &&
774         (src1->extents.top <= src2->extents.top) &&
775         (src1->extents.right >= src2->extents.right) &&
776         (src1->extents.bottom >= src2->extents.bottom))
777         return copy_region( dst, src1 );
778
779     if ((src2->num_rects == 1) &&
780         (src2->extents.left <= src1->extents.left) &&
781         (src2->extents.top <= src1->extents.top) &&
782         (src2->extents.right >= src1->extents.right) &&
783         (src2->extents.bottom >= src1->extents.bottom))
784         return copy_region( dst, src2 );
785
786     if (!region_op( dst, src1, src2, union_overlapping,
787                     union_non_overlapping, union_non_overlapping )) return NULL;
788
789     dst->extents.left = min(src1->extents.left, src2->extents.left);
790     dst->extents.top = min(src1->extents.top, src2->extents.top);
791     dst->extents.right = max(src1->extents.right, src2->extents.right);
792     dst->extents.bottom = max(src1->extents.bottom, src2->extents.bottom);
793     return dst;
794 }
795
796 /* compute the exclusive or of two regions into dst, which can be one of the source regions */
797 struct region *xor_region( struct region *dst, const struct region *src1,
798                            const struct region *src2 )
799 {
800     struct region *tmp = create_empty_region();
801
802     if (!tmp) return NULL;
803
804     if (!subtract_region( tmp, src1, src2 ) ||
805         !subtract_region( dst, src2, src1 ) ||
806         !union_region( dst, dst, tmp ))
807         dst = NULL;
808
809     free_region( tmp );
810     return dst;
811 }
812
813 /* check if the given point is inside the region */
814 int point_in_region( struct region *region, int x, int y )
815 {
816     const rectangle_t *ptr, *end;
817
818     for (ptr = region->rects, end = region->rects + region->num_rects; ptr < end; ptr++)
819     {
820         if (ptr->top > y) return 0;
821         if (ptr->bottom <= y) continue;
822         /* now we are in the correct band */
823         if (ptr->left > x) return 0;
824         if (ptr->right <= x) continue;
825         return 1;
826     }
827     return 0;
828 }
829
830 /* check if the given rectangle is (at least partially) inside the region */
831 int rect_in_region( struct region *region, const rectangle_t *rect )
832 {
833     const rectangle_t *ptr, *end;
834
835     for (ptr = region->rects, end = region->rects + region->num_rects; ptr < end; ptr++)
836     {
837         if (ptr->top >= rect->bottom) return 0;
838         if (ptr->bottom <= rect->top) continue;
839         if (ptr->left >= rect->right) continue;
840         if (ptr->right <= rect->left) continue;
841         return 1;
842     }
843     return 0;
844 }