server: Convert the server start time to the abs_time_t type.
[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., 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 - 1)
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             left = r1->left;
473         }
474     }
475
476     while (r1 != r1End)
477     {
478         rectangle_t *rect = add_rect( pReg );
479         if (!rect) return 0;
480         rect->left = left;
481         rect->top = top;
482         rect->right = r1->right;
483         rect->bottom = bottom;
484         r1++;
485         if (r1 != r1End) left = r1->left;
486     }
487     return 1;
488 }
489
490 /* handle a non-overlapping band for union_region */
491 static int union_non_overlapping( struct region *pReg, const rectangle_t *r,
492                                   const rectangle_t *rEnd, int top, int bottom )
493 {
494     while (r != rEnd)
495     {
496         rectangle_t *rect = add_rect( pReg );
497         if (!rect) return 0;
498         rect->left = r->left;
499         rect->top = top;
500         rect->right = r->right;
501         rect->bottom = bottom;
502         r++;
503     }
504     return 1;
505 }
506
507 /* handle an overlapping band for union_region */
508 static int union_overlapping( struct region *pReg,
509                               const rectangle_t *r1, const rectangle_t *r1End,
510                               const rectangle_t *r2, const rectangle_t *r2End,
511                               int top, int bottom )
512 {
513 #define MERGERECT(r) \
514     if ((pReg->num_rects != 0) &&  \
515         (pReg->rects[pReg->num_rects-1].top == top) &&  \
516         (pReg->rects[pReg->num_rects-1].bottom == bottom) &&  \
517         (pReg->rects[pReg->num_rects-1].right >= r->left))  \
518     {  \
519         if (pReg->rects[pReg->num_rects-1].right < r->right)  \
520         {  \
521             pReg->rects[pReg->num_rects-1].right = r->right;  \
522         }  \
523     }  \
524     else  \
525     {  \
526         rectangle_t *rect = add_rect( pReg ); \
527         if (!rect) return 0; \
528         rect->top = top;  \
529         rect->bottom = bottom;  \
530         rect->left = r->left;  \
531         rect->right = r->right;  \
532     }  \
533     r++;
534
535     while ((r1 != r1End) && (r2 != r2End))
536     {
537         if (r1->left < r2->left)
538         {
539             MERGERECT(r1);
540         }
541         else
542         {
543             MERGERECT(r2);
544         }
545     }
546
547     if (r1 != r1End)
548     {
549         do
550         {
551             MERGERECT(r1);
552         } while (r1 != r1End);
553     }
554     else while (r2 != r2End)
555     {
556         MERGERECT(r2);
557     }
558     return 1;
559 #undef MERGERECT
560 }
561
562
563 /* create an empty region */
564 struct region *create_empty_region(void)
565 {
566     struct region *region;
567
568     if (!(region = mem_alloc( sizeof(*region) ))) return NULL;
569     if (!(region->rects = mem_alloc( RGN_DEFAULT_RECTS * sizeof(*region->rects) )))
570     {
571         free( region );
572         return NULL;
573     }
574     region->size = RGN_DEFAULT_RECTS;
575     region->num_rects = 0;
576     region->extents.left = 0;
577     region->extents.top = 0;
578     region->extents.right = 0;
579     region->extents.bottom = 0;
580     return region;
581 }
582
583 /* create a region from request data */
584 struct region *create_region_from_req_data( const void *data, data_size_t size )
585 {
586     unsigned int alloc_rects;
587     struct region *region;
588     const rectangle_t *rects = data;
589     int nb_rects = size / sizeof(rectangle_t);
590
591     /* special case: empty region can be specified by a single all-zero rectangle */
592     if (nb_rects == 1 && !memcmp( rects, &empty_rect, sizeof(empty_rect) )) nb_rects = 0;
593
594     if (!validate_rectangles( rects, nb_rects ))
595     {
596         set_error( STATUS_INVALID_PARAMETER );
597         return NULL;
598     }
599
600     if (!(region = mem_alloc( sizeof(*region) ))) return NULL;
601
602     alloc_rects = max( nb_rects, RGN_DEFAULT_RECTS );
603     if (!(region->rects = mem_alloc( alloc_rects * sizeof(*region->rects) )))
604     {
605         free( region );
606         return NULL;
607     }
608     region->size = alloc_rects;
609     region->num_rects = nb_rects;
610     memcpy( region->rects, rects, nb_rects * sizeof(*rects) );
611     set_region_extents( region );
612     return region;
613 }
614
615 /* free a region */
616 void free_region( struct region *region )
617 {
618     free( region->rects );
619     free( region );
620 }
621
622 /* set region to a simple rectangle */
623 void set_region_rect( struct region *region, const rectangle_t *rect )
624 {
625     if (rect->left < rect->right && rect->top < rect->bottom)
626     {
627         region->num_rects = 1;
628         region->rects[0] = region->extents = *rect;
629     }
630     else
631     {
632         region->num_rects = 0;
633         region->extents.left = 0;
634         region->extents.top = 0;
635         region->extents.right = 0;
636         region->extents.bottom = 0;
637     }
638 }
639
640 /* retrieve the region data for sending to the client */
641 rectangle_t *get_region_data( const struct region *region, data_size_t max_size, data_size_t *total_size )
642 {
643     const rectangle_t *data = region->rects;
644
645     if (!(*total_size = region->num_rects * sizeof(rectangle_t)))
646     {
647         /* return a single empty rect for empty regions */
648         *total_size = sizeof(empty_rect);
649         data = &empty_rect;
650     }
651     if (max_size >= *total_size) return memdup( data, *total_size );
652     set_error( STATUS_BUFFER_OVERFLOW );
653     return NULL;
654 }
655
656 /* retrieve the region data for sending to the client and free the region at the same time */
657 rectangle_t *get_region_data_and_free( struct region *region, data_size_t max_size, data_size_t *total_size )
658 {
659     rectangle_t *ret = region->rects;
660
661     if (!(*total_size = region->num_rects * sizeof(rectangle_t)))
662     {
663         /* return a single empty rect for empty regions */
664         *total_size = sizeof(empty_rect);
665         if (max_size >= sizeof(empty_rect))
666         {
667             ret = memdup( &empty_rect, sizeof(empty_rect) );
668             free( region->rects );
669         }
670     }
671
672     if (max_size < *total_size)
673     {
674         free( region->rects );
675         set_error( STATUS_BUFFER_OVERFLOW );
676         ret = NULL;
677     }
678     free( region );
679     return ret;
680 }
681
682 /* check if a given region is empty */
683 int is_region_empty( const struct region *region )
684 {
685     return region->num_rects == 0;
686 }
687
688
689 /* get the extents rect of a region */
690 void get_region_extents( const struct region *region, rectangle_t *rect )
691 {
692     *rect = region->extents;
693 }
694
695 /* add an offset to a region */
696 void offset_region( struct region *region, int x, int y )
697 {
698     rectangle_t *rect, *end;
699
700     if (!region->num_rects) return;
701     for (rect = region->rects, end = rect + region->num_rects; rect < end; rect++)
702     {
703         rect->left += x;
704         rect->right += x;
705         rect->top += y;
706         rect->bottom += y;
707     }
708     region->extents.left += x;
709     region->extents.right += x;
710     region->extents.top += y;
711     region->extents.bottom += y;
712 }
713
714 /* make a copy of a region; returns dst or NULL on error */
715 struct region *copy_region( struct region *dst, const struct region *src )
716 {
717     if (dst == src) return dst;
718
719     if (dst->size < src->num_rects)
720     {
721         rectangle_t *rect = realloc( dst->rects, src->num_rects * sizeof(*rect) );
722         if (!rect)
723         {
724             set_error( STATUS_NO_MEMORY );
725             return NULL;
726         }
727         dst->rects = rect;
728         dst->size = src->num_rects;
729     }
730     dst->num_rects = src->num_rects;
731     dst->extents = src->extents;
732     memcpy( dst->rects, src->rects, src->num_rects * sizeof(*dst->rects) );
733     return dst;
734 }
735
736 /* compute the intersection of two regions into dst, which can be one of the source regions */
737 struct region *intersect_region( struct region *dst, const struct region *src1,
738                                  const struct region *src2 )
739 {
740     if (!src1->num_rects || !src2->num_rects || !EXTENTCHECK(&src1->extents, &src2->extents))
741     {
742         dst->num_rects = 0;
743         dst->extents.left = 0;
744         dst->extents.top = 0;
745         dst->extents.right = 0;
746         dst->extents.bottom = 0;
747         return dst;
748     }
749     if (!region_op( dst, src1, src2, intersect_overlapping, NULL, NULL )) return NULL;
750     set_region_extents( dst );
751     return dst;
752 }
753
754 /* compute the subtraction of two regions into dst, which can be one of the source regions */
755 struct region *subtract_region( struct region *dst, const struct region *src1,
756                                 const struct region *src2 )
757 {
758     if (!src1->num_rects || !src2->num_rects || !EXTENTCHECK(&src1->extents, &src2->extents))
759         return copy_region( dst, src1 );
760
761     if (!region_op( dst, src1, src2, subtract_overlapping,
762                     subtract_non_overlapping, NULL )) return NULL;
763     set_region_extents( dst );
764     return dst;
765 }
766
767 /* compute the union of two regions into dst, which can be one of the source regions */
768 struct region *union_region( struct region *dst, const struct region *src1,
769                              const struct region *src2 )
770 {
771     if (src1 == src2) return copy_region( dst, src1 );
772     if (!src1->num_rects) return copy_region( dst, src2 );
773     if (!src2->num_rects) return copy_region( dst, src1 );
774
775     if ((src1->num_rects == 1) &&
776         (src1->extents.left <= src2->extents.left) &&
777         (src1->extents.top <= src2->extents.top) &&
778         (src1->extents.right >= src2->extents.right) &&
779         (src1->extents.bottom >= src2->extents.bottom))
780         return copy_region( dst, src1 );
781
782     if ((src2->num_rects == 1) &&
783         (src2->extents.left <= src1->extents.left) &&
784         (src2->extents.top <= src1->extents.top) &&
785         (src2->extents.right >= src1->extents.right) &&
786         (src2->extents.bottom >= src1->extents.bottom))
787         return copy_region( dst, src2 );
788
789     if (!region_op( dst, src1, src2, union_overlapping,
790                     union_non_overlapping, union_non_overlapping )) return NULL;
791
792     dst->extents.left = min(src1->extents.left, src2->extents.left);
793     dst->extents.top = min(src1->extents.top, src2->extents.top);
794     dst->extents.right = max(src1->extents.right, src2->extents.right);
795     dst->extents.bottom = max(src1->extents.bottom, src2->extents.bottom);
796     return dst;
797 }
798
799 /* compute the exclusive or of two regions into dst, which can be one of the source regions */
800 struct region *xor_region( struct region *dst, const struct region *src1,
801                            const struct region *src2 )
802 {
803     struct region *tmp = create_empty_region();
804
805     if (!tmp) return NULL;
806
807     if (!subtract_region( tmp, src1, src2 ) ||
808         !subtract_region( dst, src2, src1 ) ||
809         !union_region( dst, dst, tmp ))
810         dst = NULL;
811
812     free_region( tmp );
813     return dst;
814 }
815
816 /* check if the given point is inside the region */
817 int point_in_region( struct region *region, int x, int y )
818 {
819     const rectangle_t *ptr, *end;
820
821     for (ptr = region->rects, end = region->rects + region->num_rects; ptr < end; ptr++)
822     {
823         if (ptr->top > y) return 0;
824         if (ptr->bottom <= y) continue;
825         /* now we are in the correct band */
826         if (ptr->left > x) return 0;
827         if (ptr->right <= x) continue;
828         return 1;
829     }
830     return 0;
831 }
832
833 /* check if the given rectangle is (at least partially) inside the region */
834 int rect_in_region( struct region *region, const rectangle_t *rect )
835 {
836     const rectangle_t *ptr, *end;
837
838     for (ptr = region->rects, end = region->rects + region->num_rects; ptr < end; ptr++)
839     {
840         if (ptr->top >= rect->bottom) return 0;
841         if (ptr->bottom <= rect->top) continue;
842         if (ptr->left >= rect->right) continue;
843         if (ptr->right <= rect->left) continue;
844         return 1;
845     }
846     return 0;
847 }