allocator.h

Go to the documentation of this file.

#ifndef ALLOCATOR_H
#define ALLOCATOR_H
 
#include "config.h"
#include "error.h"
#include "maths.h"
#include "type_traits"
#include "utility"
 
namespace original {
 
    class allocators final {
    public:
        template <typename TYPE>
        static TYPE* malloc(u_integer size);
 
        template <typename TYPE>
        static void free(TYPE* ptr);
    };
 
    template<typename TYPE, template <typename> typename DERIVED>
    class allocatorBase{
    public:
        using propagate_on_container_copy_assignment = std::false_type; 
        using propagate_on_container_move_assignment = std::false_type; 
        using propagate_on_container_swap = std::false_type; 
        using propagate_on_container_merge = std::false_type; 
 
        template <typename O_TYPE>
        using rebind_alloc = DERIVED<O_TYPE>;
 
        constexpr allocatorBase();
 
        virtual TYPE* allocate(u_integer size) = 0;
 
        virtual void deallocate(TYPE* ptr, u_integer size) = 0;
 
        template<typename O_TYPE, typename... Args>
        void construct(O_TYPE* o_ptr, Args&&... args);
 
        template<typename O_TYPE>
        static void destroy(O_TYPE* o_ptr);
 
        virtual ~allocatorBase() = 0; 
    };
 
    template<typename TYPE>
    class allocator : public allocatorBase<TYPE, allocator> {
    public:
        using typename allocatorBase<TYPE, allocator>::propagate_on_container_copy_assignment;
        using typename allocatorBase<TYPE, allocator>::propagate_on_container_move_assignment;
        using typename allocatorBase<TYPE, allocator>::propagate_on_container_swap;
        using typename allocatorBase<TYPE, allocator>::propagate_on_container_merge;
 
        TYPE* allocate(u_integer size) override;
 
        void deallocate(TYPE* ptr, u_integer size) override;
    };
 
    template<typename TYPE>
    class objPoolAllocator final : public allocatorBase<TYPE, objPoolAllocator>
    {
        class freeChunk
        {
        public:
            freeChunk* next = nullptr; 
        };
 
        class allocatedChunks {
        public:
            void* chunks = nullptr;       
            allocatedChunks* next = nullptr; 
        };
 
        static constexpr u_integer CHUNK_SIZE =  sizeof(TYPE) > sizeof(freeChunk*) ? sizeof(TYPE) : sizeof(freeChunk*);
 
        u_integer size_class_count;      
        u_integer chunk_count_init;      
        u_integer* chunk_count;          
        freeChunk** free_list_head;      
        allocatedChunks* allocated_list_head; 
        u_integer* chunks_available;     
 
        void poolInit();
 
        [[nodiscard]] static constexpr u_integer getChunkIndex(u_integer size);
 
        void chunkAllocate(u_integer num_element, u_integer index);
 
        void release() noexcept;
 
    public:
        using typename allocatorBase<TYPE, objPoolAllocator>::propagate_on_container_copy_assignment;
        using propagate_on_container_move_assignment = std::true_type; 
        using propagate_on_container_swap = std::true_type; 
        using propagate_on_container_merge = std::true_type; 
 
        explicit objPoolAllocator(u_integer size_class_count = 8, u_integer count = 4);
 
        objPoolAllocator(const objPoolAllocator&) = delete; 
        objPoolAllocator& operator=(const objPoolAllocator&) = delete; 
 
        objPoolAllocator& operator+=(objPoolAllocator& other);
 
        objPoolAllocator(objPoolAllocator&& other) noexcept;
 
        objPoolAllocator& operator=(objPoolAllocator&& other) noexcept;
 
        void swap(objPoolAllocator& other) noexcept;
 
        TYPE* allocate(u_integer size) override;
 
        void deallocate(TYPE* ptr, u_integer size) override;
 
        ~objPoolAllocator() override;
    };
}
 
namespace std {
    template<typename TYPE>
    void swap(original::objPoolAllocator<TYPE>& lhs, original::objPoolAllocator<TYPE>& rhs) noexcept; // NOLINT
}
 
template<typename TYPE>
TYPE* original::allocators::malloc(const u_integer size) {
    if (size == 0) {
        return nullptr;
    }
 
    try {
        return static_cast<TYPE*>(operator new(size * sizeof(TYPE)));
    } catch (const std::bad_alloc&) {
        throw allocateError();
    }
}
 
template<typename TYPE>
void original::allocators::free(TYPE* ptr) {
    ::operator delete(ptr);
}
 
template <typename TYPE, template <typename> typename DERIVED>
constexpr original::allocatorBase<TYPE, DERIVED>::allocatorBase()
{
    staticError<allocateError, sizeof(TYPE) == 0 || std::is_void_v<TYPE>>::asserts();
}
 
template<typename TYPE, template <typename> typename DERIVED>
original::allocatorBase<TYPE, DERIVED>::~allocatorBase() = default;
 
template<typename TYPE, template <typename> typename DERIVED>
template<typename O_TYPE, typename... Args>
void original::allocatorBase<TYPE, DERIVED>::construct(O_TYPE *o_ptr, Args &&... args) {
    new (o_ptr) O_TYPE{std::forward<Args>(args)...};
}
 
template<typename TYPE, template <typename> typename DERIVED>
template<typename O_TYPE>
void original::allocatorBase<TYPE, DERIVED>::destroy(O_TYPE *o_ptr) {
    o_ptr->~O_TYPE();
}
 
template<typename TYPE>
TYPE* original::allocator<TYPE>::allocate(const u_integer size) {
    return allocators::malloc<TYPE>(size);
}
 
template<typename TYPE>
void original::allocator<TYPE>::deallocate(TYPE* ptr, u_integer) {
    allocators::free(ptr);
}
 
template<typename TYPE>
constexpr original::u_integer
original::objPoolAllocator<TYPE>::getChunkIndex(const u_integer size) {
    u_integer index = 0;
    while (static_cast<u_integer>(1) << index < size) {
        index += 1;
    }
    return index;
}
 
template<typename TYPE>
void original::objPoolAllocator<TYPE>::poolInit() {
    this->chunk_count = allocators::malloc<u_integer>(this->size_class_count);
    this->free_list_head = allocators::malloc<freeChunk*>(this->size_class_count);
    this->chunks_available = allocators::malloc<u_integer>(this->size_class_count);
    this->allocated_list_head = nullptr;
 
    for (u_integer i = 0; i < this->size_class_count; i++) {
        this->chunk_count[i] = this->chunk_count_init;
        this->free_list_head[i] = nullptr;
        this->chunks_available[i] = 0;
    }
}
 
template <typename TYPE>
void original::objPoolAllocator<TYPE>::chunkAllocate(const u_integer num_element, u_integer index)
{
    const u_integer block_size = (1 << index) * CHUNK_SIZE;
    auto new_free_chunk = allocators::malloc<byte>(num_element * block_size);
    auto new_allocated_chunk = allocators::malloc<allocatedChunks>(1);
 
    new_allocated_chunk->chunks = new_free_chunk;
    new_allocated_chunk->next = this->allocated_list_head;
    this->allocated_list_head = new_allocated_chunk;
 
    for (u_integer i = 0; i < num_element; i++)
    {
        auto cur_ptr = reinterpret_cast<freeChunk*>(new_free_chunk + i * block_size);
        cur_ptr->next = this->free_list_head[index];
        this->free_list_head[index] = cur_ptr;
    }
    this->chunks_available[index] += num_element;
    this->chunk_count[index] = this->chunk_count[index] + (this->chunk_count[index] >> 1);
}
 
template<typename TYPE>
void original::objPoolAllocator<TYPE>::release() noexcept {
    while (this->allocated_list_head) {
        auto next_chunk = this->allocated_list_head->next;
        allocators::free(this->allocated_list_head->chunks);
        allocators::free(this->allocated_list_head);
        this->allocated_list_head = next_chunk;
    }
 
    if (this->chunk_count) {
        allocators::free(this->chunk_count);
        this->chunk_count = nullptr;
    }
    if (this->free_list_head) {
        allocators::free(this->free_list_head);
        this->free_list_head = nullptr;
    }
    if (this->chunks_available) {
        allocators::free(this->chunks_available);
        this->chunks_available = nullptr;
    }
}
 
template <typename TYPE>
original::objPoolAllocator<TYPE>::objPoolAllocator(const u_integer size_class_count, const u_integer count)
    : size_class_count(size_class_count), chunk_count_init(count), chunk_count(nullptr),
      free_list_head(nullptr), allocated_list_head(nullptr), chunks_available(nullptr) {
    this->poolInit();
}
 
template<typename TYPE>
original::objPoolAllocator<TYPE>& original::objPoolAllocator<TYPE>::operator+=(objPoolAllocator& other) {
    if (this == &other)
        return *this;
 
    auto size_class_count_max = maximum(this->size_class_count, other.size_class_count);
    auto chunk_count_init_max = maximum(this->chunk_count_init, other.chunk_count_init);
    auto chunk_count_max = allocators::malloc<u_integer>(size_class_count_max);
    auto free_list_head_max = allocators::malloc<freeChunk*>(size_class_count_max);
    auto chunks_available_max = allocators::malloc<u_integer>(size_class_count_max);
 
    for (u_integer i = 0; i < size_class_count_max; i++) {
        if (i < this->size_class_count && i < other.size_class_count) {
            chunk_count_max[i] = maximum(this->chunk_count[i], other.chunk_count[i]);
            chunks_available_max[i] = this->chunks_available[i] + other.chunks_available[i];
            auto cur_list_head_i = other.free_list_head[i];
            if (cur_list_head_i) {
                while (cur_list_head_i->next) {
                    cur_list_head_i = cur_list_head_i->next;
                }
                cur_list_head_i->next = this->free_list_head[i];
                free_list_head_max[i] = other.free_list_head[i];
            }else {
                free_list_head_max[i] = this->free_list_head[i];
            }
        }else if (i < this->size_class_count) {
            chunk_count_max[i] = this->chunk_count[i];
            chunks_available_max[i] = this->chunks_available[i];
            free_list_head_max[i] = this->free_list_head[i];
        }else {
            chunk_count_max[i] = other.chunk_count[i];
            chunks_available_max[i] = other.chunks_available[i];
            free_list_head_max[i] = other.free_list_head[i];
        }
    }
 
    auto allocated_list_head_max = other.allocated_list_head;
    auto cur_allocated_list_head = allocated_list_head_max;
    if (cur_allocated_list_head) {
        while (cur_allocated_list_head->next) {
            cur_allocated_list_head = cur_allocated_list_head->next;
        }
        cur_allocated_list_head->next = this->allocated_list_head;
    }else {
        allocated_list_head_max = this->allocated_list_head;
    }
    this->allocated_list_head = nullptr;
    other.allocated_list_head = nullptr;
 
    this->release();
    other.release();
    other.poolInit();
 
    this->size_class_count = size_class_count_max;
    this->chunk_count_init = chunk_count_init_max;
    this->chunk_count = chunk_count_max;
    this->free_list_head = free_list_head_max;
    this->chunks_available = chunks_available_max;
    this->allocated_list_head = allocated_list_head_max;
 
    return *this;
}
 
template<typename TYPE>
original::objPoolAllocator<TYPE>::objPoolAllocator(objPoolAllocator&& other) noexcept : objPoolAllocator() {
    this->operator=(std::move(other));
}
 
template<typename TYPE>
original::objPoolAllocator<TYPE>& original::objPoolAllocator<TYPE>::operator=(objPoolAllocator&& other) noexcept {
    if (this == &other)
        return *this;
 
    this->release();
 
    this->size_class_count = other.size_class_count;
    this->chunk_count_init = other.chunk_count_init;
    this->chunk_count = other.chunk_count;
    this->free_list_head = other.free_list_head;
    this->allocated_list_head = other.allocated_list_head;
    this->chunks_available = other.chunks_available;
 
    other.poolInit();
    return *this;
}
 
template <typename TYPE>
void original::objPoolAllocator<TYPE>::swap(objPoolAllocator& other) noexcept
{
    if (this == &other)
        return;
 
    std::swap(this->size_class_count, other.size_class_count);
    std::swap(this->chunk_count_init, other.chunk_count_init);
    std::swap(this->chunk_count, other.chunk_count);
    std::swap(this->free_list_head, other.free_list_head);
    std::swap(this->allocated_list_head, other.allocated_list_head);
    std::swap(this->chunks_available, other.chunks_available);
}
 
template <typename TYPE>
TYPE* original::objPoolAllocator<TYPE>::allocate(const u_integer size)
{
    if (size == 0) {
        return nullptr;
    }
 
    u_integer index = getChunkIndex(size);
 
    if (index >= this->size_class_count) {
        return allocators::malloc<TYPE>(size);
    }
 
    if (!this->free_list_head[index] || this->chunks_available[index] * (static_cast<u_integer>(1) << index) < size) {
        this->chunkAllocate(maximum<u_integer>(1, this->chunk_count[index]), index);
    }
 
    auto cur_ptr = this->free_list_head[index];
    this->free_list_head[index] = this->free_list_head[index]->next;
    this->chunks_available[index] -= 1;
    return reinterpret_cast<TYPE*>(cur_ptr);
}
 
template <typename TYPE>
void original::objPoolAllocator<TYPE>::deallocate(TYPE* ptr, const u_integer size)
{
    if (size == 0) {
        return;
    }
 
    u_integer index = getChunkIndex(size);
 
    if (index >= this->size_class_count) {
        allocators::free(ptr);
        return;
    }
 
    auto p = reinterpret_cast<freeChunk*>(ptr);
    p->next = this->free_list_head[index];
    this->free_list_head[index] = p;
    this->chunks_available[index] += 1;
}
 
template<typename TYPE>
original::objPoolAllocator<TYPE>::~objPoolAllocator() {
    this->release();
}
 
template <typename TYPE>
void std::swap(original::objPoolAllocator<TYPE>& lhs, original::objPoolAllocator<TYPE>& rhs) noexcept // NOLINT
{
    lhs.swap(rhs);
}
 
#endif //ALLOCATOR_H