graphlab::hopscotch_table< T, Synchronized, Hash, KeyEqual > Class Template Reference

#include <graphlab/util/hopscotch_table.hpp>

List of all members.

Classes
struct	const_iterator
struct	insert_iterator
struct	iterator

Public Types
typedef T	value_type
	The data type stored in the table.
typedef size_t	size_type
typedef Hash	hasher
	The type of the hasher object.
typedef KeyEqual	equality_function
	The type of the equality tester.
typedef value_type *	pointer
	A pointer to the data type stored in the table.
typedef value_type &	reference
	A reference to the data type stored in the table.
typedef const value_type *	const_pointer
	A constant pointer to the data type stored in the table.
typedef const value_type &	const_reference
	A constant reference to the data type stored in the table.

Public Member Functions
	hopscotch_table (size_t len, Hash hashfun=Hash(), KeyEqual equalfun=KeyEqual())
hasher	hash_function () const
	Returns the hash function used by the hash table.
equality_function	key_eq () const
	Returns the equality function used by the hash table.
iterator	insert (const value_type &newdata)
iterator	insert_do_not_overwrite (const value_type &newdata)
const_iterator	find (const value_type &key) const
iterator	find (const value_type &key)
void	clear ()
bool	erase (iterator iter)
bool	erase (const value_type &key)
	Erases a entry matching a given value.
iterator	begin ()
	Returns an iterator to the start of the table.
const_iterator	begin () const
	Returns an iterator to the start of the table.
iterator	end ()
	Returns an iterator to the end of the table.
const_iterator	end () const
	Returns an iterator to the end of the table.
size_t	count (const value_type &v) const
	Returns 1 if the table contains a given element. 0 otherwise.
bool	contains (const value_type &v) const
	Returns true if the table contains a given element. false otherwise.
size_t	size () const
	Returns the number of elements in the table.
size_t	capacity () const
	Returns the capacity of the table.
float	load_factor () const
size_t	size_sync () const
	Returns the size of the hash table. Safe under parallel access.
size_t	capacity_sync () const
	Returns the capacity of the table.
float	load_factor_sync () const
hopscotch_table &	operator= (const hopscotch_table &other)
bool	put_sync (const T &t)
bool	put_do_not_overwrite_sync (const T &t)
std::pair< bool, T >	get_sync (const T &t) const
bool	erase_sync (const T &t)

---

Detailed Description

template<typename T, bool Synchronized = true, typename Hash = _HOPSCOTCH_TABLE_DEFAULT_HASH, typename KeyEqual = std::equal_to<T>>
class graphlab::hopscotch_table< T, Synchronized, Hash, KeyEqual >

This defines a hash table where each entry stores a fixed data type T. The data type T should be small and should preferably fit in a couple of words. This hash table is not resizeable. Use the hopscotch_map For a more general purpose table.

Safe access is guaranteed if you restrict to the functions suffixed with _sync.

Template Parameters:

T	The data type stored in the hash table
Synchronized	Defaults to True. If True, locking is used to ensure safe reads and writes to the hash table. Even under "Synchronized", the only operations which are safe for parallel access are all functions suffixed with "sync".
Hash	The hash functor type. Defaults to std::hash<T> if C++11 is available. Otherwise defaults to boost::hash<T>
KeyEqual	The functor used to identify object equality. Defaults to std::equal_to<T>

Definition at line 45 of file hopscotch_table.hpp.

---

Constructor & Destructor Documentation

template<typename T , bool Synchronized = true, typename Hash = _HOPSCOTCH_TABLE_DEFAULT_HASH, typename KeyEqual = std::equal_to<T>>

graphlab::hopscotch_table< T, Synchronized, Hash, KeyEqual >::hopscotch_table ( size_t  len, Hash  hashfun = Hash(), KeyEqual  equalfun = KeyEqual()  )

inline

Constructs a hopscotch table of a given length.

Parameters:

len	This rounded up to the next power of 2 will be used as the length of the table. This table is not resizeable.
hashfun	The hasher functor. Defaults to Hash()
equalfun	A functor used to test for equality. Defaults to KeyEqual()

Definition at line 133 of file hopscotch_table.hpp.

---

Member Function Documentation

template<typename T , bool Synchronized = true, typename Hash = _HOPSCOTCH_TABLE_DEFAULT_HASH, typename KeyEqual = std::equal_to<T>>

bool graphlab::hopscotch_table< T, Synchronized, Hash, KeyEqual >::erase ( iterator  iter )

inline

Erases an entry pointed to by an iterator.

Definition at line 544 of file hopscotch_table.hpp.

template<typename T , bool Synchronized = true, typename Hash = _HOPSCOTCH_TABLE_DEFAULT_HASH, typename KeyEqual = std::equal_to<T>>

bool graphlab::hopscotch_table< T, Synchronized, Hash, KeyEqual >::erase_sync ( const T &  t )

inline

Returns true if the erasure was successful. If false, the entry was not found in the hash table

Definition at line 708 of file hopscotch_table.hpp.

template<typename T , bool Synchronized = true, typename Hash = _HOPSCOTCH_TABLE_DEFAULT_HASH, typename KeyEqual = std::equal_to<T>>

const_iterator graphlab::hopscotch_table< T, Synchronized, Hash, KeyEqual >::find ( const value_type &  key ) const

inline

Searches for an entry and returns an iterator to the entry. KeyEqual will be used to identify if an entry matches the request. return end() on failure.

Definition at line 516 of file hopscotch_table.hpp.

template<typename T , bool Synchronized = true, typename Hash = _HOPSCOTCH_TABLE_DEFAULT_HASH, typename KeyEqual = std::equal_to<T>>

iterator graphlab::hopscotch_table< T, Synchronized, Hash, KeyEqual >::find ( const value_type &  key )

inline

Searches for an entry and returns an iterator to the entry. KeyEqual will be used to identify if an entry matches the request. return end() on failure.

Definition at line 526 of file hopscotch_table.hpp.

template<typename T , bool Synchronized = true, typename Hash = _HOPSCOTCH_TABLE_DEFAULT_HASH, typename KeyEqual = std::equal_to<T>>

std::pair<bool, T> graphlab::hopscotch_table< T, Synchronized, Hash, KeyEqual >::get_sync ( const T &  t ) const

inline

If the argument is found in the hash table, return {true, V} where V is the hash table content matching the argument. Otherwise {false, T()} is returned. KeyEqual() is used to compare entries. Safe under parallel access.

Definition at line 669 of file hopscotch_table.hpp.

template<typename T , bool Synchronized = true, typename Hash = _HOPSCOTCH_TABLE_DEFAULT_HASH, typename KeyEqual = std::equal_to<T>>

iterator graphlab::hopscotch_table< T, Synchronized, Hash, KeyEqual >::insert ( const value_type &  newdata )

inline

Inserts an entry into the array. Returns an iterator to the just inserted data on success. If the entry already exists, it will be overwritten. Returns end() on failure.

Definition at line 494 of file hopscotch_table.hpp.

template<typename T , bool Synchronized = true, typename Hash = _HOPSCOTCH_TABLE_DEFAULT_HASH, typename KeyEqual = std::equal_to<T>>

iterator graphlab::hopscotch_table< T, Synchronized, Hash, KeyEqual >::insert_do_not_overwrite ( const value_type &  newdata )

inline

Inserts an entry into the array. Returns an iterator to the just inserted data on success. This function check if the entry already exists, if it does, do nothing Returns end() on failure.

Definition at line 505 of file hopscotch_table.hpp.

template<typename T , bool Synchronized = true, typename Hash = _HOPSCOTCH_TABLE_DEFAULT_HASH, typename KeyEqual = std::equal_to<T>>

bool graphlab::hopscotch_table< T, Synchronized, Hash, KeyEqual >::put_do_not_overwrite_sync ( const T &  t )

inline

Inserts an element into the hash table. Safe under parallel access. if t already exists, nothing will happen

Definition at line 656 of file hopscotch_table.hpp.

template<typename T , bool Synchronized = true, typename Hash = _HOPSCOTCH_TABLE_DEFAULT_HASH, typename KeyEqual = std::equal_to<T>>

bool graphlab::hopscotch_table< T, Synchronized, Hash, KeyEqual >::put_sync ( const T &  t )

inline

Inserts an element into the hash table. Safe under parallel access. if t already exists, it will be overwritten

Definition at line 646 of file hopscotch_table.hpp.

---

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

• graphlab/util/hopscotch_table.hpp