Intrusive hash table template. More...

#include <hashcontainer.hh>

Public Types
enum	{ max_bucket_count = 4194303 , initial_bucket_count = 63 }

typedef A::key_type	key_type
	Key type.

typedef T	value_type
	Value type.

typedef size_t	size_type
	Type of sizes.

typedef uint32_t	bucket_count_type
	Type of bucket counts.

typedef HashContainer_const_iterator< T, A >	const_iterator

typedef HashContainer_iterator< T, A >	iterator

Public Member Functions
	HashContainer ()
	Construct an empty HashContainer.

	HashContainer (bucket_count_type n)
	Construct an empty HashContainer with at least n buckets.

	~HashContainer ()
	Destroy the HashContainer.

size_type	size () const
	Return the number of elements stored.

bool	empty () const
	Return true iff size() == 0.

bucket_count_type	bucket_count () const
	Return the number of buckets.

size_type	bucket_size (bucket_count_type n) const
	Return the number of elements in bucket n.

bucket_count_type	bucket (const key_type &key) const
	Return the bucket number containing elements with key.

bool	unbalanced () const
	Return true if this HashContainer should be rebalanced.

iterator	begin ()
	Return an iterator for the first element in the container.

const_iterator	begin () const

iterator	end ()
	Return an iterator for the end of the container.

const_iterator	end () const

iterator	begin (bucket_count_type n)
	Return an iterator for the first element in bucket n.

const_iterator	begin (bucket_count_type n) const

bool	contains (const key_type &key) const
	Test if an element with key key exists in the table.

size_type	count (const key_type &key) const
	Return the number of elements with key key in the table.

iterator	find (const key_type &key)
	Return an iterator for an element with key, if any.

const_iterator	find (const key_type &key) const

iterator	find_prefer (const key_type &key)
	Return an iterator for an element with key key, if any.

T *	get (const key_type &key) const
	Return an element for key, if any.

void	insert_at (iterator &it, T *element)
	Insert an element at position it.

T *	set (iterator &it, T *element, bool balance=false)
	Replace the element at position it with element.

T *	set (T *element)
	Replace the element with element->hashkey() with element.

T *	erase (iterator &it)
	Remove the element at position it.

T *	erase (const key_type &key)
	Remove an element with hashkey key.

void	clear ()
	Removes all elements from the container.

void	swap (HashContainer< T, A > &x)
	Swaps the contents of *this and x.

void	rehash (bucket_count_type n)
	Rehash the table, ensuring it contains at least n buckets.

void	balance ()
	Rehash the table if it is unbalanced.

Detailed Description

template<typename T, typename A>
class HashContainer< T, A >

Intrusive hash table template.

The HashContainer template implements a hash table or associative array suitable for use in the kernel or at user level.

HashContainer is intrusive. This means it does not manage its contents' memory. While non-intrusive containers are more common in the STL, intrusive containers make it simple to store objects in more than one container at a time.

Unlike many hash tables HashContainer does not automatically grow itself to maintain good lookup performance. Its users are expected to call rehash() when appropriate. See unbalanced().

With the default adapter type (A), the template type T must:

Define a "key_type" type that supports equality.
Define a "key_const_reference" type, usually the same as "key_type."
Contain a member "T *_hashnext" accessible to HashContainer_adapter<T>.
Define a "hashkey()" member function that returns the relevant hash key. This function must have return type "key_const_reference."

These requirements can be changed by supplying a different A, or adapter, type.

HashContainer can store multiple elements with the same key, although this is not the normal use. An element stored in a HashContainer should not modify its key.

HashContainer is used to implement Click's HashTable template.

Member Typedef Documentation

◆ key_type

template<typename T , typename A >

typedef A::key_type HashContainer< T, A >::key_type

Key type.

◆ value_type

template<typename T , typename A >

typedef T HashContainer< T, A >::value_type

Value type.

Must meet the HashContainer requirements defined by type A.

◆ size_type

template<typename T , typename A >

typedef size_t HashContainer< T, A >::size_type

Type of sizes.

◆ bucket_count_type

template<typename T , typename A >

typedef uint32_t HashContainer< T, A >::bucket_count_type

Type of bucket counts.

Constructor & Destructor Documentation

◆ HashContainer() [1/2]

template<typename T , typename A >

HashContainer< T, A >::HashContainer ( )

Construct an empty HashContainer.

◆ HashContainer() [2/2]

template<typename T , typename A >

HashContainer< T, A >::HashContainer ( bucket_count_type n )

explicit

Construct an empty HashContainer with at least n buckets.

◆ ~HashContainer()

template<typename T , typename A >

HashContainer< T, A >::~HashContainer ( )

Destroy the HashContainer.

Member Function Documentation

◆ size()

template<typename T , typename A >

size_type HashContainer< T, A >::size ( ) const

inline

Return the number of elements stored.

◆ empty()

template<typename T , typename A >

bool HashContainer< T, A >::empty ( ) const

inline

Return true iff size() == 0.

◆ bucket_count()

template<typename T , typename A >

bucket_count_type HashContainer< T, A >::bucket_count ( ) const

inline

Return the number of buckets.

◆ bucket_size()

template<typename T , typename A >

size_type HashContainer< T, A >::bucket_size ( bucket_count_type n ) const

inline

Return the number of elements in bucket n.

◆ bucket()

template<typename T , typename A >

HashContainer< T, A >::bucket_count_type HashContainer< T, A >::bucket ( const key_type & key ) const

inline

Return the bucket number containing elements with key.

◆ unbalanced()

template<typename T , typename A >

bool HashContainer< T, A >::unbalanced ( ) const

inline

Return true if this HashContainer should be rebalanced.

◆ begin() [1/4]

template<typename T , typename A >

HashContainer< T, A >::iterator HashContainer< T, A >::begin ( )

inline

Return an iterator for the first element in the container.

Note: HashContainer iterators return elements in random order.

◆ begin() [2/4]

template<typename T , typename A >

HashContainer< T, A >::const_iterator HashContainer< T, A >::begin ( ) const

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ end() [1/2]

template<typename T , typename A >

HashContainer< T, A >::iterator HashContainer< T, A >::end ( )

inline

Return an iterator for the end of the container.

Invariant: end().live() == false

◆ end() [2/2]

template<typename T , typename A >

HashContainer< T, A >::const_iterator HashContainer< T, A >::end ( ) const

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ begin() [3/4]

template<typename T , typename A >

HashContainer< T, A >::iterator HashContainer< T, A >::begin ( bucket_count_type n )

inline

Return an iterator for the first element in bucket n.

◆ begin() [4/4]

template<typename T , typename A >

HashContainer< T, A >::const_iterator HashContainer< T, A >::begin ( bucket_count_type n ) const

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ contains()

template<typename T , typename A >

bool HashContainer< T, A >::contains ( const key_type & key ) const

inline

Test if an element with key key exists in the table.

◆ count()

template<typename T , typename A >

HashContainer< T, A >::size_type HashContainer< T, A >::count ( const key_type & key ) const

inline

Return the number of elements with key key in the table.

◆ find() [1/2]

template<typename T , typename A >

HashContainer< T, A >::iterator HashContainer< T, A >::find ( const key_type & key )

inline

Return an iterator for an element with key, if any.

If no element with key exists in the table, find() returns an iterator that compares equal to end(). However, this iterator is special, and can also be used to efficiently insert an element with key key. In particular, the return value of find() always has can_insert(), and can thus be passed to insert_at() or set(). (It will insert elements at the head of the relevant bucket.)

◆ find() [2/2]

template<typename T , typename A >

HashContainer< T, A >::const_iterator HashContainer< T, A >::find ( const key_type & key ) const

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ find_prefer()

template<typename T , typename A >

HashContainer< T, A >::iterator HashContainer< T, A >::find_prefer ( const key_type & key )

inline

Return an iterator for an element with key key, if any.

Like find(), but additionally moves any found element to the head of its bucket, possibly speeding up future lookups.

◆ get()

template<typename T , typename A >

T * HashContainer< T, A >::get ( const key_type & key ) const

inline

Return an element for key, if any.

Returns null if no element for key currently exists. Equivalent to find(key).get().

◆ insert_at()

template<typename T , typename A >

void HashContainer< T, A >::insert_at	(	iterator &	it,
		T *	element
	)

inline

Insert an element at position it.

Parameters

it	iterator
element	element

Precondition: it.can_insert(); it.bucket() == bucket(element->hashkey()); element != NULL; element is not already in the HashContainer

Inserts element at the position in the hash table indicated by it. For instance, if it == begin(n) for some bucket number n, then element becomes the first element in bucket n. Other elements in the bucket, if any, are chained along.

On return, it is updated to point immediately after element. If it was not live before, then it will not be live after.

Note: HashContainer never automatically rehashes itself, so element insertion leaves any existing iterators valid. For best performance, however, users must call balance() to resize the container when it becomes unbalanced().

◆ set() [1/2]

template<typename T , typename A >

T * HashContainer< T, A >::set	(	iterator &	it,
		T *	element,
		bool	balance = `false`
	)

Replace the element at position it with element.

Parameters

it	iterator
element	element (can be null)
balance	whether to balance the hash table

Returns: the previous value of it.get()

Precondition: it.can_insert(); it.bucket() == bucket(element->hashkey()); element is not already in the HashContainer

Replaces the element pointed to by it with element, and returns the former element. If element is null the former element is removed. If there is no former element then element is inserted. When inserting an element with balance true, set() may rebalance the hash table.

As a side effect, it is advanced to point at the newly inserted element. If element is null, then it is advanced to point at the next element as by ++it.

◆ set() [2/2]

template<typename T , typename A >

T * HashContainer< T, A >::set ( T * element )

inline

Replace the element with element->hashkey() with element.

Parameters

element element

Returns: the previous value of find(element->hashkey()).get()

Precondition: element is not already in the HashContainer

Finds an element with the same hashkey as element, removes it from the HashContainer, and replaces it with element. If there is no former element then element is inserted.

◆ erase() [1/2]

template<typename T , typename A >

T * HashContainer< T, A >::erase ( iterator & it )

inline

Remove the element at position it.

Parameters

it iterator

Returns: the previous value of it.get()

As a side effect, it is advanced to the next element as by ++it.

◆ erase() [2/2]

template<typename T , typename A >

T * HashContainer< T, A >::erase ( const key_type & key )

inline

Remove an element with hashkey key.

Returns: the element removed, if any

Roughly equivalent to erase(find(key)).

◆ clear()

template<typename T , typename A >

void HashContainer< T, A >::clear ( )

inline

Removes all elements from the container.

Postcondition: size() == 0

◆ swap()

template<typename T , typename A >

void HashContainer< T, A >::swap ( HashContainer< T, A > & x )

inline

Swaps the contents of *this and x.

◆ rehash()

template<typename T , typename A >

void HashContainer< T, A >::rehash ( bucket_count_type n )

Rehash the table, ensuring it contains at least n buckets.

If n < bucket_count(), this function may make the hash table slower.

Note: Rehashing invalidates all existing iterators.

◆ balance()

template<typename T , typename A >

void HashContainer< T, A >::balance ( )

inline

Rehash the table if it is unbalanced.

Note: Rehashing invalidates all existing iterators.

The documentation for this class was generated from the following file:

include/click/hashcontainer.hh

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ key_type

◆ value_type

◆ size_type

◆ bucket_count_type

Constructor & Destructor Documentation

◆ HashContainer() [1/2]

◆ HashContainer() [2/2]

◆ ~HashContainer()

Member Function Documentation

◆ size()

◆ empty()

◆ bucket_count()

◆ bucket_size()

◆ bucket()

◆ unbalanced()

◆ begin() [1/4]

◆ begin() [2/4]

◆ end() [1/2]

◆ end() [2/2]

◆ begin() [3/4]

◆ begin() [4/4]

◆ contains()

◆ count()

◆ find() [1/2]

◆ find() [2/2]

◆ find_prefer()

◆ get()

◆ insert_at()

◆ set() [1/2]

◆ set() [2/2]

◆ erase() [1/2]

◆ erase() [2/2]

◆ clear()

◆ swap()

◆ rehash()

◆ balance()