darray_ext_impl.h

#pragma once
#include "gaia/config/config.h"
 
#include <cstddef>
#include <initializer_list>
#include <type_traits>
#include <utility>
 
#include "gaia/cnt/impl/array_utils.h"
#include "gaia/core/iterator.h"
#include "gaia/core/utility.h"
#include "gaia/mem/data_layout_policy.h"
#include "gaia/mem/mem_sani.h"
#include "gaia/mem/mem_utils.h"
#include "gaia/mem/raw_data_holder.h"
 
namespace gaia {
  namespace cnt {
    namespace darr_ext_detail {
      using difference_type = int32_t;
      using size_type = uint32_t;
    } // namespace darr_ext_detail
 
    template <typename T, darr_ext_detail::size_type N, typename Allocator = mem::DefaultAllocatorAdaptor>
    class darr_ext {
    public:
      static_assert(N > 0);
 
      using value_type = T;
      using reference = T&;
      using const_reference = const T&;
      using pointer = T*;
      using const_pointer = const T*;
      using view_policy = mem::data_view_policy_aos<T>;
      using difference_type = darr_ext_detail::difference_type;
      using size_type = darr_ext_detail::size_type;
 
      using iterator = pointer;
      using const_iterator = const_pointer;
      using reverse_iterator = core::reverse_iterator<iterator, difference_type>;
      using const_reverse_iterator = core::reverse_iterator<const_iterator, difference_type>;
      using iterator_category = core::random_access_iterator_tag;
 
      static constexpr size_t value_size = sizeof(T);
      static constexpr size_type extent = N;
      static constexpr uint32_t allocated_bytes = view_policy::get_min_byte_size(0, N);
 
    private:
      mem::raw_data_holder<T, allocated_bytes> m_data;
      uint8_t* m_pDataHeap = nullptr;
      uint8_t* m_pData = m_data;
      size_type m_cnt = size_type(0);
      size_type m_cap = extent;
 
      void try_grow() {
        if (m_cnt == m_cap)
          reserve(m_cap != 0 ? (m_cap * 3 + 1) / 2 : 4);
      }
 
    public:
      darr_ext() noexcept = default;
      darr_ext(core::zero_t) noexcept {}
 
      darr_ext(size_type count, const_reference value) {
        resize(count, value);
      }
 
      darr_ext(size_type count) {
        resize(count);
      }
 
      template <typename InputIt>
      darr_ext(InputIt first, InputIt last) {
        const auto count = (size_type)core::distance(first, last);
        resize(count);
 
        if constexpr (std::is_pointer_v<InputIt>) {
          for (size_type i = 0; i < count; ++i)
            operator[](i) = first[i];
        } else if constexpr (std::is_same_v<typename InputIt::iterator_category, core::random_access_iterator_tag>) {
          for (size_type i = 0; i < count; ++i)
            operator[](i) = *(first[i]);
        } else {
          size_type i = 0;
          for (auto it = first; it != last; ++it)
            operator[](i++) = *it;
        }
      }
 
      darr_ext(std::initializer_list<T> il): darr_ext(il.begin(), il.end()) {}
 
      darr_ext(const darr_ext& other): darr_ext(other.begin(), other.end()) {}
 
      darr_ext(darr_ext&& other) noexcept {
        GAIA_ASSERT(core::addressof(other) != this);
 
        // Moving from stack-allocated source
        if (other.m_pDataHeap == nullptr) {
          GAIA_MEM_SANI_ADD_BLOCK(value_size, m_data, extent, other.size());
          mem::move_ctor_elements<T>(m_data, other.m_data, other.size());
          core::call_dtor_n(other.data(), other.size());
          GAIA_MEM_SANI_DEL_BLOCK(value_size, other.m_data, extent, other.size());
          m_pDataHeap = nullptr;
          m_pData = m_data;
        } else {
          m_pDataHeap = other.m_pDataHeap;
          m_pData = m_pDataHeap;
        }
 
        m_cnt = other.m_cnt;
        m_cap = other.m_cap;
 
        other.m_pDataHeap = nullptr;
        other.m_pData = other.m_data;
        other.m_cnt = size_type(0);
        other.m_cap = extent;
      }
 
      darr_ext& operator=(std::initializer_list<T> il) {
        *this = darr_ext(il.begin(), il.end());
        return *this;
      }
 
      darr_ext& operator=(const darr_ext& other) {
        GAIA_ASSERT(core::addressof(other) != this);
 
        resize(other.size());
        mem::copy_elements<T, false>(
            m_pData, (const uint8_t*)other.m_pData, other.size(), 0, capacity(), other.capacity());
 
        return *this;
      }
 
      darr_ext& operator=(darr_ext&& other) noexcept {
        GAIA_ASSERT(core::addressof(other) != this);
 
        // Release previously allocated memory or its stack-container annotation.
        if (m_pDataHeap != nullptr)
          view_policy::template free<Allocator>(m_pDataHeap, m_cap, m_cnt);
        else {
          core::call_dtor_n(data(), m_cnt);
          GAIA_MEM_SANI_DEL_BLOCK(value_size, m_data, extent, m_cnt);
        }
 
        // Moving from stack-allocated source
        if (other.m_pDataHeap == nullptr) {
          GAIA_MEM_SANI_ADD_BLOCK(value_size, m_data, extent, other.size());
          mem::move_ctor_elements<T>(m_data, other.m_data, other.size());
          core::call_dtor_n(other.data(), other.size());
          GAIA_MEM_SANI_DEL_BLOCK(value_size, other.m_data, extent, other.size());
          m_pDataHeap = nullptr;
          m_pData = m_data;
        } else {
          m_pDataHeap = other.m_pDataHeap;
          m_pData = m_pDataHeap;
        }
 
        m_cnt = other.m_cnt;
        m_cap = other.m_cap;
 
        other.m_pDataHeap = nullptr;
        other.m_pData = other.m_data;
        other.m_cnt = size_type(0);
        other.m_cap = extent;
 
        return *this;
      }
 
      ~darr_ext() {
        if (m_pDataHeap != nullptr)
          view_policy::template free<Allocator>(m_pDataHeap, m_cap, m_cnt);
        else {
          core::call_dtor_n(data(), m_cnt);
          GAIA_MEM_SANI_DEL_BLOCK(value_size, m_data, extent, m_cnt);
        }
      }
 
      GAIA_CLANG_WARNING_PUSH()
      // Memory is aligned so we can silence this warning
      GAIA_CLANG_WARNING_DISABLE("-Wcast-align")
 
      GAIA_NODISCARD pointer data() noexcept {
        return reinterpret_cast<pointer>(m_pData);
      }
 
      GAIA_NODISCARD const_pointer data() const noexcept {
        return reinterpret_cast<const_pointer>(m_pData);
      }
 
      GAIA_NODISCARD decltype(auto) operator[](size_type pos) noexcept {
        GAIA_ASSERT(pos < size());
        return view_policy::set({(typename view_policy::TargetCastType)m_pData, size()}, pos);
      }
 
      GAIA_NODISCARD decltype(auto) operator[](size_type pos) const noexcept {
        GAIA_ASSERT(pos < size());
        return view_policy::get({(typename view_policy::TargetCastType)m_pData, size()}, pos);
      }
 
      GAIA_CLANG_WARNING_POP()
 
      
      void reserve(size_type cap) {
        if (cap <= m_cap)
          return;
 
        auto* pDataOld = m_pDataHeap;
        m_pDataHeap = view_policy::template alloc<Allocator>(cap);
        GAIA_MEM_SANI_ADD_BLOCK(value_size, m_pDataHeap, cap, m_cnt);
        if (pDataOld != nullptr) {
          mem::move_ctor_elements<T>(m_pDataHeap, pDataOld, m_cnt);
          view_policy::template free<Allocator>(pDataOld, m_cap, m_cnt);
        } else {
          mem::move_ctor_elements<T>(m_pDataHeap, m_data, m_cnt);
          core::call_dtor_n(data(), m_cnt);
          GAIA_MEM_SANI_DEL_BLOCK(value_size, m_data, m_cap, m_cnt);
        }
 
        m_cap = cap;
        m_pData = m_pDataHeap;
      }
 
      void resize(size_type count, ResizePolicy policy = ResizePolicy::Exact) {
        if (count == m_cnt)
          return;
 
        // Resizing to a smaller size
        if (count < m_cnt) {
          // Destroy elements at the end
          core::call_dtor_n(&data()[count], m_cnt - count);
          GAIA_MEM_SANI_POP_N(value_size, data(), m_cap, m_cnt, m_cnt - count);
 
          m_cnt = count;
          return;
        }
 
        // Resizing to a bigger size but still within allocated capacity
        if (count <= m_cap) {
          // Construct new elements
          GAIA_MEM_SANI_PUSH_N(value_size, data(), m_cap, m_cnt, count - m_cnt);
          core::call_ctor_n(&data()[m_cnt], count - m_cnt);
 
          m_cnt = count;
          return;
        }
 
        const auto cap = detail::resize_capacity(policy, m_cap, count);
        auto* pDataOld = m_pDataHeap;
        m_pDataHeap = view_policy::template alloc<Allocator>(cap);
        GAIA_MEM_SANI_ADD_BLOCK(value_size, m_pDataHeap, cap, count);
        auto* pDataNew = reinterpret_cast<pointer>(m_pDataHeap);
        if (pDataOld != nullptr) {
          mem::move_ctor_elements<T>(m_pDataHeap, pDataOld, m_cnt);
          view_policy::template free<Allocator>(pDataOld, m_cap, m_cnt);
        } else {
          mem::move_ctor_elements<T>(m_pDataHeap, m_data, m_cnt);
          core::call_dtor_n(data(), m_cnt);
          GAIA_MEM_SANI_DEL_BLOCK(value_size, m_data, m_cap, m_cnt);
        }
 
        core::call_ctor_n(&pDataNew[m_cnt], count - m_cnt);
 
        m_cap = cap;
        m_cnt = count;
        m_pData = m_pDataHeap;
      }
 
      void resize(size_type count, const_reference value, ResizePolicy policy = ResizePolicy::Exact) {
        if (count <= m_cnt) {
          resize(count, policy);
          return;
        }
        const auto oldCount = m_cnt;
        if constexpr (std::is_copy_constructible_v<value_type>) {
          const value_type valueCopy = value;
          resize(count, policy);
          for (size_type i = oldCount; i < m_cnt; ++i)
            operator[](i) = valueCopy;
        } else {
          value_type valueCopy;
          valueCopy = value;
          resize(count, policy);
          for (size_type i = oldCount; i < m_cnt; ++i)
            operator[](i) = valueCopy;
        }
      }
 
      void push_back(const T& arg) {
        emplace_back(arg);
      }
 
      void push_back(T&& arg) {
        emplace_back(GAIA_MOV(arg));
      }
 
      template <typename... Args>
      decltype(auto) emplace_back(Args&&... args) {
        if GAIA_UNLIKELY (m_cnt == m_cap) {
          const auto cap = m_cap != 0 ? (m_cap * 3 + 1) / 2 : 4;
          auto* pDataNew = view_policy::template alloc<Allocator>(cap);
          GAIA_MEM_SANI_ADD_BLOCK(value_size, pDataNew, cap, m_cnt + 1);
          core::call_ctor(&static_cast<T*>(static_cast<void*>(pDataNew))[m_cnt], GAIA_FWD(args)...);
          mem::move_ctor_elements<T>(pDataNew, m_pData, m_cnt);
          if (m_pDataHeap != nullptr)
            view_policy::template free<Allocator>(m_pDataHeap, m_cap, m_cnt);
          else {
            core::call_dtor_n(data(), m_cnt);
            GAIA_MEM_SANI_DEL_BLOCK(value_size, m_data, m_cap, m_cnt);
          }
          m_pDataHeap = pDataNew;
          m_pData = pDataNew;
          m_cap = cap;
        } else {
          GAIA_MEM_SANI_PUSH(value_size, m_pData, m_cap, m_cnt);
          core::call_ctor(&data()[m_cnt], GAIA_FWD(args)...);
        }
        return (reference)data()[m_cnt++];
      }
 
      void pop_back() noexcept {
        GAIA_ASSERT(!empty());
 
        auto* ptr = &data()[m_cnt - 1];
        core::call_dtor(ptr);
        GAIA_MEM_SANI_POP(value_size, data(), m_cap, m_cnt);
 
        --m_cnt;
      }
 
      iterator insert(iterator pos, const T& arg) {
        GAIA_ASSERT(pos >= data());
        GAIA_ASSERT(pos <= iterator(data() + size()));
 
        T value(arg);
        const auto idxSrc = (size_type)core::distance(begin(), pos);
        try_grow();
        const auto idxDst = (size_type)core::distance(begin(), end());
 
        GAIA_MEM_SANI_PUSH(value_size, data(), m_cap, m_cnt);
        auto* ptr = &data()[idxSrc];
        if (idxSrc == idxDst) {
          core::call_ctor(ptr, std::move_if_noexcept(value));
        } else {
          mem::move_ctor_elements<T>((uint8_t*)&data()[idxDst], (uint8_t*)&data()[idxDst - 1], 1);
          mem::shift_elements_right<T, false>(m_pData, idxDst - 1, idxSrc, m_cap);
          mem::move_element<T, false>((uint8_t*)ptr, (uint8_t*)&value, 0, 0, 1, 1);
        }
 
        ++m_cnt;
 
        return iterator(ptr);
      }
 
      iterator insert(iterator pos, T&& arg) {
        GAIA_ASSERT(pos >= data());
        GAIA_ASSERT(pos <= iterator(data() + size()));
 
        T value(GAIA_MOV(arg));
        const auto idxSrc = (size_type)core::distance(begin(), pos);
        try_grow();
        const auto idxDst = (size_type)core::distance(begin(), end());
 
        GAIA_MEM_SANI_PUSH(value_size, data(), m_cap, m_cnt);
        auto* ptr = &data()[idxSrc];
        if (idxSrc == idxDst) {
          core::call_ctor(ptr, std::move_if_noexcept(value));
        } else {
          mem::move_ctor_elements<T>((uint8_t*)&data()[idxDst], (uint8_t*)&data()[idxDst - 1], 1);
          mem::shift_elements_right<T, false>(m_pData, idxDst - 1, idxSrc, m_cap);
          mem::move_element<T, false>((uint8_t*)ptr, (uint8_t*)&value, 0, 0, 1, 1);
        }
 
        ++m_cnt;
 
        return iterator(ptr);
      }
 
      iterator erase(iterator pos) noexcept {
        GAIA_ASSERT(pos >= data());
        GAIA_ASSERT(empty() || (pos < iterator(data() + size())));
 
        if (empty())
          return end();
 
        const auto idxSrc = (size_type)core::distance(begin(), pos);
        const auto idxDst = (size_type)core::distance(begin(), end()) - 1;
 
        mem::shift_elements_left<T, false>(m_pData, idxDst, idxSrc, m_cap);
        // Destroy if it's the last element
        auto* ptr = &data()[m_cnt - 1];
        core::call_dtor(ptr);
        GAIA_MEM_SANI_POP(value_size, data(), m_cap, m_cnt);
 
        --m_cnt;
 
        return iterator(&data()[idxSrc]);
      }
 
      iterator erase(iterator first, iterator last) noexcept {
        GAIA_ASSERT(first >= data())
        GAIA_ASSERT(empty() || (first < iterator(data() + size())));
        GAIA_ASSERT(last > first);
        GAIA_ASSERT(last <= iterator(data() + size()));
 
        if (empty())
          return end();
 
        const auto idxSrc = (size_type)core::distance(begin(), first);
        const auto idxDst = size();
        const auto cnt = (size_type)(last - first);
 
        mem::shift_elements_left_fast<T, false>(m_pData, idxDst, idxSrc, cnt, m_cap);
        // Destroy if it's the last element
        core::call_dtor_n(&data()[m_cnt - cnt], cnt);
        GAIA_MEM_SANI_POP_N(value_size, data(), m_cap, m_cnt, cnt);
 
        m_cnt -= cnt;
 
        return iterator(&data()[idxSrc]);
      }
 
      void clear() noexcept {
        resize(0);
      }
 
      void shrink_to_fit() {
        const auto cap = capacity();
        const auto cnt = size();
        if (m_pDataHeap == nullptr || (cnt > extent && cap == cnt))
          return;
 
        auto* pDataOld = m_pDataHeap;
        if (cnt <= extent) {
          GAIA_MEM_SANI_ADD_BLOCK(value_size, m_data, extent, cnt);
          mem::move_ctor_elements<T>(m_data, pDataOld, cnt);
          m_pDataHeap = nullptr;
          m_pData = m_data;
          m_cap = extent;
        } else {
          m_pDataHeap = view_policy::template alloc<Allocator>(cnt);
          GAIA_MEM_SANI_ADD_BLOCK(value_size, m_pDataHeap, cnt, cnt);
          mem::move_ctor_elements<T>(m_pDataHeap, pDataOld, cnt);
          m_pData = m_pDataHeap;
          m_cap = cnt;
        }
        view_policy::template free<Allocator>(pDataOld, cap, cnt);
      }
 
      template <typename Func>
      auto retain(Func&& func) noexcept {
        const auto oldCount = m_cnt;
        const auto newSize = detail::retain_array<false>(*this, m_cnt, func);
        GAIA_MEM_SANI_POP_N(value_size, data(), m_cap, oldCount, oldCount - m_cnt);
        return newSize;
      }
 
      GAIA_NODISCARD size_type size() const noexcept {
        return m_cnt;
      }
 
      GAIA_NODISCARD bool empty() const noexcept {
        return size() == 0;
      }
 
      GAIA_NODISCARD size_type capacity() const noexcept {
        return m_cap;
      }
 
      GAIA_NODISCARD size_type max_size() const noexcept {
        return N;
      }
 
      GAIA_NODISCARD decltype(auto) front() noexcept {
        GAIA_ASSERT(!empty());
        return (reference)*begin();
      }
 
      GAIA_NODISCARD decltype(auto) front() const noexcept {
        GAIA_ASSERT(!empty());
        return (const_reference)*begin();
      }
 
      GAIA_NODISCARD decltype(auto) back() noexcept {
        GAIA_ASSERT(!empty());
        return (reference) operator[](m_cnt - 1);
      }
 
      GAIA_NODISCARD decltype(auto) back() const noexcept {
        GAIA_ASSERT(!empty());
        return (const_reference) operator[](m_cnt - 1);
      }
 
      GAIA_NODISCARD auto begin() noexcept {
        return iterator(data());
      }
 
      GAIA_NODISCARD auto begin() const noexcept {
        return const_iterator(data());
      }
 
      GAIA_NODISCARD auto cbegin() const noexcept {
        return const_iterator(data());
      }
 
      GAIA_NODISCARD auto rbegin() noexcept {
        return reverse_iterator(end());
      }
 
      GAIA_NODISCARD auto rbegin() const noexcept {
        return const_reverse_iterator(end());
      }
 
      GAIA_NODISCARD auto crbegin() const noexcept {
        return const_reverse_iterator(cend());
      }
 
      GAIA_NODISCARD auto end() noexcept {
        return iterator(data() + size());
      }
 
      GAIA_NODISCARD auto end() const noexcept {
        return const_iterator(data() + size());
      }
 
      GAIA_NODISCARD auto cend() const noexcept {
        return const_iterator(data() + size());
      }
 
      GAIA_NODISCARD auto rend() noexcept {
        return reverse_iterator(begin());
      }
 
      GAIA_NODISCARD auto rend() const noexcept {
        return const_reverse_iterator(begin());
      }
 
      GAIA_NODISCARD auto crend() const noexcept {
        return const_reverse_iterator(cbegin());
      }
 
      GAIA_NODISCARD bool operator==(const darr_ext& other) const noexcept {
        if (m_cnt != other.m_cnt)
          return false;
        const size_type n = size();
        for (size_type i = 0; i < n; ++i)
          if (!(operator[](i) == other[i]))
            return false;
        return true;
      }
 
      GAIA_NODISCARD constexpr bool operator!=(const darr_ext& other) const noexcept {
        return !operator==(other);
      }
    };
 
    namespace detail {
      template <typename T, uint32_t N, uint32_t... I>
      darr_ext<std::remove_cv_t<T>, N> to_sarray_impl(T (&a)[N], std::index_sequence<I...> /*no_name*/) {
        return {{a[I]...}};
      }
    } // namespace detail
 
    template <typename T, uint32_t N>
    darr_ext<std::remove_cv_t<T>, N> to_sarray(T (&a)[N]) {
      return detail::to_sarray_impl(a, std::make_index_sequence<N>{});
    }
 
  } // namespace cnt
 
} // namespace gaia