template <class It>
struct range_based_for_pair : public std::pair<It, It>{
using std::pair<It, It>::pair;
It &begin() {
return std::pair<It, It>::first;
}
It &end() {
return std::pair<It, It>::second;
}
};
template<typename _Tp, size_t chunk_size>
class chunked_vector {
public:
using underlying = std::vector<bastion::span<_Tp>>;
using chunk_iterator = typename underlying::const_iterator;
template<typename T>
class iterator_base {
public:
using iterator_category = std::random_access_iterator_tag ;
using value_type = T;
using difference_type = std::ptrdiff_t;
using pointer = T *;
using reference = T &;
iterator_base() noexcept {}
~iterator_base() = default;
iterator_base(chunk_iterator const &ref, ptrdiff_t offset = 0) {
*this = ref;
operator+=(offset);
}
iterator_base(iterator_base &&rhs) noexcept {
operator=(std::move(rhs));
}
iterator_base(iterator_base const &rhs) noexcept {
operator=(rhs);
}
iterator_base &operator=(chunk_iterator const &rhs) noexcept {
offset_ = 0;
chunk_ = rhs;
return *this;
}
iterator_base &operator=(chunk_iterator &&rhs) noexcept {
offset_ = 0;
chunk_ = std::move(rhs);
return *this;
}
iterator_base &operator=(iterator_base &&rhs) noexcept {
offset_ = rhs.offset_;
chunk_ = std::move(rhs.chunk_);
return *this;
}
iterator_base &operator=(iterator_base const &rhs) noexcept {
offset_ = rhs.offset_;
chunk_ = std::move(rhs.chunk_);
return *this;
}
reference operator*() {
return (*chunk_)[offset_];
}
reference operator[](std::ptrdiff_t at) {
auto offset_in_chunks = at / chunk_size;
offset_ = at - offset_in_chunks * chunk_size;
return chunk_[offset_in_chunks][offset_];
}
iterator_base &operator++() noexcept {
++offset_;
if (offset_ == chunk_size) {
offset_ = 0;
++chunk_;
}
return *this;
}
iterator_base operator++(int) noexcept {
iterator_base copy { *this };
operator++();
return copy;
}
iterator_base &operator--() noexcept {
if (offset_ == 0) {
offset_ = chunk_size - 1;
--chunk_;
return *this;
}
--offset_;
return *this;
}
iterator_base operator--(int) noexcept {
iterator_base copy { *this };
operator--();
return copy;
}
inline iterator_base &operator+=(ptrdiff_t rhs) noexcept {
if (rhs < 0) {
return operator-=( -rhs );
}
size_t diff = offset_ + static_cast<size_t>(rhs);
ptrdiff_t offset_in_chunks = diff / chunk_size;
chunk_ += offset_in_chunks;
offset_ = diff - static_cast<size_t>(offset_in_chunks) * chunk_size;
return *this;
}
inline iterator_base &operator-=(ptrdiff_t srhs) noexcept {
if (srhs < 0) {
return operator+=( -srhs );
}
auto rhs = static_cast<size_t>(srhs);
if (offset_ >= rhs) {
offset_ -= rhs;
return *this;
}
size_t diff = rhs - offset_;
ptrdiff_t offset_in_chunks = (diff + chunk_size - 1) / chunk_size;
chunk_ -= offset_in_chunks;
offset_ = chunk_size - (diff % chunk_size);
return *this;
}
bool operator==(iterator_base const &rhs) const noexcept {
return chunk_ == rhs.chunk_ && offset_ == rhs.offset_;
}
bool operator!=(iterator_base const &rhs) const noexcept {
if (chunk_ != rhs.chunk_) {
return true;
}
return offset_ != rhs.offset_;
}
bool operator<(iterator_base const &rhs) const noexcept {
if (chunk_ == rhs.chunk_) {
return offset_ < rhs.offset_;
}
return chunk_ < rhs.chunk_;
}
bool operator>(iterator_base const &rhs) const noexcept {
if (chunk_ == rhs.chunk_) {
return offset_ > rhs.offset_;
}
return chunk_ > rhs.chunk_;
}
bool operator>=(iterator_base const &rhs) const noexcept {
if (chunk_ == rhs.chunk_) {
return offset_ >= rhs.offset_;
}
return chunk_ >= rhs.chunk_;
}
bool operator<=(iterator_base const &rhs) const noexcept{
if (chunk_ == rhs.chunk_) {
return offset_ <= rhs.offset_;
}
return chunk_ <= rhs.chunk_;
}
friend iterator_base operator+(iterator_base const &lhs, ptrdiff_t rhs) noexcept {
iterator_base it = lhs;
it += rhs;
return it;
}
friend iterator_base operator-(iterator_base const &lhs, ptrdiff_t rhs) noexcept {
iterator_base it = lhs;
it -= rhs;
return it;
}
friend ptrdiff_t operator-(iterator_base const &lhs, iterator_base const &rhs) noexcept {
return (lhs.chunk_ - rhs.chunk_) * chunk_size + (lhs.offset_ - rhs.offset_);
}
private:
friend class basic_chunked_byte_vector;
size_t offset_ = 0;
chunk_iterator chunk_;
};
using value_type = _Tp;
using pointer = value_type *;
using const_pointer = value_type const *;
using reference = value_type &;
using const_reference = value_type const&;
using size_type = size_t;
using difference_type = ptrdiff_t;
using iterator = iterator_base<value_type>;
using const_iterator = iterator_base<value_type const>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;
using reverse_iterator = std::reverse_iterator<iterator>;
chunked_vector() = default;
chunked_vector(size_type count, const value_type& value) {
resize(count, value);
}
chunked_vector(std::initializer_list<value_type> il) {
assign(il);
}
template <class InputIterator>
chunked_vector(InputIterator first, InputIterator last) {
assign(first, last);
}
template <class Container>
chunked_vector &operator=(Container c) {
assign(c.begin(), c.end());
return *this;
}
chunked_vector &operator=(std::initializer_list<value_type> il) {
assign(il);
return *this;
}
~chunked_vector() {
clear();
shrink_to_fit();
}
void reserve(size_t n) {
if (n <= capacity_) {
return;
}
size_t allocation_count = (n + chunk_size - 1) / chunk_size;
size_t old_capacity = capacity_in_chunks_;
underlying_.resize(allocation_count);
// if exception is thrown, container will be shrunk to current allocated memory size
// that memory will not leak and can be used, for example in push_back operations.
try {
for (size_t it = old_capacity; it < underlying_.size(); ++it) {
auto storage = new (std::align_val_t{ alignof (value_type) }) std::byte[sizeof(value_type) * chunk_size];
bastion::span<value_type> page( reinterpret_cast<pointer>(storage), size_t{0} );
underlying_[it] = page;
// register new page. If exception was thrown, container left in valid state and all memory will be free/reused on dealocation
capacity_ += chunk_size;
++capacity_in_chunks_;
}
} catch (...) {
underlying_.resize(capacity_in_chunks_);
throw;
}
}
template <class InputIterator>
void assign (InputIterator first, InputIterator last) {
if (!empty()) {
clear();
}
size_t const n = last - first;
size_t chunks = (n + chunk_size - 1) / chunk_size;
reserve(n);
size_t current = 0;
size_t left = n;
try {
for (; current < chunks; ++current) {
size_t to_copy = std::min(left, chunk_size);
auto view = underlying_[current];
std::uninitialized_copy_n(first, to_copy, view.data());
underlying_[current] = bastion::span<value_type>(view.data(), to_copy);
first += to_copy;
left -= to_copy;
}
size_ = n;
size_in_chunks_ = chunks;
assert(first == last);
assert(left == 0);
} catch (...) {
_resize_down(0, current);
throw;
}
}
void assign (std::initializer_list<value_type> il) {
if (!empty()) {
clear();
}
size_t const n = il.size();
size_t chunks = (n + chunk_size - 1) / chunk_size;
reserve(n);
size_t current = 0;
size_t left = n;
auto first = il.begin();
auto last = il.end();
try {
for (; current < chunks; ++current) {
size_t to_copy = std::min(left, chunk_size);
auto view = underlying_[current];
if constexpr (std::is_move_constructible_v<value_type>
|| std::is_move_assignable_v<value_type>) {
std::uninitialized_move_n(first, to_copy, view.data());
} else {
std::uninitialized_copy_n(first, to_copy, view.data());
}
underlying_[current] = bastion::span<value_type>(view.data(), to_copy);
first += to_copy;
left -= to_copy;
}
size_ = il.size();
size_in_chunks_ = chunks;
assert(first == last);
assert(left == 0);
} catch (...) {
_resize_down(0, current);
throw;
}
}
void push_back(value_type &&v) {
// allocates memory
reserve(size_ + 1);
// constructs new item
_emplace_back_impl(std::move(v));
}
void push_back(value_type const &v) {
// allocates memory
reserve(size_ + 1);
// constructs new item
_emplace_back_impl(v);
}
template<typename ...Args>
inline void emplace_back(Args && ...args) {
// allocates memory
reserve(size_ + 1);
// constructs new item
_emplace_back_impl(std::forward<Args...>(args...));
}
void resize(size_t n) {
value_type tmp{};
resize(n, tmp);
}
void resize(size_t n, const value_type& val) {
if (n == size_) {
return;
}
// 3 cases:
assert(size_ <= capacity_);
if (n < size_) {
_resize_down(n, size_in_chunks());
return;
}
assert (n > size_);
reserve(n);
size_t new_size_in_chunks = (n + chunk_size - 1) / chunk_size;
size_t count = n;
size_t current = _back_chunk_idx();
if (underlying_[current].size() == chunk_size) {
++current;
}
try {
while (count > 0) {
auto view = underlying_[current];
size_t fill = std::min(chunk_size - view.size(), count);
std::uninitialized_fill_n(view.data() + view.size(), fill, val);
underlying_[current] = bastion::span<value_type>(view.data(), view.size() + fill);
count -= fill;
++current;
}
size_ = n;
size_in_chunks_ = new_size_in_chunks;
} catch (...) {
_resize_down(size_, current);
throw;
}
assert(size_ == n);
assert(size_in_chunks() == new_size_in_chunks);
}
size_t size() const {
return size_;
}
size_t capacity() const {
return capacity_;
}
size_t size_in_chunks() const {
assert(((size_ + chunk_size - 1) / chunk_size) == size_in_chunks_);
return size_in_chunks_;
}
size_t capacity_in_chunks() const {
return capacity_in_chunks_;
}
void shrink_to_fit() {
for (size_t it = size_in_chunks(); it < capacity_in_chunks_; ++it) {
operator delete [] (underlying_[it].data(), std::align_val_t{ alignof (value_type) });
}
underlying_.resize(size_in_chunks()); // nothrow
underlying_.shrink_to_fit(); // nothrow
capacity_in_chunks_ = size_in_chunks();
size_in_chunks_ = capacity_in_chunks_;
capacity_ = capacity_in_chunks_ * chunk_size; // round up to chunk_size
}
value_type const &operator[](size_t at) const {
assert(at < size());
size_t chunk_at = at / chunk_size;
assert(chunk_at < size_in_chunks());
size_t offset_in = at - chunk_at * chunk_size;
assert(offset_in < chunk_size);
return underlying_[at / chunk_size][offset_in];
}
value_type &operator[](size_t at) {
return const_cast<value_type &>(operator[](at));
}
bastion::span<value_type const> chunk(size_t at) const {
assert(at < size_in_chunks());
return underlying_[at];
}
bastion::span<value_type> chunk(size_t at) {
assert(at < size_in_chunks());
return underlying_[at];
}
bool empty() const {
return size_ == 0;
}
void clear() {
_resize_down(0, size_in_chunks());
size_ = 0;
size_in_chunks_ = 0;
}
range_based_for_pair<chunk_iterator>
chunks() const {
return {chunks_begin(), chunks_end()};
}
chunk_iterator chunks_begin() const {
return underlying_.cbegin();
}
chunk_iterator chunks_end() const {
return underlying_.cbegin() + size_in_chunks();
}
iterator begin() {
return chunks_begin();
}
const_iterator cbegin() const {
return chunks_begin();
}
iterator end() {
// back chunk + offset on its size
return { chunks_begin() + std::ptrdiff_t(_back_chunk_idx()), std::ptrdiff_t(underlying_[_back_chunk_idx()].size()) };
}
const_iterator cend() const {
// back chunk + offset on its size
return { chunks_begin() + std::ptrdiff_t(_back_chunk_idx()), std::ptrdiff_t(underlying_[_back_chunk_idx()].size()) };
}
reverse_iterator rbegin() { return reverse_iterator{end()}; }
const_reverse_iterator crbegin() const { return const_reverse_iterator{ cend() }; }
reverse_iterator rend() { return reverse_iterator{begin()}; }
const_reverse_iterator crend() const { return const_reverse_iterator{ cbegin()}; }
template<typename ...Args>
inline void _emplace_back_impl(Args && ...args) {
auto old_size_in_chunks_ = size_in_chunks_;
try {
if (size_ == 0 || underlying_[_back_chunk_idx()].size() == chunk_size) {
++size_in_chunks_;
}
size_t back_chunk = size_in_chunks_ - 1;
auto extended_span = underlying_[back_chunk];
extended_span = bastion::span<value_type>(extended_span.data(), extended_span.size() + 1);
new (&extended_span[extended_span.size() - 1]) value_type(std::forward<Args...>(args...)); // may throw...
// registers it
underlying_[back_chunk] = extended_span;
++size_;
} catch (...) {
size_in_chunks_ = old_size_in_chunks_;
throw;
}
}
void _resize_down(size_t dest_size, size_t old_size_in_chunks) {
size_t new_size_in_chunks = (dest_size + chunk_size - 1) / chunk_size;
size_t back_chunk_size = dest_size - (new_size_in_chunks - 1) * chunk_size;
// in case of dest_size == 0 all chunks will be processed inside other loop.
if (dest_size != 0) {
// examines separately chunk that is going to be last after resize
// destroys excess elements
assert(new_size_in_chunks > 0);
size_t back = new_size_in_chunks - 1;
auto view = underlying_[back];
if constexpr (!std::is_trivially_destructible_v<value_type>) {
std::destroy_n(view.data() + back_chunk_size, view.size() - back_chunk_size);
}
underlying_[back] = bastion::span<value_type>(view.data(), back_chunk_size);
}
// others chunks
// destroys all elements in them
for (size_t it = new_size_in_chunks; it < old_size_in_chunks; ++it) {
auto view = underlying_[it];
if constexpr (!std::is_trivially_destructible_v<value_type>) {
std::destroy_n(view.data(), view.size());
}
underlying_[it] = bastion::span<value_type>(view.data(), size_t{0});
}
size_in_chunks_ = new_size_in_chunks;
size_ = dest_size;
}
inline size_t _back_chunk_idx() const {
return (size_in_chunks_ > 0)? size_in_chunks_ - 1 : 0;
}
private:
underlying underlying_;
size_t size_ = 0;
size_t size_in_chunks_ = 0;
size_t capacity_ = 0;
size_t capacity_in_chunks_ = 0;
};