A wait-free hash map implementation. More...

#include <wf_hash_map.h>

Classes
class	ArrayNode
	This class is used to hold the secondary array structure. More...

class	DataNode
	This class is used to hold a key and value pair. More...

class	ForceExpandOp
	TODO(steven): add description TODO(steven): move into a file. More...

class	Node
	This class is used to differentiate between data_nodes and array_nodes/. More...

class	ValueAccessor
	This class is used to safe guard access to values. More...

Public Member Functions
	HashMap (uint64_t capacity, uint64_t expansion_rate=3)

	~HashMap ()
	Not Thread Safe! May create a very large stack! Note: should implement a better way... More...

bool	at (Key key, ValueAccessor &va)
	This function returns true and initializes the passed ValueAccessor if the key exists in the hash map. More...

bool	insert (Key key, Value value)
	This function returns true if the key value pair was successfully inserted. More...

bool	remove (Key key)
	Attempts to remove a key/value pair from the hash map Returns false in the event the key is not in the hash map or if the access_counter is non-zero. More...

size_t	size ()

uint64_t	get_position (Key &key, size_t depth)

uint64_t	max_depth ()

void	print_key (Key &key)
	Outputs the positions a key belongs in at each depth. More...

Private Types
typedef std::atomic< Node * >	Location

Private Member Functions
void	expand_map (Location loc, Node curr_value, size_t depth)
	Increases the capacity of the hash map by replacing a data node reference with a reference to an array node containing a reference to that data node. More...

bool	hp_watch_and_get_value (Location loc, Node &value)
	This is a wrapper for hazard pointers. More...

void	hp_unwatch ()

Private Attributes
const size_t	primary_array_size_

const size_t	primary_array_pow_

const size_t	secondary_array_size_

const size_t	secondary_array_pow_

std::atomic< uint64_t >	size_

std::unique_ptr< Location[]>	primary_array_

Friends
class	Node

class	ForceExpandOp

Detailed Description

template<class Key, class Value, class Functor = default_functor<Key, Value>>
class tervel::containers::wf::HashMap< Key, Value, Functor >

A wait-free hash map implementation.

TODO(steven): Provide general overview

Functor should have the following functions: -Key hash(Key k) (where hash(a) == (hash(b) implies a == b -bool key_equals (Key a, Key b) Important Note: the hashed value of keys will be passed in.

Member Typedef Documentation

template<class Key , class Value , class Functor = default_functor<Key, Value>>

typedef std::atomic<Node *> tervel::containers::wf::HashMap< Key, Value, Functor >::Location

private

Constructor & Destructor Documentation

template<class Key , class Value , class Functor = default_functor<Key, Value>>

tervel::containers::wf::HashMap< Key, Value, Functor >::HashMap	(	uint64_t	capacity,
		uint64_t	expansion_rate = `3`
	)

inline

template<class Key , class Value , class Functor = default_functor<Key, Value>>

tervel::containers::wf::HashMap< Key, Value, Functor >::~HashMap ( )

inline

Not Thread Safe! May create a very large stack! Note: should implement a better way...

If it is a node type then the node will be freed If it is an array node then the destructor of the array node will free any nodes that are referenced it. This may cause more array node's to be freed. Stack can reach max_depth() in size.

Member Function Documentation

template<class Key , class Value , class Functor >

bool tervel::containers::wf::HashMap< Key, Value, Functor >::at	(	Key	key,
		ValueAccessor &	va
	)

This function returns true and initializes the passed ValueAccessor if the key exists in the hash map.

Initializing the ValueAccessor consists of assigning storing a reference to the associated value and a reference to the access counter. The access counter will have been increased by one. Upon the destruction or re-initialization of the ValueAccessor, the access counter will be decremented.

The sequential complexity of this operation is O(max_depth()).

Parameters

key	the key to look up
va	the location to store the address of the value/access_counter

Returns: whether or not the key is present

template<class Key , class Value , class Functor >

void tervel::containers::wf::HashMap< Key, Value, Functor >::expand_map	(	Location *	loc,
		Node *	curr_value,
		size_t	depth
	)

private

Increases the capacity of the hash map by replacing a data node reference with a reference to an array node containing a reference to that data node.

Parameters

loc	The location to expand at
curr_value	The current value (data node) at the location
next_position	The position the data node belongs at the next depth.

template<class Key , class Value , class Functor >

uint64_t tervel::containers::wf::HashMap< Key, Value, Functor >::get_position	(	Key &	key,
		size_t	depth
	)

Parameters

key	The key
depth	The depth

Returns: the position this key belongs in at the specified depth.

template<class Key , class Value , class Functor >

void tervel::containers::wf::HashMap< Key, Value, Functor >::hp_unwatch ( )

private

template<class Key , class Value , class Functor >

bool tervel::containers::wf::HashMap< Key, Value, Functor >::hp_watch_and_get_value	(	Location *	loc,
		Node *&	value
	)

private

This is a wrapper for hazard pointers.

If it returns true then the value has been assigned the current value of loc and it is hazard pointer protected.

Parameters

loc	the location to dereference a Node object from
value	the destination to write the Node objet pointer

Returns: whether or not it was able to dereference and hazard pointer watch a node object.

template<class Key , class Value , class Functor >

bool tervel::containers::wf::HashMap< Key, Value, Functor >::insert	(	Key	key,
		Value	value
	)

This function returns true if the key value pair was successfully inserted.

Otherwise it returns false.

A key can fail to insert in the event the key is already present.

The sequential complexity of this operation is O(max_depth()).

Parameters

key	The key to insert
value	The key's associated value

Returns: whether or not the the key/value was inserted

template<class Key , class Value , class Functor >

uint64_t tervel::containers::wf::HashMap< Key, Value, Functor >::max_depth ( )

Returns: the maximum depth of the hash map, any depth beyond this would not produce any non-zero positions.

template<class Key , class Value , class Functor >

void tervel::containers::wf::HashMap< Key, Value, Functor >::print_key ( Key & key )

Outputs the positions a key belongs in at each depth.

Parameters

key The Key

template<class Key , class Value , class Functor >

bool tervel::containers::wf::HashMap< Key, Value, Functor >::remove ( Key key )

Attempts to remove a key/value pair from the hash map Returns false in the event the key is not in the hash map or if the access_counter is non-zero.

Parameters

key	The key to resume

Returns: where or not the key was removed

template<class Key , class Value , class Functor = default_functor<Key, Value>>

size_t tervel::containers::wf::HashMap< Key, Value, Functor >::size ( )

inline

Returns: the number of keys in the hash map

Friends And Related Function Documentation

template<class Key , class Value , class Functor = default_functor<Key, Value>>

friend class ForceExpandOp

friend

template<class Key , class Value , class Functor = default_functor<Key, Value>>

friend class Node

friend

Member Data Documentation

template<class Key , class Value , class Functor = default_functor<Key, Value>>

std::unique_ptr<Location[]> tervel::containers::wf::HashMap< Key, Value, Functor >::primary_array_

private

template<class Key , class Value , class Functor = default_functor<Key, Value>>

const size_t tervel::containers::wf::HashMap< Key, Value, Functor >::primary_array_pow_

private

template<class Key , class Value , class Functor = default_functor<Key, Value>>

const size_t tervel::containers::wf::HashMap< Key, Value, Functor >::primary_array_size_

private

template<class Key , class Value , class Functor = default_functor<Key, Value>>

const size_t tervel::containers::wf::HashMap< Key, Value, Functor >::secondary_array_pow_

private

template<class Key , class Value , class Functor = default_functor<Key, Value>>

const size_t tervel::containers::wf::HashMap< Key, Value, Functor >::secondary_array_size_

private

template<class Key , class Value , class Functor = default_functor<Key, Value>>

std::atomic<uint64_t> tervel::containers::wf::HashMap< Key, Value, Functor >::size_

private

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

tervel/containers/wf/hash-map/wf_hash_map.h

Classes

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Friends

Detailed Description

template<class Key, class Value, class Functor = default_functor<Key, Value>> class tervel::containers::wf::HashMap< Key, Value, Functor >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation

template<class Key, class Value, class Functor = default_functor<Key, Value>>
class tervel::containers::wf::HashMap< Key, Value, Functor >