cugar::cuda::HashMap< KeyT, HashT, INVALID_KEY > Struct Template Reference

Detailed description

template<typename KeyT, typename HashT, KeyT INVALID_KEY = 0xFFFFFFFF>
struct cugar::cuda::HashMap< KeyT, HashT, INVALID_KEY >

This class implements a device-side Hash Map, allowing arbitrary threads from potentially different CTAs of a cuda kernel to add new entries at the same time.

The constructor of the class accepts pointers to the arrays representing the underlying data structure:

• an array of hashed keys
• an array of unique set entries
• an array of slots keeping track of the unique position where each inserted key has been mapped
• a pointer to a counter, keeping track of the number of set entries

Before starting to use the HashSet, the array of hash slots has to be initialized to INVALID_KEY.

The class provides two methods:

- HashMap::insert
- HashMap::find

It's important to notice that calls to the two methods cannot be mixed without interposing a global synchronization between them.

#include <hash.h>

Inheritance diagram for cugar::cuda::HashMap< KeyT, HashT, INVALID_KEY >:

Public Methods
CUGAR_DEVICE	HashMap ()
CUGAR_DEVICE	HashMap (const uint32 _table_size, KeyT *_hash, KeyT *_unique, uint32 *_slots, uint32 *_count)
CUGAR_DEVICE void	insert (const KeyT key, const HashT hash_code)
CUGAR_DEVICE uint32	find (const KeyT key, const HashT hash_code)
CUGAR_DEVICE uint32	size () const
CUGAR_DEVICE KeyT	get_unique (const uint32 i) const

Public Members
uint32	table_size
KeyT *	hash
KeyT *	unique
uint32 *	slots
uint32 *	count

Constructor & Destructor Documentation

HashMap() [1/2]

template<typename KeyT , typename HashT , KeyT INVALID_KEY = 0xFFFFFFFF>

CUGAR_DEVICE cugar::cuda::HashMap< KeyT, HashT, INVALID_KEY >::HashMap ( )

inline

constructor

HashMap() [2/2]

template<typename KeyT , typename HashT , KeyT INVALID_KEY = 0xFFFFFFFF>

CUGAR_DEVICE cugar::cuda::HashMap< KeyT, HashT, INVALID_KEY >::HashMap ( const uint32  _table_size, KeyT *  _hash, KeyT *  _unique, uint32 *  _slots, uint32 *  _count  )

inline

constructor

Parameters

_table_size	the size of the hash table (needs to be a power of 2)
_hash	a pointer to the array of _table_size hashing slots - needs to be initialized to INVALID_KEY before first use
_unique	a pointer to the array where inserted entries will be stored - needs to be appropriately sized to contain all unique entries
_slots	a pointer to an array of _table_size entries keeping track of the unique position where each inserted key has been mapped
_count	a pointer to a single counter, used to keep track of how many unique entries have been inserted

Member Function Documentation

find()

template<typename KeyT , typename HashT , KeyT INVALID_KEY = 0xFFFFFFFF>

CUGAR_DEVICE uint32 cugar::cuda::HashMap< KeyT, HashT, INVALID_KEY >::find ( const KeyT  key, const HashT  hash_code  )

inline

find the unique slot associated to an inserted key (NOTE: needs to be separated from insertion by a synchronization point)

get_unique()

template<typename KeyT , typename HashT , KeyT INVALID_KEY = 0xFFFFFFFF>

CUGAR_DEVICE KeyT cugar::cuda::HashMap< KeyT, HashT, INVALID_KEY >::get_unique ( const uint32  i ) const

inline

return the i-th unique element in the set

insert()

template<typename KeyT , typename HashT , KeyT INVALID_KEY = 0xFFFFFFFF>

CUGAR_DEVICE void cugar::cuda::HashMap< KeyT, HashT, INVALID_KEY >::insert ( const KeyT  key, const HashT  hash_code  )

inline

insert an element with its hashing value

Parameters

key	the element to insert
hash_code	the hashing value

size()

template<typename KeyT , typename HashT , KeyT INVALID_KEY = 0xFFFFFFFF>

CUGAR_DEVICE uint32 cugar::cuda::HashMap< KeyT, HashT, INVALID_KEY >::size ( ) const

inline

return the size of the hash set

---

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

• C:/p4research/research/jpantaleoni/Fermat-Public/contrib/cugar/basic/cuda/hash.h