chromium/v8/src/base/small-vector.h

// Copyright 2018 the V8 project 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 V8_BASE_SMALL_VECTOR_H_
#define V8_BASE_SMALL_VECTOR_H_

#include <algorithm>
#include <type_traits>
#include <utility>

#include "src/base/bits.h"
#include "src/base/macros.h"
#include "src/base/vector.h"

namespace v8 {
namespace base {

// Minimal SmallVector implementation. Uses inline storage first, switches to
// dynamic storage when it overflows.
template <typename T, size_t kSize, typename Allocator = std::allocator<T>>
class SmallVector {
  // Currently only support trivially copyable and trivially destructible data
  // types, as it uses memcpy to copy elements and never calls destructors.
  ASSERT_TRIVIALLY_COPYABLE(T);
  static_assert(std::is_trivially_destructible<T>::value);

 public:
  static constexpr size_t kInlineSize = kSize;
  using value_type = T;

  SmallVector() = default;
  explicit SmallVector(const Allocator& allocator) : … { … }
  explicit V8_INLINE SmallVector(size_t size,
                                 const Allocator& allocator = Allocator())
      : … { … }
  SmallVector(const SmallVector& other) V8_NOEXCEPT
      : … { … }
  SmallVector(const SmallVector& other, const Allocator& allocator) V8_NOEXCEPT
      : … { … }
  SmallVector(SmallVector&& other) V8_NOEXCEPT
      : … { … }
  SmallVector(SmallVector&& other, const Allocator& allocator) V8_NOEXCEPT
      : … { … }
  V8_INLINE SmallVector(std::initializer_list<T> init,
                        const Allocator& allocator = Allocator())
      : … { … }
  explicit V8_INLINE SmallVector(base::Vector<const T> init,
                                 const Allocator& allocator = Allocator())
      : … { … }

  ~SmallVector() { … }

  SmallVector& operator=(const SmallVector& other) V8_NOEXCEPT { … }

  SmallVector& operator=(SmallVector&& other) V8_NOEXCEPT { … }

  T* data() { … }
  const T* data() const { … }

  T* begin() { … }
  const T* begin() const { … }

  T* end() { … }
  const T* end() const { … }

  auto rbegin() { … }
  auto rbegin() const { … }

  auto rend() { … }
  auto rend() const { … }

  size_t size() const { … }
  bool empty() const { … }
  size_t capacity() const { … }

  T& front() { … }
  const T& front() const { … }

  T& back() { … }
  const T& back() const { … }

  T& operator[](size_t index) { … }

  const T& at(size_t index) const { … }

  const T& operator[](size_t index) const { … }

  template <typename... Args>
  void emplace_back(Args&&... args) { … }

  void push_back(T x) { … }

  void pop_back(size_t count = 1) { … }

  T* insert(T* pos, const T& value) { … }
  T* insert(T* pos, size_t count, const T& value) { … }
  template <typename It>
  T* insert(T* pos, It begin, It end) { … }

  T* insert(T* pos, std::initializer_list<T> values) { … }

  void resize_no_init(size_t new_size) { … }

  void resize_and_init(size_t new_size, const T& initial_value = { … }

  void reserve(size_t new_capacity) { … }

  // Clear without reverting back to inline storage.
  void clear() { … }

  Allocator get_allocator() const { … }

 private:
  // Grows the backing store by a factor of two. Returns the new end of the used
  // storage (this reduces binary size).
  V8_NOINLINE V8_PRESERVE_MOST void Grow() { … }

  // Grows the backing store by a factor of two, and at least to {min_capacity}.
  V8_NOINLINE V8_PRESERVE_MOST void Grow(size_t min_capacity) { … }

  T* AllocateDynamicStorage(size_t number_of_elements) { … }

  V8_NOINLINE V8_PRESERVE_MOST void FreeDynamicStorage() { … }

  // Clear and go back to inline storage. Dynamic storage is *not* freed. For
  // internal use only.
  void reset_to_inline_storage() { … }

  bool is_big() const { … }

  T* inline_storage_begin() { … }
  const T* inline_storage_begin() const { … }

  V8_NO_UNIQUE_ADDRESS Allocator allocator_;

  T* begin_ = inline_storage_begin();
  T* end_ = begin_;
  T* end_of_storage_ = begin_ + kInlineSize;
  typename std::aligned_storage<sizeof(T) * kInlineSize, alignof(T)>::type
      inline_storage_;
};

}  // namespace base
}  // namespace v8

#endif  // V8_BASE_SMALL_VECTOR_H_