First version of new merge algorithm (not enabled yet)

Source/platform/graphics/paint/DisplayItemList.h

Index: Source/platform/graphics/paint/DisplayItemList.h
diff --git a/Source/platform/graphics/paint/DisplayItemList.h b/Source/platform/graphics/paint/DisplayItemList.h
index c1949ad0a9d3f2bfdb2140a9089bf7e687794d61..810ba35668b4500175689285af8245bcf7b74466 100644
--- a/Source/platform/graphics/paint/DisplayItemList.h
+++ b/Source/platform/graphics/paint/DisplayItemList.h
@@ -7,6 +7,7 @@
 
 #include "platform/PlatformExport.h"
 #include "platform/graphics/paint/DisplayItem.h"
+#include "wtf/HashMap.h"
 #include "wtf/HashSet.h"
 #include "wtf/PassOwnPtr.h"
 #include "wtf/Vector.h"
@@ -25,9 +26,12 @@ public:
 
     void endNewPaints() { updatePaintList(); }
 
-    const PaintList& paintList();
+    const PaintList& paintList() const;
     void add(WTF::PassOwnPtr<DisplayItem>);
 
+    const PaintList& newPaintListForTesting() const { return m_newPaints; }

[chrishtr, 2015/02/03 22:30:48]

friend classses would be better for these two. Chromium has FRIEND_TEST to make
this easy..

[Xianzhu, 2015/02/04 00:13:24]

For now we can't include either <gtest/gtest.h> or "base/gtest_prod_util.h" from
non-testing blink code.

Use another way: let the test base classes be friend, and access the private
member in the base classes.

+    const PaintList& oldPaintListForTesting() const { return m_paintList; }
+
     void invalidate(DisplayItemClient);
     void invalidateAll();
     bool clientCacheIsValid(DisplayItemClient) const;
@@ -43,17 +47,28 @@ protected:
     DisplayItemList() { };
 
 private:
-    PaintList::iterator findNextMatchingCachedItem(PaintList::iterator, const DisplayItem&);
-    bool wasInvalidated(const DisplayItem&) const;
-    void updatePaintList();
-
 #ifndef NDEBUG
     WTF::String paintListAsDebugString(const PaintList&) const;
 #endif
 
+    void updatePaintList();
+
+    typedef HashSet<DisplayItemClient> DisplayItemClientSet;
+    typedef HashMap<DisplayItem::Id, size_t> DisplayItemIndexMap;
+
+    size_t findDisplayItemById(const DisplayItem::Id&) const;
+    size_t findMatchingCachedItem(const DisplayItem&) const;
+
+    static void appendDisplayItem(WTF::PassOwnPtr<DisplayItem>, PaintList&, DisplayItemClientSet&, DisplayItemIndexMap&);
+    void copyCachedSubtree(const DisplayItem&, PaintList&, DisplayItemClientSet&, DisplayItemIndexMap&);
+
     PaintList m_paintList;
-    HashSet<DisplayItemClient> m_cachedClients;
+    DisplayItemClientSet m_cachedClients;
+    DisplayItemIndexMap m_displayItemIndexMap;
     PaintList m_newPaints;
+#if ENABLE(ASSERT)
+    HashSet<DisplayItem::Id> m_newPaintIds;
+#endif
 };
 
 } // namespace blink