Tervel  1.0.0
A collection of wait-free containers and algorithms.
Classes | Public Member Functions | Private Types | Private Member Functions | Private Attributes | Friends | List of all members
tervel::containers::wf::HashMapNoDelete< Key, Value, Functor > Class Template Reference

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

#include <wf_hash_map_no_delete.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  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

 HashMapNoDelete (uint64_t capacity, uint64_t expansion_rate=3)
 
 ~HashMapNoDelete ()
 Not Thread Safe! 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. 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...
 
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, uint64_t next_position)
 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...
 

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
 

Detailed Description

template<class Key, class Value, class Functor = default_functor<Key, Value>>
class tervel::containers::wf::HashMapNoDelete< 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::HashMapNoDelete< Key, Value, Functor >::Location
private

Constructor & Destructor Documentation

template<class Key , class Value , class Functor = default_functor<Key, Value>>
tervel::containers::wf::HashMapNoDelete< Key, Value, Functor >::HashMapNoDelete ( uint64_t  capacity,
uint64_t  expansion_rate = 3 
)
inline
template<class Key , class Value , class Functor = default_functor<Key, Value>>
tervel::containers::wf::HashMapNoDelete< Key, Value, Functor >::~HashMapNoDelete ( )
inline

Not Thread Safe! 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::HashMapNoDelete< 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
keythe key to look up
vathe 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::HashMapNoDelete< Key, Value, Functor >::expand_map ( Location loc,
Node *&  curr_value,
uint64_t  next_position 
)
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
locThe location to expand at
curr_valueThe current value (data node) at the location
next_positionThe position the data node belongs at the next depth.
template<class Key , class Value , class Functor >
uint64_t tervel::containers::wf::HashMapNoDelete< Key, Value, Functor >::get_position ( Key &  key,
size_t  depth 
)
Parameters
keyThe key
depthThe depth
Returns
the position this key belongs in at the specified depth.
template<class Key , class Value , class Functor >
bool tervel::containers::wf::HashMapNoDelete< 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
keyThe key to insert
valueThe 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::HashMapNoDelete< 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::HashMapNoDelete< Key, Value, Functor >::print_key ( Key &  key)

Outputs the positions a key belongs in at each depth.

Used for Debugging

Parameters
keyThe Key
template<class Key , class Value , class Functor = default_functor<Key, Value>>
size_t tervel::containers::wf::HashMapNoDelete< 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 Node
friend

Member Data Documentation

template<class Key , class Value , class Functor = default_functor<Key, Value>>
std::unique_ptr<Location[]> tervel::containers::wf::HashMapNoDelete< Key, Value, Functor >::primary_array_
private
template<class Key , class Value , class Functor = default_functor<Key, Value>>
const size_t tervel::containers::wf::HashMapNoDelete< Key, Value, Functor >::primary_array_pow_
private
template<class Key , class Value , class Functor = default_functor<Key, Value>>
const size_t tervel::containers::wf::HashMapNoDelete< Key, Value, Functor >::primary_array_size_
private
template<class Key , class Value , class Functor = default_functor<Key, Value>>
const size_t tervel::containers::wf::HashMapNoDelete< Key, Value, Functor >::secondary_array_pow_
private
template<class Key , class Value , class Functor = default_functor<Key, Value>>
const size_t tervel::containers::wf::HashMapNoDelete< 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::HashMapNoDelete< Key, Value, Functor >::size_
private

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