cascading.h

Go to the documentation of this file.

#pragma once
 
#include "../utility/aligned_malloc.h"
#include "../utility/alignment.h"
#include "../utility/assert.h"
#include "../utility/empty_base.h"
#include "../utility/meta.h"
#include "cascading_fwd.h"
#include "type_allocator.h"
 
#include <memory>
#include <type_traits>
 
namespace ktl
{
    template<typename Alloc>
    class cascading
    {
    private:
        static_assert(detail::has_no_value_type_v<Alloc>, "Building on top of typed allocators is not allowed. Use allocators without a type");
        static_assert(detail::has_owns_v<Alloc>, "The allocator is required to have an 'owns(void*)' method");
 
    public:
        typedef typename detail::get_size_type_t<Alloc> size_type;
 
    private:
        struct node
        {
            KTL_EMPTY_BASE Alloc Allocator;
            size_type Allocations = 0;
            node* Next = nullptr;
        };
 
    public:
        cascading() noexcept :
            m_Node(nullptr) {}
 
        cascading(const cascading&) = delete;
 
        cascading(cascading&& other)
            noexcept(std::is_nothrow_move_constructible_v<node>) :
            m_Node(std::move(other.m_Node))
        {
            other.m_Node = nullptr;
        }
 
        ~cascading()
        {
            release();
        }
 
        cascading& operator=(const cascading&) = delete;
 
        cascading& operator=(cascading&& rhs)
            noexcept(std::is_nothrow_move_assignable_v<node>)
        {
            release();
 
            m_Node = std::move(rhs.m_Node);
 
            rhs.m_Node = nullptr;
 
            return *this;
        }
 
        bool operator==(const cascading& rhs) const noexcept
        {
            return m_Node == rhs.m_Node;
        }
 
        bool operator!=(const cascading& rhs) const noexcept
        {
            return m_Node != rhs.m_Node;
        }
 
#pragma region Allocation
        void* allocate(size_type n) noexcept(
            std::is_nothrow_default_constructible_v<node> &&
            detail::has_nothrow_allocate_v<Alloc> &&
            (!detail::has_max_size_v<Alloc> || detail::has_nothrow_max_size_v<Alloc>))
        {
            // Add an initial allocator
            if (!m_Node)
                m_Node = detail::aligned_new<node>(detail::ALIGNMENT);
 
            if constexpr (detail::has_max_size_v<Alloc>)
            {
                if (n > m_Node->Allocator.max_size())
                    return nullptr;
            }
 
            void* p = m_Node->Allocator.allocate(n);
 
            // If the allocator was unable to allocate it, create a new one
            if (p == nullptr)
            {
                node* next = m_Node;
 
                m_Node = detail::aligned_new<node>(detail::ALIGNMENT);
                m_Node->Next = next;
 
                p = m_Node->Allocator.allocate(n);
            }
 
            if (p)
                m_Node->Allocations++;
 
            return p;
        }
 
        void deallocate(void* p, size_type n) noexcept(
            std::is_nothrow_destructible_v<node> &&
            detail::has_nothrow_owns_v<Alloc> &&
            detail::has_nothrow_deallocate_v<Alloc>)
        {
            KTL_ASSERT(p != nullptr);
 
            node* prev = nullptr;
            node* next = m_Node;
            while (next)
            {
                if (next->Allocator.owns(p))
                {
                    next->Allocator.deallocate(p, n);
 
                    // If this allocator holds no allocations then delete it
                    // Unless it's the main one, in which case keep it
                    if (--next->Allocations == 0 && prev)
                    {
                        prev->Next = next->Next;
 
                        detail::aligned_delete(next);
                    }
 
                    break;
                }
 
                prev = next;
                next = next->Next;
            }
        }
#pragma endregion
 
#pragma region Construction
        template<typename T, typename... Args>
        typename std::enable_if<detail::has_construct_v<Alloc, T*, Args...>, void>::type
        construct(T* p, Args&&... args) noexcept(
            detail::has_nothrow_owns_v<Alloc> &&
            detail::has_nothrow_construct_v<Alloc, T*, Args...>)
        {
            node* next = m_Node;
            while (next)
            {
                if (next->Allocator.owns(p))
                {
                    next->Allocator.construct(p, std::forward<Args>(args)...);
                    return;
                }
 
                next = next->Next;
            }
 
            // If we ever get to this point, something has gone wrong with the internal allocators
            KTL_ASSERT(false);
 
            ::new(p) T(std::forward<Args>(args)...);
        }
 
        template<typename T>
        typename std::enable_if<detail::has_destroy_v<Alloc, T*>, void>::type
        destroy(T* p) noexcept(
            detail::has_nothrow_owns_v<Alloc> &&
            detail::has_nothrow_destroy_v<Alloc, T*>)
        {
            node* next = m_Node;
            while (next)
            {
                if (next->Allocator.owns(p))
                {
                    next->Allocator.destroy(p);
                    return;
                }
 
                next = next->Next;
            }
 
            // If we ever get to this point, something has gone wrong with the internal allocators
            KTL_ASSERT(false);
 
            p->~T();
        }
#pragma endregion
 
#pragma region Utility
        template<typename A = Alloc>
        typename std::enable_if<detail::has_max_size_v<A>, size_type>::type
        max_size() const
            noexcept(detail::has_nothrow_max_size_v<A>)
        {
            return m_Node->Allocator.max_size();
        }
 
        bool owns(void* p) const
            noexcept(detail::has_nothrow_owns_v<Alloc>)
        {
            node* next = m_Node;
            while (next)
            {
                if (next->Allocator.owns(p))
                    return true;
 
                next = next->Next;
            }
 
            return false;
        }
#pragma endregion
 
    private:
        void release()
            noexcept(std::is_nothrow_destructible_v<node>)
        {
            node* next = m_Node;
            while (next)
            {
                // Assert that we only have a single allocator left
                // Otherwise someone forgot to deallocate memory
                // This isn't a hard-error though
                KTL_ASSERT(next == m_Node);
 
                node* current = next;
 
                next = current->Next;
 
                detail::aligned_delete(current);
            }
        }
 
    private:
        node* m_Node;
    };
}