CUDPP  2.1
CUDA Data-Parallel Primitives Library
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
Public Member Functions | Protected Attributes | List of all members
CudaHT::CuckooHashing::HashTable Class Reference

Basic hash table that stores one value for each key. More...

#include <hash_table.h>

Inherited by CudaHT::CuckooHashing::CompactingHashTable, and CudaHT::CuckooHashing::MultivalueHashTable.

Public Member Functions

virtual bool Initialize (const unsigned max_input_size, const float space_usage=1.25, const unsigned num_functions=4)
 
virtual void Release ()
 Free all memory.
 
virtual bool Build (const unsigned input_size, const unsigned *d_keys, const unsigned *d_vals)
 Build the hash table. More...
 
virtual void Retrieve (const unsigned n_queries, const unsigned *d_query_keys, unsigned *d_query_results)
 Query the hash table. More...
 
Accessors

Mainly needed to use the device CudaHT::retrieve() function directly.

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.
 

Protected Attributes

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

Basic hash table that stores one value for each key.

The input consists of two unsigned arrays of keys and values. None of the keys are expected to be repeated.

Todo:
Templatize the interface without forcing the header file to have CUDA calls.

Member Function Documentation

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

Initialize the hash table's memory. Must be called before Build() and after the random number generator has been seeded.

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).

The minimum space usage is dependent on the number of functions being used; for two through five functions, the minimum space usage is 2.1, 1.1, 1.03, and 1.02 respectively.

Reimplemented in CudaHT::CuckooHashing::MultivalueHashTable, and CudaHT::CuckooHashing::CompactingHashTable.

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

Build the hash table.

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).

Several attempts are allowed to build the hash table in case of failure. The input keys are expected to be completely unique. To reduce the chance of a failure, increase the space usage or number of functions. Keys are not allowed to be equal to CudaHT::CuckooHashing::kKeyEmpty.

Reimplemented in CudaHT::CuckooHashing::CompactingHashTable, and CudaHT::CuckooHashing::MultivalueHashTable.

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

Query the hash table.

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.

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

Reimplemented in CudaHT::CuckooHashing::CompactingHashTable, and CudaHT::CuckooHashing::MultivalueHashTable.


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