po: Update Lithuanian translation.
[wine.git] / server / region.c
blob33e2a54fab947679646732033011b14189987760
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)
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 if (r1 != r1End)
473 left = r1->left;
477 while (r1 != r1End)
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;
488 return 1;
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 )
495 while (r != rEnd)
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++;
505 return 1;
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 )
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)) \
520 if (pReg->rects[pReg->num_rects-1].right < r->right) \
522 pReg->rects[pReg->num_rects-1].right = r->right; \
525 else \
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; \
534 r++;
536 while ((r1 != r1End) && (r2 != r2End))
538 if (r1->left < r2->left)
540 MERGERECT(r1);
542 else
544 MERGERECT(r2);
548 if (r1 != r1End)
552 MERGERECT(r1);
553 } while (r1 != r1End);
555 else while (r2 != r2End)
557 MERGERECT(r2);
559 return 1;
560 #undef MERGERECT
564 /* create an empty region */
565 struct region *create_empty_region(void)
567 struct region *region;
569 if (!(region = mem_alloc( sizeof(*region) ))) return NULL;
570 if (!(region->rects = mem_alloc( RGN_DEFAULT_RECTS * sizeof(*region->rects) )))
572 free( region );
573 return NULL;
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;
584 /* create a region from request data */
585 struct region *create_region_from_req_data( const void *data, data_size_t size )
587 unsigned int alloc_rects;
588 struct region *region;
589 const rectangle_t *rects = data;
590 int nb_rects = size / sizeof(rectangle_t);
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;
595 if (!validate_rectangles( rects, nb_rects ))
597 set_error( STATUS_INVALID_PARAMETER );
598 return NULL;
601 if (!(region = mem_alloc( sizeof(*region) ))) return NULL;
603 alloc_rects = max( nb_rects, RGN_DEFAULT_RECTS );
604 if (!(region->rects = mem_alloc( alloc_rects * sizeof(*region->rects) )))
606 free( region );
607 return NULL;
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;
616 /* free a region */
617 void free_region( struct region *region )
619 free( region->rects );
620 free( region );
623 /* set region to a simple rectangle */
624 void set_region_rect( struct region *region, const rectangle_t *rect )
626 if (rect->left < rect->right && rect->top < rect->bottom)
628 region->num_rects = 1;
629 region->rects[0] = region->extents = *rect;
631 else
633 region->num_rects = 0;
634 region->extents.left = 0;
635 region->extents.top = 0;
636 region->extents.right = 0;
637 region->extents.bottom = 0;
641 /* retrieve the region data for sending to the client */
642 rectangle_t *get_region_data( const struct region *region, data_size_t max_size, data_size_t *total_size )
644 const rectangle_t *data = region->rects;
646 if (!(*total_size = region->num_rects * sizeof(rectangle_t)))
648 /* return a single empty rect for empty regions */
649 *total_size = sizeof(empty_rect);
650 data = &empty_rect;
652 if (max_size >= *total_size) return memdup( data, *total_size );
653 set_error( STATUS_BUFFER_OVERFLOW );
654 return NULL;
657 /* retrieve the region data for sending to the client and free the region at the same time */
658 rectangle_t *get_region_data_and_free( struct region *region, data_size_t max_size, data_size_t *total_size )
660 rectangle_t *ret = region->rects;
662 if (!(*total_size = region->num_rects * sizeof(rectangle_t)))
664 /* return a single empty rect for empty regions */
665 *total_size = sizeof(empty_rect);
666 if (max_size >= sizeof(empty_rect))
668 ret = memdup( &empty_rect, sizeof(empty_rect) );
669 free( region->rects );
673 if (max_size < *total_size)
675 free( region->rects );
676 set_error( STATUS_BUFFER_OVERFLOW );
677 ret = NULL;
679 free( region );
680 return ret;
683 /* check if a given region is empty */
684 int is_region_empty( const struct region *region )
686 return region->num_rects == 0;
690 /* get the extents rect of a region */
691 void get_region_extents( const struct region *region, rectangle_t *rect )
693 *rect = region->extents;
696 /* add an offset to a region */
697 void offset_region( struct region *region, int x, int y )
699 rectangle_t *rect, *end;
701 if (!region->num_rects) return;
702 for (rect = region->rects, end = rect + region->num_rects; rect < end; rect++)
704 rect->left += x;
705 rect->right += x;
706 rect->top += y;
707 rect->bottom += y;
709 region->extents.left += x;
710 region->extents.right += x;
711 region->extents.top += y;
712 region->extents.bottom += y;
715 /* mirror a region relative to a window client rect */
716 void mirror_region( const rectangle_t *client_rect, struct region *region )
718 int start, end, i, j;
720 for (start = 0; start < region->num_rects; start = end + 1)
722 for (end = start; end < region->num_rects - 1; end++)
723 if (region->rects[end + 1].top != region->rects[end].top) break;
724 for (i = start, j = end; i < j; i++, j--)
726 rectangle_t rect = region->rects[j];
727 region->rects[i] = region->rects[j];
728 region->rects[j] = rect;
729 mirror_rect( client_rect, &region->rects[j] );
730 mirror_rect( client_rect, &region->rects[i] );
732 if (i == j) mirror_rect( client_rect, &region->rects[i] );
734 mirror_rect( client_rect, &region->extents );
738 /* make a copy of a region; returns dst or NULL on error */
739 struct region *copy_region( struct region *dst, const struct region *src )
741 if (dst == src) return dst;
743 if (dst->size < src->num_rects)
745 rectangle_t *rect = realloc( dst->rects, src->num_rects * sizeof(*rect) );
746 if (!rect)
748 set_error( STATUS_NO_MEMORY );
749 return NULL;
751 dst->rects = rect;
752 dst->size = src->num_rects;
754 dst->num_rects = src->num_rects;
755 dst->extents = src->extents;
756 memcpy( dst->rects, src->rects, src->num_rects * sizeof(*dst->rects) );
757 return dst;
760 /* compute the intersection of two regions into dst, which can be one of the source regions */
761 struct region *intersect_region( struct region *dst, const struct region *src1,
762 const struct region *src2 )
764 if (!src1->num_rects || !src2->num_rects || !EXTENTCHECK(&src1->extents, &src2->extents))
766 dst->num_rects = 0;
767 dst->extents.left = 0;
768 dst->extents.top = 0;
769 dst->extents.right = 0;
770 dst->extents.bottom = 0;
771 return dst;
773 if (!region_op( dst, src1, src2, intersect_overlapping, NULL, NULL )) return NULL;
774 set_region_extents( dst );
775 return dst;
778 /* compute the subtraction of two regions into dst, which can be one of the source regions */
779 struct region *subtract_region( struct region *dst, const struct region *src1,
780 const struct region *src2 )
782 if (!src1->num_rects || !src2->num_rects || !EXTENTCHECK(&src1->extents, &src2->extents))
783 return copy_region( dst, src1 );
785 if (!region_op( dst, src1, src2, subtract_overlapping,
786 subtract_non_overlapping, NULL )) return NULL;
787 set_region_extents( dst );
788 return dst;
791 /* compute the union of two regions into dst, which can be one of the source regions */
792 struct region *union_region( struct region *dst, const struct region *src1,
793 const struct region *src2 )
795 if (src1 == src2) return copy_region( dst, src1 );
796 if (!src1->num_rects) return copy_region( dst, src2 );
797 if (!src2->num_rects) return copy_region( dst, src1 );
799 if ((src1->num_rects == 1) &&
800 (src1->extents.left <= src2->extents.left) &&
801 (src1->extents.top <= src2->extents.top) &&
802 (src1->extents.right >= src2->extents.right) &&
803 (src1->extents.bottom >= src2->extents.bottom))
804 return copy_region( dst, src1 );
806 if ((src2->num_rects == 1) &&
807 (src2->extents.left <= src1->extents.left) &&
808 (src2->extents.top <= src1->extents.top) &&
809 (src2->extents.right >= src1->extents.right) &&
810 (src2->extents.bottom >= src1->extents.bottom))
811 return copy_region( dst, src2 );
813 if (!region_op( dst, src1, src2, union_overlapping,
814 union_non_overlapping, union_non_overlapping )) return NULL;
816 dst->extents.left = min(src1->extents.left, src2->extents.left);
817 dst->extents.top = min(src1->extents.top, src2->extents.top);
818 dst->extents.right = max(src1->extents.right, src2->extents.right);
819 dst->extents.bottom = max(src1->extents.bottom, src2->extents.bottom);
820 return dst;
823 /* compute the exclusive or of two regions into dst, which can be one of the source regions */
824 struct region *xor_region( struct region *dst, const struct region *src1,
825 const struct region *src2 )
827 struct region *tmp = create_empty_region();
829 if (!tmp) return NULL;
831 if (!subtract_region( tmp, src1, src2 ) ||
832 !subtract_region( dst, src2, src1 ) ||
833 !union_region( dst, dst, tmp ))
834 dst = NULL;
836 free_region( tmp );
837 return dst;
840 /* check if the given point is inside the region */
841 int point_in_region( struct region *region, int x, int y )
843 const rectangle_t *ptr, *end;
845 for (ptr = region->rects, end = region->rects + region->num_rects; ptr < end; ptr++)
847 if (ptr->top > y) return 0;
848 if (ptr->bottom <= y) continue;
849 /* now we are in the correct band */
850 if (ptr->left > x) return 0;
851 if (ptr->right <= x) continue;
852 return 1;
854 return 0;
857 /* check if the given rectangle is (at least partially) inside the region */
858 int rect_in_region( struct region *region, const rectangle_t *rect )
860 const rectangle_t *ptr, *end;
862 for (ptr = region->rects, end = region->rects + region->num_rects; ptr < end; ptr++)
864 if (ptr->top >= rect->bottom) return 0;
865 if (ptr->bottom <= rect->top) continue;
866 if (ptr->left >= rect->right) continue;
867 if (ptr->right <= rect->left) continue;
868 return 1;
870 return 0;