1582da173SStephan Aßmus/* $Xorg: Region.c,v 1.6 2001/02/09 02:03:35 xorgcvs Exp $ */
2582da173SStephan Aßmus/************************************************************************
3582da173SStephan Aßmus
4582da173SStephan AßmusCopyright 1987, 1988, 1998  The Open Group
5582da173SStephan Aßmus
6582da173SStephan AßmusPermission to use, copy, modify, distribute, and sell this software and its
7582da173SStephan Aßmusdocumentation for any purpose is hereby granted without fee, provided that
8582da173SStephan Aßmusthe above copyright notice appear in all copies and that both that
9582da173SStephan Aßmuscopyright notice and this permission notice appear in supporting
10582da173SStephan Aßmusdocumentation.
11582da173SStephan Aßmus
12582da173SStephan AßmusThe above copyright notice and this permission notice shall be included in
13582da173SStephan Aßmusall copies or substantial portions of the Software.
14582da173SStephan Aßmus
15582da173SStephan AßmusTHE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16582da173SStephan AßmusIMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17582da173SStephan AßmusFITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
18582da173SStephan AßmusOPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
19582da173SStephan AßmusAN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
20582da173SStephan AßmusCONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
21582da173SStephan Aßmus
22582da173SStephan AßmusExcept as contained in this notice, the name of The Open Group shall not be
23582da173SStephan Aßmusused in advertising or otherwise to promote the sale, use or other dealings
24582da173SStephan Aßmusin this Software without prior written authorization from The Open Group.
25582da173SStephan Aßmus
26582da173SStephan Aßmus
27582da173SStephan AßmusCopyright 1987, 1988 by Digital Equipment Corporation, Maynard, Massachusetts.
28582da173SStephan Aßmus
29582da173SStephan Aßmus                        All Rights Reserved
30582da173SStephan Aßmus
317deac319SAugustin CavalierPermission to use, copy, modify, and distribute this software and its
327deac319SAugustin Cavalierdocumentation for any purpose and without fee is hereby granted,
33582da173SStephan Aßmusprovided that the above copyright notice appear in all copies and that
347deac319SAugustin Cavalierboth that copyright notice and this permission notice appear in
35582da173SStephan Aßmussupporting documentation, and that the name of Digital not be
36582da173SStephan Aßmusused in advertising or publicity pertaining to distribution of the
377deac319SAugustin Cavaliersoftware without specific, written prior permission.
38582da173SStephan Aßmus
39582da173SStephan AßmusDIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
40582da173SStephan AßmusALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
41582da173SStephan AßmusDIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
42582da173SStephan AßmusANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
43582da173SStephan AßmusWHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
44582da173SStephan AßmusARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
45582da173SStephan AßmusSOFTWARE.
46582da173SStephan Aßmus
47582da173SStephan Aßmus************************************************************************/
48582da173SStephan Aßmus/* $XFree86: xc/lib/X11/Region.c,v 1.9 2002/06/04 22:19:57 dawes Exp $ */
49582da173SStephan Aßmus/*
50582da173SStephan Aßmus * The functions in this file implement the BRegion* abstraction, similar to one
51582da173SStephan Aßmus * used in the X11 sample server. A BRegion* is simply an area, as the name
52582da173SStephan Aßmus * implies, and is implemented as a "y-x-banded" array of rectangles. To
53582da173SStephan Aßmus * explain: Each BRegion* is made up of a certain number of rectangles sorted
54582da173SStephan Aßmus * by y coordinate first, and then by x coordinate.
55582da173SStephan Aßmus *
56582da173SStephan Aßmus * Furthermore, the rectangles are banded such that every rectangle with a
57582da173SStephan Aßmus * given upper-left y coordinate (top) will have the same lower-right y
58582da173SStephan Aßmus * coordinate (bottom) and vice versa. If a rectangle has scanlines in a band, it
59582da173SStephan Aßmus * will span the entire vertical distance of the band. This means that some
60582da173SStephan Aßmus * areas that could be merged into a taller rectangle will be represented as
61582da173SStephan Aßmus * several shorter rectangles to account for shorter rectangles to its left
62582da173SStephan Aßmus * or right but within its "vertical scope".
63582da173SStephan Aßmus *
64582da173SStephan Aßmus * An added constraint on the rectangles is that they must cover as much
65582da173SStephan Aßmus * horizontal area as possible. E.g. no two rectangles in a band are allowed
66582da173SStephan Aßmus * to touch.
67582da173SStephan Aßmus *
68582da173SStephan Aßmus * Whenever possible, bands will be merged together to cover a greater vertical
69582da173SStephan Aßmus * distance (and thus reduce the number of rectangles). Two bands can be merged
70582da173SStephan Aßmus * only if the bottom of one touches the top of the other and they have
71582da173SStephan Aßmus * rectangles in the same places (of the same width, of course). This maintains
72582da173SStephan Aßmus * the y-x-banding that's so nice to have...
73582da173SStephan Aßmus */
74582da173SStephan Aßmus
75582da173SStephan Aßmus#include "RegionSupport.h"
76582da173SStephan Aßmus
776e927a5fSIngo Weinhold#include <stdlib.h>
784be90e7fSStefano Ceccherini#include <new>
798d1a0ee7SStefano Ceccherini
80582da173SStephan Aßmususing std::nothrow;
81791e557cSStefano Ceccherini
82582da173SStephan Aßmus#include <SupportDefs.h>
838d1a0ee7SStefano Ceccherini
84791e557cSStefano Ceccherini
85582da173SStephan Aßmus#ifdef DEBUG
86582da173SStephan Aßmus#include <stdio.h>
87582da173SStephan Aßmus#define assert(expr) {if (!(expr)) fprintf(stderr,\
88e2c699caSIngo Weinhold"Assertion failed file %s, line %d: " #expr "\n", __FILE__, __LINE__); }
894be90e7fSStefano Ceccherini#else
90582da173SStephan Aßmus#define assert(expr)
914be90e7fSStefano Ceccherini#endif
924be90e7fSStefano Ceccherini
9364b98d23Shaydentech
94582da173SStephan Aßmus/*  1 if two clipping_rects overlap.
95582da173SStephan Aßmus *  0 if two clipping_rects do not overlap.
967deac319SAugustin Cavalier *  Remember, right and bottom are not in the region
97582da173SStephan Aßmus */
98582da173SStephan Aßmus#define EXTENTCHECK(r1, r2) \
99582da173SStephan Aßmus	((r1)->right > (r2)->left && \
100582da173SStephan Aßmus	 (r1)->left < (r2)->right && \
101582da173SStephan Aßmus	 (r1)->bottom > (r2)->top && \
102582da173SStephan Aßmus	 (r1)->top < (r2)->bottom)
103582da173SStephan Aßmus
104582da173SStephan Aßmus/*
105582da173SStephan Aßmus *  update region fBounds
106582da173SStephan Aßmus */
107582da173SStephan Aßmus#define EXTENTS(r,idRect){\
1083bfa2d12SJérôme Duval            if ((r)->left < (idRect)->fBounds.left)\
109582da173SStephan Aßmus              (idRect)->fBounds.left = (r)->left;\
1103bfa2d12SJérôme Duval            if ((r)->top < (idRect)->fBounds.top)\
111582da173SStephan Aßmus              (idRect)->fBounds.top = (r)->top;\
1123bfa2d12SJérôme Duval            if ((r)->right > (idRect)->fBounds.right)\
113582da173SStephan Aßmus              (idRect)->fBounds.right = (r)->right;\
1143bfa2d12SJérôme Duval            if ((r)->bottom > (idRect)->fBounds.bottom)\
115582da173SStephan Aßmus              (idRect)->fBounds.bottom = (r)->bottom;\
116582da173SStephan Aßmus        }
117582da173SStephan Aßmus
118582da173SStephan Aßmus/*
119582da173SStephan Aßmus *   Check to see if there is enough memory in the present region.
120582da173SStephan Aßmus */
121582da173SStephan Aßmus#define MEMCHECK(reg, rect, firstrect){\
122582da173SStephan Aßmus        if ((reg)->fCount >= ((reg)->fDataSize - 1)){\
123582da173SStephan Aßmus          (firstrect) = (clipping_rect *) realloc \
124582da173SStephan Aßmus          ((char *)(firstrect), (unsigned) (2 * (sizeof(clipping_rect)) * ((reg)->fDataSize)));\
125582da173SStephan Aßmus          if ((firstrect) == 0)\
126582da173SStephan Aßmus            return(0);\
127582da173SStephan Aßmus          (reg)->fDataSize *= 2;\
128582da173SStephan Aßmus          (rect) = &(firstrect)[(reg)->fCount];\
129582da173SStephan Aßmus         }\
130582da173SStephan Aßmus       }
131582da173SStephan Aßmus
132582da173SStephan Aßmus/*  this routine checks to see if the previous rectangle is the same
133582da173SStephan Aßmus *  or subsumes the new rectangle to add.
134582da173SStephan Aßmus */
135582da173SStephan Aßmus
136582da173SStephan Aßmus#define CHECK_PREVIOUS(Reg, R, Rx1, Ry1, Rx2, Ry2)\
137582da173SStephan Aßmus               (!(((Reg)->fCount > 0)&&\
138582da173SStephan Aßmus                  ((R-1)->top == (Ry1)) &&\
139582da173SStephan Aßmus                  ((R-1)->bottom == (Ry2)) &&\
140582da173SStephan Aßmus                  ((R-1)->left <= (Rx1)) &&\
141582da173SStephan Aßmus                  ((R-1)->right >= (Rx2))))
142582da173SStephan Aßmus
143582da173SStephan Aßmus/*  add a rectangle to the given BRegion */
144582da173SStephan Aßmus#define ADDRECT(reg, r, rx1, ry1, rx2, ry2){\
145582da173SStephan Aßmus    if (((rx1) < (rx2)) && ((ry1) < (ry2)) &&\
146582da173SStephan Aßmus        CHECK_PREVIOUS((reg), (r), (rx1), (ry1), (rx2), (ry2))){\
147582da173SStephan Aßmus              (r)->left = (rx1);\
148582da173SStephan Aßmus              (r)->top = (ry1);\
149582da173SStephan Aßmus              (r)->right = (rx2);\
150582da173SStephan Aßmus              (r)->bottom = (ry2);\
151582da173SStephan Aßmus              EXTENTS((r), (reg));\
152582da173SStephan Aßmus              (reg)->fCount++;\
153582da173SStephan Aßmus              (r)++;\
154582da173SStephan Aßmus            }\
155582da173SStephan Aßmus        }
156582da173SStephan Aßmus
157582da173SStephan Aßmus
158582da173SStephan Aßmus
159582da173SStephan Aßmus/*  add a rectangle to the given BRegion */
160582da173SStephan Aßmus#define ADDRECTNOX(reg, r, rx1, ry1, rx2, ry2){\
161582da173SStephan Aßmus            if ((rx1 < rx2) && (ry1 < ry2) &&\
162582da173SStephan Aßmus                CHECK_PREVIOUS((reg), (r), (rx1), (ry1), (rx2), (ry2))){\
163582da173SStephan Aßmus              (r)->left = (rx1);\
164582da173SStephan Aßmus              (r)->top = (ry1);\
165582da173SStephan Aßmus              (r)->right = (rx2);\
166582da173SStephan Aßmus              (r)->bottom = (ry2);\
167582da173SStephan Aßmus              (reg)->fCount++;\
168582da173SStephan Aßmus              (r)++;\
169582da173SStephan Aßmus            }\
170582da173SStephan Aßmus        }
171582da173SStephan Aßmus
172582da173SStephan Aßmus#define EMPTY_REGION(pReg) pReg->MakeEmpty()
173582da173SStephan Aßmus
174582da173SStephan Aßmus#define REGION_NOT_EMPTY(pReg) pReg->fCount
175582da173SStephan Aßmus
176582da173SStephan Aßmus#define INBOX(r, x, y) \
177582da173SStephan Aßmus      ( ( ((r).right >  x)) && \
178582da173SStephan Aßmus        ( ((r).left <= x)) && \
179582da173SStephan Aßmus        ( ((r).bottom >  y)) && \
180582da173SStephan Aßmus        ( ((r).top <= y)) )
181582da173SStephan Aßmus
182582da173SStephan Aßmus
183582da173SStephan Aßmus
184582da173SStephan Aßmus/*	Create a new empty region	*/
185582da173SStephan AßmusBRegion*
186582da173SStephan AßmusBRegion::Support::CreateRegion(void)
187791e557cSStefano Ceccherini{
188582da173SStephan Aßmus    return new (nothrow) BRegion();
189791e557cSStefano Ceccherini}
190791e557cSStefano Ceccherini
191791e557cSStefano Ceccherinivoid
192582da173SStephan AßmusBRegion::Support::DestroyRegion(BRegion* r)
193791e557cSStefano Ceccherini{
194582da173SStephan Aßmus	delete r;
195791e557cSStefano Ceccherini}
196791e557cSStefano Ceccherini
197791e557cSStefano Ceccherini
198582da173SStephan Aßmus/*-
199582da173SStephan Aßmus *-----------------------------------------------------------------------
200582da173SStephan Aßmus * miSetExtents --
201582da173SStephan Aßmus *	Reset the fBounds of a region to what they should be. Called by
202582da173SStephan Aßmus *	miSubtract and miIntersect b/c they can't figure it out along the
203582da173SStephan Aßmus *	way or do so easily, as miUnion can.
204582da173SStephan Aßmus *
205582da173SStephan Aßmus * Results:
206582da173SStephan Aßmus *	None.
207582da173SStephan Aßmus *
208582da173SStephan Aßmus * Side Effects:
209582da173SStephan Aßmus *	The region's 'fBounds' structure is overwritten.
210582da173SStephan Aßmus *
211582da173SStephan Aßmus *-----------------------------------------------------------------------
212582da173SStephan Aßmus */
213791e557cSStefano Ceccherinivoid
214582da173SStephan AßmusBRegion::Support::miSetExtents(BRegion* pReg)
215791e557cSStefano Ceccherini{
216582da173SStephan Aßmus    register clipping_rect*	pBox;
217582da173SStephan Aßmus	clipping_rect* pBoxEnd;
218582da173SStephan Aßmus	clipping_rect* pExtents;
219582da173SStephan Aßmus
220582da173SStephan Aßmus    if (pReg->fCount == 0)
221582da173SStephan Aßmus    {
222582da173SStephan Aßmus	pReg->fBounds.left = 0;
223582da173SStephan Aßmus	pReg->fBounds.top = 0;
224582da173SStephan Aßmus	pReg->fBounds.right = 0;
225582da173SStephan Aßmus	pReg->fBounds.bottom = 0;
226582da173SStephan Aßmus	return;
227582da173SStephan Aßmus    }
228582da173SStephan Aßmus
229582da173SStephan Aßmus    pExtents = &pReg->fBounds;
230582da173SStephan Aßmus    pBox = pReg->fData;
231582da173SStephan Aßmus    pBoxEnd = &pBox[pReg->fCount - 1];
232582da173SStephan Aßmus
233582da173SStephan Aßmus    /*
234582da173SStephan Aßmus     * Since pBox is the first rectangle in the region, it must have the
235582da173SStephan Aßmus     * smallest top and since pBoxEnd is the last rectangle in the region,
236582da173SStephan Aßmus     * it must have the largest bottom, because of banding. Initialize left and
237582da173SStephan Aßmus     * right from  pBox and pBoxEnd, resp., as good things to initialize them
238582da173SStephan Aßmus     * to...
239582da173SStephan Aßmus     */
240582da173SStephan Aßmus    pExtents->left = pBox->left;
241582da173SStephan Aßmus    pExtents->top = pBox->top;
242582da173SStephan Aßmus    pExtents->right = pBoxEnd->right;
243582da173SStephan Aßmus    pExtents->bottom = pBoxEnd->bottom;
244582da173SStephan Aßmus
245582da173SStephan Aßmus    assert(pExtents->top < pExtents->bottom);
246582da173SStephan Aßmus    while (pBox <= pBoxEnd)
247582da173SStephan Aßmus    {
248582da173SStephan Aßmus	if (pBox->left < pExtents->left)
249582da173SStephan Aßmus	{
250582da173SStephan Aßmus	    pExtents->left = pBox->left;
2514be90e7fSStefano Ceccherini	}
252582da173SStephan Aßmus	if (pBox->right > pExtents->right)
253582da173SStephan Aßmus	{
254582da173SStephan Aßmus	    pExtents->right = pBox->right;
255582da173SStephan Aßmus	}
256582da173SStephan Aßmus	pBox++;
257582da173SStephan Aßmus    }
258582da173SStephan Aßmus    assert(pExtents->left < pExtents->right);
2594be90e7fSStefano Ceccherini}
2604be90e7fSStefano Ceccherini
2614be90e7fSStefano Ceccherini
262582da173SStephan Aßmus/* TranslateRegion(pRegion, x, y)
263582da173SStephan Aßmus   translates in place
264582da173SStephan Aßmus   added by raymond
2654be90e7fSStefano Ceccherini*/
2664be90e7fSStefano Ceccherinivoid
267582da173SStephan AßmusBRegion::Support::XOffsetRegion(
268582da173SStephan Aßmus    register BRegion* pRegion,
269582da173SStephan Aßmus    register int x,
270582da173SStephan Aßmus    register int y)
2714be90e7fSStefano Ceccherini{
272582da173SStephan Aßmus    register int nbox;
273582da173SStephan Aßmus    register clipping_rect *pbox;
274582da173SStephan Aßmus
275582da173SStephan Aßmus    pbox = pRegion->fData;
276582da173SStephan Aßmus    nbox = pRegion->fCount;
277582da173SStephan Aßmus
278582da173SStephan Aßmus    while(nbox--)
279582da173SStephan Aßmus    {
280582da173SStephan Aßmus	pbox->left += x;
281582da173SStephan Aßmus	pbox->right += x;
282582da173SStephan Aßmus	pbox->top += y;
283582da173SStephan Aßmus	pbox->bottom += y;
284582da173SStephan Aßmus	pbox++;
285582da173SStephan Aßmus    }
286582da173SStephan Aßmus    pRegion->fBounds.left += x;
287582da173SStephan Aßmus    pRegion->fBounds.right += x;
288582da173SStephan Aßmus    pRegion->fBounds.top += y;
289582da173SStephan Aßmus    pRegion->fBounds.bottom += y;
2904be90e7fSStefano Ceccherini}
2914be90e7fSStefano Ceccherini
2927deac319SAugustin Cavalier/*
293582da173SStephan Aßmus   Utility procedure Compress:
2947deac319SAugustin Cavalier   Replace r by the region r', where
295582da173SStephan Aßmus     p in r' iff (Quantifer m <= dx) (p + m in r), and
296