tail_list.cpp

#include <type_traits>
#include <memory>
#include <vector>

#include <iostream>

namespace buffer
{

template <class Type>
struct TAbstract
{
    virtual Type* allocate() = 0;   
};

template <class Traits>
class TStack : public Traits::Abstract
{
    using Memory = typename Traits::Memory;
    using Type   = typename Traits::Type;
    
    static constexpr auto head = Traits::head;
    static constexpr auto tail = Traits::tail;
    
public:

    TStack() :
        _head{head(&_memory)},
        _tail{tail(&_memory)}
    {}
    
    Type* allocate() override
    {
        if (_head == _tail)
        {
            return nullptr;    
        }
        
        return _head++;
    }
    
    void clean()
    {
        auto temp = head(&_memory);
        
        while (temp != _head)
        {
            temp->~Type();
            temp++;
        }
        
        _head = head(&_memory);
    }
    
    ~TStack()
    {
        clean();    
    }
    
private:

          Type*       _head;
    const Type* const _tail;
    
    Memory _memory;
};

namespace stack
{

template <class StackType, std::size_t SIZE>
struct TTraits
{
    using Type = StackType;
    
    using Abstract = TAbstract<Type>;
    
    using Memory = std::aligned_storage_t<sizeof(Type) * SIZE, alignof(Type)>;
    
    static constexpr auto head = [](Memory* memoryPtr) { return reinterpret_cast<Type*>(memoryPtr)        ; };
    static constexpr auto tail = [](Memory* memoryPtr) { return reinterpret_cast<Type*>(memoryPtr) + SIZE ; }; 
};

} // namespace stack

template <class Type, std::size_t SIZE>
using TMakeStack = TStack<stack::TTraits<Type, SIZE>>;

template <class Traits>
class THeap : public Traits::Abstract
{
    using Type = typename Traits::Type;

public:

    THeap(const std::size_t size) :
        _memory{reinterpret_cast<Type*>(new uint8_t[sizeof(Type) * size])}
    {
        _head = _memory;
        _tail = _memory + size;
    }
    
    Type* allocate() override
    {
        if (_head == _tail)
        {
            return nullptr;    
        }
        
        return _head++;
    }
    
    void clean()
    {
        auto temp = _memory;
        
        while (temp != _head)
        {
            temp->~Type();
            temp++;
        }
        
        _head = _memory;
    }
    
    ~THeap()
    {
        clean();
        delete[] _memory;
        _memory = nullptr;
    }
    
private:

          Type* _head;
    const Type* _tail;
          Type* _memory;
};

namespace heap
{

template <class HeapType>
struct TTraits
{
    using Type     = HeapType;
    using Abstract = TAbstract<Type>;
};

} // namespace heap

template <class Type>
using TMakeHeap = THeap<heap::TTraits<Type>>;

} // namespace buffer

template <class Traits>
class TStableAddressAmortizedAllocator
{
    using Type = typename Traits::Type;
    
    using AbstractBuffer = typename Traits::AbstractBuffer; 
    using    StackBuffer = typename Traits::   StackBuffer;
    using     HeapBuffer = typename Traits::    HeapBuffer;
    
    static constexpr std::size_t SIZE = Traits::SIZE;
    
public:

    TStableAddressAmortizedAllocator() :
        _bufferPtr{&_stackBuffer},
        _size{SIZE}
    {}
    
    Type* allocate()
    {
        if (!_recycleds.empty())
        {
            Type* const ptr = _recycleds.back();
            _recycleds.pop_back();
            return ptr;
        }
        
        Type* const ptr = _bufferPtr->allocate();
        
        if (!ptr)
        {
            _heapBuffers.emplace_back(std::make_unique<HeapBuffer>(_size <<= 1));
            _bufferPtr = _heapBuffers.back().get();
        
            return _heapBuffers.back()->allocate();
        }
        
        return ptr;
    }
    
    void recycle(Type* ptr)
    {
        _recycleds.emplace_back(ptr);    
    }
    
    void clean()
    {
        _stackBuffer.clean();
        
        for (auto& heapBuffer : _heapBuffers)
        {
            heapBuffer.clean();    
        }
    }
    
    void freeMemory()
    {
        _stackBuffer.clean();
        _heapBuffers.clear();
        
        _bufferPtr = &_stackBuffer;
    }
    
private:

    AbstractBuffer*                          _bufferPtr;
    StackBuffer                              _stackBuffer;
    std::vector<Type*>                       _recycleds;
    std::vector<std::unique_ptr<HeapBuffer>> _heapBuffers;
    
    std::size_t _size;
};

namespace stable_address_amortized_allocator
{

template <class TraitsType, std::size_t TRAITS_SIZE>
struct TTraits
{    
    static constexpr std::size_t SIZE = TRAITS_SIZE;

    using Type = TraitsType;
    
    using    StackBuffer = buffer::TMakeStack <Type, SIZE>;
    using AbstractBuffer = buffer::TAbstract  <Type>;
    using     HeapBuffer = buffer::TMakeHeap  <Type>;
};

} // namespace stable_address_amortized_allocator

template <class Type, std::size_t SIZE>
using TMakeStableAddressAmortizedAllocator = TStableAddressAmortizedAllocator<stable_address_amortized_allocator::TTraits<Type, SIZE>>;

template <class Traits>
class TStableAddressAmortizedFactory
{
    using Type      = typename Traits::Type;
    using Allocator = typename Traits::Allocator;

public:

    template <class... Args>
    Type& make(Args&&... args)
    {
        return *(new(static_cast<void *>(_allocator.allocate())) Type(std::forward<Args>(args)...));
    }
    
    void recycle(Type& value)
    {
        value.~Type();
        _allocator.recycle(&value);    
    }
    
private:

    Allocator _allocator;
};

namespace stable_address_amortized_factory
{

template <class TraitsType, std::size_t SIZE>
struct TTraits
{
    using Type = TraitsType;
    
    using Allocator = TMakeStableAddressAmortizedAllocator<Type, SIZE>;
};

} // namespace stable_address_amortized_factory

template <class Type, std::size_t SIZE>
using TMakeStableAddressAmortizedFactory = TStableAddressAmortizedFactory<stable_address_amortized_factory::TTraits<Type, SIZE>>;

template <class Type>
struct TTailCell
{
    template <class... Args>
    TTailCell(TTailCell* tail, Args&&... args) :
        value{args...},
        prev{tail}
    {}

    Type value;
  
    TTailCell* prev = nullptr;
    TTailCell* next = nullptr;
};

template <class Traits>
class TTailList
{
    using Cell    = typename Traits::Cell;
    
public:

    using Factory = typename Traits::Factory;

    template <class... Args>
    void emplace_back(Args&&... args)
    {
        _tail = &(_factory.make(_tail, args...));
    }
    
    void pop_back()
    {
        Cell* const prev = _tail->prev;
        _factory.recycle(*_tail);
        _tail = prev;
    }
    
    Cell& back()
    {
        return *_tail; // may segfault if wrongly called    
    }
    
    void erase(Cell& cell)
    {
        Cell* prev = cell.prev;
        Cell* next = cell.next;
        
        if (prev)
        {
            prev->next = next;
        }
        
        if (next)
        {
            next->prev = prev;    
        }
        
        _factory.recycle(cell);
    }

private:

    Cell* _tail = nullptr;
    
    static Factory _factory;
};

namespace tail_list
{

template <class TraitsType, std::size_t SIZE>
struct TTraits
{
    using Type = TraitsType;
    
    using Cell = TTailCell<Type>;
    
    using Factory = TMakeStableAddressAmortizedFactory<Cell, SIZE>;
};

} // namespace tail_list

template <class Type, std::size_t SIZE>
using TMakeTailList = TTailList<tail_list::TTraits<Type, SIZE>>;

/*template <class Type, std::size_t SIZE>
typename TTailList<tail_list::TTraits<Type, SIZE>>::Factory TTailList<tail_list::TTraits<Type, SIZE>>::_factory;*/

struct S
{
    S(int _a, int _b, int _c, int _d) : a{_a}, b{_b}, c{_c}, d{_d} {} 
    
    int a;
    int b;
    int c;
    int d;
};

template <>
typename TTailList<tail_list::TTraits<S, 1>>::Factory TTailList<tail_list::TTraits<S, 1>>::_factory{};

int main()
{
    using TailListOfInt = TMakeTailList<S, 1>;
    
    TailListOfInt tailListOfInt;
    
    tailListOfInt.emplace_back(1,2,3,4);
    
    auto&& fourtyTwo = tailListOfInt.back();
    
    tailListOfInt.emplace_back(5,6,7,8);
    
    auto&& fourtyThree = tailListOfInt.back();
    
    tailListOfInt.emplace_back(5,6,7,8);
    
    auto&& fourtyFour = tailListOfInt.back();
    
    std::cout << &(fourtyTwo.value) << std::endl;
    
    std::cout << &(fourtyThree.value) << std::endl;
    
    std::cout << &(fourtyFour.value) << std::endl;
    
    tailListOfInt.erase(fourtyThree);
    
    return 0;
}