OrderIterator should be O(number of children)

Source/core/rendering/OrderIterator.cpp

Index: Source/core/rendering/OrderIterator.cpp
diff --git a/Source/core/rendering/OrderIterator.cpp b/Source/core/rendering/OrderIterator.cpp
index d55779cc4cf8de6523a7a428241a3f9b5530328a..1bc7bc2929cc8cbb0718a96ca7f6fd928df9e97d 100644
--- a/Source/core/rendering/OrderIterator.cpp
+++ b/Source/core/rendering/OrderIterator.cpp
@@ -38,7 +38,8 @@ namespace WebCore {
 OrderIterator::OrderIterator(const RenderBox* containerBox)
     : m_containerBox(containerBox)
     , m_currentChild(0)
-    , m_orderValuesIterator(0)
+    , m_currentOrderIndex(0)
+    , m_currentChildIndex(0)
 {
 }
 
@@ -50,73 +51,50 @@ RenderBox* OrderIterator::first()
 
 RenderBox* OrderIterator::next()
 {
-    do {
-        if (!m_currentChild) {
-            if (m_orderValuesIterator == m_orderValues.end())
-                return 0;
-            if (m_orderValuesIterator) {
-                ++m_orderValuesIterator;
-                if (m_orderValuesIterator == m_orderValues.end())
-                    return 0;
-            } else {
-                m_orderValuesIterator = m_orderValues.begin();
-            }
-
-            m_currentChild = m_containerBox->firstChildBox();
-        } else {
-            m_currentChild = m_currentChild->nextSiblingBox();
+    for (; m_currentOrderIndex < m_orderValues.size(); ++m_currentOrderIndex) {
+        const Vector<RenderBox*>& currentOrderChildren = m_orderedValues.get(m_orderValues[m_currentOrderIndex]);
+        ASSERT(!currentOrderChildren.isEmpty());
+        for (; m_currentChildIndex < currentOrderChildren.size(); ++m_currentChildIndex) {

[tony, 2013/07/19 17:36:31]

Using a for loop here is weird since you always return in body.  This could be
an if statement.

+            m_currentChild = currentOrderChildren[m_currentChildIndex];
+            ++m_currentChildIndex;
+            return m_currentChild;
         }
-    } while (!m_currentChild || m_currentChild->style()->order() != *m_orderValuesIterator);
 
+        m_currentChildIndex = 0;
+    }
+
+    m_currentChild = 0;
     return m_currentChild;
 }
 
 void OrderIterator::reset()
 {
+    m_currentOrderIndex = 0;
+    m_currentChildIndex = 0;
     m_currentChild = 0;
-    m_orderValuesIterator = 0;
 }
 
 OrderIteratorPopulator::~OrderIteratorPopulator()
 {
     m_iterator.reset();
 
-    if (m_anyChildHasDefaultOrderValue)
-        m_iterator.m_orderValues.append(0);
-
-    if (m_iterator.m_orderValues.size() > 1)
-        removeDuplicatedOrderValues();
+    std::sort(m_iterator.m_orderValues.begin(), m_iterator.m_orderValues.end());
 
     // Ensure that we release any extra memory we hold onto.
     m_iterator.m_orderValues.shrinkToFit();
 }
 
-void OrderIteratorPopulator::removeDuplicatedOrderValues()
-{
-    OrderIterator::OrderValues& orderValues = m_iterator.m_orderValues;
-
-    std::sort(orderValues.begin(), orderValues.end());
-
-    int previous = orderValues[0];
-    size_t uniqueItemIndex = 0;
-    for (size_t i = 1; i < orderValues.size(); ++i) {
-        int current = orderValues[i];
-        if (current == previous)
-            continue;
-        ++uniqueItemIndex;
-        std::swap(orderValues[i], orderValues[uniqueItemIndex]);
-        previous = current;
-    }
-    orderValues.shrink(uniqueItemIndex + 1);
-}
-
-void OrderIteratorPopulator::collectChild(const RenderBox* child)
+void OrderIteratorPopulator::collectChild(RenderBox* child)
 {
-    // Avoid growing the vector for the common-case default value of 0.
-    if (int order = child->style()->order())
+    int order = child->style()->order();
+
+    // FIXME: Ideally we would want to avoid inserting into the HashMap for the common case where there are only items
+    // with the default 'order' 0. The current API is designed to blend into a single iteration which makes having a
+    // slower fallback difficult without having to store the children (grid items may not be contiguous in DOM order).
+    OrderIterator::OrderedValuesMap::AddResult result = m_iterator.m_orderedValues.add(order, Vector<RenderBox*>());

[tony, 2013/07/19 17:36:31]

Can we use a std::map<int, Vector<RenderBox*> > here?  Keeping 2 data structures
seems like extra complexity.

+    result.iterator->value.append(child);
+    if (result.isNewEntry)
         m_iterator.m_orderValues.append(order);
-    else
-        m_anyChildHasDefaultOrderValue = true;
 }
 
 } // namespace WebCore