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

public:

static constexpr size_t kInlineSize = kSize;

using value_type = T;

SmallVector() = default;

explicit SmallVector(const Allocator& allocator) : allocator_(allocator) {}

explicit V8_INLINE SmallVector(size_t size,

const Allocator& allocator = Allocator())

: allocator_(allocator) {

resize(size);

}

explicit V8_INLINE SmallVector(size_t size, const T& initial_value,

const Allocator& allocator = Allocator())

: allocator_(allocator) {

resize(size, initial_value);

}

SmallVector(const SmallVector& other) V8_NOEXCEPT

: allocator_(other.allocator_) {

*this = other;

}

SmallVector(const SmallVector& other, const Allocator& allocator) V8_NOEXCEPT

: allocator_(allocator) {

*this = other;

}

SmallVector(SmallVector&& other) V8_NOEXCEPT

: allocator_(std::move(other.allocator_)) {

*this = std::move(other);

}

SmallVector(SmallVector&& other, const Allocator& allocator) V8_NOEXCEPT

: allocator_(allocator) {

*this = std::move(other);

}

V8_INLINE SmallVector(std::initializer_list<T> init,

const Allocator& allocator = Allocator())

: allocator_(allocator) {

if (init.size() > capacity()) Grow(init.size());

DCHECK_GE(capacity(), init.size()); // Sanity check.

std::uninitialized_move(init.begin(), init.end(), begin_);

end_ = begin_ + init.size();

}

explicit V8_INLINE SmallVector(base::Vector<const T> init,

const Allocator& allocator = Allocator())

: allocator_(allocator) {

if (init.size() > capacity()) Grow(init.size());

DCHECK_GE(capacity(), init.size()); // Sanity check.

std::uninitialized_copy(init.begin(), init.end(), begin_);

end_ = begin_ + init.size();

}

~SmallVector() { FreeStorage(); }

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

if (this == &other) return *this;

size_t other_size = other.size();

if (capacity() < other_size) {

// Create large-enough heap-allocated storage.

FreeStorage();

begin_ = AllocateDynamicStorage(other_size);

end_of_storage_ = begin_ + other_size;

std::uninitialized_copy(other.begin_, other.end_, begin_);

} else if constexpr (kHasTrivialElement) {

std::copy(other.begin_, other.end_, begin_);

} else {

ptrdiff_t to_copy =

std::min(static_cast<ptrdiff_t>(other_size), end_ - begin_);

std::copy(other.begin_, other.begin_ + to_copy, begin_);

if (other.begin_ + to_copy < other.end_) {

std::uninitialized_copy(other.begin_ + to_copy, other.end_,

begin_ + to_copy);

} else {

std::destroy_n(begin_ + to_copy, size() - to_copy);

}

}

end_ = begin_ + other_size;

return *this;

}

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

if (this == &other) return *this;

if (other.is_big()) {

FreeStorage();

begin_ = other.begin_;

end_ = other.end_;

end_of_storage_ = other.end_of_storage_;

} else {

DCHECK_GE(capacity(), other.size()); // Sanity check.

size_t other_size = other.size();

if constexpr (kHasTrivialElement) {

std::move(other.begin_, other.end_, begin_);

} else {

ptrdiff_t to_move =

std::min(static_cast<ptrdiff_t>(other_size), end_ - begin_);

std::move(other.begin_, other.begin_ + to_move, begin_);

if (other.begin_ + to_move < other.end_) {

std::uninitialized_move(other.begin_ + to_move, other.end_,

begin_ + to_move);

} else {

std::destroy_n(begin_ + to_move, size() - to_move);

}

}

end_ = begin_ + other_size;

}

other.reset_to_inline_storage();

return *this;

}

T* data() { return begin_; }

const T* data() const { return begin_; }

T* begin() { return begin_; }

const T* begin() const { return begin_; }

T* end() { return end_; }

const T* end() const { return end_; }

auto rbegin() { return std::make_reverse_iterator(end_); }

auto rbegin() const { return std::make_reverse_iterator(end_); }

auto rend() { return std::make_reverse_iterator(begin_); }

auto rend() const { return std::make_reverse_iterator(begin_); }

size_t size() const { return end_ - begin_; }

bool empty() const { return end_ == begin_; }

size_t capacity() const { return end_of_storage_ - begin_; }

T& front() {

DCHECK_NE(0, size());

return begin_[0];

}

const T& front() const {

DCHECK_NE(0, size());

return begin_[0];

}

T& back() {

DCHECK_NE(0, size());

return end_[-1];

}

const T& back() const {

DCHECK_NE(0, size());

return end_[-1];

}

T& at(size_t index) {

DCHECK_GT(size(), index);

return begin_[index];

}

T& operator[](size_t index) {

DCHECK_GT(size(), index);

return begin_[index];

}

const T& at(size_t index) const {

DCHECK_GT(size(), index);

return begin_[index];

}

const T& operator[](size_t index) const { return at(index); }

template <typename... Args>

void emplace_back(Args&&... args) {

if (V8_UNLIKELY(end_ == end_of_storage_)) Grow();

void* storage = end_;

end_ += 1;

new (storage) T(std::forward<Args>(args)...);

}

void push_back(T x) { emplace_back(std::move(x)); }

void pop_back(size_t count = 1) {

DCHECK_GE(size(), count);

end_ -= count;

std::destroy_n(end_, count);

}

T* insert(T* pos, const T& value) {

return insert(pos, static_cast<size_t>(1), value);

}

T* insert(T* pos, size_t count, const T& value) {

DCHECK_LE(pos, end_);

size_t offset = pos - begin_;

size_t old_size = size();

resize(old_size + count);

pos = begin_ + offset;

T* old_end = begin_ + old_size;

DCHECK_LE(old_end, end_);

std::move_backward(pos, old_end, end_);

std::fill_n(pos, count, value);

return pos;

}

template <typename It>

T* insert(T* pos, It begin, It end) {

DCHECK_LE(pos, end_);

size_t offset = pos - begin_;

size_t count = std::distance(begin, end);

size_t old_size = size();

resize(old_size + count);

pos = begin_ + offset;

T* old_end = begin_ + old_size;

DCHECK_LE(old_end, end_);

std::move_backward(pos, old_end, end_);

std::copy(begin, end, pos);

return pos;

}

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

return insert(pos, values.begin(), values.end());

}

void erase(T* erase_start) {

DCHECK_GE(erase_start, begin_);

DCHECK_LE(erase_start, end_);

ptrdiff_t count = end_ - erase_start;

end_ = erase_start;

std::destroy_n(end_, count);

}

void resize(size_t new_size) {

if (new_size > capacity()) Grow(new_size);

T* new_end = begin_ + new_size;

if constexpr (!kHasTrivialElement) {

if (new_end > end_) {

std::uninitialized_default_construct(end_, new_end);

} else {

std::destroy_n(new_end, end_ - new_end);

}

}

end_ = new_end;

}

void resize(size_t new_size, const T& initial_value) {

if (new_size > capacity()) Grow(new_size);

T* new_end = begin_ + new_size;

if (new_end > end_) {

std::uninitialized_fill(end_, new_end, initial_value);

} else {

std::destroy_n(new_end, end_ - new_end);

}

end_ = new_end;

}

void reserve(size_t new_capacity) {

if (new_capacity > capacity()) Grow(new_capacity);

}

// Clear without reverting back to inline storage.

void clear() {

std::destroy_n(begin_, end_ - begin_);

end_ = begin_;

}

Allocator get_allocator() const { return allocator_; }

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() { Grow(0); }

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

size_t in_use = end_ - begin_;

size_t new_capacity =

base::bits::RoundUpToPowerOfTwo(std::max(min_capacity, 2 * capacity()));

T* new_storage = AllocateDynamicStorage(new_capacity);

if (new_storage == nullptr) {

FatalOOM(OOMType::kProcess, "base::SmallVector::Grow");

}

std::uninitialized_move(begin_, end_, new_storage);

FreeStorage();

begin_ = new_storage;

end_ = new_storage + in_use;

end_of_storage_ = new_storage + new_capacity;

}

T* AllocateDynamicStorage(size_t number_of_elements) {

return allocator_.allocate(number_of_elements);

}

V8_NOINLINE V8_PRESERVE_MOST void FreeStorage() {

std::destroy_n(begin_, end_ - begin_);

if (is_big()) allocator_.deallocate(begin_, end_of_storage_ - begin_);

}

// Clear and go back to inline storage. Dynamic storage is *not* freed. For

// internal use only.

void reset_to_inline_storage() {

if constexpr (!kHasTrivialElement) {

if (!is_big()) std::destroy_n(begin_, end_ - begin_);

}

begin_ = inline_storage_begin();

end_ = begin_;

end_of_storage_ = begin_ + kInlineSize;

}

bool is_big() const { return begin_ != inline_storage_begin(); }

T* inline_storage_begin() { return reinterpret_cast<T*>(inline_storage_); }

const T* inline_storage_begin() const {

return reinterpret_cast<const T*>(inline_storage_);

}

V8_NO_UNIQUE_ADDRESS Allocator allocator_;

// Invariants:

// 1. The elements in the range between `begin_` (included) and `end_` (not

// included) will be initialized at all times.

// 2. All other elements outside the range, both in the inline storage and in

// the dynamic storage (if it exists), will be uninitialized at all times.

T* begin_ = inline_storage_begin();

T* end_ = begin_;

T* end_of_storage_ = begin_ + kInlineSize;

alignas(T) char inline_storage_[sizeof(T) * kInlineSize];

static constexpr bool kHasTrivialElement =

is_trivially_copyable<T>::value && is_trivially_destructible<T>::value;

};

} // namespace base

} // namespace v8

#endif // V8_BASE_SMALL_VECTOR_H_