cc: Add RandomAccessListContainer, which has more restricted API.

cc/base/list_container.h

 // Copyright 2014 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.
 
 #ifndef CC_BASE_LIST_CONTAINER_H_
 #define CC_BASE_LIST_CONTAINER_H_
 
+#include <deque>
+
 #include "base/logging.h"
 #include "base/macros.h"
 #include "base/memory/scoped_ptr.h"
 #include "cc/base/cc_export.h"
 
 namespace cc {
 
 // ListContainer is a container type that handles allocating contiguous memory
 // for new elements and traversing through elements with either iterator or
 // reverse iterator. Since this container hands out raw pointers of its
 // elements, it is very important that this container never reallocate its
 // memory so those raw pointer will continue to be valid.  This class is used to
 // contain SharedQuadState or DrawQuad. Since the size of each DrawQuad varies,
 // to hold DrawQuads, the allocations size of each element in this class is
 // LargestDrawQuadSize while BaseElementType is DrawQuad.
 
 // Helper class for non-templated logic. All methods are private, and only
 // exposed to friend classes.
 // For usage, see comments in ListContainer.
 class CC_EXPORT ListContainerHelper {
  private:
   template <typename T>
   friend class CC_EXPORT ListContainer;
 
+  template <typename T>
+  friend class CC_EXPORT RandomAccessListContainer;
+
   explicit ListContainerHelper(size_t max_size_for_derived_class);
   ListContainerHelper(size_t max_size_for_derived_class,
                       size_t num_of_elements_to_reserve_for);
   ~ListContainerHelper();
 
   // This class deals only with char* and void*. It does allocation and passing
   // out raw pointers, as well as memory deallocation when being destroyed.
   class ListContainerCharAllocator;
 
   // This class points to a certain position inside memory of
@@ skipping 452 matching lines @@
         ListContainerHelper::ConstReverseIterator base_iterator)
         : ListContainerHelper::ConstReverseIterator(base_iterator) {}
     friend ConstReverseIterator ListContainer<BaseElementType>::crbegin() const;
     friend ConstReverseIterator ListContainer<BaseElementType>::crend() const;
   };
 
  private:
   ListContainerHelper helper_;
 };
 
+template <class BaseElementType>
+class CC_EXPORT RandomAccessListContainer {
+ public:
+  // BaseElementType is the type of raw pointers this class hands out; however,
+  // its derived classes might require different memory sizes.
+  // max_size_for_derived_class the largest memory size required for all the
+  // derived classes to use for allocation.
+  explicit RandomAccessListContainer(size_t max_size_for_derived_class)
+      : helper_(max_size_for_derived_class) {}
+
+  // This constructor omits input variable for max_size_for_derived_class. This
+  // is used when there is no derived classes from BaseElementType we need to
+  // worry about, and allocation size is just sizeof(BaseElementType).
+  RandomAccessListContainer() : helper_(sizeof(BaseElementType)) {}
+
+  // This constructor reserves the requested memory up front so only single
+  // allocation is needed. When num_of_elements_to_reserve_for is zero, use the
+  // default size.
+  RandomAccessListContainer(size_t max_size_for_derived_class,
+                            size_t num_of_elements_to_reserve_for)
+      : helper_(max_size_for_derived_class, num_of_elements_to_reserve_for) {}
+
+  ~RandomAccessListContainer() {
+    for (BaseElementType* item : items_)
+      item->~BaseElementType();
+  }
+
+  void clear() {
+    for (BaseElementType* item : items_)
+      item->~BaseElementType();
+    helper_.clear();
+    items_.clear();
+  }
+
+  bool empty() const { return helper_.empty(); }
+  size_t size() const { return helper_.size(); }
+  size_t GetCapacityInBytes() const { return helper_.GetCapacityInBytes(); }
+
+  template <typename DerivedElementType>
+  DerivedElementType* AllocateAndConstruct() {
+    auto* value =
+        new (helper_.Allocate(sizeof(DerivedElementType))) DerivedElementType;
+    items_.push_back(value);
+    return value;
+  }
+
+  void RemoveLast() {
+    items_.back()->~BaseElementType();
+    items_.pop_back();
+    helper_.RemoveLast();
+  }
+
+  const BaseElementType* operator[](size_t index) const {

[weiliangc, 2015/09/14 20:02:47]

Can you also add at()? Or explain in comment this class doesn't support at?

[vmpstr, 2015/09/15 00:17:48]

I'm not sure why we need at() as well. I assume you mean something similar to
vector::at, which is equivalent to operator[] except it does bounds checking. I
do bounds checking with dchecks in operator[] here. 

+    DCHECK_GE(index, 0u);
+    DCHECK_LT(index, items_.size());
+    return items_[index];
+  }
+
+  using ConstIterator = typename std::deque<BaseElementType*>::const_iterator;

[weiliangc, 2015/09/14 20:02:47]

Seems like only have const access, is this intended? Can you add it to comment?

[vmpstr, 2015/09/15 00:17:48]

Hmm. The const access is to the iterator whose value_type is a BaseElementType*
const, so you technically can still change the value pointed to, you just can't
change the deque directly... That is,

*it = new_ptr; // error
(*it)->base_value = new_base_value; // ok
**it = new_object; // also ok

This is by design, but maybe this mimics more of the non-const ListContainer
iterators?

FWIW, For ListContainers, both const and non-const iterators don't allow *it =
new_ptr;

+  ConstIterator begin() const { return items_.begin(); }
+  ConstIterator end() const { return items_.end(); }
+
+ private:
+  ListContainerHelper helper_;
+  std::deque<BaseElementType*> items_;
+};
+
 }  // namespace cc
 
 #endif  // CC_BASE_LIST_CONTAINER_H_