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 ***** */
39
#include "nsISupportsImpl.h"
41
// Fast inline analogues of nsRect methods for nsRegion::nsRectFast.
42
// Check for emptiness is not required - it is guaranteed by caller.
44
inline PRBool nsRegion::nsRectFast::Contains (const nsRect& aRect) const
46
return (PRBool) ((aRect.x >= x) && (aRect.y >= y) &&
47
(aRect.XMost () <= XMost ()) && (aRect.YMost () <= YMost ()));
50
inline PRBool nsRegion::nsRectFast::Intersects (const nsRect& aRect) const
52
return (PRBool) ((x < aRect.XMost ()) && (y < aRect.YMost ()) &&
53
(aRect.x < XMost ()) && (aRect.y < YMost ()));
56
inline PRBool nsRegion::nsRectFast::IntersectRect (const nsRect& aRect1, const nsRect& aRect2)
58
const nscoord xmost = PR_MIN (aRect1.XMost (), aRect2.XMost ());
59
x = PR_MAX (aRect1.x, aRect2.x);
61
if (width <= 0) return PR_FALSE;
63
const nscoord ymost = PR_MIN (aRect1.YMost (), aRect2.YMost ());
64
y = PR_MAX (aRect1.y, aRect2.y);
66
if (height <= 0) return PR_FALSE;
71
inline void nsRegion::nsRectFast::UnionRect (const nsRect& aRect1, const nsRect& aRect2)
73
const nscoord xmost = PR_MAX (aRect1.XMost (), aRect2.XMost ());
74
const nscoord ymost = PR_MAX (aRect1.YMost (), aRect2.YMost ());
75
x = PR_MIN (aRect1.x, aRect2.x);
76
y = PR_MIN (aRect1.y, aRect2.y);
83
// Custom memory allocator for nsRegion::RgnRect structures.
84
// Entries are allocated from global memory pool.
85
// Memory pool can grow in size, but it can't shrink.
87
#define INIT_MEM_CHUNK_ENTRIES 100
88
#define INCR_MEM_CHUNK_ENTRIES 100
90
class RgnRectMemoryAllocator
92
nsRegion::RgnRect* mFreeListHead;
93
PRUint32 mFreeEntries;
98
void InitLock () { mLock = PR_NewLock (); }
99
void DestroyLock () { PR_DestroyLock (mLock); }
100
void Lock () { PR_Lock (mLock); }
101
void Unlock () { PR_Unlock (mLock); }
102
#elif defined (DEBUG)
105
void InitLock () { NS_ASSERT_OWNINGTHREAD (RgnRectMemoryAllocator); }
106
void DestroyLock () { NS_ASSERT_OWNINGTHREAD (RgnRectMemoryAllocator); }
107
void Lock () { NS_ASSERT_OWNINGTHREAD (RgnRectMemoryAllocator); }
108
void Unlock () { NS_ASSERT_OWNINGTHREAD (RgnRectMemoryAllocator); }
111
void DestroyLock () { }
116
void* AllocChunk (PRUint32 aEntries, void* aNextChunk, nsRegion::RgnRect* aTailDest)
118
PRUint8* pBuf = new PRUint8 [aEntries * sizeof (nsRegion::RgnRect) + sizeof (void*)];
119
*reinterpret_cast<void**>(pBuf) = aNextChunk;
120
nsRegion::RgnRect* pRect = reinterpret_cast<nsRegion::RgnRect*>(pBuf + sizeof (void*));
122
for (PRUint32 cnt = 0 ; cnt < aEntries - 1 ; cnt++)
123
pRect [cnt].next = &pRect [cnt + 1];
125
pRect [aEntries - 1].next = aTailDest;
130
void FreeChunk (void* aChunk) { delete [] (PRUint8 *) aChunk; }
131
void* NextChunk (void* aThisChunk) const { return *static_cast<void**>(aThisChunk); }
133
nsRegion::RgnRect* ChunkHead (void* aThisChunk) const
134
{ return reinterpret_cast<nsRegion::RgnRect*>(static_cast<PRUint8*>(aThisChunk) + sizeof (void*)); }
137
RgnRectMemoryAllocator (PRUint32 aNumOfEntries);
138
~RgnRectMemoryAllocator ();
140
nsRegion::RgnRect* Alloc ();
141
void Free (nsRegion::RgnRect* aRect);
145
RgnRectMemoryAllocator::RgnRectMemoryAllocator (PRUint32 aNumOfEntries)
148
mChunkListHead = AllocChunk (aNumOfEntries, nsnull, nsnull);
149
mFreeEntries = aNumOfEntries;
150
mFreeListHead = ChunkHead (mChunkListHead);
153
RgnRectMemoryAllocator::~RgnRectMemoryAllocator ()
155
while (mChunkListHead)
157
void* tmp = mChunkListHead;
158
mChunkListHead = NextChunk (mChunkListHead);
164
* As a static object this class outlives any library which would implement
165
* locking. So we intentionally leak the 'lock'.
167
* Currently RgnRectMemoryAllocator is only used from the primary thread,
168
* so we aren't using a lock which means that there is no lock to leak.
169
* If we ever switch to multiple GUI threads (e.g. one per window),
170
* we'd probably use one allocator per window-thread to avoid the
171
* locking overhead and just require consumers not to pass regions
172
* across threads/windows, which would be a reasonable restriction
173
* because they wouldn't be useful outside their window.
179
nsRegion::RgnRect* RgnRectMemoryAllocator::Alloc ()
183
if (mFreeEntries == 0)
185
mChunkListHead = AllocChunk (INCR_MEM_CHUNK_ENTRIES, mChunkListHead, mFreeListHead);
186
mFreeEntries = INCR_MEM_CHUNK_ENTRIES;
187
mFreeListHead = ChunkHead (mChunkListHead);
190
nsRegion::RgnRect* tmp = mFreeListHead;
191
mFreeListHead = mFreeListHead->next;
198
void RgnRectMemoryAllocator::Free (nsRegion::RgnRect* aRect)
202
aRect->next = mFreeListHead;
203
mFreeListHead = aRect;
208
// Global pool for nsRegion::RgnRect allocation
209
static RgnRectMemoryAllocator gRectPool (INIT_MEM_CHUNK_ENTRIES);
212
void* nsRegion::RgnRect::operator new (size_t) CPP_THROW_NEW
214
return gRectPool.Alloc ();
217
void nsRegion::RgnRect::operator delete (void* aRect, size_t)
219
gRectPool.Free (static_cast<RgnRect*>(aRect));
224
void nsRegion::Init()
226
mRectListHead.prev = mRectListHead.next = &mRectListHead;
227
mCurRect = &mRectListHead;
229
mBoundRect.SetRect (0, 0, 0, 0);
232
inline void nsRegion::InsertBefore (RgnRect* aNewRect, RgnRect* aRelativeRect)
234
aNewRect->prev = aRelativeRect->prev;
235
aNewRect->next = aRelativeRect;
236
aRelativeRect->prev->next = aNewRect;
237
aRelativeRect->prev = aNewRect;
242
inline void nsRegion::InsertAfter (RgnRect* aNewRect, RgnRect* aRelativeRect)
244
aNewRect->prev = aRelativeRect;
245
aNewRect->next = aRelativeRect->next;
246
aRelativeRect->next->prev = aNewRect;
247
aRelativeRect->next = aNewRect;
253
// Adjust the number of rectangles in region.
254
// Content of rectangles should be changed by caller.
256
void nsRegion::SetToElements (PRUint32 aCount)
258
if (mRectCount < aCount) // Add missing rectangles
260
PRUint32 InsertCount = aCount - mRectCount;
262
RgnRect* pPrev = &mRectListHead;
263
RgnRect* pNext = mRectListHead.next;
265
while (InsertCount--)
267
mCurRect = new RgnRect;
268
mCurRect->prev = pPrev;
269
pPrev->next = mCurRect;
276
if (mRectCount > aCount) // Remove unnecessary rectangles
278
PRUint32 RemoveCount = mRectCount - aCount;
280
mCurRect = mRectListHead.next;
282
while (RemoveCount--)
284
RgnRect* tmp = mCurRect;
285
mCurRect = mCurRect->next;
289
mRectListHead.next = mCurRect;
290
mCurRect->prev = &mRectListHead;
295
// Save the entire chain of linked elements in 'prev' field of the RgnRect structure.
296
// After that forward-only iterations using 'next' field could still be used.
297
// Some elements from forward-only chain could be temporarily removed to optimize inner loops.
298
// The original double linked state could be restored by call to RestoreLinkChain ().
299
// Both functions despite size can be inline because they are called only from one function.
301
inline void nsRegion::SaveLinkChain ()
303
RgnRect* pRect = &mRectListHead;
307
pRect->prev = pRect->next;
309
} while (pRect != &mRectListHead);
313
inline void nsRegion::RestoreLinkChain ()
315
RgnRect* pPrev = &mRectListHead;
316
RgnRect* pRect = mRectListHead.next = mRectListHead.prev;
318
while (pRect != &mRectListHead)
320
pRect->next = pRect->prev;
326
mRectListHead.prev = pPrev;
330
// Insert node in right place of sorted list
331
// If necessary then bounding rectangle could be updated and rectangle combined
332
// with neighbour rectangles. This is usually done in Optimize ()
334
void nsRegion::InsertInPlace (RgnRect* aRect, PRBool aOptimizeOnFly)
337
InsertAfter (aRect, &mRectListHead);
340
if (aRect->y > mCurRect->y)
342
mRectListHead.y = PR_INT32_MAX;
344
while (aRect->y > mCurRect->next->y)
345
mCurRect = mCurRect->next;
347
while (aRect->y == mCurRect->next->y && aRect->x > mCurRect->next->x)
348
mCurRect = mCurRect->next;
350
InsertAfter (aRect, mCurRect);
352
if (aRect->y < mCurRect->y)
354
mRectListHead.y = PR_INT32_MIN;
356
while (aRect->y < mCurRect->prev->y)
357
mCurRect = mCurRect->prev;
359
while (aRect->y == mCurRect->prev->y && aRect->x < mCurRect->prev->x)
360
mCurRect = mCurRect->prev;
362
InsertBefore (aRect, mCurRect);
365
if (aRect->x > mCurRect->x)
367
mRectListHead.y = PR_INT32_MAX;
369
while (aRect->y == mCurRect->next->y && aRect->x > mCurRect->next->x)
370
mCurRect = mCurRect->next;
372
InsertAfter (aRect, mCurRect);
375
mRectListHead.y = PR_INT32_MIN;
377
while (aRect->y == mCurRect->prev->y && aRect->x < mCurRect->prev->x)
378
mCurRect = mCurRect->prev;
380
InsertBefore (aRect, mCurRect);
389
mBoundRect = *mCurRect;
392
mBoundRect.UnionRect (mBoundRect, *mCurRect);
394
// Check if we can go left or up before starting to combine rectangles
395
if ((mCurRect->y == mCurRect->prev->y && mCurRect->height == mCurRect->prev->height &&
396
mCurRect->x == mCurRect->prev->XMost ()) ||
397
(mCurRect->x == mCurRect->prev->x && mCurRect->width == mCurRect->prev->width &&
398
mCurRect->y == mCurRect->prev->YMost ()) )
399
mCurRect = mCurRect->prev;
401
// Try to combine with rectangle on right side
402
while (mCurRect->y == mCurRect->next->y && mCurRect->height == mCurRect->next->height &&
403
mCurRect->XMost () == mCurRect->next->x)
405
mCurRect->width += mCurRect->next->width;
406
delete Remove (mCurRect->next);
409
// Try to combine with rectangle under this one
410
while (mCurRect->x == mCurRect->next->x && mCurRect->width == mCurRect->next->width &&
411
mCurRect->YMost () == mCurRect->next->y)
413
mCurRect->height += mCurRect->next->height;
414
delete Remove (mCurRect->next);
421
nsRegion::RgnRect* nsRegion::Remove (RgnRect* aRect)
423
aRect->prev->next = aRect->next;
424
aRect->next->prev = aRect->prev;
427
if (mCurRect == aRect)
428
mCurRect = (aRect->next != &mRectListHead) ? aRect->next : aRect->prev;
434
// Try to reduce the number of rectangles in complex region by combining with
435
// surrounding ones on right and bottom sides of each rectangle in list.
436
// Update bounding rectangle
438
void nsRegion::Optimize ()
441
mBoundRect.SetRect (0, 0, 0, 0);
444
RgnRect* pRect = mRectListHead.next;
445
PRInt32 xmost = mRectListHead.prev->XMost ();
446
PRInt32 ymost = mRectListHead.prev->YMost ();
447
mBoundRect.x = mRectListHead.next->x;
448
mBoundRect.y = mRectListHead.next->y;
450
while (pRect != &mRectListHead)
452
// Try to combine with rectangle on right side
453
while (pRect->y == pRect->next->y && pRect->height == pRect->next->height &&
454
pRect->XMost () == pRect->next->x)
456
pRect->width += pRect->next->width;
457
delete Remove (pRect->next);
460
// Try to combine with rectangle under this one
461
while (pRect->x == pRect->next->x && pRect->width == pRect->next->width &&
462
pRect->YMost () == pRect->next->y)
464
pRect->height += pRect->next->height;
465
delete Remove (pRect->next);
468
// Determine bound rectangle. Use fact that rectangles are sorted.
469
if (pRect->x < mBoundRect.x) mBoundRect.x = pRect->x;
470
if (pRect->XMost () > xmost) xmost = pRect->XMost ();
471
if (pRect->YMost () > ymost) ymost = pRect->YMost ();
476
mBoundRect.width = xmost - mBoundRect.x;
477
mBoundRect.height = ymost - mBoundRect.y;
482
// Move rectangles starting from 'aStartRect' till end of the list to the destionation region.
483
// Important for temporary objects - instead of copying rectangles with Merge () and then
484
// emptying region in destructor they could be moved to destination region in one step.
486
void nsRegion::MoveInto (nsRegion& aDestRegion, const RgnRect* aStartRect)
488
RgnRect* pRect = const_cast<RgnRect*>(aStartRect);
489
RgnRect* pPrev = pRect->prev;
491
while (pRect != &mRectListHead)
493
RgnRect* next = pRect->next;
494
aDestRegion.InsertInPlace (pRect);
500
pPrev->next = &mRectListHead;
501
mRectListHead.prev = pPrev;
502
mCurRect = mRectListHead.next;
506
// Merge two non-overlapping regions into one.
507
// Automatically optimize region by calling Optimize ()
509
void nsRegion::Merge (const nsRegion& aRgn1, const nsRegion& aRgn2)
511
if (aRgn1.mRectCount == 0) // Region empty. Result is equal to other region
514
if (aRgn2.mRectCount == 0) // Region empty. Result is equal to other region
516
if (aRgn1.mRectCount == 1) // Region is single rectangle. Optimize on fly
518
RgnRect* TmpRect = new RgnRect (*aRgn1.mRectListHead.next);
520
InsertInPlace (TmpRect, PR_TRUE);
522
if (aRgn2.mRectCount == 1) // Region is single rectangle. Optimize on fly
524
RgnRect* TmpRect = new RgnRect (*aRgn2.mRectListHead.next);
526
InsertInPlace (TmpRect, PR_TRUE);
529
const nsRegion* pCopyRegion, *pInsertRegion;
531
// Determine which region contains more rectangles. Copy the larger one
532
if (aRgn1.mRectCount >= aRgn2.mRectCount)
534
pCopyRegion = &aRgn1;
535
pInsertRegion = &aRgn2;
538
pCopyRegion = &aRgn2;
539
pInsertRegion = &aRgn1;
542
if (pInsertRegion == this) // Do merge in-place
543
pInsertRegion = pCopyRegion;
547
const RgnRect* pSrcRect = pInsertRegion->mRectListHead.next;
549
while (pSrcRect != &pInsertRegion->mRectListHead)
551
InsertInPlace (new RgnRect (*pSrcRect));
553
pSrcRect = pSrcRect->next;
561
nsRegion& nsRegion::Copy (const nsRegion& aRegion)
563
if (&aRegion == this)
566
if (aRegion.mRectCount == 0)
570
SetToElements (aRegion.mRectCount);
572
const RgnRect* pSrc = aRegion.mRectListHead.next;
573
RgnRect* pDest = mRectListHead.next;
575
while (pSrc != &aRegion.mRectListHead)
583
mCurRect = mRectListHead.next;
584
mBoundRect = aRegion.mBoundRect;
591
nsRegion& nsRegion::Copy (const nsRect& aRect)
593
if (aRect.IsEmpty ())
598
*mRectListHead.next = static_cast<const RgnRect&>(aRect);
599
mBoundRect = static_cast<const nsRectFast&>(aRect);
606
nsRegion& nsRegion::And (const nsRegion& aRgn1, const nsRegion& aRgn2)
608
if (&aRgn1 == &aRgn2) // And with self
611
if (aRgn1.mRectCount == 0 || aRgn2.mRectCount == 0) // If either region is empty then result is empty
617
if (aRgn1.mRectCount == 1 && aRgn2.mRectCount == 1) // Intersect rectangle with rectangle
619
TmpRect.IntersectRect (*aRgn1.mRectListHead.next, *aRgn2.mRectListHead.next);
623
if (!aRgn1.mBoundRect.Intersects (aRgn2.mBoundRect)) // Regions do not intersect
627
// Region is simple rectangle and it fully overlays other region
628
if (aRgn1.mRectCount == 1 && aRgn1.mBoundRect.Contains (aRgn2.mBoundRect))
631
// Region is simple rectangle and it fully overlays other region
632
if (aRgn2.mRectCount == 1 && aRgn2.mBoundRect.Contains (aRgn1.mBoundRect))
637
nsRegion* pSrcRgn1 = const_cast<nsRegion*>(&aRgn1);
638
nsRegion* pSrcRgn2 = const_cast<nsRegion*>(&aRgn2);
640
if (&aRgn1 == this) // Copy region if it is both source and result
642
TmpRegion.Copy (aRgn1);
643
pSrcRgn1 = &TmpRegion;
646
if (&aRgn2 == this) // Copy region if it is both source and result
648
TmpRegion.Copy (aRgn2);
649
pSrcRgn2 = &TmpRegion;
652
// For outer loop prefer region for which at least one rectangle is below other's bound rectangle
653
if (pSrcRgn2->mRectListHead.prev->y >= pSrcRgn1->mBoundRect.YMost ())
655
nsRegion* Tmp = pSrcRgn1;
662
pSrcRgn2->SaveLinkChain ();
664
pSrcRgn1->mRectListHead.y = PR_INT32_MAX;
665
pSrcRgn2->mRectListHead.y = PR_INT32_MAX;
667
for (RgnRect* pSrcRect1 = pSrcRgn1->mRectListHead.next ;
668
pSrcRect1->y < pSrcRgn2->mBoundRect.YMost () ; pSrcRect1 = pSrcRect1->next)
670
if (pSrcRect1->Intersects (pSrcRgn2->mBoundRect)) // Rectangle intersects region. Process each rectangle
672
RgnRect* pPrev2 = &pSrcRgn2->mRectListHead;
674
for (RgnRect* pSrcRect2 = pSrcRgn2->mRectListHead.next ;
675
pSrcRect2->y < pSrcRect1->YMost () ; pSrcRect2 = pSrcRect2->next)
677
if (pSrcRect2->YMost () <= pSrcRect1->y) // Rect2's bottom is above the top of Rect1.
678
{ // No successive rectangles in Rgn1 can intersect it.
679
pPrev2->next = pSrcRect2->next; // Remove Rect2 from Rgn2's checklist
683
if (pSrcRect1->Contains (*pSrcRect2)) // Rect1 fully overlays Rect2.
684
{ // No any other rectangle in Rgn1 can intersect it.
685
pPrev2->next = pSrcRect2->next; // Remove Rect2 from Rgn2's checklist
686
InsertInPlace (new RgnRect (*pSrcRect2));
691
if (TmpRect.IntersectRect (*pSrcRect1, *pSrcRect2))
692
InsertInPlace (new RgnRect (TmpRect));
699
pSrcRgn2->RestoreLinkChain ();
710
nsRegion& nsRegion::And (const nsRegion& aRegion, const nsRect& aRect)
712
// If either region or rectangle is empty then result is empty
713
if (aRegion.mRectCount == 0 || aRect.IsEmpty ())
715
else // Intersect region with rectangle
717
const nsRectFast& aRectFast = static_cast<const nsRectFast&>(aRect);
720
if (aRegion.mRectCount == 1) // Intersect rectangle with rectangle
722
TmpRect.IntersectRect (*aRegion.mRectListHead.next, aRectFast);
724
} else // Intersect complex region with rectangle
726
if (!aRectFast.Intersects (aRegion.mBoundRect)) // Rectangle does not intersect region
730
if (aRectFast.Contains (aRegion.mBoundRect)) // Rectangle fully overlays region
735
nsRegion* pSrcRegion = const_cast<nsRegion*>(&aRegion);
737
if (&aRegion == this) // Copy region if it is both source and result
739
TmpRegion.Copy (aRegion);
740
pSrcRegion = &TmpRegion;
744
pSrcRegion->mRectListHead.y = PR_INT32_MAX;
746
for (const RgnRect* pSrcRect = pSrcRegion->mRectListHead.next ;
747
pSrcRect->y < aRectFast.YMost () ; pSrcRect = pSrcRect->next)
749
if (TmpRect.IntersectRect (*pSrcRect, aRectFast))
750
InsertInPlace (new RgnRect (TmpRect));
763
nsRegion& nsRegion::Or (const nsRegion& aRgn1, const nsRegion& aRgn2)
765
if (&aRgn1 == &aRgn2) // Or with self
768
if (aRgn1.mRectCount == 0) // Region empty. Result is equal to other region
771
if (aRgn2.mRectCount == 0) // Region empty. Result is equal to other region
775
if (!aRgn1.mBoundRect.Intersects (aRgn2.mBoundRect)) // Regions do not intersect
776
Merge (aRgn1, aRgn2);
779
// Region is simple rectangle and it fully overlays other region
780
if (aRgn1.mRectCount == 1 && aRgn1.mBoundRect.Contains (aRgn2.mBoundRect))
783
// Region is simple rectangle and it fully overlays other region
784
if (aRgn2.mRectCount == 1 && aRgn2.mBoundRect.Contains (aRgn1.mBoundRect))
789
aRgn1.SubRegion (aRgn2, TmpRegion); // Get only parts of region which not overlap the other region
791
TmpRegion.MoveInto (*this);
801
nsRegion& nsRegion::Or (const nsRegion& aRegion, const nsRect& aRect)
803
if (aRegion.mRectCount == 0) // Region empty. Result is equal to rectangle
806
if (aRect.IsEmpty ()) // Rectangle is empty. Result is equal to region
810
const nsRectFast& aRectFast = static_cast<const nsRectFast&>(aRect);
812
if (!aRectFast.Intersects (aRegion.mBoundRect)) // Rectangle does not intersect region
815
InsertInPlace (new RgnRect (aRectFast), PR_TRUE);
818
// Region is simple rectangle and it fully overlays rectangle
819
if (aRegion.mRectCount == 1 && aRegion.mBoundRect.Contains (aRectFast))
822
if (aRectFast.Contains (aRegion.mBoundRect)) // Rectangle fully overlays region
826
aRegion.SubRect (aRectFast, *this); // Exclude from region parts that overlap the rectangle
827
InsertInPlace (new RgnRect (aRectFast));
837
nsRegion& nsRegion::Xor (const nsRegion& aRgn1, const nsRegion& aRgn2)
839
if (&aRgn1 == &aRgn2) // Xor with self
842
if (aRgn1.mRectCount == 0) // Region empty. Result is equal to other region
845
if (aRgn2.mRectCount == 0) // Region empty. Result is equal to other region
849
if (!aRgn1.mBoundRect.Intersects (aRgn2.mBoundRect)) // Regions do not intersect
850
Merge (aRgn1, aRgn2);
853
// Region is simple rectangle and it fully overlays other region
854
if (aRgn1.mRectCount == 1 && aRgn1.mBoundRect.Contains (aRgn2.mBoundRect))
856
aRgn1.SubRegion (aRgn2, *this);
859
// Region is simple rectangle and it fully overlays other region
860
if (aRgn2.mRectCount == 1 && aRgn2.mBoundRect.Contains (aRgn1.mBoundRect))
862
aRgn2.SubRegion (aRgn1, *this);
867
aRgn1.SubRegion (aRgn2, TmpRegion);
868
aRgn2.SubRegion (aRgn1, *this);
869
TmpRegion.MoveInto (*this);
879
nsRegion& nsRegion::Xor (const nsRegion& aRegion, const nsRect& aRect)
881
if (aRegion.mRectCount == 0) // Region empty. Result is equal to rectangle
884
if (aRect.IsEmpty ()) // Rectangle is empty. Result is equal to region
888
const nsRectFast& aRectFast = static_cast<const nsRectFast&>(aRect);
890
if (!aRectFast.Intersects (aRegion.mBoundRect)) // Rectangle does not intersect region
893
InsertInPlace (new RgnRect (aRectFast), PR_TRUE);
896
// Region is simple rectangle and it fully overlays rectangle
897
if (aRegion.mRectCount == 1 && aRegion.mBoundRect.Contains (aRectFast))
899
aRegion.SubRect (aRectFast, *this);
902
if (aRectFast.Contains (aRegion.mBoundRect)) // Rectangle fully overlays region
905
TmpRegion.Copy (aRectFast);
906
TmpRegion.SubRegion (aRegion, *this);
911
TmpRegion.Copy (aRectFast);
912
TmpRegion.SubRegion (aRegion, TmpRegion);
913
aRegion.SubRect (aRectFast, *this);
914
TmpRegion.MoveInto (*this);
924
nsRegion& nsRegion::Sub (const nsRegion& aRgn1, const nsRegion& aRgn2)
926
if (&aRgn1 == &aRgn2) // Sub from self
929
if (aRgn1.mRectCount == 0) // If source is empty then result is empty, too
932
if (aRgn2.mRectCount == 0) // Nothing to subtract
936
if (!aRgn1.mBoundRect.Intersects (aRgn2.mBoundRect)) // Regions do not intersect
940
aRgn1.SubRegion (aRgn2, *this);
949
nsRegion& nsRegion::Sub (const nsRegion& aRegion, const nsRect& aRect)
951
if (aRegion.mRectCount == 0) // If source is empty then result is empty, too
954
if (aRect.IsEmpty ()) // Nothing to subtract
958
const nsRectFast& aRectFast = static_cast<const nsRectFast&>(aRect);
960
if (!aRectFast.Intersects (aRegion.mBoundRect)) // Rectangle does not intersect region
964
if (aRectFast.Contains (aRegion.mBoundRect)) // Rectangle fully overlays region
968
aRegion.SubRect (aRectFast, *this);
977
PRBool nsRegion::Contains (const nsRect& aRect) const
984
return mBoundRect.Contains (aRect);
987
tmpRgn.Sub(aRect, *this);
988
return tmpRgn.IsEmpty();
991
PRBool nsRegion::Intersects (const nsRect& aRect) const
993
if (aRect.IsEmpty() || IsEmpty())
996
const RgnRect* r = mRectListHead.next;
997
while (r != &mRectListHead)
999
if (r->Intersects(aRect))
1006
// Subtract region from current region.
1007
// Both regions are non-empty and they intersect each other.
1008
// Result could be empty region if aRgn2 is rectangle that fully overlays aRgn1.
1009
// Optimize () is not called on exit (bound rectangle is not updated).
1011
void nsRegion::SubRegion (const nsRegion& aRegion, nsRegion& aResult) const
1013
if (aRegion.mRectCount == 1) // Subtract simple rectangle
1015
if (aRegion.mBoundRect.Contains (mBoundRect))
1016
aResult.SetEmpty ();
1018
SubRect (*aRegion.mRectListHead.next, aResult);
1021
nsRegion TmpRegion, CompletedRegion;
1022
const nsRegion* pSubRgn = &aRegion;
1024
if (&aResult == &aRegion) // Copy region if it is both source and result
1026
TmpRegion.Copy (aRegion);
1027
pSubRgn = &TmpRegion;
1030
const RgnRect* pSubRect = pSubRgn->mRectListHead.next;
1032
SubRect (*pSubRect, aResult, CompletedRegion);
1033
pSubRect = pSubRect->next;
1035
while (pSubRect != &pSubRgn->mRectListHead)
1037
aResult.SubRect (*pSubRect, aResult, CompletedRegion);
1038
pSubRect = pSubRect->next;
1041
CompletedRegion.MoveInto (aResult);
1046
// Subtract rectangle from current region.
1047
// Both region and rectangle are non-empty and they intersect each other.
1048
// Result could be empty region if aRect fully overlays aRegion.
1049
// Could be called repeatedly with 'this' as input and result - bound rectangle is not known.
1050
// Optimize () is not called on exit (bound rectangle is not updated).
1052
// aCompleted is filled with rectangles which are already checked and could be safely
1053
// removed from further examination in case aRect rectangles come from ordered list.
1054
// aCompleted is not automatically emptied. aCompleted and aResult could be the same region.
1056
void nsRegion::SubRect (const nsRectFast& aRect, nsRegion& aResult, nsRegion& aCompleted) const
1059
const nsRegion* pSrcRegion = this;
1061
if (&aResult == this) // Copy region if it is both source and result
1063
TmpRegion.Copy (*this);
1064
pSrcRegion = &TmpRegion;
1067
aResult.SetToElements (0);
1069
(const_cast<nsRegion*>(pSrcRegion))->mRectListHead.y = PR_INT32_MAX;
1070
const RgnRect* pSrcRect = pSrcRegion->mRectListHead.next;
1072
for ( ; pSrcRect->y < aRect.YMost () ; pSrcRect = pSrcRect->next)
1076
// If bottom of current rectangle is above the top of aRect then this rectangle
1077
// could be moved to aCompleted region. Successive aRect rectangles from ordered
1078
// list do not have to check this rectangle again.
1079
if (pSrcRect->YMost () <= aRect.y)
1081
aCompleted.InsertInPlace (new RgnRect (*pSrcRect));
1085
if (!TmpRect.IntersectRect (*pSrcRect, aRect))
1086
aResult.InsertInPlace (new RgnRect (*pSrcRect));
1089
// Rectangle A. Subtract from this rectangle B
1090
const nscoord ax = pSrcRect->x;
1091
const nscoord axm = pSrcRect->XMost ();
1092
const nscoord aw = pSrcRect->width;
1093
const nscoord ay = pSrcRect->y;
1094
const nscoord aym = pSrcRect->YMost ();
1095
const nscoord ah = pSrcRect->height;
1096
// Rectangle B. Subtract this from rectangle A
1097
const nscoord bx = aRect.x;
1098
const nscoord bxm = aRect.XMost ();
1099
const nscoord by = aRect.y;
1100
const nscoord bym = aRect.YMost ();
1101
// Rectangle I. Area where rectangles A and B intersect
1102
const nscoord ix = TmpRect.x;
1103
const nscoord ixm = TmpRect.XMost ();
1104
const nscoord iy = TmpRect.y;
1105
const nscoord iym = TmpRect.YMost ();
1106
const nscoord ih = TmpRect.height;
1108
// There are 16 combinations how rectangles could intersect
1110
if (bx <= ax && by <= ay)
1112
if (bxm < axm && bym < aym) // 1.
1114
aResult.InsertInPlace (new RgnRect (ixm, ay, axm - ixm, ih));
1115
aResult.InsertInPlace (new RgnRect (ax, iym, aw, aym - iym));
1117
if (bxm >= axm && bym < aym) // 2.
1119
aResult.InsertInPlace (new RgnRect (ax, iym, aw, aym - iym));
1121
if (bxm < axm && bym >= aym) // 3.
1123
aResult.InsertInPlace (new RgnRect (ixm, ay, axm - ixm, ah));
1125
if (*pSrcRect == aRect) // 4. subset
1126
{ // Current rectangle is equal to aRect
1127
pSrcRect = pSrcRect->next; // don't add this one to the result, it's removed
1128
break; // No any other rectangle in region can intersect it
1131
if (bx > ax && by <= ay)
1133
if (bxm < axm && bym < aym) // 5.
1135
aResult.InsertInPlace (new RgnRect (ax, ay, ix - ax, ih));
1136
aResult.InsertInPlace (new RgnRect (ixm, ay, axm - ixm, ih));
1137
aResult.InsertInPlace (new RgnRect (ax, iym, aw, aym - iym));
1139
if (bxm >= axm && bym < aym) // 6.
1141
aResult.InsertInPlace (new RgnRect (ax, ay, ix - ax, ih));
1142
aResult.InsertInPlace (new RgnRect (ax, iym, aw, aym - iym));
1144
if (bxm < axm && bym >= aym) // 7.
1146
aResult.InsertInPlace (new RgnRect (ax, ay, ix - ax, ah));
1147
aResult.InsertInPlace (new RgnRect (ixm, ay, axm - ixm, ah));
1149
if (bxm >= axm && bym >= aym) // 8.
1151
aResult.InsertInPlace (new RgnRect (ax, ay, ix - ax, ah));
1154
if (bx <= ax && by > ay)
1156
if (bxm < axm && bym < aym) // 9.
1158
aResult.InsertInPlace (new RgnRect (ax, ay, aw, iy - ay));
1159
aResult.InsertInPlace (new RgnRect (ixm, iy, axm - ixm, ih));
1160
aResult.InsertInPlace (new RgnRect (ax, iym, aw, aym - iym));
1162
if (bxm >= axm && bym < aym) // 10.
1164
aResult.InsertInPlace (new RgnRect (ax, ay, aw, iy - ay));
1165
aResult.InsertInPlace (new RgnRect (ax, iym, aw, aym - iym));
1167
if (bxm < axm && bym >= aym) // 11.
1169
aResult.InsertInPlace (new RgnRect (ax, ay, aw, iy - ay));
1170
aResult.InsertInPlace (new RgnRect (ixm, iy, axm - ixm, ih));
1172
if (bxm >= axm && bym >= aym) // 12.
1174
aResult.InsertInPlace (new RgnRect (ax, ay, aw, iy - ay));
1177
if (bx > ax && by > ay)
1179
if (bxm < axm && bym < aym) // 13.
1181
aResult.InsertInPlace (new RgnRect (ax, ay, aw, iy - ay));
1182
aResult.InsertInPlace (new RgnRect (ax, iy, ix - ax, ih));
1183
aResult.InsertInPlace (new RgnRect (ixm, iy, axm - ixm, ih));
1184
aResult.InsertInPlace (new RgnRect (ax, iym, aw, aym - iym));
1186
// Current rectangle fully overlays aRect. No any other rectangle can intersect it.
1187
pSrcRect = pSrcRect->next; // don't add this one to the result, it's removed
1190
if (bxm >= axm && bym < aym) // 14.
1192
aResult.InsertInPlace (new RgnRect (ax, ay, aw, iy - ay));
1193
aResult.InsertInPlace (new RgnRect (ax, iy, ix - ax, ih));
1194
aResult.InsertInPlace (new RgnRect (ax, iym, aw, aym - iym));
1196
if (bxm < axm && bym >= aym) // 15.
1198
aResult.InsertInPlace (new RgnRect (ax, ay, aw, iy - ay));
1199
aResult.InsertInPlace (new RgnRect (ax, iy, ix - ax, ih));
1200
aResult.InsertInPlace (new RgnRect (ixm, iy, axm - ixm, ih));
1202
if (bxm >= axm && bym >= aym) // 16.
1204
aResult.InsertInPlace (new RgnRect (ax, ay, aw, iy - ay));
1205
aResult.InsertInPlace (new RgnRect (ax, iy, ix - ax, ih));
1211
// Just copy remaining rectangles in region which are below aRect and can't intersect it.
1212
// If rectangles are in temporary region then they could be moved.
1213
if (pSrcRegion == &TmpRegion)
1214
TmpRegion.MoveInto (aResult, pSrcRect);
1217
while (pSrcRect != &pSrcRegion->mRectListHead)
1219
aResult.InsertInPlace (new RgnRect (*pSrcRect));
1220
pSrcRect = pSrcRect->next;
1226
PRBool nsRegion::IsEqual (const nsRegion& aRegion) const
1228
if (mRectCount == 0)
1229
return (aRegion.mRectCount == 0) ? PR_TRUE : PR_FALSE;
1231
if (aRegion.mRectCount == 0)
1232
return (mRectCount == 0) ? PR_TRUE : PR_FALSE;
1234
if (mRectCount == 1 && aRegion.mRectCount == 1) // Both regions are simple rectangles
1235
return (*mRectListHead.next == *aRegion.mRectListHead.next);
1236
else // At least one is complex region.
1238
if (mBoundRect != aRegion.mBoundRect) // If regions are equal then bounding rectangles should match
1243
TmpRegion.Xor (*this, aRegion); // Get difference between two regions
1245
return (TmpRegion.mRectCount == 0);
1251
void nsRegion::MoveBy (nsPoint aPt)
1255
RgnRect* pRect = mRectListHead.next;
1257
while (pRect != &mRectListHead)
1259
pRect->MoveBy (aPt.x, aPt.y);
1260
pRect = pRect->next;
1263
mBoundRect.MoveBy (aPt.x, aPt.y);
1267
void nsRegion::SimplifyOutward (PRUint32 aMaxRects)
1269
NS_ASSERTION(aMaxRects >= 1, "Invalid max rect count");
1271
if (mRectCount <= aMaxRects)
1274
*this = GetBounds();
1277
void nsRegion::SimplifyInward (PRUint32 aMaxRects)
1279
NS_ASSERTION(aMaxRects >= 1, "Invalid max rect count");
1281
if (mRectCount <= aMaxRects)
1287
void nsRegion::SimpleSubtract (const nsRect& aRect)
1289
if (aRect.IsEmpty())
1292
// protect against aRect being one of our own rectangles
1293
nsRect param = aRect;
1294
RgnRect* r = mRectListHead.next;
1295
while (r != &mRectListHead)
1297
RgnRect* next = r->next;
1298
if (param.Contains(*r)) {
1307
void nsRegion::SimpleSubtract (const nsRegion& aRegion)
1309
if (aRegion.IsEmpty())
1312
if (&aRegion == this) {
1317
const RgnRect* r = aRegion.mRectListHead.next;
1318
while (r != &aRegion.mRectListHead)