table.cpp

// http://coliru.stacked-crooked.com/a/f567a9698865eb15

#include <type_traits>
#include <utility>
#include <cstdint>
#include <memory>

#include <iostream>

/********************************
 *         LIKELYWOOD           *
 ********************************/

#if defined __GNUC__ || \
    defined __llvm__
    #define ROBIN_LIKELY(x) __builtin_expect ((x), 1)
    #define ROBIN_UNLIKELY(x) __builtin_expect ((x), 0)
#else
    #define ROBIN_LIKELY(x) (x)
    #define ROBIN_UNLIKELY(x) (x)
#endif

/**************************
 *         VIEW           *
 **************************/

namespace buffer
{ 

template <std::size_t VIEW_SIZEOF>
struct TView
{
    static constexpr std::size_t SIZEOF = VIEW_SIZEOF;

    uint8_t* const    data;
    const std::size_t size;
};

} // namespace buffer

/****************************
 *         BUFFER           *
 ****************************/

namespace buffer
{

template <class AbstractTraits>
class TAbstract
{
    using Heap = typename AbstractTraits::Heap;
    using View = typename AbstractTraits::View;
    
public:

    virtual                 View  makeView()       = 0;
    virtual std::unique_ptr<Heap> makeNext() const = 0;
    virtual std::unique_ptr<Heap> makePrev() const = 0;

    virtual ~TAbstract() {}
};

template <class>
class THeap;

namespace heap
{

template <std::size_t, std::size_t>
struct TTraits;

} // namespace heap

namespace abstract
{

template <std::size_t SIZEOF,
          std::size_t ALIGNOF>
struct TTraits
{    
    using HeapTraits = heap::TTraits<SIZEOF, ALIGNOF>;
    
    using Heap = THeap<HeapTraits>;
    
    using View = TView<SIZEOF>;
};

template <class Type>
using TMakeTraitsFromType = TTraits<sizeof  (Type),
                                    alignof (Type)>;

} // namespace abstract

} // namespace buffer

/**************************
 *         HEAP           *
 **************************/

namespace buffer
{

template <class HeapTraits>
class THeap : public TAbstract<typename HeapTraits::AbstractTraits>
{    
    using Bucket = typename HeapTraits::Bucket;
    using Heap   = typename HeapTraits::Heap;
    using View   = typename HeapTraits::View;
    
public:

    THeap(const std::size_t size) :
        _data{new Bucket[size]},
        _size{size}
    {}
    
    View makeView() override
    {
        return {reinterpret_cast<uint8_t*>(_data), _size};   
    }
    
    std::unique_ptr<Heap> makeNext() const override
    {
        return std::make_unique<Heap>(((_size - 1) << 1) + 1);
    }
    
    std::unique_ptr<Heap> makePrev() const override
    {
        return std::make_unique<Heap>(((_size - 1) >> 2) + 1);
    }
    
    ~THeap() override
    {
        delete[] _data;
    }

private:

    Bucket* const    _data;
    const std::size_t _size;
};

namespace heap
{

template <std::size_t SIZEOF,
          std::size_t ALIGNOF>
struct TTraits
{    
    using AbstractTraits =      abstract::TTraits <SIZEOF, ALIGNOF>;
    using Bucket         = std::aligned_storage_t <SIZEOF, ALIGNOF>;
    
    using Heap = THeap<TTraits<SIZEOF, ALIGNOF>>;
    
    using View = TView<SIZEOF>;
};

template <class Type>
using TMakeTraitsFromType = TTraits<sizeof  (Type),
                                    alignof (Type)>;
} // namespace heap

} // namespace buffer

/***************************
 *         STACK           *
 ***************************/

namespace buffer
{

template <class StackTraits>
class TStack : public TAbstract<typename StackTraits::AbstractTraits>
{
    static constexpr std::size_t SIZE = StackTraits::SIZE;
    
    using Bucket = typename StackTraits::Bucket;
    using Heap   = typename StackTraits::Heap;
    using View   = typename StackTraits::View;

public:

    View makeView() override
    {
        return {reinterpret_cast<uint8_t*>(_array.data()), SIZE + 1};    
    }
    
    std::unique_ptr<Heap> makeNext() const override
    {
        return std::make_unique<Heap>((SIZE << 1) + 1);
    }
    
    std::unique_ptr<Heap> makePrev() const override
    {
        return {};
    }

private:

    std::array<Bucket, SIZE + 1> _array;
};

namespace stack
{

template <std::size_t STACK_SIZE,
          std::size_t STACK_SIZEOF,
          std::size_t STACK_ALIGNOF>
struct TTraits
{   
    static constexpr std::size_t SIZE    = STACK_SIZE;
    static constexpr std::size_t SIZEOF  = STACK_SIZEOF;
    static constexpr std::size_t ALIGNOF = STACK_ALIGNOF;
    
    using AbstractTraits =      abstract::TTraits <SIZEOF, ALIGNOF>;
    using HeapTraits     =          heap::TTraits <SIZEOF, ALIGNOF>;
    using Bucket         = std::aligned_storage_t <SIZEOF, ALIGNOF>;
    
    using Heap = THeap<HeapTraits>;
    
    using View = TView<SIZEOF>;
};

template <class Type, std::size_t SIZE>
using TMakeTraitsFromType = TTraits<SIZE,
                                    sizeof  (Type),
                                    alignof (Type)>;
} // namespace stack

} // namespace buffer

/*****************************
 *         MANAGER           *
 *****************************/

namespace buffer
{

template <class ManagerTraits>
class TManager
{
    static constexpr std::size_t SIZEOF  = ManagerTraits::SIZEOF;
                                     
    using Abstract = typename ManagerTraits::Abstract;
    using Stack    = typename ManagerTraits::Stack;
    using Heap     = typename ManagerTraits::Heap;
    using View     = typename ManagerTraits::View;

public:

    TManager() : _bufferPtr{&_stack} {}
    
    View makeView()
    {
        return  _bufferPtr->makeView();   
    }
    
    View makeNextView()
    {
        _tempPtr = std::move(_bufferPtr->makeNext());
        return _tempPtr->makeView();
    }
    
    View makePrevView()
    {
        _tempPtr = std::move(_bufferPtr->makePrev());
        return _tempPtr->makeView();
    }
    
    void swapBuffers()
    {
        _heapPtr = std::move(_tempPtr);
        _bufferPtr = _heapPtr.get();
    }
    
private:

    Abstract*             _bufferPtr;
    Stack                 _stack;
    std::unique_ptr<Heap> _heapPtr;
    std::unique_ptr<Heap> _tempPtr;
};

namespace manager
{

template <std::size_t MANAGER_SIZE,
          std::size_t MANAGER_SIZEOF,
          std::size_t MANAGER_ALIGNOF>
struct TTraits
{
    static constexpr std::size_t SIZE    = MANAGER_SIZE;
    static constexpr std::size_t SIZEOF  = MANAGER_SIZEOF;
    static constexpr std::size_t ALIGNOF = MANAGER_ALIGNOF; 

    using StackTraits    = stack::TTraits    <SIZE,
                                              SIZEOF,
                                              ALIGNOF>;
                                       
    using HeapTraits     = heap::TTraits     <SIZEOF,
                                              ALIGNOF>;
                                     
    using AbstractTraits = abstract::TTraits <SIZEOF,
                                              ALIGNOF>;
                                     
    using Abstract = TAbstract <AbstractTraits>;
    using Stack    = TStack    <StackTraits>;
    using Heap     = THeap     <HeapTraits>;
    
    using View = TView<SIZEOF>;
};

template <class Type, std::size_t SIZE>
using TMakeTraitsFromType = TTraits<SIZE,
                                    sizeof  (Type),
                                    alignof (Type)>;

template <class Type, std::size_t SIZE>
using TMakeFromType = TManager<TMakeTraitsFromType<Type, SIZE>>;

} // namespace manager

} // namespace buffer

/*******************************************
 *         DEFAULT_CONSTRUCTIBLE           *
 *******************************************/

template <class Type>
union DefaultConstructible
{

public:

    DefaultConstructible() : _dummy{} {}
    
    template<class... Args>
    void construct(Args&&... args)
    {
        new (static_cast<void*>(&_value)) Type(std::forward<Args>(args)...);
    }

    void destroy()
    {
        _value.~Type();
    }

          Type&  value()       &  { return           _value  ; }
          Type&& value()       && { return std::move(_value) ; }
    const Type&  value() const &  { return           _value  ; }

private:

    uint8_t _dummy;
    Type    _value;
};

/****************************
 *         BUCKET           *
 ****************************/

namespace table
{

template <typename Type>
class TBucket
{

public:

    enum
    {
        EMPTY  = 0,
        FILLED = 1
    };

    TBucket() : _dib{EMPTY} {}

    void markEmpty () { _dib = EMPTY ; }
    void markFilled() { _dib = FILLED; }

    bool isEmpty () const { return _dib == EMPTY; }
    bool isFilled() const { return _dib != EMPTY; }

    template<class... Args>
    void fill(uint8_t dib, Args&&... args)
    {
        _dib = dib;
        _val.construct(args...);
    }

    uint8_t dib() const { return _dib; }

    ~TBucket()
    {
        if (!isEmpty())
        {
            _val.destroy();
        }
    }

          Type&  value()       &  {              return _val.value(); }
          Type&& value()       && { markEmpty(); return _val.value(); }
    const Type&  value() const &  {              return _val.value(); }

private:

    uint8_t                    _dib;
    DefaultConstructible<Type> _val;
};

} // namespace table

/******************************
 *         ITERATOR           *
 ******************************/

template <class>
class TTable;

namespace table
{

template <class>
class TIterator;

template <class IteratorTraits>
bool operator==(const TIterator<IteratorTraits>& lhs,
                const TIterator<IteratorTraits>& rhs);

template <class IteratorTraits>
bool operator!=(const TIterator<IteratorTraits>& lhs,
                const TIterator<IteratorTraits>& rhs);

namespace iterator
{

template <class TableTraits>
struct TTraits
{
    using Table  = TTable<TableTraits>;
    using Type   = typename TableTraits::Type;
    using Bucket = typename TableTraits::Bucket;

    using Traits = TTraits<TableTraits>;

    using Iterator = TIterator<Traits>;
};

template <class TableTraits>
using TMakeFromTraits = TIterator<TTraits<TableTraits>>;

} // namespace iterator

template <class IteratorTraits>
class TIterator : std::iterator<std::forward_iterator_tag,
                                typename IteratorTraits::Type>
{
    using Bucket   = typename IteratorTraits::Bucket;
    using Table    = typename IteratorTraits::Table;
    using Type     = typename IteratorTraits::Type;
    using Iterator = typename IteratorTraits::Iterator;

    friend Table;

    friend bool operator==<IteratorTraits>(const Iterator& lhs,
                                           const Iterator& rhs);

    friend bool operator!=<IteratorTraits>(const Iterator& lhs,
                                           const Iterator& rhs);
public:

    TIterator(Bucket* const bucketPtr) :
        _bucketPtr{bucketPtr}
    {}

    TIterator(const Iterator& toCopy) :
        _bucketPtr{toCopy._bucketPtr}
    {}

    void operator=(const Iterator& toCopy)
    {
        _bucketPtr = toCopy._bucketPtr;
    }

    const Type& operator*() const
    {
        return _bucketPtr->value();
    }

    Iterator& operator++()
    {
        do
        {
            _bucketPtr++;

        } while (_bucketPtr->isEmpty());
        // we skipped the empty buckets ! Hoora !
        return *this;
    }

    Iterator operator++(int)
    {
        Iterator tmp{*this};
        operator++();
        return tmp;
    }

private:

    Bucket* _bucketPtr;
};

template <class IteratorTraits>
bool operator==(const TIterator<IteratorTraits>& lhs,
                const TIterator<IteratorTraits>& rhs)
{
    return lhs._bucketPtr == rhs._bucketPtr;
}

template <class IteratorTraits>
bool operator!=(const TIterator<IteratorTraits>& lhs,
                const TIterator<IteratorTraits>& rhs)
{
    return lhs._bucketPtr != rhs._bucketPtr;
}

} // namespace table

/***************************
 *         TABLE           *
 ***************************/

template <class TableTraits>
class TTable
{
    using Type          = typename TableTraits::Type;
    using Bucket        = typename TableTraits::Bucket;
    using Hasher        = typename TableTraits::Hasher;
    using Comparator    = typename TableTraits::Comparator;
    using BufferManager = typename TableTraits::BufferManager;

    static constexpr std::size_t MASK              = TableTraits::MASK;
    static constexpr std::size_t STACK_SIZE        = TableTraits::STACK_SIZE;
    static constexpr std::size_t LOAD_FACTOR_LEVEL = TableTraits::LOAD_FACTOR_LEVEL;

public:

    using       iterator = typename TableTraits::     Iterator;
    using const_iterator = typename TableTraits::ConstIterator;

    TTable() :
        _mask{MASK},
        _size{0}
    {
        const auto& bufferView = _bufferManager.makeView();

        _buckets  = reinterpret_cast<Bucket*>(bufferView.data);
        _capacity =                           bufferView.size - 1;

        init();
    }

    void rehashPrev()
    {
        const Bucket* const oldBuckets  = _buckets;
        const std::size_t   oldCapacity = _capacity;

        const auto& bufferPrevView = _bufferManager.makePrevView();

        _buckets = reinterpret_cast<Bucket*>(bufferPrevView.data);

        _capacity >>= 2;
        _mask = _capacity - 1;
        _size = 0;

        init();

        for (std::size_t bucketIndex = 0; 
                         bucketIndex < oldCapacity;
                         bucketIndex++)
        {
            const auto& oldBucket = oldBuckets[bucketIndex];
            
            if (oldBucket.isFilled())
            {
                emplace(oldBucket.value());
                oldBucket.~Bucket();
            }
        }

        oldBuckets[oldCapacity].~Bucket();

        _bufferManager.swapBuffers();
    }
    
    void rehashNext()
    {
        const Bucket* const oldBuckets  = _buckets;
        const std::size_t   oldCapacity = _capacity;

        const auto& bufferNextView = _bufferManager.makeNextView();

        _buckets = reinterpret_cast<Bucket*>(bufferNextView.data);

        _capacity <<= 1;
        _mask = _capacity - 1;
        _size = 0;

        init();

        for (std::size_t bucketIndex = 0; 
                         bucketIndex < oldCapacity;
                         bucketIndex++)
        {
            const auto& oldBucket = oldBuckets[bucketIndex];
            
            if (oldBucket.isFilled())
            {
                emplace(oldBucket.value());
                oldBucket.~Bucket();
            }
        }

        oldBuckets[oldCapacity].~Bucket();

        _bufferManager.swapBuffers();
    }

    template <class... Args>
    void emplace(Args&&... args)
    {
        Type t{args...};

        REDO: // goto label

        const std::size_t hash = _hasher(t);

        uint8_t dib = Bucket::FILLED;

        Bucket* head = _buckets + ((hash + dib) & _mask);

        // Skip filled buckets with larger dib
        while (dib < head->dib())
        {
            BUCKET_SCAN: // goto label

            ++dib;
            head = (++head == _buckets + _capacity) ? _buckets : head;

            if (ROBIN_UNLIKELY(!dib))
            {
                rehashNext();
                goto REDO;
            }
        }

        if (head->isEmpty())
        {
            if (ROBIN_UNLIKELY(++_size << LOAD_FACTOR_LEVEL > (_capacity << LOAD_FACTOR_LEVEL) - _capacity))
            {
                rehashNext();
                goto REDO;
            }

            head->fill(dib, std::move(t));

            if (head < _beginPtr)
            {
                _beginPtr = head;
            }
        }   
        else
        {
            if (dib != head->dib())
            {
                // Copy the value of the found bucket and insert our own
                Type tTmp = std::move(head->value());
                const uint8_t dibTmp = head->dib();

                head->fill(dib, std::move(t));

                t = std::move(tTmp);
                dib = dibTmp;
                goto BUCKET_SCAN;
            }
            else if (_comparator(t, head->value()))
            {
                return;
            }

            goto BUCKET_SCAN;
        }
    }

    void erase(const Type& t)
    {
        uint8_t dib = Bucket::FILLED;

        Bucket* prec = _buckets + ((_hasher(t) + dib) & _mask);

        // Skip buckets with lower dib or different value
        while (dib < prec->dib() || (dib == prec->dib() && !_comparator(t, prec->value())))
        {
            dib++;
            prec = (++prec == _buckets + _capacity) ? _buckets : prec;
        }

        if (dib == prec->dib())
        {
            shiftBuckets(prec);
        }
    }

    std::size_t size() const
    {
        return _size;
    }

    bool empty() const
    {
        return _size == 0;
    }

    iterator begin()
    {
        return iterator{_beginPtr};
    }

    const_iterator begin() const
    {
        return const_iterator{_beginPtr};
    }

    iterator end()
    {
        return iterator{_buckets + _capacity};
    }

    const_iterator end() const
    {
        return const_iterator{_buckets + _capacity};
    }

    template <class Type>
    iterator find(const Type& t)
    {
        return tFind<TTable<TableTraits>, iterator, Type>(*this, t);
    }

    template <class Type>
    const_iterator find(const Type& t) const
    {
        return tFind<const TTable<TableTraits>, const_iterator, Type>(*this, t);
    }

    void erase(const_iterator it)
    {
        Bucket* bucketPtr = it._bucketPtr;

        shiftBuckets(bucketPtr);
    }

private:

    void shiftBuckets(Bucket* prec)
    {
        Bucket* succ = (prec + 1 == _buckets + _capacity) ? _buckets : prec + 1;

        // Shift the right-adjacent buckets to the left
        while (succ->dib() > Bucket::FILLED)
        {
            prec->fill(succ->dib() - 1, std::move(succ->value()));
            prec = succ;
            succ = (++succ == _buckets + _capacity) ? _buckets : succ;
        }

        // Empty the bucket and decrement the size
        prec->markEmpty();

        if (prec == _beginPtr)
        {
            do
            {
                _beginPtr++;

            } while (_beginPtr->isEmpty());
        }
        
        if (ROBIN_UNLIKELY(--_size < (_capacity >> 2) && _size > STACK_SIZE))
        {
            rehashPrev();
        }
    }

    template <class Table, class Iterator, class Type>
    static Iterator tFind(Table& table, const Type& t)
    {
        uint8_t dib =  Bucket::FILLED;

        Bucket* prec = table._buckets + ((table._hasher(t) + dib) & table._mask);

        const Comparator& comparator = table._comparator;
        const std::size_t capacity   = table._capacity;
        Bucket* const     buckets    = table._buckets;

        // Skip buckets with lower dib or different value
        while (dib < prec->dib() || (dib == prec->dib() && !comparator(t, prec->value())))
        {
            dib++;
            prec = (++prec == buckets + capacity) ? buckets : prec;
        }

        if (dib == prec->dib())
        {
            return Iterator{prec};
        }

        // No luck :(
        return table.end();
    }


    void init()
    {
        for (std::size_t bucketIndex = 0; 
                 bucketIndex <= _capacity;
                 bucketIndex++)
        {
            new (reinterpret_cast<void*>(_buckets + bucketIndex)) Bucket();
        }

        _beginPtr = _buckets + _capacity;

        _beginPtr->markFilled(); // for it == end() optimization
    }

    Bucket*       _buckets;
    std::size_t   _mask;
    std::size_t   _size;
    std::size_t   _capacity;
    Bucket*       _beginPtr;
    Hasher        _hasher;
    Comparator    _comparator;
    BufferManager _bufferManager;
};

namespace table
{

template <class TableType,
          class TableHasher,
          class TableComparator,
          std::size_t STACK_SIZE_LOG2,
          std::size_t TABLE_LOAD_FACTOR_LEVEL>
struct TTraits
{
    static constexpr std::size_t STACK_SIZE = 1 << STACK_SIZE_LOG2;
    static constexpr std::size_t MASK       = STACK_SIZE - 1;

    static constexpr std::size_t LOAD_FACTOR_LEVEL = TABLE_LOAD_FACTOR_LEVEL;

    using Type       = TableType;
    using Hasher     = TableHasher;
    using Comparator = TableComparator;

    using Bucket = TBucket<Type>;

    using BufferManager = buffer::manager::TMakeFromType<Bucket, STACK_SIZE>;

    using Traits = TTraits<Type, Hasher, Comparator, STACK_SIZE_LOG2, LOAD_FACTOR_LEVEL>;

    using      Iterator = table::iterator::TMakeFromTraits<Traits>;
    using ConstIterator = table::iterator::TMakeFromTraits<Traits>;   
};

} // namespace table

int main()
{
    using TableTraits = table::TTraits<int, std::hash<int>, std::equal_to<int>, 2, 4>;
    using Table       = TTable<TableTraits>;
    
    Table table;
    
    table.emplace(1);
    table.emplace(2);
    table.emplace(3);
    table.emplace(5);
    
    for (const auto& element : table)
    {
        std::cout << element << std::endl;    
    }
    
    return 0;    
}