cds  2.3.1
cds::intrusive::FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits > Class Template Reference

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

#include <cds/intrusive/feldman_hashset_rcu.h>

Inheritance diagram for cds::intrusive::FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >:
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.
 
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
 

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.
 
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_typeget (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...
 
Thread-safe iterators
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 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.
 

Detailed Description

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

Intrusive 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.

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.

Constructor & Destructor Documentation

◆ FeldmanHashSet()

template<class RCU , class T , class Traits = feldman_hashset::traits>
cds::intrusive::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- 2head_bits specifies the size of head array, minimum is 4.
array_bits- 2array_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

◆ begin()

template<class RCU , class T , class Traits = feldman_hashset::traits>
iterator cds::intrusive::FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >::begin ( )
inline

Returns an iterator to the beginning of the set.

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 for iterating thread but you must not erase the items from the set because 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 hash_accessor {
uint32_t operator()( foo const& src ) const
{
retur src.hash;
}
};
};
typedef cds::urcu::gc< cds::urcu::general_buffered<>> rcu;
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.

◆ clear()

template<class RCU , class T , class Traits = feldman_hashset::traits>
void cds::intrusive::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.

For each item the disposer is called after unlinking.

◆ contains()

template<class RCU , class T , class Traits = feldman_hashset::traits>
bool cds::intrusive::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.

The function applies RCU lock internally.

◆ crend()

template<class RCU , class T , class Traits = feldman_hashset::traits>
const_reverse_iterator cds::intrusive::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.

◆ empty()

template<class RCU , class T , class Traits = feldman_hashset::traits>
bool cds::intrusive::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.

◆ erase() [1/2]

template<class RCU , class T , class Traits = feldman_hashset::traits>
bool cds::intrusive::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, unlinks the item found, and returns true. If that item is not found the function returns false.

The disposer specified in Traits is called by garbage collector GC asynchronously.

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

◆ erase() [2/2]

template<class RCU , class T , class Traits = feldman_hashset::traits>
template<typename Func >
bool cds::intrusive::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 unlinks it from the set. The disposer specified in Traits is called by garbage collector GC asynchronously.

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.

◆ extract()

template<class RCU , class T , class Traits = feldman_hashset::traits>
exempt_ptr cds::intrusive::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:

set_type theSet;
// ...
typename set_type::exempt_ptr ep( theSet.extract( 5 ));
if ( ep ) {
// Deal with ep
//...
// Dispose returned item.
ep.release();
}

◆ find()

template<class RCU , class T , class Traits = feldman_hashset::traits>
template<typename Func >
bool cds::intrusive::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.

The function applies RCU lock internally.

◆ get()

template<class RCU , class T , class Traits = feldman_hashset::traits>
value_type* cds::intrusive::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:

my_set theSet;
// ...
{
// lock RCU
my_set::rcu_lock;
foo * p = theSet.get( 5 );
if ( p ) {
// Deal with p
//...
}
}

◆ get_level_statistics()

template<class RCU , class T , class Traits = feldman_hashset::traits>
void cds::intrusive::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.

◆ insert() [1/2]

template<class RCU , class T , class Traits = feldman_hashset::traits>
bool cds::intrusive::FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >::insert ( value_type val)
inline

Inserts new node.

The function inserts val in the set if it does not contain an item with that hash.

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

The function locks RCU internally.

◆ insert() [2/2]

template<class RCU , class T , class Traits = feldman_hashset::traits>
template<typename Func >
bool cds::intrusive::FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >::insert ( value_type val,
Func  f 
)
inline

Inserts new node.

This function is intended for derived non-intrusive containers.

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 val.

The functor signature is:

void func( value_type& val );

where val is the item inserted.

The user-defined functor is called only if the inserting is success.

The function locks RCU internally.

Warning
See insert item troubleshooting.

◆ rend() [1/2]

template<class RCU , class T , class Traits = feldman_hashset::traits>
reverse_iterator cds::intrusive::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.

◆ rend() [2/2]

template<class RCU , class T , class Traits = feldman_hashset::traits>
const_reverse_iterator cds::intrusive::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.

◆ unlink()

template<class RCU , class T , class Traits = feldman_hashset::traits>
bool cds::intrusive::FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >::unlink ( value_type const &  val)
inline

Unlinks the item val from the set.

The function searches the item val in the set and unlink it if it is found and its address is equal to &val.

The function returns true if success and false otherwise.

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

◆ update()

template<class RCU , class T , class Traits = feldman_hashset::traits>
std::pair<bool, bool> cds::intrusive::FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >::update ( value_type val,
bool  bInsert = true 
)
inline

Updates the node.

Performs inserting or updating the item with hash value equal to val.

  • If hash value is found then existing item is replaced with val, old item is disposed with Traits::disposer. Note that the disposer is called by GC asynchronously. The function returns std::pair<true, false>
  • If hash value is not found and bInsert is true then val is inserted, the function returns std::pair<true, true>
  • If hash value is not found and bInsert is false then the set is unchanged, the function returns std::pair<false, false>

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 new item has been added or false if the set contains that hash.

The function locks RCU internally.


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

cds 2.3.1 Developed by Maxim Khizhinsky aka khizmax 2007 - 2017
Autogenerated Fri Sep 1 2017 08:47:20 by Doxygen 1.8.13