hash_set_robin_hood.hpp

// By Emil Ernerfeldt 2014-2016
// LICENSE:
//   This software is dual-licensed to the public domain and under the following
//   license: you are granted a perpetual, irrevocable license to copy, modify,
//   publish, and distribute this file as you see fit.

// This is heavily inspired by https://gist.github.com/ssylvan/5538011

#pragma once

#include <cstdlib> // std::malloc
#include <cstring> // std::memset
#include <iterator>
#include <utility> // std::move and std::pair

namespace emilib {

// like std::equal_to but no need to #include <functional>
template<typename T>
struct HashSetRHEqualTo
{
    constexpr bool operator()(const T &lhs, const T &rhs) const
    {
        return lhs == rhs;
    }
};

// A cache-friendly hash set with open addressing, linear probing and power-of-two capacity
template <typename KeyT, typename HasherT = std::hash<KeyT>, typename EqT = HashSetRHEqualTo<KeyT>>
class HashSetRH
{
private:
    using MyType = HashSetRH<KeyT, HasherT, EqT>;

public:
    using size_type       = size_t;
    using value_type      = KeyT;
    using reference       = KeyT&;
    using const_reference = const KeyT&;
    using HashCode        = size_t;

    static const size_t   kMaxLoadFactorPercent = 90;
    static const HashCode kUnusedHashCode       =  0;
    static const HashCode kTombStoneFlag        =  HashCode(1) << HashCode(8 * sizeof(HashCode) - 1);

    class iterator
    {
    public:
        using iterator_category = std::forward_iterator_tag;
        using difference_type   = size_t;
        using distance_type     = size_t;
        using value_type        = KeyT;
        using pointer           = value_type*;
        using reference         = value_type&;

        iterator() { }

        iterator(MyType* hash_set, size_t bucket) : _set(hash_set), _bucket(bucket)
        {
        }

        iterator& operator++()
        {
            goto_next_element();
            return *this;
        }

        iterator operator++(int)
        {
            size_t old_index = _bucket;
            goto_next_element();
            return iterator(_set, old_index);
        }

        reference operator*() const
        {
            return _set->_keys[_bucket];
        }

        pointer operator->() const
        {
            return _set->_keys + _bucket;
        }

        bool operator==(const iterator& rhs)
        {
            return this->_bucket == rhs._bucket;
        }

        bool operator!=(const iterator& rhs)
        {
            return this->_bucket != rhs._bucket;
        }

    private:
        void goto_next_element()
        {
            do {
                _bucket++;
            } while (_bucket < _set->_num_buckets && !_is_filled_hash(_set->_hashes[_bucket]));
        }

    public:
        MyType* _set;
        size_t  _bucket;
    };

    class const_iterator
    {
    public:
        using iterator_category = std::forward_iterator_tag;
        using difference_type   = size_t;
        using distance_type     = size_t;
        using value_type        = const KeyT;
        using pointer           = value_type*;
        using reference         = value_type&;

        const_iterator() { }

        const_iterator(iterator proto) : _set(proto._set), _bucket(proto._bucket)
        {
        }

        const_iterator(const MyType* hash_set, size_t bucket) : _set(hash_set), _bucket(bucket)
        {
        }

        const_iterator& operator++()
        {
            goto_next_element();
            return *this;
        }

        const_iterator operator++(int)
        {
            size_t old_index = _bucket;
            goto_next_element();
            return const_iterator(_set, old_index);
        }

        reference operator*() const
        {
            return _set->_keys[_bucket];
        }

        pointer operator->() const
        {
            return _set->_keys + _bucket;
        }

        bool operator==(const const_iterator& rhs)
        {
            return this->_bucket == rhs._bucket;
        }

        bool operator!=(const const_iterator& rhs)
        {
            return this->_bucket != rhs._bucket;
        }

    private:
        void goto_next_element()
        {
            do {
                _bucket++;
            } while (_bucket < _set->_num_buckets && !_is_filled_hash(_set->_hashes[_bucket]));
        }

    public:
        const MyType* _set;
        size_t        _bucket;
    };

    // ------------------------------------------------------------------------

    HashSetRH() = default;

    HashSetRH(const HashSetRH& other)
    {
        reserve(other.size());
        insert(cbegin(other), cend(other));
    }

    HashSetRH(HashSetRH&& other)
    {
        *this = std::move(other);
    }

    HashSetRH& operator=(const HashSetRH& other)
    {
        clear();
        reserve(other.size());
        insert(cbegin(other), cend(other));
        return *this;
    }

    void operator=(HashSetRH&& other)
    {
        this->swap(other);
    }

    ~HashSetRH()
    {
        for (size_t bucket=0; bucket<_num_buckets; ++bucket) {
            if (_is_filled_hash(_hashes[bucket])) {
                _keys[bucket].~KeyT();
            }
        }
        std::free(_hashes);
        std::free(_keys);
    }

    void swap(HashSetRH& other)
    {
        std::swap(_hasher,       other._hasher);
        std::swap(_eq,           other._eq);
        std::swap(_keys,         other._keys);
        std::swap(_hashes,       other._hashes);
        std::swap(_num_buckets,  other._num_buckets);
        std::swap(_num_filled,   other._num_filled);
        std::swap(_rehash_limit, other._rehash_limit);
        std::swap(_mask,         other._mask);
    }

    // -------------------------------------------------------------

    iterator begin()
    {
        size_t bucket = 0;
        while (bucket<_num_buckets && !_is_filled_hash(_hashes[bucket])) {
            ++bucket;
        }
        return iterator(this, bucket);
    }

    const_iterator begin() const
    {
        size_t bucket = 0;
        while (bucket<_num_buckets && !_is_filled_hash(_hashes[bucket])) {
            ++bucket;
        }
        return const_iterator(this, bucket);
    }

    iterator end()
    { return iterator(this, _num_buckets); }

    const_iterator end() const
    { return const_iterator(this, _num_buckets); }

    size_t size() const
    {
        return _num_filled;
    }

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

    size_t bucket_count() const
    {
        return _num_buckets;
    }

    // ------------------------------------------------------------

    iterator find(const KeyT& key)
    {
        auto bucket = _find_filled_bucket(key);
        if (bucket == (size_t)-1) {
            return end();
        }
        return iterator(this, bucket);
    }

    const_iterator find(const KeyT& key) const
    {
        auto bucket = _find_filled_bucket(key);
        if (bucket == (size_t)-1) {
            return end();
        }
        return const_iterator(this, bucket);
    }

    bool contains(const KeyT& k) const
    {
        return _find_filled_bucket(k) != (size_t)-1;
    }

    size_t count(const KeyT& k) const
    {
        return contains(k) ? 1 : 0;
    }

    // -----------------------------------------------------

    // Insert an element, unless it already exists.
    // Returns a pair consisting of an iterator to the inserted element
    // (or to the element that prevented the insertion)
    // and a bool denoting whether the insertion took place.
    std::pair<iterator, bool> insert(KeyT key)
    {
        const HashCode hash = _hash_key(key);
        size_t existing_pos = _find_filled_bucket(hash, key);
        if (existing_pos == (size_t)-1) {
            // printf("insert\n");
            _check_expand_need();
            size_t pos = _insert_unique_no_expand_check(hash, std::move(key));
            return {iterator{this, pos}, true};
        } else {
            // printf("already_existed\n");
            return {iterator{this, existing_pos}, false};
        }
    }

    template<class... Args>
    std::pair<iterator, bool> emplace(Args&&... args)
    {
        return insert(KeyT(std::forward<Args>(args)...));
    }

    void insert(const_iterator begin, const_iterator end)
    {
        for (; begin != end; ++begin) {
            insert(*begin);
        }
    }

    // Same as above, but contains(key) MUST be false
    void insert_unique(KeyT key)
    {
        _check_expand_need();
        _insert_unique_no_expand_check(_hash_key(key), std::move(key));
    }

    // -------------------------------------------------------

    /* Erase an element from the hash set.
       return false if element was not found */
    bool erase(const KeyT& key)
    {
        const HashCode hash = _hash_key(key);
        const size_t pos = _find_filled_bucket(hash, key);
        if (pos != (size_t)-1) {
            _keys[pos].~KeyT();
            _hashes[pos] |= kTombStoneFlag;
            --_num_filled;
            return true;
        }
    }

    /* Erase an element using an iterator.
       Returns an iterator to the next element (or end()). */
    iterator erase(iterator it)
    {
        _keys[it._bucket].~KeyT();
        _hashes[it._bucket] |= kTombStoneFlag;
        --_num_filled;
        return true;
    }

    // Remove all elements, keeping full capacity.
    void clear()
    {
        for (size_t bucket=0; bucket<_num_buckets; ++bucket) {
            if (_is_filled_hash(_hashes[bucket])) {
                _keys[bucket].~KeyT();
            }
        }
        _num_filled = 0;
        static_assert(kUnusedHashCode == 0, "");
        std::memset(_hashes, 0, _num_buckets * sizeof(HashCode));
    }

    // Make room for this many elements
    void reserve(size_t num_elems)
    {
        if (num_elems <= _rehash_limit) {
            return;
        }

        size_t min_required_buckets = 1 + num_elems * 100 / kMaxLoadFactorPercent;
        size_t num_buckets = 4;
        while (num_buckets < min_required_buckets) { num_buckets *= 2; }

        // printf("New size: %lu\n", num_buckets);

        auto new_hashes = (HashCode*)std::malloc(num_buckets * sizeof(HashCode));
        auto new_keys   = (KeyT*)std::malloc(num_buckets  * sizeof(KeyT));

        if (new_hashes == nullptr || new_keys == nullptr) {
            std::free(new_hashes);
            std::free(new_keys);
            throw std::bad_alloc();
        }

        // auto old_num_filled  = _num_filled;
        auto old_num_buckets = _num_buckets;
        auto old_hashes      = _hashes;
        auto old_keys        = _keys;

        _num_filled   = 0;
        _num_buckets  = num_buckets;
        _rehash_limit = (_num_buckets * kMaxLoadFactorPercent) / 100;
        _mask         = _num_buckets - 1;
        _hashes       = new_hashes;
        _keys         = new_keys;

        static_assert(kUnusedHashCode == 0, "");
        std::memset(_hashes, 0, _num_buckets * sizeof(HashCode));

        for (size_t src_bucket=0; src_bucket<old_num_buckets; ++src_bucket) {
            auto src_hash = old_hashes[src_bucket];
            if (_is_filled_hash(src_hash)) {
                auto& src_key = old_keys[src_bucket];
                _insert_unique_no_expand_check(src_hash, std::move(src_key));
                src_key.~KeyT();
            }
        }

        std::free(old_hashes);
        std::free(old_keys);
    }

private:
    // Can we fit another element?
    void _check_expand_need()
    {
        reserve(_num_filled + 1);
    }

    uint32_t _hash_key(const KeyT& key) const
    {
        HashCode hash = static_cast<HashCode>(_hasher(key));

        // Ensure kTombStoneFlag is cleared:
        hash &= ~kTombStoneFlag;

        // Ensure that we never return kUnusedHashCode as a hash:
        hash ^= hash==kUnusedHashCode;

        return hash;
    }

    static bool _is_deleted_hash(HashCode hash)
    {
        return (hash & kTombStoneFlag) != 0;
    }

    static bool _is_filled_hash(HashCode hash)
    {
        return hash != kUnusedHashCode && !_is_deleted_hash(hash);
    }

    size_t _desired_pos(HashCode hash) const
    {
        return hash & _mask;
    }

    size_t _probe_distance(HashCode hash, HashCode pos) const
    {
        return (pos + _num_buckets - _desired_pos(hash)) & _mask;
    }

    void _construct(size_t pos, HashCode hash, KeyT&& key)
    {
        new (&_keys[pos]) KeyT(std::move(key));
        _hashes[pos] = hash;
        ++_num_filled;
    }

    size_t _insert_unique_no_expand_check(HashCode hash, KeyT&& key)
    {
        size_t pos = _desired_pos(hash);
        size_t dist = 0;
        for (;;) {
            // printf("_insert_unique_no_expand_check: %lu\n", pos);
            if (_hashes[pos] == kUnusedHashCode) {
                _construct(pos, hash, std::move(key));
                return pos;
            }

            // If the existing elem has probed less than us, then swap places with existing
            // elem, and keep going to find another slot for that elem.
            size_t existing_elem_probe_dist = _probe_distance(_hashes[pos], pos);
            if (existing_elem_probe_dist < dist) {
                if (_is_deleted_hash(_hashes[pos])) {
                    _construct(pos, hash, std::move(key));
                    return pos;
                }

                std::swap(hash, _hashes[pos]);
                std::swap(key, _keys[pos]);
                dist = existing_elem_probe_dist;
            }

            pos = (pos + 1) & _mask;
            ++dist;
        }
    }

    size_t _find_filled_bucket(HashCode hash, const KeyT& key) const
    {
        if (_num_buckets == 0) { return (size_t)-1; }
        size_t pos = _desired_pos(hash);
        size_t dist = 0;
        for (;;) {
            // printf("_find_filled_bucket: %lu\n", pos);
            if (_hashes[pos] == kUnusedHashCode) {
                return (size_t)-1;
            } else if (dist > _probe_distance(_hashes[pos], pos)) {
                return (size_t)-1;
            } else if (_hashes[pos] == hash && _keys[pos] == key) {
                return pos;
            }

            pos = (pos + 1) & _mask;
            ++dist;
        }
    }

private:
    // TODO: __restrict
    HasherT   _hasher;
    EqT       _eq;
    KeyT*     _keys         = nullptr;
    HashCode* _hashes       = nullptr;
    size_t    _num_buckets  = 0; // capacity
    size_t    _num_filled   = 0; // size
    size_t    _rehash_limit = 0; // when _num_buckets exceed this, rehash.
    size_t    _mask         = 0; // _num_buckets minus one
};

} // namespace emilib