Hash set based on multi-level array, RCU specialization. More...

#include <cds/container/feldman_hashset_rcu.h>

Inheritance diagram for cds::container::FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >:

Public Types
typedef cds::urcu::gc< RCU >	gc
	RCU garbage collector.

typedef T	value_type
	type of value stored in the set

typedef Traits	traits
	Traits template parameter, see `feldman_hashset::traits`.

typedef base_class::hash_accessor	hash_accessor
	Hash accessor functor.

typedef base_class::hash_type	hash_type
	Hash type deduced from `hash_accessor` return type.

typedef base_class::hash_comparator	hash_comparator
	hash compare functor based on `opt::compare` and `opt::less` option setter

typedef traits::item_counter	item_counter
	Item counter type.

typedef traits::allocator	allocator
	Element allocator.

typedef traits::node_allocator	node_allocator
	Array node allocator.

typedef traits::memory_model	memory_model
	Memory model.

typedef traits::back_off	back_off
	Backoff strategy.

typedef traits::stat	stat
	Internal statistics type.

typedef traits::rcu_check_deadlock	rcu_check_deadlock
	Deadlock checking policy.

typedef gc::scoped_lock	rcu_lock
	RCU scoped lock.

typedef base_class::exempt_ptr	exempt_ptr
	pointer to extracted node

typedef feldman_hashset::level_statistics	level_statistics
	Level statistics.

Public Member Functions
	FeldmanHashSet (size_t head_bits=8, size_t array_bits=4)
	Creates empty set. More...

	~FeldmanHashSet ()
	Destructs the set and frees all data.

template<typename Q >
bool	insert (Q const &val)
	Inserts new element. More...

template<typename Q , typename Func >
bool	insert (Q const &val, Func f)
	Inserts new element. More...

template<typename Q , typename Func >
std::pair< bool, bool >	update (Q const &val, Func func, bool bInsert=true)
	Updates the element. More...

template<typename... Args>
bool	emplace (Args &&...args)
	Inserts data of type `value_type` created in-place from `std::forward<Args>(args)...` More...

bool	erase (hash_type const &hash)
	Deletes the item from the set. More...

template<typename Func >
bool	erase (hash_type const &hash, Func f)
	Deletes the item from the set. More...

exempt_ptr	extract (hash_type const &hash)
	Extracts the item with specified `hash`. More...

template<typename Func >
bool	find (hash_type const &hash, Func f)
	Finds an item by it's `hash`. More...

bool	contains (hash_type const &hash)
	Checks whether the set contains `hash`. More...

value_type *	get (hash_type const &hash)
	Finds an item by it's `hash` and returns the item found. More...

void	clear ()
	Clears the set (non-atomic) More...

bool	empty () const
	Checks if the set is empty. More...

size_t	size () const
	Returns item count in the set.

stat const &	statistics () const
	Returns const reference to internal statistics.

size_t	head_size () const
	Returns the size of head node.

size_t	array_node_size () const
	Returns the size of the array node.

void	get_level_statistics (std::vector< feldman_hashset::level_statistics > &stat) const
	Collects tree level statistics into `stat`. More...

Static Public Attributes
static constexpr const bool	c_bExtractLockExternal = false
	Group of `extract_xxx` functions does not require external locking.

static constexpr size_t const	c_hash_size = base_class::c_hash_size
	The size of hash_type in bytes, see `feldman_hashset::traits::hash_size` for explanation.

Thread-safe iterators
Bidirectional iterator
typedef base_class::iterator	iterator

typedef base_class::const_iterator	const_iterator
	bidirectional const iterator type

typedef base_class::reverse_iterator	reverse_iterator
	bidirectional reverse iterator type

typedef base_class::const_reverse_iterator	const_reverse_iterator
	bidirectional reverse const iterator type

iterator	begin ()
	Returns an iterator to the beginning of the set.

const_iterator	begin () const
	Returns an const iterator to the beginning of the set.

const_iterator	cbegin ()
	Returns an const iterator to the beginning of the set.

iterator	end ()
	Returns an iterator to the element following the last element of the set. This element acts as a placeholder; attempting to access it results in undefined behavior.

const_iterator	end () const
	Returns a const iterator to the element following the last element of the set. This element acts as a placeholder; attempting to access it results in undefined behavior.

const_iterator	cend ()
	Returns a const iterator to the element following the last element of the set. This element acts as a placeholder; attempting to access it results in undefined behavior.

reverse_iterator	rbegin ()
	Returns a reverse iterator to the first element of the reversed set.

const_reverse_iterator	rbegin () const
	Returns a const reverse iterator to the first element of the reversed set.

const_reverse_iterator	crbegin ()
	Returns a const reverse iterator to the first element of the reversed set.

reverse_iterator	rend ()
	Returns a reverse iterator to the element following the last element of the reversed set. More...

const_reverse_iterator	rend () const
	Returns a const reverse iterator to the element following the last element of the reversed set. More...

const_reverse_iterator	crend ()
	Returns a const reverse iterator to the element following the last element of the reversed set. More...

Additional Inherited Members
Protected Types inherited from cds::intrusive::FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >
typedef cds::urcu::gc< RCU >	gc
	RCU garbage collector.

typedef T	value_type
	type of value stored in the set

typedef Traits	traits
	Traits template parameter.

typedef traits::hash_accessor	hash_accessor
	Hash accessor functor.

typedef base_class::hash_type	hash_type
	Hash type deduced from `hash_accessor` return type.

typedef traits::disposer	disposer
	data node disposer

typedef base_class::hash_comparator	hash_comparator
	hash compare functor based on `traits::compare` and `traits::less` options

typedef traits::item_counter	item_counter
	Item counter type.

typedef traits::node_allocator	node_allocator
	Array node allocator.

typedef traits::memory_model	memory_model
	Memory model.

typedef traits::back_off	back_off
	Backoff strategy.

typedef traits::stat	stat
	Internal statistics type.

typedef traits::rcu_check_deadlock	rcu_check_deadlock
	Deadlock checking policy.

typedef gc::scoped_lock	rcu_lock
	RCU scoped lock.

using	exempt_ptr = cds::urcu::exempt_ptr< gc, value_type, value_type, disposer, void >
	pointer to extracted node

typedef implementation_defined	iterator
	bidirectional iterator type

typedef implementation_defined	const_iterator
	bidirectional const iterator type

typedef implementation_defined	reverse_iterator
	bidirectional reverse iterator type

typedef implementation_defined	const_reverse_iterator
	bidirectional reverse const iterator type

Protected Member Functions inherited from cds::intrusive::FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >
	FeldmanHashSet (size_t head_bits=8, size_t array_bits=4)
	Creates empty set. More...

	~FeldmanHashSet ()
	Destructs the set and frees all data.

bool	insert (value_type &val)
	Inserts new node. More...

template<typename Func >
bool	insert (value_type &val, Func f)
	Inserts new node. More...

std::pair< bool, bool >	update (value_type &val, bool bInsert=true)
	Updates the node. More...

bool	unlink (value_type const &val)
	Unlinks the item `val` from the set. More...

bool	erase (hash_type const &hash)
	Deletes the item from the set. More...

template<typename Func >
bool	erase (hash_type const &hash, Func f)
	Deletes the item from the set. More...

exempt_ptr	extract (hash_type const &hash)
	Extracts the item with specified `hash`. More...

template<typename Func >
bool	find (hash_type const &hash, Func f)
	Finds an item by it's `hash`. More...

bool	contains (hash_type const &hash)
	Checks whether the set contains `hash`. More...

value_type *	get (hash_type const &hash)
	Finds an item by it's `hash` and returns the item found. More...

void	clear ()
	Clears the set (non-atomic) More...

bool	empty () const
	Checks if the set is empty. More...

size_t	size () const
	Returns item count in the set.

stat const &	statistics () const
	Returns const reference to internal statistics.

void	get_level_statistics (std::vector< feldman_hashset::level_statistics > &stat) const
	Collects tree level statistics into `stat`. More...

iterator	begin ()
	Returns an iterator to the beginning of the set. More...

const_iterator	begin () const
	Returns an const iterator to the beginning of the set.

const_iterator	cbegin ()
	Returns an const iterator to the beginning of the set.

iterator	end ()
	Returns an iterator to the element following the last element of the set. This element acts as a placeholder; attempting to access it results in undefined behavior.

const_iterator	end () const
	Returns a const iterator to the element following the last element of the set. This element acts as a placeholder; attempting to access it results in undefined behavior.

const_iterator	cend ()
	Returns a const iterator to the element following the last element of the set. This element acts as a placeholder; attempting to access it results in undefined behavior.

reverse_iterator	rbegin ()
	Returns a reverse iterator to the first element of the reversed set.

const_reverse_iterator	rbegin () const
	Returns a const reverse iterator to the first element of the reversed set.

const_reverse_iterator	crbegin ()
	Returns a const reverse iterator to the first element of the reversed set.

reverse_iterator	rend ()
	Returns a reverse iterator to the element following the last element of the reversed set. More...

const_reverse_iterator	rend () const
	Returns a const reverse iterator to the element following the last element of the reversed set. More...

const_reverse_iterator	crend ()
	Returns a const reverse iterator to the element following the last element of the reversed set. More...

Static Protected Attributes inherited from cds::intrusive::FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >
static constexpr const bool	c_bExtractLockExternal = false
	Group of `extract_xxx` functions does not require external locking.

static constexpr size_t const	c_hash_size = base_class::c_hash_size
	The size of hash_type in bytes, see `feldman_hashset::traits::hash_size` for explanation.

Detailed Description

template<class RCU, typename T, class Traits = feldman_hashset::traits>
class cds::container::FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >

Hash set based on multi-level array, RCU specialization.

Source:

[2013] Steven Feldman, Pierre LaBorde, Damian Dechev "Concurrent Multi-level Arrays: Wait-free Extensible Hash Maps"

See algorithm short description here

Note

Two important things you should keep in mind when you're using FeldmanHashSet:

all keys must be fixed-size. It means that you cannot use std::string as a key for FeldmanHashSet. Instead, for the strings you should use well-known hashing algorithms like SHA1, SHA2, MurmurHash, CityHash or its successor FarmHash and so on, which converts variable-length strings to fixed-length bit-strings, and use that hash as a key in FeldmanHashSet.
FeldmanHashSet uses a perfect hashing. It means that if two different keys, for example, of type std::string, have identical hash then you cannot insert both that keys in the set. FeldmanHashSet does not maintain the key, it maintains its fixed-size hash value.

The set supports bidirectional thread-safe iterators.

Template parameters:

RCU - one of RCU type
T - a value type to be stored in the set
Traits - type traits, the structure based on feldman_hashset::traits or result of feldman_hashset::make_traits metafunction. Traits is the mandatory argument because it has one mandatory type - an accessor to hash value of T. The set algorithm does not calculate that hash value.

Note
Before including <cds/intrusive/feldman_hashset_rcu.h> you should include appropriate RCU header file, see RCU type for list of existing RCU class and corresponding header files.

The set supports bidirectional thread-safe iterators with some restrictions.

Member Typedef Documentation

template<class RCU , typename T , class Traits = feldman_hashset::traits>

typedef base_class::iterator cds::container::FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >::iterator

The set supports thread-safe iterators: you may iterate over the set in multi-threaded environment under explicit RCU lock. RCU lock requirement means that inserting or searching is allowed but you must not erase the items from the set since erasing under RCU lock can lead to a deadlock. However, another thread can call erase() safely while your thread is iterating.

A typical example is:

struct foo {
    uint32_t    hash;
    // ... other fields
    uint32_t    payload; // only for example
};
struct set_traits: cds::container::feldman_hashset::traits
{
    struct hash_accessor {
        uint32_t operator()( foo const& src ) const
        {
            retur src.hash;
        }
    };
};
typedef cds::urcu::gc< cds::urcu::general_buffered<>> rcu;
typedef cds::container::FeldmanHashSet< rcu, foo, set_traits > set_type;
set_type s;
// ...
// iterate over the set
{
    // lock the RCU.
    typename set_type::rcu_lock l; // scoped RCU lock
    // traverse the set
    for ( auto i = s.begin(); i != s.end(); ++i ) {
        // deal with i. Remember, erasing is prohibited here!
        i->payload++;
    }
} // at this point RCU lock is released

Each iterator object supports the common interface:

dereference operators:
value_type [const] * operator ->() noexcept

value_type [const] & operator *() noexcept
pre-increment and pre-decrement. Post-operators is not supported
equality operators == and !=. Iterators are equal iff they point to the same cell of the same array node. Note that for two iterators it1 and it2 the condition it1 == it2 does not entail &(*it1) == &(*it2) : welcome to concurrent containers

Note: It is possible the item can be iterated more that once, for example, if an iterator points to the item in an array node that is being splitted.

Constructor & Destructor Documentation

template<class RCU , typename T , class Traits = feldman_hashset::traits>

cds::container::FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >::FeldmanHashSet	(	size_t	head_bits = `8`,
		size_t	array_bits = `4`
	)

inline

Creates empty set.

Parameters

head_bits	- 2^head_bits specifies the size of head array, minimum is 4.
array_bits	- 2^array_bits specifies the size of array node, minimum is 2.

Equation for head_bits and array_bits:

sizeof(hash_type) * 8 == head_bits + N * array_bits

where N is multi-level array depth.

Member Function Documentation

template<class RCU , typename T , class Traits = feldman_hashset::traits>

void cds::container::FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >::clear ( )

inline

Clears the set (non-atomic)

The function unlink all data node from the set. The function is not atomic but is thread-safe. After clear() the set may not be empty because another threads may insert items.

template<class RCU , typename T , class Traits = feldman_hashset::traits>

bool cds::container::FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >::contains ( hash_type const & hash )

inline

Checks whether the set contains hash.

The function searches the item by its hash and returns true if it is found, or false otherwise.

template<class RCU , typename T , class Traits = feldman_hashset::traits>

const_reverse_iterator cds::container::FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >::crend ( )

inline

Returns a const reverse iterator to the element following the last element of the reversed set.

It corresponds to the element preceding the first element of the non-reversed container. This element acts as a placeholder, attempting to access it results in undefined behavior.

template<class RCU , typename T , class Traits = feldman_hashset::traits>

template<typename... Args>

bool cds::container::FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >::emplace ( Args &&... args )

inline

Inserts data of type value_type created in-place from std::forward<Args>(args)...

Returns true if inserting successful, false otherwise.

template<class RCU , typename T , class Traits = feldman_hashset::traits>

bool cds::container::FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >::empty ( ) const

inline

Checks if the set is empty.

Emptiness is checked by item counting: if item count is zero then the set is empty. Thus, the correct item counting feature is an important part of the set implementation.

template<class RCU , typename T , class Traits = feldman_hashset::traits>

bool cds::container::FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >::erase ( hash_type const & hash )

inline

Deletes the item from the set.

The function searches hash in the set, deletes the item found, and returns true. If that item is not found the function returns false.

RCU should not be locked. The function locks RCU internally.

template<class RCU , typename T , class Traits = feldman_hashset::traits>

template<typename Func >

bool cds::container::FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >::erase	(	hash_type const &	hash,
		Func	f
	)

inline

Deletes the item from the set.

The function searches hash in the set, call f functor with item found, and deltes the element from the set.

The Func interface is

struct functor {
    void operator()( value_type& item );
};

If hash is not found the function returns false.

RCU should not be locked. The function locks RCU internally.

template<class RCU , typename T , class Traits = feldman_hashset::traits>

exempt_ptr cds::container::FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >::extract ( hash_type const & hash )

inline

Extracts the item with specified hash.

The function searches hash in the set, unlinks it from the set, and returns exempt_ptr pointer to the item found. If the item with key equal to key is not found the function returns an empty exempt_ptr.

RCU synchronize method can be called. RCU should NOT be locked. The function does not call the disposer for the item found. The disposer will be implicitly invoked when the returned object is destroyed or when its release() member function is called. Example:

typedef cds::container::FeldmanHashSet< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > set_type;
set_type theSet;
// ...
typename set_type::exempt_ptr ep( theSet.extract( 5 ));
if ( ep ) {
    // Deal with ep
    //...
    // Dispose returned item.
    ep.release();
}

template<class RCU , typename T , class Traits = feldman_hashset::traits>

template<typename Func >

bool cds::container::FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >::find	(	hash_type const &	hash,
		Func	f
	)

inline

Finds an item by it's hash.

The function searches the item by hash and calls the functor f for item found. The interface of Func functor is:

struct functor {
    void operator()( value_type& item );
};

where item is the item found.

The functor may change non-key fields of item. Note that the functor is only guarantee that item cannot be disposed during the functor is executing. The functor does not serialize simultaneous access to the set's item. If such access is possible you must provide your own synchronization schema on item level to prevent unsafe item modifications.

The function returns true if hash is found, false otherwise.

template<class RCU , typename T , class Traits = feldman_hashset::traits>

value_type* cds::container::FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >::get ( hash_type const & hash )

inline

Finds an item by it's hash and returns the item found.

The function searches the item by its hash and returns the pointer to the item found. If hash is not found the function returns nullptr.

RCU should be locked before the function invocation. Returned pointer is valid only while RCU is locked.

Usage:

typedef cds::container::FeldmanHashSet< your_template_params >  my_set;
my_set theSet;
// ...
{
    // lock RCU
    my_set::rcu_lock lock;
    foo * p = theSet.get( 5 );
    if ( p ) {
        // Deal with p
        //...
    }
}

template<class RCU , typename T , class Traits = feldman_hashset::traits>

void cds::container::FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >::get_level_statistics ( std::vector< feldman_hashset::level_statistics > & stat ) const

inline

Collects tree level statistics into stat.

The function traverses the set and collects statistics for each level of the tree into feldman_hashset::level_statistics struct. The element of stat[i] represents statistics for level i, level 0 is head array. The function is thread-safe and may be called in multi-threaded environment.

Result can be useful for estimating efficiency of hash functor you use.

template<class RCU , typename T , class Traits = feldman_hashset::traits>

template<typename Q >

bool cds::container::FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >::insert ( Q const & val )

inline

Inserts new element.

The function creates an element with copy of val value and then inserts it into the set.

The type Q should contain as minimum the complete hash for the element. The object of value_type should be constructible from a value of type Q. In trivial case, Q is equal to value_type.

Returns true if val is inserted into the set, false otherwise.

The function locks RCU internally.

template<class RCU , typename T , class Traits = feldman_hashset::traits>

template<typename Q , typename Func >

bool cds::container::FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >::insert	(	Q const &	val,
		Func	f
	)

inline

Inserts new element.

The function allows to split creating of new item into two part:

create item with key only
insert new item into the set
if inserting is success, calls f functor to initialize value-fields of val.

The functor signature is:

void func( value_type& val );

where val is the item inserted. User-defined functor f should guarantee that during changing val no any other changes could be made on this set's item by concurrent threads. The user-defined functor is called only if the inserting is success.

The function locks RCU internally.

template<class RCU , typename T , class Traits = feldman_hashset::traits>

reverse_iterator cds::container::FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >::rend ( )

inline

Returns a reverse iterator to the element following the last element of the reversed set.

It corresponds to the element preceding the first element of the non-reversed container. This element acts as a placeholder, attempting to access it results in undefined behavior.

template<class RCU , typename T , class Traits = feldman_hashset::traits>

const_reverse_iterator cds::container::FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >::rend ( ) const

inline

Returns a const reverse iterator to the element following the last element of the reversed set.

It corresponds to the element preceding the first element of the non-reversed container. This element acts as a placeholder, attempting to access it results in undefined behavior.

template<class RCU , typename T , class Traits = feldman_hashset::traits>

template<typename Q , typename Func >

std::pair<bool, bool> cds::container::FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >::update	(	Q const &	val,
		Func	func,
		bool	bInsert = `true`
	)

inline

Updates the element.

The operation performs inserting or replacing with lock-free manner.

If the val key not found in the set, then the new item created from val will be inserted into the set iff bInsert is true. Otherwise, if val is found, it is replaced with new item created from val and previous item is disposed. In both cases func functor is called.

The functor Func signature:

struct my_functor {
    void operator()( value_type& cur, value_type * prev );
};

where:

cur - current element
prev - pointer to previous element with such hash. prev is nullptr if cur was just inserted.

The functor may change non-key fields of the item; however, func must guarantee that during changing no any other modifications could be made on this item by concurrent threads.

Returns std::pair<bool, bool> where first is true if operation is successful, i.e. the item has been inserted or updated, second is true if the new item has been added or false if the item with key equal to val already exists.

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

cds/container/feldman_hashset_rcu.h

Public Types

Public Member Functions

Static Public Attributes

Thread-safe iterators

Additional Inherited Members

Detailed Description

template<class RCU, typename T, class Traits = feldman_hashset::traits> class cds::container::FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

template<class RCU, typename T, class Traits = feldman_hashset::traits>
class cds::container::FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >