hashcontainer.hh

#ifndef CLICK_HASHCONTAINER_HH
#define CLICK_HASHCONTAINER_HH
#include <click/glue.hh>
#include <click/hashcode.hh>
#include <click/libdivide.h>
#if CLICK_DEBUG_HASHMAP
# define click_hash_assert(x) assert(x)
#else
# define click_hash_assert(x)
#endif
CLICK_DECLS
 
template <typename T> class HashContainer_adapter;
template <typename T, typename A = HashContainer_adapter<T> > class HashContainer_const_iterator;
template <typename T, typename A = HashContainer_adapter<T> > class HashContainer_iterator;
template <typename T, typename A = HashContainer_adapter<T> > class HashContainer;
 
template <typename T, typename A>
class HashContainer_rep : public A {
    T **buckets;
    uint32_t nbuckets;
    mutable uint32_t first_bucket;
    size_t size;
    libdivide_u32_t bucket_divider;
#if defined(CLICK_HASH_ITERATOR_EPOCHS)
    unsigned epoch;
#endif
    friend class HashContainer<T, A>;
    friend class HashContainer_const_iterator<T, A>;
    friend class HashContainer_iterator<T, A>;
};
template <typename T>
class HashContainer_adapter { public:
    typedef typename T::key_type key_type;
    typedef typename T::key_const_reference key_const_reference;
    static T *&hashnext(T *e) {
        return e->_hashnext;
    }
    static key_const_reference hashkey(const T *e) {
        return e->hashkey();
    }
    static bool hashkeyeq(const key_type &a, const key_type &b) {
        return a == b;
    }
};
 
template <typename T, typename A>
class HashContainer { public:
 
    typedef typename A::key_type key_type;
 
    typedef T value_type;
 
    typedef size_t size_type;
 
    typedef uint32_t bucket_count_type;
 
    enum {
#if CLICK_LINUXMODULE
        max_bucket_count = 4194303,
#else
        max_bucket_count = (bucket_count_type) -1,
#endif
        initial_bucket_count = 63
    };
 
    HashContainer();
 
    explicit HashContainer(bucket_count_type n);
 
    ~HashContainer();
 
 
    inline size_type size() const {
        return _rep.size;
    }
 
    inline bool empty() const {
        return _rep.size == 0;
    }
 
    inline bucket_count_type bucket_count() const {
        return _rep.nbuckets;
    }
 
    inline size_type bucket_size(bucket_count_type n) const {
        click_hash_assert(n < _rep.nbuckets);
        size_type s = 0;
        for (T *element = _rep.buckets[n]; element; element = _rep.hashnext(element))
            ++s;
        return s;
    }
 
    bucket_count_type bucket(const key_type &key) const;
 
    inline bool unbalanced() const {
        return _rep.size > 2 * _rep.nbuckets && _rep.nbuckets < max_bucket_count;
    }
 
    typedef HashContainer_const_iterator<T, A> const_iterator;
    typedef HashContainer_iterator<T, A> iterator;
 
    inline iterator begin();
    inline const_iterator begin() const;
 
    inline iterator end();
    inline const_iterator end() const;
 
    inline iterator begin(bucket_count_type n);
    inline const_iterator begin(bucket_count_type n) const;
 
    inline bool contains(const key_type& key) const;
    inline size_type count(const key_type& key) const;
 
    inline iterator find(const key_type &key);
    inline const_iterator find(const key_type &key) const;
 
    inline iterator find_prefer(const key_type &key);
 
    inline T *get(const key_type &key) const;
 
    inline void insert_at(iterator &it, T *element);
 
    T *set(iterator &it, T *element, bool balance = false);
 
    inline T *set(T *element);
 
    inline T *erase(iterator &it);
 
    inline T *erase(const key_type &key);
 
    void clear();
 
    inline void swap(HashContainer<T, A> &x);
 
    void rehash(bucket_count_type n);
 
    inline void balance() {
        if (unbalanced())
            rehash(bucket_count() + 1);
    }
 
  private:
 
    HashContainer_rep<T, A> _rep;
 
    HashContainer(const HashContainer<T, A> &);
    HashContainer<T, A> &operator=(const HashContainer<T, A> &);
 
    friend class HashContainer_iterator<T, A>;
    friend class HashContainer_const_iterator<T, A>;
 
};
 
template <typename T, typename A>
class HashContainer_const_iterator { public:
 
    typedef typename HashContainer<T, A>::size_type size_type;
    typedef typename HashContainer<T, A>::bucket_count_type bucket_count_type;
 
    HashContainer_const_iterator() {
    }
 
    T *get() const {
#if defined(CLICK_HASH_ITERATOR_EPOCHS)
        assert(!_element || _hc->_rep.epoch == _epoch);
#endif
        return _element;
    }
 
    T *operator->() const {
#if defined(CLICK_HASH_ITERATOR_EPOCHS)
        assert(!_element || _hc->_rep.epoch == _epoch);
#endif
        return _element;
    }
 
    T &operator*() const {
#if defined(CLICK_HASH_ITERATOR_EPOCHS)
        assert(!_element || _hc->_rep.epoch == _epoch);
#endif
        return *_element;
    }
 
    inline bool live() const {
#if defined(CLICK_HASH_ITERATOR_EPOCHS)
        assert(!_element || _hc->_rep.epoch == _epoch);
#endif
        return _element;
    }
 
    typedef T *(HashContainer_const_iterator::*unspecified_bool_type)() const;
    inline operator unspecified_bool_type() const {
#if defined(CLICK_HASH_ITERATOR_EPOCHS)
        assert(!_element || _hc->_rep.epoch == _epoch);
#endif
        return _element ? &HashContainer_const_iterator::get : 0;
    }
 
    const HashContainer<T, A> *hashcontainer() const {
        return _hc;
    }
 
    bucket_count_type bucket() const {
        return _bucket;
    }
 
    void operator++() {
#if defined(CLICK_HASH_ITERATOR_EPOCHS)
        assert(!_element || _hc->_rep.epoch == _epoch);
#endif
        if (_element && _hc->_rep.hashnext(_element)) {
            _pprev = &_hc->_rep.hashnext(_element);
            _element = *_pprev;
        } else if (_bucket != _hc->_rep.nbuckets) {
            for (++_bucket; _bucket != _hc->_rep.nbuckets; ++_bucket)
                if (*(_pprev = &_hc->_rep.buckets[_bucket])) {
                    _element = *_pprev;
                    return;
                }
            _element = 0;
        }
    }
 
    void operator++(int) {
        ++*this;
    }
 
  private:
 
    T *_element;
    T **_pprev;
    bucket_count_type _bucket;
    const HashContainer<T, A> *_hc;
#if defined(CLICK_HASH_ITERATOR_EPOCHS)
    unsigned _epoch;
#endif
 
    inline HashContainer_const_iterator(const HashContainer<T, A> *hc)
        : _hc(hc) {
        _bucket = hc->_rep.first_bucket;
        _pprev = &hc->_rep.buckets[_bucket];
#if defined(CLICK_HASH_ITERATOR_EPOCHS)
        _epoch = hc->_rep.epoch;
#endif
        if (unlikely(_bucket == hc->_rep.nbuckets))
            _element = 0;
        else if (!(_element = *_pprev)) {
            (*this)++;
            hc->_rep.first_bucket = _bucket;
        }
    }
 
    inline HashContainer_const_iterator(const HashContainer<T, A> *hc, bucket_count_type b, T **pprev, T *element)
        : _element(element), _pprev(pprev), _bucket(b), _hc(hc)
#if defined(CLICK_HASH_ITERATOR_EPOCHS)
        , _epoch(hc->_rep.epoch)
#endif
        {
        click_hash_assert((!_pprev && !_element) || *_pprev == _element);
    }
 
    friend class HashContainer<T, A>;
    friend class HashContainer_iterator<T, A>;
 
};
 
template <typename T, typename A>
class HashContainer_iterator : public HashContainer_const_iterator<T, A> { public:
 
    typedef HashContainer_const_iterator<T, A> inherited;
 
    HashContainer_iterator() {
    }
 
    bool can_insert() const {
        return this->_bucket < this->_hc->bucket_count();
    }
 
    HashContainer<T, A> *hashcontainer() const {
        return const_cast<HashContainer<T, A> *>(this->_hc);
    }
 
  private:
 
    inline HashContainer_iterator(HashContainer<T, A> *hc)
        : inherited(hc) {
    }
 
    inline HashContainer_iterator(HashContainer<T, A> *hc, typename inherited::bucket_count_type b, T **pprev, T *element)
        : inherited(hc, b, pprev, element) {
    }
 
    friend class HashContainer<T, A>;
 
};
 
template <typename T, typename A>
HashContainer<T, A>::HashContainer()
{
    _rep.size = 0;
    _rep.nbuckets = initial_bucket_count;
    _rep.buckets = (T **) CLICK_LALLOC(sizeof(T *) * _rep.nbuckets);
    _rep.first_bucket = _rep.nbuckets;
    _rep.bucket_divider = libdivide_u32_gen(_rep.nbuckets);
    click_hash_assert(_rep.nbuckets == libdivide_u32_recover(&_rep.bucket_divider));
#if defined(CLICK_HASH_ITERATOR_EPOCHS)
    _rep.epoch = 0;
#endif
    for (bucket_count_type b = 0; b < _rep.nbuckets; ++b)
        _rep.buckets[b] = 0;
}
 
template <typename T, typename A>
HashContainer<T, A>::HashContainer(bucket_count_type nb)
{
    bucket_count_type b = 1;
    while (b < nb && b < max_bucket_count)
        b = ((b + 1) << 1) - 1;
    _rep.size = 0;
    _rep.nbuckets = b;
    _rep.buckets = (T **) CLICK_LALLOC(sizeof(T *) * _rep.nbuckets);
    _rep.first_bucket = _rep.nbuckets;
    _rep.bucket_divider = libdivide_u32_gen(_rep.nbuckets);
    click_hash_assert(_rep.nbuckets == libdivide_u32_recover(&_rep.bucket_divider));
#if defined(CLICK_HASH_ITERATOR_EPOCHS)
    _rep.epoch = 0;
#endif
    for (b = 0; b < _rep.nbuckets; ++b)
        _rep.buckets[b] = 0;
}
 
template <typename T, typename A>
HashContainer<T, A>::~HashContainer()
{
    CLICK_LFREE(_rep.buckets, sizeof(T *) * _rep.nbuckets);
}
 
template <typename T, typename A>
inline typename HashContainer<T, A>::bucket_count_type
HashContainer<T, A>::bucket(const key_type &key) const
{
    bucket_count_type h = hashcode(key);
    bucket_count_type d = libdivide_u32_do(h, &_rep.bucket_divider);
    bucket_count_type r = h - _rep.nbuckets * d;
    click_hash_assert(_rep.nbuckets == libdivide_u32_recover(&_rep.bucket_divider));
    click_hash_assert(r == h % _rep.nbuckets);
    return r;
}
 
template <typename T, typename A>
inline typename HashContainer<T, A>::const_iterator
HashContainer<T, A>::begin() const
{
    return const_iterator(this);
}
 
template <typename T, typename A>
inline typename HashContainer<T, A>::iterator
HashContainer<T, A>::begin()
{
    return iterator(this);
}
 
template <typename T, typename A>
inline typename HashContainer<T, A>::const_iterator
HashContainer<T, A>::end() const
{
    return const_iterator(this, -1, 0, 0);
}
 
template <typename T, typename A>
inline typename HashContainer<T, A>::iterator
HashContainer<T, A>::end()
{
    return iterator(this, -1, 0, 0);
}
 
template <typename T, typename A>
inline typename HashContainer<T, A>::iterator
HashContainer<T, A>::begin(bucket_count_type b)
{
    click_hash_assert(b < _rep.nbuckets);
    return iterator(this, b, &_rep.buckets[b], _rep.buckets[b]);
}
 
template <typename T, typename A>
inline typename HashContainer<T, A>::const_iterator
HashContainer<T, A>::begin(bucket_count_type b) const
{
    click_hash_assert(b < _rep.nbuckets);
    return const_iterator(this, b, &_rep.buckets[b], _rep.buckets[b]);
}
 
template <typename T, typename A>
inline bool HashContainer<T, A>::contains(const key_type& key) const
{
    bucket_count_type b = bucket(key);
    T **pprev;
    for (pprev = &_rep.buckets[b]; *pprev; pprev = &_rep.hashnext(*pprev))
        if (_rep.hashkeyeq(_rep.hashkey(*pprev), key))
            return true;
    return false;
}
 
template <typename T, typename A>
inline typename HashContainer<T, A>::size_type
HashContainer<T, A>::count(const key_type& key) const
{
    bucket_count_type b = bucket(key);
    size_t c = 0;
    T **pprev;
    for (pprev = &_rep.buckets[b]; *pprev; pprev = &_rep.hashnext(*pprev))
        c += _rep.hashkeyeq(_rep.hashkey(*pprev), key);
    return c;
}
 
template <typename T, typename A>
inline typename HashContainer<T, A>::iterator
HashContainer<T, A>::find(const key_type &key)
{
    bucket_count_type b = bucket(key);
    T **pprev;
    for (pprev = &_rep.buckets[b]; *pprev; pprev = &_rep.hashnext(*pprev))
        if (_rep.hashkeyeq(_rep.hashkey(*pprev), key))
            return iterator(this, b, pprev, *pprev);
    return iterator(this, b, &_rep.buckets[b], 0);
}
 
template <typename T, typename A>
inline typename HashContainer<T, A>::const_iterator
HashContainer<T, A>::find(const key_type &key) const
{
    return const_cast<HashContainer<T, A> *>(this)->find(key);
}
 
template <typename T, typename A>
inline typename HashContainer<T, A>::iterator
HashContainer<T, A>::find_prefer(const key_type &key)
{
    bucket_count_type b = bucket(key);
    T **pprev;
    for (pprev = &_rep.buckets[b]; *pprev; pprev = &_rep.hashnext(*pprev))
        if (_rep.hashkeyeq(_rep.hashkey(*pprev), key)) {
            T *element = *pprev;
            *pprev = _rep.hashnext(element);
            _rep.hashnext(element) = _rep.buckets[b];
            _rep.buckets[b] = element;
#if defined(CLICK_HASH_ITERATOR_EPOCHS)
            ++_rep.epoch;
#endif
            return iterator(this, b, &_rep.buckets[b], element);
        }
    return iterator(this, b, &_rep.buckets[b], 0);
}
 
template <typename T, typename A>
inline T *HashContainer<T, A>::get(const key_type &key) const
{
    return find(key).get();
}
 
template <typename T, typename A>
T *HashContainer<T, A>::set(iterator &it, T *element, bool balance)
{
    click_hash_assert(it._hc == this && it._bucket < _rep.nbuckets);
    click_hash_assert(bucket(_rep.hashkey(element)) == it._bucket);
    click_hash_assert(!it._element || _rep.hashkeyeq(_rep.hashkey(element), _rep.hashkey(it._element)));
    T *old = it.get();
    if (unlikely(old == element))
        return old;
    if (!element) {
        --_rep.size;
        if (!(*it._pprev = it._element = _rep.hashnext(old)))
            ++it;
#if defined(CLICK_HASH_ITERATOR_EPOCHS)
        ++_rep.epoch;
        it._epoch = _rep.epoch;
#endif
        return old;
    }
    if (old)
        _rep.hashnext(element) = _rep.hashnext(old);
    else {
        ++_rep.size;
        if (unlikely(unbalanced()) && balance) {
            rehash(bucket_count() + 1);
            it._bucket = bucket(_rep.hashkey(element));
            it._pprev = &_rep.buckets[it._bucket];
        }
        if (!(_rep.hashnext(element) = *it._pprev))
            _rep.first_bucket = 0;
    }
    *it._pprev = it._element = element;
#if defined(CLICK_HASH_ITERATOR_EPOCHS)
    ++_rep.epoch;
    it._epoch = _rep.epoch;
#endif
    return old;
}
 
template <typename T, typename A>
inline void HashContainer<T, A>::insert_at(iterator &it, T *element)
{
    click_hash_assert(it._hc == this && it._bucket < _rep.nbuckets);
    click_hash_assert(bucket(_rep.hashkey(element)) == it._bucket);
    ++_rep.size;
#if defined(CLICK_HASH_ITERATOR_EPOCHS)
    ++_rep.epoch;
#endif
    if (!(_rep.hashnext(element) = *it._pprev))
        _rep.first_bucket = 0;
    *it._pprev = element;
    it._pprev = &_rep.hashnext(element);
#if defined(CLICK_HASH_ITERATOR_EPOCHS)
    it._epoch = _rep.epoch;
#endif
}
 
template <typename T, typename A>
inline T *HashContainer<T, A>::set(T *element)
{
    iterator it = find(_rep.hashkey(element));
    return set(it, element);
}
 
template <typename T, typename A>
inline T *HashContainer<T, A>::erase(iterator &it)
{
    click_hash_assert(it._hc == this);
    return set(it, 0);
}
 
template <typename T, typename A>
inline T *HashContainer<T, A>::erase(const key_type &key)
{
    iterator it = find(key);
    return set(it, 0);
}
 
template <typename T, typename A>
inline void HashContainer<T, A>::clear()
{
#if defined(CLICK_HASH_ITERATOR_EPOCHS)
    ++_rep.epoch;
#endif
    for (bucket_count_type b = 0; b < _rep.nbuckets; ++b)
        _rep.buckets[b] = 0;
    _rep.size = 0;
}
 
template <typename T, typename A>
inline void HashContainer<T, A>::swap(HashContainer<T, A> &o)
{
    HashContainer_rep<T, A> rep(_rep);
    _rep = o._rep;
    o._rep = rep;
}
 
template <typename T, typename A>
void HashContainer<T, A>::rehash(bucket_count_type n)
{
#if defined(CLICK_HASH_ITERATOR_EPOCHS)
    ++_rep.epoch;
#endif
    bucket_count_type new_nbuckets = 1;
    while (new_nbuckets < n && new_nbuckets < max_bucket_count)
        new_nbuckets = ((new_nbuckets + 1) << 1) - 1;
    click_hash_assert(new_nbuckets > 0 && new_nbuckets <= max_bucket_count);
    if (_rep.nbuckets == new_nbuckets)
        return;
 
    T **new_buckets = (T **) CLICK_LALLOC(sizeof(T *) * new_nbuckets);
    for (bucket_count_type b = 0; b < new_nbuckets; ++b)
        new_buckets[b] = 0;
 
    bucket_count_type old_nbuckets = _rep.nbuckets;
    T **old_buckets = _rep.buckets;
    _rep.nbuckets = new_nbuckets;
    _rep.buckets = new_buckets;
    _rep.first_bucket = 0;
    _rep.bucket_divider = libdivide_u32_gen(_rep.nbuckets);
    click_hash_assert(_rep.nbuckets == libdivide_u32_recover(&_rep.bucket_divider));
 
    for (size_t b = 0; b < old_nbuckets; b++)
        for (T *element = old_buckets[b]; element; ) {
            T *next = _rep.hashnext(element);
            bucket_count_type new_b = bucket(_rep.hashkey(element));
            _rep.hashnext(element) = new_buckets[new_b];
            new_buckets[new_b] = element;
            element = next;
        }
 
    CLICK_LFREE(old_buckets, sizeof(T *) * old_nbuckets);
}
 
template <typename T, typename A>
inline bool
operator==(const HashContainer_const_iterator<T, A> &a, const HashContainer_const_iterator<T, A> &b)
{
    click_hash_assert(a.hashcontainer() == b.hashcontainer());
    return a.get() == b.get();
}
 
template <typename T, typename A>
inline bool
operator!=(const HashContainer_const_iterator<T, A> &a, const HashContainer_const_iterator<T, A> &b)
{
    click_hash_assert(a.hashcontainer() == b.hashcontainer());
    return a.get() != b.get();
}
 
CLICK_ENDDECLS
#endif