CUDPP  2.3
CUDA Data-Parallel Primitives Library
Public Member Functions | List of all members
CudaHT::CuckooHashing::CompactingHashTable Class Reference

Hash table that provides O(1) translation between keys and unique identifiers. More...

#include <hash_compacting.h>

Inherits CudaHT::CuckooHashing::HashTable.

Public Member Functions

virtual bool Initialize (const unsigned max_input_size, const float space_usage=1.25, const unsigned num_functions=4)
 Initializes the compacting hash table's memory. More...
 
virtual bool Build (const unsigned input_size, const unsigned *d_keys, const unsigned *d_vals)
 Builds a compacting hash table. More...
 
virtual void Retrieve (const unsigned n_queries, const unsigned *d_query_keys, unsigned *d_query_results)
 Queries the hash table for the unique identifiers of the query keys. More...
 
virtual void Release ()
 Releases all of the memory.
 
unsigned get_unique_keys_size () const
 Returns the number of unique keys found in the input.
 
const unsigned * get_unique_keys () const
 Returns the unique keys found in the input.
 
- 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 Entryget_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.
 
Entryd_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 provides O(1) translation between keys and unique identifiers.

Member Function Documentation

bool CudaHT::CuckooHashing::CompactingHashTable::Initialize ( const unsigned  max_input_size,
const float  space_usage = 1.25,
const unsigned  num_functions = 4 
)
virtual

Initializes the compacting hash table's memory.

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

Parameters
[in]max_input_sizeLargest expected number of items in the input.
[in]space_usageSize of the hash table relative to the input. Bigger tables are faster to build and retrieve from.
[in]num_functionsNumber 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.

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

Builds a compacting hash table.

See HashTable::Build() for an explanation of the parameters. Keys may be repeated; the structure will compact them down into a list of unique keys and assign each a unique key an ID from 0 to K-1, where K is the number of unique keys. The values are not used with this structure and are ignored.

Parameters
[in]input_sizeNumber of key-value pairs being inserted.
[in]d_keysDevice memory array containing all of the input keys.
[in]d_valsDevice 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.

void CudaHT::CuckooHashing::CompactingHashTable::Retrieve ( const unsigned  n_queries,
const unsigned *  d_query_keys,
unsigned *  d_query_results 
)
virtual

Queries the hash table for the unique identifiers of the query keys.

Parameters
[in]n_queriesNumber of keys in the query set.
[in]d_query_keysDevice memory array containing all of the query keys.
[in]d_query_resultsValues for the query keys.

CUDPP_HASH_KEY_NOT_FOUND is returned for any query key that failed to be found in the table.

Reimplemented from CudaHT::CuckooHashing::HashTable.


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