JASS::hash_table< KEY, ELEMENT, BITS > Class Template Reference

Thread-safe hash table (without delete). More...

#include <hash_table.h>

Collaboration diagram for JASS::hash_table< KEY, ELEMENT, BITS >:

Classes
class	iterator
	Iterate over the hash table. More...

Public Member Functions
	hash_table (allocator &pool)
	Constructor. More...
	~hash_table ()
	Destructor.
iterator	begin () const
	Return an iterator pointing to the smallest element in the hash table. More...
iterator	end () const
	Return an iterator pointing past the end of the hash table. More...
void	text_render (std::ostream &stream) const
	Write the contents of this object to the output steam. More...
ELEMENT &	operator[] (const KEY &key)
	Return a reference to the element associated with the key. If there is no element the create an empty one. More...

Static Public Member Functions
static void	unittest (void)
	Unit test this class.

Static Protected Member Functions
static constexpr size_t	size (size_t bits)
	Return the size of the hash table (in elements) given the size of the hash table in 2^bits. More...

Protected Attributes
std::atomic< binary_tree< KEY, ELEMENT > * > *	table
	The hash table is just an array of binary trees.
allocator &	memory_pool
	The pool allocator.

Static Protected Attributes
static constexpr size_t	hash_table_size = size(BITS)
	The size of the hash table (in elements)

Related Functions
(Note that these are not member functions.)
template<typename A , typename B , size_t C>
std::ostream &	operator<< (std::ostream &stream, const hash_table< A, B, C > &tree)
	Output a human readable serialisation to an ostream.

Detailed Description

template<typename KEY, typename ELEMENT, size_t BITS = 24>
class JASS::hash_table< KEY, ELEMENT, BITS >

Thread-safe hash table (without delete).

The thread-safe hash table is implemented as an array of pointers to the thread-safe binary tree. The only way to access elements is with operator[], thus making it easier to access and easier to implement as thread safe. As a thread-safe lock-free structure using a pool allocator, its possible for there to be a leak if multiple threads try and allocate the same node (or same node in the same tree) at the same time. Destructors of ELEMENT and KEY are never called as all memory is managed by the pool allocator. There is no way to remove an element from the hash table once added.

Template Parameters

KEY	The type used as the key to the element (must include KEY(allocator, KEY) copy constructor).
ELEMENT	The element data returned given the key (must include ELEMENT(allocator) constructur).
BITS	The size of the hash table will be 2^BITS (must be 8, 16, or 24).

Constructor & Destructor Documentation

hash_table()

template<typename KEY, typename ELEMENT, size_t BITS = 24>

JASS::hash_table< KEY, ELEMENT, BITS >::hash_table ( allocator &  pool )

inline

Constructor.

Parameters

pool	[in] All memmory associated with this object is allocated using the pool.

Member Function Documentation

begin()

template<typename KEY, typename ELEMENT, size_t BITS = 24>

iterator JASS::hash_table< KEY, ELEMENT, BITS >::begin ( void  ) const

inline

Return an iterator pointing to the smallest element in the hash table.

Returns

Iterator pointing to smallest element in the hash table.

end()

template<typename KEY, typename ELEMENT, size_t BITS = 24>

iterator JASS::hash_table< KEY, ELEMENT, BITS >::end ( void  ) const

inline

Return an iterator pointing past the end of the hash table.

Returns

Iterator pointing past the end of the hash table.

operator[]()

template<typename KEY, typename ELEMENT, size_t BITS = 24>

ELEMENT& JASS::hash_table< KEY, ELEMENT, BITS >::operator[] ( const KEY &  key )

inline

Return a reference to the element associated with the key. If there is no element the create an empty one.

Parameters

key	[in] The key to look up.

Returns

The element associated with the key.

size()

template<typename KEY, typename ELEMENT, size_t BITS = 24>

static constexpr size_t JASS::hash_table< KEY, ELEMENT, BITS >::size ( size_t  bits )

inlinestaticprotected

Return the size of the hash table (in elements) given the size of the hash table in 2^bits.

as this method is evaluated at compile time, it calls static_assert() if bits is not value (it must be 8, 16, or 24).

Parameters

bits	[in] The size of the hash table is 2^bits

Returns

2^bits.

text_render()

template<typename KEY, typename ELEMENT, size_t BITS = 24>

void JASS::hash_table< KEY, ELEMENT, BITS >::text_render ( std::ostream &  stream ) const

inline

Write the contents of this object to the output steam.

Parameters

stream

[in] The stream to write to.

---

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

• source/hash_table.h