An open source method of characteristics neutron transport code.
Classes | Public Member Functions | List of all members
ParallelHashMap< K, V > Class Template Reference

A thread-safe hash map supporting insertion and lookup operations. More...

#include "src/ParallelHashMap.h"

Public Member Functions

 ParallelHashMap (size_t M=64, size_t L=64)
 Constructor generates initial underlying table as a fixed-sized hash map and initializes concurrency structures.
 
virtual ~ParallelHashMap ()
 Destructor frees memory associated with fixed-sized hash map and concurrency structures.
 
bool contains (K &key)
 Determine whether the parallel hash map contains a given key. More...
 
V at (K &key)
 Determine the value associated with a given key. More...
 
void update (K &key, V value)
 Updates the value associated with a key in the parallel hash map. More...
 
void insert (K key, V value)
 Insert a given key/value pair into the parallel hash map. More...
 
long insert_and_get_count (K key, V value)
 Insert a given key/value pair into the parallel hash map and return the order number. More...
 
size_t size ()
 Returns the number of key/value pairs in the underlying table. More...
 
size_t bucket_count ()
 Returns the number of buckets in the underlying table. More...
 
size_t num_locks ()
 Returns the number of locks in the parallel hash map. More...
 
K * keys ()
 Returns an array of the keys in the underlying table. More...
 
V * values ()
 Returns an array of the values in the underlying table. More...
 
void clear ()
 Clears all key/value pairs form the hash table.
 
void setFixedSize ()
 Prevents the parallel hash map from further resizing.
 
void print_buckets ()
 Prints the contents of each bucket to the screen. More...
 
void realloc (size_t M)
 Reallocates the underlying table to the desired size. More...
 

Detailed Description

template<class K, class V>
class ParallelHashMap< K, V >

A thread-safe hash map supporting insertion and lookup operations.

The ParallelHashMap class is built on top of the FixedHashMap class, supporting insertion and lookup operations but not deletion as deletion is not needed in the OpenMOC application. This hash table uses chaining for collisions, as defined in FixedHashMap. It offers lock free lookups in O(1) time on average and fine-grained locking for insertions in O(1) time on average as well. Resizing is conducted periodically during inserts, although the starting table size can be chosen to limit the number of resizing operations.

Member Function Documentation

◆ at()

template<class K, class V >
V ParallelHashMap< K, V >::at ( K &  key)

Determine the value associated with a given key.

This function follows the same algorithm as "contains" except that the value associated with the searched key is returned. First the thread accessing the table acquires the lock corresponding with the associated bucket based on the key. Then the linked list in the bucket is searched for the key. An exception is thrown if the key is not found. When the thread has finished accessing the table, it releases the lock.

Parameters
keykey to be searched
Returns
value associated with the key

◆ bucket_count()

template<class K , class V >
size_t ParallelHashMap< K, V >::bucket_count ( )

Returns the number of buckets in the underlying table.

Returns
number of buckets in the map

◆ contains()

template<class K, class V >
bool ParallelHashMap< K, V >::contains ( K &  key)

Determine whether the parallel hash map contains a given key.

First the thread accessing the table announces its presence and which table it is reading. Then the linked list in the bucket associated with the key is searched without setting any locks to determine whether the key is present. When the thread has finished accessing the table, the announcement is reset to NULL. The announcement ensures that the data in the map is not freed during a resize until all threads have finished accessing the map.

Parameters
keykey to be searched
Returns
boolean value referring to whether the key is contained in the map

◆ insert()

template<class K, class V>
void ParallelHashMap< K, V >::insert ( K  key,
V  value 
)

Insert a given key/value pair into the parallel hash map.

First the underlying table is checked to determine if a resize should be conducted. Then, the table is checked to see if it already contains the key. If so, the key/value pair is not inserted and the function returns. Otherwise, the lock of the associated bucket is acquired and the key/value pair is added to the bucket.

Parameters
keykey of the key/value pair to be inserted
valuevalue of the key/value pair to be inserted

◆ insert_and_get_count()

template<class K, class V>
long ParallelHashMap< K, V >::insert_and_get_count ( K  key,
V  value 
)

Insert a given key/value pair into the parallel hash map and return the order number.

First the underlying table is checked to determine if a resize should be conducted. Then, the table is checked to see if it already contains the key. If so, the key/value pair is not inserted and the function returns. Otherwise, the lock of the associated bucket is acquired and the key/value pair is added to the bucket.

Parameters
keykey of the key/value pair to be inserted
valuevalue of the key/value pair to be inserted
Returns
order number in which the key/value pair was inserted, -1 if it already exists

◆ keys()

template<class K , class V >
K * ParallelHashMap< K, V >::keys ( )

Returns an array of the keys in the underlying table.

All buckets are scanned in order to form a list of all keys present in the table and then the list is returned. Threads announce their presence to ensure table memory is not freed during access. WARNING: The user is responsible for freeing the allocated memory once the array is no longer needed.

Returns
an array of keys in the map whose length is the number of key/value pairs in the table.

◆ num_locks()

template<class K , class V >
size_t ParallelHashMap< K, V >::num_locks ( )

Returns the number of locks in the parallel hash map.

Returns
number of locks in the map

◆ print_buckets()

template<class K , class V >
void ParallelHashMap< K, V >::print_buckets ( )

Prints the contents of each bucket to the screen.

All buckets are scanned and the contents of the buckets are printed, which are pointers to linked lists. If the pointer is NULL suggesting that the linked list is empty, NULL is printed to the screen. Threads announce their presence to ensure table memory is not freed during access.

◆ realloc()

template<class K , class V >
void ParallelHashMap< K, V >::realloc ( size_t  M)

Reallocates the underlying table to the desired size.

Parameters
MThe requested new size

◆ size()

template<class K , class V >
size_t ParallelHashMap< K, V >::size ( )

Returns the number of key/value pairs in the underlying table.

Returns
number of key/value pairs in the map

◆ update()

template<class K, class V>
void ParallelHashMap< K, V >::update ( K &  key,
V  value 
)

Updates the value associated with a key in the parallel hash map.

The thread first acquires the lock for the bucket associated with the key is acquired, then the linked list in the bucket is searched for the key. If the key is not found, an exception is returned. When the key is found, the value is updated and the lock is released.

Parameters
keythe key of the key/value pair to be updated
valuethe new value for the key/value pair

◆ values()

template<class K , class V >
V * ParallelHashMap< K, V >::values ( )

Returns an array of the values in the underlying table.

All buckets are scanned in order to form a list of all values present in the table and then the list is returned. Threads announce their presence to ensure table memory is not freed during access. WARNING: The user is responsible for freeing the allocated memory once the array is no longer needed.

Returns
an array of values in the map whose length is the number of key/value pairs in the table.
The documentation for this class was generated from the following file: