Bug 512336. Make frame lists doubly-linked. r=roc,fantasai
authorBoris Zbarsky <bzbarsky@mit.edu>
Fri, 02 Oct 2009 12:27:37 -0400
changeset 33388 c52390466bd122a2970b64937f9c094931557863
parent 33387 265a796d91cbaf6c732001c91541f5fea7fcfc4e
child 33389 0629dc7b3e5edcc86f6de68a83491d00a4966da2
push id9471
push userbzbarsky@mozilla.com
push dateFri, 02 Oct 2009 16:32:43 +0000
treeherdermozilla-central@26d5186da496 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersroc, fantasai
bugs512336
milestone1.9.3a1pre
Bug 512336. Make frame lists doubly-linked. r=roc,fantasai
layout/base/nsCSSFrameConstructor.cpp
layout/base/nsFrameTraversal.cpp
layout/generic/nsBlockFrame.cpp
layout/generic/nsFrame.cpp
layout/generic/nsFrameList.cpp
layout/generic/nsFrameList.h
layout/generic/nsIFrame.h
layout/mathml/nsMathMLmoFrame.cpp
layout/tables/nsTableFrame.cpp
layout/xul/base/src/nsBoxFrame.cpp
layout/xul/base/src/nsListBoxBodyFrame.cpp
layout/xul/base/src/nsSplitterFrame.cpp
layout/xul/base/src/nsXULPopupManager.cpp
layout/xul/base/src/tree/src/nsTreeColFrame.cpp
--- a/layout/base/nsCSSFrameConstructor.cpp
+++ b/layout/base/nsCSSFrameConstructor.cpp
@@ -2009,24 +2009,21 @@ nsCSSFrameConstructor::AdjustParentFrame
   }
 }
 
 // Pull all the captions present in aItems out  into aCaptions
 static void
 PullOutCaptionFrames(nsFrameItems& aItems, nsFrameItems& aCaptions)
 {
   nsIFrame *child = aItems.FirstChild();
-  nsIFrame* prev = nsnull;
   while (child) {
     nsIFrame *nextSibling = child->GetNextSibling();
     if (nsGkAtoms::tableCaptionFrame == child->GetType()) {
-      aItems.RemoveFrame(child, prev);
+      aItems.RemoveFrame(child);
       aCaptions.AddChild(child);
-    } else {
-      prev = child;
     }
     child = nextSibling;
   }
 }
 
 
 // Construct the outer, inner table frames and the children frames for the table. 
 // XXX Page break frames for pseudo table frames are not constructed to avoid the risk
@@ -3458,27 +3455,25 @@ nsCSSFrameConstructor::ConstructFieldSet
   }
 
   ProcessChildren(aState, content, styleContext, blockFrame, PR_TRUE,
                   childItems, PR_TRUE);
 
   nsFrameItems fieldsetKids;
   fieldsetKids.AddChild(blockFrame);
 
-  for (nsFrameList::FrameLinkEnumerator link(childItems);
-       !link.AtEnd();
-       link.Next()) {
-    nsLegendFrame* legendFrame = do_QueryFrame(link.NextFrame());
+  for (nsFrameList::Enumerator e(childItems); !e.AtEnd(); e.Next()) {
+    nsLegendFrame* legendFrame = do_QueryFrame(e.get());
     if (legendFrame) {
       // We want the legend to be the first frame in the fieldset child list.
       // That way the EventStateManager will do the right thing when tabbing
       // from a selection point within the legend (bug 236071), which is
       // used for implementing legend access keys (bug 81481).
       // GetAdjustedParentFrame() below depends on this frame order.
-      childItems.RemoveFrame(link.NextFrame(), link.PrevFrame());
+      childItems.RemoveFrame(legendFrame);
       // Make sure to reparent the legend so it has the fieldset as the parent.
       fieldsetKids.InsertFrame(newFrame, nsnull, legendFrame);
       break;
     }
   }
 
   // Set the inner frame's initial child lists
   blockFrame->SetInitialChildList(nsnull, childItems);
@@ -3965,17 +3960,17 @@ nsCSSFrameConstructor::ConstructFrameFro
       while ((f = childItems.FirstChild()) != nsnull) {
         PRBool wrapFrame = IsInlineFrame(f) || IsFrameSpecial(f);
         if (!wrapFrame) {
           rv = FlushAccumulatedBlock(aState, content, newFrame, &currentBlock, &newItems);
           if (NS_FAILED(rv))
             break;
         }
 
-        childItems.RemoveFrame(f, nsnull);
+        childItems.RemoveFrame(f);
         if (wrapFrame) {
           currentBlock.AddChild(f);
         } else {
           newItems.AddChild(f);
         }
       }
       rv = FlushAccumulatedBlock(aState, content, newFrame, &currentBlock, &newItems);
 
@@ -5695,17 +5690,17 @@ AdjustAppendParentForAfterContent(nsPres
  * it takes a parent frame (must not be null) and its :after frame (may be
  * null).
  */
 static nsIFrame*
 FindAppendPrevSibling(nsIFrame* aParentFrame, nsIFrame* aAfterFrame)
 {
   if (aAfterFrame) {
     NS_ASSERTION(aAfterFrame->GetParent() == aParentFrame, "Wrong parent");
-    return aParentFrame->GetChildList(nsnull).GetPrevSiblingFor(aAfterFrame);
+    return aAfterFrame->GetPrevSibling();
   }
 
   return aParentFrame->GetLastChild(nsnull);
 }
 
 /**
  * This function will get the next sibling for a frame insert operation given
  * the parent and previous sibling.  aPrevSibling may be null.
@@ -10178,17 +10173,17 @@ nsCSSFrameConstructor::WrapFramesInFirst
                                     letterFrames, &stopLooking);
   if (NS_FAILED(rv)) {
     return rv;
   }
   if (parentFrame) {
     if (parentFrame == aBlockFrame) {
       // Take textFrame out of the block's frame list and substitute the
       // letter frame(s) instead.
-      aBlockFrames.DestroyFrame(textFrame, prevFrame);
+      aBlockFrames.DestroyFrame(textFrame);
       aBlockFrames.InsertFrames(nsnull, prevFrame, letterFrames);
     }
     else {
       // Take the old textFrame out of the inline parent's child list
       ::DeletingFrameSubtree(mPresShell->FrameManager(), textFrame);
       parentFrame->RemoveFrame(nsnull, textFrame);
 
       // Insert in the letter frame(s)
@@ -10339,28 +10334,17 @@ nsCSSFrameConstructor::RemoveFloatingFir
     nsIFrame* nextFrameToDelete = frameToDelete->GetPrevContinuation();
     if (frameToDeleteParent) {
       ::DeletingFrameSubtree(aFrameManager, frameToDelete);
       aFrameManager->RemoveFrame(frameToDeleteParent, nsnull, frameToDelete);
     }
     frameToDelete = nextFrameToDelete;
   }
 
-  // First find out where (in the content) the placeholder frames
-  // text is and its previous sibling frame, if any.  Note that:
-  // 1)  The placeholder had better be in the principal child list of
-  //     parentFrame.
-  // 2)  It's probably near the beginning (since we're a first-letter frame),
-  //     so just doing a linear search for the prevSibling is ok.
-  // 3)  Trying to use FindPreviousSibling will fail if the first-letter is in
-  //     anonymous content (eg generated content).
-  const nsFrameList& siblingList(parentFrame->GetChildList(nsnull));
-  NS_ASSERTION(siblingList.ContainsFrame(placeholderFrame),
-               "Placeholder not in parent's principal child list?");
-  nsIFrame* prevSibling = siblingList.GetPrevSiblingFor(placeholderFrame);
+  nsIFrame* prevSibling = placeholderFrame->GetPrevSibling();
 
   // Now that everything is set...
 #ifdef NOISY_FIRST_LETTER
   printf("RemoveFloatingFirstLetterFrames: textContent=%p oldTextFrame=%p newTextFrame=%p\n",
          textContent.get(), textFrame, newTextFrame);
 #endif
 
   // Remove the float frame
--- a/layout/base/nsFrameTraversal.cpp
+++ b/layout/base/nsFrameTraversal.cpp
@@ -499,20 +499,17 @@ nsFrameIterator::GetLastChildInner(nsIFr
 
 nsIFrame*
 nsFrameIterator::GetNextSiblingInner(nsIFrame* aFrame) {
   return aFrame->GetNextSibling();
 }
 
 nsIFrame*
 nsFrameIterator::GetPrevSiblingInner(nsIFrame* aFrame) {
-  nsIFrame* parent = GetParentFrame(aFrame);
-  if (!parent)
-    return nsnull;
-  return parent->GetChildList(nsnull).GetPrevSiblingFor(aFrame);
+  return aFrame->GetPrevSibling();
 }
 
 
 nsIFrame*
 nsFrameIterator::GetPlaceholderFrame(nsIFrame* aFrame)
 {
   nsIFrame* result = aFrame;
   nsIPresShell *presShell = mPresContext->GetPresShell();
--- a/layout/generic/nsBlockFrame.cpp
+++ b/layout/generic/nsBlockFrame.cpp
@@ -3256,17 +3256,17 @@ nsBlockFrame::ReflowBlockFrame(nsBlockRe
               // It already exists, but as a normal next-in-flow, so we need
               // to dig it out of the child lists.
               nsContainerFrame* parent = static_cast<nsContainerFrame*>
                                            (nextFrame->GetParent());
               rv = parent->StealFrame(aState.mPresContext, nextFrame);
               NS_ENSURE_SUCCESS(rv, rv);
             }
             else if (madeContinuation) {
-              mFrames.RemoveFrame(nextFrame, frame);
+              mFrames.RemoveFrame(nextFrame);
             }
 
             // Put it in our overflow list
             aState.mOverflowTracker->Insert(nextFrame, frameReflowStatus);
             NS_MergeReflowStatusInto(&aState.mReflowStatus, frameReflowStatus);
 
 #ifdef NOISY_VERTICAL_MARGINS
             ListTag(stdout);
@@ -5198,63 +5198,48 @@ nsBlockFrame::DoRemoveFrame(nsIFrame* aD
   nsIFrame* next = aDeletedFrame->GetNextInFlow();
   if (next && next->GetStateBits() & NS_FRAME_IS_OVERFLOW_CONTAINER) {
     static_cast<nsContainerFrame*>(next->GetParent())
       ->DeleteNextInFlowChild(next->PresContext(), next, PR_FALSE);
   }
 
   nsIPresShell* presShell = presContext->PresShell();
 
-  // Find the line and the previous sibling that contains
-  // deletedFrame; we also find the pointer to the line.
+  // Find the line that contains deletedFrame
   nsLineList::iterator line_start = mLines.begin(),
                        line_end = mLines.end();
   nsLineList::iterator line = line_start;
   PRBool searchingOverflowList = PR_FALSE;
-  nsIFrame* prevSibling = nsnull;
   // Make sure we look in the overflow lines even if the normal line
   // list is empty
   TryAllLines(&line, &line_start, &line_end, &searchingOverflowList);
   while (line != line_end) {
-    nsIFrame* frame = line->mFirstChild;
-    PRInt32 n = line->GetChildCount();
-    while (--n >= 0) {
-      if (frame == aDeletedFrame) {
-        goto found_frame;
-      }
-      prevSibling = frame;
-      frame = frame->GetNextSibling();
+    if (line->Contains(aDeletedFrame)) {
+      break;
     }
     ++line;
     TryAllLines(&line, &line_start, &line_end, &searchingOverflowList);
   }
-found_frame:;
+
   if (line == line_end) {
     NS_ERROR("can't find deleted frame in lines");
     return NS_ERROR_FAILURE;
   }
   
   if (!(aFlags & FRAMES_ARE_EMPTY)) {
     if (line != line_start) {
       line.prev()->MarkDirty();
       line.prev()->SetInvalidateTextRuns(PR_TRUE);
     }
     else if (searchingOverflowList && !mLines.empty()) {
       mLines.back()->MarkDirty();
       mLines.back()->SetInvalidateTextRuns(PR_TRUE);
     }
   }
 
-  if (prevSibling && !prevSibling->GetNextSibling()) {
-    // We must have found the first frame in the overflow line list. So
-    // there is no prevSibling
-    prevSibling = nsnull;
-  }
-  NS_ASSERTION(!prevSibling || prevSibling->GetNextSibling() == aDeletedFrame, "bad prevSibling");
-
   while ((line != line_end) && (nsnull != aDeletedFrame)) {
     NS_ASSERTION(this == aDeletedFrame->GetParent(), "messed up delete code");
     NS_ASSERTION(line->Contains(aDeletedFrame), "frame not in line");
 
     if (!(aFlags & FRAMES_ARE_EMPTY)) {
       line->MarkDirty();
       line->SetInvalidateTextRuns(PR_TRUE);
     }
@@ -5282,23 +5267,24 @@ found_frame:;
       line->MarkDirty();
     }
     ++line;
 
     // Take aDeletedFrame out of the sibling list. Note that
     // prevSibling will only be nsnull when we are deleting the very
     // first frame in the main or overflow list.
     if (searchingOverflowList) {
+      nsIFrame* prevSibling = aDeletedFrame->GetPrevSibling();
       if (prevSibling) {
         // XXXbz If we switch overflow lines to nsFrameList, we should
         // change this SetNextSibling call.
         prevSibling->SetNextSibling(nextFrame);
       }
     } else {
-      mFrames.RemoveFrame(aDeletedFrame, prevSibling);
+      mFrames.RemoveFrame(aDeletedFrame);
     }
 
     // Update the child count of the line to be accurate
     PRInt32 lineChildCount = line->GetChildCount();
     lineChildCount--;
     line->SetChildCount(lineChildCount);
 
     // Destroy frame; capture its next continuation first in case we need
@@ -5380,30 +5366,20 @@ found_frame:;
       if (haveAdvancedToNextLine) {
         if (line != line_end && !searchingOverflowList &&
             !line->Contains(deletedNextContinuation)) {
           // We have advanced to the next *normal* line but the next-in-flow
           // is not there - force a switch to the overflow line list.
           line = line_end;
         }
 
-        PRBool wasSearchingOverflowList = searchingOverflowList;
         TryAllLines(&line, &line_start, &line_end, &searchingOverflowList);
-        if (NS_UNLIKELY(searchingOverflowList && !wasSearchingOverflowList &&
-                        prevSibling)) {
-          // We switched to the overflow line list and we have a prev sibling
-          // (in the main list), in this case we don't want to pick up any
-          // sibling list from the deceased frames (bug 344557).
-          NS_ASSERTION(!prevSibling->GetNextSibling(), "Unexpected next sibling");
-          prevSibling = nsnull;
-        }
 #ifdef NOISY_REMOVE_FRAME
-        printf("DoRemoveFrame: now on %s line=%p prevSibling=%p\n",
-               searchingOverflowList?"overflow":"normal", line.get(),
-               prevSibling);
+        printf("DoRemoveFrame: now on %s line=%p\n",
+               searchingOverflowList?"overflow":"normal", line.get());
 #endif
       }
     }
   }
 
   if (!(aFlags & FRAMES_ARE_EMPTY) && line.next() != line_end) {
     line.next()->MarkDirty();
     line.next()->SetInvalidateTextRuns(PR_TRUE);
@@ -5462,17 +5438,17 @@ nsBlockFrame::StealFrame(nsPresContext* 
         }
         if (searchingOverflowList) {
           // XXXbz If we switch overflow lines to nsFrameList, we should
           // change this SetNextSibling call.
           if (prevSibling)
             prevSibling->SetNextSibling(frame->GetNextSibling());
           frame->SetNextSibling(nsnull);
         } else {
-          mFrames.RemoveFrame(frame, prevSibling);
+          mFrames.RemoveFrame(frame);
         }
 
         // Register removal with the line boxes
         PRInt32 count = line->GetChildCount();
         line->SetChildCount(--count);
         if (count > 0) {
            line->MarkDirty();
         }
--- a/layout/generic/nsFrame.cpp
+++ b/layout/generic/nsFrame.cpp
@@ -4765,21 +4765,20 @@ FindBlockFrameOrBR(nsIFrame* aFrame, nsD
     aFrame->GetOffsets(startOffset, endOffset);
     result.mContent = aFrame->GetContent();
     result.mOffset = endOffset - (aDirection == eDirPrevious ? 0 : 1);
     return result;
   }
 
   // Iterate over children and call ourselves recursively
   if (aDirection == eDirPrevious) {
-    const nsFrameList& children(aFrame->GetChildList(nsnull));
-    nsIFrame* child = children.LastChild();
+    nsIFrame* child = aFrame->GetChildList(nsnull).LastChild();
     while(child && !result.mContent) {
       result = FindBlockFrameOrBR(child, aDirection);
-      child = children.GetPrevSiblingFor(child);
+      child = child->GetPrevSibling();
     }
   } else { // eDirNext
     nsIFrame* child = aFrame->GetFirstChild(nsnull);
     while(child && !result.mContent) {
       result = FindBlockFrameOrBR(child, aDirection);
       child = child->GetNextSibling();
     }
   }
@@ -4802,21 +4801,20 @@ nsIFrame::PeekOffsetParagraph(nsPeekOffs
   if (aPos->mDirection == eDirPrevious) {
     while (!reachedBlockAncestor) {
       nsIFrame* parent = frame->GetParent();
       // Treat a frame associated with the root content as if it were a block frame.
       if (!frame->mContent || !frame->mContent->GetParent()) {
         reachedBlockAncestor = PR_TRUE;
         break;
       }
-      const nsFrameList& siblings(parent->GetChildList(nsnull));
-      nsIFrame* sibling = siblings.GetPrevSiblingFor(frame);
+      nsIFrame* sibling = frame->GetPrevSibling();
       while (sibling && !blockFrameOrBR.mContent) {
         blockFrameOrBR = FindBlockFrameOrBR(sibling, eDirPrevious);
-        sibling = siblings.GetPrevSiblingFor(sibling);
+        sibling = sibling->GetPrevSibling();
       }
       if (blockFrameOrBR.mContent) {
         aPos->mResultContent = blockFrameOrBR.mContent;
         aPos->mContentOffset = blockFrameOrBR.mOffset;
         break;
       }
       frame = parent;
       reachedBlockAncestor = (nsLayoutUtils::GetAsBlock(frame) != nsnull);
--- a/layout/generic/nsFrameList.cpp
+++ b/layout/generic/nsFrameList.cpp
@@ -89,52 +89,49 @@ nsFrameList::SetFrames(nsIFrame* aFrameL
 {
   NS_PRECONDITION(!mFirstChild, "Losing frames");
 
   mFirstChild = aFrameList;
   mLastChild = nsLayoutUtils::GetLastSibling(mFirstChild);
 }
 
 void
-nsFrameList::RemoveFrame(nsIFrame* aFrame, nsIFrame* aPrevSiblingHint)
+nsFrameList::RemoveFrame(nsIFrame* aFrame)
 {
   NS_PRECONDITION(aFrame, "null ptr");
   NS_PRECONDITION(ContainsFrame(aFrame), "wrong list");
 
   nsIFrame* nextFrame = aFrame->GetNextSibling();
   if (aFrame == mFirstChild) {
     mFirstChild = nextFrame;
     aFrame->SetNextSibling(nsnull);
     if (!nextFrame) {
       mLastChild = nsnull;
     }
   }
   else {
-    nsIFrame* prevSibling = aPrevSiblingHint;
-    if (!prevSibling || prevSibling->GetNextSibling() != aFrame) {
-      prevSibling = GetPrevSiblingFor(aFrame);
-    }
-    if (prevSibling) {
-      prevSibling->SetNextSibling(nextFrame);
-      aFrame->SetNextSibling(nsnull);
-      if (!nextFrame) {
-        mLastChild = prevSibling;
-      }
+    nsIFrame* prevSibling = aFrame->GetPrevSibling();
+    NS_ASSERTION(prevSibling && prevSibling->GetNextSibling() == aFrame,
+                 "Broken frame linkage");
+    prevSibling->SetNextSibling(nextFrame);
+    aFrame->SetNextSibling(nsnull);
+    if (!nextFrame) {
+      mLastChild = prevSibling;
     }
   }
 }
 
 PRBool
 nsFrameList::RemoveFrameIfPresent(nsIFrame* aFrame)
 {
   NS_PRECONDITION(aFrame, "null ptr");
 
-  for (FrameLinkEnumerator iter(*this); !iter.AtEnd(); iter.Next()) {
-    if (iter.NextFrame() == aFrame) {
-      RemoveFrame(aFrame, iter.PrevFrame());
+  for (Enumerator e(*this); !e.AtEnd(); e.Next()) {
+    if (e.get() == aFrame) {
+      RemoveFrame(aFrame);
       return PR_TRUE;
     }
   }
   return PR_FALSE;
 }
 
 nsFrameList
 nsFrameList::RemoveFramesAfter(nsIFrame* aAfterFrame)
@@ -156,20 +153,20 @@ nsFrameList::RemoveFirstChild()
   if (mFirstChild) {
     RemoveFrame(mFirstChild);
     return PR_TRUE;
   }
   return PR_FALSE;
 }
 
 void
-nsFrameList::DestroyFrame(nsIFrame* aFrame, nsIFrame* aPrevSiblingHint)
+nsFrameList::DestroyFrame(nsIFrame* aFrame)
 {
   NS_PRECONDITION(aFrame, "null ptr");
-  RemoveFrame(aFrame, aPrevSiblingHint);
+  RemoveFrame(aFrame);
   aFrame->Destroy();
 }
 
 PRBool
 nsFrameList::DestroyFrameIfPresent(nsIFrame* aFrame)
 {
   NS_PRECONDITION(aFrame, "null ptr");
 
@@ -426,38 +423,16 @@ nsFrameList::SortByContentOrder()
     nsIFrame* ff = array.ElementAt(i);
     f->SetNextSibling(ff);
     f = ff;
   }
   f->SetNextSibling(nsnull);
   mLastChild = f;
 }
 
-nsIFrame*
-nsFrameList::GetPrevSiblingFor(nsIFrame* aFrame) const
-{
-  NS_PRECONDITION(aFrame, "null ptr");
-  NS_PRECONDITION(mFirstChild, "GetPrevSiblingFor() on empty frame list");
-
-  if (aFrame == mFirstChild) {
-    return nsnull;
-  }
-  nsIFrame* frame = mFirstChild;
-  while (frame) {
-    nsIFrame* next = frame->GetNextSibling();
-    if (next == aFrame) {
-      break;
-    }
-    frame = next;
-  }
-
-  NS_POSTCONDITION(frame, "GetPrevSiblingFor() on wrong frame list");
-  return frame;
-}
-
 void
 nsFrameList::ApplySetParent(nsIFrame* aParent) const
 {
   NS_ASSERTION(aParent, "null ptr");
 
   for (nsIFrame* f = FirstChild(); f; f = f->GetNextSibling()) {
     f->SetParent(aParent);
   }
@@ -480,17 +455,17 @@ nsFrameList::List(FILE* out) const
 nsIFrame*
 nsFrameList::GetPrevVisualFor(nsIFrame* aFrame) const
 {
   if (!mFirstChild)
     return nsnull;
   
   nsIFrame* parent = mFirstChild->GetParent();
   if (!parent)
-    return aFrame ? GetPrevSiblingFor(aFrame) : LastChild();
+    return aFrame ? aFrame->GetPrevSibling() : LastChild();
 
   nsBidiLevel baseLevel = nsBidiPresUtils::GetFrameBaseLevel(mFirstChild);  
   nsBidiPresUtils* bidiUtils = mFirstChild->PresContext()->GetBidiUtils();
 
   nsAutoLineIterator iter = parent->GetLineIterator();
   if (!iter) { 
     // Parent is not a block Frame
     if (parent->GetType() == nsGkAtoms::lineFrame) {
@@ -499,17 +474,17 @@ nsFrameList::GetPrevVisualFor(nsIFrame* 
         return bidiUtils->GetFrameToLeftOf(aFrame, mFirstChild, -1);
       } else { // RTL
         return bidiUtils->GetFrameToRightOf(aFrame, mFirstChild, -1);
       }
     } else {
       // Just get the next or prev sibling, depending on block and frame direction.
       nsBidiLevel frameEmbeddingLevel = nsBidiPresUtils::GetFrameEmbeddingLevel(mFirstChild);
       if ((frameEmbeddingLevel & 1) == (baseLevel & 1)) {
-        return aFrame ? GetPrevSiblingFor(aFrame) : LastChild();
+        return aFrame ? aFrame->GetPrevSibling() : LastChild();
       } else {
         return aFrame ? aFrame->GetNextSibling() : mFirstChild;
       }    
     }
   }
 
   // Parent is a block frame, so use the LineIterator to find the previous visual 
   // sibling on this line, or the last one on the previous line.
@@ -555,17 +530,17 @@ nsFrameList::GetPrevVisualFor(nsIFrame* 
 nsIFrame*
 nsFrameList::GetNextVisualFor(nsIFrame* aFrame) const
 {
   if (!mFirstChild)
     return nsnull;
   
   nsIFrame* parent = mFirstChild->GetParent();
   if (!parent)
-    return aFrame ? GetPrevSiblingFor(aFrame) : mFirstChild;
+    return aFrame ? aFrame->GetPrevSibling() : mFirstChild;
 
   nsBidiLevel baseLevel = nsBidiPresUtils::GetFrameBaseLevel(mFirstChild);
   nsBidiPresUtils* bidiUtils = mFirstChild->PresContext()->GetBidiUtils();
   
   nsAutoLineIterator iter = parent->GetLineIterator();
   if (!iter) { 
     // Parent is not a block Frame
     if (parent->GetType() == nsGkAtoms::lineFrame) {
@@ -576,17 +551,17 @@ nsFrameList::GetNextVisualFor(nsIFrame* 
         return bidiUtils->GetFrameToLeftOf(aFrame, mFirstChild, -1);
       }
     } else {
       // Just get the next or prev sibling, depending on block and frame direction.
       nsBidiLevel frameEmbeddingLevel = nsBidiPresUtils::GetFrameEmbeddingLevel(mFirstChild);
       if ((frameEmbeddingLevel & 1) == (baseLevel & 1)) {
         return aFrame ? aFrame->GetNextSibling() : mFirstChild;
       } else {
-        return aFrame ? GetPrevSiblingFor(aFrame) : LastChild();
+        return aFrame ? aFrame->GetPrevSibling() : LastChild();
       }
     }
   }
 
   // Parent is a block frame, so use the LineIterator to find the next visual 
   // sibling on this line, or the first one on the next line.
   
   PRInt32 thisLine;
--- a/layout/generic/nsFrameList.h
+++ b/layout/generic/nsFrameList.h
@@ -117,22 +117,21 @@ public:
    * reparents the newly added frame.
    */
   void AppendFrame(nsIFrame* aParent, nsIFrame* aFrame) {
     nsFrameList temp(aFrame, aFrame);
     AppendFrames(aParent, temp);
   }
 
   /**
+   * Take aFrame out of the frame list. This also disconnects aFrame
    * from the sibling list. The frame must be non-null and present on
    * this list.
-   * The second frame is a hint for the prev-sibling of aFrame; if the
-   * hint is correct, then this is O(1) time.
    */
-  void RemoveFrame(nsIFrame* aFrame, nsIFrame* aPrevSiblingHint = nsnull);
+  void RemoveFrame(nsIFrame* aFrame);
 
   /**
    * Take aFrame out of the frame list, if present. This also disconnects
    * aFrame from the sibling list. aFrame must be non-null but is not
    * required to be on the list.
    * @return PR_TRUE if aFrame was removed
    */
   PRBool RemoveFrameIfPresent(nsIFrame* aFrame);
@@ -148,20 +147,18 @@ public:
    * Take the first frame (if any) out of the frame list.
    * @return PR_TRUE if a frame was removed
    */
   PRBool RemoveFirstChild();
 
   /**
    * Take aFrame out of the frame list and then destroy it.
    * The frame must be non-null and present on this list.
-   * The second frame is a hint for the prev-sibling of aFrame; if the
-   * hint is correct, then this is O(1) time.
    */
-  void DestroyFrame(nsIFrame* aFrame, nsIFrame* aPrevSiblingHint = nsnull);
+  void DestroyFrame(nsIFrame* aFrame);
 
   /**
    * If aFrame is present on this list then take it out of the list and
    * then destroy it. The frame must be non-null.
    * @return PR_TRUE if the frame was found
    */
   PRBool DestroyFrameIfPresent(nsIFrame* aFrame);
 
@@ -230,18 +227,16 @@ public:
     return nsnull != mFirstChild;
   }
 
   PRBool ContainsFrame(const nsIFrame* aFrame) const;
   PRBool ContainsFrameBefore(const nsIFrame* aFrame, const nsIFrame* aEnd) const;
 
   PRInt32 GetLength() const;
 
-  nsIFrame* GetPrevSiblingFor(nsIFrame* aFrame) const;
-
   /**
    * If this frame list has only one frame, return that frame.
    * Otherwise, return null.
    */
   nsIFrame* OnlyChild() const {
     if (FirstChild() == LastChild()) {
       return FirstChild();
     }
--- a/layout/generic/nsIFrame.h
+++ b/layout/generic/nsIFrame.h
@@ -872,24 +872,32 @@ public:
     return GetChildList(aListName).FirstChild();
   }
   // XXXmats this method should also go away then
   nsIFrame* GetLastChild(nsIAtom* aListName) const {
     return GetChildList(aListName).LastChild();
   }
 
   /**
-   * Child frames are linked together in a singly-linked list
+   * Child frames are linked together in a doubly-linked list
    */
   nsIFrame* GetNextSibling() const { return mNextSibling; }
   void SetNextSibling(nsIFrame* aNextSibling) {
-    NS_ASSERTION(this != aNextSibling, "Creating a circular frame list, this is very bad."); 
+    NS_ASSERTION(this != aNextSibling, "Creating a circular frame list, this is very bad.");
+    if (mNextSibling && mNextSibling->GetPrevSibling() == this) {
+      mNextSibling->mPrevSibling = nsnull;
+    }
     mNextSibling = aNextSibling;
+    if (mNextSibling) {
+      mNextSibling->mPrevSibling = this;
+    }
   }
 
+  nsIFrame* GetPrevSibling() const { return mPrevSibling; }
+
   /**
    * Builds the display lists for the content represented by this frame
    * and its descendants. The background+borders of this element must
    * be added first, before any other content.
    * 
    * This should only be called by methods in nsFrame. Instead of calling this
    * directly, call either BuildDisplayListForStackingContext or
    * BuildDisplayListForChild.
@@ -2314,17 +2322,18 @@ NS_PTR_TO_INT32(frame->GetProperty(nsGkA
 
 protected:
   // Members
   nsRect           mRect;
   nsIContent*      mContent;
   nsStyleContext*  mStyleContext;
   nsIFrame*        mParent;
 private:
-  nsIFrame*        mNextSibling;  // singly-linked list of frames
+  nsIFrame*        mNextSibling;  // doubly-linked list of frames
+  nsIFrame*        mPrevSibling;  // Do not touch outside SetNextSibling!
 protected:
   nsFrameState     mState;
 
   // When there is an overflow area only slightly larger than mRect,
   // we store a set of four 1-byte deltas from the edges of mRect
   // rather than allocating a whole separate rectangle property.
   // Note that these are unsigned values, all measured "outwards"
   // from the edges of mRect, so /mLeft/ and /mTop/ are reversed from
--- a/layout/mathml/nsMathMLmoFrame.cpp
+++ b/layout/mathml/nsMathMLmoFrame.cpp
@@ -347,21 +347,20 @@ nsMathMLmoFrame::ProcessOperatorData()
 
     // flag if we have an embellished ancestor
     if (embellishAncestor != this)
       mFlags |= NS_MATHML_OPERATOR_EMBELLISH_ANCESTOR;
     else
       mFlags &= ~NS_MATHML_OPERATOR_EMBELLISH_ANCESTOR;
 
     // find the position of our outermost embellished container w.r.t
-    // its siblings (frames are singly-linked together).
-    const nsFrameList& frameList(parentAncestor->GetChildList(nsnull));
+    // its siblings.
 
     nsIFrame* nextSibling = embellishAncestor->GetNextSibling();
-    nsIFrame* prevSibling = frameList.GetPrevSiblingFor(embellishAncestor);
+    nsIFrame* prevSibling = embellishAncestor->GetPrevSibling();
 
     // flag to distinguish from a real infix
     if (!prevSibling && !nextSibling)
       mFlags |= NS_MATHML_OPERATOR_EMBELLISH_ISOLATED;
     else
       mFlags &= ~NS_MATHML_OPERATOR_EMBELLISH_ISOLATED;
 
     // find our form
--- a/layout/tables/nsTableFrame.cpp
+++ b/layout/tables/nsTableFrame.cpp
@@ -1948,39 +1948,38 @@ void
 nsTableFrame::PushChildren(const FrameArray& aFrames,
                            PRInt32 aPushFrom)
 {
   NS_PRECONDITION(aPushFrom > 0, "pushing first child");
 
   // extract the frames from the array into a sibling list
   nsFrameList frames;
   PRUint32 childX;
-  nsIFrame* prevSiblingHint = aFrames.SafeElementAt(aPushFrom - 1);
   for (childX = aPushFrom; childX < aFrames.Length(); ++childX) {
     nsIFrame* f = aFrames[childX];
     // Don't push repeatable frames, do push non-rowgroup frames.
     // XXXbz Need to push the non-rowgroup frames, even though we don't reflow
     // them, so that we don't lose them.  Of course there shouldn't be any
     // non-rowgroup frames here...
     nsTableRowGroupFrame* rgFrame = GetRowGroupFrame(f);
     NS_ASSERTION(rgFrame, "Unexpected non-row-group frame");
     if (!rgFrame || !rgFrame->IsRepeatable()) {
-      mFrames.RemoveFrame(f, prevSiblingHint);
+      mFrames.RemoveFrame(f);
       frames.AppendFrame(nsnull, f);
     }
   }
 
   if (nsnull != GetNextInFlow()) {
     nsTableFrame* nextInFlow = (nsTableFrame*)GetNextInFlow();
 
     // Insert the frames after any repeated header and footer frames
     nsIFrame* firstBodyFrame = nextInFlow->GetFirstBodyRowGroupFrame();
     nsIFrame* prevSibling = nsnull;
     if (firstBodyFrame) {
-      prevSibling = nextInFlow->mFrames.GetPrevSiblingFor(firstBodyFrame);
+      prevSibling = firstBodyFrame->GetPrevSibling();
     }
     // When pushing and pulling frames we need to check for whether any
     // views need to be reparented.
     ReparentFrameViewList(PresContext(), frames, this, nextInFlow);
     nextInFlow->mFrames.InsertFrames(nextInFlow, prevSibling,
                                      frames);
   }
   else if (frames.NotEmpty()) {
--- a/layout/xul/base/src/nsBoxFrame.cpp
+++ b/layout/xul/base/src/nsBoxFrame.cpp
@@ -2088,44 +2088,38 @@ nsBoxFrame::LayoutChildAt(nsBoxLayoutSta
 NS_IMETHODIMP
 nsBoxFrame::RelayoutChildAtOrdinal(nsBoxLayoutState& aState, nsIBox* aChild)
 {
   if (!SupportsOrdinalsInChildren())
     return NS_OK;
 
   PRUint32 ord = aChild->GetOrdinal(aState);
   
-  nsIFrame *child = mFrames.FirstChild();
-  nsIFrame *curPrevSib = nsnull, *newPrevSib = nsnull;
-  PRBool foundPrevSib = PR_FALSE, foundNewPrevSib = PR_FALSE;
+  nsIFrame* child = mFrames.FirstChild();
+  nsIFrame* newPrevSib = nsnull;
 
   while (child) {
-    if (child == aChild)
-      foundPrevSib = PR_TRUE;
-    else if (!foundPrevSib)
-      curPrevSib = child;
+    if (ord < child->GetOrdinal(aState)) {
+      break;
+    }
 
-    PRUint32 ordCmp = child->GetOrdinal(aState);
-    if (ord < ordCmp)
-      foundNewPrevSib = PR_TRUE;
-    else if (!foundNewPrevSib && child != aChild)
+    if (child != aChild) {
       newPrevSib = child;
+    }
 
     child = child->GetNextBox();
   }
 
-  NS_ASSERTION(foundPrevSib, "aChild not in frame list?");
-
-  if (curPrevSib == newPrevSib) {
+  if (aChild->GetPrevSibling() == newPrevSib) {
     // This box is not moving.
     return NS_OK;
   }
 
   // Take |aChild| out of its old position in the child list.
-  mFrames.RemoveFrame(aChild, curPrevSib);
+  mFrames.RemoveFrame(aChild);
 
   // Insert it after |newPrevSib| or at the start if it's null.
   mFrames.InsertFrame(nsnull, newPrevSib, aChild);
 
   return NS_OK;
 }
 
 /**
--- a/layout/xul/base/src/nsListBoxBodyFrame.cpp
+++ b/layout/xul/base/src/nsListBoxBodyFrame.cpp
@@ -1105,17 +1105,17 @@ nsListBoxBodyFrame::ReverseDestroyRows(P
   nsBoxLayoutState state(PresContext());
 
   nsCSSFrameConstructor* fc = PresContext()->PresShell()->FrameConstructor();
   fc->BeginUpdate();
   while (childFrame && aRowsToLose > 0) {
     --aRowsToLose;
     
     nsIFrame* prevFrame;
-    prevFrame = mFrames.GetPrevSiblingFor(childFrame);
+    prevFrame = childFrame->GetPrevSibling();
     RemoveChildFrame(state, childFrame);
 
     mBottomFrame = childFrame = prevFrame;
   }
   fc->EndUpdate();
 
   PresContext()->PresShell()->
     FrameNeedsReflow(this, nsIPresShell::eTreeChange,
--- a/layout/xul/base/src/nsSplitterFrame.cpp
+++ b/layout/xul/base/src/nsSplitterFrame.cpp
@@ -869,18 +869,17 @@ nsSplitterFrameInner::UpdateState()
     return;
   }
 
   if ((SupportsCollapseDirection(Before) || SupportsCollapseDirection(After)) &&
       mOuter->GetParent()->IsBoxFrame()) {
     // Find the splitter's immediate sibling.
     nsIFrame* splitterSibling;
     if (newState == CollapsedBefore || mState == CollapsedBefore) {
-      splitterSibling =
-        mOuter->GetParent()->GetChildList(nsnull).GetPrevSiblingFor(mOuter);
+      splitterSibling = mOuter->GetPrevSibling();
     } else {
       splitterSibling = mOuter->GetNextSibling();
     }
 
     if (splitterSibling) {
       nsCOMPtr<nsIContent> sibling = splitterSibling->GetContent();
       if (sibling) {
         if (mState == CollapsedBefore || mState == CollapsedAfter) {
--- a/layout/xul/base/src/nsXULPopupManager.cpp
+++ b/layout/xul/base/src/nsXULPopupManager.cpp
@@ -1804,40 +1804,40 @@ nsXULPopupManager::GetPreviousMenuItem(n
     FrameConstructor()->GetInsertionPoint(aParent, nsnull, &immediateParent);
   if (!immediateParent)
     immediateParent = aParent;
 
   const nsFrameList& frames(immediateParent->GetChildList(nsnull));
 
   nsIFrame* currFrame = nsnull;
   if (aStart)
-    currFrame = frames.GetPrevSiblingFor(aStart);
+    currFrame = aStart->GetPrevSibling();
   else
     currFrame = frames.LastChild();
 
   while (currFrame) {
     // See if it's a menu item.
     if (IsValidMenuItem(presContext, currFrame->GetContent(), aIsPopup)) {
       return (currFrame->GetType() == nsGkAtoms::menuFrame) ?
              static_cast<nsMenuFrame *>(currFrame) : nsnull;
     }
-    currFrame = frames.GetPrevSiblingFor(currFrame);
+    currFrame = currFrame->GetPrevSibling();
   }
 
   currFrame = frames.LastChild();
 
   // Still don't have anything. Try cycling from the end.
   while (currFrame && currFrame != aStart) {
     // See if it's a menu item.
     if (IsValidMenuItem(presContext, currFrame->GetContent(), aIsPopup)) {
       return (currFrame->GetType() == nsGkAtoms::menuFrame) ?
              static_cast<nsMenuFrame *>(currFrame) : nsnull;
     }
 
-    currFrame = frames.GetPrevSiblingFor(currFrame);
+    currFrame = currFrame->GetPrevSibling();
   }
 
   // No luck. Just return our start value.
   return aStart;
 }
 
 PRBool
 nsXULPopupManager::IsValidMenuItem(nsPresContext* aPresContext,
--- a/layout/xul/base/src/tree/src/nsTreeColFrame.cpp
+++ b/layout/xul/base/src/tree/src/nsTreeColFrame.cpp
@@ -125,17 +125,17 @@ nsDisplayXULTreeColSplitterTarget::HitTe
     right = tmp;
   }
 
   if (left || right) {
     // We are a header. Look for the correct splitter.
     const nsFrameList& frames(mFrame->GetParent()->GetChildList(nsnull));
     nsIFrame* child;
     if (left)
-      child = frames.GetPrevSiblingFor(mFrame);
+      child = mFrame->GetPrevSibling();
     else
       child = mFrame->GetNextSibling();
 
     if (child && child->GetContent()->NodeInfo()->Equals(nsGkAtoms::splitter,
                                                          kNameSpaceID_XUL)) {
       return child;
     }
   }