Blink-side contiguous allocation of display items.

Source/platform/graphics/paint/DisplayItems.cpp

 // Copyright 2015 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "config.h"
 #include "platform/graphics/paint/DisplayItems.h"
 
+#include <algorithm>
+
 namespace blink {
 
+static const size_t capacityOfFirstInnerVector = 32;
+
 DisplayItems::DisplayItems()
 {
 }
 
 DisplayItems::~DisplayItems()
 {
 }
 
-void DisplayItems::append(PassOwnPtr<DisplayItem> displayItem)
-{
-    m_items.append(displayItem);
-}
-
 void DisplayItems::appendByMoving(const Iterator& it)
 {
-    // Release the underlying OwnPtr to move the display item ownership.
     ASSERT(!it->isGone());
-    append(it.m_iterator->release());
+
+    DisplayItem& oldItem = *it->m_ptr;
+    oldItem.appendByMoving(*this);
 }
 
 void DisplayItems::removeLast()
 {
+    ASSERT(!isEmpty());
+
+    // Find the last non-empty buffer. This is where the last element is.
+    auto isNonEmpty = [](const OwnPtr<InnerVector>& innerVector) -> bool {
+        return !innerVector->isEmpty();
+    };
+    auto it = std::find_if(m_buffers.rbegin(), m_buffers.rend(), isNonEmpty);
+    ASSERT(it != m_buffers.rend());
+
+    // This is the vector which contains the last element.
+    // We can now remove the element.
+    // (The pointer in m_items may be null to indicate "gone".)
+    InnerVector& innerVector = **it;
+    RELEASE_ASSERT(innerVector.last().asDisplayItem() == m_items.last() || !m_items.last());
+    innerVector.removeLast();
     m_items.removeLast();
+
+    // If there's an empty buffer after this one, remove it.
+    if (it != m_buffers.rbegin())
+        m_buffers.removeLast();
 }
 
 void DisplayItems::clear()
 {
+    m_buffers.clear();
     m_items.clear();
 }
 
 void DisplayItems::swap(DisplayItems& other)
 {
+    m_buffers.swap(other.m_buffers);
     m_items.swap(other.m_items);
 }
 
 void DisplayItems::setGone(const Iterator& it)
 {
-    it.m_iterator->clear();
+    *it.m_iterator = nullptr;
+}
+
+DisplayItems::StorageBuffer& DisplayItems::appendStorageBuffer()
+{
+    // Find the first inner vector with space in it.
+    // We don't want to increase capacity of these vectors.
+    auto hasCapacity = [](const OwnPtr<InnerVector>& innerVector) -> bool {
+        return innerVector->size() != innerVector->capacity();
+    };
+    auto it = std::find_if(m_buffers.begin(), m_buffers.end(), hasCapacity);
+
+    // If there's no space, allocate a new inner vector.
+    if (it == m_buffers.end()) {
+        size_t capacity = m_buffers.isEmpty() ? capacityOfFirstInnerVector : 2 * m_buffers.last()->capacity();
+        OwnPtr<InnerVector> innerVector = adoptPtr(new InnerVector);
+        innerVector->reserveInitialCapacity(capacity);
+        m_buffers.append(innerVector.release());
+        it = m_buffers.end() - 1;
+    }
+
+    // Now that we have the inner vector, we can create storage buffer for one
+    // display item.
+    InnerVector& innerVector = **it;
+    innerVector.grow(innerVector.size() + 1);
+    return innerVector.last();
 }
 
 } // namespace blink