hashtable.hh

Go to the documentation of this file.

#ifndef CLICK_HASHTABLE_HH
#define CLICK_HASHTABLE_HH
/*
 * hashtable.hh -- HashTable template
 * Eddie Kohler
 *
 * Copyright (c) 2008 Meraki, Inc.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software")
 * to deal in the Software without restriction, subject to the conditions
 * listed in the Click LICENSE file. These conditions include: you must
 * preserve this copyright notice, and you cannot mention the copyright
 * holders in advertising related to the Software without their permission.
 * The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This
 * notice is a summary of the Click LICENSE file; the license in that file is
 * legally binding.
 */
#include <click/pair.hh>
#include <click/hashcontainer.hh>
#include <click/hashallocator.hh>
CLICK_DECLS
 
template <typename K, typename V = void> class HashTable;
template <typename T> class HashTable_iterator;
template <typename T> class HashTable_const_iterator;
 
template <typename T>
class HashTable<T> {
 
    struct elt {
        T v;
        elt *_hashnext;
        elt(const T &v_)
            : v(v_) {
        }
        typedef typename T::key_type key_type;
        typedef typename T::key_const_reference key_const_reference;
        key_const_reference hashkey() const {
            return v.hashkey();
        }
    };
 
    typedef HashContainer<elt> rep_type;
 
  public:
 
    typedef typename T::key_type key_type;
 
    typedef typename T::key_const_reference key_const_reference;
 
    typedef T value_type;
 
    typedef typename rep_type::size_type size_type;
 
    typedef typename rep_type::bucket_count_type bucket_count_type;
 
 
    HashTable()
        : _rep() {
    }
 
    explicit HashTable(bucket_count_type n)
        : _rep(n) {
    }
 
    HashTable(const HashTable<T> &x)
        : _rep(x._rep.bucket_count()) {
        clone_elements(x);
    }
 
#if HAVE_CXX_RVALUE_REFERENCES
    HashTable(HashTable<T> &&x)
        : _rep() {
        x.swap(*this);
    }
#endif
 
    ~HashTable();
 
 
    inline size_type size() const {
        return _rep.size();
    }
 
    inline bool empty() const {
        return _rep.empty();
    }
 
    inline bucket_count_type bucket_count() const {
        return _rep.bucket_count();
    }
 
    inline size_type bucket_size(bucket_count_type n) const {
        return _rep.bucket_size(n);
    }
 
 
    typedef HashTable_const_iterator<T> const_iterator;
    typedef HashTable_iterator<T> iterator;
 
    inline iterator begin();
    inline const_iterator begin() const;
 
    inline iterator end();
    inline const_iterator end() const;
 
 
    inline size_type count(key_const_reference key) const;
 
    inline iterator find(key_const_reference key);
    inline const_iterator find(key_const_reference key) const;
 
    inline iterator find_prefer(key_const_reference key);
 
    inline iterator find_insert(key_const_reference key);
 
    inline value_type &operator[](key_const_reference key);
 
    inline iterator find_insert(const value_type &value);
 
    bool set(const value_type &value);
 
    iterator erase(const iterator &it);
 
    size_type erase(const key_type &key);
 
    void clear();
 
 
    void swap(HashTable<T> &x);
 
 
    void rehash(bucket_count_type n) {
        _rep.rehash(n);
    }
 
 
    HashTable<T> &operator=(const HashTable<T> &x);
 
#if HAVE_CXX_RVALUE_REFERENCES
    inline HashTable<T> &operator=(HashTable<T> &&x) {
        x.swap(*this);
        return *this;
    }
#endif
 
  private:
 
    rep_type _rep;
    SizedHashAllocator<sizeof(elt)> _alloc;
 
    void clone_elements(const HashTable<T> &);
    void copy_elements(const HashTable<T> &);
 
    friend class HashTable_iterator<T>;
    friend class HashTable_const_iterator<T>;
    template <typename K, typename V> friend class HashTable;
 
};
 
template <typename T>
class HashTable_const_iterator { public:
 
    HashTable_const_iterator() {
    }
 
    const T *get() const {
        if (_rep)
            return &_rep.get()->v;
        else
            return 0;
    }
 
    const T *operator->() const {
        return &_rep.get()->v;
    }
 
    const T &operator*() const {
        return _rep.get()->v;
    }
 
    typename HashTable<T>::key_const_reference key() const {
        return _rep.get()->hashkey();
    }
 
    bool live() const {
        return (bool) _rep;
    }
 
    typedef bool (HashTable_const_iterator::*unspecified_bool_type)() const;
    inline operator unspecified_bool_type() const {
        return _rep ? &HashTable_const_iterator::live : 0;
    }
 
    void operator++(int) {
        _rep++;
    }
 
    void operator++() {
        ++_rep;
    }
 
  private:
 
    typename HashTable<T>::rep_type::const_iterator _rep;
 
    inline HashTable_const_iterator(const typename HashTable<T>::rep_type::const_iterator &i)
        : _rep(i) {
    }
 
    friend class HashTable<T>;
    friend class HashTable_iterator<T>;
 
};
 
template <typename T>
class HashTable_iterator : public HashTable_const_iterator<T> { public:
 
    typedef HashTable_const_iterator<T> inherited;
 
    HashTable_iterator() {
    }
 
    T *get() const {
        return const_cast<T *>(inherited::get());
    }
 
    inline T *operator->() const {
        return const_cast<T *>(inherited::operator->());
    }
 
    inline T &operator*() const {
        return const_cast<T &>(inherited::operator*());
    }
 
  private:
 
    inline HashTable_iterator(const typename HashTable<T>::rep_type::const_iterator &i)
        : inherited(i) {
    }
 
    friend class HashTable<T>;
 
};
 
template <typename K, typename V>
class HashTable_const_iterator<Pair<K, V> > { public:
 
    HashTable_const_iterator() {
    }
 
    const Pair<K, V> *get() const {
        if (_rep)
            return &_rep.get()->v;
        else
            return 0;
    }
 
    const Pair<K, V> *operator->() const {
        return &_rep.get()->v;
    }
 
    const Pair<K, V> &operator*() const {
        return _rep.get()->v;
    }
 
    const K &key() const {
        return operator*().first;
    }
 
    const V &value() const {
        return operator*().second;
    }
 
    bool live() const {
        return (bool) _rep;
    }
 
    typedef bool (HashTable_const_iterator::*unspecified_bool_type)() const;
    inline operator unspecified_bool_type() const {
        return _rep ? &HashTable_const_iterator::live : 0;
    }
 
    void operator++(int) {
        _rep++;
    }
 
    void operator++() {
        ++_rep;
    }
 
  private:
 
    typename HashTable<Pair<K, V> >::rep_type::const_iterator _rep;
 
    inline HashTable_const_iterator(const typename HashTable<Pair<K, V> >::rep_type::const_iterator &i)
        : _rep(i) {
    }
 
    friend class HashTable<Pair<K, V> >;
    friend class HashTable_iterator<Pair<K, V> >;
 
};
 
template <typename K, typename V>
class HashTable_iterator<Pair<K, V> > : public HashTable_const_iterator<Pair<K, V> > { public:
 
    typedef HashTable_const_iterator<Pair<K, V> > inherited;
 
    HashTable_iterator() {
    }
 
    Pair<K, V> *get() const {
        return const_cast<Pair<K, V> *>(inherited::get());
    }
 
    inline Pair<K, V> *operator->() const {
        return const_cast<Pair<K, V> *>(inherited::operator->());
    }
 
    inline Pair<K, V> &operator*() const {
        return const_cast<Pair<K, V> &>(inherited::operator*());
    }
 
    V &value() const {
        return operator*().second;
    }
 
  private:
 
    inline HashTable_iterator(const typename HashTable<Pair<K, V> >::rep_type::const_iterator &i)
        : inherited(i) {
    }
 
    friend class HashTable<Pair<K, V> >;
 
};
 
 
template <typename K, typename V>
class HashTable {
 
    typedef HashTable<Pair<const K, V> > rep_type;
 
  public:
 
    typedef K key_type;
 
    typedef const K &key_const_reference;
 
    typedef V mapped_type;
 
    typedef Pair<const K, V> value_type;
 
    typedef typename rep_type::size_type size_type;
 
    typedef typename rep_type::bucket_count_type bucket_count_type;
 
 
    HashTable()
        : _rep(), _default_value() {
    }
 
    explicit HashTable(const mapped_type &d)
        : _rep(), _default_value(d) {
    }
 
    HashTable(const mapped_type &d, bucket_count_type n)
        : _rep(n), _default_value(d) {
    }
 
    HashTable(const HashTable<K, V> &x)
        : _rep(x._rep), _default_value(x._default_value) {
    }
 
#if HAVE_CXX_RVALUE_REFERENCES
    HashTable(HashTable<K, V> &&x)
        : _rep(), _default_value() {
        x.swap(*this);
    }
#endif
 
    ~HashTable() {
    }
 
 
    inline size_type size() const {
        return _rep.size();
    }
 
    inline bool empty() const {
        return _rep.empty();
    }
 
    inline bucket_count_type bucket_count() const {
        return _rep.bucket_count();
    }
 
    inline size_type bucket_size(bucket_count_type n) const {
        return _rep.bucket_size(n);
    }
 
    inline const mapped_type &default_value() const {
        return _default_value;
    }
 
 
    typedef HashTable_const_iterator<value_type> const_iterator;
    typedef HashTable_iterator<value_type> iterator;
 
    inline iterator begin() {
        return _rep.begin();
    }
    inline const_iterator begin() const {
        return _rep.begin();
    }
 
    inline iterator end() {
        return _rep.end();
    }
    inline const_iterator end() const {
        return _rep.end();
    }
 
 
    inline size_type count(key_const_reference key) const {
        return _rep.count(key);
    }
 
    inline const_iterator find(key_const_reference key) const {
        return _rep.find(key);
    }
    inline iterator find(key_const_reference key) {
        return _rep.find(key);
    }
 
    inline iterator find_prefer(key_const_reference key) {
        return _rep.find_prefer(key);
    }
 
 
    const mapped_type &get(key_const_reference key) const {
        if (const_iterator i = find(key))
            return i.value();
        else
            return _default_value;
    }
 
    mapped_type *get_pointer(key_const_reference key) {
        if (iterator i = find(key))
            return &i.value();
        else
            return 0;
    }
    const mapped_type *get_pointer(key_const_reference key) const {
        if (const_iterator i = find(key))
            return &i.value();
        else
            return 0;
    }
 
    const mapped_type &operator[](key_const_reference key) const {
        if (const_iterator i = find(key))
            return i.value();
        else
            return _default_value;
    }
 
#if CLICK_HASHMAP_UPGRADE_WARNINGS
    inline mapped_type &operator[](key_const_reference key) CLICK_DEPRECATED;
#else
    inline mapped_type &operator[](key_const_reference key);
#endif
 
 
    inline iterator find_insert(key_const_reference key) {
        return _rep.find_insert(value_type(key, _default_value));
    }
 
    inline iterator find_insert(key_const_reference key,
                                const mapped_type &value) {
        return _rep.find_insert(value_type(key, value));
    }
 
 
    bool set(key_const_reference key, const mapped_type &value);
 
    bool replace(key_const_reference key, const mapped_type &value) CLICK_DEPRECATED;
 
    iterator erase(const iterator &it) {
        return _rep.erase(it);
    }
 
    size_type erase(key_const_reference key) {
        return _rep.erase(key);
    }
 
    void clear() {
        _rep.clear();
    }
 
 
    void swap(HashTable<K, V> &x) {
        _rep.swap(x._rep);
        click_swap(x._default_value, _default_value);
    }
 
 
    void rehash(bucket_count_type nb) {
        _rep.rehash(nb);
    }
 
 
    HashTable<K, V> &operator=(const HashTable<K, V> &x) {
        _rep = x._rep;
        _default_value = x._default_value;
        return *this;
    }
 
#if HAVE_CXX_RVALUE_REFERENCES
    HashTable<K, V> &operator=(HashTable<K, V> &&x) {
        x.swap(*this);
        return *this;
    }
#endif
 
  private:
 
    rep_type _rep;
    V _default_value;
 
};
 
 
 
template <typename T>
HashTable<T>::~HashTable()
{
    for (typename rep_type::iterator it = _rep.begin(); it; ) {
        elt *e = _rep.erase(it);
        e->v.~T();
        _alloc.deallocate(e);
    }
}
 
template <typename T>
inline typename HashTable<T>::const_iterator HashTable<T>::begin() const
{
    return const_iterator(_rep.begin());
}
 
template <typename T>
inline typename HashTable<T>::iterator HashTable<T>::begin()
{
    return iterator(_rep.begin());
}
 
template <typename T>
inline typename HashTable<T>::const_iterator HashTable<T>::end() const
{
    return const_iterator(_rep.end());
}
 
template <typename T>
inline typename HashTable<T>::iterator HashTable<T>::end()
{
    return iterator(_rep.end());
}
 
template <typename T>
inline typename HashTable<T>::size_type HashTable<T>::count(key_const_reference key) const
{
    return _rep.contains(key);
}
 
template <typename T>
inline HashTable_const_iterator<T> HashTable<T>::find(key_const_reference key) const
{
    return HashTable_const_iterator<T>(_rep.find(key));
}
 
template <typename T>
inline HashTable_iterator<T> HashTable<T>::find(key_const_reference key)
{
    return HashTable_iterator<T>(_rep.find(key));
}
 
template <typename T>
inline HashTable_iterator<T> HashTable<T>::find_prefer(key_const_reference key)
{
    return HashTable_iterator<T>(_rep.find_prefer(key));
}
 
template <typename T>
HashTable_iterator<T> HashTable<T>::find_insert(key_const_reference key)
{
    typename rep_type::iterator i = _rep.find(key);
    if (!i)
        if (elt *e = reinterpret_cast<elt *>(_alloc.allocate())) {
            new(reinterpret_cast<void *>(&e->v)) T(key);
            _rep.set(i, e, true);
        }
    return i;
}
 
template <typename T>
typename HashTable<T>::value_type &
HashTable<T>::operator[](key_const_reference key)
{
    return *find_insert(key);
}
 
template <typename T>
HashTable_iterator<T> HashTable<T>::find_insert(const value_type &v)
{
    typename rep_type::iterator i = _rep.find(hashkey(v));
    if (!i)
        if (elt *e = reinterpret_cast<elt *>(_alloc.allocate())) {
            new(reinterpret_cast<void *>(&e->v)) T(v);
            _rep.set(i, e, true);
        }
    return i;
}
 
template <typename T>
bool HashTable<T>::set(const value_type &value)
{
    typename rep_type::iterator i = _rep.find(hashkey(value));
    if (i)
        i->v = value;
    else if (elt *e = reinterpret_cast<elt *>(_alloc.allocate())) {
        new(reinterpret_cast<void *>(&e->v)) T(value);
        _rep.set(i, e, true);
        return true;
    }
    return false;
}
 
template <typename K, typename V>
bool HashTable<K, V>::set(const key_type &key, const mapped_type &value)
{
    typename rep_type::rep_type::iterator i = _rep._rep.find(key);
    if (i)
        i->v.second = value;
    else if (typename rep_type::elt *e = reinterpret_cast<typename rep_type::elt *>(_rep._alloc.allocate())) {
        new(reinterpret_cast<void *>(&e->v)) value_type(key, value);
        _rep._rep.set(i, e, true);
        return true;
    }
    return false;
}
 
template <typename T>
typename HashTable<T>::iterator HashTable<T>::erase(const iterator &it)
{
    iterator itx(it);
    if (elt *e = _rep.erase(reinterpret_cast<typename rep_type::iterator &>(itx._rep))) {
        e->v.~T();
        _alloc.deallocate(e);
    }
    return itx;
}
 
template <typename T>
typename HashTable<T>::size_type HashTable<T>::erase(const key_type &key)
{
    if (elt *e = _rep.erase(key)) {
        e->v.~T();
        _alloc.deallocate(e);
        return 1;
    } else
        return 0;
}
 
template <typename T>
void HashTable<T>::clone_elements(const HashTable<T> &o)
  // requires that 'this' is empty and has the same number of buckets as 'o'
{
    bucket_count_type b = (bucket_count_type) -1;
    typename rep_type::iterator j = _rep.end();
    for (typename rep_type::const_iterator i = o._rep.begin(); i; ++i) {
        if (b != i.bucket())
            j = _rep.begin((b = i.bucket()));
        if (elt *e = reinterpret_cast<elt *>(_alloc.allocate())) {
            new(reinterpret_cast<void *>(&e->v)) T(i->v);
            _rep.insert_at(j, e);
        }
    }
}
 
template <typename T>
void HashTable<T>::copy_elements(const HashTable<T> &o)
{
    for (typename rep_type::const_iterator i = o._rep.begin(); i; ++i)
        find_insert(i->v);
}
 
template <typename T>
HashTable<T> &HashTable<T>::operator=(const HashTable<T> &o)
{
    if (&o != this) {
        clear();
        if (_rep.bucket_count() < o._rep.bucket_count())
            _rep.rehash(o._rep.bucket_count());
        copy_elements(o);
    }
    return *this;
}
 
template <typename T>
void HashTable<T>::clear()
{
    for (typename rep_type::iterator it = _rep.begin(); it; ) {
        elt *e = _rep.erase(it);
        e->v.~T();
        _alloc.deallocate(e);
    }
}
 
template <typename T>
void HashTable<T>::swap(HashTable<T> &o)
{
    _rep.swap(o._rep);
    _alloc.swap(o._alloc);
}
 
template <typename K, typename V>
inline typename HashTable<K, V>::mapped_type &HashTable<K, V>::operator[](const key_type &key)
{
    return find_insert(key).value();
}
 
template <typename K, typename V>
bool HashTable<K, V>::replace(const key_type &key, const mapped_type &value)
{
    return set(key, value);
}
 
 
template <typename T>
inline bool operator==(const HashTable_const_iterator<T> &a, const HashTable_const_iterator<T> &b)
{
    return a.get() == b.get();
}
 
template <typename T>
inline bool operator!=(const HashTable_const_iterator<T> &a, const HashTable_const_iterator<T> &b)
{
    return a.get() != b.get();
}
 
 
template <typename K, typename V>
inline void click_swap(HashTable<K, V> &a, HashTable<K, V> &b)
{
    a.swap(b);
}
 
template <typename K, typename V>
inline void assign_consume(HashTable<K, V> &a, HashTable<K, V> &b)
{
    a.swap(b);
}
 
template <typename K, typename V>
inline void clear_by_swap(HashTable<K, V> &x)
{
    // specialization avoids losing x's default value
    HashTable<K, V> tmp(x.default_value());
    x.swap(tmp);
}
 
CLICK_ENDDECLS
#endif