closed_hash.hpp

Go to the documentation of this file.

/*
    Copyright 2013 Adobe
    Distributed under the Boost Software License, Version 1.0.
    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
*/
/**************************************************************************************************/
 
#ifndef ADOBE_CLOSED_HASH_HPP
#define ADOBE_CLOSED_HASH_HPP
 
/**************************************************************************************************/
 
#include <adobe/config.hpp>
 
#include <adobe/closed_hash_fwd.hpp>
 
#include <climits>
#include <cstddef>
#include <cstdint>
#include <initializer_list>
#include <limits>
#include <utility>
 
#include <boost/compressed_pair.hpp>
#include <boost/iterator/iterator_adaptor.hpp>
#include <boost/iterator/iterator_facade.hpp>
#include <boost/next_prior.hpp>
#include <boost/operators.hpp>
 
#include <adobe/algorithm/lower_bound.hpp>
#include <adobe/conversion.hpp>
#include <adobe/empty.hpp>
#include <adobe/functional.hpp>
#include <adobe/iterator/set_next.hpp>
#include <adobe/memory.hpp>
#include <adobe/type_traits.hpp>
#include <adobe/utility.hpp>
 
#include <adobe/implementation/swap.hpp>
 
/**************************************************************************************************/
 
namespace adobe {
 
/**************************************************************************************************/
 
namespace implementation {
 
/**************************************************************************************************/
 
template <typename T, typename V> // V is value_type(T) const qualified
class closed_hash_iterator : public boost::iterator_facade<closed_hash_iterator<T, V>, V,
                                                           std::bidirectional_iterator_tag> {
    typedef boost::iterator_facade<closed_hash_iterator<T, V>, V, std::bidirectional_iterator_tag>
        inherited_t;
 
    typedef typename T::node_t node_t;
 
public:
    typedef typename inherited_t::reference reference;
    typedef typename inherited_t::difference_type difference_type;
    typedef typename inherited_t::value_type value_type;
 
    closed_hash_iterator() : node_m(0) {}
 
    template <typename O>
    closed_hash_iterator(const closed_hash_iterator<T, O>& x) : node_m(x.node_m) {}
 
public:
    /*
        REVISIT (sparent@adobe.com) : node_m should be private but
        "gcc version 4.0.1 (Apple Inc. build 5465)" doesn't like it.
    */
 
    node_t* node_m;
 
private:
    reference dereference() const { return node_m->value_m; }
    void increment() { node_m = node_m->next(); }
    void decrement() { node_m = node_m->prior(); }
 
    template <typename O>
    bool equal(const closed_hash_iterator<T, O>& y) const {
        return node_m == y.node_m;
    }
 
    std::size_t state() const { return node_m->state(); }
    void set_state(std::size_t x) { return node_m->set_state(x); }
 
    explicit closed_hash_iterator(node_t* node) : node_m(node) {}
 
    friend class version_1::closed_hash_set<value_type, typename T::key_transform,
                                            typename T::hasher, typename T::key_equal,
                                            typename T::allocator_type>;
    friend class boost::iterator_core_access;
    friend struct unsafe::set_next_fn<closed_hash_iterator>;
};
 
/**************************************************************************************************/
 
} // namespace implementation
 
/**************************************************************************************************/
 
namespace unsafe {
 
template <typename T, typename V>
struct set_next_fn<implementation::closed_hash_iterator<T, V>> {
    typedef typename implementation::closed_hash_iterator<T, V> iterator;
 
    void operator()(iterator x, iterator y) const { set_next(*x.node_m, *y.node_m); }
};
 
} // namespace unsafe
 
/**************************************************************************************************/
 
#ifndef ADOBE_NO_DOCUMENTATION
 
inline namespace version_1 {
 
#endif
 
/**************************************************************************************************/

 
template <typename T, typename KeyTransform, typename Hash, typename Pred, typename A>
class closed_hash_set
    : boost::equality_comparable<closed_hash_set<T, KeyTransform, Hash, Pred, A>,
                                 closed_hash_set<T, KeyTransform, Hash, Pred, A>,
                                 empty_base<closed_hash_set<T, KeyTransform, Hash, Pred, A>>> {
public:
    typedef KeyTransform key_transform;
 
    using key_type = std::remove_reference_t<adobe::invoke_result_t<KeyTransform, T>>;
 
    typedef T value_type;
    typedef Hash hasher;
    typedef Pred key_equal;
    typedef A allocator_type;
    typedef value_type* pointer;
    typedef const value_type* const_pointer;
    typedef value_type& reference;
    typedef const value_type& const_reference;
    typedef std::size_t size_type;
    typedef std::ptrdiff_t difference_type;
 
    friend class implementation::closed_hash_iterator<closed_hash_set, value_type>;
    friend class implementation::closed_hash_iterator<closed_hash_set, const value_type>;
 
    typedef implementation::closed_hash_iterator<closed_hash_set, value_type> iterator;
    typedef implementation::closed_hash_iterator<closed_hash_set, const value_type> const_iterator;
 
    typedef std::reverse_iterator<iterator> reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 
private:
    enum { state_free = 0, state_home = 1, state_misplaced = 2 };
 
    template <typename U> // U is derived node
    struct list_node_base {
        list_node_base() {
            next_m = static_cast<U*>(this);
            prior_m = static_cast<U*>(this);
        }
 
        U* address() { return static_cast<U*>(this); }
        const U* address() const { return static_cast<const U*>(this); }
 
        operator U&() { return *static_cast<U*>(this); }
        operator const U&() const { return *static_cast<const U*>(this); }
 
        friend inline void set_next(U& x, U& y) {
            x.next_m = reinterpret_cast<U*>(std::uintptr_t(&y) | std::uintptr_t(x.state()));
            y.prior_m = &x;
        }
 
        friend inline void set_next_raw(U& x, U& y) {
            x.next_m = &y;
            y.prior_m = &x;
        }
 
        std::size_t state() const {
            return std::size_t(std::uintptr_t(next_m) & std::uintptr_t(0x03UL));
        }
        void set_state(std::size_t x) {
            assert(x < 0x04UL);
            next_m = reinterpret_cast<U*>(std::uintptr_t(next()) | std::uintptr_t(x));
        }
 
        U* next() const {
            return reinterpret_cast<U*>(reinterpret_cast<std::uintptr_t>(next_m) &
                                        ~std::uintptr_t(0x03UL));
        }
        U* prior() const { return prior_m; }
 
    private:
        U* next_m;
        U* prior_m;
    };
 
    struct node_t : list_node_base<node_t> {
        T value_m;
    };
 
    typedef list_node_base<node_t> node_base_t;
 
    struct header_t {
        struct compact_header_t {
            boost::compressed_pair<allocator_type, node_base_t> alloc_free_tail_m;
            node_base_t used_tail_m;
            std::size_t capacity_m;
            std::size_t size_m;
        };
 
        /*
        NOTE (sparent) - the assumption is that the initial items are pointers and that size_t
        is
        either equal to the sizeof a pointer or a lower power of two so this packs tightly.
        */
 
        static_assert(!(sizeof(A) == sizeof(void*) || sizeof(A) == 0) ||
                      (sizeof(compact_header_t) ==
                       (sizeof(allocator_type) + 2 * sizeof(node_base_t) +
                        2 * sizeof(std::size_t))));
 
        aligned_storage<compact_header_t> header_m;
        node_t storage_m[1];
 
        allocator_type& allocator() { return header_m.get().alloc_free_tail_m.first(); }
        const allocator_type& allocator() const { return header_m.get().alloc_free_tail_m.first(); }
        node_base_t& free_tail() { return header_m.get().alloc_free_tail_m.second(); }
        const node_base_t& free_tail() const { return header_m.get().alloc_free_tail_m.second(); }
        node_base_t& used_tail() { return header_m.get().used_tail_m; }
        const node_base_t& used_tail() const { return header_m.get().used_tail_m; }
        std::size_t& capacity() { return header_m.get().capacity_m; }
        const std::size_t& capacity() const { return header_m.get().capacity_m; }
        std::size_t& size() { return header_m.get().size_m; }
        const std::size_t& size() const { return header_m.get().size_m; }
    };
 
    typedef node_t* node_ptr;
 
    typedef boost::compressed_pair<
        hasher, boost::compressed_pair<key_equal, boost::compressed_pair<key_transform, header_t*>>>
        data_t;
 
    data_t data_m;
 
    typedef header_t* header_pointer;
 
    const header_pointer& header() const { return data_m.second().second().second(); }
    header_pointer& header() { return data_m.second().second().second(); }
 
public:
    // construct/destroy/copy
 
    closed_hash_set() { header() = 0; }
 
    explicit closed_hash_set(size_type n) {
        header() = 0;
        allocate(allocator_type(), n);
    }
 
    closed_hash_set(size_type n, const hasher& hf, const key_equal& eq = key_equal(),
                    const key_transform& kf = key_transform(),
                    const allocator_type& a = allocator_type()) {
        header() = 0;
        data_m.first() = hf;
        data_m.second().first() = eq;
        data_m.second().second().first() = kf;
        allocate(a, n);
    }
 
    template <typename I> // I models InputIterator
    closed_hash_set(I f, I l) {
        header() = 0;
        insert(f, l);
    }
 
    closed_hash_set(std::initializer_list<value_type> init) {
        header() = 0;
        insert(init.begin(), init.end());
    }
 
    template <typename I> // I models InputIterator
    closed_hash_set(I f, I l, size_type n, const hasher& hf = hasher(),
                    const key_equal& eq = key_equal(), const key_transform& kf = key_transform(),
                    const allocator_type& a = allocator_type()) {
        header() = 0;
        data_m.first() = hf;
        data_m.second().first() = eq;
        data_m.second().second().first() = kf;
        allocate(a, n);
        insert(f, l);
    }
 
    closed_hash_set(const closed_hash_set& x) : data_m(x.data_m) {
        header() = 0;
        allocate(x.get_allocator(), x.size());
        insert(x.begin(), x.end());
    }
    closed_hash_set& operator=(closed_hash_set x) {
        swap(x, *this);
        return *this;
    }
 
    allocator_type get_allocator() const {
        return header() ? header()->allocator() : allocator_type();
    }
 
    closed_hash_set(closed_hash_set&& x) noexcept : data_m(x.data_m) { x.header() = 0; }
 
    // size and capacity
 
    size_type size() const { return header() ? header()->size() : 0; }
    size_type max_size() const { return size_type(-1) / sizeof(node_t); }
    bool empty() const { return size() == 0; }
    size_type capacity() const { return header() ? capacity_() : 0; }
 
    void reserve(size_type n) {
        if (n <= capacity())
            return;
 
        if (!header())
            allocate(allocator_type(), n);
        else {
            closed_hash_set tmp(n, hash_function(), key_eq(), key_function(), get_allocator());
            tmp.move_insert(begin(), end());
            swap(*this, tmp);
        }
    }
 
    key_transform key_function() const { return data_m.second().second().first(); }
    hasher hash_function() const { return data_m.first(); }
    key_equal key_eq() const { return data_m.second().first(); }
 
    iterator begin() { return iterator(header() ? header()->used_tail().next() : 0); }
    iterator end() { return iterator(header() ? header()->used_tail().address() : 0); }
 
    const_iterator begin() const { return iterator(header() ? header()->used_tail().next() : 0); }
    const_iterator end() const {
        return iterator(header() ? const_cast<node_t*>(header()->used_tail().address()) : 0);
    }
 
    reverse_iterator rbegin() { return reverse_iterator(end()); }
    reverse_iterator rend() { return reverse_iterator(begin()); }
 
    const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
    const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
 
    iterator erase(iterator location) {
        iterator next(boost::next(location));
        iterator result = next;
 
        if ((location.state() == std::size_t(state_home)) && (next != end()) &&
            (next.state() == std::size_t(state_misplaced))) {
            swap(*next, *location);
            result = location;
            location = next;
        }
 
        unsafe::skip_node(location);
        erase_raw(location);
 
        --header()->size();
 
        return result;
    }
 
    std::size_t erase(const key_type& key) {
        iterator node(find(key));
        if (node == end())
            return 0;
        erase(node);
        return 1;
    }
 
    void clear() {
        for (iterator first(begin()), last(end()); first != last; first = erase(first))
            ;
    }
 
    const_iterator find(const key_type& key) const { return find(key, hash_function()(key)); }
 
    const_iterator find(const key_type& key, std::size_t hash) const {
        return adobe::remove_const(*this).find(key, hash);
    }
 
    iterator find(const key_type& key) { return find(key, hash_function()(key)); }
 
    iterator find(const key_type& key, std::size_t hash) {
        if (!header())
            return iterator(0);
 
        iterator node = bucket_(hash);
        iterator last = end_();
 
        if (node.state() != std::size_t(state_home))
            return last;
 
        return find(node, last, key);
    }
 
    std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const {
        return equal_range(key, hash_function()(key));
    }
 
    std::pair<const_iterator, const_iterator> equal_range(const key_type& key, size_t hash) const {
        const_iterator result = find(key, hash);
        if (result == end())
            return std::make_pair(result, result);
        return std::make_pair(result, boost::next(result));
    }
 
 
    std::pair<iterator, iterator> equal_range(const key_type& key) {
        return equal_range(key, hash_function()(key));
    }
 
    std::pair<iterator, iterator> equal_range(const key_type& key, std::size_t hash) {
        iterator result = find(key, hash);
        if (result == end())
            return std::make_pair(result, result);
        return std::make_pair(result, boost::next(result));
    }
 
 
    std::size_t count(const key_type& key) const { return count(key, hash_function()(key)); }
    std::size_t count(const key_type& key, std::size_t hash) const {
        return std::size_t(find(key, hash) != end());
    }
 
    template <typename I> // I models InputIterator
    void insert(I first, I last) {
        while (first != last) {
            insert(*first);
            ++first;
        }
    }
 
    template <typename I> // I models ForwardIterator
    void move_insert(I first, I last) {
        while (first != last) {
            insert(std::move(*first));
            ++first;
        }
    }
 
    std::pair<iterator, bool> insert(value_type x) {
        return insert(x, hash_function()(key_function()(x)));
    }
 
    /*
        NOTE (sparent): If there is not enough space for one element we will reserve the space
        prior to attempting the insert even if the item is already in the hash table. Without
        recalculating the bucket (a potentially expensive operation) there is no other solution.
    */
 
    std::pair<iterator, bool> insert(value_type x, std::size_t hash) {
        if (capacity() == size())
            reserve(size() ? 2 * size() : 3);
 
        iterator node = bucket_(hash);
 
        switch (node.state()) {
        case state_home: {
            iterator found = find(node, end_(), key_function()(x));
            if (found != end()) {
                return std::make_pair(found, false);
            }
 
            iterator free(begin_free());
            insert_raw(free, std::move(x), state_misplaced);
            unsafe::splice_node_range(node, free, free);
            node = free;
        } break;
        case state_misplaced: {
            iterator free(begin_free());
            insert_raw(free, std::move(*node), state_misplaced);
 
            unsafe::set_next(boost::prior(node), free);
            unsafe::set_next(free, boost::next(node));
 
            erase_raw(node);
        }
        // fall through
        default: // state_free
        {
            insert_raw(node, std::move(x), state_home);
            unsafe::splice_node_range(end(), node, node);
        }
        }
        header()->size() += 1;
        return std::make_pair(node, true);
    }
 
    iterator insert(iterator, value_type x) { return insert(std::move(x)).first; }
 
    ~closed_hash_set() {
        if (header()) {
            for (iterator first(begin()), last(end()); first != last; ++first)
                destroy(&*first);
            raw_allocator alloc(get_allocator());
            alloc.deallocate(reinterpret_cast<char*>(header()), 0);
        }
    }
 
    friend void swap(closed_hash_set& x, closed_hash_set& y) { std::swap(x.data_m, y.data_m); }
 
    friend bool operator==(const closed_hash_set& x, const closed_hash_set& y) {
        if (x.size() != y.size())
            return false;
        for (const_iterator first(x.begin()), last(x.end()); first != last; ++first) {
            const_iterator iter(y.find(y.key_function()(*first)));
            if (iter == y.end() || !(*first == *iter))
                return false;
        }
        return true;
    }
 
private:
    typedef typename allocator_type::template rebind<char>::other raw_allocator;
 
 
    void allocate(const allocator_type& a, size_type n) {
        // table of primes such that p[n + 1] = next_prime(2 * p[n])
 
        static const std::size_t prime_table[] = {
            3UL,        7UL,         17UL,        37UL,        79UL,         163UL,
            331UL,      673UL,       1361UL,      2729UL,      5471UL,       10949UL,
            21911UL,    43853UL,     87719UL,     175447UL,    350899UL,     701819UL,
            1403641UL,  2807303UL,   5614657UL,   11229331UL,  22458671UL,   44917381UL,
            89834777UL, 179669557UL, 359339171UL, 718678369UL, 1437356741UL, 2874713497UL,
            ULONG_MAX};
 
        assert(!header() && "WARNING (sparent@adobe.com) : About to write over allocated header.");
 
        if (n == 0 && a == allocator_type())
            return;
 
        n = *adobe::lower_bound(prime_table, n);
 
        raw_allocator alloc(a);
 
        header() = reinterpret_cast<header_t*>(
            alloc.allocate(sizeof(header_t) - sizeof(node_t) + sizeof(node_t) * n));
        header()->capacity() = n;
        header()->size() = 0;
        adobe::construct_at(&header()->free_tail());
        adobe::construct_at(&header()->used_tail());
        adobe::construct_at(&header()->allocator(), a);
 
        node_t* prior = header()->free_tail().address();
        for (node_ptr first(&header()->storage_m[0]), last(&header()->storage_m[0] + n);
             first != last; ++first) {
            set_next_raw(*prior, *first);
            prior = first;
            // first->set_state(state_free);
        }
        set_next_raw(*prior, header()->free_tail());
    }
 
 
    // precondition: header() != NULL
    iterator end_() { return iterator(header()->used_tail().address()); }
 
    // precondition: header() != NULL
    size_type capacity_() const { return header()->capacity(); }
 
    // precondition: header() != NULL
    iterator bucket_(std::size_t hash) {
        return iterator(&header()->storage_m[0] + hash % capacity_());
    }
 
    // preconditino: [f, l) is not empty
    iterator find(iterator f, iterator l, const key_type& key) {
        do {
            if (key_eq()(key, key_function()(*f)))
                return f;
            ++f;
        } while ((f != l) && (f.state() != std::size_t(state_home)));
 
        return l;
    }
 
    // location points to a free node
    static void insert_raw(iterator location, value_type x, std::size_t state) {
        adobe::construct_at<value_type>(&*location, std::move(x));
        location.set_state(state);
        unsafe::skip_node(location);
    }
 
    // location points to a used but detatched node
    void erase_raw(iterator location) {
        destroy(&*location);
        location.set_state(state_free);
        unsafe::splice_node_range(end_free(), location, location);
    }
 
    iterator begin_free() { return iterator(header() ? header()->free_tail().next() : 0); }
    iterator end_free() { return iterator(header() ? header()->free_tail().address() : 0); }
};
 
/**************************************************************************************************/

 
template <typename Key, typename T, typename Hash, typename Pred, typename A>
class closed_hash_map : public closed_hash_set<std::pair<Key, T>, get_element<0>, Hash, Pred, A> {
 
    using set_type = closed_hash_set<std::pair<Key, T>, get_element<0>, Hash, Pred, A>;
 
public:
    typedef T mapped_type;
 
    closed_hash_map() {}
 
    template <typename I> // I models InputIterator
    closed_hash_map(I f, I l) : set_type(f, l) {}
 
    closed_hash_map(std::initializer_list<typename set_type::value_type> init) : set_type(init) {}
 
    closed_hash_map(const closed_hash_map& x) : set_type(x) {}
    closed_hash_map(closed_hash_map&& x) noexcept : set_type(std::move(x)) {}
    closed_hash_map& operator=(closed_hash_map x) {
        swap(x, *this);
        return *this;
    }
 
    friend void swap(closed_hash_map& x, closed_hash_map& y) {
        swap(static_cast<set_type&>(x), static_cast<set_type&>(y));
    }
 
 
    friend bool operator==(const closed_hash_map& x, const closed_hash_map& y) {
        return static_cast<const set_type&>(x) == static_cast<const set_type&>(y);
    }
 
    /*
        NOTE (sparent) : Can't use boost::equality_comparable without introducing extra base
       class
        overhead.
    */
 
    friend bool operator!=(const closed_hash_map& x, const closed_hash_map& y) { return !(x == y); }
 
#ifndef ADOBE_CLOSED_HASH_MAP_INDEX
#define ADOBE_CLOSED_HASH_MAP_INDEX 1
#endif
 
#if ADOBE_CLOSED_HASH_MAP_INDEX
 
    mapped_type& operator[](const Key& x) {
        typename set_type::iterator i = this->find(x);
        if (i == this->end()) {
            return this->insert(std::make_pair(x, mapped_type())).first->second;
        }
        return i->second;
    }
 
#endif
};
 
/**************************************************************************************************/
 
static_assert(sizeof(closed_hash_set<int>) == sizeof(void*));
 
 
#ifndef ADOBE_NO_DOCUMENTATION
 
} // namespace version_1
 
#endif
 
/**************************************************************************************************/
 
} // namespace adobe
 
/**************************************************************************************************/
 
#endif
 
/**************************************************************************************************/