// 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 "base/compiler_specific.h"
#include "platform/PlatformExport.h"
#include "wtf/Alignment.h"
#include "wtf/Allocator.h"
#include "wtf/Compiler.h"
#include "wtf/Noncopyable.h"
#include "wtf/TypeTraits.h"
#include "wtf/Vector.h"
#include <cstddef>
#include <iterator>
#include <memory>
#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);
  ContiguousContainerBase(ContiguousContainerBase&&);
  ~ContiguousContainerBase();

  ContiguousContainerBase& operator=(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 reserveInitialCapacity(size_t, const char* typeName);
  void* allocate(size_t objectSize, const char* typeName);
  void removeLast();
  void clear();
  void swap(ContiguousContainerBase&);

  // Discards excess buffer capacity. Intended for use when no more appending
  // is anticipated.
  void shrinkToFit();

  Vector<void*> m_elements;

 private:
  class Buffer;

  Buffer* allocateNewBufferForNextAllocation(size_t, const char* typeName);

  Vector<std::unique_ptr<Buffer>> m_buffers;
  unsigned m_endIndex;
  size_t m_maxObjectSize;
};

// 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)) {}

  ContiguousContainer(size_t maxObjectSize, size_t initialSizeBytes)
      : ContiguousContainer(maxObjectSize) {
    reserveInitialCapacity(std::max(maxObjectSize, initialSizeBytes),
                           WTF_HEAP_PROFILER_TYPE_NAME(BaseElementType));
  }

  ContiguousContainer(ContiguousContainer&& source)
      : ContiguousContainerBase(std::move(source)) {}

  ~ContiguousContainer() {
    for (auto& element : *this) {
      (void)element;  // MSVC incorrectly reports this variable as unused.
      element.~BaseElementType();
    }
  }

  ContiguousContainer& operator=(ContiguousContainer&& source) {
    // Must clear in the derived class to ensure that element destructors
    // care called.
    clear();

    ContiguousContainerBase::operator=(std::move(source));
    return *this;
  }

  using ContiguousContainerBase::size;
  using ContiguousContainerBase::isEmpty;
  using ContiguousContainerBase::capacityInBytes;
  using ContiguousContainerBase::usedCapacityInBytes;
  using ContiguousContainerBase::memoryUsageInBytes;
  using ContiguousContainerBase::shrinkToFit;

  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.");
    return *new (alignedAllocate(sizeof(DerivedElementType)))
        DerivedElementType(std::forward<Args>(args)...);
  }

  void removeLast() {
    ASSERT(!isEmpty());
    last().~BaseElementType();
    ContiguousContainerBase::removeLast();
  }

  DISABLE_CFI_PERF
  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 = alignedAllocate(size);
    memcpy(newItem, static_cast<void*>(&item), size);
    new (&item) BaseElementType;
    return *static_cast<BaseElementType*>(newItem);
  }

 private:
  void* alignedAllocate(size_t size) {
    void* result = ContiguousContainerBase::allocate(
        align(size), WTF_HEAP_PROFILER_TYPE_NAME(BaseElementType));
    DCHECK_EQ(reinterpret_cast<intptr_t>(result) & (alignment - 1), 0u);
    return result;
  }

  static size_t align(size_t size) {
    size_t alignedSize = alignment * ((size + alignment - 1) / alignment);
    DCHECK_EQ(alignedSize % alignment, 0u);
    DCHECK_GE(alignedSize, size);
    DCHECK_LT(alignedSize, size + alignment);
    return alignedSize;
  }
};

}  // namespace blink

#endif  // ContiguousContainer_h