We know that if we expand the hash map a fixed number of times there can be no collision as duplicate keys
are not provided for in the standard semantics of a hash map.
- \p %MultiLevelHashSet is a multi-level array whitch has a structure similar to a tree:
+ \p %MultiLevelHashSet is a multi-level array which has a structure similar to a tree:
@image html multilevel_hashset.png
The multi-level array differs from a tree in that each position on the tree could hold an array of nodes or a single node.
- A position that holds a single node is a \p dataNode which holds the hash value of a key and the value that is associated\r
- with that key; it is a simple struct holding two variables. A \p dataNode in the multi-level array could be marked.\r
- A \p markedDataNode refers to a pointer to a \p dataNode that has been bitmarked at the least significant bit (LSB)\r
- of the pointer to the node. This signifies that this \p dataNode is contended. An expansion must occur at this node;\r
- any thread that sees this \p markedDataNode will try to replace it with an \p arrayNode; which is a position that holds\r
- an array of nodes. The pointer to an \p arrayNode is differentiated from that of a pointer to a \p dataNode by a bitmark\r
- on the second-least significant bit.\r
-\r
- \p %MultiLevelHashSet multi-level array is similar to a tree in that we keep a pointer to the root, which is a memory array\r
- called \p head. The length of the \p head memory array is unique, whereas every other \p arrayNode has a uniform length;\r
- a normal \p arrayNode has a fixed power-of-two length equal to the binary logarithm of a variable called \p arrayLength.\r
- The maximum depth of the tree, \p maxDepth, is the maximum number of pointers that must be followed to reach any node.\r
- We define \p currentDepth as the number of memory arrays that we need to traverse to reach the \p arrayNode on which\r
- we need to operate; this is initially one, because of \p head.\r
-\r
- That approach to the structure of the hash map uses an extensible hashing scheme; <b> the hash value is treated as a bit\r
- string</b> and rehash incrementally.\r
-\r
- @note Two important things you should keep in mind when you're using \p %MultiLevelHashSet:\r
- - all keys must be fixed-size. It means that you cannot use \p std::string as a key for \p %MultiLevelHashSet.\r
- Instead, for the strings you should use well-known hashing algorithms like <a href="https://en.wikipedia.org/wiki/Secure_Hash_Algorithm">SHA1, SHA2</a>,\r
- <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>, <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a> \r
- or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a> and so on, which\r
- converts variable-length strings to fixed-length bit-strings, and use that hash as a key in \p %MultiLevelHashSet.\r
- - \p %MultiLevelHashSet uses a perfect hashing. It means that if two different keys, for example, of type \p std::string,\r
- have identical hash then you cannot insert both that keys in the set. \p %MultiLevelHashSet does not maintain the key,\r
- it maintains its fixed-size hash value.\r
-\r
- The set supports @ref cds_intrusive_MultilevelHashSet_iterators "bidirectional thread-safe iterators".\r
-\r
- Template parameters:\r
- - \p GC - safe memory reclamation schema. Can be \p gc::HP, \p gc::DHP or one of \ref cds_urcu_type "RCU type"\r
- - \p T - a value type to be stored in the set\r
- - \p Traits - type traits, the structure based on \p multilevel_hashset::traits or result of \p multilevel_hashset::make_traits metafunction.\r
- \p Traits is the mandatory argument because it has one mandatory type - an @ref multilevel_hashset::traits::hash_accessor "accessor" \r
- to hash value of \p T. The set algorithm does not calculate that hash value.\r
-\r
+ A position that holds a single node is a \p dataNode which holds the hash value of a key and the value that is associated
+ with that key; it is a simple struct holding two variables. A \p dataNode in the multi-level array could be marked.
+ A \p markedDataNode refers to a pointer to a \p dataNode that has been bitmarked at the least significant bit (LSB)
+ of the pointer to the node. This signifies that this \p dataNode is contended. An expansion must occur at this node;
+ any thread that sees this \p markedDataNode will try to replace it with an \p arrayNode; which is a position that holds
+ an array of nodes. The pointer to an \p arrayNode is differentiated from that of a pointer to a \p dataNode by a bitmark
+ on the second-least significant bit.
+
+ \p %MultiLevelHashSet multi-level array is similar to a tree in that we keep a pointer to the root, which is a memory array
+ called \p head. The length of the \p head memory array is unique, whereas every other \p arrayNode has a uniform length;
+ a normal \p arrayNode has a fixed power-of-two length equal to the binary logarithm of a variable called \p arrayLength.
+ The maximum depth of the tree, \p maxDepth, is the maximum number of pointers that must be followed to reach any node.
+ We define \p currentDepth as the number of memory arrays that we need to traverse to reach the \p arrayNode on which
+ we need to operate; this is initially one, because of \p head.
+
+ That approach to the structure of the hash set uses an extensible hashing scheme; <b> the hash value is treated as a bit
+ string</b> and rehash incrementally.
+
+ @note Two important things you should keep in mind when you're using \p %MultiLevelHashSet:
+ - all keys must be fixed-size. It means that you cannot use \p std::string as a key for \p %MultiLevelHashSet.
+ Instead, for the strings you should use well-known hashing algorithms like <a href="https://en.wikipedia.org/wiki/Secure_Hash_Algorithm">SHA1, SHA2</a>,
+ <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>, <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a>
+ or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a> and so on, which
+ converts variable-length strings to fixed-length bit-strings, and use that hash as a key in \p %MultiLevelHashSet.
+ - \p %MultiLevelHashSet uses a perfect hashing. It means that if two different keys, for example, of type \p std::string,
+ have identical hash then you cannot insert both that keys in the set. \p %MultiLevelHashSet does not maintain the key,
+ it maintains its fixed-size hash value.
+
+ The set supports @ref cds_intrusive_MultilevelHashSet_iterators "bidirectional thread-safe iterators".
+
+ Template parameters:
+ - \p GC - safe memory reclamation schema. Can be \p gc::HP, \p gc::DHP or one of \ref cds_urcu_type "RCU type"
+ - \p T - a value type to be stored in the set
+ - \p Traits - type traits, the structure based on \p multilevel_hashset::traits or result of \p multilevel_hashset::make_traits metafunction.
+ \p Traits is the mandatory argument because it has one mandatory type - an @ref multilevel_hashset::traits::hash_accessor "accessor"
+ to hash value of \p T. The set algorithm does not calculate that hash value.
+
There are several specializations of \p %MultiLevelHashSet for each \p GC. You should include:
- <tt><cds/intrusive/multilevel_hashset_hp.h></tt> for \p gc::HP garbage collector
- <tt><cds/intrusive/multilevel_hashset_dhp.h></tt> for \p gc::DHP garbage collector
- - <tt><cds/intrusive/multilevel_hashset_rcu.h></tt> for \ref cds_intrusive_MultiLevelHashSet_rcu "RCU type". RCU specialization
+ - <tt><cds/intrusive/multilevel_hashset_rcu.h></tt> for \ref cds_intrusive_MultilevelHashSet_rcu "RCU type". RCU specialization
has a slightly different interface.
*/
template <
typedef typename traits::hash_accessor hash_accessor; ///< Hash accessor functor
static_assert(!std::is_same< hash_accessor, cds::opt::none >::value, "hash_accessor functor must be specified" );
- /// Hash type defined as \p hash_accessor return type
- typedef typename std::decay<
+ /// Hash type deduced from \p hash_accessor return type
+ typedef typename std::decay<
typename std::remove_reference<
decltype( hash_accessor()( std::declval<T>()) )
>::type
# ifdef CDS_DOXYGEN_INVOKED
typedef implementation_defined hash_comparator ; ///< hash compare functor based on opt::compare and opt::less option setter
# else
- typedef typename cds::opt::details::make_comparator_from<
+ typedef typename cds::opt::details::make_comparator_from<
hash_type,
traits,
multilevel_hashset::bitwise_compare< hash_type >
typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
/// Count of hazard pointers required
- static CDS_CONSTEXPR size_t const c_nHazardPtrCount = 1;
+ static CDS_CONSTEXPR size_t const c_nHazardPtrCount = 2;
/// Node marked poiter
typedef cds::details::marked_ptr< value_type, 3 > node_ptr;
typedef cds::details::Allocator< array_node, node_allocator > cxx_array_node_allocator;
typedef multilevel_hashset::details::hash_splitter< hash_type > hash_splitter;
-
- struct metrics {
- size_t head_node_size; // power-of-two
- size_t head_node_size_log; // log2( head_node_size )
- size_t array_node_size; // power-of-two
- size_t array_node_size_log;// log2( array_node_size )
- };
//@endcond
protected:
//@cond
- /// Bidirectional iterator class
- template <bool IsConst>
- class bidirectional_iterator
+ class iterator_base
{
friend class MultiLevelHashSet;
+ protected:
array_node * m_pNode; ///< current array node
size_t m_idx; ///< current position in m_pNode
typename gc::Guard m_guard; ///< HP guard
MultiLevelHashSet const* m_set; ///< Hash set
public:
- typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
- typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
-
- public:
- bidirectional_iterator() CDS_NOEXCEPT
+ iterator_base() CDS_NOEXCEPT
: m_pNode( nullptr )
, m_idx( 0 )
, m_set( nullptr )
{}
- bidirectional_iterator( bidirectional_iterator const& rhs ) CDS_NOEXCEPT
+ iterator_base( iterator_base const& rhs ) CDS_NOEXCEPT
: m_pNode( rhs.m_pNode )
, m_idx( rhs.m_idx )
, m_set( rhs.m_set )
m_guard.copy( rhs.m_guard );
}
- bidirectional_iterator& operator=(bidirectional_iterator const& rhs) CDS_NOEXCEPT
+ iterator_base& operator=(iterator_base const& rhs) CDS_NOEXCEPT
{
m_pNode = rhs.m_pNode;
m_idx = rhs.m_idx;
return *this;
}
- bidirectional_iterator& operator++()
+ iterator_base& operator++()
{
forward();
return *this;
}
- bidirectional_iterator& operator--()
+ iterator_base& operator--()
{
backward();
return *this;
}
- value_ptr operator ->() const CDS_NOEXCEPT
- {
- return pointer();
- }
-
- value_ref operator *() const CDS_NOEXCEPT
- {
- value_ptr p = pointer();
- assert( p );
- return *p;
- }
-
void release()
{
m_guard.clear();
}
- template <bool IsConst2>
- bool operator ==(bidirectional_iterator<IsConst2> const& rhs) const
+ bool operator ==(iterator_base const& rhs) const CDS_NOEXCEPT
{
return m_pNode == rhs.m_pNode && m_idx == rhs.m_idx && m_set == rhs.m_set;
}
- template <bool IsConst2>
- bool operator !=(bidirectional_iterator<IsConst2> const& rhs) const
+ bool operator !=(iterator_base const& rhs) const CDS_NOEXCEPT
{
return !( *this == rhs );
}
protected:
- bidirectional_iterator( MultiLevelHashSet& set, array_node * pNode, size_t idx, bool )
+ iterator_base( MultiLevelHashSet const& set, array_node * pNode, size_t idx, bool )
: m_pNode( pNode )
, m_idx( idx )
, m_set( &set )
{}
- bidirectional_iterator( MultiLevelHashSet& set, array_node * pNode, size_t idx )
+ iterator_base( MultiLevelHashSet const& set, array_node * pNode, size_t idx )
: m_pNode( pNode )
, m_idx( idx )
, m_set( &set )
forward();
}
- value_ptr pointer() const CDS_NOEXCEPT
+ value_type * pointer() const CDS_NOEXCEPT
{
return m_guard.template get<value_type>();
}
}
};
+ template <class Iterator>
+ Iterator init_begin() const
+ {
+ return Iterator( *this, m_Head, size_t(0) - 1 );
+ }
+
+ template <class Iterator>
+ Iterator init_end() const
+ {
+ return Iterator( *this, m_Head, head_size(), false );
+ }
+
+ template <class Iterator>
+ Iterator init_rbegin() const
+ {
+ return Iterator( *this, m_Head, head_size() );
+ }
+
+ template <class Iterator>
+ Iterator init_rend() const
+ {
+ return Iterator( *this, m_Head, size_t(0) - 1, false );
+ }
+
+ /// Bidirectional iterator class
+ template <bool IsConst>
+ class bidirectional_iterator: protected iterator_base
+ {
+ friend class MultiLevelHashSet;
+
+ protected:
+ static CDS_CONSTEXPR bool const c_bConstantIterator = IsConst;
+
+ public:
+ typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
+ typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
+
+ public:
+ bidirectional_iterator() CDS_NOEXCEPT
+ {}
+
+ bidirectional_iterator( bidirectional_iterator const& rhs ) CDS_NOEXCEPT
+ : iterator_base( rhs )
+ {}
+
+ bidirectional_iterator& operator=(bidirectional_iterator const& rhs) CDS_NOEXCEPT
+ {
+ iterator_base::operator=( rhs );
+ return *this;
+ }
+
+ bidirectional_iterator& operator++()
+ {
+ iterator_base::operator++();
+ return *this;
+ }
+
+ bidirectional_iterator& operator--()
+ {
+ iterator_base::operator--();
+ return *this;
+ }
+
+ value_ptr operator ->() const CDS_NOEXCEPT
+ {
+ return iterator_base::pointer();
+ }
+
+ value_ref operator *() const CDS_NOEXCEPT
+ {
+ value_ptr p = iterator_base::pointer();
+ assert( p );
+ return *p;
+ }
+
+ void release()
+ {
+ iterator_base::release();
+ }
+
+ template <bool IsConst2>
+ bool operator ==(bidirectional_iterator<IsConst2> const& rhs) const CDS_NOEXCEPT
+ {
+ return iterator_base::operator==( rhs );
+ }
+
+ template <bool IsConst2>
+ bool operator !=(bidirectional_iterator<IsConst2> const& rhs) const CDS_NOEXCEPT
+ {
+ return !( *this == rhs );
+ }
+
+ protected:
+ bidirectional_iterator( MultiLevelHashSet& set, array_node * pNode, size_t idx, bool )
+ : iterator_base( set, pNode, idx, false )
+ {}
+
+ bidirectional_iterator( MultiLevelHashSet& set, array_node * pNode, size_t idx )
+ : iterator_base( set, pNode, idx )
+ {}
+ };
+
/// Reverse bidirectional iterator
template <bool IsConst>
- class reverse_bidirectional_iterator : protected bidirectional_iterator<IsConst>
+ class reverse_bidirectional_iterator : public iterator_base
{
- typedef bidirectional_iterator<IsConst> base_class;
friend class MultiLevelHashSet;
public:
- typedef typename base_class::value_ptr value_ptr;
- typedef typename base_class::value_ref value_ref;
+ typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
+ typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
public:
reverse_bidirectional_iterator() CDS_NOEXCEPT
- : base_class()
+ : iterator_base()
{}
reverse_bidirectional_iterator( reverse_bidirectional_iterator const& rhs ) CDS_NOEXCEPT
- : base_class( rhs )
+ : iterator_base( rhs )
{}
reverse_bidirectional_iterator& operator=( reverse_bidirectional_iterator const& rhs) CDS_NOEXCEPT
{
- base_class::operator=( rhs );
+ iterator_base::operator=( rhs );
return *this;
}
reverse_bidirectional_iterator& operator++()
{
- base_class::backward();
+ iterator_base::operator--();
return *this;
}
reverse_bidirectional_iterator& operator--()
{
- base_class::forward();
+ iterator_base::operator++();
return *this;
}
value_ptr operator ->() const CDS_NOEXCEPT
{
- return base_class::operator->();
+ return iterator_base::pointer();
}
value_ref operator *() const CDS_NOEXCEPT
{
- return base_class::operator*();
+ value_ptr p = iterator_base::pointer();
+ assert( p );
+ return *p;
}
void release()
{
- base_class::release();
+ iterator_base::release();
}
template <bool IsConst2>
bool operator ==(reverse_bidirectional_iterator<IsConst2> const& rhs) const
{
- return base_class::operator==( rhs );
+ return iterator_base::operator==( rhs );
}
template <bool IsConst2>
}
private:
+ reverse_bidirectional_iterator( MultiLevelHashSet& set, array_node * pNode, size_t idx, bool )
+ : iterator_base( set, pNode, idx, false )
+ {}
+
reverse_bidirectional_iterator( MultiLevelHashSet& set, array_node * pNode, size_t idx )
- : base_class( set, pNode, idx, false )
+ : iterator_base( set, pNode, idx, false )
{
- base_class::backward();
+ iterator_base::backward();
}
};
//@endcond
public:
- typedef bidirectional_iterator<false> iterator; ///< @ref cds_intrusive_MultilevelHashSet_iterators "bidirectional iterator" type
- typedef bidirectional_iterator<true> const_iterator; ///< @ref cds_intrusive_MultilevelHashSet_iterators "bidirectional const iterator" type
- typedef reverse_bidirectional_iterator<false> reverse_iterator; ///< @ref cds_intrusive_MultilevelHashSet_iterators "bidirectional reverse iterator" type
- typedef reverse_bidirectional_iterator<true> const_reverse_iterator; ///< @ref cds_intrusive_MultilevelHashSet_iterators "bidirectional reverse const iterator" type
+#ifdef CDS_DOXYGEN_INVOKED
+ typedef implementation_defined iterator; ///< @ref cds_intrusive_MultilevelHashSet_iterators "bidirectional iterator" type
+ typedef implementation_defined const_iterator; ///< @ref cds_intrusive_MultilevelHashSet_iterators "bidirectional const iterator" type
+ typedef implementation_defined reverse_iterator; ///< @ref cds_intrusive_MultilevelHashSet_iterators "bidirectional reverse iterator" type
+ typedef implementation_defined const_reverse_iterator; ///< @ref cds_intrusive_MultilevelHashSet_iterators "bidirectional reverse const iterator" type
+#else
+ typedef bidirectional_iterator<false> iterator;
+ typedef bidirectional_iterator<true> const_iterator;
+ typedef reverse_bidirectional_iterator<false> reverse_iterator;
+ typedef reverse_bidirectional_iterator<true> const_reverse_iterator;
+#endif
private:
//@cond
- metrics const m_Metrics; ///< Metrics
+ multilevel_hashset::details::metrics const m_Metrics; ///< Metrics
array_node * m_Head; ///< Head array
item_counter m_ItemCounter; ///< Item counter
stat m_Stat; ///< Internal statistics
where \p N is multi-level array depth.
*/
MultiLevelHashSet( size_t head_bits = 8, size_t array_bits = 4 )
- : m_Metrics(make_metrics( head_bits, array_bits ))
+ : m_Metrics( multilevel_hashset::details::metrics::make( head_bits, array_bits, sizeof(hash_type)))
, m_Head( alloc_head_node())
{}
/// Inserts new node
/**
- The function inserts \p val in the set if it does not contain
+ The function inserts \p val in the set if it does not contain
an item with that hash.
Returns \p true if \p val is placed into the set, \p false otherwise.
array_node * pArr = m_Head;
size_t nSlot = splitter.cut( m_Metrics.head_node_size_log );
assert( nSlot < m_Metrics.head_node_size );
+ size_t nHeight = 1;
while ( true ) {
node_ptr slot = pArr->nodes[nSlot].load( memory_model::memory_order_acquire );
assert( nSlot < m_Metrics.array_node_size );
pArr = to_array( slot.ptr() );
nOffset += m_Metrics.array_node_size_log;
+ ++nHeight;
}
else if ( slot.bits() == flag_array_converting ) {
// the slot is converting to array node right now
f( val );
++m_ItemCounter;
m_Stat.onInsertSuccess();
+ m_Stat.height( nHeight );
return true;
}
*/
std::pair<bool, bool> update( value_type& val, bool bInsert = true )
{
- hash_type const& hash = hash_accessor()( val );
- hash_splitter splitter( hash );
- hash_comparator cmp;
- typename gc::Guard guard;
- back_off bkoff;
-
- array_node * pArr = m_Head;
- size_t nSlot = splitter.cut( m_Metrics.head_node_size_log );
- assert( nSlot < m_Metrics.head_node_size );
- size_t nOffset = m_Metrics.head_node_size_log;
-
- while ( true ) {
- node_ptr slot = pArr->nodes[nSlot].load( memory_model::memory_order_acquire );
- if ( slot.bits() == flag_array_node ) {
- // array node, go down the tree
- assert( slot.ptr() != nullptr );
- nSlot = splitter.cut( m_Metrics.array_node_size_log );
- assert( nSlot < m_Metrics.array_node_size );
- pArr = to_array( slot.ptr() );
- nOffset += m_Metrics.array_node_size_log;
- }
- else if ( slot.bits() == flag_array_converting ) {
- // the slot is converting to array node right now
- bkoff();
- m_Stat.onSlotConverting();
- }
- else {
- // data node
- assert(slot.bits() == 0 );
-
- // protect data node by hazard pointer
- if ( guard.protect( pArr->nodes[nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) {
- // slot value has been changed - retry
- m_Stat.onSlotChanged();
- }
- else if ( slot.ptr() ) {
- if ( cmp( hash, hash_accessor()( *slot.ptr() )) == 0 ) {
- // the item with that hash value already exists
- // Replace it with val
- if ( slot.ptr() == &val ) {
- m_Stat.onUpdateExisting();
- return std::make_pair( true, false );
- }
-
- if ( pArr->nodes[nSlot].compare_exchange_strong( slot, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed )) {
- // slot can be disposed
- gc::template retire<disposer>( slot.ptr() );
- m_Stat.onUpdateExisting();
- return std::make_pair( true, false );
- }
-
- m_Stat.onUpdateRetry();
- continue;
- }
-
- // the slot must be expanded
- expand_slot( pArr, nSlot, slot, nOffset );
- }
- else {
- // the slot is empty, try to insert data node
- if ( bInsert ) {
- node_ptr pNull;
- if ( pArr->nodes[nSlot].compare_exchange_strong( pNull, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
- {
- // the new data node has been inserted
- ++m_ItemCounter;
- m_Stat.onUpdateNew();
- return std::make_pair( true, true );
- }
- }
- else {
- m_Stat.onUpdateFailed();
- return std::make_pair( false, false );
- }
-
- // insert failed - slot has been changed by another thread
- // retry updating
- m_Stat.onUpdateRetry();
- }
- }
- } // while
+ return do_update(val, [](value_type&, value_type *) {}, bInsert );
}
/// Unlinks the item \p val from the set
typename gc::Guard guard;
auto pred = [&val](value_type const& item) -> bool { return &item == &val; };
value_type * p = do_erase( hash_accessor()( val ), guard, std::ref( pred ));
-
- // p is guarded by HP
- if ( p ) {
- gc::template retire<disposer>( p );
- --m_ItemCounter;
- m_Stat.onEraseSuccess();
- return true;
- }
- return false;
+ return p != nullptr;
}
/// Deletes the item from the set
- /**
+ /**
The function searches \p hash in the set,
unlinks the item found, and returns \p true.
If that item is not found the function returns \p false.
The \ref disposer specified in \p Traits is called by garbage collector \p GC asynchronously.
-
*/
bool erase( hash_type const& hash )
{
// p is guarded by HP
if ( p ) {
- gc::template retire<disposer>( p );
- --m_ItemCounter;
f( *p );
- m_Stat.onEraseSuccess();
return true;
}
return false;
}
- /// Deletes the item pointed by iterator \p it
+ /// Deletes the item pointed by iterator \p iter
/**
Returns \p true if the operation is successful, \p false otherwise.
The function does not invalidate the iterator, it remains valid and can be used for further traversing.
*/
- bool erase_at( iterator const& it )
+ bool erase_at( iterator const& iter )
{
- if ( it.m_set != this )
- return false;
- if ( it.m_pNode == m_Head && it.m_idx >= head_size())
- return false;
- if ( it.m_idx >= array_node_size() )
- return false;
-
- for (;;) {
- node_ptr slot = it.m_pNode->nodes[it.m_idx].load( memory_model::memory_order_acquire );
- if ( slot.bits() == 0 && slot.ptr() == it.pointer() ) {
- if ( it.m_pNode->nodes[it.m_idx].compare_exchange_strong(slot, node_ptr(nullptr), memory_model::memory_order_acquire, atomics::memory_order_relaxed) ) {
- // the item is guarded by iterator, so we may retire it safely
- gc::template retire<disposer>( slot.ptr() );
- --m_ItemCounter;
- m_Stat.onEraseSuccess();
- return true;
- }
- }
- else
- return false;
- }
+ return do_erase_at( iter );
}
+ //@cond
+ bool erase_at( reverse_iterator const& iter )
+ {
+ return do_erase_at( iter );
+ }
+ //@endcond
/// Extracts the item with specified \p hash
- /**
+ /**
The function searches \p hash in the set,
unlinks it from the set, and returns an guarded pointer to the item extracted.
If \p hash is not found the function returns an empty guarded pointer.
guarded_ptr gp;
{
typename gc::Guard guard;
- value_type * p = do_erase( hash, guard, []( value_type const&) -> bool {return true; } );
+ value_type * p = do_erase( hash, guard, []( value_type const&) -> bool {return true;} );
// p is guarded by HP
- if ( p ) {
- gc::template retire<disposer>( p );
- --m_ItemCounter;
- m_Stat.onEraseSuccess();
+ if ( p )
gp.reset( p );
- }
}
return gp;
}
public:
///@name Thread-safe iterators
/** @anchor cds_intrusive_MultilevelHashSet_iterators
- The set supports thread-safe iterators: you may iterate over the set in multi-threaded environment.\r
- It is guaranteed that the iterators will remain valid even if another thread deletes the node the iterator points to:\r
- Hazard Pointer embedded into the iterator object protects the node from physical reclamation.\r
-\r
- @note Since the iterator object contains hazard pointer that is a thread-local resource,\r
- the iterator should not be passed to another thread.\r
-\r
- Each iterator object supports the common interface:\r
- - dereference operators:\r
- @code\r
- value_type [const] * operator ->() noexcept\r
- value_type [const] & operator *() noexcept\r
- @endcode\r
- - pre-increment and pre-decrement. Post-operators is not supported\r
- - equality operators <tt>==</tt> and <tt>!=</tt>.\r
+ The set supports thread-safe iterators: you may iterate over the set in multi-threaded environment.
+ It is guaranteed that the iterators will remain valid even if another thread deletes the node the iterator points to:
+ Hazard Pointer embedded into the iterator object protects the node from physical reclamation.
+
+ @note Since the iterator object contains hazard pointer that is a thread-local resource,
+ the iterator should not be passed to another thread.
+
+ Each iterator object supports the common interface:
+ - dereference operators:
+ @code
+ value_type [const] * operator ->() noexcept
+ value_type [const] & operator *() noexcept
+ @endcode
+ - pre-increment and pre-decrement. Post-operators is not supported
+ - equality operators <tt>==</tt> and <tt>!=</tt>.
Iterators are equal iff they point to the same cell of the same array node.
- Note that for two iterators \p it1 and \p it2, the conditon <tt> it1 == it2 </tt>
+ Note that for two iterators \p it1 and \p it2, the conditon <tt> it1 == it2 </tt>
does not entail <tt> &(*it1) == &(*it2) </tt>: welcome to concurrent containers
- - helper member function \p release() that clears internal hazard pointer.\r
- After \p release() call the iterator points to \p nullptr but it still remain valid: further iterating is possible.
+ - helper member function \p release() that clears internal hazard pointer.
+ After \p release() the iterator points to \p nullptr but it still remain valid: further iterating is possible.
+
+ During iteration you may safely erase any item from the set;
+ @ref erase_at() function call doesn't invalidate any iterator.
+ If some iterator points to the item to be erased, that item is not deleted immediately
+ but only after that iterator will be advanced forward or backward.
+
+ @note It is possible the item can be iterated more that once, for example, if an iterator points to the item
+ in array node that is being splitted.
*/
///@{
return const_iterator( *this, m_Head, size_t(0) - 1 );
}
- /// 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.
+ /// 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.
iterator end()
{
- return iterator( *this, m_Head, head_size() - 1 );
+ return iterator( *this, m_Head, head_size(), false );
}
- /// 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.
+ /// 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 end() const
{
- return const_iterator( *this, m_Head, head_size() - 1 );
+ return const_iterator( *this, m_Head, head_size(), false );
}
- /// 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.
+ /// 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()
{
- return const_iterator( *this, m_Head, head_size() - 1 );
+ return const_iterator( *this, m_Head, head_size(), false );
}
/// Returns a reverse iterator to the first element of the reversed set
/// 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.
+ 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.
*/
reverse_iterator rend()
{
- return reverse_iterator( *this, m_Head, 0 );
+ return reverse_iterator( *this, m_Head, size_t(0) - 1, false );
}
/// 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.
+ 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.
*/
const_reverse_iterator rend() const
{
- return const_reverse_iterator( *this, m_Head, 0 );
+ return const_reverse_iterator( *this, m_Head, size_t(0) - 1, false );
}
/// 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.
+ 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.
*/
const_reverse_iterator crend()
{
- return const_reverse_iterator( *this, m_Head, 0 );
+ return const_reverse_iterator( *this, m_Head, size_t(0) - 1, false );
}
///@}
private:
//@cond
- static metrics make_metrics( size_t head_bits, size_t array_bits )
- {
- size_t const hash_bits = sizeof( hash_type ) * 8;
-
- if ( array_bits < 2 )
- array_bits = 2;
- if ( head_bits < 4 )
- head_bits = 4;
- if ( head_bits > hash_bits )
- head_bits = hash_bits;
- if ( (hash_bits - head_bits) % array_bits != 0 )
- head_bits += (hash_bits - head_bits) % array_bits;
-
- assert( (hash_bits - head_bits) % array_bits == 0 );
-
- metrics m;
- m.head_node_size_log = head_bits;
- m.head_node_size = size_t(1) << head_bits;
- m.array_node_size_log = array_bits;
- m.array_node_size = size_t(1) << array_bits;
- return m;
- }
array_node * alloc_head_node() const
{
node_ptr cur(current.ptr());
atomic_node_ptr& slot = pParent->nodes[idxParent];
- if ( !slot.compare_exchange_strong( cur, cur | flag_array_converting, memory_model::memory_order_release, atomics::memory_order_relaxed ))
+ if ( !slot.compare_exchange_strong( cur, cur | flag_array_converting, memory_model::memory_order_release, atomics::memory_order_relaxed ))
{
m_Stat.onExpandNodeFailed();
free_array_node( pArr );
pArr->nodes[idx].store( current, memory_model::memory_order_release );
cur = cur | flag_array_converting;
- CDS_VERIFY(
+ CDS_VERIFY(
slot.compare_exchange_strong( cur, node_ptr( to_node( pArr ), flag_array_node ), memory_model::memory_order_release, atomics::memory_order_relaxed )
);
+ m_Stat.onExpandNodeSuccess();
m_Stat.onArrayNodeCreated();
return true;
}
+ //@endcond
+ protected:
+ //@cond
value_type * search( hash_type const& hash, typename gc::Guard& guard )
{
hash_splitter splitter( hash );
else if ( slot.ptr() ) {
if ( cmp( hash, hash_accessor()( *slot.ptr() )) == 0 && pred( *slot.ptr() )) {
// item found - replace it with nullptr
- if ( pArr->nodes[nSlot].compare_exchange_strong(slot, node_ptr(nullptr), memory_model::memory_order_acquire, atomics::memory_order_relaxed))
+ if ( pArr->nodes[nSlot].compare_exchange_strong(slot, node_ptr(nullptr), memory_model::memory_order_acquire, atomics::memory_order_relaxed) ) {
+ // slot is guarded by HP
+ gc::template retire<disposer>( slot.ptr() );
+ --m_ItemCounter;
+ m_Stat.onEraseSuccess();
+
return slot.ptr();
+ }
m_Stat.onEraseRetry();
continue;
}
} // while
}
+ bool do_erase_at( iterator_base const& iter )
+ {
+ if ( iter.m_set != this )
+ return false;
+ if ( iter.m_pNode == m_Head && iter.m_idx >= head_size())
+ return false;
+ if ( iter.m_idx >= array_node_size() )
+ return false;
+
+ for (;;) {
+ node_ptr slot = iter.m_pNode->nodes[iter.m_idx].load( memory_model::memory_order_acquire );
+ if ( slot.bits() == 0 && slot.ptr() == iter.pointer() ) {
+ if ( iter.m_pNode->nodes[iter.m_idx].compare_exchange_strong(slot, node_ptr(nullptr), memory_model::memory_order_acquire, atomics::memory_order_relaxed) ) {
+ // the item is guarded by iterator, so we may retire it safely
+ gc::template retire<disposer>( slot.ptr() );
+ --m_ItemCounter;
+ m_Stat.onEraseSuccess();
+ return true;
+ }
+ }
+ else
+ return false;
+ }
+ }
+
+ template <typename Func>
+ std::pair<bool, bool> do_update( value_type& val, Func f, bool bInsert = true )
+ {
+ hash_type const& hash = hash_accessor()( val );
+ hash_splitter splitter( hash );
+ hash_comparator cmp;
+ typename gc::template GuardArray<2> guards;
+ back_off bkoff;
+
+ array_node * pArr = m_Head;
+ size_t nSlot = splitter.cut( m_Metrics.head_node_size_log );
+ assert( nSlot < m_Metrics.head_node_size );
+ size_t nOffset = m_Metrics.head_node_size_log;
+ size_t nHeight = 1;
+
+ guards.assign( 1, &val );
+
+ while ( true ) {
+ node_ptr slot = pArr->nodes[nSlot].load( memory_model::memory_order_acquire );
+ if ( slot.bits() == flag_array_node ) {
+ // array node, go down the tree
+ assert( slot.ptr() != nullptr );
+ nSlot = splitter.cut( m_Metrics.array_node_size_log );
+ assert( nSlot < m_Metrics.array_node_size );
+ pArr = to_array( slot.ptr() );
+ nOffset += m_Metrics.array_node_size_log;
+ ++nHeight;
+ }
+ else if ( slot.bits() == flag_array_converting ) {
+ // the slot is converting to array node right now
+ bkoff();
+ m_Stat.onSlotConverting();
+ }
+ else {
+ // data node
+ assert(slot.bits() == 0 );
+
+ // protect data node by hazard pointer
+ if ( guards.protect( 0, pArr->nodes[nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) {
+ // slot value has been changed - retry
+ m_Stat.onSlotChanged();
+ }
+ else if ( slot.ptr() ) {
+ if ( cmp( hash, hash_accessor()( *slot.ptr() )) == 0 ) {
+ // the item with that hash value already exists
+ // Replace it with val
+ if ( slot.ptr() == &val ) {
+ m_Stat.onUpdateExisting();
+ return std::make_pair( true, false );
+ }
+
+ if ( pArr->nodes[nSlot].compare_exchange_strong( slot, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed )) {
+ // slot can be disposed
+ f( val, slot.ptr() );
+ gc::template retire<disposer>( slot.ptr() );
+ m_Stat.onUpdateExisting();
+ return std::make_pair( true, false );
+ }
+
+ m_Stat.onUpdateRetry();
+ continue;
+ }
+
+ // the slot must be expanded
+ expand_slot( pArr, nSlot, slot, nOffset );
+ }
+ else {
+ // the slot is empty, try to insert data node
+ if ( bInsert ) {
+ node_ptr pNull;
+ if ( pArr->nodes[nSlot].compare_exchange_strong( pNull, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
+ {
+ // the new data node has been inserted
+ f( val, nullptr );
+ ++m_ItemCounter;
+ m_Stat.onUpdateNew();
+ m_Stat.height( nHeight );
+ return std::make_pair( true, true );
+ }
+ }
+ else {
+ m_Stat.onUpdateFailed();
+ return std::make_pair( false, false );
+ }
+
+ // insert failed - slot has been changed by another thread
+ // retry updating
+ m_Stat.onUpdateRetry();
+ }
+ }
+ } // while
+ }
//@endcond
};
}} // namespace cds::intrusive
/*
-//@cond
namespace std {
template <class GC, typename T, typename Traits>
};
} // namespace std
-//@endcond
*/
#endif // #ifndef CDSLIB_INTRUSIVE_IMPL_MULTILEVEL_HASHSET_H
projects / libcds.git / blobdiff