shm/Project4/page_heap.h

#pragma once

#define PTR_TO_LV0(ptr)	(ptr) >> 25
#define PTR_TO_LV1(ptr)	((ptr) >> 15 & 0x3FF)
#define PTR_TO_LV2(ptr)	((ptr) & 0x7FFF)
namespace bg
{
    namespace detail
    {
        struct Span
        {
            Span() = default;
            Span(size_t start_page, size_t page_count) : m_start_page(start_page), m_page_count(page_count) {}

            void RemoveNextSpan()
            {
                auto next_span = m_next;

                m_next = next_span->m_next;
                next_span->m_next->m_prev = next_span->m_prev;

                next_span->m_prev = nullptr;
                next_span->m_next = nullptr;
            }

            void InstertNextSpan(Span* span)
            {
                span->m_prev = m_next->m_prev;
                span->m_next = m_next;
                m_next->m_prev = span;
                m_next = span;
            }

            bool m_in_use{};
            unsigned char m_size_class{255};
            size_t m_used_count{};
            size_t m_start_page{};
            size_t m_page_count{};

            Span* m_prev{this};
            Span* m_next{this};
            void* m_chunk_list{};

        };

        template<size_t size0, size_t size1, size_t size2>
        struct RadixTree
        {
            struct  NodeV2
            {
                Span* lv2[1 << size2]{0};
            };
            struct NodeV1
            {
                NodeV2* lv1[1 << size1]{0};
            };

            NodeV1* lv0[1 << size0]{0};
        };

        template<typename T>
        struct MetadataAllocator
        {
            void* m_free_list{};
            char* m_free_area{};
            size_t m_free_left{};
        };


        class PageHeap
        {
        public:
            PageHeap();

            bg::detail::Span* GetSpanMap(size_t start_page);

            bool SetSpanMap(size_t page, bg::detail::Span* span);

            void DeallocateSpan(bg::detail::Span* s);

            void RegisterSpan(bg::detail::Span* s);

            bool GrowHeap(size_t page_count);

            bg::detail::Span* AllocateSpan(size_t page_count);

            bg::detail::Span* GetNewSpan();

            bg::detail::Span* GetLastSpan(size_t page_count);

            using  RadixTree = RadixTree<10ul, 10ul, 15ul>;
            RadixTree m_span_map;
            MetadataAllocator<bg::detail::Span> m_span_allocator;
            Span m_free_lists[128]{};
            Span m_large_list{};
        };
    }
}