text: // 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.
  
  #ifndef ContiguousContainer_h
  #define ContiguousContainer_h
  
  #include "platform/PlatformExport.h"
  #include "wtf/Alignment.h"
  #include "wtf/Allocator.h"
  #include "wtf/Compiler.h"
  #include "wtf/Noncopyable.h"
  #include "wtf/OwnPtr.h"
  #include "wtf/TypeTraits.h"
  #include "wtf/Vector.h"
  #include <cstddef>
  #include <iterator>
  #include <utility>
  
  namespace blink {
  
  // ContiguousContainer is a container which stores a list of heterogeneous
  // objects (in particular, of varying sizes), packed next to one another in
  // memory. Objects are never relocated, so it is safe to store pointers to them
  // for the lifetime of the container (unless the object is removed).
  //
  // Memory is allocated in a series of buffers (with exponential growth). When an
  // object is allocated, it is given only the space it requires (possibly with
  // enough padding to preserve alignment), rather than the maximum possible size.
  // This allows small and large objects to coexist without wasting much space.
  //
  // Since it stores pointers to all of the objects it allocates in a vector, it
  // supports efficient iteration and indexing. However, for mutation the
  // supported operations are limited to appending to, and removing from, the end
  // of the list.
  //
  // Clients should instantiate ContiguousContainer; ContiguousContainerBase is an
  // artifact of the implementation.
  
  class PLATFORM_EXPORT ContiguousContainerBase {
      DISALLOW_NEW();
      WTF_MAKE_NONCOPYABLE(ContiguousContainerBase);
  protected:
      explicit ContiguousContainerBase(size_t maxObjectSize, const char* typeName);
      ContiguousContainerBase(size_t maxObjectSize, size_t initialSizeBytes, const char* typeName);
      ~ContiguousContainerBase();
  
      size_t size() const { return m_elements.size(); }
      bool isEmpty() const { return !size(); }
      size_t capacityInBytes() const;
      size_t usedCapacityInBytes() const;
      size_t memoryUsageInBytes() const;
  
      // These do not invoke constructors or destructors.
      void* allocate(size_t objectSize, const char* typeName);
      void removeLast();
      void clear();
      void swap(ContiguousContainerBase&);
  
      Vector<void*> m_elements;
  
  private:
      class Buffer;
  
      Buffer* allocateNewBufferForNextAllocation(size_t, const char* typeName);
  
      Vector<OwnPtr<Buffer>> m_buffers;
      unsigned m_endIndex;
      size_t m_maxObjectSize;
  
      // Makes Buffer accessible when clearing m_buffers. Fixes MSVC build.
      friend struct WTF::OwnedPtrDeleter<Buffer>;
  };
  
  // For most cases, no alignment stricter than pointer alignment is required. If
  // one of the derived classes has stronger alignment requirements (and the
  // static_assert fires), set alignment to the LCM of the derived class
  // alignments. For small structs without pointers, it may be possible to reduce
  // alignment for tighter packing.
  
  template <class BaseElementType, unsigned alignment = sizeof(void*)>
  class ContiguousContainer : public ContiguousContainerBase {
  private:
      // Declares itself as a forward iterator, but also supports a few more
      // things. The whole random access iterator interface is a bit much.
      template <typename BaseIterator, typename ValueType>
      class IteratorWrapper : public std::iterator<std::forward_iterator_tag, ValueType> {
          DISALLOW_NEW();
      public:
          IteratorWrapper() {}
          bool operator==(const IteratorWrapper& other) const { return m_it == other.m_it; }
          bool operator!=(const IteratorWrapper& other) const { return m_it != other.m_it; }
          ValueType& operator*() const { return *static_cast<ValueType*>(*m_it); }
          ValueType* operator->() const { return &operator*(); }
          IteratorWrapper operator+(std::ptrdiff_t n) const { return IteratorWrapper(m_it + n); }
          IteratorWrapper operator++(int) { IteratorWrapper tmp = *this; ++m_it; return tmp; }
          std::ptrdiff_t operator-(const IteratorWrapper& other) const { return m_it - other.m_it; }
          IteratorWrapper& operator++() { ++m_it; return *this; }
      private:
          explicit IteratorWrapper(const BaseIterator& it) : m_it(it) {}
          BaseIterator m_it;
          friend class ContiguousContainer;
      };
  
  public:
      using iterator = IteratorWrapper<Vector<void*>::iterator, BaseElementType>;
      using const_iterator = IteratorWrapper<Vector<void*>::const_iterator, const BaseElementType>;
      using reverse_iterator = IteratorWrapper<Vector<void*>::reverse_iterator, BaseElementType>;
      using const_reverse_iterator = IteratorWrapper<Vector<void*>::const_reverse_iterator, const BaseElementType>;
  
      explicit ContiguousContainer(size_t maxObjectSize)
          : ContiguousContainerBase(align(maxObjectSize), WTF_HEAP_PROFILER_TYPE_NAME(BaseElementType)) {}
      ContiguousContainer(size_t maxObjectSize, size_t initialSizeBytes)
          : ContiguousContainerBase(align(maxObjectSize), initialSizeBytes, WTF_HEAP_PROFILER_TYPE_NAME(BaseElementType)) {}
  
      ~ContiguousContainer()
      {
          for (auto& element : *this) {
              (void)element; // MSVC incorrectly reports this variable as unused.
              element.~BaseElementType();
          }
      }
  
      using ContiguousContainerBase::size;
      using ContiguousContainerBase::isEmpty;
      using ContiguousContainerBase::capacityInBytes;
      using ContiguousContainerBase::usedCapacityInBytes;
      using ContiguousContainerBase::memoryUsageInBytes;
  
      iterator begin() { return iterator(m_elements.begin()); }
      iterator end() { return iterator(m_elements.end()); }
      const_iterator begin() const { return const_iterator(m_elements.begin()); }
      const_iterator end() const { return const_iterator(m_elements.end()); }
      reverse_iterator rbegin() { return reverse_iterator(m_elements.rbegin()); }
      reverse_iterator rend() { return reverse_iterator(m_elements.rend()); }
      const_reverse_iterator rbegin() const { return const_reverse_iterator(m_elements.rbegin()); }
      const_reverse_iterator rend() const { return const_reverse_iterator(m_elements.rend()); }
  
      BaseElementType& first() { return *begin(); }
      const BaseElementType& first() const { return *begin(); }
      BaseElementType& last() { return *rbegin(); }
      const BaseElementType& last() const { return *rbegin(); }
      BaseElementType& operator[](size_t index) { return *(begin() + index); }
      const BaseElementType& operator[](size_t index) const { return *(begin() + index); }
  
      template <class DerivedElementType, typename... Args>
      DerivedElementType& allocateAndConstruct(Args&&... args)
      {
          static_assert(WTF::IsSubclass<DerivedElementType, BaseElementType>::value,
              "Must use subclass of BaseElementType.");
          static_assert(alignment % WTF_ALIGN_OF(DerivedElementType) == 0,
              "Derived type requires stronger alignment.");
          size_t allocSize = align(sizeof(DerivedElementType));
          return *new (allocate(allocSize, WTF_HEAP_PROFILER_TYPE_NAME(DerivedElementType))) DerivedElementType(std::forward<Args>(args)...);
      }
  
      void removeLast()
      {
          ASSERT(!isEmpty());
          last().~BaseElementType();
          ContiguousContainerBase::removeLast();
      }
  
      void clear()
      {
          for (auto& element : *this) {
              (void)element; // MSVC incorrectly reports this variable as unused.
              element.~BaseElementType();
          }
          ContiguousContainerBase::clear();
      }
  
      void swap(ContiguousContainer& other) { ContiguousContainerBase::swap(other); }
  
      // Appends a new element using memcpy, then default-constructs a base
      // element in its place. Use with care.
      BaseElementType& appendByMoving(BaseElementType& item, size_t size)
      {
          ASSERT(size >= sizeof(BaseElementType));
          void* newItem = allocate(size, WTF_HEAP_PROFILER_TYPE_NAME(BaseElementType));
          memcpy(newItem, static_cast<void*>(&item), size);
          new (&item) BaseElementType;
          return *static_cast<BaseElementType*>(newItem);
      }
  
  private:
      static size_t align(size_t size)
      {
          size_t alignedSize = alignment * ((size + alignment - 1) / alignment);
          ASSERT(alignedSize % alignment == 0);
          ASSERT(alignedSize >= size);
          ASSERT(alignedSize < size + alignment);
          return alignedSize;
      }
  };
  
  } // namespace blink
  
  #endif // ContiguousContainer_h
  