xor_list/StackAllocator.h

//
// Created by Ivan Arkhipov on 29.04.2018.
//

#ifndef XOR_LIST_STACKALLOCATOR_H
#define XOR_LIST_STACKALLOCATOR_H

#include <c++/cstddef>
#include <c++/new>
#include <memory.h>

template<typename T, size_t elements_in_block = 128256>
class StackAllocator {

public:
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    typedef T *pointer;
    typedef const T *const_pointer;
    typedef T &reference;
    typedef const T &const_reference;
    typedef T value_type;

    template<typename T1>
    struct rebind {
        typedef StackAllocator<T1> other;
    };

    StackAllocator() : last_block_(nullptr) {}


    StackAllocator(const StackAllocator &other) : last_block_(nullptr) {};

    template<class U>
    explicit StackAllocator(const StackAllocator<U> &other) : last_block_(nullptr) {};

    ~StackAllocator() {
        for (Block *block = last_block_; block != nullptr;) {
            Block *prev_block = block->prev_block_;
            delete block;
            block = prev_block;
        }
    }

    pointer allocate(size_type n, const void * = nullptr) {
        if (!last_block_ || last_block_->end_ + n >= last_block_->block_end_) {
            last_block_ = new Block(std::max(n, elements_in_block), last_block_);
        }
        pointer result = last_block_->end_;
        last_block_->end_ += n;
        return result;
    }

    void deallocate(pointer p, size_type n) {
        // does nothing
    }

    template<class U, class... Args>
    void construct(U *p, Args &&... args) {
        ::new((void *) p) U(std::forward<Args>(args)...);
    };

    template<class U>
    void destroy(U *p) {
        p->~U();
    }

private:
    struct Block {
    private:
        Block() {}

    public:
        explicit Block(int els_in_block = elements_in_block, Block *prev_block = nullptr) {
            begin_ = reinterpret_cast<pointer>(::operator new(sizeof(value_type) * els_in_block));
            end_ = begin_;
            block_end_ = begin_ + elements_in_block;
            prev_block_ = prev_block;
        }

        ~Block() {
            delete[] begin_;
        }

        pointer begin_;
        pointer end_;
        pointer block_end_;

        Block *prev_block_;
    };

    Block *last_block_;
};

#endif //XOR_LIST_STACKALLOCATOR_H