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
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
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.
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
73 ************************************************************************/
79 #define WIN32_NO_STATUS
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 );
116 set_error( STATUS_NO_MEMORY );
119 reg->rects = new_rect;
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 */
141 if (ptr[0].bottom > ptr[1].top) return 0; /* not properly y ordered */
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 )
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);
165 if (pCurRect != 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;
185 } while (prevNumRects != 0);
187 pReg->num_rects -= curNumRects;
188 pCurRect -= curNumRects;
189 pPrevRect -= curNumRects;
193 pPrevRect->bottom = pCurRect->bottom;
197 } while (curNumRects != 0);
199 if (pCurRect == pRegEnd) curStart = prevStart;
200 else do { *pPrevRect++ = *pCurRect++; } while (pCurRect != pRegEnd);
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;
235 ybot = reg2->extents.top;
241 curBand = newReg->num_rects;
244 while ((r1BandEnd != r1End) && (r1BandEnd->top == r1->top)) r1BandEnd++;
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;
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;
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;
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;
298 if (non_overlap1_func)
303 while ((r1BandEnd < r1End) && (r1BandEnd->top == r1->top)) r1BandEnd++;
304 if (!non_overlap1_func( newReg, r1, r1BandEnd, max(r1->top,ybot), r1->bottom ))
307 } while (r1 != r1End);
310 else if ((r2 != r2End) && non_overlap2_func)
315 while ((r2BandEnd < r2End) && (r2BandEnd->top == r2->top)) r2BandEnd++;
316 if (!non_overlap2_func( newReg, r2, r2BandEnd, max(r2->top,ybot), r2->bottom ))
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;
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;
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;
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 )
378 while ((r1 != r1End) && (r2 != r2End))
380 left = max(r1->left, r2->left);
381 right = min(r1->right, r2->right);
385 rectangle_t *rect = add_rect( pReg );
390 rect->bottom = bottom;
393 if (r1->right < r2->right) r1++;
394 else if (r2->right < r1->right) r2++;
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 )
410 rectangle_t *rect = add_rect( pReg );
412 rect->left = r->left;
414 rect->right = r->right;
415 rect->bottom = bottom;
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 )
429 while ((r1 != r1End) && (r2 != r2End))
431 if (r2->right <= left) r2++;
432 else if (r2->left <= left)
435 if (left >= r1->right)
443 else if (r2->left < r1->right)
445 rectangle_t *rect = add_rect( pReg );
449 rect->right = r2->left;
450 rect->bottom = bottom;
452 if (left >= r1->right)
462 if (r1->right > left)
464 rectangle_t *rect = add_rect( pReg );
468 rect->right = r1->right;
469 rect->bottom = bottom;
478 rectangle_t *rect = add_rect( pReg );
482 rect->right = r1->right;
483 rect->bottom = bottom;
485 if (r1 != r1End) left = r1->left;
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 )
496 rectangle_t *rect = add_rect( pReg );
498 rect->left = r->left;
500 rect->right = r->right;
501 rect->bottom = bottom;
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; \
526 rectangle_t *rect = add_rect( pReg ); \
527 if (!rect) return 0; \
529 rect->bottom = bottom; \
530 rect->left = r->left; \
531 rect->right = r->right; \
535 while ((r1 != r1End) && (r2 != r2End))
537 if (r1->left < r2->left)
552 } while (r1 != r1End);
554 else while (r2 != r2End)
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) )))
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;
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 );
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) )))
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 );
616 void free_region( struct region *region )
618 free( region->rects );
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;
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);
651 if (max_size >= *total_size) return memdup( data, *total_size );
652 set_error( STATUS_BUFFER_OVERFLOW );
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 );
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++)
708 region->extents.left += x;
709 region->extents.right += x;
710 region->extents.top += y;
711 region->extents.bottom += y;
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 )
717 if (dst == src) return dst;
719 if (dst->size < src->num_rects)
721 rectangle_t *rect = realloc( dst->rects, src->num_rects * sizeof(*rect) );
724 set_error( STATUS_NO_MEMORY );
728 dst->size = src->num_rects;
730 dst->num_rects = src->num_rects;
731 dst->extents = src->extents;
732 memcpy( dst->rects, src->rects, src->num_rects * sizeof(*dst->rects) );
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 )
740 if (!src1->num_rects || !src2->num_rects || !EXTENTCHECK(&src1->extents, &src2->extents))
743 dst->extents.left = 0;
744 dst->extents.top = 0;
745 dst->extents.right = 0;
746 dst->extents.bottom = 0;
749 if (!region_op( dst, src1, src2, intersect_overlapping, NULL, NULL )) return NULL;
750 set_region_extents( dst );
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 )
758 if (!src1->num_rects || !src2->num_rects || !EXTENTCHECK(&src1->extents, &src2->extents))
759 return copy_region( dst, src1 );
761 if (!region_op( dst, src1, src2, subtract_overlapping,
762 subtract_non_overlapping, NULL )) return NULL;
763 set_region_extents( dst );
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 )
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 );
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 );
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 );
789 if (!region_op( dst, src1, src2, union_overlapping,
790 union_non_overlapping, union_non_overlapping )) return NULL;
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);
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 )
803 struct region *tmp = create_empty_region();
805 if (!tmp) return NULL;
807 if (!subtract_region( tmp, src1, src2 ) ||
808 !subtract_region( dst, src2, src1 ) ||
809 !union_region( dst, dst, tmp ))
816 /* check if the given point is inside the region */
817 int point_in_region( struct region *region, int x, int y )
819 const rectangle_t *ptr, *end;
821 for (ptr = region->rects, end = region->rects + region->num_rects; ptr < end; ptr++)
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;
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 )
836 const rectangle_t *ptr, *end;
838 for (ptr = region->rects, end = region->rects + region->num_rects; ptr < end; ptr++)
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;