OrderIterator should be O(number of children)

Source/core/rendering/OrderIterator.cpp

 /*
  * Copyright (C) 2011 Google Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions are
  * met:
  *
  *     * Redistributions of source code must retain the above copyright
  * notice, this list of conditions and the following disclaimer.
  *     * Redistributions in binary form must reproduce the above
@@ skipping 20 matching lines @@
 #include "config.h"
 #include "core/rendering/OrderIterator.h"
 
 #include "core/rendering/RenderBox.h"
 
 namespace WebCore {
 
 OrderIterator::OrderIterator(const RenderBox* containerBox)
     : m_containerBox(containerBox)
     , m_currentChild(0)
-    , m_orderValuesIterator(0)
+    , m_currentOrderIndex(0)
+    , m_currentChildIndex(0)
 {
 }
 
 RenderBox* OrderIterator::first()
 {
     reset();
     return next();
 }
 
 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();
-            }
+    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;
+        }
 
-            m_currentChild = m_containerBox->firstChildBox();
-        } else {
-            m_currentChild = m_currentChild->nextSiblingBox();
-        }
-    } 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()
+void OrderIteratorPopulator::collectChild(RenderBox* child)
 {
-    OrderIterator::OrderValues& orderValues = m_iterator.m_orderValues;
+    int order = child->style()->order();
 
-    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)
-{
-    // Avoid growing the vector for the common-case default value of 0.
-    if (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