hashtable.hh

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

    /** @brief Advance this iterator to the next element. */
    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>;

};

/** @class HashTable_iterator
  @brief The iterator type for HashTable.

  These iterators apply to HashTable classes that store either a unified
  key-value pair (HashTable<T>), or to HashTable classes that map keys to
  explicit values (HashTable<K, V>).

  Iterators for HashTable<K, V> objects have additional methods.  Given
  HashTable<K, V>::iterator it:

  <ul>
  <li>*it has type Pair<const K, V>.</li>
  <li>it.key() returns the associated key, and is equivalent to it->first.</li>
  <li>it.value() returns the associated value, and is equivalent to
    it->second.</li>
  <li>it.value() is a mutable reference for iterator objects and a const
    reference for const_iterator objects.</li>
  </ul>
*/
template <typename T>
class HashTable_iterator : public HashTable_const_iterator<T> { public:

    typedef HashTable_const_iterator<T> inherited;

    /** @brief Construct an uninitialized iterator. */
    HashTable_iterator() {
    }

    /** @brief Return a pointer to the element, null if *this == end(). */
    T *get() const {
	return const_cast<T *>(inherited::get());
    }

    /** @brief Return a pointer to the element, null if *this == end(). */
    inline T *operator->() const {
	return const_cast<T *>(inherited::operator->());
    }

    /** @brief Return a reference to the element.
     * @pre *this != end() */
    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>;

};

/** @class HashTable_const_iterator
 * @brief The const_iterator type for HashTable. */
template <typename K, typename V>
class HashTable_const_iterator<Pair<K, V> > { public:

    /** @brief Construct an uninitialized iterator. */
    HashTable_const_iterator() {
    }

    /** @brief Return a pointer to the element, null if *this == end(). */
    const Pair<K, V> *get() const {
	if (_rep)
	    return &_rep.get()->v;
	else
	    return 0;
    }

    /** @brief Return a pointer to the element, null if *this == end(). */
    const Pair<K, V> *operator->() const {
	return get();
    }

    /** @brief Return a reference to the element.
     * @pre *this != end() */
    const Pair<K, V> &operator*() const {
	return _rep.get()->v;
    }

    /** @brief Return a reference to the element's key.
     * @return get()->first */
    const K &key() const {
	return get()->first;
    }

    /** @brief Return a reference to the element's value.
     * @return get()->second */
    const V &value() const {
	return get()->second;
    }

    /** @brief Return true iff *this != end(). */
    bool live() const {
	return (bool) _rep;
    }

    typedef bool (HashTable_const_iterator::*unspecified_bool_type)() const;
    /** @brief Return true iff *this != end(). */
    inline operator unspecified_bool_type() const {
	return _rep ? &HashTable_const_iterator::live : 0;
    }

    /** @brief Advance this iterator to the next element. */
    void operator++(int) {
	_rep++;
    }

    /** @brief Advance this iterator to the next element. */
    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> >;

};

/** @class HashTable_iterator
 * @brief The iterator type for HashTable. */
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;

    /** @brief Construct an uninitialized iterator. */
    HashTable_iterator() {
    }

    /** @brief Return a pointer to the element, null if *this == end(). */
    Pair<K, V> *get() const {
	return const_cast<Pair<K, V> *>(inherited::get());
    }

    /** @brief Return a pointer to the element, null if *this == end(). */
    inline Pair<K, V> *operator->() const {
	return get();
    }

    /** @brief Return a reference to the element.
     * @pre *this != end() */
    inline Pair<K, V> &operator*() const {
	return const_cast<Pair<K, V> &>(inherited::operator*());
    }

    /** @brief Return a mutable reference to the element's value.
     * @return get()->second */
    V &value() const {
	return get()->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:

    /** @brief Key type. */
    typedef K key_type;

    /** @brief Const reference to key type. */
    typedef const K &key_const_reference;

    /** @brief Value type. */
    typedef V mapped_type;

    /** @brief Pair of key type and value type. */
    typedef Pair<const K, V> value_type;

    /** @brief Type of sizes. */
    typedef typename rep_type::size_type size_type;


    /** @brief Construct an empty hash table with normal default value. */
    HashTable()
	: _rep(), _default_value() {
    }

    /** @brief Construct an empty hash table with default value @a d. */
    explicit HashTable(const mapped_type &d)
	: _rep(), _default_value(d) {
    }

    /** @brief Construct an empty hash table with at least @a n buckets.
     * @param d default value
     * @param n minimum number of buckets */
    HashTable(const mapped_type &d, size_type n)
	: _rep(n), _default_value(d) {
    }

    /** @brief Construct a hash table as a copy of @a x. */
    HashTable(const HashTable<K, V> &x)
	: _rep(x._rep), _default_value(x._default_value) {
    }

    /** @brief Destroy this hash table, freeing its memory. */
    ~HashTable() {
    }


    /** @brief Return the number of elements in the hash table. */
    inline size_type size() const {
	return _rep.size();
    }

    /** @brief Return true iff size() == 0. */
    inline bool empty() const {
	return _rep.empty();
    }

    /** @brief Return the number of buckets in the hash table. */
    inline size_type bucket_count() const {
	return _rep.bucket_count();
    }

    /** @brief Return the number of elements in bucket @a n.
     * @param n bucket number, >= 0 and < bucket_count() */
    inline size_type bucket_size(size_type n) const {
	return _rep.bucket_size(n);
    }

    /** @brief Return the hash table's default value.
     *
     * The default value is returned by operator[]() when a key does not
     * exist. */
    inline const mapped_type &default_value() const {
	return _default_value;
    }


    typedef HashTable_const_iterator<value_type> const_iterator;
    typedef HashTable_iterator<value_type> iterator;

    /** @brief Return an iterator for the first element in the table.
     *
     * @note HashTable iterators return elements in undefined order. */
    inline iterator begin() {
	return _rep.begin();
    }
    /** @overload */
    inline const_iterator begin() const {
	return _rep.begin();
    }

    /** @brief Return an iterator for the end of the table.
     * @invariant end().live() == false */
    inline iterator end() {
	return _rep.end();
    }
    /** @overload */
    inline const_iterator end() const {
	return _rep.end();
    }


    /** @brief Return an iterator for the element with key @a key, if any.
     *
     * Returns end() if no such element exists. */
    inline const_iterator find(const key_type &key) const {
	return _rep.find(key);
    }
    /** @overload */
    inline iterator find(const key_type &key) {
	return _rep.find(key);
    }

    /** @brief Return an iterator for the element with key @a key, if any.
     *
     * Like find(), but additionally moves the found element to the head of
     * its bucket, possibly speeding up future lookups. */
    inline iterator find_prefer(const key_type &key) {
	return _rep.find_prefer(key);
    }


    /** @brief Return the value for @a key.
     *
     * If no element for @a key currently exists (find(@a key) == end()),
     * returns default_value(). */
    const mapped_type &get(const key_type &key) const {
	if (const_iterator i = find(key))
	    return i.value();
	else
	    return _default_value;
    }

    /** @brief Return a pointer to the value for @a key.
     *
     * If no element for @a key currently exists (find(@a key) == end()),
     * returns null. */
    mapped_type *get_pointer(const key_type &key) {
	if (iterator i = find(key))
	    return &i.value();
	else
	    return 0;
    }
    /** @overload */
    const mapped_type *get_pointer(const key_type &key) const {
	if (const_iterator i = find(key))
	    return &i.value();
	else
	    return 0;
    }

    /** @brief Return the value for @a key.
     *
     * If no element for @a key currently exists (find(@a key) == end()),
     * returns default_value().