gfx/src/nsRegion.cpp

   1 /* ***** BEGIN LICENSE BLOCK *****
   2  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   3  *
   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/
   8  *
   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
  12  * License.
  13  *
  14  * The Original Code is mozilla.org code.
  15  *
  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.
  20  *
  21  * Contributor(s):
  22  *
  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.
  34  *
  35  * ***** END LICENSE BLOCK ***** */
  36
  37 #include "prlock.h"
  38 #include "nsRegion.h"
  39 #include "nsISupportsImpl.h"
  40
  41 // Fast inline analogues of nsRect methods for nsRegion::nsRectFast.
  42 // Check for emptiness is not required - it is guaranteed by caller.
  43
  44 inline PRBool nsRegion::nsRectFast::Contains (const nsRect& aRect) const
  45 {
  46   return (PRBool) ((aRect.x >= x) && (aRect.y >= y) &&
  47                    (aRect.XMost () <= XMost ()) && (aRect.YMost () <= YMost ()));
  48 }
  49
  50 inline PRBool nsRegion::nsRectFast::Intersects (const nsRect& aRect) const
  51 {
  52   return (PRBool) ((x < aRect.XMost ()) && (y < aRect.YMost ()) &&
  53                    (aRect.x < XMost ()) && (aRect.y < YMost ()));
  54 }
  55
  56 inline PRBool nsRegion::nsRectFast::IntersectRect (const nsRect& aRect1, const nsRect& aRect2)
  57 {
  58   const nscoord xmost = PR_MIN (aRect1.XMost (), aRect2.XMost ());
  59   x = PR_MAX (aRect1.x, aRect2.x);
  60   width = xmost - x;
  61   if (width <= 0) return PR_FALSE;
  62
  63   const nscoord ymost = PR_MIN (aRect1.YMost (), aRect2.YMost ());
  64   y = PR_MAX (aRect1.y, aRect2.y);
  65   height = ymost - y;
  66   if (height <= 0) return PR_FALSE;
  67
  68   return PR_TRUE;
  69 }
  70
  71 inline void nsRegion::nsRectFast::UnionRect (const nsRect& aRect1, const nsRect& aRect2)
  72 {
  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);
  77   width  = xmost - x;
  78   height = ymost - y;
  79 }
  80
  81
  82
  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.
  86
  87 #define INIT_MEM_CHUNK_ENTRIES 100
  88 #define INCR_MEM_CHUNK_ENTRIES 100
  89
  90 class RgnRectMemoryAllocator
  91 {
  92   nsRegion::RgnRect*  mFreeListHead;
  93   PRUint32  mFreeEntries;
  94   void*     mChunkListHead;
  95 #if 0
  96   PRLock*   mLock;
  97
  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)
 103   NS_DECL_OWNINGTHREAD
 104
 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); }
 109 #else
 110   void InitLock ()    { }
 111   void DestroyLock () { }
 112   void Lock ()        { }
 113   void Unlock ()      { }
 114 #endif
 115
 116   void* AllocChunk (PRUint32 aEntries, void* aNextChunk, nsRegion::RgnRect* aTailDest)
 117   {
 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*));
 121
 122     for (PRUint32 cnt = 0 ; cnt < aEntries - 1 ; cnt++)
 123       pRect [cnt].next = &pRect [cnt + 1];
 124
 125     pRect [aEntries - 1].next = aTailDest;
 126
 127     return pBuf;
 128   }
 129
 130   void FreeChunk (void* aChunk) {  delete [] (PRUint8 *) aChunk;  }
 131   void* NextChunk (void* aThisChunk) const { return *static_cast<void**>(aThisChunk); }
 132
 133   nsRegion::RgnRect* ChunkHead (void* aThisChunk) const
 134   {   return reinterpret_cast<nsRegion::RgnRect*>(static_cast<PRUint8*>(aThisChunk) + sizeof (void*));  }
 135
 136 public:
 137   RgnRectMemoryAllocator (PRUint32 aNumOfEntries);
 138  ~RgnRectMemoryAllocator ();
 139
 140   nsRegion::RgnRect* Alloc ();
 141   void Free (nsRegion::RgnRect* aRect);
 142 };
 143
 144
 145 RgnRectMemoryAllocator::RgnRectMemoryAllocator (PRUint32 aNumOfEntries)
 146 {
 147   InitLock ();
 148   mChunkListHead = AllocChunk (aNumOfEntries, nsnull, nsnull);
 149   mFreeEntries   = aNumOfEntries;
 150   mFreeListHead  = ChunkHead (mChunkListHead);
 151 }
 152
 153 RgnRectMemoryAllocator::~RgnRectMemoryAllocator ()
 154 {
 155   while (mChunkListHead)
 156   {
 157     void* tmp = mChunkListHead;
 158     mChunkListHead = NextChunk (mChunkListHead);
 159     FreeChunk (tmp);
 160   }
 161
 162 #if 0
 163   /*
 164    * As a static object this class outlives any library which would implement
 165    * locking. So we intentionally leak the 'lock'.
 166    *
 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.
 174    */
 175   DestroyLock ();
 176 #endif
 177 }
 178
 179 nsRegion::RgnRect* RgnRectMemoryAllocator::Alloc ()
 180 {
 181   Lock ();
 182
 183   if (mFreeEntries == 0)
 184   {
 185     mChunkListHead = AllocChunk (INCR_MEM_CHUNK_ENTRIES, mChunkListHead, mFreeListHead);
 186     mFreeEntries   = INCR_MEM_CHUNK_ENTRIES;
 187     mFreeListHead  = ChunkHead (mChunkListHead);
 188   }
 189
 190   nsRegion::RgnRect* tmp = mFreeListHead;
 191   mFreeListHead = mFreeListHead->next;
 192   mFreeEntries--;
 193   Unlock ();
 194
 195   return tmp;
 196 }
 197
 198 void RgnRectMemoryAllocator::Free (nsRegion::RgnRect* aRect)
 199 {
 200   Lock ();
 201   mFreeEntries++;
 202   aRect->next = mFreeListHead;
 203   mFreeListHead = aRect;
 204   Unlock ();
 205 }
 206
 207
 208 // Global pool for nsRegion::RgnRect allocation
 209 static RgnRectMemoryAllocator gRectPool (INIT_MEM_CHUNK_ENTRIES);
 210
 211
 212 void* nsRegion::RgnRect::operator new (size_t) CPP_THROW_NEW
 213 {
 214   return gRectPool.Alloc ();
 215 }
 216
 217 void nsRegion::RgnRect::operator delete (void* aRect, size_t)
 218 {
 219   gRectPool.Free (static_cast<RgnRect*>(aRect));
 220 }
 221
 222
 223
 224 void nsRegion::Init()
 225 {
 226   mRectListHead.prev = mRectListHead.next = &mRectListHead;
 227   mCurRect = &mRectListHead;
 228   mRectCount = 0;
 229   mBoundRect.SetRect (0, 0, 0, 0);
 230 }
 231
 232 inline void nsRegion::InsertBefore (RgnRect* aNewRect, RgnRect* aRelativeRect)
 233 {
 234   aNewRect->prev = aRelativeRect->prev;
 235   aNewRect->next = aRelativeRect;
 236   aRelativeRect->prev->next = aNewRect;
 237   aRelativeRect->prev = aNewRect;
 238   mCurRect = aNewRect;
 239   mRectCount++;
 240 }
 241
 242 inline void nsRegion::InsertAfter (RgnRect* aNewRect, RgnRect* aRelativeRect)
 243 {
 244   aNewRect->prev = aRelativeRect;
 245   aNewRect->next = aRelativeRect->next;
 246   aRelativeRect->next->prev = aNewRect;
 247   aRelativeRect->next = aNewRect;
 248   mCurRect = aNewRect;
 249   mRectCount++;
 250 }
 251
 252
 253 // Adjust the number of rectangles in region.
 254 // Content of rectangles should be changed by caller.
 255
 256 void nsRegion::SetToElements (PRUint32 aCount)
 257 {
 258   if (mRectCount < aCount)        // Add missing rectangles
 259   {
 260     PRUint32 InsertCount = aCount - mRectCount;
 261     mRectCount = aCount;
 262     RgnRect* pPrev = &mRectListHead;
 263     RgnRect* pNext = mRectListHead.next;
 264
 265     while (InsertCount--)
 266     {
 267       mCurRect = new RgnRect;
 268       mCurRect->prev = pPrev;
 269       pPrev->next = mCurRect;
 270       pPrev = mCurRect;
 271     }
 272
 273     pPrev->next = pNext;
 274     pNext->prev = pPrev;
 275   } else
 276   if (mRectCount > aCount)        // Remove unnecessary rectangles
 277   {
 278     PRUint32 RemoveCount = mRectCount - aCount;
 279     mRectCount = aCount;
 280     mCurRect = mRectListHead.next;
 281
 282     while (RemoveCount--)
 283     {
 284       RgnRect* tmp = mCurRect;
 285       mCurRect = mCurRect->next;
 286       delete tmp;
 287     }
 288
 289     mRectListHead.next = mCurRect;
 290     mCurRect->prev = &mRectListHead;
 291   }
 292 }
 293
 294
 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.
 300
 301 inline void nsRegion::SaveLinkChain ()
 302 {
 303   RgnRect* pRect = &mRectListHead;
 304
 305   do
 306   {
 307     pRect->prev = pRect->next;
 308     pRect = pRect->next;
 309   } while (pRect != &mRectListHead);
 310 }
 311
 312
 313 inline void nsRegion::RestoreLinkChain ()
 314 {
 315   RgnRect* pPrev = &mRectListHead;
 316   RgnRect* pRect = mRectListHead.next = mRectListHead.prev;
 317
 318   while (pRect != &mRectListHead)
 319   {
 320     pRect->next = pRect->prev;
 321     pRect->prev = pPrev;
 322     pPrev = pRect;
 323     pRect = pRect->next;
 324   }
 325
 326   mRectListHead.prev = pPrev;
 327 }
 328
 329
 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 ()
 333
 334 void nsRegion::InsertInPlace (RgnRect* aRect, PRBool aOptimizeOnFly)
 335 {
 336   if (mRectCount == 0)
 337     InsertAfter (aRect, &mRectListHead);
 338   else
 339   {
 340     if (aRect->y > mCurRect->y)
 341     {
 342       mRectListHead.y = PR_INT32_MAX;
 343
 344       while (aRect->y > mCurRect->next->y)
 345         mCurRect = mCurRect->next;
 346
 347       while (aRect->y == mCurRect->next->y && aRect->x > mCurRect->next->x)
 348         mCurRect = mCurRect->next;
 349
 350       InsertAfter (aRect, mCurRect);
 351     } else
 352     if (aRect->y < mCurRect->y)
 353     {
 354       mRectListHead.y = PR_INT32_MIN;
 355
 356       while (aRect->y < mCurRect->prev->y)
 357         mCurRect = mCurRect->prev;
 358
 359       while (aRect->y == mCurRect->prev->y && aRect->x < mCurRect->prev->x)
 360         mCurRect = mCurRect->prev;
 361
 362       InsertBefore (aRect, mCurRect);
 363     } else
 364     {
 365       if (aRect->x > mCurRect->x)
 366       {
 367         mRectListHead.y = PR_INT32_MAX;
 368
 369         while (aRect->y == mCurRect->next->y && aRect->x > mCurRect->next->x)
 370           mCurRect = mCurRect->next;
 371
 372         InsertAfter (aRect, mCurRect);
 373       } else
 374       {
 375         mRectListHead.y = PR_INT32_MIN;
 376
 377         while (aRect->y == mCurRect->prev->y && aRect->x < mCurRect->prev->x)
 378           mCurRect = mCurRect->prev;
 379
 380         InsertBefore (aRect, mCurRect);
 381       }
 382     }
 383   }
 384
 385
 386   if (aOptimizeOnFly)
 387   {
 388     if (mRectCount == 1)
 389       mBoundRect = *mCurRect;
 390     else
 391     {
 392       mBoundRect.UnionRect (mBoundRect, *mCurRect);
 393
 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;
 400
 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)
 404       {
 405         mCurRect->width += mCurRect->next->width;
 406         delete Remove (mCurRect->next);
 407       }
 408
 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)
 412       {
 413         mCurRect->height += mCurRect->next->height;
 414         delete Remove (mCurRect->next);
 415       }
 416     }
 417   }
 418 }
 419
 420
 421 nsRegion::RgnRect* nsRegion::Remove (RgnRect* aRect)
 422 {
 423   aRect->prev->next = aRect->next;
 424   aRect->next->prev = aRect->prev;
 425   mRectCount--;
 426
 427   if (mCurRect == aRect)
 428     mCurRect = (aRect->next != &mRectListHead) ? aRect->next : aRect->prev;
 429
 430   return aRect;
 431 }
 432
 433
 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
 437
 438 void nsRegion::Optimize ()
 439 {
 440   if (mRectCount == 0)
 441     mBoundRect.SetRect (0, 0, 0, 0);
 442   else
 443   {
 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;
 449
 450     while (pRect != &mRectListHead)
 451     {
 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)
 455       {
 456         pRect->width += pRect->next->width;
 457         delete Remove (pRect->next);
 458       }
 459
 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)
 463       {
 464         pRect->height += pRect->next->height;
 465         delete Remove (pRect->next);
 466       }
 467
 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 ();
 472
 473       pRect = pRect->next;
 474     }
 475
 476     mBoundRect.width  = xmost - mBoundRect.x;
 477     mBoundRect.height = ymost - mBoundRect.y;
 478   }
 479 }
 480
 481
 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.
 485
 486 void nsRegion::MoveInto (nsRegion& aDestRegion, const RgnRect* aStartRect)
 487 {
 488   RgnRect* pRect = const_cast<RgnRect*>(aStartRect);
 489   RgnRect* pPrev = pRect->prev;
 490
 491   while (pRect != &mRectListHead)
 492   {
 493     RgnRect* next = pRect->next;
 494     aDestRegion.InsertInPlace (pRect);
 495
 496     mRectCount--;
 497     pRect = next;
 498   }
 499
 500   pPrev->next = &mRectListHead;
 501   mRectListHead.prev = pPrev;
 502   mCurRect = mRectListHead.next;
 503 }
 504
 505
 506 // Merge two non-overlapping regions into one.
 507 // Automatically optimize region by calling Optimize ()
 508
 509 void nsRegion::Merge (const nsRegion& aRgn1, const nsRegion& aRgn2)
 510 {
 511   if (aRgn1.mRectCount == 0)            // Region empty. Result is equal to other region
 512     Copy (aRgn2);
 513   else
 514   if (aRgn2.mRectCount == 0)            // Region empty. Result is equal to other region
 515     Copy (aRgn1);
 516   if (aRgn1.mRectCount == 1)            // Region is single rectangle. Optimize on fly
 517   {
 518     RgnRect* TmpRect = new RgnRect (*aRgn1.mRectListHead.next);
 519     Copy (aRgn2);
 520     InsertInPlace (TmpRect, PR_TRUE);
 521   } else
 522   if (aRgn2.mRectCount == 1)            // Region is single rectangle. Optimize on fly
 523   {
 524     RgnRect* TmpRect = new RgnRect (*aRgn2.mRectListHead.next);
 525     Copy (aRgn1);
 526     InsertInPlace (TmpRect, PR_TRUE);
 527   } else
 528   {
 529     const nsRegion* pCopyRegion, *pInsertRegion;
 530
 531     // Determine which region contains more rectangles. Copy the larger one
 532     if (aRgn1.mRectCount >= aRgn2.mRectCount)
 533     {
 534       pCopyRegion = &aRgn1;
 535       pInsertRegion = &aRgn2;
 536     } else
 537     {
 538       pCopyRegion = &aRgn2;
 539       pInsertRegion = &aRgn1;
 540     }
 541
 542     if (pInsertRegion == this)          // Do merge in-place
 543       pInsertRegion = pCopyRegion;
 544     else
 545       Copy (*pCopyRegion);
 546
 547     const RgnRect* pSrcRect = pInsertRegion->mRectListHead.next;
 548
 549     while (pSrcRect != &pInsertRegion->mRectListHead)
 550     {
 551       InsertInPlace (new RgnRect (*pSrcRect));
 552
 553       pSrcRect = pSrcRect->next;
 554     }
 555
 556     Optimize ();
 557   }
 558 }
 559
 560
 561 nsRegion& nsRegion::Copy (const nsRegion& aRegion)
 562 {
 563   if (&aRegion == this)
 564     return *this;
 565
 566   if (aRegion.mRectCount == 0)
 567     SetEmpty ();
 568   else
 569   {
 570     SetToElements (aRegion.mRectCount);
 571
 572     const RgnRect* pSrc = aRegion.mRectListHead.next;
 573     RgnRect* pDest = mRectListHead.next;
 574
 575     while (pSrc != &aRegion.mRectListHead)
 576     {
 577       *pDest = *pSrc;
 578
 579       pSrc  = pSrc->next;
 580       pDest = pDest->next;
 581     }
 582
 583     mCurRect = mRectListHead.next;
 584     mBoundRect = aRegion.mBoundRect;
 585   }
 586
 587   return *this;
 588 }
 589
 590
 591 nsRegion& nsRegion::Copy (const nsRect& aRect)
 592 {
 593   if (aRect.IsEmpty ())
 594     SetEmpty ();
 595   else
 596   {
 597     SetToElements (1);
 598     *mRectListHead.next = static_cast<const RgnRect&>(aRect);
 599     mBoundRect = static_cast<const nsRectFast&>(aRect);
 600   }
 601
 602   return *this;
 603 }
 604
 605
 606 nsRegion& nsRegion::And (const nsRegion& aRgn1, const nsRegion& aRgn2)
 607 {
 608   if (&aRgn1 == &aRgn2)                                       // And with self
 609     Copy (aRgn1);
 610   else
 611   if (aRgn1.mRectCount == 0 || aRgn2.mRectCount == 0)         // If either region is empty then result is empty
 612     SetEmpty ();
 613   else
 614   {
 615     nsRectFast TmpRect;
 616
 617     if (aRgn1.mRectCount == 1 && aRgn2.mRectCount == 1)       // Intersect rectangle with rectangle
 618     {
 619       TmpRect.IntersectRect (*aRgn1.mRectListHead.next, *aRgn2.mRectListHead.next);
 620       Copy (TmpRect);
 621     } else
 622     {
 623       if (!aRgn1.mBoundRect.Intersects (aRgn2.mBoundRect))    // Regions do not intersect
 624         SetEmpty ();
 625       else
 626       {
 627         // Region is simple rectangle and it fully overlays other region
 628         if (aRgn1.mRectCount == 1 && aRgn1.mBoundRect.Contains (aRgn2.mBoundRect))
 629           Copy (aRgn2);
 630         else
 631         // Region is simple rectangle and it fully overlays other region
 632         if (aRgn2.mRectCount == 1 && aRgn2.mBoundRect.Contains (aRgn1.mBoundRect))
 633           Copy (aRgn1);
 634         else
 635         {
 636           nsRegion TmpRegion;
 637           nsRegion* pSrcRgn1 = const_cast<nsRegion*>(&aRgn1);
 638           nsRegion* pSrcRgn2 = const_cast<nsRegion*>(&aRgn2);
 639
 640           if (&aRgn1 == this)     // Copy region if it is both source and result
 641           {
 642             TmpRegion.Copy (aRgn1);
 643             pSrcRgn1 = &TmpRegion;
 644           }
 645
 646           if (&aRgn2 == this)     // Copy region if it is both source and result
 647           {
 648             TmpRegion.Copy (aRgn2);
 649             pSrcRgn2 = &TmpRegion;
 650           }
 651
 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 ())
 654           {
 655             nsRegion* Tmp = pSrcRgn1;
 656             pSrcRgn1 = pSrcRgn2;
 657             pSrcRgn2 = Tmp;
 658           }
 659
 660
 661           SetToElements (0);
 662           pSrcRgn2->SaveLinkChain ();
 663
 664           pSrcRgn1->mRectListHead.y = PR_INT32_MAX;
 665           pSrcRgn2->mRectListHead.y = PR_INT32_MAX;
 666
 667           for (RgnRect* pSrcRect1 = pSrcRgn1->mRectListHead.next ;
 668                pSrcRect1->y < pSrcRgn2->mBoundRect.YMost () ; pSrcRect1 = pSrcRect1->next)
 669           {
 670             if (pSrcRect1->Intersects (pSrcRgn2->mBoundRect))   // Rectangle intersects region. Process each rectangle
 671             {
 672               RgnRect* pPrev2 = &pSrcRgn2->mRectListHead;
 673
 674               for (RgnRect* pSrcRect2 = pSrcRgn2->mRectListHead.next ;
 675                    pSrcRect2->y < pSrcRect1->YMost () ; pSrcRect2 = pSrcRect2->next)
 676               {
 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
 680                   continue;
 681                 }
 682
 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));
 687                   continue;
 688                 }
 689
 690
 691                 if (TmpRect.IntersectRect (*pSrcRect1, *pSrcRect2))
 692                   InsertInPlace (new RgnRect (TmpRect));
 693
 694                 pPrev2 = pSrcRect2;
 695               }
 696             }
 697           }
 698
 699           pSrcRgn2->RestoreLinkChain ();
 700           Optimize ();
 701         }
 702       }
 703     }
 704   }
 705
 706   return *this;
 707 }
 708
 709
 710 nsRegion& nsRegion::And (const nsRegion& aRegion, const nsRect& aRect)
 711 {
 712   // If either region or rectangle is empty then result is empty
 713   if (aRegion.mRectCount == 0 || aRect.IsEmpty ())
 714     SetEmpty ();
 715   else                            // Intersect region with rectangle
 716   {
 717     const nsRectFast& aRectFast = static_cast<const nsRectFast&>(aRect);
 718     nsRectFast TmpRect;
 719
 720     if (aRegion.mRectCount == 1)  // Intersect rectangle with rectangle
 721     {
 722       TmpRect.IntersectRect (*aRegion.mRectListHead.next, aRectFast);
 723       Copy (TmpRect);
 724     } else                        // Intersect complex region with rectangle
 725     {
 726       if (!aRectFast.Intersects (aRegion.mBoundRect))   // Rectangle does not intersect region
 727         SetEmpty ();
 728       else
 729       {
 730         if (aRectFast.Contains (aRegion.mBoundRect))    // Rectangle fully overlays region
 731           Copy (aRegion);
 732         else
 733         {
 734           nsRegion TmpRegion;
 735           nsRegion* pSrcRegion = const_cast<nsRegion*>(&aRegion);
 736
 737           if (&aRegion == this)   // Copy region if it is both source and result
 738           {
 739             TmpRegion.Copy (aRegion);
 740             pSrcRegion = &TmpRegion;
 741           }
 742
 743           SetToElements (0);
 744           pSrcRegion->mRectListHead.y = PR_INT32_MAX;
 745
 746           for (const RgnRect* pSrcRect = pSrcRegion->mRectListHead.next ;
 747                pSrcRect->y < aRectFast.YMost () ; pSrcRect = pSrcRect->next)
 748           {
 749             if (TmpRect.IntersectRect (*pSrcRect, aRectFast))
 750               InsertInPlace (new RgnRect (TmpRect));
 751           }
 752
 753           Optimize ();
 754         }
 755       }
 756     }
 757   }
 758
 759   return *this;
 760 }
 761
 762
 763 nsRegion& nsRegion::Or (const nsRegion& aRgn1, const nsRegion& aRgn2)
 764 {
 765   if (&aRgn1 == &aRgn2)                 // Or with self
 766     Copy (aRgn1);
 767   else
 768   if (aRgn1.mRectCount == 0)            // Region empty. Result is equal to other region
 769     Copy (aRgn2);
 770   else
 771   if (aRgn2.mRectCount == 0)            // Region empty. Result is equal to other region
 772     Copy (aRgn1);
 773   else
 774   {
 775     if (!aRgn1.mBoundRect.Intersects (aRgn2.mBoundRect))  // Regions do not intersect
 776       Merge (aRgn1, aRgn2);
 777     else
 778     {
 779       // Region is simple rectangle and it fully overlays other region
 780       if (aRgn1.mRectCount == 1 && aRgn1.mBoundRect.Contains (aRgn2.mBoundRect))
 781         Copy (aRgn1);
 782       else
 783       // Region is simple rectangle and it fully overlays other region
 784       if (aRgn2.mRectCount == 1 && aRgn2.mBoundRect.Contains (aRgn1.mBoundRect))
 785         Copy (aRgn2);
 786       else
 787       {
 788         nsRegion TmpRegion;
 789         aRgn1.SubRegion (aRgn2, TmpRegion);               // Get only parts of region which not overlap the other region
 790         Copy (aRgn2);
 791         TmpRegion.MoveInto (*this);
 792         Optimize ();
 793       }
 794     }
 795   }
 796
 797   return *this;
 798 }
 799
 800
 801 nsRegion& nsRegion::Or (const nsRegion& aRegion, const nsRect& aRect)
 802 {
 803   if (aRegion.mRectCount == 0)          // Region empty. Result is equal to rectangle
 804     Copy (aRect);
 805   else
 806   if (aRect.IsEmpty ())                 // Rectangle is empty. Result is equal to region
 807     Copy (aRegion);
 808   else
 809   {
 810     const nsRectFast& aRectFast = static_cast<const nsRectFast&>(aRect);
 811
 812     if (!aRectFast.Intersects (aRegion.mBoundRect))     // Rectangle does not intersect region
 813     {
 814       Copy (aRegion);
 815       InsertInPlace (new RgnRect (aRectFast), PR_TRUE);
 816     } else
 817     {
 818       // Region is simple rectangle and it fully overlays rectangle
 819       if (aRegion.mRectCount == 1 && aRegion.mBoundRect.Contains (aRectFast))
 820         Copy (aRegion);
 821       else
 822       if (aRectFast.Contains (aRegion.mBoundRect))      // Rectangle fully overlays region
 823         Copy (aRectFast);
 824       else
 825       {
 826         aRegion.SubRect (aRectFast, *this);             // Exclude from region parts that overlap the rectangle
 827         InsertInPlace (new RgnRect (aRectFast));
 828         Optimize ();
 829       }
 830     }
 831   }
 832
 833   return *this;
 834 }
 835
 836
 837 nsRegion& nsRegion::Xor (const nsRegion& aRgn1, const nsRegion& aRgn2)
 838 {
 839   if (&aRgn1 == &aRgn2)                 // Xor with self
 840     SetEmpty ();
 841   else
 842   if (aRgn1.mRectCount == 0)            // Region empty. Result is equal to other region
 843     Copy (aRgn2);
 844   else
 845   if (aRgn2.mRectCount == 0)            // Region empty. Result is equal to other region
 846     Copy (aRgn1);
 847   else
 848   {
 849     if (!aRgn1.mBoundRect.Intersects (aRgn2.mBoundRect))      // Regions do not intersect
 850       Merge (aRgn1, aRgn2);
 851     else
 852     {
 853       // Region is simple rectangle and it fully overlays other region
 854       if (aRgn1.mRectCount == 1 && aRgn1.mBoundRect.Contains (aRgn2.mBoundRect))
 855       {
 856         aRgn1.SubRegion (aRgn2, *this);
 857         Optimize ();
 858       } else
 859       // Region is simple rectangle and it fully overlays other region
 860       if (aRgn2.mRectCount == 1 && aRgn2.mBoundRect.Contains (aRgn1.mBoundRect))
 861       {
 862         aRgn2.SubRegion (aRgn1, *this);
 863         Optimize ();
 864       } else
 865       {
 866         nsRegion TmpRegion;
 867         aRgn1.SubRegion (aRgn2, TmpRegion);
 868         aRgn2.SubRegion (aRgn1, *this);
 869         TmpRegion.MoveInto (*this);
 870         Optimize ();
 871       }
 872     }
 873   }
 874
 875   return *this;
 876 }
 877
 878
 879 nsRegion& nsRegion::Xor (const nsRegion& aRegion, const nsRect& aRect)
 880 {
 881   if (aRegion.mRectCount == 0)          // Region empty. Result is equal to rectangle
 882     Copy (aRect);
 883   else
 884   if (aRect.IsEmpty ())                 // Rectangle is empty. Result is equal to region
 885     Copy (aRegion);
 886   else
 887   {
 888     const nsRectFast& aRectFast = static_cast<const nsRectFast&>(aRect);
 889
 890     if (!aRectFast.Intersects (aRegion.mBoundRect))     // Rectangle does not intersect region
 891     {
 892       Copy (aRegion);
 893       InsertInPlace (new RgnRect (aRectFast), PR_TRUE);
 894     } else
 895     {
 896       // Region is simple rectangle and it fully overlays rectangle
 897       if (aRegion.mRectCount == 1 && aRegion.mBoundRect.Contains (aRectFast))
 898       {
 899         aRegion.SubRect (aRectFast, *this);
 900         Optimize ();
 901       } else
 902       if (aRectFast.Contains (aRegion.mBoundRect))      // Rectangle fully overlays region
 903       {
 904         nsRegion TmpRegion;
 905         TmpRegion.Copy (aRectFast);
 906         TmpRegion.SubRegion (aRegion, *this);
 907         Optimize ();
 908       } else
 909       {
 910         nsRegion TmpRegion;
 911         TmpRegion.Copy (aRectFast);
 912         TmpRegion.SubRegion (aRegion, TmpRegion);
 913         aRegion.SubRect (aRectFast, *this);
 914         TmpRegion.MoveInto (*this);
 915         Optimize ();
 916       }
 917     }
 918   }
 919
 920   return *this;
 921 }
 922
 923
 924 nsRegion& nsRegion::Sub (const nsRegion& aRgn1, const nsRegion& aRgn2)
 925 {
 926   if (&aRgn1 == &aRgn2)         // Sub from self
 927     SetEmpty ();
 928   else
 929   if (aRgn1.mRectCount == 0)    // If source is empty then result is empty, too
 930     SetEmpty ();
 931   else
 932   if (aRgn2.mRectCount == 0)    // Nothing to subtract
 933     Copy (aRgn1);
 934   else
 935   {
 936     if (!aRgn1.mBoundRect.Intersects (aRgn2.mBoundRect))   // Regions do not intersect
 937       Copy (aRgn1);
 938     else
 939     {
 940       aRgn1.SubRegion (aRgn2, *this);
 941       Optimize ();
 942     }
 943   }
 944
 945   return *this;
 946 }
 947
 948
 949 nsRegion& nsRegion::Sub (const nsRegion& aRegion, const nsRect& aRect)
 950 {
 951   if (aRegion.mRectCount == 0)    // If source is empty then result is empty, too
 952     SetEmpty ();
 953   else
 954   if (aRect.IsEmpty ())           // Nothing to subtract
 955     Copy (aRegion);
 956   else
 957   {
 958     const nsRectFast& aRectFast = static_cast<const nsRectFast&>(aRect);
 959
 960     if (!aRectFast.Intersects (aRegion.mBoundRect))   // Rectangle does not intersect region
 961       Copy (aRegion);
 962     else
 963     {
 964       if (aRectFast.Contains (aRegion.mBoundRect))    // Rectangle fully overlays region
 965         SetEmpty ();
 966       else
 967       {
 968         aRegion.SubRect (aRectFast, *this);
 969         Optimize ();
 970       }
 971     }
 972   }
 973
 974   return *this;
 975 }
 976
 977 PRBool nsRegion::Contains (const nsRect& aRect) const
 978 {
 979   if (aRect.IsEmpty())
 980     return PR_TRUE;
 981   if (IsEmpty())
 982     return PR_FALSE;
 983   if (!IsComplex())
 984     return mBoundRect.Contains (aRect);
 985
 986   nsRegion tmpRgn;
 987   tmpRgn.Sub(aRect, *this);
 988   return tmpRgn.IsEmpty();
 989 }
 990
 991 PRBool nsRegion::Intersects (const nsRect& aRect) const
 992 {
 993   if (aRect.IsEmpty() || IsEmpty())
 994     return PR_FALSE;
 995
 996   const RgnRect* r = mRectListHead.next;
 997   while (r != &mRectListHead)
 998   {
 999     if (r->Intersects(aRect))
1000       return PR_TRUE;
1001     r = r->next;
1002   }
1003   return PR_FALSE;
1004 }
1005
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).
1010
1011 void nsRegion::SubRegion (const nsRegion& aRegion, nsRegion& aResult) const
1012 {
1013   if (aRegion.mRectCount == 1)    // Subtract simple rectangle
1014   {
1015     if (aRegion.mBoundRect.Contains (mBoundRect))
1016       aResult.SetEmpty ();
1017     else
1018       SubRect (*aRegion.mRectListHead.next, aResult);
1019   } else
1020   {
1021     nsRegion TmpRegion, CompletedRegion;
1022     const nsRegion* pSubRgn = &aRegion;
1023
1024     if (&aResult == &aRegion)     // Copy region if it is both source and result
1025     {
1026       TmpRegion.Copy (aRegion);
1027       pSubRgn = &TmpRegion;
1028     }
1029
1030     const RgnRect* pSubRect = pSubRgn->mRectListHead.next;
1031
1032     SubRect (*pSubRect, aResult, CompletedRegion);
1033     pSubRect = pSubRect->next;
1034
1035     while (pSubRect != &pSubRgn->mRectListHead)
1036     {
1037       aResult.SubRect (*pSubRect, aResult, CompletedRegion);
1038       pSubRect = pSubRect->next;
1039     }
1040
1041     CompletedRegion.MoveInto (aResult);
1042   }
1043 }
1044
1045
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).
1051 //
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.
1055
1056 void nsRegion::SubRect (const nsRectFast& aRect, nsRegion& aResult, nsRegion& aCompleted) const
1057 {
1058   nsRegion TmpRegion;
1059   const nsRegion* pSrcRegion = this;
1060
1061   if (&aResult == this)           // Copy region if it is both source and result
1062   {
1063     TmpRegion.Copy (*this);
1064     pSrcRegion = &TmpRegion;
1065   }
1066
1067   aResult.SetToElements (0);
1068
1069   (const_cast<nsRegion*>(pSrcRegion))->mRectListHead.y = PR_INT32_MAX;
1070   const RgnRect* pSrcRect = pSrcRegion->mRectListHead.next;
1071
1072   for ( ; pSrcRect->y < aRect.YMost () ; pSrcRect = pSrcRect->next)
1073   {
1074     nsRectFast TmpRect;
1075
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)
1080     {
1081       aCompleted.InsertInPlace (new RgnRect (*pSrcRect));
1082       continue;
1083     }
1084
1085     if (!TmpRect.IntersectRect (*pSrcRect, aRect))
1086       aResult.InsertInPlace (new RgnRect (*pSrcRect));
1087     else
1088     {
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;
1107
1108       // There are 16 combinations how rectangles could intersect
1109
1110       if (bx <= ax && by <= ay)
1111       {
1112         if (bxm < axm && bym < aym)     // 1.
1113         {
1114           aResult.InsertInPlace (new RgnRect (ixm, ay, axm - ixm, ih));
1115           aResult.InsertInPlace (new RgnRect (ax, iym, aw, aym - iym));
1116         } else
1117         if (bxm >= axm && bym < aym)    // 2.
1118         {
1119           aResult.InsertInPlace (new RgnRect (ax, iym, aw, aym - iym));
1120         } else
1121         if (bxm < axm && bym >= aym)    // 3.
1122         {
1123           aResult.InsertInPlace (new RgnRect (ixm, ay, axm - ixm, ah));
1124         } else
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
1129         }
1130       } else
1131       if (bx > ax && by <= ay)
1132       {
1133         if (bxm < axm && bym < aym)     // 5.
1134         {
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));
1138         } else
1139         if (bxm >= axm && bym < aym)    // 6.
1140         {
1141           aResult.InsertInPlace (new RgnRect (ax, ay, ix - ax, ih));
1142           aResult.InsertInPlace (new RgnRect (ax, iym, aw, aym - iym));
1143         } else
1144         if (bxm < axm && bym >= aym)    // 7.
1145         {
1146           aResult.InsertInPlace (new RgnRect (ax, ay, ix - ax, ah));
1147           aResult.InsertInPlace (new RgnRect (ixm, ay, axm - ixm, ah));
1148         } else
1149         if (bxm >= axm && bym >= aym)   // 8.
1150         {
1151           aResult.InsertInPlace (new RgnRect (ax, ay, ix - ax, ah));
1152         }
1153       } else
1154       if (bx <= ax && by > ay)
1155       {
1156         if (bxm < axm && bym < aym)     // 9.
1157         {
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));
1161         } else
1162         if (bxm >= axm && bym < aym)    // 10.
1163         {
1164           aResult.InsertInPlace (new RgnRect (ax, ay, aw, iy - ay));
1165           aResult.InsertInPlace (new RgnRect (ax, iym, aw, aym - iym));
1166         } else
1167         if (bxm < axm && bym >= aym)    // 11.
1168         {
1169           aResult.InsertInPlace (new RgnRect (ax, ay, aw, iy - ay));
1170           aResult.InsertInPlace (new RgnRect (ixm, iy, axm - ixm, ih));
1171         } else
1172         if (bxm >= axm && bym >= aym)   // 12.
1173         {
1174           aResult.InsertInPlace (new RgnRect (ax, ay, aw, iy - ay));
1175         }
1176       } else
1177       if (bx > ax && by > ay)
1178       {
1179         if (bxm < axm && bym < aym)     // 13.
1180         {
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));
1185
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
1188           break;
1189         } else
1190         if (bxm >= axm && bym < aym)    // 14.
1191         {
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));
1195         } else
1196         if (bxm < axm && bym >= aym)    // 15.
1197         {
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));
1201         } else
1202         if (bxm >= axm && bym >= aym)   // 16.
1203         {
1204           aResult.InsertInPlace (new RgnRect (ax, ay, aw, iy - ay));
1205           aResult.InsertInPlace (new RgnRect (ax, iy, ix - ax, ih));
1206         }
1207       }
1208     }
1209   }
1210
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);
1215   else
1216   {
1217     while (pSrcRect != &pSrcRegion->mRectListHead)
1218     {
1219       aResult.InsertInPlace (new RgnRect (*pSrcRect));
1220       pSrcRect = pSrcRect->next;
1221     }
1222   }
1223 }
1224
1225
1226 PRBool nsRegion::IsEqual (const nsRegion& aRegion) const
1227 {
1228   if (mRectCount == 0)
1229     return (aRegion.mRectCount == 0) ? PR_TRUE : PR_FALSE;
1230
1231   if (aRegion.mRectCount == 0)
1232     return (mRectCount == 0) ? PR_TRUE : PR_FALSE;
1233
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.
1237   {
1238     if (mBoundRect != aRegion.mBoundRect)         // If regions are equal then bounding rectangles should match
1239       return PR_FALSE;
1240     else
1241     {
1242       nsRegion TmpRegion;
1243       TmpRegion.Xor (*this, aRegion);             // Get difference between two regions
1244
1245       return (TmpRegion.mRectCount == 0);
1246     }
1247   }
1248 }
1249
1250
1251 void nsRegion::MoveBy (nsPoint aPt)
1252 {
1253   if (aPt.x || aPt.y)
1254   {
1255     RgnRect* pRect = mRectListHead.next;
1256
1257     while (pRect != &mRectListHead)
1258     {
1259       pRect->MoveBy (aPt.x, aPt.y);
1260       pRect = pRect->next;
1261     }
1262
1263     mBoundRect.MoveBy (aPt.x, aPt.y);
1264   }
1265 }
1266
1267 void nsRegion::SimplifyOutward (PRUint32 aMaxRects)
1268 {
1269   NS_ASSERTION(aMaxRects >= 1, "Invalid max rect count");
1270
1271   if (mRectCount <= aMaxRects)
1272     return;
1273
1274   *this = GetBounds();
1275 }
1276
1277 void nsRegion::SimplifyInward (PRUint32 aMaxRects)
1278 {
1279   NS_ASSERTION(aMaxRects >= 1, "Invalid max rect count");
1280
1281   if (mRectCount <= aMaxRects)
1282     return;
1283
1284   SetEmpty();
1285 }
1286
1287 void nsRegion::SimpleSubtract (const nsRect& aRect)
1288 {
1289   if (aRect.IsEmpty())
1290     return;
1291
1292   // protect against aRect being one of our own rectangles
1293   nsRect param = aRect;
1294   RgnRect* r = mRectListHead.next;
1295   while (r != &mRectListHead)
1296   {
1297     RgnRect* next = r->next;
1298     if (param.Contains(*r)) {
1299       delete Remove(r);
1300     }
1301     r = next;
1302   }
1303
1304   Optimize();
1305 }
1306
1307 void nsRegion::SimpleSubtract (const nsRegion& aRegion)
1308 {
1309   if (aRegion.IsEmpty())
1310     return;
1311
1312   if (&aRegion == this) {
1313     SetEmpty();
1314     return;
1315   }
1316
1317   const RgnRect* r = aRegion.mRectListHead.next;
1318   while (r != &aRegion.mRectListHead)
1319   {
1320     SimpleSubtract(*r);
1321     r = r->next;
1322   }
1323
1324   Optimize();
1325 }