lifo.h

//   Copyright Giuseppe Campana (giu.campana@gmail.com) 2016-2018.
// Distributed under the Boost Software License, Version 1.0.
//    (See accompanying file LICENSE_1_0.txt or copy at
//          http://www.boost.org/LICENSE_1_0.txt)

#pragma once
#include <cstring> // for memcpy
#include <density/default_allocator.h>
#include <density/density_common.h>
#include <density/runtime_type.h>
#include <iterator>
#include <type_traits>

namespace density
{
    template <typename UNDERLYING_ALLOCATOR = default_allocator, size_t ALIGNMENT = alignof(void *)>
    class lifo_allocator : private UNDERLYING_ALLOCATOR
    {
      public:
        static_assert(ALIGNMENT > 0 && is_power_of_2(ALIGNMENT), "ALIGNMENT must be a power of 2");

        using underlying_allocator = UNDERLYING_ALLOCATOR;

        static constexpr size_t alignment = ALIGNMENT;

        // compile time checks
        static_assert(
          alignment <= UNDERLYING_ALLOCATOR::page_alignment,
          "The alignment of the pages is too small");

        constexpr lifo_allocator() noexcept {}

        lifo_allocator(const UNDERLYING_ALLOCATOR & i_underlying_allocator)
            : UNDERLYING_ALLOCATOR(i_underlying_allocator)
        {
        }

        lifo_allocator(UNDERLYING_ALLOCATOR && i_underlying_allocator)
            : UNDERLYING_ALLOCATOR(std::move(i_underlying_allocator))
        {
        }

        lifo_allocator(const lifo_allocator &) = delete;

        lifo_allocator & operator=(const lifo_allocator &) = delete;

        void * allocate(size_t i_size)
        {
            DENSITY_ASSUME_UINT_ALIGNED(i_size, alignment);

            auto const new_top = m_top + i_size;
            auto const new_offset =
              new_top - uint_lower_align(m_top, UNDERLYING_ALLOCATOR::page_alignment);
            if (!DENSITY_LIKELY(new_offset < UNDERLYING_ALLOCATOR::page_size))
            {
                // page overflow
                return allocate_slow_path(i_size);
            }
            else
            {
                // advance m_top
                DENSITY_ASSUME(i_size <= UNDERLYING_ALLOCATOR::page_size);
                auto const new_block = reinterpret_cast<void *>(m_top);
                m_top                = new_top;
                return new_block;
            }
        }

        void * allocate_empty() noexcept { return reinterpret_cast<void *>(m_top); }

        void deallocate(void * i_block, size_t i_size) noexcept
        {
            DENSITY_ASSUME(i_block != nullptr);
            DENSITY_ASSUME_UINT_ALIGNED(i_size, alignment);

            // this check detects page switches and external blocks
            if (!DENSITY_LIKELY(same_page(i_block, reinterpret_cast<void *>(m_top))))
            {
                deallocate_slow_path(i_block, i_size);
            }
            else
            {
                m_top = reinterpret_cast<uintptr_t>(i_block);
            }
        }

        void * reallocate(void * i_block, size_t i_old_size, size_t i_new_size)
        {
            // branch depending on the old block: this check detects page switches and external blocks
            if (same_page(i_block, reinterpret_cast<void *>(m_top)))
            {
                // the following call sets the top only when it is sure to not throw
                auto const new_block = set_top_and_allocate(i_block, i_new_size);

                copy(i_block, i_old_size, new_block, i_new_size);
                return new_block;
            }
            else
            {
                if (
                  (m_top & (UNDERLYING_ALLOCATOR::page_alignment - 1)) == sizeof(PageHeader) &&
                  same_page(reinterpret_cast<PageHeader *>(m_top)[-1].m_prev_page, i_block))
                {
                    auto const page_to_deallocate = reinterpret_cast<void *>(m_top);
                    DENSITY_ASSERT_INTERNAL(!same_page(page_to_deallocate, i_block));

                    // the following call sets the top only when it is sure to not throw
                    auto const new_block = set_top_and_allocate(i_block, i_new_size);

                    copy(i_block, i_old_size, new_block, i_new_size);

                    UNDERLYING_ALLOCATOR::deallocate_page(page_to_deallocate);
                    return new_block;
                }
                else
                {
                    // the old block is external
                    auto const new_block = allocate(i_new_size);
                    copy(i_block, i_old_size, new_block, i_new_size);
                    UNDERLYING_ALLOCATOR::deallocate(i_block, i_old_size, alignment);
                    return new_block;
                }
            }
        }

        ~lifo_allocator()
        {
            if (m_top != s_virgin_top)
            {
                UNDERLYING_ALLOCATOR::deallocate_page(reinterpret_cast<void *>(m_top));
            }
        }

        UNDERLYING_ALLOCATOR & underlying_allocator_ref() noexcept { return *this; }

        const UNDERLYING_ALLOCATOR & underlying_allocator_ref() const noexcept { return *this; }

      private:
        struct alignas(alignment) alignas(void *) PageHeader
        {
            void * m_prev_page; 
        };

        static_assert(
          UNDERLYING_ALLOCATOR::page_size / 2 > sizeof(PageHeader), "page_size is too small");

        static bool same_page(const void * i_first, const void * i_second) noexcept
        {
            auto const page_mask = UNDERLYING_ALLOCATOR::page_alignment - 1;
            return ((reinterpret_cast<uintptr_t>(i_first) ^ reinterpret_cast<uintptr_t>(i_second)) &
                    ~page_mask) == 0;
        }

        DENSITY_NO_INLINE void * allocate_slow_path(size_t i_size)
        {
            DENSITY_ASSUME_UINT_ALIGNED(i_size, alignment);
            if (i_size < UNDERLYING_ALLOCATOR::page_size / 2)
            {
                // allocate a new page
                auto const new_page = UNDERLYING_ALLOCATOR::allocate_page();
                DENSITY_ASSUME(new_page != nullptr);
                auto const new_header   = new (new_page) PageHeader;
                new_header->m_prev_page = reinterpret_cast<void *>(m_top);
                m_top                   = reinterpret_cast<uintptr_t>(new_header + 1) + i_size;
                return new_header + 1;
            }
            else
            {
                // external block
                return UNDERLYING_ALLOCATOR::allocate(i_size, alignment);
            }
        }

        DENSITY_NO_INLINE void deallocate_slow_path(void * i_block, size_t i_size) noexcept
        {
            DENSITY_ASSUME_UINT_ALIGNED(i_size, alignment);

            if (
              (m_top & (UNDERLYING_ALLOCATOR::page_alignment - 1)) == sizeof(PageHeader) &&
              same_page(reinterpret_cast<PageHeader *>(m_top)[-1].m_prev_page, i_block))
            {
                // deallocate the top page
                auto const page_to_deallocate = reinterpret_cast<void *>(m_top);
                DENSITY_ASSERT_INTERNAL(!same_page(page_to_deallocate, i_block));
                UNDERLYING_ALLOCATOR::deallocate_page(page_to_deallocate);
                m_top = reinterpret_cast<uintptr_t>(i_block);
            }
            else
            {
                // external block
                UNDERLYING_ALLOCATOR::deallocate(i_block, i_size, alignment);
            }
        }

        void * set_top_and_allocate(void * const i_current_top, size_t const i_size)
        {
            DENSITY_ASSUME_UINT_ALIGNED(i_size, alignment);

            auto const current_top = reinterpret_cast<uintptr_t>(i_current_top);

            // we have to procrastinate the assignment of m_top until we have allocated the page or the external block
            auto const new_top = current_top + i_size;
            auto const new_offset =
              new_top - uint_lower_align(current_top, UNDERLYING_ALLOCATOR::page_alignment);
            if (new_offset < UNDERLYING_ALLOCATOR::page_size)
            {
                DENSITY_ASSUME(i_size <= UNDERLYING_ALLOCATOR::page_size);
                auto const new_block = i_current_top;
                m_top                = new_top;
                return new_block;
            }
            else if (i_size < UNDERLYING_ALLOCATOR::page_size / 2)
            {
                // allocate a new page
                auto const new_page =
                  static_cast<PageHeader *>(UNDERLYING_ALLOCATOR::allocate_page());
                new_page->m_prev_page = reinterpret_cast<void *>(current_top);
                m_top                 = reinterpret_cast<uintptr_t>(new_page + 1) + i_size;
                return new_page + 1;
            }
            else
            {
                // external block
                auto const new_external_block = UNDERLYING_ALLOCATOR::allocate(i_size, alignment);
                m_top                         = reinterpret_cast<uintptr_t>(i_current_top);
                return new_external_block;
            }
        }

        void copy(
          void * i_old_block, size_t i_old_size, void * i_new_block, size_t i_new_size) noexcept
        {
            if (i_old_block != i_new_block)
            {
                auto const size_to_copy = detail::size_min(i_new_size, i_old_size);
                DENSITY_ASSUME_UINT_ALIGNED(size_to_copy, alignment);
                DENSITY_ASSUME_ALIGNED(i_old_block, alignment);
                DENSITY_ASSUME_ALIGNED(i_new_block, alignment);
                memcpy(i_new_block, i_old_block, size_to_copy);
            }
        }

      private:
        static constexpr uintptr_t s_virgin_top =
          uint_lower_align(UNDERLYING_ALLOCATOR::page_alignment - 1, alignment);
        uintptr_t m_top = s_virgin_top; 
    };

    namespace detail
    {
        template <int = 0> class ThreadLifoAllocator
        {
#ifndef DENSITY_USER_DATA_STACK

            // default data stack

          public:
            static constexpr size_t alignment =
              lifo_allocator<data_stack_underlying_allocator>::alignment;

            static void * allocate(size_t i_size) { return s_allocator.allocate(i_size); }

            static void * allocate_empty() noexcept { return s_allocator.allocate_empty(); }

            static void * reallocate(void * i_block, size_t i_old_size, size_t i_new_size)
            {
                return s_allocator.reallocate(i_block, i_old_size, i_new_size);
            }

            static void deallocate(void * i_block, size_t i_size) noexcept
            {
                s_allocator.deallocate(i_block, i_size);
            }

          private:
            static thread_local lifo_allocator<data_stack_underlying_allocator> s_allocator;
#else

            // DENSITY_USER_DATA_STACK is defined: forward to the user defined data stack

          public:
            static constexpr size_t alignment = user_data_stack::alignment;

            static void * allocate(size_t i_size) { return user_data_stack::allocate(i_size); }

            static void * allocate_empty() noexcept { return user_data_stack::allocate_empty(); }

            static void * reallocate(void * i_block, size_t i_old_size, size_t i_new_size)
            {
                return user_data_stack::reallocate(i_block, i_old_size, i_new_size);
            }

            static void deallocate(void * i_block, size_t i_size) noexcept
            {
                user_data_stack::deallocate(i_block, i_size);
            }

#endif
        };

#ifndef DENSITY_USER_DATA_STACK
        template <int DUMMY>
        thread_local lifo_allocator<data_stack_underlying_allocator>
          ThreadLifoAllocator<DUMMY>::s_allocator;
#endif

    } // namespace detail

    class lifo_buffer
    {
      public:
        static constexpr size_t alignment = detail::ThreadLifoAllocator<>::alignment;

        lifo_buffer() noexcept : m_data(detail::ThreadLifoAllocator<>::allocate_empty()), m_size(0)
        {
        }

        lifo_buffer(size_t i_size)
            : m_data(detail::ThreadLifoAllocator<>::allocate(uint_upper_align(i_size, alignment))),
              m_size(i_size)
        {
        }

        lifo_buffer(const lifo_buffer &) = delete;

        lifo_buffer & operator=(const lifo_buffer &) = delete;

        ~lifo_buffer()
        {
            detail::ThreadLifoAllocator<>::deallocate(m_data, uint_upper_align(m_size, alignment));
        }

        void * resize(size_t i_new_size)
        {
            /* we must allocate before updating any data member, so that in case of exception no change remains */
            auto const block = m_data = detail::ThreadLifoAllocator<>::reallocate(
              m_data, uint_upper_align(m_size, alignment), uint_upper_align(i_new_size, alignment));
            m_size = i_new_size;
            return block;
        }

        void * data() const noexcept { return m_data; }

        size_t size() const noexcept { return m_size; }

      private:
        void * m_data;
        size_t m_size;
    };

    namespace detail
    {
        template <
          typename TYPE,
          bool OVER_ALIGNED = (alignof(TYPE) > detail::ThreadLifoAllocator<>::alignment)>
        class LifoArrayImpl;

        template <typename TYPE> class LifoArrayImpl<TYPE, false>
        {
          public:
            static size_t compute_mem_size(size_t i_element_count) noexcept
            {
                auto const mem_size  = i_element_count * sizeof(TYPE);
                bool already_aligned = sizeof(TYPE) % detail::ThreadLifoAllocator<>::alignment == 0;
                if (already_aligned)
                    return mem_size;
                else
                    return uint_upper_align(mem_size, detail::ThreadLifoAllocator<>::alignment);
            }

            LifoArrayImpl(size_t i_element_count)
                : m_elements(static_cast<TYPE *>(
                    detail::ThreadLifoAllocator<>::allocate(compute_mem_size(i_element_count)))),
                  m_size(i_element_count)
            {
            }

            ~LifoArrayImpl()
            {
                detail::ThreadLifoAllocator<>::deallocate(m_elements, compute_mem_size(m_size));
            }

          protected:
            TYPE * const m_elements;
            size_t const m_size; 
        };

        template <typename TYPE> class LifoArrayImpl<TYPE, true>
        {
          public:
            static constexpr size_t size_overhead =
              alignof(TYPE) - detail::ThreadLifoAllocator<>::alignment;

            static size_t compute_mem_size(size_t i_element_count) noexcept
            {
                auto const mem_size  = i_element_count * sizeof(TYPE) + size_overhead;
                bool already_aligned = sizeof(TYPE) % detail::ThreadLifoAllocator<>::alignment == 0;
                if (already_aligned)
                    return mem_size;
                else
                    return uint_upper_align(mem_size, detail::ThreadLifoAllocator<>::alignment);
            }

            LifoArrayImpl(size_t i_size) : m_size(i_size)
            {
                auto const mem_size = compute_mem_size(m_size);
                m_block             = detail::ThreadLifoAllocator<>::allocate(mem_size);
                m_elements = static_cast<TYPE *>(address_upper_align(m_block, alignof(TYPE)));
                DENSITY_ASSERT_INTERNAL(
                  address_diff(m_elements, m_block) <= size_overhead &&
                  m_elements + m_size <= address_add(m_block, mem_size));
            }

            ~LifoArrayImpl()
            {
                auto const mem_size = compute_mem_size(m_size);
                detail::ThreadLifoAllocator<>::deallocate(m_block, mem_size);
            }

          protected:
            void *       m_block;
            TYPE *       m_elements;
            size_t const m_size; 
        };
    } // namespace detail

    template <typename TYPE> class lifo_array final : detail::LifoArrayImpl<TYPE>
    {
        struct PrivateTag
        {
        };

      public:
        using value_type      = TYPE;
        using reference       = TYPE &;
        using const_reference = TYPE &;
        using pointer         = TYPE *;
        using const_pointer   = const TYPE *;
        using size_type       = size_t;
        using difference_type = ptrdiff_t;

        class iterator
        {
          public:
            using difference_type   = ptrdiff_t;
            using value_type        = TYPE;
            using pointer           = TYPE *;
            using reference         = TYPE &;
            using iterator_category = std::random_access_iterator_tag;

            iterator(PrivateTag, TYPE * i_ptr) noexcept : m_curr(i_ptr) {}

            iterator() noexcept                 = default;
            iterator(const iterator &) noexcept = default;
            iterator & operator=(const iterator &) noexcept = default;

            TYPE * operator->() const noexcept { return m_curr; }

            TYPE & operator*() const & noexcept { return *m_curr; }

            TYPE && operator*() const && noexcept { return *m_curr; }

            iterator & operator++() noexcept
            {
                m_curr++;
                return *this;
            }

            iterator operator++(int) noexcept
            {
                iterator copy(*this);
                         operator++();
                return copy;
            }

            iterator & operator+=(difference_type i_diff) noexcept
            {
                m_curr += i_diff;
                return *this;
            }

            iterator & operator--() noexcept
            {
                m_curr--;
                return *this;
            }

            iterator operator--(int) noexcept
            {
                iterator copy(*this);
                         operator++();
                return copy;
            }

            iterator & operator-=(difference_type i_diff) noexcept
            {
                m_curr -= i_diff;
                return *this;
            }

            friend difference_type
              operator-(const iterator & i_first, const iterator & i_second) noexcept
            {
                return i_first.m_curr - i_second.m_curr;
            }

            // relational operators

            friend bool operator<(const iterator & i_first, const iterator & i_second) noexcept
            {
                return i_first.m_curr < i_second.m_curr;
            }

            friend bool operator<=(const iterator & i_first, const iterator & i_second) noexcept
            {
                return i_first.m_curr <= i_second.m_curr;
            }

            friend bool operator==(const iterator & i_first, const iterator & i_second) noexcept
            {
                return i_first.m_curr == i_second.m_curr;
            }

            friend bool operator!=(const iterator & i_first, const iterator & i_second) noexcept
            {
                return i_first.m_curr != i_second.m_curr;
            }

            friend bool operator>(const iterator & i_first, const iterator & i_second) noexcept
            {
                return i_first.m_curr > i_second.m_curr;
            }

            friend bool operator>=(const iterator & i_first, const iterator & i_second) noexcept
            {
                return i_first.m_curr >= i_second.m_curr;
            }

          private:
            TYPE * m_curr{};
        };

        class const_iterator
        {
          public:
            using difference_type   = ptrdiff_t;
            using value_type        = const TYPE;
            using pointer           = const TYPE *;
            using reference         = const TYPE &;
            using iterator_category = std::random_access_iterator_tag;

            const_iterator(PrivateTag, const TYPE * i_ptr) noexcept : m_curr(i_ptr) {}

            const_iterator() noexcept                       = default;
            const_iterator(const const_iterator &) noexcept = default;
            const_iterator & operator=(const const_iterator &) noexcept = default;

            const TYPE * operator->() const noexcept { return m_curr; }

            const TYPE & operator*() const & noexcept { return *m_curr; }

            const TYPE && operator*() const && noexcept { return *m_curr; }

            const_iterator & operator++() noexcept
            {
                m_curr++;
                return *this;
            }

            const_iterator operator++(int) noexcept
            {
                const_iterator copy(*this);
                               operator++();
                return copy;
            }

            const_iterator & operator+=(difference_type i_diff) noexcept
            {
                m_curr += i_diff;
                return *this;
            }

            const_iterator & operator--() noexcept
            {
                m_curr--;
                return *this;
            }

            const_iterator operator--(int) noexcept
            {
                const_iterator copy(*this);
                               operator++();
                return copy;
            }

            const_iterator & operator-=(difference_type i_diff) noexcept
            {
                m_curr -= i_diff;
                return *this;
            }

            friend difference_type
              operator-(const const_iterator & i_first, const const_iterator & i_second) noexcept
            {
                return i_first.m_curr - i_second.m_curr;
            }

            // relational operators

            friend bool
              operator<(const const_iterator & i_first, const const_iterator & i_second) noexcept
            {
                return i_first.m_curr < i_second.m_curr;
            }

            friend bool
              operator<=(const const_iterator & i_first, const const_iterator & i_second) noexcept
            {
                return i_first.m_curr <= i_second.m_curr;
            }

            friend bool
              operator==(const const_iterator & i_first, const const_iterator & i_second) noexcept
            {
                return i_first.m_curr == i_second.m_curr;
            }

            friend bool
              operator!=(const const_iterator & i_first, const const_iterator & i_second) noexcept
            {
                return i_first.m_curr != i_second.m_curr;
            }

            friend bool
              operator>(const const_iterator & i_first, const const_iterator & i_second) noexcept
            {
                return i_first.m_curr > i_second.m_curr;
            }

            friend bool
              operator>=(const const_iterator & i_first, const const_iterator & i_second) noexcept
            {
                return i_first.m_curr >= i_second.m_curr;
            }

          private:
            const TYPE * m_curr{};
        };

        lifo_array(size_t i_size) : detail::LifoArrayImpl<TYPE>(i_size)
        {
            default_construct(std::is_pod<TYPE>());
        }

        template <typename... CONSTRUCTION_PARAMS>
        lifo_array(size_t i_size, const CONSTRUCTION_PARAMS &... i_construction_params)
            : detail::LifoArrayImpl<TYPE>(i_size)
        {
            size_t element_index = 0;
            try
            {
                for (; element_index < i_size; element_index++)
                {
                    new (m_elements + element_index) TYPE(i_construction_params...);
                }
            }
            catch (...)
            {
                // destroy all the elements constructed till now, and then deallocate
                auto it = m_elements + element_index;
                it--;
                for (; it >= m_elements; it--)
                {
                    it->TYPE::~TYPE();
                }
                throw;
            }
        }

        template <typename INPUT_ITERATOR>
        lifo_array(
          INPUT_ITERATOR i_begin,
          INPUT_ITERATOR i_end,
          typename std::iterator_traits<INPUT_ITERATOR>::iterator_category =
            typename std::iterator_traits<INPUT_ITERATOR>::iterator_category())
            : detail::LifoArrayImpl<TYPE>(std::distance(i_begin, i_end))
        {
            auto dest_element = m_elements;
            try
            {
                for (; i_begin != i_end; ++i_begin)
                {
                    DENSITY_ASSUME(dest_element != nullptr);
                    new (dest_element) TYPE(*i_begin);
                    ++dest_element;
                }
            }
            catch (...)
            {
                // destroy all the elements constructed until now. The destructor of the base class will deallocate the block
                auto count_to_destroy = dest_element - m_elements;
                while (count_to_destroy > 0)
                {
                    --dest_element;
                    --count_to_destroy;
                    dest_element->TYPE::~TYPE();
                }
                throw;
            }
        }

        lifo_array(const lifo_array &) = delete;

        lifo_array & operator=(const lifo_array &) = delete;

        ~lifo_array() { destroy_elements(std::is_trivially_destructible<TYPE>()); }

        size_t size() const noexcept { return m_size; }

        TYPE & operator[](size_t i_index) noexcept
        {
            DENSITY_ASSUME(i_index < m_size);
            return m_elements[i_index];
        }

        const TYPE & operator[](size_t i_index) const noexcept
        {
            DENSITY_ASSUME(i_index < m_size);
            return m_elements[i_index];
        }

        pointer data() noexcept { return m_elements; }

        const_pointer data() const noexcept { return m_elements; }

        iterator begin() noexcept { return iterator(PrivateTag{}, m_elements); }

        iterator end() noexcept { return iterator(PrivateTag{}, m_elements + m_size); }

        const_iterator cbegin() const noexcept { return const_iterator(PrivateTag{}, m_elements); }

        const_iterator cend() const noexcept
        {
            return const_iterator(PrivateTag{}, m_elements + m_size);
        }

        const_iterator begin() const noexcept { return const_iterator(PrivateTag{}, m_elements); }

        const_iterator end() const noexcept
        {
            return const_iterator(PrivateTag{}, m_elements + m_size);
        }

      private:
        // trivially default constructible types
        void default_construct(std::true_type) {}

        // non-trivially default constructible types
        void default_construct(std::false_type)
        {
            size_t element_index = 0;
            try
            {
                for (; element_index < m_size; element_index++)
                {
                    auto const dest = m_elements + element_index;
                    DENSITY_ASSUME(dest != nullptr);
                    new (dest) TYPE();
                }
            }
            catch (...)
            {
                // destroy all the elements constructed until now. The destructor of the base class will deallocate the block
                auto count_to_destroy = element_index;
                while (count_to_destroy > 0)
                {
                    --count_to_destroy;
                    m_elements[count_to_destroy].TYPE::~TYPE();
                }
                throw;
            }
        }

        void destroy_elements(std::true_type) noexcept {}

        void destroy_elements(std::false_type) noexcept
        {
            auto it = m_elements + m_size;
            it--;
            for (; it >= m_elements; it--)
            {
                it->TYPE::~TYPE();
            }
        }

      private:
        using detail::LifoArrayImpl<TYPE>::m_elements;
        using detail::LifoArrayImpl<TYPE>::m_size;
    };

} // namespace density