CUDPP  2.1
CUDA Data-Parallel Primitives Library
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
Namespaces | Functions
hash_table.cuh File Reference

Implements kernel and device functions for a basic hash table. More...

#include "definitions.h"
#include "hash_table.h"
#include <driver_types.h>

Namespaces

 CudaHT
 Encapsulates the hash table library.
 

Functions

__device__ __host__ Entry CudaHT::CuckooHashing::make_entry (unsigned key, unsigned value)
 Makes an 64-bit Entry out of a key-value pair for the hash table.
 
__device__ __host__ unsigned CudaHT::CuckooHashing::get_key (Entry entry)
 Returns the key of an Entry.
 
__device__ __host__ unsigned CudaHT::CuckooHashing::get_value (Entry entry)
 Returns the value of an Entry.
 
template<unsigned kNumHashFunctions>
__device__ unsigned CudaHT::CuckooHashing::retrieve (const unsigned query_key, const unsigned table_size, const Entry *table, const Functions< kNumHashFunctions > constants, const uint2 stash_constants, const unsigned stash_count, unsigned *num_probes_required=NULL)
 Answers a single query. More...
 
template<unsigned kNumHashFunctions>
__global__ void CudaHT::CuckooHashing::hash_retrieve (const unsigned n_queries, const unsigned *keys_in, const unsigned table_size, const Entry *table, const Functions< kNumHashFunctions > constants, const uint2 stash_constants, const unsigned stash_count, unsigned *values_out, unsigned *num_probes_required=NULL)
 Perform a retrieval from a basic hash table. Each thread manages a single query.
 
Internal
template<class T >
__global__ void CudaHT::CuckooHashing::clear_table (const unsigned table_size, const T value, T *table)
 Fills the entire array with a specific value.
 
template<unsigned kNumHashFunctions>
__device__ void CudaHT::CuckooHashing::KeyLocations (const Functions< kNumHashFunctions > constants, const unsigned table_size, const unsigned key, unsigned locations[kNumHashFunctions])
 Determine where in the hash table the key could be located.
 
template<unsigned kNumHashFunctions>
__device__ unsigned CudaHT::CuckooHashing::determine_next_location (const Functions< kNumHashFunctions > constants, const unsigned table_size, const unsigned key, const unsigned previous_location)
 Determine where to insert the key next. The hash functions are used in round-robin order.
 
template<unsigned kNumHashFunctions>
__device__ bool CudaHT::CuckooHashing::insert (const unsigned table_size, const Functions< kNumHashFunctions > constants, const uint2 stash_constants, const unsigned max_iteration_attempts, Entry *table, unsigned *stash_count, Entry entry, unsigned *iterations_used)
 Attempts to insert a single entry into the hash table. More...
 
template<unsigned kNumHashFunctions>
__global__ void CudaHT::CuckooHashing::CuckooHash (const unsigned n_entries, const unsigned *keys, const unsigned *values, const unsigned table_size, const Functions< kNumHashFunctions > constants, const unsigned max_iteration_attempts, Entry *table, uint2 stash_constants, unsigned *stash_count, unsigned *failures, unsigned *iterations_taken)
 

Detailed Description

Implements kernel and device functions for a basic hash table.