FixedHashMap< K, V > Class Template Reference

A fixed-size hash map supporting insertion and lookup operations. More...

#include "src/ParallelHashMap.h"

Public Member Functions
	FixedHashMap (size_t M=64)
	Constructor initializes fixed-size table of buckets filled with empty linked lists. More...
virtual	~FixedHashMap ()
	Destructor deletes all nodes in the linked lists associated with each bucket in the fixed-size table and their pointers.
bool	contains (K &key)
	Determine whether the fixed-size table contains a given key. More...
V &	at (K &key)
	Determine the value associated with a given key in the fixed-size table. More...
void	insert (K key, V value)
	Inserts a key/value pair into the fixed-size table. More...
long	insert_and_get_count (K key, V value)
	Inserts a key/value pair into the fixed-size table and returns the order number with which it was inserted. More...
size_t	size ()
	Returns the number of key/value pairs in the fixed-size table. More...
size_t	bucket_count ()
	Returns the number of buckets in the fixed-size table. More...
K *	keys ()
	Returns an array of the keys in the fixed-size table. More...
V *	values ()
	Returns an array of the values in the fixed-size table. More...
void	clear ()
	Clears all key/value pairs form the hash table.
void	print_buckets ()
	Prints the contents of each bucket to the screen. More...

Detailed Description

template<class K, class V>
class FixedHashMap< K, V >

A fixed-size hash map supporting insertion and lookup operations.

The FixedHashMap class supports insertion and lookup operations but not deletion as deletion is not needed in the OpenMOC application. This hash table uses chaining for collisions and does not incorporate concurrency objects except for tracking the number of entries in the table for which an atomic increment is used. This hash table is not thread safe but is used as a building block for the ParallelHashMap class. This table guarantees O(1) insertions and lookups on average.

Constructor & Destructor Documentation

FixedHashMap()

template<class K , class V >

FixedHashMap< K, V >::FixedHashMap

(

size_t

M = 64

)

Constructor initializes fixed-size table of buckets filled with empty linked lists.

The constructor initializes a fixed-size hash map with the size as an input parameter. If no size is given the default size (64) is used. Buckets are filled with empty linked lists presented as NULL pointers.

Parameters

M	size of fixed hash map

Member Function Documentation

at()

template<class K, class V >

V & FixedHashMap< K, V >::at

(

K &

key

)

Determine the value associated with a given key in the fixed-size table.

The linked list in the bucket associated with the key is searched and once the key is found, the corresponding value is returned. An exception is thrown if the key is not present in the map.

Parameters

key	key whose corresponding value is desired

Returns

value associated with the given key

bucket_count()

template<class K , class V >

size_t FixedHashMap< K, V >::bucket_count

(

)

Returns the number of buckets in the fixed-size table.

Returns

number of buckets in the map

contains()

template<class K, class V >

bool FixedHashMap< K, V >::contains

(

K &

key

)

Determine whether the fixed-size table contains a given key.

The linked list in the bucket associated with the key is searched to determine whether the key is present.

Parameters

key	key to be searched

Returns

boolean value referring to whether the key is contained in the map

insert()

template<class K, class V>

void FixedHashMap< K, V >::insert	(	K	key,
		V	value
	)

Inserts a key/value pair into the fixed-size table.

The specified key value pair is inserted into the fixed-size table. If the key already exists in the table, the pair is not inserted and the function returns.

Parameters

key	key of the key/value pair to be inserted
value	value of the key/value pair to be inserted

insert_and_get_count()

template<class K, class V>

long FixedHashMap< K, V >::insert_and_get_count	(	K	key,
		V	value
	)

Inserts a key/value pair into the fixed-size table and returns the order number with which it was inserted.

The specified key value pair is inserted into the fixed-size table. If the key already exists in the table, the pair is not inserted and the function returns -1.

Parameters

key	key of the key/value pair to be inserted
value	value of the key/value pair to be inserted

Returns

order number in which key/value pair was inserted, -1 is returned if key was already present in map.

keys()

template<class K , class V >

K * FixedHashMap< K, V >::keys

(

)

Returns an array of the keys in the fixed-size table.

All buckets are scanned in order to form a list of all keys present in the table and then the list is returned. 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.

print_buckets()

template<class K , class V >

void FixedHashMap< 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.

size()

template<class K , class V >

size_t FixedHashMap< K, V >::size

(

)

Returns the number of key/value pairs in the fixed-size table.

Returns

number of key/value pairs in the map

values()

template<class K , class V >

V * FixedHashMap< K, V >::values

(

)

Returns an array of the values in the fixed-size table.

All buckets are scanned in order to form a list of all values present in the table and then the list is returned. 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:

• /home/guillaume/Research/OpenMOC/src/ParallelHashMap.h