3
\$\begingroup\$

I am writing a custom allocator for my educational game engine project where I need to iterate through a collection of components(similar to Unity3D) every frame. There are game objects and every game object is composed of these components. Components are classes like Transform, Camera, Light, Mesh Renderer and so on which need to be updated every frame.

I also needed my own shared_ptr implementation, ptr_ref, as these components need to be destroyed even before the reference count reaches zero and this was not possible with std::shared_ptr. ptr_ref works very similar to std::shared_ptr on the outside, with the exception that all instances pointing to the same memory can be invalidated(their underlying data set to nullptr).

ptr_ref.h

#pragma once
#include <functional>

template <typename T>
class ptr_ref
{
    using Deleter = std::function<void( ptr_ref<T>& )>;

public:

    ptr_ref( )
        : refCount_( nullptr ), data_( nullptr ), deleter_( nullptr )
    {
    }

    ptr_ref( T* ptr, const Deleter& deleter = nullptr )
        : refCount_( new size_t( 1 ) ), data_( new T* ( ptr ) ), deleter_( deleter )
    {
    }

    ptr_ref( const ptr_ref& other )
        : refCount_( other.refCount_ ), data_( other.data_ ), deleter_( other.deleter_ )
    {
        ++( *refCount_ );
    }

    ptr_ref( ptr_ref&& other ) noexcept
        : refCount_( other.refCount_ ), data_( other.data_ ), deleter_( other.deleter_ )
    {
        other.data_ = nullptr;
        other.refCount_ = nullptr;
        other.deleter_ = nullptr;
    }

    ptr_ref& operator=( const ptr_ref& other )
    {
        this->refCount_ = other.refCount_;
        this->data_ = other.data_;
        this->deleter_ = other.deleter_;

        ++( *refCount_ );

        return *this;
    }

    ptr_ref& operator=( ptr_ref&& other ) noexcept
    {
        this->refCount_ = other.refCount_;
        this->data_ = other.data_;
        this->deleter_ = other.deleter_;

        other.data_ = nullptr;
        other.refCount_ = nullptr;
        other.deleter_ = nullptr;

        return *this;
    }

    ~ptr_ref( )
    {
        if (data_)
        {
            --( *refCount_ );

            if (*refCount_ <= 0)
            {
                if (*data_)
                {
                    if (deleter_)
                        deleter_( *this );
                    else
                        delete ( *data_ );
                }

                delete refCount_;
                delete data_;

                data_ = nullptr;
                refCount_ = nullptr;
            }
        }
    }

    //decreases the refcount by 1
    void reset( )
    {
        if (data_)
        {
            --( *refCount_ );

            if (*refCount_ <= 0)
            {

                if (*data_)
                {
                    if (deleter_)
                        deleter_( *this );
                    else
                        delete ( *data_ );
                }

                delete refCount_;
                delete data_;
            }

            data_ = nullptr;
            refCount_ = nullptr;
        }
    }

    T* operator->( ) const
    {
        return ( *data_ );
    }

    T operator*( ) const
    {
        return *( *data_ );
    }

    bool operator==( const ptr_ref& other ) const
    {
        return ( *data_ ) == *( other.data_ );
    }

    bool operator!=( const ptr_ref& other ) const
    {
        return ( *data_ ) != *( other.data_ );
    }

    template <typename... params >
    static ptr_ref<T> make( params&& ...args )
    {
        ptr_ref<T> ref;

        ref.refCount_ = new size_t( 1 );
        ref.data_ = new T * ( new T( std::forward<params>( args )... ) );

        return ref;
    }

    inline T* get( ) const
    {
        return ( *data_ );
    }

    inline T** get_address( ) const
    {
        return data_;
    }

    inline size_t ref_count( ) const
    {
        return ( *refCount_ );
    }

    void set( T* ptr )
    {
        *data_ = ptr;
    }

protected:
    size_t* refCount_;
    T** data_;
    Deleter deleter_;
};

GrowingListAllocator.h

#pragma once
#include <vector>
#include <unordered_map>
#include <set>
#include "../utils/ptr_ref.h"

template <typename T, size_t BLOCK_SIZE>
struct Chunk
{
public:

    explicit Chunk( size_t priority )
        : priority_( priority ), buffer_( nullptr ), size_( 0 )
    {
        buffer_ = reinterpret_cast<T*>( malloc( BLOCK_SIZE * sizeof( T ) ) );
        addresses_.resize( BLOCK_SIZE, nullptr );
    }

    ~Chunk( )
    {
        for (size_t i = 0; i < size_; ++i)
        {
            ( buffer_ + i )->~T( );
        }

        addresses_.clear( );
        free( buffer_ );
        buffer_ = nullptr;
    }

    inline bool is_full( ) const
    {
        return  size_ == BLOCK_SIZE;
    }

    inline bool size( ) const
    {
        return size_;
    }

    inline size_t priority( ) const
    {
        return priority_;
    }

    T* allocate( )
    {
        T* ptr = ( buffer_ + size_ );
        ++size_;
        return ptr;
    }

    T* get_pointer_at( size_t index )
    {
        return ( buffer_ + index );
    }

    void set_address( T** ptr )
    {
        addresses_[ size_ - 1 ] = ptr;
    }

    void release( T* ptr, Chunk<T, BLOCK_SIZE>* lastChunk, const std::function<void( T** )>& OnSwap )
    {
        ptr->~T( );

        void* src = reinterpret_cast<void*>( lastChunk->buffer_ + ( lastChunk->size_ - 1 ) );
        void* current = reinterpret_cast<void*>( ptr );
        if (src != current)
        {
            memcpy( current, src, sizeof( T ) );

            *( lastChunk->addresses_[ lastChunk->size_ - 1 ] ) = reinterpret_cast<T*>( current );
            OnSwap( lastChunk->addresses_[ lastChunk->size_ - 1 ] );
        }
        --lastChunk->size_;
    }

private:
    T* buffer_;
    std::vector<T**> addresses_;
    size_t size_, priority_;
};

template <typename T, size_t BLOCK_SIZE>
class GrowingBlockAllocator
{
    using TChunk = Chunk<T, BLOCK_SIZE>;
public:
    GrowingBlockAllocator( )
        :size_( 0 )
    {

    }

    ~GrowingBlockAllocator( )
    {
        freeChunks_.clear( );
        for (TChunk* chunk : chunks_)
        {
            delete chunk;
        }
        chunks_.clear( );
        memoryMap_.clear( );
    }

    template <typename... params>
    ptr_ref<T> instantiate( params&& ...args )
    {
        if (freeChunks_.empty( ))
        {
            TChunk* chunk = new TChunk( chunks_.size( ) );
            chunks_.push_back( chunk );
            freeChunks_.insert( chunk );
        }

        TChunk* chunk = *( freeChunks_.begin( ) );
        T* ptr = chunk->allocate( );

        //If there is no more memory in the chunk, remove it from the free list
        if (chunk->is_full( ))
        {
            freeChunks_.erase( chunk );
        }

        ptr_ref<T> ref( new( ptr ) T( std::forward<params>( args )... ), [ this ] ( ptr_ref<T>& ref )
        {
            this->release( ref );
        } );

        chunk->set_address( ref.get_address( ) );
        memoryMap_[ ref.get_address( ) ] = chunk;

        ++size_;
        return ref;
    }

    void release( ptr_ref<T>& ref )
    {
        TChunk* chunk = memoryMap_[ ref.get_address( ) ];
        TChunk* lastChunk = nullptr;

        for (auto rit = chunks_.rbegin( ); rit != chunks_.rend( ); ++rit)
        {
            lastChunk = *( rit );
            size_t size = lastChunk->size( );
            if (size > 0)
            {
                break;
            }
        }

        chunk->release( ref.get( ), lastChunk, [ & ] ( T** ptr )
        {
            this->memoryMap_[ ptr ] = chunk;
        } );

        if (!lastChunk->is_full( ))
        {
            freeChunks_.insert( lastChunk );
        }

        if (chunk->is_full( ))
        {
            freeChunks_.erase( chunk );
        }

        ref.set( nullptr );
        --size_;
    }

    inline size_t size( ) const
    {
        return size_;
    }

    T* operator[]( size_t i )
    {
        size_t ptr_index = i % BLOCK_SIZE;
        size_t chunk_index = ( i - ptr_index ) / BLOCK_SIZE;

        return chunks_[ chunk_index ]->get_pointer_at( ptr_index );
    }

private:
    std::vector<TChunk*> chunks_;
    std::unordered_map<T**, TChunk*> memoryMap_;

    struct Comparator
    {
    public:
        inline bool operator()( TChunk* lhs, TChunk* rhs ) const
        {
            return lhs->priority( ) < rhs->priority( );
        }
    };

    std::set<TChunk*, Comparator> freeChunks_;
    size_t size_;
};

Usage(main.cpp)

#include <iostream>
#include "allocators/GrowingBlockAllocator.h"

struct Data
{
public:
    int32_t* Marks;
    int32_t id;

    Data( int32_t id_ ) :id( id_ )
    {
        Marks = new int32_t[ 5 ];
        std::cout << "Data_" << id << "is constructed" << std::endl;
    }

    ~Data( )
    {
        delete[ ] Marks;
        std::cout << "Data_" << id << "is destroyed" << std::endl;
    }
};

struct Pack
{
public:
    Pack( int32_t v )
        :value( v )
    {
        std::cout << "Pack_" << value << "is constructed at " << (void*) this << std::endl;
        data = new Data( value );
    }

    ~Pack( )
    {
        delete data;
        std::cout << "Pack_" << value << "is destroyed at " << (void*) this << std::endl;
    }

    Data* data;
    int32_t value;
};

int main( )
{
    GrowingBlockAllocator<Pack, 3> allocator;
    std::vector< ptr_ref<Pack>> packs;

    std::cout << '\n' << "**************************" << '\n' << std::endl;
    for (size_t i = 0; i < 7; i++)
    {
        packs.push_back( allocator.instantiate( static_cast<int32_t>( 1 + i ) ) );
    }

    std::cout << '\n' << "**************************" << '\n' << std::endl;
    allocator.release( packs[ 1 ] );
    allocator.release( packs[ 4 ] );

    std::cout << "Is packs[4] null? " << ( packs[ 4 ] == nullptr ) << std::endl;
    packs[ 4 ] = allocator.instantiate( 8 );
    std::cout << "Is packs[4] null? " << ( packs[ 4 ] == nullptr ) << std::endl;

    std::cout << '\n' << "**************************" << '\n' << std::endl;

    std::cout << "Elements in Memery Pool :" << std::endl;
    for (size_t i = 0; i < allocator.size( ); i++)
    {
        std::cout << "Data_" << allocator[ i ]->value << std::endl;
    }
    std::cout << '\n' << "**************************" << '\n' << std::endl;

    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ "these components need to be destroyed even before the reference count reaches zero" can you explain why? Does std::weak_ptr solve the problem? Why not follow the interface of std::allocator? \$\endgroup\$ – sudo rm -rf slash Apr 28 at 1:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.