Hash table that stores multiple values per key. More...

#include <hash_multivalue.h>

Inherits CudaHT::CuckooHashing::HashTable.

Public Member Functions
virtual bool	Build (const unsigned input_size, const unsigned d_keys, const unsigned d_vals)
	Build the multi-value hash table. More...

virtual void	Release ()
	Free all memory.

virtual void	Retrieve (const unsigned, const unsigned , unsigned )
	Don't call this. More...

virtual void	Retrieve (const unsigned n_queries, const unsigned d_keys, uint2 d_location_counts)
	Retrieve from a multi-value hash table. More...

const unsigned *	get_all_values () const
	Returns the array of values, where each key's values are stored contiguously in memory.

unsigned	get_values_size () const
	Gets the total number of values between all of the keys.

const uint2 *	get_index_counts () const
	Gets the location and number of values each key has.

virtual bool	Initialize (const unsigned max_input_size, const float space_usage=1.2, const unsigned num_functions=4)
	Initializes the multi-value hash table's memory. More...

Public Member Functions inherited from CudaHT::CuckooHashing::HashTable
unsigned	get_table_size () const
	Returns how many slots the hash table has.

unsigned	get_stash_count () const
	Returns how many items are stored in the stash.

uint2	get_stash_constants () const
	Returns the constants used by the stash.

const Entry *	get_contents () const
	Returns the hash table contents.

unsigned	get_num_hash_functions () const
	Returns the number of hash functions being used.

Functions< 2 >	get_constants_2 () const
	When using two hash functions, returns the constants.

Functions< 3 >	get_constants_3 () const
	When using three hash functions, returns the constants.

Functions< 4 >	get_constants_4 () const
	When using four hash functions, returns the constants.

Functions< 5 >	get_constants_5 () const
	When using five hash functions, returns the constants.

void	setTheCudpp (CUDPPHandle theCudpp_)
	Set the internal CUDPP instance.

Additional Inherited Members
Protected Attributes inherited from CudaHT::CuckooHashing::HashTable
unsigned	table_size_
	Size of the hash table.

unsigned	num_hash_functions_
	Number of hash functions being used.

Entry *	d_contents_
	Device memory: The hash table contents. The stash is stored at the end.

unsigned	stash_count_
	Number of key-value pairs currently stored.

uint2	stash_constants_
	Hash function constants for the stash.

Functions< 2 >	constants_2_
	Constants for a set of two hash functions.

Functions< 3 >	constants_3_
	Constants for a set of three hash functions.

Functions< 4 >	constants_4_
	Constants for a set of four hash functions.

Functions< 5 >	constants_5_
	Constants for a set of five hash functions.

unsigned *	d_failures_
	Device memory: General use error flag.

CUDPPHandle	theCudpp
	CUDPP instance.

Detailed Description

Hash table that stores multiple values per key.

A key with multiple values is represented by multiple key-value pairs in the input with the same key.

Querying the structure returns how many items the key has and its location in the array returned by get_all_values().

Member Function Documentation

bool CudaHT::CuckooHashing::MultivalueHashTable::Build	(	const unsigned	input_size,
		const unsigned *	d_keys,
		const unsigned *	d_vals
	)

virtual

Build the multi-value hash table.

See HashTable::Build() for an explanation of the parameters. Key-value pairs in the input with the same key are assumed to be values associated with the same key.

Parameters

[in]	input_size	Number of key-value pairs being inserted.
[in]	d_keys	Device memory array containing all of the input keys.
[in]	d_vals	Device memory array containing the keys' values.

Returns: Whether the hash table was built successfully (true) or not (false).

See also: HashTable::Build()

Reimplemented from CudaHT::CuckooHashing::HashTable.

virtual void CudaHT::CuckooHashing::MultivalueHashTable::Retrieve	(	const unsigned	,
		const unsigned *	,
		unsigned *
	)

inlinevirtual

Don't call this.

Todo:: Remove this function entirely somehow.

Reimplemented from CudaHT::CuckooHashing::HashTable.

void CudaHT::CuckooHashing::MultivalueHashTable::Retrieve	(	const unsigned	n_queries,
		const unsigned *	d_keys,
		uint2 *	d_location_counts
	)

virtual

Retrieve from a multi-value hash table.

Parameters

[in]	n_queries	Number of queries in the input.
[in]	d_keys	Device mem: All of the query keys.
[out]	d_location_counts	Contains the index of a query key's first value and the number of values associated with the key. If a query fails, the number of values the key has will be marked as zero.

bool CudaHT::CuckooHashing::MultivalueHashTable::Initialize	(	const unsigned	max_input_size,
		const float	space_usage = `1.2`,
		const unsigned	num_functions = `4`
	)

virtual

Initializes the multi-value hash table's memory.

See HashTable::Initialize() for an explanation of the parameters.

Parameters

[in]	max_input_size	Largest expected number of items in the input.
[in]	space_usage	Size of the hash table relative to the input. Bigger tables are faster to build and retrieve from.
[in]	num_functions	Number of hash functions to use. May be 2-5. More hash functions make it easier to build the table, but increase retrieval times.

Returns: Whether the hash table was initialized successfully (true) or not (false).

See also: HashTable::Initialize()

Reimplemented from CudaHT::CuckooHashing::HashTable.

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

/home/jwmak/Projects/cudpp/src/cudpp_hash/hash_multivalue.h
/home/jwmak/Projects/cudpp/src/cudpp_hash/hash_multivalue.cpp

Public Member Functions

Additional Inherited Members

Detailed Description

Member Function Documentation