roc::core::Hashmap< T, EmbeddedCapacity, OwnershipPolicy > Class Template Reference

Intrusive hash table. More...

#include <hashmap.h>

Inheritance diagram for roc::core::Hashmap< T, EmbeddedCapacity, OwnershipPolicy >:

Collaboration diagram for roc::core::Hashmap< T, EmbeddedCapacity, OwnershipPolicy >:

Public Types
typedef OwnershipPolicy< T >::Pointer	Pointer
	Pointer type. More...

Public Member Functions
	Hashmap ()
	Initialize empty hashmap without arena. More...
	Hashmap (IArena &arena)
	Initialize empty hashmap with arena. More...
	~Hashmap ()
	Release ownership of all elements. More...
size_t	capacity () const
	Get maximum number of elements that can be added to hashmap before grow() should be called. More...
size_t	size () const
	Get number of elements added to hashmap. More...
bool	is_empty () const
	Check if size is zero. More...
bool	contains (const T &element) const
	Check if element belongs to hashmap. More...
template<class Key >
Pointer	find (const Key &key) const
	Find element in the hashmap by key. More...
Pointer	front () const
	Get first element in hashmap. Elements are ordered by insertion. More...
Pointer	back () const
	Get last element in hashmap. Elements are ordered by insertion. More...
Pointer	nextof (T &element) const
	Get hashmap element next to given one. Elements are ordered by insertion. More...
ROC_ATTR_NODISCARD bool	insert (T &element)
	Insert element into hashmap. More...
void	remove (T &element)
	Remove element from hashmap. More...
ROC_ATTR_NODISCARD bool	grow ()
	Grow hashtable capacity. More...

Detailed Description

template<class T, size_t EmbeddedCapacity = 0, template< class TT > class OwnershipPolicy = RefCountedOwnership>
class roc::core::Hashmap< T, EmbeddedCapacity, OwnershipPolicy >

Intrusive hash table.

Characteristics: 1) Intrusive. Hash table nodes are stored directly in elements. No allocations are needed to insert a node. Arena is used only to allocate an array of buckets. 2) Collision-chaining. Implemented as an array of buckets, where a bucket is the head of a doubly-linked lists of bucket elements. 3) Controllable allocations. Allocations and deallocations are performed only when the hash table is explicitly growed. All other operations don't touch arena. 4) Zero allocations for small hash tables. A fixed number of buckets can be embedded directly into hash table object. 5) Incremental rehashing. After hash table growth, rehashing is performed incrementally when inserting and removing elements. The slower hash table size growth is, the less overhead rehashing adds to each operation. 6) Allows to iterate elements in insertion order. Implements safe iteration with regards to element insertion and deletion. Elements deleted during iteration won't be visited. Elements inserted during iteration will be visited.

Incremental rehashing technique is inspired by Go's map implementation, though there are differences. Load factor value is taken from it as well. Prime numbers for sizes are from https://planetmath.org/goodhashtableprimes.

Template Parameters

T	defines object type, it should inherit HashmapNode and additionally implement three methods:

// get object key
Key key() const;
 
// compute key hash
static core::hashsum_t key_hash(Key key);
 
// compare two keys for equality
static bool key_equal(Key key1, Key key2);

"Key" can be any type. Hashmap doesn't use it directly. It is never stored and is always accessed via the three methods above. The hash is computed for a key only once when an object is inserted into hash table.

Template Parameters

EmbeddedCapacity	defines the capacity embedded directly into Hashmap. It is used instead of dynamic memory while the number of elements is smaller than this capacity. The actual object size occupied to provide the requested capacity is implementation defined.
OwnershipPolicy	defines ownership policy which is used to acquire an element ownership when it's added to the hashmap and release ownership when it's removed from the hashmap.

Definition at line 83 of file hashmap.h.

Member Typedef Documentation

Pointer

template<class T , size_t EmbeddedCapacity = 0, template< class TT > class OwnershipPolicy = RefCountedOwnership>

typedef OwnershipPolicy<T>::Pointer roc::core::Hashmap< T, EmbeddedCapacity, OwnershipPolicy >::Pointer

Pointer type.

Remarks

either raw or smart pointer depending on the ownership policy.

Definition at line 88 of file hashmap.h.

Constructor & Destructor Documentation

Hashmap() [1/2]

template<class T , size_t EmbeddedCapacity = 0, template< class TT > class OwnershipPolicy = RefCountedOwnership>

roc::core::Hashmap< T, EmbeddedCapacity, OwnershipPolicy >::Hashmap ( )

inline

Initialize empty hashmap without arena.

Remarks

Hashmap capacity will be limited to the embedded capacity.

Definition at line 93 of file hashmap.h.

Hashmap() [2/2]

template<class T , size_t EmbeddedCapacity = 0, template< class TT > class OwnershipPolicy = RefCountedOwnership>

roc::core::Hashmap< T, EmbeddedCapacity, OwnershipPolicy >::Hashmap ( IArena &  arena )

inlineexplicit

Initialize empty hashmap with arena.

Remarks

Hashmap capacity may grow using arena.

Definition at line 100 of file hashmap.h.

~Hashmap()

template<class T , size_t EmbeddedCapacity = 0, template< class TT > class OwnershipPolicy = RefCountedOwnership>

roc::core::Hashmap< T, EmbeddedCapacity, OwnershipPolicy >::~Hashmap ( )

inline

Release ownership of all elements.

Definition at line 105 of file hashmap.h.

Member Function Documentation

back()

template<class T , size_t EmbeddedCapacity = 0, template< class TT > class OwnershipPolicy = RefCountedOwnership>

Pointer roc::core::Hashmap< T, EmbeddedCapacity, OwnershipPolicy >::back ( ) const

inline

Get last element in hashmap. Elements are ordered by insertion.

Returns

last element or NULL if hashmap is empty.

Definition at line 180 of file hashmap.h.

capacity()

template<class T , size_t EmbeddedCapacity = 0, template< class TT > class OwnershipPolicy = RefCountedOwnership>

size_t roc::core::Hashmap< T, EmbeddedCapacity, OwnershipPolicy >::capacity ( ) const

inline

Get maximum number of elements that can be added to hashmap before grow() should be called.

Definition at line 118 of file hashmap.h.

contains()

template<class T , size_t EmbeddedCapacity = 0, template< class TT > class OwnershipPolicy = RefCountedOwnership>

bool roc::core::Hashmap< T, EmbeddedCapacity, OwnershipPolicy >::contains ( const T &  element ) const

inline

Check if element belongs to hashmap.

Note

• has O(1) complexity
• doesn't compute key hashes

Definition at line 137 of file hashmap.h.

find()

template<class T , size_t EmbeddedCapacity = 0, template< class TT > class OwnershipPolicy = RefCountedOwnership>

template<class Key >

Pointer roc::core::Hashmap< T, EmbeddedCapacity, OwnershipPolicy >::find ( const Key &  key ) const

inline

Find element in the hashmap by key.

Returns

Pointer to the element with given key or NULL if it's not found.

Note

• has O(1) complexity in average and O(n) in the worst case
• computes key hash

The worst case is achieved when the hash function produces many collisions.

Definition at line 153 of file hashmap.h.

front()

template<class T , size_t EmbeddedCapacity = 0, template< class TT > class OwnershipPolicy = RefCountedOwnership>

Pointer roc::core::Hashmap< T, EmbeddedCapacity, OwnershipPolicy >::front ( ) const

inline

Get first element in hashmap. Elements are ordered by insertion.

Returns

first element or NULL if hashmap is empty.

Definition at line 168 of file hashmap.h.

grow()

template<class T , size_t EmbeddedCapacity = 0, template< class TT > class OwnershipPolicy = RefCountedOwnership>

ROC_ATTR_NODISCARD bool roc::core::Hashmap< T, EmbeddedCapacity, OwnershipPolicy >::grow ( )

inline

Grow hashtable capacity.

Remarks

Check if hash table is full (size is equal to capacity), and if so, increase hash table capacity and initiate incremental rehashing. Rehashing will be performed during subsequent insertions and removals.

Returns

• true if no growth needed or growth succeeded
• false if allocation failed

Note

• has O(1) complexity
• doesn't computes key hashes
• makes allocations and deallocations
• doesn't proceed lazy rehashing

Definition at line 272 of file hashmap.h.

insert()

template<class T , size_t EmbeddedCapacity = 0, template< class TT > class OwnershipPolicy = RefCountedOwnership>

ROC_ATTR_NODISCARD bool roc::core::Hashmap< T, EmbeddedCapacity, OwnershipPolicy >::insert ( T &  element )

inline

Insert element into hashmap.

Remarks

• acquires ownership of element

Returns

false if the allocation failed

Precondition

• element should not be member of any hashmap
• hashmap shouldn't have an element with the same key

Note

• has O(1) complexity in average and O(n) in the worst case
• computes key hash
• doesn't make allocations or deallocations
• proceedes lazy rehashing

Insertion speed is higher when insert to remove ratio is close to one or lower, and slows down when it becomes higher than one. The slow down is caused by the incremental rehashing algorithm.

Definition at line 228 of file hashmap.h.

is_empty()

template<class T , size_t EmbeddedCapacity = 0, template< class TT > class OwnershipPolicy = RefCountedOwnership>

bool roc::core::Hashmap< T, EmbeddedCapacity, OwnershipPolicy >::is_empty ( ) const

inline

Check if size is zero.

Definition at line 128 of file hashmap.h.

nextof()

template<class T , size_t EmbeddedCapacity = 0, template< class TT > class OwnershipPolicy = RefCountedOwnership>

Pointer roc::core::Hashmap< T, EmbeddedCapacity, OwnershipPolicy >::nextof ( T &  element ) const

inline

Get hashmap element next to given one. Elements are ordered by insertion.

Returns

hashmap element following element if element is not last, or NULL otherwise.

Precondition

element should be member of this hashmap.

Definition at line 197 of file hashmap.h.

remove()

template<class T , size_t EmbeddedCapacity = 0, template< class TT > class OwnershipPolicy = RefCountedOwnership>

void roc::core::Hashmap< T, EmbeddedCapacity, OwnershipPolicy >::remove ( T &  element )

inline

Remove element from hashmap.

Remarks

• releases ownership of element

Precondition

element should be member of this hashmap.

Note

• has O(1) complexity
• doesn't compute key hash
• doesn't make allocations or deallocations
• proceedes lazy rehashing

Definition at line 250 of file hashmap.h.

size()

template<class T , size_t EmbeddedCapacity = 0, template< class TT > class OwnershipPolicy = RefCountedOwnership>

size_t roc::core::Hashmap< T, EmbeddedCapacity, OwnershipPolicy >::size ( ) const

inline

Get number of elements added to hashmap.

Definition at line 123 of file hashmap.h.

---

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

• roc_core/hashmap.h