BLI_vector.hh

Go to the documentation of this file.

/*
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 */
 
#pragma once
 
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <memory>
 
#include "BLI_allocator.hh"
#include "BLI_index_range.hh"
#include "BLI_listbase_wrapper.hh"
#include "BLI_math_base.h"
#include "BLI_memory_utils.hh"
#include "BLI_span.hh"
#include "BLI_string.h"
#include "BLI_string_ref.hh"
#include "BLI_utildefines.h"
 
#include "MEM_guardedalloc.h"
 
namespace blender {
 
template<
    typename T,
    int64_t InlineBufferCapacity = default_inline_buffer_capacity(sizeof(T)),
    typename Allocator = GuardedAllocator>
class Vector {
 public:
  using value_type = T;
  using pointer = T *;
  using const_pointer = const T *;
  using reference = T &;
  using const_reference = const T &;
  using iterator = T *;
  using const_iterator = const T *;
  using size_type = int64_t;
 
 private:
  T *begin_;
  T *end_;
  T *capacity_end_;
 
  Allocator allocator_;
 
  TypedBuffer<T, InlineBufferCapacity> inline_buffer_;
 
#ifndef NDEBUG
  int64_t debug_size_;
#  define UPDATE_VECTOR_SIZE(ptr) \
    (ptr)->debug_size_ = static_cast<int64_t>((ptr)->end_ - (ptr)->begin_)
#else
#  define UPDATE_VECTOR_SIZE(ptr) ((void)0)
#endif
 
  template<typename OtherT, int64_t OtherInlineBufferCapacity, typename OtherAllocator>
  friend class Vector;
 
 public:
  Vector(Allocator allocator = {}) noexcept : allocator_(allocator)
  {
    begin_ = inline_buffer_;
    end_ = begin_;
    capacity_end_ = begin_ + InlineBufferCapacity;
    UPDATE_VECTOR_SIZE(this);
  }
 
  Vector(NoExceptConstructor, Allocator allocator = {}) noexcept : Vector(allocator)
  {
  }
 
  explicit Vector(int64_t size, Allocator allocator = {})
      : Vector(NoExceptConstructor(), allocator)
  {
    this->resize(size);
  }
 
  Vector(int64_t size, const T &value, Allocator allocator = {})
      : Vector(NoExceptConstructor(), allocator)
  {
    this->resize(size, value);
  }
 
  template<typename U, typename std::enable_if_t<std::is_convertible_v<U, T>> * = nullptr>
  Vector(Span<U> values, Allocator allocator = {}) : Vector(NoExceptConstructor(), allocator)
  {
    const int64_t size = values.size();
    this->reserve(size);
    uninitialized_convert_n<U, T>(values.data(), size, begin_);
    this->increase_size_by_unchecked(size);
  }
 
  template<typename U, typename std::enable_if_t<std::is_convertible_v<U, T>> * = nullptr>
  Vector(const std::initializer_list<U> &values) : Vector(Span<U>(values))
  {
  }
 
  Vector(const std::initializer_list<T> &values) : Vector(Span<T>(values))
  {
  }
 
  template<typename U,
           size_t N,
           typename std::enable_if_t<std::is_convertible_v<U, T>> * = nullptr>
  Vector(const std::array<U, N> &values) : Vector(Span(values))
  {
  }
 
  template<typename InputIt,
           /* This constructor should not be called with e.g. Vector(3, 10), because that is
            * expected to produce the vector (10, 10, 10). */
           typename std::enable_if_t<!std::is_convertible_v<InputIt, int>> * = nullptr>
  Vector(InputIt first, InputIt last, Allocator allocator = {})
      : Vector(NoExceptConstructor(), allocator)
  {
    for (InputIt current = first; current != last; ++current) {
      this->append(*current);
    }
  }
 
  Vector(ListBase &values, Allocator allocator = {}) : Vector(NoExceptConstructor(), allocator)
  {
    LISTBASE_FOREACH (T, value, &values) {
      this->append(value);
    }
  }
 
  Vector(const Vector &other) : Vector(other.as_span(), other.allocator_)
  {
  }
 
  template<int64_t OtherInlineBufferCapacity>
  Vector(const Vector<T, OtherInlineBufferCapacity, Allocator> &other)
      : Vector(other.as_span(), other.allocator_)
  {
  }
 
  template<int64_t OtherInlineBufferCapacity>
  Vector(Vector<T, OtherInlineBufferCapacity, Allocator> &&other) noexcept(
      std::is_nothrow_move_constructible_v<T>)
      : Vector(NoExceptConstructor(), other.allocator_)
  {
    const int64_t size = other.size();
 
    if (other.is_inline()) {
      if (size <= InlineBufferCapacity) {
        /* Copy between inline buffers. */
        uninitialized_relocate_n(other.begin_, size, begin_);
        end_ = begin_ + size;
      }
      else {
        /* Copy from inline buffer to newly allocated buffer. */
        const int64_t capacity = size;
        begin_ = static_cast<T *>(
            allocator_.allocate(sizeof(T) * static_cast<size_t>(capacity), alignof(T), AT));
        capacity_end_ = begin_ + capacity;
        uninitialized_relocate_n(other.begin_, size, begin_);
        end_ = begin_ + size;
      }
    }
    else {
      /* Steal the pointer. */
      begin_ = other.begin_;
      end_ = other.end_;
      capacity_end_ = other.capacity_end_;
    }
 
    other.begin_ = other.inline_buffer_;
    other.end_ = other.begin_;
    other.capacity_end_ = other.begin_ + OtherInlineBufferCapacity;
    UPDATE_VECTOR_SIZE(this);
    UPDATE_VECTOR_SIZE(&other);
  }
 
  ~Vector()
  {
    destruct_n(begin_, this->size());
    if (!this->is_inline()) {
      allocator_.deallocate(begin_);
    }
  }
 
  Vector &operator=(const Vector &other)
  {
    return copy_assign_container(*this, other);
  }
 
  Vector &operator=(Vector &&other)
  {
    return move_assign_container(*this, std::move(other));
  }
 
  const T &operator[](int64_t index) const
  {
    BLI_assert(index >= 0);
    BLI_assert(index < this->size());
    return begin_[index];
  }
 
  T &operator[](int64_t index)
  {
    BLI_assert(index >= 0);
    BLI_assert(index < this->size());
    return begin_[index];
  }
 
  operator Span<T>() const
  {
    return Span<T>(begin_, this->size());
  }
 
  operator MutableSpan<T>()
  {
    return MutableSpan<T>(begin_, this->size());
  }
 
  template<typename U, typename std::enable_if_t<is_span_convertible_pointer_v<T, U>> * = nullptr>
  operator Span<U>() const
  {
    return Span<U>(begin_, this->size());
  }
 
  template<typename U, typename std::enable_if_t<is_span_convertible_pointer_v<T, U>> * = nullptr>
  operator MutableSpan<U>()
  {
    return MutableSpan<U>(begin_, this->size());
  }
 
  Span<T> as_span() const
  {
    return *this;
  }
 
  MutableSpan<T> as_mutable_span()
  {
    return *this;
  }
 
  void reserve(const int64_t min_capacity)
  {
    if (min_capacity > this->capacity()) {
      this->realloc_to_at_least(min_capacity);
    }
  }
 
  void resize(const int64_t new_size)
  {
    BLI_assert(new_size >= 0);
    const int64_t old_size = this->size();
    if (new_size > old_size) {
      this->reserve(new_size);
      default_construct_n(begin_ + old_size, new_size - old_size);
    }
    else {
      destruct_n(begin_ + new_size, old_size - new_size);
    }
    end_ = begin_ + new_size;
    UPDATE_VECTOR_SIZE(this);
  }
 
  void resize(const int64_t new_size, const T &value)
  {
    BLI_assert(new_size >= 0);
    const int64_t old_size = this->size();
    if (new_size > old_size) {
      this->reserve(new_size);
      uninitialized_fill_n(begin_ + old_size, new_size - old_size, value);
    }
    else {
      destruct_n(begin_ + new_size, old_size - new_size);
    }
    end_ = begin_ + new_size;
    UPDATE_VECTOR_SIZE(this);
  }
 
  void clear()
  {
    destruct_n(begin_, this->size());
    end_ = begin_;
    UPDATE_VECTOR_SIZE(this);
  }
 
  void clear_and_make_inline()
  {
    destruct_n(begin_, this->size());
    if (!this->is_inline()) {
      allocator_.deallocate(begin_);
    }
 
    begin_ = inline_buffer_;
    end_ = begin_;
    capacity_end_ = begin_ + InlineBufferCapacity;
    UPDATE_VECTOR_SIZE(this);
  }
 
  void append(const T &value)
  {
    this->ensure_space_for_one();
    this->append_unchecked(value);
  }
  void append(T &&value)
  {
    this->ensure_space_for_one();
    this->append_unchecked(std::move(value));
  }
 
  int64_t append_and_get_index(const T &value)
  {
    const int64_t index = this->size();
    this->append(value);
    return index;
  }
 
  void append_non_duplicates(const T &value)
  {
    if (!this->contains(value)) {
      this->append(value);
    }
  }
 
  template<typename ForwardT> void append_unchecked(ForwardT &&value)
  {
    BLI_assert(end_ < capacity_end_);
    new (end_) T(std::forward<ForwardT>(value));
    end_++;
    UPDATE_VECTOR_SIZE(this);
  }
 
  void append_n_times(const T &value, const int64_t n)
  {
    BLI_assert(n >= 0);
    this->reserve(this->size() + n);
    uninitialized_fill_n(end_, n, value);
    this->increase_size_by_unchecked(n);
  }
 
  void increase_size_by_unchecked(const int64_t n) noexcept
  {
    BLI_assert(end_ + n <= capacity_end_);
    end_ += n;
    UPDATE_VECTOR_SIZE(this);
  }
 
  void extend(Span<T> array)
  {
    this->extend(array.data(), array.size());
  }
  void extend(const T *start, int64_t amount)
  {
    this->reserve(this->size() + amount);
    this->extend_unchecked(start, amount);
  }
 
  void extend_non_duplicates(Span<T> array)
  {
    for (const T &value : array) {
      this->append_non_duplicates(value);
    }
  }
 
  void extend_unchecked(Span<T> array)
  {
    this->extend_unchecked(array.data(), array.size());
  }
  void extend_unchecked(const T *start, int64_t amount)
  {
    BLI_assert(amount >= 0);
    BLI_assert(begin_ + amount <= capacity_end_);
    uninitialized_copy_n(start, amount, end_);
    end_ += amount;
    UPDATE_VECTOR_SIZE(this);
  }
 
  template<typename InputIt> void extend(InputIt first, InputIt last)
  {
    this->insert(this->end(), first, last);
  }
 
  void insert(const int64_t insert_index, const T &value)
  {
    this->insert(insert_index, Span<T>(&value, 1));
  }
  void insert(const int64_t insert_index, T &&value)
  {
    this->insert(
        insert_index, std::make_move_iterator(&value), std::make_move_iterator(&value + 1));
  }
  void insert(const int64_t insert_index, Span<T> array)
  {
    this->insert(begin_ + insert_index, array.begin(), array.end());
  }
  template<typename InputIt> void insert(const T *insert_position, InputIt first, InputIt last)
  {
    const int64_t insert_index = insert_position - begin_;
    this->insert(insert_index, first, last);
  }
  template<typename InputIt> void insert(const int64_t insert_index, InputIt first, InputIt last)
  {
    BLI_assert(insert_index >= 0);
    BLI_assert(insert_index <= this->size());
 
    const int64_t insert_amount = std::distance(first, last);
    const int64_t old_size = this->size();
    const int64_t new_size = old_size + insert_amount;
    const int64_t move_amount = old_size - insert_index;
 
    this->reserve(new_size);
    for (int64_t i = 0; i < move_amount; i++) {
      const int64_t src_index = insert_index + move_amount - i - 1;
      const int64_t dst_index = new_size - i - 1;
      try {
        new (static_cast<void *>(begin_ + dst_index)) T(std::move(begin_[src_index]));
      }
      catch (...) {
        /* Destruct all values that have been moved already. */
        destruct_n(begin_ + dst_index + 1, i);
        end_ = begin_ + src_index + 1;
        UPDATE_VECTOR_SIZE(this);
        throw;
      }
      begin_[src_index].~T();
    }
 
    try {
      std::uninitialized_copy_n(first, insert_amount, begin_ + insert_index);
    }
    catch (...) {
      /* Destruct all values that have been moved. */
      destruct_n(begin_ + new_size - move_amount, move_amount);
      end_ = begin_ + insert_index;
      UPDATE_VECTOR_SIZE(this);
      throw;
    }
    end_ = begin_ + new_size;
    UPDATE_VECTOR_SIZE(this);
  }
 
  void prepend(const T &&value)
  {
    this->insert(0, value);
  }
  void prepend(T &&value)
  {
    this->insert(0, std::move(value));
  }
  void prepend(Span<T> values)
  {
    this->insert(0, values);
  }
  template<typename InputIt> void prepend(InputIt first, InputIt last)
  {
    this->insert(0, first, last);
  }
 
  const T &last() const
  {
    BLI_assert(this->size() > 0);
    return *(end_ - 1);
  }
  T &last()
  {
    BLI_assert(this->size() > 0);
    return *(end_ - 1);
  }
 
  int64_t size() const
  {
    const int64_t current_size = static_cast<int64_t>(end_ - begin_);
    BLI_assert(debug_size_ == current_size);
    return current_size;
  }
 
  bool is_empty() const
  {
    return begin_ == end_;
  }
 
  void remove_last()
  {
    BLI_assert(!this->is_empty());
    end_--;
    end_->~T();
    UPDATE_VECTOR_SIZE(this);
  }
 
  T pop_last()
  {
    BLI_assert(!this->is_empty());
    T value = std::move(*(end_ - 1));
    end_--;
    end_->~T();
    UPDATE_VECTOR_SIZE(this);
    return value;
  }
 
  void remove_and_reorder(const int64_t index)
  {
    BLI_assert(index >= 0);
    BLI_assert(index < this->size());
    T *element_to_remove = begin_ + index;
    if (element_to_remove < end_) {
      *element_to_remove = std::move(*(end_ - 1));
    }
    end_--;
    end_->~T();
    UPDATE_VECTOR_SIZE(this);
  }
 
  void remove_first_occurrence_and_reorder(const T &value)
  {
    const int64_t index = this->first_index_of(value);
    this->remove_and_reorder(index);
  }
 
  void remove(const int64_t index)
  {
    BLI_assert(index >= 0);
    BLI_assert(index < this->size());
    const int64_t last_index = this->size() - 1;
    for (int64_t i = index; i < last_index; i++) {
      begin_[i] = std::move(begin_[i + 1]);
    }
    begin_[last_index].~T();
    end_--;
    UPDATE_VECTOR_SIZE(this);
  }
 
  void remove(const int64_t start_index, const int64_t amount)
  {
    const int64_t old_size = this->size();
    BLI_assert(start_index >= 0);
    BLI_assert(amount >= 0);
    BLI_assert(start_index + amount <= old_size);
    const int64_t move_amount = old_size - start_index - amount;
    for (int64_t i = 0; i < move_amount; i++) {
      begin_[start_index + i] = std::move(begin_[start_index + amount + i]);
    }
    destruct_n(end_ - amount, amount);
    end_ -= amount;
    UPDATE_VECTOR_SIZE(this);
  }
 
  int64_t first_index_of_try(const T &value) const
  {
    for (const T *current = begin_; current != end_; current++) {
      if (*current == value) {
        return static_cast<int64_t>(current - begin_);
      }
    }
    return -1;
  }
 
  int64_t first_index_of(const T &value) const
  {
    const int64_t index = this->first_index_of_try(value);
    BLI_assert(index >= 0);
    return index;
  }
 
  bool contains(const T &value) const
  {
    return this->first_index_of_try(value) != -1;
  }
 
  void fill(const T &value) const
  {
    initialized_fill_n(begin_, this->size(), value);
  }
 
  T *data()
  {
    return begin_;
  }
 
  const T *data() const
  {
    return begin_;
  }
 
  T *begin()
  {
    return begin_;
  }
  T *end()
  {
    return end_;
  }
 
  const T *begin() const
  {
    return begin_;
  }
  const T *end() const
  {
    return end_;
  }
 
  std::reverse_iterator<T *> rbegin()
  {
    return std::reverse_iterator<T *>(this->end());
  }
  std::reverse_iterator<T *> rend()
  {
    return std::reverse_iterator<T *>(this->begin());
  }
 
  std::reverse_iterator<const T *> rbegin() const
  {
    return std::reverse_iterator<T *>(this->end());
  }
  std::reverse_iterator<const T *> rend() const
  {
    return std::reverse_iterator<T *>(this->begin());
  }
 
  int64_t capacity() const
  {
    return static_cast<int64_t>(capacity_end_ - begin_);
  }
 
  IndexRange index_range() const
  {
    return IndexRange(this->size());
  }
 
  friend bool operator==(const Vector &a, const Vector &b)
  {
    return a.as_span() == b.as_span();
  }
 
  friend bool operator!=(const Vector &a, const Vector &b)
  {
    return !(a == b);
  }
 
  void print_stats(StringRef name = "") const
  {
    std::cout << "Vector Stats: " << name << "\n";
    std::cout << "  Address: " << this << "\n";
    std::cout << "  Elements: " << this->size() << "\n";
    std::cout << "  Capacity: " << (capacity_end_ - begin_) << "\n";
    std::cout << "  Inline Capacity: " << InlineBufferCapacity << "\n";
 
    char memory_size_str[15];
    BLI_str_format_byte_unit(memory_size_str, sizeof(*this), true);
    std::cout << "  Size on Stack: " << memory_size_str << "\n";
  }
 
 private:
  bool is_inline() const
  {
    return begin_ == inline_buffer_;
  }
 
  void ensure_space_for_one()
  {
    if (UNLIKELY(end_ >= capacity_end_)) {
      this->realloc_to_at_least(this->size() + 1);
    }
  }
 
  BLI_NOINLINE void realloc_to_at_least(const int64_t min_capacity)
  {
    if (this->capacity() >= min_capacity) {
      return;
    }
 
    /* At least double the size of the previous allocation. Otherwise consecutive calls to grow can
     * cause a reallocation every time even though min_capacity only increments.  */
    const int64_t min_new_capacity = this->capacity() * 2;
 
    const int64_t new_capacity = std::max(min_capacity, min_new_capacity);
    const int64_t size = this->size();
 
    T *new_array = static_cast<T *>(
        allocator_.allocate(static_cast<size_t>(new_capacity) * sizeof(T), alignof(T), AT));
    try {
      uninitialized_relocate_n(begin_, size, new_array);
    }
    catch (...) {
      allocator_.deallocate(new_array);
      throw;
    }
 
    if (!this->is_inline()) {
      allocator_.deallocate(begin_);
    }
 
    begin_ = new_array;
    end_ = begin_ + size;
    capacity_end_ = begin_ + new_capacity;
  }
};
 
#undef UPDATE_VECTOR_SIZE
 
template<typename T, int64_t InlineBufferCapacity = default_inline_buffer_capacity(sizeof(T))>
using RawVector = Vector<T, InlineBufferCapacity, RawAllocator>;
 
} /* namespace blender */