freelist.h

Go to the documentation of this file.

#pragma once
 
#include "../utility/assert.h"
#include "../utility/empty_base.h"
#include "../utility/meta.h"
#include "../utility/source_location.h"
#include "freelist_fwd.h"
#include "type_allocator.h"
 
#include <cstddef>
#include <memory>
#include <type_traits>
 
namespace ktl
{
    template<size_t Min, size_t Max, typename Alloc>
    class freelist
    {
    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(Max >= sizeof(void*), "The freelist allocator requires a Max of at least the size of a pointer");
 
    public:
        typedef typename detail::get_size_type_t<Alloc> size_type;
 
    private:
        struct link
        {
            link* Next;
        };
        
    public:
        template<typename A = Alloc>
        freelist()
            noexcept(std::is_nothrow_default_constructible_v<A>) :
            m_Alloc(),
            m_Free(nullptr) {}
 
        template<typename... Args,
            typename = std::enable_if_t<
            std::is_constructible_v<Alloc, Args...>>>
        explicit freelist(Args&&... args)
            noexcept(std::is_nothrow_constructible_v<Alloc, Args...>) :
            m_Alloc(std::forward<Args>(args)...),
            m_Free(nullptr) {}
 
        freelist(const freelist&) = delete;
 
        freelist(freelist&& other)
            noexcept(std::is_nothrow_move_constructible_v<Alloc>) :
            m_Alloc(std::move(other.m_Alloc)),
            m_Free(other.m_Free)
        {
            // Moving raw allocators in use is undefined
            KTL_ASSERT(m_Alloc == other.m_Alloc || other.m_Free == nullptr);
 
            other.m_Free = nullptr;
        }
 
        ~freelist()
        {
            release();
        }
 
        freelist& operator=(const freelist&) = delete;
 
        freelist& operator=(freelist&& rhs)
            noexcept(std::is_nothrow_move_assignable_v<Alloc>)
        {
            release();
 
            m_Alloc = std::move(rhs.m_Alloc);
            m_Free = rhs.m_Free;
 
            // Moving raw allocators in use is undefined
            KTL_ASSERT(m_Alloc == rhs.m_Alloc || rhs.m_Free == nullptr);
 
            rhs.m_Free = nullptr;
 
            return *this;
        }
 
        bool operator==(const freelist& rhs) const
            noexcept(detail::has_nothrow_equal_v<Alloc>)
        {
            return m_Alloc == rhs.m_Alloc && m_Free == rhs.m_Free;
        }
 
        bool operator!=(const freelist& rhs) const
            noexcept(detail::has_nothrow_not_equal_v<Alloc>)
        {
            return m_Alloc != rhs.m_Alloc || m_Free != rhs.m_Free;
        }
 
#pragma region Allocation
        void* allocate(size_type n, const source_location source = KTL_SOURCE())
            noexcept(detail::has_nothrow_allocate_v<Alloc>)
        {
            if (n > Min && n <= Max)
            {
                link* next = m_Free;
                if (next)
                {
                    m_Free = next->Next;
                    return std::launder(next);
                }
 
                return detail::allocate(m_Alloc, Max, source);
            }
 
            return nullptr;
        }
 
        void deallocate(void* p, size_type n)
            noexcept(detail::has_nothrow_deallocate_v<Alloc>)
        {
            KTL_ASSERT(p != nullptr);
 
            if (n > Min && n <= Max && p)
            {
                link* next = std::launder(reinterpret_cast<link*>(p));
                next->Next = m_Free;
                m_Free = 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_construct_v<Alloc, T*, Args...>)
        {
            m_Alloc.construct(p, 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_destroy_v<Alloc, T*>)
        {
            m_Alloc.destroy(p);
        }
#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_Alloc.max_size();
        }
 
        template<typename A = Alloc>
        typename std::enable_if<detail::has_owns_v<A>, bool>::type
        owns(void* p) const
            noexcept(detail::has_nothrow_owns_v<A>)
        {
            return m_Alloc.owns(p);
        }
#pragma endregion
 
        Alloc& get_allocator() noexcept
        {
            return m_Alloc;
        }
 
        const Alloc& get_allocator() const noexcept
        {
            return m_Alloc;
        }
 
    private:
        void release()
            noexcept(detail::has_nothrow_deallocate_v<Alloc>)
        {
            link* next = m_Free;
            while (next)
            {
                link* prev = next;
                next = next->Next;
                m_Alloc.deallocate(prev, Max);
            }
        }
 
    private:
        KTL_EMPTY_BASE Alloc m_Alloc;
        link* m_Free;
    };
}