OrderIterator should be O(number of children)

Source/core/rendering/OrderIterator.h

Index: Source/core/rendering/OrderIterator.h
diff --git a/Source/core/rendering/OrderIterator.h b/Source/core/rendering/OrderIterator.h
index 8639bdcb1001f7a24c31fcdf2470ab73822bf86d..8704078968c6cd215facd2cacd9f4dfe71643039 100644
--- a/Source/core/rendering/OrderIterator.h
+++ b/Source/core/rendering/OrderIterator.h
@@ -31,6 +31,7 @@
 #ifndef OrderIterator_h
 #define OrderIterator_h
 
+#include "wtf/HashMap.h"
 #include "wtf/Noncopyable.h"
 #include "wtf/Vector.h"
 
@@ -38,6 +39,16 @@ namespace WebCore {
 
 class RenderBox;
 
+// Normally, -1 and 0 are not valid in a HashSet, but these are relatively likel y order: values. Instead,
+// we make the two smallest int values invalid order: values (in the css parser code we clamp them to
+// int min + 2).
+struct OrdererValueMapKeyHashTraits : WTF::GenericHashTraits<int> {
+    static const bool emptyValueIsZero = false;
+    static int emptyValue() { return std::numeric_limits<int>::min(); }
+    static void constructDeletedValue(int& slot) { slot = std::numeric_limits<int>::min() + 1; }
+    static bool isDeletedValue(int value) { return value == std::numeric_limits<int>::min() + 1; }
+};
+
 class OrderIterator {
     WTF_MAKE_NONCOPYABLE(OrderIterator);
 public:
@@ -52,34 +63,38 @@ public:
 
 private:
     const RenderBox* m_containerBox;
-    RenderBox* m_currentChild;
+
     // The inline capacity for a single item is used to cover the most
     // common case by far: if we only have the default 'order' value 0.
     typedef Vector<int, 1> OrderValues;
     OrderValues m_orderValues;
-    Vector<int>::const_iterator m_orderValuesIterator;
+
+    RenderBox* m_currentChild;
+    size_t m_currentOrderIndex;
+    size_t m_currentChildIndex;
+
+    // This HashMap is empty if there is only one value.
+    typedef HashMap<int, Vector<RenderBox*>, DefaultHash<int>::Hash, OrdererValueMapKeyHashTraits > OrderedValuesMap;
+    OrderedValuesMap m_orderedValues;
 };
 
 class OrderIteratorPopulator {
 public:
     OrderIteratorPopulator(OrderIterator& iterator)
         : m_iterator(iterator)
-        , m_anyChildHasDefaultOrderValue(false)
     {
         // Note that we don't release the memory here, we only invalidate the size.
         // This avoids unneeded reallocation if the size ends up not changing.
         m_iterator.m_orderValues.shrink(0);
+        m_iterator.m_orderedValues.clear();
     }
 
     ~OrderIteratorPopulator();
 
-    void collectChild(const RenderBox*);
+    void collectChild(RenderBox*);
 
 private:
-    void removeDuplicatedOrderValues();
-
     OrderIterator& m_iterator;
-    bool m_anyChildHasDefaultOrderValue;
 };
 
 } // namespace WebCore