#include <core/generics/hopscotch_table.hpp>

Classes
struct	const_iterator

struct	insert_iterator

struct	iterator

Public Types
typedef T	value_type
	The data type stored in the table.

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)

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.

bool	put (const T &t)

bool	put_do_not_overwrite (const T &t)

std::pair< bool, T >	get (const T &t) const

Detailed Description

template<typename T, typename Hash = _HOPSCOTCH_TABLE_DEFAULT_HASH, typename KeyEqual = std::equal_to<T>>
class turi::hopscotch_table< T, 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.

Template Parameters

T	The data type stored in the hash table
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 38 of file hopscotch_table.hpp.

Constructor & Destructor Documentation

◆ hopscotch_table()

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

turi::hopscotch_table< T, 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 119 of file hopscotch_table.hpp.

Member Function Documentation

◆ erase()

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

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

inline

Erases an entry pointed to by an iterator.

Definition at line 479 of file hopscotch_table.hpp.

◆ find() [1/2]

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

const_iterator turi::hopscotch_table< T, 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 451 of file hopscotch_table.hpp.

◆ find() [2/2]

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

iterator turi::hopscotch_table< T, 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 461 of file hopscotch_table.hpp.

◆ get()

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

std::pair<bool, T> turi::hopscotch_table< T, Hash, KeyEqual >::get ( 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 589 of file hopscotch_table.hpp.

◆ insert()

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

iterator turi::hopscotch_table< T, 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 429 of file hopscotch_table.hpp.

◆ insert_do_not_overwrite()

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

iterator turi::hopscotch_table< T, 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 440 of file hopscotch_table.hpp.

◆ put()

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

bool turi::hopscotch_table< T, Hash, KeyEqual >::put ( 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 566 of file hopscotch_table.hpp.

◆ put_do_not_overwrite()

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

bool turi::hopscotch_table< T, Hash, KeyEqual >::put_do_not_overwrite ( 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 576 of file hopscotch_table.hpp.

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

core/generics/hopscotch_table.hpp

Classes

Public Types

Public Member Functions

Detailed Description

template<typename T, typename Hash = _HOPSCOTCH_TABLE_DEFAULT_HASH, typename KeyEqual = std::equal_to<T>> class turi::hopscotch_table< T, Hash, KeyEqual >

Constructor & Destructor Documentation

◆ hopscotch_table()

Member Function Documentation

◆ erase()

◆ find() [1/2]

◆ find() [2/2]

◆ get()

◆ insert()

◆ insert_do_not_overwrite()

◆ put()

◆ put_do_not_overwrite()

template<typename T, typename Hash = _HOPSCOTCH_TABLE_DEFAULT_HASH, typename KeyEqual = std::equal_to<T>>
class turi::hopscotch_table< T, Hash, KeyEqual >