hashtable.hh

Click is a modular router toolkit. To use it you ll need to know how to compile and install the sof

     *
     * @warning The overloaded operator[] on non-const hash tables may add an
     * element to the table.  If you don't want to add an element, either
     * access operator[] through a const hash table, or use get().  */
    const mapped_type &operator[](const key_type &key) const {
	if (const_iterator i = find(key))
	    return i.value();
	else
	    return _default_value;
    }

    /** @brief Return a reference to the value for @a key.
     *
     * The caller can assign the reference to change the value.  If no element
     * for @a key currently exists (find(@a key) == end()), adds a new element
     * with default_value() and returns a reference to that value.
     *
     * @note Inserting an element into a HashTable invalidates all existing
     * iterators. */
#if CLICK_HASHMAP_UPGRADE_WARNINGS
    inline mapped_type &operator[](const key_type &key) CLICK_DEPRECATED;
#else
    inline mapped_type &operator[](const key_type &key);
#endif


    /** @brief Ensure an element with key @a key and return its iterator.
     *
     * If an element with @a key already exists in the table, then find(@a
     * key) and find_insert(@a key) are equivalent.  Otherwise, find_insert
     * adds a new element with key @a key and value default_value() to the
     * table and returns its iterator.
     *
     * @note Inserting an element into a HashTable invalidates all existing
     * iterators. */
    inline iterator find_insert(const key_type &key) {
	return _rep.find_insert(value_type(key, _default_value));
    }

    /** @brief Ensure an element for key @a key and return its iterator.
     *
     * If an element with @a key already exists in the table, then find(@a
     * key) and find_insert(@a value) are equivalent.  Otherwise,
     * find_insert(@a key, @a value) adds a new element with key @a key and
     * value @a value to the table and returns its iterator.
     *
     * @note Inserting an element into a HashTable invalidates all existing
     * iterators. */
    inline iterator find_insert(const key_type &key, const mapped_type &value) {
	return _rep.find_insert(value_type(key, value));
    }


    /** @brief Set the mapping for @a key to @a value.
     *
     * If an element for @a key already exists in the table, then its value is
     * assigned to @a value and the function returns false.  Otherwise, a new
     * element mapping @a key to @a value is added and the function returns
     * true.
     *
     * The behavior is basically the same as "(*this)[@a key] = @a value".
     * (The difference is that if (*this)[@a key] is not already in the hash
     * table, the new @a value is constructed rather than assigned.)
     *
     * @note Inserting an element into a HashTable invalidates all existing
     * iterators. */
    bool set(const key_type &key, const mapped_type &value);

    /** @brief Set the mapping for @a key to @a value.
     *
     * This is a deprecated synonym for set().
     *
     * @deprecated Use set(). */
    bool replace(const key_type &key, const mapped_type &value) CLICK_DEPRECATED;

    /** @brief Remove the element indicated by @a it.
     * @return A valid iterator pointing at the next element remaining, or
     * end() if no such element exists. */
    iterator erase(const iterator &it) {
	return _rep.erase(it);
    }

    /** @brief Remove any element with @a key.
     *
     * Returns the number of elements removed, which is always 0 or 1. */
    size_type erase(const key_type &key) {
	return _rep.erase(key);
    }

    /** @brief Remove all elements.
     * @post size() == 0 */
    void clear() {
	_rep.clear();
    }


    /** @brief Swap the contents of this hash table and @a x. */
    void swap(HashTable<K, V> &x) {
	_rep.swap(x._rep);

	V odefault_value(_default_value);
	_default_value = x._default_value;
	x._default_value = odefault_value;
    }


    /** @brief Rehash the table, ensuring it contains at least @a n buckets.
     *
     * All existing iterators are invalidated.  If @a n < bucket_count(), this
     * function may make the hash table slower. */
    void rehash(size_type nb) {
	_rep.rehash(nb);
    }


    /** @brief Assign this hash table's contents to a copy of @a x. */
    HashTable<K, V> &operator=(const HashTable<K, V> &x) {
	_rep = x._rep;
	_default_value = x._default_value;
	return *this;
    }

  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 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'
{
    size_type b = (size_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);
}


/** @brief Compare two HashTable iterators for equality. */
template <typename T>
inline bool operator==(const HashTable_const_iterator<T> &a, const HashTable_const_iterator<T> &b)
{
    return a.get() == b.get();
}

/** @brief Compare two HashTable iterators for inequality. */
template <typename T>
inline bool operator!=(const HashTable_const_iterator<T> &a, const HashTable_const_iterator<T> &b)
{
    return a.get() != b.get();
}

CLICK_ENDDECLS
#endif