Setting up OrderIterator shouldn't require an extra Vector

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 13 matching lines @@
  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
 
 #include "config.h"
 #include "core/rendering/OrderIterator.h"
 
-#include "core/rendering/RenderFlexibleBox.h"
-#include "core/rendering/RenderGrid.h"
+#include "core/rendering/RenderBox.h"
 
 namespace WebCore {
 
 OrderIterator::OrderIterator(const RenderBox* containerBox)
     : m_containerBox(containerBox)
     , m_currentChild(0)
     , m_orderValuesIterator(0)
 {
 }
 
-void OrderIterator::setOrderValues(Vector<int>& orderValues)
-{
-    reset();
-    m_orderValues.clear();
-
-    if (orderValues.isEmpty())
-        return;
-
-    std::sort(orderValues.begin(), orderValues.end());
-
-
-    // This is inefficient if there are many repeated values, but
-    // saves a lot of allocations when the values are unique. By far,
-    // the common case is that there's exactly one item in the list
-    // (the default order value of 0).
-    m_orderValues.reserveInitialCapacity(orderValues.size());
-
-    int previous = orderValues[0];
-    m_orderValues.append(previous);
-    for (size_t i = 1; i < orderValues.size(); ++i) {
-        int current = orderValues[i];
-        if (current == previous)
-            continue;
-        m_orderValues.append(current);
-        previous = current;
-    }
-    m_orderValues.shrinkToFit();
-}
-
 RenderBox* OrderIterator::first()
 {
     reset();
     return next();
 }
 
 RenderBox* OrderIterator::next()
 {
     do {
         if (!m_currentChild) {
@@ skipping 15 matching lines @@
 
     return m_currentChild;
 }
 
 void OrderIterator::reset()
 {
     m_currentChild = 0;
     m_orderValuesIterator = 0;
 }
 
+OrderIteratorPopulator::~OrderIteratorPopulator()
+{
+    if (m_anyChildHasDefaultOrderValue)
+        m_iterator.m_orderValues.append(0);
+
+    m_iterator.reset();

[cbiesinger, 2013/07/10 19:35:32]

It feels weird to have this reset() call in the middle of setting up
m_orderValues. Maybe move it to the beginning or end of the destructor?

[Julien - ping for review, 2013/07/10 21:15:48]

Sounds good moved it to the beginning of the destructor.

+
+    if (m_iterator.m_orderValues.size() > 1)
+        removeDuplicatedOrderValues();
+
+    // 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)
+{
+    // Avoid growing the vector for the common-case default value of 0.
+    if (int order = child->style()->order())
+        m_iterator.m_orderValues.append(order);
+    else
+        m_anyChildHasDefaultOrderValue = true;
+}
+
 } // namespace WebCore