hashtable.hh

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

#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

/** @file <click/hashtable.hh>
 * @brief Click's hash table container template.
 */

template <typename K, typename V = void> class HashTable;
template <typename T> class HashTable_iterator;
template <typename T> class HashTable_const_iterator;

/** @class HashTable
  @brief Hash table template.

  The HashTable template implements a hash table or associative array suitable
  for use in the kernel or at user level.  Its interface is similar to C++'s
  map and unordered_map, although those types have more methods.

  Used with two template parameters, as HashTable<K, V>, the table maps keys K
  to values V.  Used with one template parameter, as HashTable<T>, HashTable
  is a hash set.  The type T must declare types named key_type and
  key_const_reference.  It also must declare a hashkey() member function
  returning type key_const_reference.  An object's hashkey() defines its key.

  HashTable is a chained hash table.  (Open coding is not
  appropriate in the kernel, where large contiguous memory allocations are
  essentially impossible.)  When run through Google's sparse_hash_table tests
  (April 2008, sparsehash-1.1), HashTable appears to perform slightly better
  than g++'s hash_map, better than sparse_hash_map, and worse than
  dense_hash_map; it takes less memory than hash_map and dense_hash_map.

  HashTable is faster than Click's prior HashMap class and has fewer potential
  race conditions in multithreaded use.  HashMap remains for backward
  compatibility but should not be used in new code.

  @warning HashMap users should beware of HashTable's operator[].  HashMap's
  operator[] returned a non-assignable const reference; it would never add an
  element to the hash table.  In contrast, the HashTable operator[]
  <em>may</em> add an element to the table.  (If added, the element will
  initially have the table's default value.)  For instance, consider:
  @code
  HashMap<String, int> h(0);
  h.insert("A", 1);
  if (!h["B"])      // Nota bene
      printf("B wasn't in table, and still isn't\n");
  for (HashMap<String, int>::iterator it = h.begin(); it; ++it)
      printf("%s -> %d\n", it.key().c_str(), it.value());
                    // Prints  B wasn't in table, and still isn't
                    //         A -> 1
  @endcode

  @warning Here the h["B"] reference does not add an element to
  the hash table, as you can see from the iteration.  Similar HashTable code
  has a different result:
  @code
  HashTable<String, int> h(0);
  h["A"] = 1;
  if (!h["B"])      // Nota bene
      printf("B wasn't in table, but it is now\n");
  for (HashMap<String, int>::iterator it = h.begin(); it; ++it)
      printf("%s -> %d\n", it.key().c_str(), it.value());
                    // Prints  B wasn't in table, but it is now
                    //         A -> 1
                    //         B -> 0
  @endcode

  @warning If you don't want operator[] to add an element, either access
  operator[] through a const hash table, or use get():
  @code
  HashTable<String, int> h(0);
  if (!h.get("B"))
      printf("B wasn't in table, and still isn't\n");
  const HashTable<String, int> &const_h = h;
  if (!const_h["B"])
      printf("B wasn't in table, and still isn't\n");
  @endcode
*/
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:

    /** @brief Key type. */
    typedef typename T::key_type key_type;

    /** @brief Const reference to key type. */
    typedef typename T::key_const_reference key_const_reference;

    /** @brief Value type.  value_type::key_type must exist. */
    typedef T value_type;

    /** @brief Type of sizes (size(), bucket_count()). */
    typedef typename rep_type::size_type size_type;


    /** @brief Construct an empty hash table. */
    HashTable()
	: _rep() {
    }

    /** @brief Construct a hash table with at least @a n buckets.
     *
     * In kernel modules HashTable has a maximum bucket count, so
     * HashTable(n).bucket_count() might be less than @a n. */
    explicit HashTable(size_type n)
	: _rep(n) {
    }

    /** @brief Construct a hash table as a copy of @a x. */
    HashTable(const HashTable<T> &x)
	: _rep(x._rep.bucket_count()) {
	clone_elements(x);
    }

    /** @brief Destroy the hash table, freeing its memory. */
    ~HashTable();


    /** @brief Return the number of elements. */
    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. */
    inline size_type bucket_count() const {
	return _rep.bucket_count();
    }

    /** @brief Return the number of elements in hash 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);
    }


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

    /** @brief Return an iterator for the first element in the table.
     *
     * @node HashTable iterators return elements in random order. */
    inline iterator begin();
    /** @overload */
    inline const_iterator begin() const;

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


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

    /** @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.
     *
     * @note find_prefer() rearranges the ordering of a bucket, and therefore
     * invalidates outstanding iterators. */
    inline iterator find_prefer(key_const_reference key);

    /** @brief Ensure an element with key @a key and return its iterator.
     *
     * If an element with @a key already exists in the table, then, like
     * find(@a key), returns an iterator pointing at at element.  Otherwise,
     * find_insert adds a new value T(@a key) to the table and returns its
     * iterator.
     *
     * @note find_insert() may rebalance the hash table, and thus invalidates
     * outstanding iterators.
     *
     * @sa operator[] */
    inline iterator find_insert(key_const_reference key);

    /** @brief Ensure an element with key @a key and return its reference.
     *
     * If an element with @a key already exists in the table, then returns a
     * reference to that element.  Otherwise, adds a new value T(@a key) to
     * the table and returns a reference to the new element.
     *
     * @note operator[] may rebalance the hash table, and thus invalidates
     * outstanding iterators.
     *
     * @sa find_insert(key_const_reference) */
    inline value_type &operator[](key_const_reference key);

    /** @brief Ensure an element with key @a value.hashkey() and return its iterator.
     *
     * If an element with @a value.hashkey() already exists in the table,
     * then, like find(), returns an iterator pointing at at element.
     * Otherwise, find_insert adds a copy of @a value to the table and returns
     * its iterator.
     *
     * @note find_insert() may rebalance the hash table, and thus invalidates
     * outstanding iterators. */
    inline iterator find_insert(const value_type &value);

    /** @brief Add @a value to the table, replacing any element with that key.
     *
     * Inserts @a value into the table.  If an element with @a value.hashkey()
     * already exists in the table, then it is replaced, and the function
     * returns false.  Otherwise, a copy of @a value is added, and the
     * function returns true.
     *
     * @note set() may rebalance the hash table, and thus invalidates
     * outstanding iterators. */
    bool set(const value_type &value);

    /** @brief Remove the element indicated by @a it.
     * @return An iterator pointing at the next element remaining, or end()
     * if no such element exists. */
    iterator erase(const iterator &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);

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


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


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


    /** @brief Assign this hash table's contents to a copy of @a x. */
    HashTable<T> &operator=(const HashTable<T> &x);

  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;

};

/** @class HashTable_const_iterator
 * @brief The const_iterator type for HashTable. */
template <typename T>
class HashTable_const_iterator { public:

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

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

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

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

    /** @brief Return this element's key.
     * @pre *this != end() */
    typename HashTable<T>::key_const_reference key() const {
	return _rep.get()->hashkey();
    }

    /** @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++;
    }