Back to index

lightning-sunbird  0.9+nobinonly
nsSpaceManager.cpp
Go to the documentation of this file.
00001 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
00002 /* ***** BEGIN LICENSE BLOCK *****
00003  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00004  *
00005  * The contents of this file are subject to the Mozilla Public License Version
00006  * 1.1 (the "License"); you may not use this file except in compliance with
00007  * the License. You may obtain a copy of the License at
00008  * http://www.mozilla.org/MPL/
00009  *
00010  * Software distributed under the License is distributed on an "AS IS" basis,
00011  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00012  * for the specific language governing rights and limitations under the
00013  * License.
00014  *
00015  * The Original Code is mozilla.org code.
00016  *
00017  * The Initial Developer of the Original Code is
00018  * Netscape Communications Corporation.
00019  * Portions created by the Initial Developer are Copyright (C) 1998
00020  * the Initial Developer. All Rights Reserved.
00021  *
00022  * Contributor(s):
00023  *   Pierre Phaneuf <pp@ludusdesign.com>
00024  *
00025  * Alternatively, the contents of this file may be used under the terms of
00026  * either of the GNU General Public License Version 2 or later (the "GPL"),
00027  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00028  * in which case the provisions of the GPL or the LGPL are applicable instead
00029  * of those above. If you wish to allow use of your version of this file only
00030  * under the terms of either the GPL or the LGPL, and not to allow others to
00031  * use your version of this file under the terms of the MPL, indicate your
00032  * decision by deleting the provisions above and replace them with the notice
00033  * and other provisions required by the GPL or the LGPL. If you do not delete
00034  * the provisions above, a recipient may use your version of this file under
00035  * the terms of any one of the MPL, the GPL or the LGPL.
00036  *
00037  * ***** END LICENSE BLOCK ***** */
00038 #include "nsSpaceManager.h"
00039 #include "nsPoint.h"
00040 #include "nsRect.h"
00041 #include "nsSize.h"
00042 #include <stdlib.h>
00043 #include "nsVoidArray.h"
00044 #include "nsIFrame.h"
00045 #include "nsString.h"
00046 #include "nsIPresShell.h"
00047 #include "nsMemory.h"
00048 #include "nsHTMLReflowState.h"
00049 #include "nsHashSets.h"
00050 #ifdef DEBUG
00051 #include "nsIFrameDebug.h"
00052 #endif
00053 
00055 // BandList
00056 
00057 PRInt32 nsSpaceManager::sCachedSpaceManagerCount = 0;
00058 void* nsSpaceManager::sCachedSpaceManagers[NS_SPACE_MANAGER_CACHE_SIZE];
00059 
00060 #define NSCOORD_MIN (-2147483647 - 1) /* minimum signed value */
00061 
00062 nsSpaceManager::BandList::BandList()
00063   : nsSpaceManager::BandRect(NSCOORD_MIN, NSCOORD_MIN, NSCOORD_MIN, NSCOORD_MIN, (nsIFrame*)nsnull)
00064 {
00065   PR_INIT_CLIST(this);
00066   mNumFrames = 0;
00067 }
00068 
00069 void
00070 nsSpaceManager::BandList::Clear()
00071 {
00072   if (!IsEmpty()) {
00073     BandRect* bandRect = Head();
00074   
00075     while (bandRect != this) {
00076       BandRect* nxt = bandRect->Next();
00077   
00078       delete bandRect;
00079       bandRect = nxt;
00080     }
00081   
00082     PR_INIT_CLIST(this);
00083   }
00084 }
00085 
00087 
00088 // PresShell Arena allocate callback (for nsIntervalSet use below)
00089 PR_STATIC_CALLBACK(void*)
00090 PSArenaAllocCB(size_t aSize, void* aClosure)
00091 {
00092   return NS_STATIC_CAST(nsIPresShell*, aClosure)->AllocateFrame(aSize);
00093 }
00094 
00095 // PresShell Arena free callback (for nsIntervalSet use below)
00096 PR_STATIC_CALLBACK(void)
00097 PSArenaFreeCB(size_t aSize, void* aPtr, void* aClosure)
00098 {
00099   NS_STATIC_CAST(nsIPresShell*, aClosure)->FreeFrame(aSize, aPtr);
00100 }
00101 
00103 // nsSpaceManager
00104 
00105 MOZ_DECL_CTOR_COUNTER(nsSpaceManager)
00106 
00107 nsSpaceManager::nsSpaceManager(nsIPresShell* aPresShell, nsIFrame* aFrame)
00108   : mFrame(aFrame),
00109     mLowestTop(NSCOORD_MIN),
00110     mFloatDamage(PSArenaAllocCB, PSArenaFreeCB, aPresShell)
00111 {
00112   MOZ_COUNT_CTOR(nsSpaceManager);
00113   mX = mY = 0;
00114   mFrameInfoMap = nsnull;
00115   mSavedStates = nsnull;
00116 }
00117 
00118 void
00119 nsSpaceManager::ClearFrameInfo()
00120 {
00121   while (mFrameInfoMap) {
00122     FrameInfo*  next = mFrameInfoMap->mNext;
00123     delete mFrameInfoMap;
00124     mFrameInfoMap = next;
00125   }
00126 }
00127 
00128 nsSpaceManager::~nsSpaceManager()
00129 {
00130   MOZ_COUNT_DTOR(nsSpaceManager);
00131   mBandList.Clear();
00132   ClearFrameInfo();
00133 
00134   NS_ASSERTION(!mSavedStates, "states remaining on state stack");
00135 
00136   while (mSavedStates && mSavedStates != &mAutoState){
00137     SpaceManagerState *state = mSavedStates;
00138     mSavedStates = state->mNext;
00139     delete state;
00140   }
00141 }
00142 
00143 // static
00144 void* nsSpaceManager::operator new(size_t aSize) CPP_THROW_NEW
00145 {
00146   if (sCachedSpaceManagerCount > 0) {
00147     // We have cached unused instances of this class, return a cached
00148     // instance in stead of always creating a new one.
00149     return sCachedSpaceManagers[--sCachedSpaceManagerCount];
00150   }
00151 
00152   // The cache is empty, this means we haveto create a new instance using
00153   // the global |operator new|.
00154   return nsMemory::Alloc(aSize);
00155 }
00156 
00157 void
00158 nsSpaceManager::operator delete(void* aPtr, size_t aSize)
00159 {
00160   if (!aPtr)
00161     return;
00162   // This space manager is no longer used, if there's still room in
00163   // the cache we'll cache this space manager, unless the layout
00164   // module was already shut down.
00165 
00166   if (sCachedSpaceManagerCount < NS_SPACE_MANAGER_CACHE_SIZE &&
00167       sCachedSpaceManagerCount >= 0) {
00168     // There's still space in the cache for more instances, put this
00169     // instance in the cache in stead of deleting it.
00170 
00171     sCachedSpaceManagers[sCachedSpaceManagerCount++] = aPtr;
00172     return;
00173   }
00174 
00175   // The cache is full, or the layout module has been shut down,
00176   // delete this space manager.
00177   nsMemory::Free(aPtr);
00178 }
00179 
00180 
00181 /* static */
00182 void nsSpaceManager::Shutdown()
00183 {
00184   // The layout module is being shut down, clean up the cache and
00185   // disable further caching.
00186 
00187   PRInt32 i;
00188 
00189   for (i = 0; i < sCachedSpaceManagerCount; i++) {
00190     void* spaceManager = sCachedSpaceManagers[i];
00191     if (spaceManager)
00192       nsMemory::Free(spaceManager);
00193   }
00194 
00195   // Disable futher caching.
00196   sCachedSpaceManagerCount = -1;
00197 }
00198 
00199 PRBool
00200 nsSpaceManager::XMost(nscoord& aXMost) const
00201 {
00202   nscoord xMost = 0;
00203   for (FrameInfo* fi = mFrameInfoMap; fi; fi = fi->mNext) {
00204     xMost = PR_MAX(xMost, fi->mRect.XMost());
00205   }
00206   aXMost = xMost;
00207   return !mBandList.IsEmpty();
00208 }
00209 
00210 PRBool
00211 nsSpaceManager::YMost(nscoord& aYMost) const
00212 {
00213   PRBool result;
00214 
00215   if (mBandList.IsEmpty()) {
00216     aYMost = 0;
00217     result = PR_FALSE;
00218 
00219   } else {
00220     BandRect* lastRect = mBandList.Tail();
00221 
00222     aYMost = lastRect->mBottom;
00223     result = PR_TRUE;
00224   }
00225 
00226   return result;
00227 }
00228 
00238 nsresult
00239 nsSpaceManager::GetBandAvailableSpace(const BandRect* aBand,
00240                                       nscoord         aY,
00241                                       const nsSize&   aMaxSize,
00242                                       nsBandData&     aBandData) const
00243 {
00244   nscoord          topOfBand = aBand->mTop;
00245   nscoord          localY = aY - mY;
00246   nscoord          height = PR_MIN(aBand->mBottom - aY, aMaxSize.height);
00247   nsBandTrapezoid* trapezoid = aBandData.mTrapezoids;
00248   nscoord          rightEdge = mX + aMaxSize.width;
00249 
00250   // Initialize the band data
00251   aBandData.mCount = 0;
00252 
00253   // Skip any rectangles that are to the left of the local coordinate space
00254   while (aBand->mTop == topOfBand) {
00255     if (aBand->mRight > mX) {
00256       break;
00257     }
00258 
00259     // Get the next rect in the band
00260     aBand = aBand->Next();
00261   }
00262 
00263   // This is used to track the current x-location within the band. This is in
00264   // world coordinates
00265   nscoord   left = mX;
00266 
00267   // Process the remaining rectangles that are within the clip width
00268   while ((aBand->mTop == topOfBand) && (aBand->mLeft < rightEdge)) {
00269     // Compare the left edge of the occupied space with the current left
00270     // coordinate
00271     if (aBand->mLeft > left) {
00272       // The rect is to the right of our current left coordinate, so we've
00273       // found some available space
00274       if (aBandData.mCount >= aBandData.mSize) {
00275         // Not enough space in the array of trapezoids
00276         aBandData.mCount += 2 * aBand->Length() + 2;  // estimate the number needed
00277         return NS_ERROR_FAILURE;
00278       }
00279       trapezoid->mState = nsBandTrapezoid::Available;
00280       trapezoid->mFrame = nsnull;
00281 
00282       // Assign the trapezoid a rectangular shape. The trapezoid must be in the
00283       // local coordinate space, so convert the current left coordinate
00284       *trapezoid = nsRect(left - mX, localY, aBand->mLeft - left, height);
00285 
00286       // Move to the next output rect
00287       trapezoid++;
00288       aBandData.mCount++;
00289     }
00290 
00291     // The rect represents unavailable space, so add another trapezoid
00292     if (aBandData.mCount >= aBandData.mSize) {
00293       // Not enough space in the array of trapezoids
00294       aBandData.mCount += 2 * aBand->Length() + 1;  // estimate the number needed
00295       return NS_ERROR_FAILURE;
00296     }
00297     if (1 == aBand->mNumFrames) {
00298       trapezoid->mState = nsBandTrapezoid::Occupied;
00299       trapezoid->mFrame = aBand->mFrame;
00300     } else {
00301       NS_ASSERTION(aBand->mNumFrames > 1, "unexpected frame count");
00302       trapezoid->mState = nsBandTrapezoid::OccupiedMultiple;
00303       trapezoid->mFrames = aBand->mFrames;
00304     }
00305 
00306     nscoord x = aBand->mLeft;
00307     // The first band can straddle the clip rect
00308     if (x < mX) {
00309       // Clip the left edge
00310       x = mX;
00311     }
00312 
00313     // Assign the trapezoid a rectangular shape. The trapezoid must be in the
00314     // local coordinate space, so convert the rects's left coordinate
00315     *trapezoid = nsRect(x - mX, localY, aBand->mRight - x, height);
00316 
00317     // Move to the next output rect
00318     trapezoid++;
00319     aBandData.mCount++;
00320 
00321     // Adjust our current x-location within the band
00322     left = aBand->mRight;
00323 
00324     // Move to the next rect within the band
00325     aBand = aBand->Next();
00326   }
00327 
00328   // No more rects left in the band. If we haven't yet reached the right edge,
00329   // then all the remaining space is available
00330   if (left < rightEdge || aBandData.mCount == 0) {
00331     if (aBandData.mCount >= aBandData.mSize) {
00332       // Not enough space in the array of trapezoids
00333       aBandData.mCount++;
00334       return NS_ERROR_FAILURE;
00335     }
00336     trapezoid->mState = nsBandTrapezoid::Available;
00337     trapezoid->mFrame = nsnull;
00338 
00339     // Assign the trapezoid a rectangular shape. The trapezoid must be in the
00340     // local coordinate space, so convert the current left coordinate
00341     *trapezoid = nsRect(left - mX, localY, rightEdge - left, height);
00342     aBandData.mCount++;
00343   }
00344 
00345   return NS_OK;
00346 }
00347 
00348 nsresult
00349 nsSpaceManager::GetBandData(nscoord       aYOffset,
00350                             const nsSize& aMaxSize,
00351                             nsBandData&   aBandData) const
00352 {
00353   NS_PRECONDITION(aBandData.mSize >= 1, "bad band data");
00354   nsresult  result = NS_OK;
00355 
00356   // Convert the y-offset to world coordinates
00357   nscoord   y = mY + aYOffset;
00358 
00359   // If there are no unavailable rects or the offset is below the bottommost
00360   // band, then all the space is available
00361   nscoord yMost;
00362   nscoord maxHeight = aMaxSize.height == NS_UNCONSTRAINEDSIZE ? NS_UNCONSTRAINEDSIZE 
00363     : PR_MAX(0, aMaxSize.height - aYOffset);
00364 
00365   if (!YMost(yMost) || (y >= yMost)) {
00366     // All the requested space is available
00367     aBandData.mCount = 1;
00368     aBandData.mTrapezoids[0] = nsRect(0, aYOffset, aMaxSize.width, maxHeight);
00369     aBandData.mTrapezoids[0].mState = nsBandTrapezoid::Available;
00370     aBandData.mTrapezoids[0].mFrame = nsnull;
00371   } else {
00372     // Find the first band that contains the y-offset or is below the y-offset
00373     NS_ASSERTION(!mBandList.IsEmpty(), "no bands");
00374     BandRect* band = mBandList.Head();
00375 
00376     aBandData.mCount = 0;
00377     while (nsnull != band) {
00378       if (band->mTop > y) {
00379         // The band is below the y-offset. The area between the y-offset and
00380         // the top of the band is available
00381         aBandData.mCount = 1;
00382         aBandData.mTrapezoids[0] =
00383           nsRect(0, aYOffset, aMaxSize.width, PR_MIN(band->mTop - y, maxHeight));
00384         aBandData.mTrapezoids[0].mState = nsBandTrapezoid::Available;
00385         aBandData.mTrapezoids[0].mFrame = nsnull;
00386         break;
00387       } else if (y < band->mBottom) {
00388         // The band contains the y-offset. Return a list of available and
00389         // unavailable rects within the band
00390         return GetBandAvailableSpace(band, y, nsSize(aMaxSize.width, maxHeight), aBandData);
00391       } else {
00392         // Skip to the next band
00393         band = GetNextBand(band);
00394       }
00395     }
00396   }
00397 
00398   NS_POSTCONDITION(aBandData.mCount > 0, "unexpected band data count");
00399   return result;
00400 }
00401 
00408 nsSpaceManager::BandRect*
00409 nsSpaceManager::GetNextBand(const BandRect* aBandRect) const
00410 {
00411   nscoord topOfBand = aBandRect->mTop;
00412 
00413   aBandRect = aBandRect->Next();
00414   while (aBandRect != &mBandList) {
00415     // Check whether this rect is part of the same band
00416     if (aBandRect->mTop != topOfBand) {
00417       // We found the start of the next band
00418       return (BandRect*)aBandRect;
00419     }
00420 
00421     aBandRect = aBandRect->Next();
00422   }
00423 
00424   // No bands left
00425   return nsnull;
00426 }
00427 
00435 void
00436 nsSpaceManager::DivideBand(BandRect* aBandRect, nscoord aBottom)
00437 {
00438   NS_PRECONDITION(aBottom < aBandRect->mBottom, "bad height");
00439   nscoord   topOfBand = aBandRect->mTop;
00440   BandRect* nextBand = GetNextBand(aBandRect);
00441 
00442   if (nsnull == nextBand) {
00443     nextBand = (BandRect*)&mBandList;
00444   }
00445 
00446   while (topOfBand == aBandRect->mTop) {
00447     // Split the band rect into two vertically
00448     BandRect* bottomBandRect = aBandRect->SplitVertically(aBottom);
00449 
00450     // Insert the new bottom part
00451     nextBand->InsertBefore(bottomBandRect);
00452 
00453     // Move to the next rect in the band
00454     aBandRect = aBandRect->Next();
00455   }
00456 }
00457 
00458 PRBool
00459 nsSpaceManager::CanJoinBands(BandRect* aBand, BandRect* aPrevBand)
00460 {
00461   PRBool  result;
00462   nscoord topOfBand = aBand->mTop;
00463   nscoord topOfPrevBand = aPrevBand->mTop;
00464 
00465   // The bands can be joined if:
00466   // - they're adjacent
00467   // - they have the same number of rects
00468   // - each rect has the same left and right edge as its corresponding rect, and
00469   //   the rects are occupied by the same frames
00470   if (aPrevBand->mBottom == aBand->mTop) {
00471     // Compare each of the rects in the two bands
00472     while (PR_TRUE) {
00473       if ((aBand->mLeft != aPrevBand->mLeft) || (aBand->mRight != aPrevBand->mRight)) {
00474         // The rects have different edges
00475         result = PR_FALSE;
00476         break;
00477       }
00478 
00479       if (!aBand->HasSameFrameList(aPrevBand)) {
00480         // The rects are occupied by different frames
00481         result = PR_FALSE;
00482         break;
00483       }
00484 
00485       // Move to the next rects within the bands
00486       aBand = aBand->Next();
00487       aPrevBand = aPrevBand->Next();
00488 
00489       // Have we reached the end of either band?
00490       PRBool  endOfBand = aBand->mTop != topOfBand;
00491       PRBool  endOfPrevBand = aPrevBand->mTop != topOfPrevBand;
00492 
00493       if (endOfBand || endOfPrevBand) {
00494         result = endOfBand & endOfPrevBand;
00495         break;  // all done
00496       }
00497     }
00498 
00499   } else {
00500     // The bands aren't adjacent
00501     result = PR_FALSE;
00502   }
00503 
00504   return result;
00505 }
00506 
00513 PRBool
00514 nsSpaceManager::JoinBands(BandRect* aBand, BandRect* aPrevBand)
00515 {
00516   if (CanJoinBands(aBand, aPrevBand)) {
00517     BandRect* startOfNextBand = aBand;
00518 
00519     while (aPrevBand != startOfNextBand) {
00520       // Adjust the top of the band we're keeping, and then move to the next
00521       // rect within the band
00522       aBand->mTop = aPrevBand->mTop;
00523       aBand = aBand->Next();
00524 
00525       // Delete the rect from the previous band
00526       BandRect* next = aPrevBand->Next();
00527 
00528       aPrevBand->Remove();
00529       delete aPrevBand;
00530       aPrevBand = next;
00531     }
00532 
00533     return PR_TRUE;
00534   }
00535 
00536   return PR_FALSE;
00537 }
00538 
00545 void
00546 nsSpaceManager::AddRectToBand(BandRect* aBand, BandRect* aBandRect)
00547 {
00548   NS_PRECONDITION((aBand->mTop == aBandRect->mTop) &&
00549                   (aBand->mBottom == aBandRect->mBottom), "bad band");
00550   NS_PRECONDITION(1 == aBandRect->mNumFrames, "shared band rect");
00551   nscoord topOfBand = aBand->mTop;
00552 
00553   // Figure out where in the band horizontally to insert the rect
00554   do {
00555     // Compare the left edge of the new rect with the left edge of the existing
00556     // rect
00557     if (aBandRect->mLeft < aBand->mLeft) {
00558       // The new rect's left edge is to the left of the existing rect's left edge.
00559       // Could be any of these cases (N is new rect, E is existing rect):
00560       //
00561       //   Case 1: left-of      Case 2: overlaps     Case 3: N.contains(E)
00562       //   ---------------      ----------------     ---------------------
00563       //   +-----+ +-----+      +-----+              +---------+
00564       //   |  N  | |  E  |      |  N  |              |    N    |
00565       //   +-----+ +-----+      +-----+              +---------+
00566       //                           +-----+              +---+
00567       //                           |  E  |              | E |
00568       //                           +-----+              +---+
00569       //
00570       // Do the two rectangles overlap?
00571       if (aBandRect->mRight <= aBand->mLeft) {
00572         // No, the new rect is completely to the left of the existing rect
00573         // (case #1). Insert a new rect
00574         aBand->InsertBefore(aBandRect);
00575         return;
00576       }
00577 
00578       // Yes, they overlap. Compare the right edges.
00579       if (aBandRect->mRight > aBand->mRight) {
00580         // The new rect's right edge is to the right of the existing rect's
00581         // right edge (case #3). Split the new rect
00582         BandRect* r1 = aBandRect->SplitHorizontally(aBand->mLeft);
00583 
00584         // Insert the part of the new rect that's to the left of the existing
00585         // rect as a new band rect
00586         aBand->InsertBefore(aBandRect);
00587 
00588         // Continue below with the part that overlaps the existing rect
00589         aBandRect = r1;
00590 
00591       } else {
00592         if (aBand->mRight > aBandRect->mRight) {
00593           // The existing rect extends past the new rect (case #2). Split the
00594           // existing rect
00595           BandRect* r1 = aBand->SplitHorizontally(aBandRect->mRight);
00596 
00597           // Insert the new right half of the existing rect
00598           aBand->InsertAfter(r1);
00599         }
00600 
00601         // Insert the part of the new rect that's to the left of the existing
00602         // rect
00603         aBandRect->mRight = aBand->mLeft;
00604         aBand->InsertBefore(aBandRect);
00605 
00606         // Mark the existing rect as shared
00607         aBand->AddFrame(aBandRect->mFrame);
00608         return;
00609       }
00610     }
00611       
00612     if (aBandRect->mLeft > aBand->mLeft) {
00613       // The new rect's left edge is to the right of the existing rect's left
00614       // edge. Could be any one of these cases:
00615       //
00616       //   Case 4: right-of    Case 5: overlaps     Case 6: E.Contains(N)
00617       //   ---------------    ----------------     ---------------------
00618       //   +-----+ +-----+    +-----+              +------------+
00619       //   |  E  | |  N  |    |  E  |              |      E     |
00620       //   +-----+ +-----+    +-----+              +------------+
00621       //                         +-----+              +-----+
00622       //                         |  N  |              |  N  |
00623       //                         +-----+              +-----+
00624       //
00625       if (aBandRect->mLeft >= aBand->mRight) {
00626         // The new rect is to the right of the existing rect (case #4), so move
00627         // to the next rect in the band
00628         aBand = aBand->Next();
00629         continue;
00630       }
00631 
00632       // The rects overlap, so divide the existing rect into two rects: the
00633       // part to the left of the new rect, and the part that overlaps
00634       BandRect* r1 = aBand->SplitHorizontally(aBandRect->mLeft);
00635 
00636       // Insert the new right half of the existing rect, and make it the current
00637       // rect
00638       aBand->InsertAfter(r1);
00639       aBand = r1;
00640     }
00641 
00642     // At this point the left edge of the new rect is the same as the left edge
00643     // of the existing rect
00644     NS_ASSERTION(aBandRect->mLeft == aBand->mLeft, "unexpected rect");
00645 
00646     // Compare which rect is wider, the new rect or the existing rect
00647     if (aBand->mRight > aBandRect->mRight) {
00648       // The existing rect is wider (case #6). Divide the existing rect into
00649       // two rects: the part that overlaps, and the part to the right of the
00650       // new rect
00651       BandRect* r1 = aBand->SplitHorizontally(aBandRect->mRight);
00652 
00653       // Insert the new right half of the existing rect
00654       aBand->InsertAfter(r1);
00655 
00656       // Mark the overlap as being shared
00657       aBand->AddFrame(aBandRect->mFrame);
00658       return;
00659 
00660     } else {
00661       // Indicate the frames share the existing rect
00662       aBand->AddFrame(aBandRect->mFrame);
00663 
00664       if (aBand->mRight == aBandRect->mRight) {
00665         // The new and existing rect have the same right edge. We're all done,
00666         // and the new band rect is no longer needed
00667         delete aBandRect;
00668         return;
00669       } else {
00670         // The new rect is wider than the existing rect (cases #5). Set the
00671         // new rect to be the overhang, and move to the next rect within the band
00672         aBandRect->mLeft = aBand->mRight;
00673         aBand = aBand->Next();
00674         continue;
00675       }
00676     }
00677   } while (aBand->mTop == topOfBand);
00678 
00679   // Insert a new rect
00680   aBand->InsertBefore(aBandRect);
00681 }
00682 
00683 // When comparing a rect to a band there are seven cases to consider.
00684 // 'R' is the rect and 'B' is the band.
00685 //
00686 //      Case 1              Case 2              Case 3              Case 4
00687 //      ------              ------              ------              ------
00688 // +-----+             +-----+                      +-----+             +-----+
00689 // |  R  |             |  R  |  +-----+    +-----+  |     |             |     |
00690 // +-----+             +-----+  |     |    |  R  |  |  B  |             |  B  |
00691 //          +-----+             |  B  |    +-----+  |     |    +-----+  |     |
00692 //          |     |             |     |             +-----+    |  R  |  +-----+
00693 //          |  B  |             +-----+                        +-----+
00694 //          |     |
00695 //          +-----+
00696 //
00697 //
00698 //
00699 //      Case 5              Case 6              Case 7
00700 //      ------              ------              ------
00701 //          +-----+    +-----+  +-----+    +-----+
00702 //          |     |    |  R  |  |  B  |    |     |  +-----+
00703 //          |  B  |    +-----+  +-----+    |  R  |  |  B  |
00704 //          |     |                        |     |  +-----+
00705 //          +-----+                        +-----+
00706 // +-----+
00707 // |  R  |
00708 // +-----+
00709 //
00710 void
00711 nsSpaceManager::InsertBandRect(BandRect* aBandRect)
00712 {
00713   // If there are no existing bands or this rect is below the bottommost
00714   // band, then add a new band
00715   nscoord yMost;
00716   if (!YMost(yMost) || (aBandRect->mTop >= yMost)) {
00717     mBandList.Append(aBandRect);
00718     return;
00719   }
00720 
00721   // Examine each band looking for a band that intersects this rect
00722   NS_ASSERTION(!mBandList.IsEmpty(), "no bands");
00723   BandRect* band = mBandList.Head();
00724 
00725   while (nsnull != band) {
00726     // Compare the top edge of this rect with the top edge of the band
00727     if (aBandRect->mTop < band->mTop) {
00728       // The top edge of the rect is above the top edge of the band.
00729       // Is there any overlap?
00730       if (aBandRect->mBottom <= band->mTop) {
00731         // Case #1. This rect is completely above the band, so insert a
00732         // new band before the current band
00733         band->InsertBefore(aBandRect);
00734         break;  // we're all done
00735       }
00736 
00737       // Case #2 and case #7. Divide this rect, creating a new rect for
00738       // the part that's above the band
00739       BandRect* bandRect1 = new BandRect(aBandRect->mLeft, aBandRect->mTop,
00740                                          aBandRect->mRight, band->mTop,
00741                                          aBandRect->mFrame);
00742 
00743       // Insert bandRect1 as a new band
00744       band->InsertBefore(bandRect1);
00745 
00746       // Modify this rect to exclude the part above the band
00747       aBandRect->mTop = band->mTop;
00748 
00749     } else if (aBandRect->mTop > band->mTop) {
00750       // The top edge of the rect is below the top edge of the band. Is there
00751       // any overlap?
00752       if (aBandRect->mTop >= band->mBottom) {
00753         // Case #5. This rect is below the current band. Skip to the next band
00754         band = GetNextBand(band);
00755         continue;
00756       }
00757 
00758       // Case #3 and case #4. Divide the current band into two bands with the
00759       // top band being the part that's above the rect
00760       DivideBand(band, aBandRect->mTop);
00761 
00762       // Skip to the bottom band that we just created
00763       band = GetNextBand(band);
00764     }
00765 
00766     // At this point the rect and the band should have the same y-offset
00767     NS_ASSERTION(aBandRect->mTop == band->mTop, "unexpected band");
00768 
00769     // Is the band higher than the rect?
00770     if (band->mBottom > aBandRect->mBottom) {
00771       // Divide the band into two bands with the top band the same height
00772       // as the rect
00773       DivideBand(band, aBandRect->mBottom);
00774     }
00775 
00776     if (aBandRect->mBottom == band->mBottom) {
00777       // Add the rect to the band
00778       AddRectToBand(band, aBandRect);
00779       break;
00780 
00781     } else {
00782       // Case #4 and case #7. The rect contains the band vertically. Divide
00783       // the rect, creating a new rect for the part that overlaps the band
00784       BandRect* bandRect1 = new BandRect(aBandRect->mLeft, aBandRect->mTop,
00785                                          aBandRect->mRight, band->mBottom,
00786                                          aBandRect->mFrame);
00787 
00788       // Add bandRect1 to the band
00789       AddRectToBand(band, bandRect1);
00790 
00791       // Modify aBandRect to be the part below the band
00792       aBandRect->mTop = band->mBottom;
00793 
00794       // Continue with the next band
00795       band = GetNextBand(band);
00796       if (nsnull == band) {
00797         // Append a new bottommost band
00798         mBandList.Append(aBandRect);
00799         break;
00800       }
00801     }
00802   }
00803 }
00804 
00805 nsresult
00806 nsSpaceManager::AddRectRegion(nsIFrame* aFrame, const nsRect& aUnavailableSpace)
00807 {
00808   NS_PRECONDITION(nsnull != aFrame, "null frame");
00809   NS_PRECONDITION(aUnavailableSpace.width >= 0 &&
00810                   aUnavailableSpace.height >= 0,
00811                   "Negative dimensions not allowed");
00812 
00813   // See if there is already a region associated with aFrame
00814   FrameInfo*  frameInfo = GetFrameInfoFor(aFrame);
00815 
00816   if (nsnull != frameInfo) {
00817     NS_WARNING("aFrame is already associated with a region");
00818     return NS_ERROR_FAILURE;
00819   }
00820 
00821   // Convert the frame to world coordinates
00822   nsRect  rect(aUnavailableSpace.x + mX, aUnavailableSpace.y + mY,
00823                aUnavailableSpace.width, aUnavailableSpace.height);
00824 
00825   if (rect.y > mLowestTop)
00826     mLowestTop = rect.y;
00827 
00828   // Create a frame info structure
00829   frameInfo = CreateFrameInfo(aFrame, rect);
00830   if (nsnull == frameInfo) {
00831     return NS_ERROR_OUT_OF_MEMORY;
00832   }
00833 
00834   if (aUnavailableSpace.height <= 0)
00835     return NS_OK;
00836 
00837   // Allocate a band rect
00838   BandRect* bandRect = new BandRect(rect.x, rect.y, rect.XMost(), rect.YMost(), aFrame);
00839   if (nsnull == bandRect) {
00840     return NS_ERROR_OUT_OF_MEMORY;
00841   }
00842 
00843   // Insert the band rect
00844   InsertBandRect(bandRect);
00845   return NS_OK;
00846 }
00847 
00848 nsresult
00849 nsSpaceManager::RemoveTrailingRegions(nsIFrame* aFrameList) {
00850   nsVoidHashSet frameSet;
00851 
00852   frameSet.Init(1);
00853   for (nsIFrame* f = aFrameList; f; f = f->GetNextSibling()) {
00854     frameSet.Put(f);
00855   }
00856 
00857   // Pop frame regions off as long as they're in the set of frames to
00858   // remove
00859   while (mFrameInfoMap && frameSet.Contains(mFrameInfoMap->mFrame)) {
00860     RemoveRegion(mFrameInfoMap->mFrame);
00861   }
00862 
00863 #ifdef DEBUG
00864   for (FrameInfo* frameInfo = mFrameInfoMap; frameInfo;
00865        frameInfo = frameInfo->mNext) {
00866     NS_ASSERTION(!frameSet.Contains(frameInfo->mFrame),
00867                  "Frame region deletion was requested but we couldn't delete it");
00868   }
00869 #endif
00870 
00871   return NS_OK;
00872 }
00873 
00874 nsresult
00875 nsSpaceManager::RemoveRegion(nsIFrame* aFrame)
00876 {
00877   // Get the frame info associated with aFrame
00878   FrameInfo*  frameInfo = GetFrameInfoFor(aFrame);
00879 
00880   if (nsnull == frameInfo) {
00881     NS_WARNING("no region associated with aFrame");
00882     return NS_ERROR_INVALID_ARG;
00883   }
00884 
00885   if (frameInfo->mRect.height > 0) {
00886     NS_ASSERTION(!mBandList.IsEmpty(), "no bands");
00887     BandRect* band = mBandList.Head();
00888     BandRect* prevBand = nsnull;
00889     PRBool    prevFoundMatchingRect = PR_FALSE;
00890 
00891     // Iterate each band looking for rects tagged with aFrame
00892     while (nsnull != band) {
00893       BandRect* rect = band;
00894       BandRect* prevRect = nsnull;
00895       nscoord   topOfBand = band->mTop;
00896       PRBool    foundMatchingRect = PR_FALSE;
00897       PRBool    prevIsSharedRect = PR_FALSE;
00898 
00899       // Iterate each rect in the band
00900       do {
00901         PRBool  isSharedRect = PR_FALSE;
00902 
00903         if (rect->IsOccupiedBy(aFrame)) {
00904           // Remember that we found a matching rect in this band
00905           foundMatchingRect = PR_TRUE;
00906 
00907           if (rect->mNumFrames > 1) {
00908             // The band rect is occupied by more than one frame
00909             rect->RemoveFrame(aFrame);
00910 
00911             // Remember that this rect was being shared by more than one frame
00912             // including aFrame
00913             isSharedRect = PR_TRUE;
00914           } else {
00915             // The rect isn't shared so just delete it
00916             BandRect* next = rect->Next();
00917             rect->Remove();
00918             if (rect == band) {
00919               // The rect we're deleting is the start of the band
00920               if (topOfBand == next->mTop) {
00921                 band = next;
00922               } else {
00923                 band = nsnull;
00924               }
00925             }
00926             delete rect;
00927             rect = next;
00928 
00929             // We don't need to try and coalesce adjacent rects in this case
00930             prevRect = nsnull;
00931             prevIsSharedRect = PR_FALSE;
00932             continue;
00933           }
00934         }
00935            
00936         // If we found a shared rect occupied by aFrame, then we need to try
00937         // and coalesce adjacent rects
00938         if (prevIsSharedRect || (isSharedRect && (nsnull != prevRect))) {
00939           NS_ASSERTION(nsnull != prevRect, "no previous rect");
00940           if ((prevRect->mRight == rect->mLeft) && (prevRect->HasSameFrameList(rect))) {
00941             // Modify the current rect's left edge, and delete the previous rect
00942             rect->mLeft = prevRect->mLeft;
00943             prevRect->Remove();
00944             if (prevRect == band) {
00945               // the rect we're deleting is the start of the band
00946               band = rect;
00947             }
00948             delete prevRect;
00949           }
00950         }
00951 
00952         // Get the next rect in the band
00953         prevRect = rect;
00954         prevIsSharedRect = isSharedRect;
00955         rect = rect->Next();
00956       } while (rect->mTop == topOfBand);
00957 
00958       if (nsnull != band) {
00959         // If we found a rect occupied by aFrame in this band or the previous band
00960         // then try to join the two bands
00961         if ((nsnull != prevBand) && (foundMatchingRect || prevFoundMatchingRect)) {
00962           // Try and join this band with the previous band
00963           JoinBands(band, prevBand);
00964         }
00965       }
00966 
00967       // Move to the next band
00968       prevFoundMatchingRect = foundMatchingRect;
00969       prevBand = band;
00970       band = (rect == &mBandList) ? nsnull : rect;
00971     }
00972   }
00973 
00974   DestroyFrameInfo(frameInfo);
00975   return NS_OK;
00976 }
00977 
00978 void
00979 nsSpaceManager::ClearRegions()
00980 {
00981   ClearFrameInfo();
00982   mBandList.Clear();
00983   mLowestTop = NSCOORD_MIN;
00984 }
00985 
00986 void
00987 nsSpaceManager::PushState()
00988 {
00989   // This is a quick and dirty push implementation, which
00990   // only saves the (x,y) and last frame in the mFrameInfoMap
00991   // which is enough info to get us back to where we should be
00992   // when pop is called.
00993   //
00994   // The alternative would be to make full copies of the contents
00995   // of mBandList and mFrameInfoMap and restore them when pop is
00996   // called, but I'm not sure it's worth the effort/bloat at this
00997   // point, since this push/pop mechanism is only used to undo any
00998   // floats that were added during the unconstrained reflow
00999   // in nsBlockReflowContext::DoReflowBlock(). (See bug 96736)
01000   //
01001   // It should also be noted that the state for mFloatDamage is
01002   // intentionally not saved or restored in PushState() and PopState(),
01003   // since that could lead to bugs where damage is missed/dropped when
01004   // we move from position A to B (during the intermediate incremental
01005   // reflow mentioned above) and then from B to C during the subsequent
01006   // reflow. In the typical case A and C will be the same, but not always.
01007   // Allowing mFloatDamage to accumulate the damage incurred during both
01008   // reflows ensures that nothing gets missed.
01009 
01010   SpaceManagerState *state;
01011 
01012   if(mSavedStates) {
01013     state = new SpaceManagerState;
01014   } else {
01015     state = &mAutoState;
01016   }
01017 
01018   NS_ASSERTION(state, "PushState() failed!");
01019 
01020   if (!state) {
01021     return;
01022   }
01023 
01024   state->mX = mX;
01025   state->mY = mY;
01026   state->mLowestTop = mLowestTop;
01027 
01028   if (mFrameInfoMap) {
01029     state->mLastFrame = mFrameInfoMap->mFrame;
01030   } else {
01031     state->mLastFrame = nsnull;
01032   }
01033 
01034   // Now that we've saved our state, add it to mSavedStates.
01035 
01036   state->mNext = mSavedStates;
01037   mSavedStates = state;
01038 }
01039 
01040 void
01041 nsSpaceManager::PopState()
01042 {
01043   // This is a quick and dirty pop implementation, to
01044   // match the current implementation of PushState(). The
01045   // idea here is to remove any frames that have been added
01046   // to the mFrameInfoMap since the last call to PushState().
01047 
01048   NS_ASSERTION(mSavedStates, "Invalid call to PopState()!");
01049 
01050   if (!mSavedStates) {
01051     return;
01052   }
01053 
01054   // mFrameInfoMap is LIFO so keep removing what it points
01055   // to until we hit mLastFrame.
01056 
01057   while (mFrameInfoMap && mFrameInfoMap->mFrame != mSavedStates->mLastFrame) {
01058     RemoveRegion(mFrameInfoMap->mFrame);
01059   }
01060 
01061   // If we trip this assertion it means that someone added
01062   // PushState()/PopState() calls around code that actually
01063   // removed mLastFrame from mFrameInfoMap, which means our
01064   // state is now out of sync with what we thought it should be.
01065 
01066   NS_ASSERTION(((mSavedStates->mLastFrame && mFrameInfoMap) ||
01067                (!mSavedStates->mLastFrame && !mFrameInfoMap)),
01068                "Unexpected outcome!");
01069 
01070   mX = mSavedStates->mX;
01071   mY = mSavedStates->mY;
01072   mLowestTop = mSavedStates->mLowestTop;
01073 
01074   // Now that we've restored our state, pop the topmost
01075   // state and delete it.  Make sure not to delete the mAutoState element
01076   // as it is embedded in this class
01077 
01078   SpaceManagerState *state = mSavedStates;
01079   mSavedStates = mSavedStates->mNext;
01080   if(state != &mAutoState) {
01081     delete state;
01082   }
01083 }
01084 
01085 void
01086 nsSpaceManager::DiscardState()
01087 {
01088   NS_ASSERTION(mSavedStates, "Invalid call to DiscardState()!");
01089 
01090   if (!mSavedStates) {
01091     return;
01092   }
01093 
01094   SpaceManagerState *state = mSavedStates;
01095   mSavedStates = mSavedStates->mNext;
01096   if(state != &mAutoState) {
01097     delete state;
01098   }
01099 }
01100 
01101 nscoord
01102 nsSpaceManager::GetLowestRegionTop()
01103 {
01104   if (mLowestTop == NSCOORD_MIN)
01105     return mLowestTop;
01106   return mLowestTop - mY;
01107 }
01108 
01109 #ifdef DEBUG
01110 void
01111 DebugListSpaceManager(nsSpaceManager *aSpaceManager)
01112 {
01113   aSpaceManager->List(stdout);
01114 }
01115 
01116 nsresult
01117 nsSpaceManager::List(FILE* out)
01118 {
01119   nsAutoString tmp;
01120 
01121   fprintf(out, "SpaceManager@%p", this);
01122   if (mFrame) {
01123     nsIFrameDebug*  frameDebug;
01124 
01125     if (NS_SUCCEEDED(mFrame->QueryInterface(NS_GET_IID(nsIFrameDebug), (void**)&frameDebug))) {
01126       frameDebug->GetFrameName(tmp);
01127       fprintf(out, " frame=");
01128       fputs(NS_LossyConvertUCS2toASCII(tmp).get(), out);
01129       fprintf(out, "@%p", mFrame);
01130     }
01131   }
01132   fprintf(out, " xy=%d,%d <\n", mX, mY);
01133   if (mBandList.IsEmpty()) {
01134     fprintf(out, "  no bands\n");
01135   }
01136   else {
01137     BandRect* band = mBandList.Head();
01138     do {
01139       fprintf(out, "  left=%d top=%d right=%d bottom=%d numFrames=%d",
01140               band->mLeft, band->mTop, band->mRight, band->mBottom,
01141               band->mNumFrames);
01142       if (1 == band->mNumFrames) {
01143         nsIFrameDebug*  frameDebug;
01144 
01145         if (NS_SUCCEEDED(band->mFrame->QueryInterface(NS_GET_IID(nsIFrameDebug), (void**)&frameDebug))) {
01146           frameDebug->GetFrameName(tmp);
01147           fprintf(out, " frame=");
01148           fputs(NS_LossyConvertUCS2toASCII(tmp).get(), out);
01149           fprintf(out, "@%p", band->mFrame);
01150         }
01151       }
01152       else if (1 < band->mNumFrames) {
01153         fprintf(out, "\n    ");
01154         nsVoidArray* a = band->mFrames;
01155         PRInt32 i, n = a->Count();
01156         for (i = 0; i < n; i++) {
01157           nsIFrame* frame = (nsIFrame*) a->ElementAt(i);
01158           if (frame) {
01159             nsIFrameDebug*  frameDebug;
01160 
01161             if (NS_SUCCEEDED(frame->QueryInterface(NS_GET_IID(nsIFrameDebug), (void**)&frameDebug))) {
01162               frameDebug->GetFrameName(tmp);
01163               fputs(NS_LossyConvertUCS2toASCII(tmp).get(), out);
01164               fprintf(out, "@%p ", frame);
01165             }
01166           }
01167         }
01168       }
01169       fprintf(out, "\n");
01170       band = band->Next();
01171     } while (band != mBandList.Head());
01172   }
01173   fprintf(out, ">\n");
01174   return NS_OK;
01175 }
01176 #endif
01177 
01178 nsSpaceManager::FrameInfo*
01179 nsSpaceManager::GetFrameInfoFor(nsIFrame* aFrame)
01180 {
01181   FrameInfo*  result = nsnull;
01182 
01183   for (result = mFrameInfoMap; result; result = result->mNext) {
01184     if (result->mFrame == aFrame) {
01185       break;
01186     }
01187   }
01188 
01189   return result;
01190 }
01191 
01192 nsSpaceManager::FrameInfo*
01193 nsSpaceManager::CreateFrameInfo(nsIFrame* aFrame, const nsRect& aRect)
01194 {
01195   FrameInfo*  frameInfo = new FrameInfo(aFrame, aRect);
01196 
01197   if (frameInfo) {
01198     // Link it into the list
01199     frameInfo->mNext = mFrameInfoMap;
01200     mFrameInfoMap = frameInfo;
01201   }
01202   return frameInfo;
01203 }
01204 
01205 void
01206 nsSpaceManager::DestroyFrameInfo(FrameInfo* aFrameInfo)
01207 {
01208   // See if it's at the head of the list
01209   if (mFrameInfoMap == aFrameInfo) {
01210     mFrameInfoMap = aFrameInfo->mNext;
01211 
01212   } else {
01213     FrameInfo*  prev;
01214     
01215     // Find the previous node in the list
01216     for (prev = mFrameInfoMap; prev && (prev->mNext != aFrameInfo); prev = prev->mNext) {
01217       ;
01218     }
01219 
01220     // Disconnect it from the list
01221     NS_ASSERTION(prev, "element not in list");
01222     if (prev) {
01223       prev->mNext = aFrameInfo->mNext;
01224     }
01225   }
01226 
01227   delete aFrameInfo;
01228 }
01229 
01230 static PRBool
01231 ShouldClearFrame(nsIFrame* aFrame, PRUint8 aBreakType)
01232 {
01233   PRUint8 floatType = aFrame->GetStyleDisplay()->mFloats;
01234   PRBool result;
01235   switch (aBreakType) {
01236     case NS_STYLE_CLEAR_LEFT_AND_RIGHT:
01237       result = PR_TRUE;
01238       break;
01239     case NS_STYLE_CLEAR_LEFT:
01240       result = floatType == NS_STYLE_FLOAT_LEFT;
01241       break;
01242     case NS_STYLE_CLEAR_RIGHT:
01243       result = floatType == NS_STYLE_FLOAT_RIGHT;
01244       break;
01245     default:
01246       result = PR_FALSE;
01247   }
01248   return result;
01249 }
01250 
01251 nscoord
01252 nsSpaceManager::ClearFloats(nscoord aY, PRUint8 aBreakType)
01253 {
01254   nscoord bottom = aY + mY;
01255 
01256   for (FrameInfo *frame = mFrameInfoMap; frame; frame = frame->mNext) {
01257     if (ShouldClearFrame(frame->mFrame, aBreakType)) {
01258       if (frame->mRect.YMost() > bottom) {
01259         bottom = frame->mRect.YMost();
01260       }
01261     }
01262   }
01263 
01264   bottom -= mY;
01265 
01266   return bottom;
01267 }
01268 
01270 // FrameInfo
01271 
01272 MOZ_DECL_CTOR_COUNTER(nsSpaceManager::FrameInfo)
01273 
01274 nsSpaceManager::FrameInfo::FrameInfo(nsIFrame* aFrame, const nsRect& aRect)
01275   : mFrame(aFrame), mRect(aRect), mNext(0)
01276 {
01277   MOZ_COUNT_CTOR(nsSpaceManager::FrameInfo);
01278 }
01279 
01280 #ifdef NS_BUILD_REFCNT_LOGGING
01281 nsSpaceManager::FrameInfo::~FrameInfo()
01282 {
01283   MOZ_COUNT_DTOR(nsSpaceManager::FrameInfo);
01284 }
01285 #endif
01286 
01288 // BandRect
01289 
01290 MOZ_DECL_CTOR_COUNTER(BandRect)
01291 
01292 nsSpaceManager::BandRect::BandRect(nscoord    aLeft,
01293                                    nscoord    aTop,
01294                                    nscoord    aRight,
01295                                    nscoord    aBottom,
01296                                    nsIFrame*  aFrame)
01297 {
01298   MOZ_COUNT_CTOR(BandRect);
01299   mLeft = aLeft;
01300   mTop = aTop;
01301   mRight = aRight;
01302   mBottom = aBottom;
01303   mFrame = aFrame;
01304   mNumFrames = 1;
01305 }
01306 
01307 nsSpaceManager::BandRect::BandRect(nscoord      aLeft,
01308                                    nscoord      aTop,
01309                                    nscoord      aRight,
01310                                    nscoord      aBottom,
01311                                    nsVoidArray* aFrames)
01312 {
01313   MOZ_COUNT_CTOR(BandRect);
01314   mLeft = aLeft;
01315   mTop = aTop;
01316   mRight = aRight;
01317   mBottom = aBottom;
01318   mFrames = new nsVoidArray;
01319   mFrames->operator=(*aFrames);
01320   mNumFrames = mFrames->Count();
01321 }
01322 
01323 nsSpaceManager::BandRect::~BandRect()
01324 {
01325   MOZ_COUNT_DTOR(BandRect);
01326   if (mNumFrames > 1) {
01327     delete mFrames;
01328   }
01329 }
01330 
01331 nsSpaceManager::BandRect*
01332 nsSpaceManager::BandRect::SplitVertically(nscoord aBottom)
01333 {
01334   // Allow aBottom == mTop, so we can split off an empty rectangle
01335   NS_PRECONDITION((aBottom >= mTop) && (aBottom < mBottom), "bad argument");
01336 
01337   // Create a new band rect for the bottom part
01338   BandRect* bottomBandRect;
01339                                             
01340   if (mNumFrames > 1) {
01341     bottomBandRect = new BandRect(mLeft, aBottom, mRight, mBottom, mFrames);
01342   } else {
01343     bottomBandRect = new BandRect(mLeft, aBottom, mRight, mBottom, mFrame);
01344   }
01345                                            
01346   // This band rect becomes the top part, so adjust the bottom edge
01347   mBottom = aBottom;
01348   return bottomBandRect;
01349 }
01350 
01351 nsSpaceManager::BandRect*
01352 nsSpaceManager::BandRect::SplitHorizontally(nscoord aRight)
01353 {
01354   // Allow aRight == mLeft, so we can split off an empty rectangle
01355   NS_PRECONDITION((aRight >= mLeft) && (aRight < mRight), "bad argument");
01356   
01357   // Create a new band rect for the right part
01358   BandRect* rightBandRect;
01359                                             
01360   if (mNumFrames > 1) {
01361     rightBandRect = new BandRect(aRight, mTop, mRight, mBottom, mFrames);
01362   } else {
01363     rightBandRect = new BandRect(aRight, mTop, mRight, mBottom, mFrame);
01364   }
01365                                            
01366   // This band rect becomes the left part, so adjust the right edge
01367   mRight = aRight;
01368   return rightBandRect;
01369 }
01370 
01371 PRBool
01372 nsSpaceManager::BandRect::IsOccupiedBy(const nsIFrame* aFrame) const
01373 {
01374   PRBool  result;
01375 
01376   if (1 == mNumFrames) {
01377     result = (mFrame == aFrame);
01378   } else {
01379     PRInt32 count = mFrames->Count();
01380 
01381     result = PR_FALSE;
01382     for (PRInt32 i = 0; i < count; i++) {
01383       nsIFrame* f = (nsIFrame*)mFrames->ElementAt(i);
01384 
01385       if (f == aFrame) {
01386         result = PR_TRUE;
01387         break;
01388       }
01389     }
01390   }
01391 
01392   return result;
01393 }
01394 
01395 void
01396 nsSpaceManager::BandRect::AddFrame(const nsIFrame* aFrame)
01397 {
01398   if (1 == mNumFrames) {
01399     nsIFrame* f = mFrame;
01400     mFrames = new nsVoidArray;
01401     mFrames->AppendElement(f);
01402   }
01403 
01404   mNumFrames++;
01405   mFrames->AppendElement((void*)aFrame);
01406   NS_POSTCONDITION(mFrames->Count() == mNumFrames, "bad frame count");
01407 }
01408 
01409 void
01410 nsSpaceManager::BandRect::RemoveFrame(const nsIFrame* aFrame)
01411 {
01412   NS_PRECONDITION(mNumFrames > 1, "only one frame");
01413   mFrames->RemoveElement((void*)aFrame);
01414   mNumFrames--;
01415 
01416   if (1 == mNumFrames) {
01417     nsIFrame* f = (nsIFrame*)mFrames->ElementAt(0);
01418 
01419     delete mFrames;
01420     mFrame = f;
01421   }
01422 }
01423 
01424 PRBool
01425 nsSpaceManager::BandRect::HasSameFrameList(const BandRect* aBandRect) const
01426 {
01427   PRBool  result;
01428 
01429   // Check whether they're occupied by the same number of frames
01430   if (mNumFrames != aBandRect->mNumFrames) {
01431     result = PR_FALSE;
01432   } else if (1 == mNumFrames) {
01433     result = (mFrame == aBandRect->mFrame);
01434   } else {
01435     result = PR_TRUE;
01436 
01437     // For each frame occupying this band rect check whether it also occupies
01438     // aBandRect
01439     PRInt32 count = mFrames->Count();
01440     for (PRInt32 i = 0; i < count; i++) {
01441       nsIFrame* f = (nsIFrame*)mFrames->ElementAt(i);
01442 
01443       if (-1 == aBandRect->mFrames->IndexOf(f)) {
01444         result = PR_FALSE;
01445         break;
01446       }
01447     }
01448   }
01449 
01450   return result;
01451 }
01452 
01457 PRInt32
01458 nsSpaceManager::BandRect::Length() const
01459 {
01460   PRInt32   len = 1;
01461   BandRect* bandRect = Next();
01462 
01463   // Because there's a header cell we know we'll either find the next band
01464   // (which has a different y-offset) or the header cell which has an invalid
01465   // y-offset
01466   while (bandRect->mTop == mTop) {
01467     len++;
01468     bandRect = bandRect->Next();
01469   }
01470 
01471   return len;
01472 }
01473 
01474 
01475 //----------------------------------------------------------------------
01476 
01477 nsAutoSpaceManager::~nsAutoSpaceManager()
01478 {
01479   // Restore the old space manager in the reflow state if necessary.
01480   if (mNew) {
01481 #ifdef NOISY_SPACEMANAGER
01482     printf("restoring old space manager %p\n", mOld);
01483 #endif
01484 
01485     mReflowState.mSpaceManager = mOld;
01486 
01487 #ifdef NOISY_SPACEMANAGER
01488     if (mOld) {
01489       NS_STATIC_CAST(nsFrame *, mReflowState.frame)->ListTag(stdout);
01490       printf(": space-manager %p after reflow\n", mOld);
01491       mOld->List(stdout);
01492     }
01493 #endif
01494 
01495 #ifdef DEBUG
01496     if (mOwns)
01497 #endif
01498       delete mNew;
01499   }
01500 }
01501 
01502 nsresult
01503 nsAutoSpaceManager::CreateSpaceManagerFor(nsPresContext *aPresContext, nsIFrame *aFrame)
01504 {
01505   // Create a new space manager and install it in the reflow
01506   // state. `Remember' the old space manager so we can restore it
01507   // later.
01508   mNew = new nsSpaceManager(aPresContext->PresShell(), aFrame);
01509   if (! mNew)
01510     return NS_ERROR_OUT_OF_MEMORY;
01511 
01512 #ifdef NOISY_SPACEMANAGER
01513   printf("constructed new space manager %p (replacing %p)\n",
01514          mNew, mReflowState.mSpaceManager);
01515 #endif
01516 
01517   // Set the space manager in the existing reflow state
01518   mOld = mReflowState.mSpaceManager;
01519   mReflowState.mSpaceManager = mNew;
01520   return NS_OK;
01521 }