1 /* ***** BEGIN LICENSE BLOCK *****
2 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
4 * The contents of this file are subject to the Mozilla Public License Version
5 * 1.1 (the "License"); you may not use this file except in compliance with
6 * the License. You may obtain a copy of the License at
7 * http://www.mozilla.org/MPL/
9 * Software distributed under the License is distributed on an "AS IS" basis,
10 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
11 * for the specific language governing rights and limitations under the
14 * The Original Code is mozilla.org code.
16 * The Initial Developer of the Original Code is
17 * Dainis Jonitis, <Dainis_Jonitis@swh-t.lv>.
18 * Portions created by the Initial Developer are Copyright (C) 2001
19 * the Initial Developer. All Rights Reserved.
23 * Alternatively, the contents of this file may be used under the terms of
24 * either of the GNU General Public License Version 2 or later (the "GPL"),
25 * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
26 * in which case the provisions of the GPL or the LGPL are applicable instead
27 * of those above. If you wish to allow use of your version of this file only
28 * under the terms of either the GPL or the LGPL, and not to allow others to
29 * use your version of this file under the terms of the MPL, indicate your
30 * decision by deleting the provisions above and replace them with the notice
31 * and other provisions required by the GPL or the LGPL. If you do not delete
32 * the provisions above, a recipient may use your version of this file under
33 * the terms of any one of the MPL, the GPL or the LGPL.
35 * ***** END LICENSE BLOCK ***** */
48 * Implementation of regions.
49 * A region is represented as circular double-linked list of nsRegion::RgnRect structures.
50 * Rectangles in this list do not overlap and are sorted by (y, x) coordinates.
52 * nsRegions use nscoord coordinates and nsRects.
56 friend class nsRegionRectIterator
;
57 friend class RgnRectMemoryAllocator
;
60 // Special version of nsRect structure for speed optimizations in nsRegion code.
61 // Most important functions could be made inline and be sure that passed rectangles
62 // will always be non-empty.
64 // Do not add any new member variables to this structure!
65 // Otherwise it will break casts from nsRect to nsRectFast, which expect data parts to be identical.
66 struct nsRectFast
: public nsRect
68 nsRectFast () {} // No need to call parent constructor to set default values
69 nsRectFast (PRInt32 aX
, PRInt32 aY
, PRInt32 aWidth
, PRInt32 aHeight
) : nsRect (aX
, aY
, aWidth
, aHeight
) {}
70 nsRectFast (const nsRect
& aRect
) : nsRect (aRect
) {}
72 // Override nsRect methods to make them inline. Do not check for emptiness.
73 inline PRBool
Contains (const nsRect
& aRect
) const;
74 inline PRBool
Intersects (const nsRect
& aRect
) const;
75 inline PRBool
IntersectRect (const nsRect
& aRect1
, const nsRect
& aRect2
);
76 inline void UnionRect (const nsRect
& aRect1
, const nsRect
& aRect2
);
80 struct RgnRect
: public nsRectFast
85 RgnRect () {} // No need to call parent constructor to set default values
86 RgnRect (PRInt32 aX
, PRInt32 aY
, PRInt32 aWidth
, PRInt32 aHeight
) : nsRectFast (aX
, aY
, aWidth
, aHeight
) {}
87 RgnRect (const nsRectFast
& aRect
) : nsRectFast (aRect
) {}
89 void* operator new (size_t) CPP_THROW_NEW
;
90 void operator delete (void* aRect
, size_t);
92 RgnRect
& operator = (const RgnRect
& aRect
) // Do not overwrite prev/next pointers
97 height
= aRect
.height
;
104 nsRegion () { Init (); }
105 nsRegion (const nsRect
& aRect
) { Init (); Copy (aRect
); }
106 nsRegion (const nsRegion
& aRegion
) { Init (); Copy (aRegion
); }
107 ~nsRegion () { SetToElements (0); }
108 nsRegion
& operator = (const nsRect
& aRect
) { Copy (aRect
); return *this; }
109 nsRegion
& operator = (const nsRegion
& aRegion
) { Copy (aRegion
); return *this; }
112 nsRegion
& And (const nsRegion
& aRgn1
, const nsRegion
& aRgn2
);
113 nsRegion
& And (const nsRegion
& aRegion
, const nsRect
& aRect
);
114 nsRegion
& And (const nsRect
& aRect
, const nsRegion
& aRegion
)
116 return And (aRegion
, aRect
);
118 nsRegion
& And (const nsRect
& aRect1
, const nsRect
& aRect2
)
122 TmpRect
.IntersectRect (aRect1
, aRect2
);
123 return Copy (TmpRect
);
126 nsRegion
& Or (const nsRegion
& aRgn1
, const nsRegion
& aRgn2
);
127 nsRegion
& Or (const nsRegion
& aRegion
, const nsRect
& aRect
);
128 nsRegion
& Or (const nsRect
& aRect
, const nsRegion
& aRegion
)
130 return Or (aRegion
, aRect
);
132 nsRegion
& Or (const nsRect
& aRect1
, const nsRect
& aRect2
)
135 return Or (*this, aRect2
);
138 nsRegion
& Xor (const nsRegion
& aRgn1
, const nsRegion
& aRgn2
);
139 nsRegion
& Xor (const nsRegion
& aRegion
, const nsRect
& aRect
);
140 nsRegion
& Xor (const nsRect
& aRect
, const nsRegion
& aRegion
)
142 return Xor (aRegion
, aRect
);
144 nsRegion
& Xor (const nsRect
& aRect1
, const nsRect
& aRect2
)
147 return Xor (*this, aRect2
);
150 nsRegion
& Sub (const nsRegion
& aRgn1
, const nsRegion
& aRgn2
);
151 nsRegion
& Sub (const nsRegion
& aRegion
, const nsRect
& aRect
);
152 nsRegion
& Sub (const nsRect
& aRect
, const nsRegion
& aRegion
)
154 return Sub (nsRegion (aRect
), aRegion
);
156 nsRegion
& Sub (const nsRect
& aRect1
, const nsRect
& aRect2
)
159 return Sub (*this, aRect2
);
162 PRBool
Contains (const nsRect
& aRect
) const;
163 PRBool
Intersects (const nsRect
& aRect
) const;
165 void MoveBy (PRInt32 aXOffset
, PRInt32 aYOffset
)
167 MoveBy (nsPoint (aXOffset
, aYOffset
));
169 void MoveBy (nsPoint aPt
);
173 mBoundRect
.SetRect (0, 0, 0, 0);
176 PRBool
IsEmpty () const { return mRectCount
== 0; }
177 PRBool
IsComplex () const { return mRectCount
> 1; }
178 PRBool
IsEqual (const nsRegion
& aRegion
) const;
179 PRUint32
GetNumRects () const { return mRectCount
; }
180 const nsRect
& GetBounds () const { return mBoundRect
; }
181 // Converts this region from aFromAPP, an appunits per pixel ratio, to
182 // aToAPP. This applies nsRect::ConvertAppUnitsRoundOut/In to each rect of
184 nsRegion
ConvertAppUnitsRoundOut (PRInt32 aFromAPP
, PRInt32 aToAPP
) const;
185 nsRegion
ConvertAppUnitsRoundIn (PRInt32 aFromAPP
, PRInt32 aToAPP
) const;
186 nsIntRegion
ToOutsidePixels (nscoord aAppUnitsPerPixel
) const;
187 nsRect
GetLargestRectangle () const;
190 * Make sure the region has at most aMaxRects by adding area to it
191 * if necessary. The simplified region will be a superset of the
192 * original region. The simplified region's bounding box will be
193 * the same as for the current region.
195 void SimplifyOutward (PRUint32 aMaxRects
);
197 * Make sure the region has at most aMaxRects by removing area from
198 * it if necessary. The simplified region will be a subset of the
201 void SimplifyInward (PRUint32 aMaxRects
);
203 * Efficiently try to remove a rectangle from this region. The actual
204 * area removed could be some sub-area contained by the rectangle
205 * (even possibly nothing at all).
207 * We remove all rectangles that are contained by aRect.
209 void SimpleSubtract (const nsRect
& aRect
);
211 * Efficiently try to remove a region from this region. The actual
212 * area removed could be some sub-area contained by aRegion
213 * (even possibly nothing at all).
215 * We remove all rectangles of this region that are contained by
216 * a rectangle of aRegion.
218 void SimpleSubtract (const nsRegion
& aRegion
);
221 * Initialize any static data associated with nsRegion.
223 static nsresult
InitStatic();
226 * Deinitialize static data.
228 static void ShutdownStatic();
233 RgnRect mRectListHead
;
234 nsRectFast mBoundRect
;
237 nsRegion
& Copy (const nsRegion
& aRegion
);
238 nsRegion
& Copy (const nsRect
& aRect
);
239 void InsertBefore (RgnRect
* aNewRect
, RgnRect
* aRelativeRect
);
240 void InsertAfter (RgnRect
* aNewRect
, RgnRect
* aRelativeRect
);
241 void SetToElements (PRUint32 aCount
);
242 RgnRect
* Remove (RgnRect
* aRect
);
243 void InsertInPlace (RgnRect
* aRect
, PRBool aOptimizeOnFly
= PR_FALSE
);
244 inline void SaveLinkChain ();
245 inline void RestoreLinkChain ();
247 void SubRegion (const nsRegion
& aRegion
, nsRegion
& aResult
) const;
248 void SubRect (const nsRectFast
& aRect
, nsRegion
& aResult
, nsRegion
& aCompleted
) const;
249 void SubRect (const nsRectFast
& aRect
, nsRegion
& aResult
) const
250 { SubRect (aRect
, aResult
, aResult
); }
251 void Merge (const nsRegion
& aRgn1
, const nsRegion
& aRgn2
);
252 void MoveInto (nsRegion
& aDestRegion
, const RgnRect
* aStartRect
);
253 void MoveInto (nsRegion
& aDestRegion
)
254 { MoveInto (aDestRegion
, mRectListHead
.next
); }
259 // Allow read-only access to region rectangles by iterating the list
261 class NS_GFX nsRegionRectIterator
263 const nsRegion
* mRegion
;
264 const nsRegion::RgnRect
* mCurPtr
;
267 nsRegionRectIterator (const nsRegion
& aRegion
)
270 mCurPtr
= &aRegion
.mRectListHead
;
273 const nsRect
* Next ()
275 mCurPtr
= mCurPtr
->next
;
276 return (mCurPtr
!= &mRegion
->mRectListHead
) ? mCurPtr
: nsnull
;
279 const nsRect
* Prev ()
281 mCurPtr
= mCurPtr
->prev
;
282 return (mCurPtr
!= &mRegion
->mRectListHead
) ? mCurPtr
: nsnull
;
287 mCurPtr
= &mRegion
->mRectListHead
;
292 * nsIntRegions use PRInt32 coordinates and nsIntRects.
294 class NS_GFX nsIntRegion
296 friend class nsIntRegionRectIterator
;
300 nsIntRegion (const nsIntRect
& aRect
) : mImpl (ToRect(aRect
)) {}
301 nsIntRegion (const nsIntRegion
& aRegion
) : mImpl (aRegion
.mImpl
) {}
302 nsIntRegion
& operator = (const nsIntRect
& aRect
) { mImpl
= ToRect (aRect
); return *this; }
303 nsIntRegion
& operator = (const nsIntRegion
& aRegion
) { mImpl
= aRegion
.mImpl
; return *this; }
305 bool operator==(const nsIntRegion
& aRgn
) const
307 return IsEqual(aRgn
);
310 nsIntRegion
& And (const nsIntRegion
& aRgn1
, const nsIntRegion
& aRgn2
)
312 mImpl
.And (aRgn1
.mImpl
, aRgn2
.mImpl
);
315 nsIntRegion
& And (const nsIntRegion
& aRegion
, const nsIntRect
& aRect
)
317 mImpl
.And (aRegion
.mImpl
, ToRect (aRect
));
320 nsIntRegion
& And (const nsIntRect
& aRect
, const nsIntRegion
& aRegion
)
322 return And (aRegion
, aRect
);
324 nsIntRegion
& And (const nsIntRect
& aRect1
, const nsIntRect
& aRect2
)
328 TmpRect
.IntersectRect (aRect1
, aRect2
);
329 mImpl
= ToRect (TmpRect
);
333 nsIntRegion
& Or (const nsIntRegion
& aRgn1
, const nsIntRegion
& aRgn2
)
335 mImpl
.Or (aRgn1
.mImpl
, aRgn2
.mImpl
);
338 nsIntRegion
& Or (const nsIntRegion
& aRegion
, const nsIntRect
& aRect
)
340 mImpl
.Or (aRegion
.mImpl
, ToRect (aRect
));
343 nsIntRegion
& Or (const nsIntRect
& aRect
, const nsIntRegion
& aRegion
)
345 return Or (aRegion
, aRect
);
347 nsIntRegion
& Or (const nsIntRect
& aRect1
, const nsIntRect
& aRect2
)
349 mImpl
= ToRect (aRect1
);
350 return Or (*this, aRect2
);
353 nsIntRegion
& Xor (const nsIntRegion
& aRgn1
, const nsIntRegion
& aRgn2
)
355 mImpl
.Xor (aRgn1
.mImpl
, aRgn2
.mImpl
);
358 nsIntRegion
& Xor (const nsIntRegion
& aRegion
, const nsIntRect
& aRect
)
360 mImpl
.Xor (aRegion
.mImpl
, ToRect (aRect
));
363 nsIntRegion
& Xor (const nsIntRect
& aRect
, const nsIntRegion
& aRegion
)
365 return Xor (aRegion
, aRect
);
367 nsIntRegion
& Xor (const nsIntRect
& aRect1
, const nsIntRect
& aRect2
)
369 mImpl
= ToRect (aRect1
);
370 return Xor (*this, aRect2
);
373 nsIntRegion
& Sub (const nsIntRegion
& aRgn1
, const nsIntRegion
& aRgn2
)
375 mImpl
.Sub (aRgn1
.mImpl
, aRgn2
.mImpl
);
378 nsIntRegion
& Sub (const nsIntRegion
& aRegion
, const nsIntRect
& aRect
)
380 mImpl
.Sub (aRegion
.mImpl
, ToRect (aRect
));
383 nsIntRegion
& Sub (const nsIntRect
& aRect
, const nsIntRegion
& aRegion
)
385 return Sub (nsIntRegion (aRect
), aRegion
);
387 nsIntRegion
& Sub (const nsIntRect
& aRect1
, const nsIntRect
& aRect2
)
389 mImpl
= ToRect (aRect1
);
390 return Sub (*this, aRect2
);
393 PRBool
Contains (const nsIntRect
& aRect
) const
395 return mImpl
.Contains (ToRect (aRect
));
397 PRBool
Intersects (const nsIntRect
& aRect
) const
399 return mImpl
.Intersects (ToRect (aRect
));
402 void MoveBy (PRInt32 aXOffset
, PRInt32 aYOffset
)
404 MoveBy (nsIntPoint (aXOffset
, aYOffset
));
406 void MoveBy (nsIntPoint aPt
)
408 mImpl
.MoveBy (aPt
.x
, aPt
.y
);
415 PRBool
IsEmpty () const { return mImpl
.IsEmpty (); }
416 PRBool
IsComplex () const { return mImpl
.IsComplex (); }
417 PRBool
IsEqual (const nsIntRegion
& aRegion
) const
419 return mImpl
.IsEqual (aRegion
.mImpl
);
421 PRUint32
GetNumRects () const { return mImpl
.GetNumRects (); }
422 nsIntRect
GetBounds () const { return FromRect (mImpl
.GetBounds ()); }
423 nsRegion
ToAppUnits (nscoord aAppUnitsPerPixel
) const;
424 nsIntRect
GetLargestRectangle () const { return FromRect (mImpl
.GetLargestRectangle()); }
427 * Make sure the region has at most aMaxRects by adding area to it
428 * if necessary. The simplified region will be a superset of the
429 * original region. The simplified region's bounding box will be
430 * the same as for the current region.
432 void SimplifyOutward (PRUint32 aMaxRects
)
434 mImpl
.SimplifyOutward (aMaxRects
);
437 * Make sure the region has at most aMaxRects by removing area from
438 * it if necessary. The simplified region will be a subset of the
441 void SimplifyInward (PRUint32 aMaxRects
)
443 mImpl
.SimplifyInward (aMaxRects
);
446 * Efficiently try to remove a rectangle from this region. The actual
447 * area removed could be some sub-area contained by the rectangle
448 * (even possibly nothing at all).
450 * We remove all rectangles that are contained by aRect.
452 void SimpleSubtract (const nsIntRect
& aRect
)
454 mImpl
.SimpleSubtract (ToRect (aRect
));
457 * Efficiently try to remove a region from this region. The actual
458 * area removed could be some sub-area contained by aRegion
459 * (even possibly nothing at all).
461 * We remove all rectangles of this region that are contained by
462 * a rectangle of aRegion.
464 void SimpleSubtract (const nsIntRegion
& aRegion
)
466 mImpl
.SimpleSubtract (aRegion
.mImpl
);
472 static nsRect
ToRect(const nsIntRect
& aRect
)
474 return nsRect (aRect
.x
, aRect
.y
, aRect
.width
, aRect
.height
);
476 static nsIntRect
FromRect(const nsRect
& aRect
)
478 return nsIntRect (aRect
.x
, aRect
.y
, aRect
.width
, aRect
.height
);
482 class NS_GFX nsIntRegionRectIterator
484 nsRegionRectIterator mImpl
;
488 nsIntRegionRectIterator (const nsIntRegion
& aRegion
) : mImpl (aRegion
.mImpl
) {}
490 const nsIntRect
* Next ()
492 const nsRect
* r
= mImpl
.Next();
495 mTmp
= nsIntRegion::FromRect (*r
);
499 const nsIntRect
* Prev ()
501 const nsRect
* r
= mImpl
.Prev();
504 mTmp
= nsIntRegion::FromRect (*r
);