po: Mark an incorrect Czech translation as fuzzy.
[wine/multimedia.git] / server / region.c
blob8b85c3458c4492dda4b56b2e93135265c8f3faef
1 /*
2 * Server-side region objects. Based on the X11 implementation.
4 * Copyright 1993, 1994, 1995, 2004 Alexandre Julliard
5 * Modifications and additions: Copyright 1998 Huw Davies
6 * 1999 Alex Korobka
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.
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.
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
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.
27 /************************************************************************
29 Copyright (c) 1987, 1988 X Consortium
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:
38 The above copyright notice and this permission notice shall be included in
39 all copies or substantial portions of the Software.
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.
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.
53 Copyright 1987, 1988 by Digital Equipment Corporation, Maynard, Massachusetts.
55 All Rights Reserved
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.
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.
73 ************************************************************************/
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"
84 struct region
86 int size;
87 int num_rects;
88 rectangle_t *rects;
89 rectangle_t extents;
93 #define RGN_DEFAULT_RECTS 2
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)
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 );
106 static const rectangle_t empty_rect; /* all-zero rectangle for empty regions */
108 /* add a rectangle to a region */
109 static inline rectangle_t *add_rect( struct region *reg )
111 if (reg->num_rects >= reg->size - 1)
113 rectangle_t *new_rect = realloc( reg->rects, 2 * sizeof(rectangle_t) * reg->size );
114 if (!new_rect)
116 set_error( STATUS_NO_MEMORY );
117 return NULL;
119 reg->rects = new_rect;
120 reg->size *= 2;
122 return reg->rects + reg->num_rects++;
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 )
128 const rectangle_t *ptr, *end;
130 for (ptr = rects, end = rects + nb_rects; ptr < end; ptr++)
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 */
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 */
139 else /* new band */
141 if (ptr[0].bottom > ptr[1].top) return 0; /* not properly y ordered */
144 return 1;
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 )
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;
158 for (curNumRects = 0;
159 (pCurRect != pRegEnd) && (pCurRect->top == bandtop);
160 curNumRects++)
162 pCurRect++;
165 if (pCurRect != pRegEnd)
167 pRegEnd--;
168 while (pRegEnd[-1].top == pRegEnd->top) pRegEnd--;
169 curStart = pRegEnd - pReg->rects;
170 pRegEnd = pReg->rects + pReg->num_rects;
173 if ((curNumRects == prevNumRects) && (curNumRects != 0))
175 pCurRect -= curNumRects;
176 if (pPrevRect->bottom == pCurRect->top)
180 if ((pPrevRect->left != pCurRect->left) ||
181 (pPrevRect->right != pCurRect->right)) return curStart;
182 pPrevRect++;
183 pCurRect++;
184 prevNumRects -= 1;
185 } while (prevNumRects != 0);
187 pReg->num_rects -= curNumRects;
188 pCurRect -= curNumRects;
189 pPrevRect -= curNumRects;
193 pPrevRect->bottom = pCurRect->bottom;
194 pPrevRect++;
195 pCurRect++;
196 curNumRects -= 1;
197 } while (curNumRects != 0);
199 if (pCurRect == pRegEnd) curStart = prevStart;
200 else do { *pPrevRect++ = *pCurRect++; } while (pCurRect != pRegEnd);
204 return curStart;
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 )
214 int ybot, ytop, top, bot, prevBand, curBand;
215 const rectangle_t *r1BandEnd, *r2BandEnd;
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;
222 rectangle_t *new_rects, *old_rects = newReg->rects;
223 int new_size, ret = 0;
225 new_size = max( reg1->num_rects, reg2->num_rects ) * 2;
226 if (!(new_rects = mem_alloc( new_size * sizeof(*newReg->rects) ))) return 0;
228 newReg->size = new_size;
229 newReg->rects = new_rects;
230 newReg->num_rects = 0;
232 if (reg1->extents.top < reg2->extents.top)
233 ybot = reg1->extents.top;
234 else
235 ybot = reg2->extents.top;
237 prevBand = 0;
241 curBand = newReg->num_rects;
243 r1BandEnd = r1;
244 while ((r1BandEnd != r1End) && (r1BandEnd->top == r1->top)) r1BandEnd++;
246 r2BandEnd = r2;
247 while ((r2BandEnd != r2End) && (r2BandEnd->top == r2->top)) r2BandEnd++;
249 if (r1->top < r2->top)
251 top = max(r1->top,ybot);
252 bot = min(r1->bottom,r2->top);
254 if ((top != bot) && non_overlap1_func)
256 if (!non_overlap1_func( newReg, r1, r1BandEnd, top, bot )) goto done;
259 ytop = r2->top;
261 else if (r2->top < r1->top)
263 top = max(r2->top,ybot);
264 bot = min(r2->bottom,r1->top);
266 if ((top != bot) && non_overlap2_func)
268 if (!non_overlap2_func( newReg, r2, r2BandEnd, top, bot )) goto done;
271 ytop = r1->top;
273 else
275 ytop = r1->top;
278 if (newReg->num_rects != curBand)
279 prevBand = coalesce_region(newReg, prevBand, curBand);
281 ybot = min(r1->bottom, r2->bottom);
282 curBand = newReg->num_rects;
283 if (ybot > ytop)
285 if (!overlap_func( newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot )) goto done;
288 if (newReg->num_rects != curBand)
289 prevBand = coalesce_region(newReg, prevBand, curBand);
291 if (r1->bottom == ybot) r1 = r1BandEnd;
292 if (r2->bottom == ybot) r2 = r2BandEnd;
293 } while ((r1 != r1End) && (r2 != r2End));
295 curBand = newReg->num_rects;
296 if (r1 != r1End)
298 if (non_overlap1_func)
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);
310 else if ((r2 != r2End) && non_overlap2_func)
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);
322 if (newReg->num_rects != curBand) coalesce_region(newReg, prevBand, curBand);
324 if ((newReg->num_rects < (newReg->size / 2)) && (newReg->size > 2))
326 new_size = max( newReg->num_rects, RGN_DEFAULT_RECTS );
327 if ((new_rects = realloc( newReg->rects, sizeof(*newReg->rects) * new_size )))
329 newReg->rects = new_rects;
330 newReg->size = new_size;
333 ret = 1;
334 done:
335 free( old_rects );
336 return ret;
339 /* recalculate the extents of a region */
340 static void set_region_extents( struct region *region )
342 rectangle_t *pRect, *pRectEnd;
344 if (region->num_rects == 0)
346 region->extents.left = 0;
347 region->extents.top = 0;
348 region->extents.right = 0;
349 region->extents.bottom = 0;
350 return;
353 pRect = region->rects;
354 pRectEnd = &pRect[region->num_rects - 1];
356 region->extents.left = pRect->left;
357 region->extents.top = pRect->top;
358 region->extents.right = pRectEnd->right;
359 region->extents.bottom = pRectEnd->bottom;
361 while (pRect <= pRectEnd)
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++;
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 )
376 int left, right;
378 while ((r1 != r1End) && (r2 != r2End))
380 left = max(r1->left, r2->left);
381 right = min(r1->right, r2->right);
383 if (left < right)
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;
393 if (r1->right < r2->right) r1++;
394 else if (r2->right < r1->right) r2++;
395 else
397 r1++;
398 r2++;
401 return 1;
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 )
408 while (r != rEnd)
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++;
418 return 1;
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 )
427 int left = r1->left;
429 while ((r1 != r1End) && (r2 != r2End))
431 if (r2->right <= left) r2++;
432 else if (r2->left <= left)
434 left = r2->right;
435 if (left >= r1->right)
437 r1++;
438 if (r1 != r1End)
439 left = r1->left;
441 else r2++;
443 else if (r2->left < r1->right)
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)
454 r1++;
455 if (r1 != r1End)
456 left = r1->left;
458 else r2++;
460 else
462 if (r1->right > left)
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;
471 r1++;
472 left = r1->left;
476 while (r1 != r1End)
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;
487 return 1;
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 )
494 while (r != rEnd)
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++;
504 return 1;
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 )
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)) \
519 if (pReg->rects[pReg->num_rects-1].right < r->right) \
521 pReg->rects[pReg->num_rects-1].right = r->right; \
524 else \
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; \
533 r++;
535 while ((r1 != r1End) && (r2 != r2End))
537 if (r1->left < r2->left)
539 MERGERECT(r1);
541 else
543 MERGERECT(r2);
547 if (r1 != r1End)
551 MERGERECT(r1);
552 } while (r1 != r1End);
554 else while (r2 != r2End)
556 MERGERECT(r2);
558 return 1;
559 #undef MERGERECT
563 /* create an empty region */
564 struct region *create_empty_region(void)
566 struct region *region;
568 if (!(region = mem_alloc( sizeof(*region) ))) return NULL;
569 if (!(region->rects = mem_alloc( RGN_DEFAULT_RECTS * sizeof(*region->rects) )))
571 free( region );
572 return NULL;
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;
583 /* create a region from request data */
584 struct region *create_region_from_req_data( const void *data, data_size_t size )
586 unsigned int alloc_rects;
587 struct region *region;
588 const rectangle_t *rects = data;
589 int nb_rects = size / sizeof(rectangle_t);
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;
594 if (!validate_rectangles( rects, nb_rects ))
596 set_error( STATUS_INVALID_PARAMETER );
597 return NULL;
600 if (!(region = mem_alloc( sizeof(*region) ))) return NULL;
602 alloc_rects = max( nb_rects, RGN_DEFAULT_RECTS );
603 if (!(region->rects = mem_alloc( alloc_rects * sizeof(*region->rects) )))
605 free( region );
606 return NULL;
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;
615 /* free a region */
616 void free_region( struct region *region )
618 free( region->rects );
619 free( region );
622 /* set region to a simple rectangle */
623 void set_region_rect( struct region *region, const rectangle_t *rect )
625 if (rect->left < rect->right && rect->top < rect->bottom)
627 region->num_rects = 1;
628 region->rects[0] = region->extents = *rect;
630 else
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;
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 )
643 const rectangle_t *data = region->rects;
645 if (!(*total_size = region->num_rects * sizeof(rectangle_t)))
647 /* return a single empty rect for empty regions */
648 *total_size = sizeof(empty_rect);
649 data = &empty_rect;
651 if (max_size >= *total_size) return memdup( data, *total_size );
652 set_error( STATUS_BUFFER_OVERFLOW );
653 return NULL;
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 )
659 rectangle_t *ret = region->rects;
661 if (!(*total_size = region->num_rects * sizeof(rectangle_t)))
663 /* return a single empty rect for empty regions */
664 *total_size = sizeof(empty_rect);
665 if (max_size >= sizeof(empty_rect))
667 ret = memdup( &empty_rect, sizeof(empty_rect) );
668 free( region->rects );
672 if (max_size < *total_size)
674 free( region->rects );
675 set_error( STATUS_BUFFER_OVERFLOW );
676 ret = NULL;
678 free( region );
679 return ret;
682 /* check if a given region is empty */
683 int is_region_empty( const struct region *region )
685 return region->num_rects == 0;
689 /* get the extents rect of a region */
690 void get_region_extents( const struct region *region, rectangle_t *rect )
692 *rect = region->extents;
695 /* add an offset to a region */
696 void offset_region( struct region *region, int x, int y )
698 rectangle_t *rect, *end;
700 if (!region->num_rects) return;
701 for (rect = region->rects, end = rect + region->num_rects; rect < end; rect++)
703 rect->left += x;
704 rect->right += x;
705 rect->top += y;
706 rect->bottom += y;
708 region->extents.left += x;
709 region->extents.right += x;
710 region->extents.top += y;
711 region->extents.bottom += y;
714 /* mirror a region relative to a window client rect */
715 void mirror_region( const rectangle_t *client_rect, struct region *region )
717 int start, end, i, j;
719 for (start = 0; start < region->num_rects; start = end + 1)
721 for (end = start; end < region->num_rects - 1; end++)
722 if (region->rects[end + 1].top != region->rects[end].top) break;
723 for (i = start, j = end; i < j; i++, j--)
725 rectangle_t rect = region->rects[j];
726 region->rects[i] = region->rects[j];
727 region->rects[j] = rect;
728 mirror_rect( client_rect, &region->rects[j] );
729 mirror_rect( client_rect, &region->rects[i] );
731 if (i == j) mirror_rect( client_rect, &region->rects[i] );
733 mirror_rect( client_rect, &region->extents );
737 /* make a copy of a region; returns dst or NULL on error */
738 struct region *copy_region( struct region *dst, const struct region *src )
740 if (dst == src) return dst;
742 if (dst->size < src->num_rects)
744 rectangle_t *rect = realloc( dst->rects, src->num_rects * sizeof(*rect) );
745 if (!rect)
747 set_error( STATUS_NO_MEMORY );
748 return NULL;
750 dst->rects = rect;
751 dst->size = src->num_rects;
753 dst->num_rects = src->num_rects;
754 dst->extents = src->extents;
755 memcpy( dst->rects, src->rects, src->num_rects * sizeof(*dst->rects) );
756 return dst;
759 /* compute the intersection of two regions into dst, which can be one of the source regions */
760 struct region *intersect_region( struct region *dst, const struct region *src1,
761 const struct region *src2 )
763 if (!src1->num_rects || !src2->num_rects || !EXTENTCHECK(&src1->extents, &src2->extents))
765 dst->num_rects = 0;
766 dst->extents.left = 0;
767 dst->extents.top = 0;
768 dst->extents.right = 0;
769 dst->extents.bottom = 0;
770 return dst;
772 if (!region_op( dst, src1, src2, intersect_overlapping, NULL, NULL )) return NULL;
773 set_region_extents( dst );
774 return dst;
777 /* compute the subtraction of two regions into dst, which can be one of the source regions */
778 struct region *subtract_region( struct region *dst, const struct region *src1,
779 const struct region *src2 )
781 if (!src1->num_rects || !src2->num_rects || !EXTENTCHECK(&src1->extents, &src2->extents))
782 return copy_region( dst, src1 );
784 if (!region_op( dst, src1, src2, subtract_overlapping,
785 subtract_non_overlapping, NULL )) return NULL;
786 set_region_extents( dst );
787 return dst;
790 /* compute the union of two regions into dst, which can be one of the source regions */
791 struct region *union_region( struct region *dst, const struct region *src1,
792 const struct region *src2 )
794 if (src1 == src2) return copy_region( dst, src1 );
795 if (!src1->num_rects) return copy_region( dst, src2 );
796 if (!src2->num_rects) return copy_region( dst, src1 );
798 if ((src1->num_rects == 1) &&
799 (src1->extents.left <= src2->extents.left) &&
800 (src1->extents.top <= src2->extents.top) &&
801 (src1->extents.right >= src2->extents.right) &&
802 (src1->extents.bottom >= src2->extents.bottom))
803 return copy_region( dst, src1 );
805 if ((src2->num_rects == 1) &&
806 (src2->extents.left <= src1->extents.left) &&
807 (src2->extents.top <= src1->extents.top) &&
808 (src2->extents.right >= src1->extents.right) &&
809 (src2->extents.bottom >= src1->extents.bottom))
810 return copy_region( dst, src2 );
812 if (!region_op( dst, src1, src2, union_overlapping,
813 union_non_overlapping, union_non_overlapping )) return NULL;
815 dst->extents.left = min(src1->extents.left, src2->extents.left);
816 dst->extents.top = min(src1->extents.top, src2->extents.top);
817 dst->extents.right = max(src1->extents.right, src2->extents.right);
818 dst->extents.bottom = max(src1->extents.bottom, src2->extents.bottom);
819 return dst;
822 /* compute the exclusive or of two regions into dst, which can be one of the source regions */
823 struct region *xor_region( struct region *dst, const struct region *src1,
824 const struct region *src2 )
826 struct region *tmp = create_empty_region();
828 if (!tmp) return NULL;
830 if (!subtract_region( tmp, src1, src2 ) ||
831 !subtract_region( dst, src2, src1 ) ||
832 !union_region( dst, dst, tmp ))
833 dst = NULL;
835 free_region( tmp );
836 return dst;
839 /* check if the given point is inside the region */
840 int point_in_region( struct region *region, int x, int y )
842 const rectangle_t *ptr, *end;
844 for (ptr = region->rects, end = region->rects + region->num_rects; ptr < end; ptr++)
846 if (ptr->top > y) return 0;
847 if (ptr->bottom <= y) continue;
848 /* now we are in the correct band */
849 if (ptr->left > x) return 0;
850 if (ptr->right <= x) continue;
851 return 1;
853 return 0;
856 /* check if the given rectangle is (at least partially) inside the region */
857 int rect_in_region( struct region *region, const rectangle_t *rect )
859 const rectangle_t *ptr, *end;
861 for (ptr = region->rects, end = region->rects + region->num_rects; ptr < end; ptr++)
863 if (ptr->top >= rect->bottom) return 0;
864 if (ptr->bottom <= rect->top) continue;
865 if (ptr->left >= rect->right) continue;
866 if (ptr->right <= rect->left) continue;
867 return 1;
869 return 0;