1 /* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6 #include "nsISupportsImpl.h"
8 #include "mozilla/ThreadLocal.h"
9 #include "nsPrintfCString.h"
13 * The SENTINEL values below guaranties that a < or >
14 * comparison with it will be false for all values of the
15 * underlying nscoord type. E.g. this is always false:
16 * aCoord > NS_COORD_GREATER_SENTINEL
17 * Setting the mRectListHead dummy rectangle to these values
18 * allows us to loop without checking for the list end.
20 #ifdef NS_COORD_IS_FLOAT
21 #define NS_COORD_LESS_SENTINEL nscoord_MIN
22 #define NS_COORD_GREATER_SENTINEL nscoord_MAX
24 #define NS_COORD_LESS_SENTINEL INT32_MIN
25 #define NS_COORD_GREATER_SENTINEL INT32_MAX
28 // Fast inline analogues of nsRect methods for nsRegion::nsRectFast.
29 // Check for emptiness is not required - it is guaranteed by caller.
31 inline bool nsRegion::nsRectFast::Contains (const nsRect
& aRect
) const
33 return (bool) ((aRect
.x
>= x
) && (aRect
.y
>= y
) &&
34 (aRect
.XMost () <= XMost ()) && (aRect
.YMost () <= YMost ()));
37 inline bool nsRegion::nsRectFast::Intersects (const nsRect
& aRect
) const
39 return (bool) ((x
< aRect
.XMost ()) && (y
< aRect
.YMost ()) &&
40 (aRect
.x
< XMost ()) && (aRect
.y
< YMost ()));
43 inline bool nsRegion::nsRectFast::IntersectRect (const nsRect
& aRect1
, const nsRect
& aRect2
)
45 const nscoord xmost
= std::min (aRect1
.XMost (), aRect2
.XMost ());
46 x
= std::max (aRect1
.x
, aRect2
.x
);
48 if (width
<= 0) return false;
50 const nscoord ymost
= std::min (aRect1
.YMost (), aRect2
.YMost ());
51 y
= std::max (aRect1
.y
, aRect2
.y
);
53 if (height
<= 0) return false;
58 inline void nsRegion::nsRectFast::UnionRect (const nsRect
& aRect1
, const nsRect
& aRect2
)
60 const nscoord xmost
= std::max (aRect1
.XMost (), aRect2
.XMost ());
61 const nscoord ymost
= std::max (aRect1
.YMost (), aRect2
.YMost ());
62 x
= std::min(aRect1
.x
, aRect2
.x
);
63 y
= std::min(aRect1
.y
, aRect2
.y
);
70 // Custom memory allocator for nsRegion::RgnRect structures.
71 // Entries are allocated from global memory pool.
72 // Memory pool can grow in size, but it can't shrink.
74 #define INIT_MEM_CHUNK_ENTRIES 100
75 #define INCR_MEM_CHUNK_ENTRIES 100
77 class RgnRectMemoryAllocator
79 nsRegion::RgnRect
* mFreeListHead
;
80 uint32_t mFreeEntries
;
85 void InitLock () { NS_ASSERT_OWNINGTHREAD (RgnRectMemoryAllocator
); }
86 void DestroyLock () { NS_ASSERT_OWNINGTHREAD (RgnRectMemoryAllocator
); }
87 void Lock () { NS_ASSERT_OWNINGTHREAD (RgnRectMemoryAllocator
); }
88 void Unlock () { NS_ASSERT_OWNINGTHREAD (RgnRectMemoryAllocator
); }
91 void DestroyLock () { }
96 void* AllocChunk (uint32_t aEntries
, void* aNextChunk
, nsRegion::RgnRect
* aTailDest
)
98 uint8_t* pBuf
= new uint8_t [aEntries
* sizeof (nsRegion::RgnRect
) + sizeof (void*)];
99 *reinterpret_cast<void**>(pBuf
) = aNextChunk
;
100 nsRegion::RgnRect
* pRect
= reinterpret_cast<nsRegion::RgnRect
*>(pBuf
+ sizeof (void*));
102 for (uint32_t cnt
= 0 ; cnt
< aEntries
- 1 ; cnt
++)
103 pRect
[cnt
].next
= &pRect
[cnt
+ 1];
105 pRect
[aEntries
- 1].next
= aTailDest
;
110 void FreeChunk (void* aChunk
) { delete [] (uint8_t *) aChunk
; }
111 void* NextChunk (void* aThisChunk
) const { return *static_cast<void**>(aThisChunk
); }
113 nsRegion::RgnRect
* ChunkHead (void* aThisChunk
) const
114 { return reinterpret_cast<nsRegion::RgnRect
*>(static_cast<uint8_t*>(aThisChunk
) + sizeof (void*)); }
117 RgnRectMemoryAllocator (uint32_t aNumOfEntries
);
118 ~RgnRectMemoryAllocator ();
120 nsRegion::RgnRect
* Alloc ();
121 void Free (nsRegion::RgnRect
* aRect
);
125 RgnRectMemoryAllocator::RgnRectMemoryAllocator (uint32_t aNumOfEntries
)
128 mChunkListHead
= AllocChunk (aNumOfEntries
, nullptr, nullptr);
129 mFreeEntries
= aNumOfEntries
;
130 mFreeListHead
= ChunkHead (mChunkListHead
);
133 RgnRectMemoryAllocator::~RgnRectMemoryAllocator ()
135 while (mChunkListHead
)
137 void* tmp
= mChunkListHead
;
138 mChunkListHead
= NextChunk (mChunkListHead
);
144 * As a static object this class outlives any library which would implement
145 * locking. So we intentionally leak the 'lock'.
147 * Currently RgnRectMemoryAllocator is only used from the primary thread,
148 * so we aren't using a lock which means that there is no lock to leak.
149 * If we ever switch to multiple GUI threads (e.g. one per window),
150 * we'd probably use one allocator per window-thread to avoid the
151 * locking overhead and just require consumers not to pass regions
152 * across threads/windows, which would be a reasonable restriction
153 * because they wouldn't be useful outside their window.
159 nsRegion::RgnRect
* RgnRectMemoryAllocator::Alloc ()
163 if (mFreeEntries
== 0)
165 mChunkListHead
= AllocChunk (INCR_MEM_CHUNK_ENTRIES
, mChunkListHead
, mFreeListHead
);
166 mFreeEntries
= INCR_MEM_CHUNK_ENTRIES
;
167 mFreeListHead
= ChunkHead (mChunkListHead
);
170 nsRegion::RgnRect
* tmp
= mFreeListHead
;
171 mFreeListHead
= mFreeListHead
->next
;
178 void RgnRectMemoryAllocator::Free (nsRegion::RgnRect
* aRect
)
182 aRect
->next
= mFreeListHead
;
183 mFreeListHead
= aRect
;
188 // Global pool for nsRegion::RgnRect allocation
189 mozilla::ThreadLocal
<RgnRectMemoryAllocator
*> gRectPoolTlsIndex
;
191 void RgnRectMemoryAllocatorDTOR(void *priv
)
193 RgnRectMemoryAllocator
* allocator
= gRectPoolTlsIndex
.get();
197 nsresult
nsRegion::InitStatic()
199 if (gRectPoolTlsIndex
.initialized()) {
200 // It's ok to call InitStatic if we called ShutdownStatic first
201 MOZ_ASSERT(gRectPoolTlsIndex
.get() == nullptr);
205 return gRectPoolTlsIndex
.init() ? NS_OK
: NS_ERROR_FAILURE
;
208 void nsRegion::ShutdownStatic()
210 RgnRectMemoryAllocator
* allocator
= gRectPoolTlsIndex
.get();
216 gRectPoolTlsIndex
.set(nullptr);
219 void* nsRegion::RgnRect::operator new (size_t) CPP_THROW_NEW
221 RgnRectMemoryAllocator
* allocator
= gRectPoolTlsIndex
.get();
223 allocator
= new RgnRectMemoryAllocator(INIT_MEM_CHUNK_ENTRIES
);
224 gRectPoolTlsIndex
.set(allocator
);
226 return allocator
->Alloc ();
229 void nsRegion::RgnRect::operator delete (void* aRect
, size_t)
231 RgnRectMemoryAllocator
* allocator
= gRectPoolTlsIndex
.get();
233 NS_ERROR("Invalid nsRegion::RgnRect delete");
236 allocator
->Free (static_cast<RgnRect
*>(aRect
));
241 void nsRegion::Init()
243 mRectListHead
.prev
= mRectListHead
.next
= &mRectListHead
;
244 mCurRect
= &mRectListHead
;
246 mBoundRect
.SetRect (0, 0, 0, 0);
249 inline void nsRegion::InsertBefore (RgnRect
* aNewRect
, RgnRect
* aRelativeRect
)
251 aNewRect
->prev
= aRelativeRect
->prev
;
252 aNewRect
->next
= aRelativeRect
;
253 aRelativeRect
->prev
->next
= aNewRect
;
254 aRelativeRect
->prev
= aNewRect
;
259 inline void nsRegion::InsertAfter (RgnRect
* aNewRect
, RgnRect
* aRelativeRect
)
261 aNewRect
->prev
= aRelativeRect
;
262 aNewRect
->next
= aRelativeRect
->next
;
263 aRelativeRect
->next
->prev
= aNewRect
;
264 aRelativeRect
->next
= aNewRect
;
270 // Adjust the number of rectangles in region.
271 // Content of rectangles should be changed by caller.
273 void nsRegion::SetToElements (uint32_t aCount
)
275 if (mRectCount
< aCount
) // Add missing rectangles
277 uint32_t InsertCount
= aCount
- mRectCount
;
279 RgnRect
* pPrev
= &mRectListHead
;
280 RgnRect
* pNext
= mRectListHead
.next
;
282 while (InsertCount
--)
284 mCurRect
= new RgnRect
;
285 mCurRect
->prev
= pPrev
;
286 pPrev
->next
= mCurRect
;
293 if (mRectCount
> aCount
) // Remove unnecessary rectangles
295 uint32_t RemoveCount
= mRectCount
- aCount
;
297 mCurRect
= mRectListHead
.next
;
299 while (RemoveCount
--)
301 RgnRect
* tmp
= mCurRect
;
302 mCurRect
= mCurRect
->next
;
306 mRectListHead
.next
= mCurRect
;
307 mCurRect
->prev
= &mRectListHead
;
312 // Save the entire chain of linked elements in 'prev' field of the RgnRect structure.
313 // After that forward-only iterations using 'next' field could still be used.
314 // Some elements from forward-only chain could be temporarily removed to optimize inner loops.
315 // The original double linked state could be restored by call to RestoreLinkChain ().
316 // Both functions despite size can be inline because they are called only from one function.
318 inline void nsRegion::SaveLinkChain ()
320 RgnRect
* pRect
= &mRectListHead
;
324 pRect
->prev
= pRect
->next
;
326 } while (pRect
!= &mRectListHead
);
330 inline void nsRegion::RestoreLinkChain ()
332 RgnRect
* pPrev
= &mRectListHead
;
333 RgnRect
* pRect
= mRectListHead
.next
= mRectListHead
.prev
;
335 while (pRect
!= &mRectListHead
)
337 pRect
->next
= pRect
->prev
;
343 mRectListHead
.prev
= pPrev
;
347 // Insert node in right place of sorted list
348 // If necessary then bounding rectangle could be updated and rectangle combined
349 // with neighbour rectangles. This is usually done in Optimize ()
351 void nsRegion::InsertInPlace (RgnRect
* aRect
, bool aOptimizeOnFly
)
354 InsertAfter (aRect
, &mRectListHead
);
357 if (aRect
->y
> mCurRect
->y
)
359 mRectListHead
.y
= NS_COORD_GREATER_SENTINEL
;
360 while (aRect
->y
> mCurRect
->next
->y
)
361 mCurRect
= mCurRect
->next
;
363 mRectListHead
.x
= NS_COORD_GREATER_SENTINEL
;
364 while (aRect
->y
== mCurRect
->next
->y
&& aRect
->x
> mCurRect
->next
->x
)
365 mCurRect
= mCurRect
->next
;
367 InsertAfter (aRect
, mCurRect
);
369 if (aRect
->y
< mCurRect
->y
)
371 mRectListHead
.y
= NS_COORD_LESS_SENTINEL
;
372 while (aRect
->y
< mCurRect
->prev
->y
)
373 mCurRect
= mCurRect
->prev
;
375 mRectListHead
.x
= NS_COORD_LESS_SENTINEL
;
376 while (aRect
->y
== mCurRect
->prev
->y
&& aRect
->x
< mCurRect
->prev
->x
)
377 mCurRect
= mCurRect
->prev
;
379 InsertBefore (aRect
, mCurRect
);
382 if (aRect
->x
> mCurRect
->x
)
384 mRectListHead
.x
= NS_COORD_GREATER_SENTINEL
;
385 while (aRect
->y
== mCurRect
->next
->y
&& aRect
->x
> mCurRect
->next
->x
)
386 mCurRect
= mCurRect
->next
;
388 InsertAfter (aRect
, mCurRect
);
391 mRectListHead
.x
= NS_COORD_LESS_SENTINEL
;
392 while (aRect
->y
== mCurRect
->prev
->y
&& aRect
->x
< mCurRect
->prev
->x
)
393 mCurRect
= mCurRect
->prev
;
395 InsertBefore (aRect
, mCurRect
);
404 mBoundRect
= *mCurRect
;
407 mBoundRect
.UnionRect (mBoundRect
, *mCurRect
);
409 // Check if we can go left or up before starting to combine rectangles
410 if ((mCurRect
->y
== mCurRect
->prev
->y
&& mCurRect
->height
== mCurRect
->prev
->height
&&
411 mCurRect
->x
== mCurRect
->prev
->XMost ()) ||
412 (mCurRect
->x
== mCurRect
->prev
->x
&& mCurRect
->width
== mCurRect
->prev
->width
&&
413 mCurRect
->y
== mCurRect
->prev
->YMost ()) )
414 mCurRect
= mCurRect
->prev
;
416 // Try to combine with rectangle on right side
417 while (mCurRect
->y
== mCurRect
->next
->y
&& mCurRect
->height
== mCurRect
->next
->height
&&
418 mCurRect
->XMost () == mCurRect
->next
->x
)
420 mCurRect
->width
+= mCurRect
->next
->width
;
421 delete Remove (mCurRect
->next
);
424 // Try to combine with rectangle under this one
425 while (mCurRect
->x
== mCurRect
->next
->x
&& mCurRect
->width
== mCurRect
->next
->width
&&
426 mCurRect
->YMost () == mCurRect
->next
->y
)
428 mCurRect
->height
+= mCurRect
->next
->height
;
429 delete Remove (mCurRect
->next
);
436 nsRegion::RgnRect
* nsRegion::Remove (RgnRect
* aRect
)
438 aRect
->prev
->next
= aRect
->next
;
439 aRect
->next
->prev
= aRect
->prev
;
442 if (mCurRect
== aRect
)
443 mCurRect
= (aRect
->next
!= &mRectListHead
) ? aRect
->next
: aRect
->prev
;
449 // Try to reduce the number of rectangles in complex region by combining with
450 // surrounding ones on right and bottom sides of each rectangle in list.
451 // Update bounding rectangle
453 void nsRegion::Optimize ()
456 mBoundRect
.SetRect (0, 0, 0, 0);
459 RgnRect
* pRect
= mRectListHead
.next
;
460 int32_t xmost
= mRectListHead
.prev
->XMost ();
461 int32_t ymost
= mRectListHead
.prev
->YMost ();
462 mBoundRect
.x
= mRectListHead
.next
->x
;
463 mBoundRect
.y
= mRectListHead
.next
->y
;
465 while (pRect
!= &mRectListHead
)
467 // Try to combine with rectangle on right side
468 while (pRect
->y
== pRect
->next
->y
&& pRect
->height
== pRect
->next
->height
&&
469 pRect
->XMost () == pRect
->next
->x
)
471 pRect
->width
+= pRect
->next
->width
;
472 delete Remove (pRect
->next
);
475 // Try to combine with rectangle under this one
476 while (pRect
->x
== pRect
->next
->x
&& pRect
->width
== pRect
->next
->width
&&
477 pRect
->YMost () == pRect
->next
->y
)
479 pRect
->height
+= pRect
->next
->height
;
480 delete Remove (pRect
->next
);
483 // Determine bound rectangle. Use fact that rectangles are sorted.
484 if (pRect
->x
< mBoundRect
.x
) mBoundRect
.x
= pRect
->x
;
485 if (pRect
->XMost () > xmost
) xmost
= pRect
->XMost ();
486 if (pRect
->YMost () > ymost
) ymost
= pRect
->YMost ();
491 mBoundRect
.width
= xmost
- mBoundRect
.x
;
492 mBoundRect
.height
= ymost
- mBoundRect
.y
;
497 // Move rectangles starting from 'aStartRect' till end of the list to the destionation region.
498 // Important for temporary objects - instead of copying rectangles with Merge () and then
499 // emptying region in destructor they could be moved to destination region in one step.
501 void nsRegion::MoveInto (nsRegion
& aDestRegion
, const RgnRect
* aStartRect
)
503 RgnRect
* pRect
= const_cast<RgnRect
*>(aStartRect
);
504 RgnRect
* pPrev
= pRect
->prev
;
506 while (pRect
!= &mRectListHead
)
508 RgnRect
* next
= pRect
->next
;
509 aDestRegion
.InsertInPlace (pRect
);
515 pPrev
->next
= &mRectListHead
;
516 mRectListHead
.prev
= pPrev
;
517 mCurRect
= mRectListHead
.next
;
521 // Merge two non-overlapping regions into one.
522 // Automatically optimize region by calling Optimize ()
524 void nsRegion::Merge (const nsRegion
& aRgn1
, const nsRegion
& aRgn2
)
526 if (aRgn1
.mRectCount
== 0) // Region empty. Result is equal to other region
529 if (aRgn2
.mRectCount
== 0) // Region empty. Result is equal to other region
531 if (aRgn1
.mRectCount
== 1) // Region is single rectangle. Optimize on fly
533 RgnRect
* TmpRect
= new RgnRect (*aRgn1
.mRectListHead
.next
);
535 InsertInPlace (TmpRect
, true);
537 if (aRgn2
.mRectCount
== 1) // Region is single rectangle. Optimize on fly
539 RgnRect
* TmpRect
= new RgnRect (*aRgn2
.mRectListHead
.next
);
541 InsertInPlace (TmpRect
, true);
544 const nsRegion
* pCopyRegion
, *pInsertRegion
;
546 // Determine which region contains more rectangles. Copy the larger one
547 if (aRgn1
.mRectCount
>= aRgn2
.mRectCount
)
549 pCopyRegion
= &aRgn1
;
550 pInsertRegion
= &aRgn2
;
553 pCopyRegion
= &aRgn2
;
554 pInsertRegion
= &aRgn1
;
557 if (pInsertRegion
== this) // Do merge in-place
558 pInsertRegion
= pCopyRegion
;
562 const RgnRect
* pSrcRect
= pInsertRegion
->mRectListHead
.next
;
564 while (pSrcRect
!= &pInsertRegion
->mRectListHead
)
566 InsertInPlace (new RgnRect (*pSrcRect
));
568 pSrcRect
= pSrcRect
->next
;
576 nsRegion
& nsRegion::Copy (const nsRegion
& aRegion
)
578 if (&aRegion
== this)
581 if (aRegion
.mRectCount
== 0)
585 SetToElements (aRegion
.mRectCount
);
587 const RgnRect
* pSrc
= aRegion
.mRectListHead
.next
;
588 RgnRect
* pDest
= mRectListHead
.next
;
590 while (pSrc
!= &aRegion
.mRectListHead
)
598 mCurRect
= mRectListHead
.next
;
599 mBoundRect
= aRegion
.mBoundRect
;
606 nsRegion
& nsRegion::Copy (const nsRect
& aRect
)
608 if (aRect
.IsEmpty ())
613 *mRectListHead
.next
= static_cast<const RgnRect
&>(aRect
);
614 mBoundRect
= static_cast<const nsRectFast
&>(aRect
);
621 nsRegion
& nsRegion::And (const nsRegion
& aRgn1
, const nsRegion
& aRgn2
)
623 if (&aRgn1
== &aRgn2
) // And with self
626 if (aRgn1
.mRectCount
== 0 || aRgn2
.mRectCount
== 0) // If either region is empty then result is empty
632 if (aRgn1
.mRectCount
== 1 && aRgn2
.mRectCount
== 1) // Intersect rectangle with rectangle
634 TmpRect
.IntersectRect (*aRgn1
.mRectListHead
.next
, *aRgn2
.mRectListHead
.next
);
638 if (!aRgn1
.mBoundRect
.Intersects (aRgn2
.mBoundRect
)) // Regions do not intersect
642 // Region is simple rectangle and it fully overlays other region
643 if (aRgn1
.mRectCount
== 1 && aRgn1
.mBoundRect
.Contains (aRgn2
.mBoundRect
))
646 // Region is simple rectangle and it fully overlays other region
647 if (aRgn2
.mRectCount
== 1 && aRgn2
.mBoundRect
.Contains (aRgn1
.mBoundRect
))
652 nsRegion
* pSrcRgn1
= const_cast<nsRegion
*>(&aRgn1
);
653 nsRegion
* pSrcRgn2
= const_cast<nsRegion
*>(&aRgn2
);
655 if (&aRgn1
== this) // Copy region if it is both source and result
657 TmpRegion
.Copy (aRgn1
);
658 pSrcRgn1
= &TmpRegion
;
661 if (&aRgn2
== this) // Copy region if it is both source and result
663 TmpRegion
.Copy (aRgn2
);
664 pSrcRgn2
= &TmpRegion
;
667 // For outer loop prefer region for which at least one rectangle is below other's bound rectangle
668 if (pSrcRgn2
->mRectListHead
.prev
->y
>= pSrcRgn1
->mBoundRect
.YMost ())
670 nsRegion
* Tmp
= pSrcRgn1
;
677 pSrcRgn2
->SaveLinkChain ();
679 pSrcRgn1
->mRectListHead
.y
= NS_COORD_GREATER_SENTINEL
;
680 pSrcRgn2
->mRectListHead
.y
= NS_COORD_GREATER_SENTINEL
;
682 for (RgnRect
* pSrcRect1
= pSrcRgn1
->mRectListHead
.next
;
683 pSrcRect1
->y
< pSrcRgn2
->mBoundRect
.YMost () ; pSrcRect1
= pSrcRect1
->next
)
685 if (pSrcRect1
->Intersects (pSrcRgn2
->mBoundRect
)) // Rectangle intersects region. Process each rectangle
687 RgnRect
* pPrev2
= &pSrcRgn2
->mRectListHead
;
689 for (RgnRect
* pSrcRect2
= pSrcRgn2
->mRectListHead
.next
;
690 pSrcRect2
->y
< pSrcRect1
->YMost () ; pSrcRect2
= pSrcRect2
->next
)
692 if (pSrcRect2
->YMost () <= pSrcRect1
->y
) // Rect2's bottom is above the top of Rect1.
693 { // No successive rectangles in Rgn1 can intersect it.
694 pPrev2
->next
= pSrcRect2
->next
; // Remove Rect2 from Rgn2's checklist
698 if (pSrcRect1
->Contains (*pSrcRect2
)) // Rect1 fully overlays Rect2.
699 { // No any other rectangle in Rgn1 can intersect it.
700 pPrev2
->next
= pSrcRect2
->next
; // Remove Rect2 from Rgn2's checklist
701 InsertInPlace (new RgnRect (*pSrcRect2
));
706 if (TmpRect
.IntersectRect (*pSrcRect1
, *pSrcRect2
))
707 InsertInPlace (new RgnRect (TmpRect
));
714 pSrcRgn2
->RestoreLinkChain ();
725 nsRegion
& nsRegion::And (const nsRegion
& aRegion
, const nsRect
& aRect
)
727 // If either region or rectangle is empty then result is empty
728 if (aRegion
.mRectCount
== 0 || aRect
.IsEmpty ())
730 else // Intersect region with rectangle
732 const nsRectFast
& aRectFast
= static_cast<const nsRectFast
&>(aRect
);
735 if (aRegion
.mRectCount
== 1) // Intersect rectangle with rectangle
737 TmpRect
.IntersectRect (*aRegion
.mRectListHead
.next
, aRectFast
);
739 } else // Intersect complex region with rectangle
741 if (!aRectFast
.Intersects (aRegion
.mBoundRect
)) // Rectangle does not intersect region
745 if (aRectFast
.Contains (aRegion
.mBoundRect
)) // Rectangle fully overlays region
750 nsRegion
* pSrcRegion
= const_cast<nsRegion
*>(&aRegion
);
752 if (&aRegion
== this) // Copy region if it is both source and result
754 TmpRegion
.Copy (aRegion
);
755 pSrcRegion
= &TmpRegion
;
759 pSrcRegion
->mRectListHead
.y
= NS_COORD_GREATER_SENTINEL
;
761 for (const RgnRect
* pSrcRect
= pSrcRegion
->mRectListHead
.next
;
762 pSrcRect
->y
< aRectFast
.YMost () ; pSrcRect
= pSrcRect
->next
)
764 if (TmpRect
.IntersectRect (*pSrcRect
, aRectFast
))
765 InsertInPlace (new RgnRect (TmpRect
));
778 nsRegion
& nsRegion::Or (const nsRegion
& aRgn1
, const nsRegion
& aRgn2
)
780 if (&aRgn1
== &aRgn2
) // Or with self
783 if (aRgn1
.mRectCount
== 0) // Region empty. Result is equal to other region
786 if (aRgn2
.mRectCount
== 0) // Region empty. Result is equal to other region
790 if (!aRgn1
.mBoundRect
.Intersects (aRgn2
.mBoundRect
)) // Regions do not intersect
791 Merge (aRgn1
, aRgn2
);
794 // Region is simple rectangle and it fully overlays other region
795 if (aRgn1
.mRectCount
== 1 && aRgn1
.mBoundRect
.Contains (aRgn2
.mBoundRect
))
798 // Region is simple rectangle and it fully overlays other region
799 if (aRgn2
.mRectCount
== 1 && aRgn2
.mBoundRect
.Contains (aRgn1
.mBoundRect
))
804 aRgn1
.SubRegion (aRgn2
, TmpRegion
); // Get only parts of region which not overlap the other region
806 TmpRegion
.MoveInto (*this);
816 nsRegion
& nsRegion::Or (const nsRegion
& aRegion
, const nsRect
& aRect
)
818 if (aRegion
.mRectCount
== 0) // Region empty. Result is equal to rectangle
821 if (aRect
.IsEmpty ()) // Rectangle is empty. Result is equal to region
825 const nsRectFast
& aRectFast
= static_cast<const nsRectFast
&>(aRect
);
827 if (!aRectFast
.Intersects (aRegion
.mBoundRect
)) // Rectangle does not intersect region
830 InsertInPlace (new RgnRect (aRectFast
), true);
833 // Region is simple rectangle and it fully overlays rectangle
834 if (aRegion
.mRectCount
== 1 && aRegion
.mBoundRect
.Contains (aRectFast
))
837 if (aRectFast
.Contains (aRegion
.mBoundRect
)) // Rectangle fully overlays region
841 aRegion
.SubRect (aRectFast
, *this); // Exclude from region parts that overlap the rectangle
842 InsertInPlace (new RgnRect (aRectFast
));
852 nsRegion
& nsRegion::Xor (const nsRegion
& aRgn1
, const nsRegion
& aRgn2
)
854 if (&aRgn1
== &aRgn2
) // Xor with self
857 if (aRgn1
.mRectCount
== 0) // Region empty. Result is equal to other region
860 if (aRgn2
.mRectCount
== 0) // Region empty. Result is equal to other region
864 if (!aRgn1
.mBoundRect
.Intersects (aRgn2
.mBoundRect
)) // Regions do not intersect
865 Merge (aRgn1
, aRgn2
);
868 // Region is simple rectangle and it fully overlays other region
869 if (aRgn1
.mRectCount
== 1 && aRgn1
.mBoundRect
.Contains (aRgn2
.mBoundRect
))
871 aRgn1
.SubRegion (aRgn2
, *this);
874 // Region is simple rectangle and it fully overlays other region
875 if (aRgn2
.mRectCount
== 1 && aRgn2
.mBoundRect
.Contains (aRgn1
.mBoundRect
))
877 aRgn2
.SubRegion (aRgn1
, *this);
882 aRgn1
.SubRegion (aRgn2
, TmpRegion
);
883 aRgn2
.SubRegion (aRgn1
, *this);
884 TmpRegion
.MoveInto (*this);
894 nsRegion
& nsRegion::Xor (const nsRegion
& aRegion
, const nsRect
& aRect
)
896 if (aRegion
.mRectCount
== 0) // Region empty. Result is equal to rectangle
899 if (aRect
.IsEmpty ()) // Rectangle is empty. Result is equal to region
903 const nsRectFast
& aRectFast
= static_cast<const nsRectFast
&>(aRect
);
905 if (!aRectFast
.Intersects (aRegion
.mBoundRect
)) // Rectangle does not intersect region
908 InsertInPlace (new RgnRect (aRectFast
), true);
911 // Region is simple rectangle and it fully overlays rectangle
912 if (aRegion
.mRectCount
== 1 && aRegion
.mBoundRect
.Contains (aRectFast
))
914 aRegion
.SubRect (aRectFast
, *this);
917 if (aRectFast
.Contains (aRegion
.mBoundRect
)) // Rectangle fully overlays region
920 TmpRegion
.Copy (aRectFast
);
921 TmpRegion
.SubRegion (aRegion
, *this);
926 TmpRegion
.Copy (aRectFast
);
927 TmpRegion
.SubRegion (aRegion
, TmpRegion
);
928 aRegion
.SubRect (aRectFast
, *this);
929 TmpRegion
.MoveInto (*this);
939 nsRegion
& nsRegion::Sub (const nsRegion
& aRgn1
, const nsRegion
& aRgn2
)
941 if (&aRgn1
== &aRgn2
) // Sub from self
944 if (aRgn1
.mRectCount
== 0) // If source is empty then result is empty, too
947 if (aRgn2
.mRectCount
== 0) // Nothing to subtract
951 if (!aRgn1
.mBoundRect
.Intersects (aRgn2
.mBoundRect
)) // Regions do not intersect
955 aRgn1
.SubRegion (aRgn2
, *this);
964 nsRegion
& nsRegion::Sub (const nsRegion
& aRegion
, const nsRect
& aRect
)
966 if (aRegion
.mRectCount
== 0) // If source is empty then result is empty, too
969 if (aRect
.IsEmpty ()) // Nothing to subtract
973 const nsRectFast
& aRectFast
= static_cast<const nsRectFast
&>(aRect
);
975 if (!aRectFast
.Intersects (aRegion
.mBoundRect
)) // Rectangle does not intersect region
979 if (aRectFast
.Contains (aRegion
.mBoundRect
)) // Rectangle fully overlays region
983 aRegion
.SubRect (aRectFast
, *this);
992 bool nsRegion::Contains (const nsRect
& aRect
) const
999 return mBoundRect
.Contains (aRect
);
1002 tmpRgn
.Sub(aRect
, *this);
1003 return tmpRgn
.IsEmpty();
1006 bool nsRegion::Contains (const nsRegion
& aRgn
) const
1008 // XXX this could be made faster
1009 nsRegionRectIterator
iter(aRgn
);
1010 while (const nsRect
* r
= iter
.Next()) {
1011 if (!Contains (*r
)) {
1018 bool nsRegion::Intersects (const nsRect
& aRect
) const
1020 if (aRect
.IsEmpty() || IsEmpty())
1023 const RgnRect
* r
= mRectListHead
.next
;
1024 while (r
!= &mRectListHead
)
1026 if (r
->Intersects(aRect
))
1033 // Subtract region from current region.
1034 // Both regions are non-empty and they intersect each other.
1035 // Result could be empty region if aRgn2 is rectangle that fully overlays aRgn1.
1036 // Optimize () is not called on exit (bound rectangle is not updated).
1038 void nsRegion::SubRegion (const nsRegion
& aRegion
, nsRegion
& aResult
) const
1040 if (aRegion
.mRectCount
== 1) // Subtract simple rectangle
1042 if (aRegion
.mBoundRect
.Contains (mBoundRect
))
1043 aResult
.SetEmpty ();
1045 SubRect (*aRegion
.mRectListHead
.next
, aResult
);
1048 nsRegion TmpRegion
, CompletedRegion
;
1049 const nsRegion
* pSubRgn
= &aRegion
;
1051 if (&aResult
== &aRegion
) // Copy region if it is both source and result
1053 TmpRegion
.Copy (aRegion
);
1054 pSubRgn
= &TmpRegion
;
1057 const RgnRect
* pSubRect
= pSubRgn
->mRectListHead
.next
;
1059 SubRect (*pSubRect
, aResult
, CompletedRegion
);
1060 pSubRect
= pSubRect
->next
;
1062 while (pSubRect
!= &pSubRgn
->mRectListHead
)
1064 aResult
.SubRect (*pSubRect
, aResult
, CompletedRegion
);
1065 pSubRect
= pSubRect
->next
;
1068 CompletedRegion
.MoveInto (aResult
);
1073 // Subtract rectangle from current region.
1074 // Both region and rectangle are non-empty and they intersect each other.
1075 // Result could be empty region if aRect fully overlays aRegion.
1076 // Could be called repeatedly with 'this' as input and result - bound rectangle is not known.
1077 // Optimize () is not called on exit (bound rectangle is not updated).
1079 // aCompleted is filled with rectangles which are already checked and could be safely
1080 // removed from further examination in case aRect rectangles come from ordered list.
1081 // aCompleted is not automatically emptied. aCompleted and aResult could be the same region.
1083 void nsRegion::SubRect (const nsRectFast
& aRect
, nsRegion
& aResult
, nsRegion
& aCompleted
) const
1086 const nsRegion
* pSrcRegion
= this;
1088 if (&aResult
== this) // Copy region if it is both source and result
1090 TmpRegion
.Copy (*this);
1091 pSrcRegion
= &TmpRegion
;
1094 aResult
.SetToElements (0);
1096 const_cast<nsRegion
*>(pSrcRegion
)->mRectListHead
.y
= NS_COORD_GREATER_SENTINEL
;
1097 const RgnRect
* pSrcRect
= pSrcRegion
->mRectListHead
.next
;
1099 for ( ; pSrcRect
->y
< aRect
.YMost () ; pSrcRect
= pSrcRect
->next
)
1103 // If bottom of current rectangle is above the top of aRect then this rectangle
1104 // could be moved to aCompleted region. Successive aRect rectangles from ordered
1105 // list do not have to check this rectangle again.
1106 if (pSrcRect
->YMost () <= aRect
.y
)
1108 aCompleted
.InsertInPlace (new RgnRect (*pSrcRect
));
1112 if (!TmpRect
.IntersectRect (*pSrcRect
, aRect
))
1113 aResult
.InsertInPlace (new RgnRect (*pSrcRect
));
1116 // Rectangle A. Subtract from this rectangle B
1117 const nscoord ax
= pSrcRect
->x
;
1118 const nscoord axm
= pSrcRect
->XMost ();
1119 const nscoord aw
= pSrcRect
->width
;
1120 const nscoord ay
= pSrcRect
->y
;
1121 const nscoord aym
= pSrcRect
->YMost ();
1122 const nscoord ah
= pSrcRect
->height
;
1123 // Rectangle B. Subtract this from rectangle A
1124 const nscoord bx
= aRect
.x
;
1125 const nscoord bxm
= aRect
.XMost ();
1126 const nscoord by
= aRect
.y
;
1127 const nscoord bym
= aRect
.YMost ();
1128 // Rectangle I. Area where rectangles A and B intersect
1129 const nscoord ix
= TmpRect
.x
;
1130 const nscoord ixm
= TmpRect
.XMost ();
1131 const nscoord iy
= TmpRect
.y
;
1132 const nscoord iym
= TmpRect
.YMost ();
1133 const nscoord ih
= TmpRect
.height
;
1135 // There are 16 combinations how rectangles could intersect
1137 if (bx
<= ax
&& by
<= ay
)
1139 if (bxm
< axm
&& bym
< aym
) // 1.
1141 aResult
.InsertInPlace (new RgnRect (ixm
, ay
, axm
- ixm
, ih
));
1142 aResult
.InsertInPlace (new RgnRect (ax
, iym
, aw
, aym
- iym
));
1144 if (bxm
>= axm
&& bym
< aym
) // 2.
1146 aResult
.InsertInPlace (new RgnRect (ax
, iym
, aw
, aym
- iym
));
1148 if (bxm
< axm
&& bym
>= aym
) // 3.
1150 aResult
.InsertInPlace (new RgnRect (ixm
, ay
, axm
- ixm
, ah
));
1152 if (pSrcRect
->IsEqualInterior(aRect
)) // 4. subset
1153 { // Current rectangle is equal to aRect
1154 pSrcRect
= pSrcRect
->next
; // don't add this one to the result, it's removed
1155 break; // No any other rectangle in region can intersect it
1158 if (bx
> ax
&& by
<= ay
)
1160 if (bxm
< axm
&& bym
< aym
) // 5.
1162 aResult
.InsertInPlace (new RgnRect (ax
, ay
, ix
- ax
, ih
));
1163 aResult
.InsertInPlace (new RgnRect (ixm
, ay
, axm
- ixm
, ih
));
1164 aResult
.InsertInPlace (new RgnRect (ax
, iym
, aw
, aym
- iym
));
1166 if (bxm
>= axm
&& bym
< aym
) // 6.
1168 aResult
.InsertInPlace (new RgnRect (ax
, ay
, ix
- ax
, ih
));
1169 aResult
.InsertInPlace (new RgnRect (ax
, iym
, aw
, aym
- iym
));
1171 if (bxm
< axm
&& bym
>= aym
) // 7.
1173 aResult
.InsertInPlace (new RgnRect (ax
, ay
, ix
- ax
, ah
));
1174 aResult
.InsertInPlace (new RgnRect (ixm
, ay
, axm
- ixm
, ah
));
1176 if (bxm
>= axm
&& bym
>= aym
) // 8.
1178 aResult
.InsertInPlace (new RgnRect (ax
, ay
, ix
- ax
, ah
));
1181 if (bx
<= ax
&& by
> ay
)
1183 if (bxm
< axm
&& bym
< aym
) // 9.
1185 aResult
.InsertInPlace (new RgnRect (ax
, ay
, aw
, iy
- ay
));
1186 aResult
.InsertInPlace (new RgnRect (ixm
, iy
, axm
- ixm
, ih
));
1187 aResult
.InsertInPlace (new RgnRect (ax
, iym
, aw
, aym
- iym
));
1189 if (bxm
>= axm
&& bym
< aym
) // 10.
1191 aResult
.InsertInPlace (new RgnRect (ax
, ay
, aw
, iy
- ay
));
1192 aResult
.InsertInPlace (new RgnRect (ax
, iym
, aw
, aym
- iym
));
1194 if (bxm
< axm
&& bym
>= aym
) // 11.
1196 aResult
.InsertInPlace (new RgnRect (ax
, ay
, aw
, iy
- ay
));
1197 aResult
.InsertInPlace (new RgnRect (ixm
, iy
, axm
- ixm
, ih
));
1199 if (bxm
>= axm
&& bym
>= aym
) // 12.
1201 aResult
.InsertInPlace (new RgnRect (ax
, ay
, aw
, iy
- ay
));
1204 if (bx
> ax
&& by
> ay
)
1206 if (bxm
< axm
&& bym
< aym
) // 13.
1208 aResult
.InsertInPlace (new RgnRect (ax
, ay
, aw
, iy
- ay
));
1209 aResult
.InsertInPlace (new RgnRect (ax
, iy
, ix
- ax
, ih
));
1210 aResult
.InsertInPlace (new RgnRect (ixm
, iy
, axm
- ixm
, ih
));
1211 aResult
.InsertInPlace (new RgnRect (ax
, iym
, aw
, aym
- iym
));
1213 // Current rectangle fully overlays aRect. No any other rectangle can intersect it.
1214 pSrcRect
= pSrcRect
->next
; // don't add this one to the result, it's removed
1217 if (bxm
>= axm
&& bym
< aym
) // 14.
1219 aResult
.InsertInPlace (new RgnRect (ax
, ay
, aw
, iy
- ay
));
1220 aResult
.InsertInPlace (new RgnRect (ax
, iy
, ix
- ax
, ih
));
1221 aResult
.InsertInPlace (new RgnRect (ax
, iym
, aw
, aym
- iym
));
1223 if (bxm
< axm
&& bym
>= aym
) // 15.
1225 aResult
.InsertInPlace (new RgnRect (ax
, ay
, aw
, iy
- ay
));
1226 aResult
.InsertInPlace (new RgnRect (ax
, iy
, ix
- ax
, ih
));
1227 aResult
.InsertInPlace (new RgnRect (ixm
, iy
, axm
- ixm
, ih
));
1229 if (bxm
>= axm
&& bym
>= aym
) // 16.
1231 aResult
.InsertInPlace (new RgnRect (ax
, ay
, aw
, iy
- ay
));
1232 aResult
.InsertInPlace (new RgnRect (ax
, iy
, ix
- ax
, ih
));
1238 // Just copy remaining rectangles in region which are below aRect and can't intersect it.
1239 // If rectangles are in temporary region then they could be moved.
1240 if (pSrcRegion
== &TmpRegion
)
1241 TmpRegion
.MoveInto (aResult
, pSrcRect
);
1244 while (pSrcRect
!= &pSrcRegion
->mRectListHead
)
1246 aResult
.InsertInPlace (new RgnRect (*pSrcRect
));
1247 pSrcRect
= pSrcRect
->next
;
1253 bool nsRegion::IsEqual (const nsRegion
& aRegion
) const
1255 if (mRectCount
== 0)
1256 return (aRegion
.mRectCount
== 0) ? true : false;
1258 if (aRegion
.mRectCount
== 0)
1259 return (mRectCount
== 0) ? true : false;
1261 if (mRectCount
== 1 && aRegion
.mRectCount
== 1) // Both regions are simple rectangles
1262 return (mRectListHead
.next
->IsEqualInterior(*aRegion
.mRectListHead
.next
));
1263 else // At least one is complex region.
1265 if (!mBoundRect
.IsEqualInterior(aRegion
.mBoundRect
)) // If regions are equal then bounding rectangles should match
1270 TmpRegion
.Xor (*this, aRegion
); // Get difference between two regions
1272 return (TmpRegion
.mRectCount
== 0);
1278 void nsRegion::MoveBy (nsPoint aPt
)
1282 RgnRect
* pRect
= mRectListHead
.next
;
1284 while (pRect
!= &mRectListHead
)
1286 pRect
->MoveBy (aPt
.x
, aPt
.y
);
1287 pRect
= pRect
->next
;
1290 mBoundRect
.MoveBy (aPt
.x
, aPt
.y
);
1294 nsRegion
& nsRegion::ScaleRoundOut (float aXScale
, float aYScale
)
1297 nsRegionRectIterator
iter(*this);
1299 const nsRect
* r
= iter
.Next();
1303 rect
.ScaleRoundOut(aXScale
, aYScale
);
1304 region
.Or(region
, rect
);
1310 nsRegion
& nsRegion::ScaleInverseRoundOut (float aXScale
, float aYScale
)
1313 nsRegionRectIterator
iter(*this);
1315 const nsRect
* r
= iter
.Next();
1319 rect
.ScaleInverseRoundOut(aXScale
, aYScale
);
1320 region
.Or(region
, rect
);
1326 nsRegion
nsRegion::ConvertAppUnitsRoundOut (int32_t aFromAPP
, int32_t aToAPP
) const
1328 if (aFromAPP
== aToAPP
) {
1331 // Do it in a simplistic and slow way to avoid any weird behaviour with
1332 // rounding causing rects to overlap. Should be fast enough for what we need.
1334 nsRegionRectIterator
iter(*this);
1336 const nsRect
* r
= iter
.Next();
1339 nsRect rect
= r
->ConvertAppUnitsRoundOut(aFromAPP
, aToAPP
);
1340 region
.Or(region
, rect
);
1345 nsRegion
nsRegion::ConvertAppUnitsRoundIn (int32_t aFromAPP
, int32_t aToAPP
) const
1347 if (aFromAPP
== aToAPP
) {
1350 // Do it in a simplistic and slow way to avoid any weird behaviour with
1351 // rounding causing rects to overlap. Should be fast enough for what we need.
1353 nsRegionRectIterator
iter(*this);
1355 const nsRect
* r
= iter
.Next();
1358 nsRect rect
= r
->ConvertAppUnitsRoundIn(aFromAPP
, aToAPP
);
1359 region
.Or(region
, rect
);
1364 nsIntRegion
nsRegion::ToPixels (nscoord aAppUnitsPerPixel
, bool aOutsidePixels
) const
1367 nsRegionRectIterator
rgnIter(*this);
1368 const nsRect
* currentRect
;
1369 while ((currentRect
= rgnIter
.Next())) {
1370 nsIntRect deviceRect
;
1372 deviceRect
= currentRect
->ToOutsidePixels(aAppUnitsPerPixel
);
1374 deviceRect
= currentRect
->ToNearestPixels(aAppUnitsPerPixel
);
1375 result
.Or(result
, deviceRect
);
1380 nsIntRegion
nsRegion::ToOutsidePixels (nscoord aAppUnitsPerPixel
) const
1382 return ToPixels(aAppUnitsPerPixel
, true);
1385 nsIntRegion
nsRegion::ToNearestPixels (nscoord aAppUnitsPerPixel
) const
1387 return ToPixels(aAppUnitsPerPixel
, false);
1390 nsIntRegion
nsRegion::ScaleToNearestPixels (float aScaleX
, float aScaleY
,
1391 nscoord aAppUnitsPerPixel
) const
1394 nsRegionRectIterator
rgnIter(*this);
1395 const nsRect
* currentRect
;
1396 while ((currentRect
= rgnIter
.Next())) {
1397 nsIntRect deviceRect
=
1398 currentRect
->ScaleToNearestPixels(aScaleX
, aScaleY
, aAppUnitsPerPixel
);
1399 result
.Or(result
, deviceRect
);
1404 nsIntRegion
nsRegion::ScaleToOutsidePixels (float aScaleX
, float aScaleY
,
1405 nscoord aAppUnitsPerPixel
) const
1408 nsRegionRectIterator
rgnIter(*this);
1409 const nsRect
* currentRect
;
1410 while ((currentRect
= rgnIter
.Next())) {
1411 nsIntRect deviceRect
=
1412 currentRect
->ScaleToOutsidePixels(aScaleX
, aScaleY
, aAppUnitsPerPixel
);
1413 result
.Or(result
, deviceRect
);
1418 nsIntRegion
nsRegion::ScaleToInsidePixels (float aScaleX
, float aScaleY
,
1419 nscoord aAppUnitsPerPixel
) const
1421 /* When scaling a rect, walk forward through the rect list up until the y value is greater
1422 * than the current rect's YMost() value.
1424 * For each rect found, check if the rects have a touching edge (in unscaled coordinates),
1425 * and if one edge is entirely contained within the other.
1427 * If it is, then the contained edge can be moved (in scaled pixels) to ensure that no
1430 * Since this could be potentially expensive - O(n^2), we only attempt this algorithm
1431 * for the first rect.
1435 RgnRect
* pRect
= mRectListHead
.next
;
1436 RgnRect
* first
= pRect
;
1438 nsIntRect firstDeviceRect
;
1439 if (pRect
!= &mRectListHead
) {
1441 pRect
->ScaleToInsidePixels(aScaleX
, aScaleY
, aAppUnitsPerPixel
);
1442 pRect
= pRect
->next
;
1445 while (pRect
!= &mRectListHead
)
1447 nsIntRect deviceRect
=
1448 pRect
->ScaleToInsidePixels(aScaleX
, aScaleY
, aAppUnitsPerPixel
);
1450 if (pRect
->y
<= first
->YMost()) {
1451 if (pRect
->XMost() == first
->x
&& pRect
->YMost() <= first
->YMost()) {
1452 // pRect is touching on the left edge of the first rect and contained within
1453 // the length of its left edge
1454 deviceRect
.SetRightEdge(firstDeviceRect
.x
);
1455 } else if (pRect
->x
== first
->XMost() && pRect
->YMost() <= first
->YMost()) {
1456 // pRect is touching on the right edge of the first rect and contained within
1457 // the length of its right edge
1458 deviceRect
.SetLeftEdge(firstDeviceRect
.XMost());
1459 } else if (pRect
->y
== first
->YMost()) {
1460 // The bottom of the first rect is on the same line as the top of pRect, but
1461 // they aren't necessarily contained.
1462 if (pRect
->x
<= first
->x
&& pRect
->XMost() >= first
->XMost()) {
1463 // The top of pRect contains the bottom of the first rect
1464 firstDeviceRect
.SetBottomEdge(deviceRect
.y
);
1465 } else if (pRect
->x
>= first
->x
&& pRect
->XMost() <= first
->XMost()) {
1466 // The bottom of the first contains the top of pRect
1467 deviceRect
.SetTopEdge(firstDeviceRect
.YMost());
1471 pRect
= pRect
->next
;
1472 result
.Or(result
, deviceRect
);
1475 result
.Or(result
, firstDeviceRect
);
1479 // A cell's "value" is a pair consisting of
1480 // a) the area of the subrectangle it corresponds to, if it's in
1481 // aContainingRect and in the region, 0 otherwise
1482 // b) the area of the subrectangle it corresponds to, if it's in the region,
1484 // Addition, subtraction and identity are defined on these values in the
1485 // obvious way. Partial order is lexicographic.
1486 // A "large negative value" is defined with large negative numbers for both
1487 // fields of the pair. This negative value has the property that adding any
1488 // number of non-negative values to it always results in a negative value.
1490 // The GetLargestRectangle algorithm works in three phases:
1491 // 1) Convert the region into a grid by adding vertical/horizontal lines for
1492 // each edge of each rectangle in the region.
1493 // 2) For each rectangle in the region, for each cell it contains, set that
1494 // cells's value as described above.
1495 // 3) Calculate the submatrix with the largest sum such that none of its cells
1496 // contain any 0s (empty regions). The rectangle represented by the
1497 // submatrix is the largest rectangle in the region.
1499 // Let k be the number of rectangles in the region.
1500 // Let m be the height of the grid generated in step 1.
1501 // Let n be the width of the grid generated in step 1.
1503 // Step 1 is O(k) in time and O(m+n) in space for the sparse grid.
1504 // Step 2 is O(mn) in time and O(mn) in additional space for the full grid.
1505 // Step 3 is O(m^2 n) in time and O(mn) in additional space
1507 // The implementation of steps 1 and 2 are rather straightforward. However our
1508 // implementation of step 3 uses dynamic programming to achieve its efficiency.
1510 // Psuedo code for step 3 is as follows where G is the grid from step 1 and A
1511 // is the array from step 2:
1512 // Phase3 = function (G, A, m, n) {
1513 // let (t,b,l,r,_) = MaxSum2D(A,m,n)
1514 // return rect(G[t],G[l],G[r],G[b]);
1516 // MaxSum2D = function (A, m, n) {
1517 // S = array(m+1,n+1)
1518 // S[0][i] = 0 for i in [0,n]
1519 // S[j][0] = 0 for j in [0,m]
1520 // S[j][i] = (if A[j-1][i-1] = 0 then some large negative value else A[j-1][i-1])
1521 // + S[j-1][n] + S[j][i-1] - S[j-1][i-1]
1523 // // top, bottom, left, right, area
1524 // var maxRect = (-1, -1, -1, -1, 0);
1526 // for all (m',m'') in [0, m]^2 {
1527 // let B = { S[m'][i] - S[m''][i] | 0 <= i <= n }
1528 // let ((l,r),area) = MaxSum1D(B,n+1)
1529 // if (area > maxRect.area) {
1530 // maxRect := (m', m'', l, r, area)
1537 // Originally taken from Improved algorithms for the k-maximum subarray problem
1538 // for small k - SE Bae, T Takaoka but modified to show the explicit tracking
1539 // of indices and we already have the prefix sums from our one call site so
1540 // there's no need to construct them.
1541 // MaxSum1D = function (A,n) {
1544 // var maxIndices = (0,0);
1546 // for i in range(n) {
1547 // let cand = A[i] - min;
1548 // if (cand > max) {
1550 // maxIndices := (minIdx, i)
1552 // if (min > A[i]) {
1557 // return (minIdx, maxIdx, max);
1561 // This class represents a partitioning of an axis delineated by coordinates.
1562 // It internally maintains a sorted array of coordinates.
1563 class AxisPartition
{
1565 // Adds a new partition at the given coordinate to this partitioning. If
1566 // the coordinate is already present in the partitioning, this does nothing.
1567 void InsertCoord(nscoord c
) {
1568 uint32_t i
= mStops
.IndexOfFirstElementGt(c
);
1569 if (i
== 0 || mStops
[i
-1] != c
) {
1570 mStops
.InsertElementAt(i
, c
);
1574 // Returns the array index of the given partition point. The partition
1575 // point must already be present in the partitioning.
1576 int32_t IndexOf(nscoord p
) const {
1577 return mStops
.BinaryIndexOf(p
);
1580 // Returns the partition at the given index which must be non-zero and
1581 // less than the number of partitions in this partitioning.
1582 nscoord
StopAt(int32_t index
) const {
1583 return mStops
[index
];
1586 // Returns the size of the gap between the partition at the given index and
1587 // the next partition in this partitioning. If the index is the last index
1588 // in the partitioning, the result is undefined.
1589 nscoord
StopSize(int32_t index
) const {
1590 return mStops
[index
+1] - mStops
[index
];
1593 // Returns the number of partitions in this partitioning.
1594 int32_t GetNumStops() const { return mStops
.Length(); }
1597 nsTArray
<nscoord
> mStops
;
1600 const int64_t kVeryLargeNegativeNumber
= 0xffff000000000000ll
;
1603 int64_t mSizeContainingRect
;
1606 SizePair() : mSizeContainingRect(0), mSize(0) {}
1608 static SizePair
VeryLargeNegative() {
1610 result
.mSize
= result
.mSizeContainingRect
= kVeryLargeNegativeNumber
;
1613 SizePair
& operator=(const SizePair
& aOther
) {
1614 mSizeContainingRect
= aOther
.mSizeContainingRect
;
1615 mSize
= aOther
.mSize
;
1618 bool operator<(const SizePair
& aOther
) const {
1619 if (mSizeContainingRect
< aOther
.mSizeContainingRect
)
1621 if (mSizeContainingRect
> aOther
.mSizeContainingRect
)
1623 return mSize
< aOther
.mSize
;
1625 bool operator>(const SizePair
& aOther
) const {
1626 return aOther
.operator<(*this);
1628 SizePair
operator+(const SizePair
& aOther
) const {
1629 SizePair result
= *this;
1630 result
.mSizeContainingRect
+= aOther
.mSizeContainingRect
;
1631 result
.mSize
+= aOther
.mSize
;
1634 SizePair
operator-(const SizePair
& aOther
) const {
1635 SizePair result
= *this;
1636 result
.mSizeContainingRect
-= aOther
.mSizeContainingRect
;
1637 result
.mSize
-= aOther
.mSize
;
1642 // Returns the sum and indices of the subarray with the maximum sum of the
1643 // given array (A,n), assuming the array is already in prefix sum form.
1644 SizePair
MaxSum1D(const nsTArray
<SizePair
> &A
, int32_t n
,
1645 int32_t *minIdx
, int32_t *maxIdx
) {
1646 // The min/max indicies of the largest subarray found so far
1648 int32_t currentMinIdx
= 0;
1653 // Because we're given the array in prefix sum form, we know the first
1655 for(int32_t i
= 1; i
< n
; i
++) {
1656 SizePair cand
= A
[i
] - min
;
1659 *minIdx
= currentMinIdx
;
1672 nsRect
nsRegion::GetLargestRectangle (const nsRect
& aContainingRect
) const {
1675 if (mRectCount
<= 1) {
1676 bestRect
= mBoundRect
;
1680 AxisPartition xaxis
, yaxis
;
1682 // Step 1: Calculate the grid lines
1683 nsRegionRectIterator
iter(*this);
1684 const nsRect
*currentRect
;
1685 while ((currentRect
= iter
.Next())) {
1686 xaxis
.InsertCoord(currentRect
->x
);
1687 xaxis
.InsertCoord(currentRect
->XMost());
1688 yaxis
.InsertCoord(currentRect
->y
);
1689 yaxis
.InsertCoord(currentRect
->YMost());
1691 if (!aContainingRect
.IsEmpty()) {
1692 xaxis
.InsertCoord(aContainingRect
.x
);
1693 xaxis
.InsertCoord(aContainingRect
.XMost());
1694 yaxis
.InsertCoord(aContainingRect
.y
);
1695 yaxis
.InsertCoord(aContainingRect
.YMost());
1698 // Step 2: Fill out the grid with the areas
1699 // Note: due to the ordering of rectangles in the region, it is not always
1700 // possible to combine steps 2 and 3 so we don't try to be clever.
1701 int32_t matrixHeight
= yaxis
.GetNumStops() - 1;
1702 int32_t matrixWidth
= xaxis
.GetNumStops() - 1;
1703 int32_t matrixSize
= matrixHeight
* matrixWidth
;
1704 nsTArray
<SizePair
> areas(matrixSize
);
1705 areas
.SetLength(matrixSize
);
1708 while ((currentRect
= iter
.Next())) {
1709 int32_t xstart
= xaxis
.IndexOf(currentRect
->x
);
1710 int32_t xend
= xaxis
.IndexOf(currentRect
->XMost());
1711 int32_t y
= yaxis
.IndexOf(currentRect
->y
);
1712 int32_t yend
= yaxis
.IndexOf(currentRect
->YMost());
1714 for (; y
< yend
; y
++) {
1715 nscoord height
= yaxis
.StopSize(y
);
1716 for (int32_t x
= xstart
; x
< xend
; x
++) {
1717 nscoord width
= xaxis
.StopSize(x
);
1718 int64_t size
= width
*int64_t(height
);
1719 if (currentRect
->Intersects(aContainingRect
)) {
1720 areas
[y
*matrixWidth
+x
].mSizeContainingRect
= size
;
1722 areas
[y
*matrixWidth
+x
].mSize
= size
;
1727 // Step 3: Find the maximum submatrix sum that does not contain a rectangle
1729 // First get the prefix sum array
1730 int32_t m
= matrixHeight
+ 1;
1731 int32_t n
= matrixWidth
+ 1;
1732 nsTArray
<SizePair
> pareas(m
*n
);
1733 pareas
.SetLength(m
*n
);
1734 for (int32_t y
= 1; y
< m
; y
++) {
1735 for (int32_t x
= 1; x
< n
; x
++) {
1736 SizePair area
= areas
[(y
-1)*matrixWidth
+x
-1];
1738 area
= SizePair::VeryLargeNegative();
1740 area
= area
+ pareas
[ y
*n
+x
-1]
1741 + pareas
[(y
-1)*n
+x
]
1742 - pareas
[(y
-1)*n
+x
-1];
1743 pareas
[y
*n
+x
] = area
;
1747 // No longer need the grid
1752 int32_t left
, top
, right
, bottom
;
1753 } bestRectIndices
= { 0, 0, 0, 0 };
1754 for (int32_t m1
= 0; m1
< m
; m1
++) {
1755 for (int32_t m2
= m1
+1; m2
< m
; m2
++) {
1756 nsTArray
<SizePair
> B
;
1758 for (int32_t i
= 0; i
< n
; i
++) {
1759 B
[i
] = pareas
[m2
*n
+i
] - pareas
[m1
*n
+i
];
1761 int32_t minIdx
, maxIdx
;
1762 SizePair area
= MaxSum1D(B
, n
, &minIdx
, &maxIdx
);
1763 if (area
> bestArea
) {
1764 bestRectIndices
.left
= minIdx
;
1765 bestRectIndices
.top
= m1
;
1766 bestRectIndices
.right
= maxIdx
;
1767 bestRectIndices
.bottom
= m2
;
1773 bestRect
.MoveTo(xaxis
.StopAt(bestRectIndices
.left
),
1774 yaxis
.StopAt(bestRectIndices
.top
));
1775 bestRect
.SizeTo(xaxis
.StopAt(bestRectIndices
.right
) - bestRect
.x
,
1776 yaxis
.StopAt(bestRectIndices
.bottom
) - bestRect
.y
);
1782 void nsRegion::SimplifyOutward (uint32_t aMaxRects
)
1784 NS_ASSERTION(aMaxRects
>= 1, "Invalid max rect count");
1786 if (mRectCount
<= aMaxRects
)
1789 // Try combining rects in horizontal bands into a single rect
1790 RgnRect
* pRect
= mRectListHead
.next
;
1791 while (pRect
!= &mRectListHead
)
1793 // Combine with the following rectangle if they have the same YMost
1794 // or if they overlap vertically. This ensures that all overlapping
1795 // rectangles are merged, preserving the invariant that rectangles
1797 // The goal here is to try to keep groups of rectangles that are vertically
1798 // discontiguous as separate rectangles in the final region. This is
1799 // simple and fast to implement and page contents tend to vary more
1800 // vertically than horizontally (which is why our rectangles are stored
1801 // sorted by y-coordinate, too).
1802 while (pRect
->next
!= &mRectListHead
&&
1803 pRect
->YMost () >= pRect
->next
->y
)
1805 pRect
->UnionRect(*pRect
, *pRect
->next
);
1806 delete Remove (pRect
->next
);
1809 pRect
= pRect
->next
;
1812 if (mRectCount
<= aMaxRects
)
1815 *this = GetBounds();
1818 void nsRegion::SimplifyInward (uint32_t aMaxRects
)
1820 NS_ASSERTION(aMaxRects
>= 1, "Invalid max rect count");
1822 if (mRectCount
<= aMaxRects
)
1828 void nsRegion::SimpleSubtract (const nsRect
& aRect
)
1830 if (aRect
.IsEmpty())
1833 // protect against aRect being one of our own rectangles
1834 nsRect param
= aRect
;
1835 RgnRect
* r
= mRectListHead
.next
;
1836 while (r
!= &mRectListHead
)
1838 RgnRect
* next
= r
->next
;
1839 if (param
.Contains(*r
)) {
1848 void nsRegion::SimpleSubtract (const nsRegion
& aRegion
)
1850 if (aRegion
.IsEmpty())
1853 if (&aRegion
== this) {
1858 const RgnRect
* r
= aRegion
.mRectListHead
.next
;
1859 while (r
!= &aRegion
.mRectListHead
)
1869 nsRegion::ToString() const
1872 result
.AppendLiteral("[");
1873 const RgnRect
* r
= mRectListHead
.next
;
1874 while (r
!= &mRectListHead
)
1876 if (r
!= mRectListHead
.next
) {
1877 result
.AppendLiteral("; ");
1879 result
.Append(nsPrintfCString("%d,%d,%d,%d", r
->x
, r
->y
, r
->XMost(), r
->YMost()));
1882 result
.AppendLiteral("]");
1887 nsRegion
nsIntRegion::ToAppUnits (nscoord aAppUnitsPerPixel
) const
1890 nsIntRegionRectIterator
rgnIter(*this);
1891 const nsIntRect
* currentRect
;
1892 while ((currentRect
= rgnIter
.Next())) {
1893 nsRect appRect
= currentRect
->ToAppUnits(aAppUnitsPerPixel
);
1894 result
.Or(result
, appRect
);