Bug 813358 part 3: Templatize nsBoxFrame's frame-sorting methods, to make the comparison function customizable. r=dbaron
authorDaniel Holbert <dholbert@cs.stanford.edu>
Fri, 30 Nov 2012 15:25:33 -0800
changeset 114666 5e89b39fd7d00fba4c1ba68b06e0e784b0253488
parent 114665 c01b1fbdacdf8d2fd6f9c1adb9450406e075738c
child 114667 58cb9bf14a4c8d3fe4a1789fd1a61941fb2c0d02
push id18911
push userdholbert@mozilla.com
push dateFri, 30 Nov 2012 23:27:10 +0000
treeherdermozilla-inbound@ceddb3b529de [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersdbaron
bugs813358
milestone20.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 813358 part 3: Templatize nsBoxFrame's frame-sorting methods, to make the comparison function customizable. r=dbaron
layout/xul/base/src/nsBoxFrame.cpp
--- a/layout/xul/base/src/nsBoxFrame.cpp
+++ b/layout/xul/base/src/nsBoxFrame.cpp
@@ -1892,24 +1892,25 @@ nsBoxFrame::RegUnregAccessKey(bool aDoRe
 }
 
 bool
 nsBoxFrame::SupportsOrdinalsInChildren()
 {
   return true;
 }
 
+template<bool IsLessThanOrEqual(nsIFrame*, nsIFrame*)>
 static nsIFrame*
 SortedMerge(nsIFrame *aLeft, nsIFrame *aRight)
 {
   NS_PRECONDITION(aLeft && aRight, "SortedMerge must have non-empty lists");
 
   nsIFrame *result;
   // Unroll first iteration to avoid null-check 'result' inside the loop.
-  if (aLeft->GetOrdinal() <= aRight->GetOrdinal()) {
+  if (IsLessThanOrEqual(aLeft, aRight)) {
     result = aLeft;
     aLeft = aLeft->GetNextSibling();
     if (!aLeft) {
       result->SetNextSibling(aRight);
       return result;
     }
   }
   else {
@@ -1918,17 +1919,17 @@ SortedMerge(nsIFrame *aLeft, nsIFrame *a
     if (!aRight) {
       result->SetNextSibling(aLeft);
       return result;
     }
   }
 
   nsIFrame *last = result;
   for (;;) {
-    if (aLeft->GetOrdinal() <= aRight->GetOrdinal()) {
+    if (IsLessThanOrEqual(aLeft, aRight)) {
       last->SetNextSibling(aLeft);
       last = aLeft;
       aLeft = aLeft->GetNextSibling();
       if (!aLeft) {
         last->SetNextSibling(aRight);
         return result;
       }
     }
@@ -1939,16 +1940,17 @@ SortedMerge(nsIFrame *aLeft, nsIFrame *a
       if (!aRight) {
         last->SetNextSibling(aLeft);
         return result;
       }
     }
   }
 }
 
+template<bool IsLessThanOrEqual(nsIFrame*, nsIFrame*)>
 static nsIFrame*
 MergeSort(nsIFrame *aSource)
 {
   NS_PRECONDITION(aSource, "MergeSort null arg");
 
   nsIFrame *sorted[32] = { nullptr };
   nsIFrame **fill = &sorted[0];
   nsIFrame **left;
@@ -1959,70 +1961,98 @@ MergeSort(nsIFrame *aSource)
     rest = rest->GetNextSibling();
     current->SetNextSibling(nullptr);
 
     // Merge it with sorted[0] if present; then merge the result with sorted[1] etc.
     // sorted[0] is a list of length 1 (or nullptr).
     // sorted[1] is a list of length 2 (or nullptr).
     // sorted[2] is a list of length 4 (or nullptr). etc.
     for (left = &sorted[0]; left != fill && *left; ++left) {
-      current = SortedMerge(*left, current);
+      current = SortedMerge<IsLessThanOrEqual>(*left, current);
       *left = nullptr;
     }
 
     // Fill the empty slot that we couldn't merge with the last result.
     *left = current;
 
     if (left == fill)
       ++fill;
   } while (rest);
 
   // Collect and merge the results.
   nsIFrame *result = nullptr;
   for (left = &sorted[0]; left != fill; ++left) {
     if (*left) {
-      result = result ? SortedMerge(*left, result) : *left;
+      result = result ? SortedMerge<IsLessThanOrEqual>(*left, result) : *left;
     }
   }
   return result;
 }
 
+// Forward-declare these so their definition can fall down below CheckBoxOrder
+// to make the diff prettier
+template<bool IsLessThanOrEqual(nsIFrame*, nsIFrame*)>
+bool IsFrameListSorted(nsFrameList& aFrameList);
+
+template<bool IsLessThanOrEqual(nsIFrame*, nsIFrame*)>
+void SortFrameList(nsFrameList& aFrameList);
+
+// Helper less-than-or-equal function, used in CheckBoxOrder() as a
+// template-parameter for the sorting functions.
+bool
+IsBoxOrdinalLEQ(nsIFrame* aFrame1,
+                nsIFrame* aFrame2)
+{
+  return aFrame1->GetOrdinal() <= aFrame2->GetOrdinal();
+}
+
 void 
 nsBoxFrame::CheckBoxOrder()
 {
-  if (!SupportsOrdinalsInChildren())
-    return;
+  if (SupportsOrdinalsInChildren() &&
+      !IsFrameListSorted<IsBoxOrdinalLEQ>(mFrames)) {
+    SortFrameList<IsBoxOrdinalLEQ>(mFrames);
+  }
+}
 
-  if (mFrames.IsEmpty()) {
+template<bool IsLessThanOrEqual(nsIFrame*, nsIFrame*)>
+bool
+IsFrameListSorted(nsFrameList& aFrameList)
+{
+  if (aFrameList.IsEmpty()) {
     // empty lists are trivially sorted.
-    return;
+    return true;
   }
 
   // We'll walk through the list with two iterators, one trailing behind the
   // other. The list is sorted IFF trailingIter <= iter, across the whole list.
-  nsFrameList::Enumerator trailingIter(mFrames);
-  nsFrameList::Enumerator iter(mFrames);
+  nsFrameList::Enumerator trailingIter(aFrameList);
+  nsFrameList::Enumerator iter(aFrameList);
   iter.Next(); // Skip |iter| past first frame. (List is nonempty, so we can.)
 
   // Now, advance the iterators in parallel, comparing each adjacent pair.
   while (!iter.AtEnd()) {
     MOZ_ASSERT(!trailingIter.AtEnd(), "trailing iter shouldn't finish first");
-    if (trailingIter.get()->GetOrdinal() > iter.get()->GetOrdinal()) {
-      break;
+    if (!IsLessThanOrEqual(trailingIter.get(), iter.get())) {
+      return false;
     }
     trailingIter.Next();
     iter.Next();
   }
 
-  // If we hit the end without breaking, then the list is sorted.
-  if (iter.AtEnd())
-    return;
+  // We made it to the end without returning early, so the list is sorted.
+  return true;
+}
 
-  nsIFrame* head = MergeSort(mFrames.FirstChild());
-  mFrames = nsFrameList(head, nsLayoutUtils::GetLastSibling(head));
+template<bool IsLessThanOrEqual(nsIFrame*, nsIFrame*)>
+void
+SortFrameList(nsFrameList& aFrameList)
+{
+  nsIFrame* head = MergeSort<IsLessThanOrEqual>(aFrameList.FirstChild());
+  aFrameList = nsFrameList(head, nsLayoutUtils::GetLastSibling(head));
 }
 
 nsresult
 nsBoxFrame::LayoutChildAt(nsBoxLayoutState& aState, nsIFrame* aBox, const nsRect& aRect)
 {
   // get the current rect
   nsRect oldRect(aBox->GetRect());
   aBox->SetBounds(aState, aRect);