HashMap< T > Class Template Reference

Lock-free HashMap with 2^n slots. More...

#include <HashMap.hpp>

Classes
struct	Data
Public Member Functions
	HashMap (unsigned bits)
	Constructs a hashmap with 2^bits slots.
	HashMap (const HashMap< T > &other)
	Copy constructor.
	~HashMap ()
	Destructor.
unsigned	bits () const
	Returns the lg2 of the number of slots.
unsigned	size () const
	Returns the number of slots.
unsigned	count () const
	Returns number of objects stored.
bool	get (hash_t key, T &out) const
	Retrieves object with key.
void	put (hash_t key, const T &obj)
	Stores a (key, object) pair.
void	clear ()
	Clears the table.
void	operator= (const HashMap< T > &other)
	Copys other's data, overwriting everything in this table.
Private Member Functions
	BOOST_CLASS_REQUIRE (T, benzene, HashMapStateConcept)
void	CopyFrom (const HashMap< T > &other)
Private Attributes
unsigned	m_bits
	See bits().
unsigned	m_size
	See size().
unsigned	m_mask
	Equal to size() - 1.
volatile unsigned	m_count
	See count().
boost::scoped_array< volatile int >	m_used
	Index into m_allocated at which data for this slot is located; index is equal to EMPTY_SLOT if unused.
boost::scoped_array< Data >	m_allocated
	Allocated space for entries in the table.
Static Private Attributes
static const int	EMPTY_SLOT = -1

Detailed Description

template<typename T>
class HashMap< T >

Lock-free HashMap with 2^n slots.

Deletes and dynamic resizing are not supported. Thread-safe, so multiple threads can read/write data at the same time. Performs simple linear probing on hash collisions.

Requires gcc builtins for atomic access.

References:

Gao, H, Groote J.F., Hesselink W.H: <a href="http://www.cs.rug.nl/~wim/mechver/hashtable/index.html" Lock-free Dynamic Hash table with Open Addressing
Cliff Click Jr: <a href="http://blogs.azulsystems.com/cliff/2007/03/a_nonblocking_h.html" A Non-Blocking HashTable

Definition at line 52 of file HashMap.hpp.

Constructor & Destructor Documentation

template<typename T >

HashMap< T >::HashMap ( unsigned bits ) [inline]

Constructs a hashmap with 2^bits slots.

Definition at line 140 of file HashMap.hpp.

References HashMap< T >::clear().

template<typename T>

HashMap< T >::HashMap ( const HashMap< T > & other ) [inline]

Copy constructor.

Definition at line 152 of file HashMap.hpp.

References HashMap< T >::CopyFrom().

template<typename T >

HashMap< T >::~HashMap ( ) [inline]

Destructor.

Definition at line 164 of file HashMap.hpp.

Member Function Documentation

template<typename T >

unsigned HashMap< T >::bits ( ) const [inline]

Returns the lg2 of the number of slots.

Definition at line 169 of file HashMap.hpp.

References HashMap< T >::m_bits.

template<typename T>

HashMap< T >::BOOST_CLASS_REQUIRE	(	T	,
		benzene	,
		HashMapStateConcept
	)			`[private]`

template<typename T >

void HashMap< T >::clear ( ) [inline]

Clears the table.

Definition at line 241 of file HashMap.hpp.

References HashMap< T >::EMPTY_SLOT, HashMap< T >::m_count, HashMap< T >::m_size, and HashMap< T >::m_used.

Referenced by HashMap< T >::HashMap().

template<typename T>

void HashMap< T >::CopyFrom ( const HashMap< T > & other ) [inline, private]

Definition at line 249 of file HashMap.hpp.

References HashMap< T >::m_allocated, HashMap< T >::m_count, HashMap< T >::m_size, and HashMap< T >::m_used.

Referenced by HashMap< T >::HashMap(), and HashMap< T >::operator=().

template<typename T >

unsigned HashMap< T >::count ( ) const [inline]

Returns number of objects stored.

Definition at line 181 of file HashMap.hpp.

References HashMap< T >::m_count.

Referenced by MoHexPlayer::TryReuseSubtree().

template<typename T>

bool HashMap< T >::get	(	hash_t	key,
		T &	out
	)			const `[inline]`

Retrieves object with key.

Performs linear probing to find key.

Returns true on success.

Definition at line 188 of file HashMap.hpp.

References HashMap< T >::EMPTY_SLOT, hash_t, HashMap< T >::m_allocated, HashMap< T >::m_mask, HashMap< T >::m_size, and HashMap< T >::m_used.

Referenced by MoHexPlayer::CopyKnowledgeData(), HexUctState::ExecuteTreeMove(), and MoHexPlayer::TryReuseSubtree().

template<typename T>

void HashMap< T >::operator= ( const HashMap< T > & other ) [inline]

Copys other's data, overwriting everything in this table.

Definition at line 261 of file HashMap.hpp.

References HashMap< T >::CopyFrom().

template<typename T>

void HashMap< T >::put	(	hash_t	key,
		const T &	obj
	)			`[inline]`

Stores a (key, object) pair.

WILL ABORT IF TABLE IS FULL!

Issues a warning if table becomes 1/4th full.

Make sure the table is much larger (at least 4x larger) than the maximum amount of data you ever expect to store in this table. This is to reduce the number of probes on subsequent get() calls, as well as to avoid the need for dynamic resizing of the table.

This function can possibly create duplicate entries. This is because put() does not check the key of the slots it runs over while searching for an empty slot. So if two threads both write try to put() k1 at the same time, each will write to its own slot. Only the first slot written will ever be used by get().

Definition at line 211 of file HashMap.hpp.

References HashMap< T >::EMPTY_SLOT, hash_t, LogSevere(), LogWarning(), HashMap< T >::m_allocated, HashMap< T >::m_count, HashMap< T >::m_mask, HashMap< T >::m_size, and HashMap< T >::m_used.

Referenced by HexUctState::ComputeKnowledge(), and MoHexPlayer::CopyKnowledgeData().

template<typename T >

unsigned HashMap< T >::size ( ) const [inline]

Returns the number of slots.

Definition at line 175 of file HashMap.hpp.

References HashMap< T >::m_size.