From: khizmax Date: Wed, 30 Sep 2015 20:03:02 +0000 (+0300) Subject: Added intrusive::MultiLevelHashSet implementation X-Git-Tag: v2.1.0~95 X-Git-Url: http://plrg.eecs.uci.edu/git/?p=libcds.git;a=commitdiff_plain;h=8bcb72c9410d4efd572c2da733d5e8f839ad3563 Added intrusive::MultiLevelHashSet implementation --- diff --git a/cds/container/impl/multilevel_hashmap.h b/cds/container/impl/multilevel_hashmap.h index e5ee5943..09fadc16 100644 --- a/cds/container/impl/multilevel_hashmap.h +++ b/cds/container/impl/multilevel_hashmap.h @@ -703,6 +703,14 @@ namespace cds { namespace container { does not entail &(*it1) == &(*it2) - 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. */ ///@{ /// Returns an iterator to the beginning of the map diff --git a/cds/container/impl/multilevel_hashset.h b/cds/container/impl/multilevel_hashset.h index 79466216..8a353e59 100644 --- a/cds/container/impl/multilevel_hashset.h +++ b/cds/container/impl/multilevel_hashset.h @@ -75,7 +75,7 @@ namespace cds { namespace container { There are several specializations of \p %MultiLevelHashSet for each \p GC. You should include: - for \p gc::HP garbage collector - for \p gc::DHP garbage collector - - for \ref cds_intrusive_MultiLevelHashSet_rcu "RCU type". RCU specialization + - for \ref cds_intrusive_MultilevelHashSet_rcu "RCU type". RCU specialization has a slightly different interface. */ template < @@ -461,6 +461,14 @@ namespace cds { namespace container { does not entail &(*it1) == &(*it2) - 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. */ ///@{ diff --git a/cds/intrusive/details/multilevel_hashset_base.h b/cds/intrusive/details/multilevel_hashset_base.h index 048f6eec..1327a0a2 100644 --- a/cds/intrusive/details/multilevel_hashset_base.h +++ b/cds/intrusive/details/multilevel_hashset_base.h @@ -57,6 +57,7 @@ namespace cds { namespace intrusive { event_counter m_nSlotConverting; ///< Number of events when we encounter a slot while it is converting to array node event_counter m_nArrayNodeCount; ///< Number of array nodes + event_counter m_nHeight; ///< Current height of the tree //@cond void onInsertSuccess() { ++m_nInsertSuccess; } @@ -77,6 +78,7 @@ namespace cds { namespace intrusive { void onSlotChanged() { ++m_nSlotChanged; } void onSlotConverting() { ++m_nSlotConverting; } void onArrayNodeCreated() { ++m_nArrayNodeCount; } + void height( size_t h ) { if (m_nHeight < h ) m_nHeight = h; } //@endcond }; @@ -101,6 +103,7 @@ namespace cds { namespace intrusive { void onSlotChanged() const {} void onSlotConverting() const {} void onArrayNodeCreated() const {} + void height(size_t) const {} //@endcond }; @@ -251,9 +254,39 @@ namespace cds { namespace intrusive { namespace details { template using hash_splitter = cds::algo::split_bitstring< HashType, UInt >; + + 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 ) + + static metrics make(size_t head_bits, size_t array_bits, size_t hash_size ) + { + size_t const hash_bits = hash_size * 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; + } + }; + } // namespace details //@endcond - } // namespace multilevel_hashset //@cond diff --git a/cds/intrusive/impl/multilevel_hashset.h b/cds/intrusive/impl/multilevel_hashset.h index 37a5414a..5c3c5455 100644 --- a/cds/intrusive/impl/multilevel_hashset.h +++ b/cds/intrusive/impl/multilevel_hashset.h @@ -77,7 +77,7 @@ namespace cds { namespace intrusive { There are several specializations of \p %MultiLevelHashSet for each \p GC. You should include: - for \p gc::HP garbage collector - for \p gc::DHP garbage collector - - for \ref cds_intrusive_MultiLevelHashSet_rcu "RCU type". RCU specialization + - for \ref cds_intrusive_MultilevelHashSet_rcu "RCU type". RCU specialization has a slightly different interface. */ template < @@ -161,13 +161,6 @@ namespace cds { namespace intrusive { 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: @@ -564,7 +557,7 @@ namespace cds { namespace intrusive { 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 @@ -583,7 +576,7 @@ namespace cds { namespace intrusive { 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()) {} @@ -638,6 +631,7 @@ namespace cds { namespace intrusive { 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 ); @@ -648,6 +642,7 @@ namespace cds { namespace intrusive { 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 @@ -682,6 +677,7 @@ namespace cds { namespace intrusive { f( val ); ++m_ItemCounter; m_Stat.onInsertSuccess(); + m_Stat.height( nHeight ); return true; } @@ -972,6 +968,14 @@ namespace cds { namespace intrusive { does not entail &(*it1) == &(*it2) : welcome to concurrent containers - 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. */ ///@{ @@ -1062,28 +1066,6 @@ namespace cds { namespace intrusive { 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 { @@ -1218,6 +1200,7 @@ namespace cds { namespace intrusive { 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; } @@ -1367,6 +1350,7 @@ namespace cds { namespace intrusive { 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 ); @@ -1379,6 +1363,7 @@ namespace cds { namespace intrusive { 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 @@ -1428,6 +1413,7 @@ namespace cds { namespace intrusive { f( val, nullptr ); ++m_ItemCounter; m_Stat.onUpdateNew(); + m_Stat.height( nHeight ); return std::make_pair( true, true ); } } diff --git a/cds/intrusive/multilevel_hashset_rcu.h b/cds/intrusive/multilevel_hashset_rcu.h new file mode 100644 index 00000000..3146a6ad --- /dev/null +++ b/cds/intrusive/multilevel_hashset_rcu.h @@ -0,0 +1,1407 @@ +//$$CDS-header$$ + +#ifndef CDSLIB_INTRUSIVE_MULTILEVEL_HASHSET_RCU_H +#define CDSLIB_INTRUSIVE_MULTILEVEL_HASHSET_RCU_H + +#include // std::ref +#include // std::iterator_traits + +#include +#include +#include +#include +#include + + +namespace cds { namespace intrusive { + /// Intrusive hash set based on multi-level array, \ref cds_urcu_desc "RCU" specialization + /** @ingroup cds_intrusive_map + @anchor cds_intrusive_MultilevelHashSet_rcu + + Source: + - [2013] Steven Feldman, Pierre LaBorde, Damian Dechev "Concurrent Multi-level Arrays: + Wait-free Extensible Hash Maps" + + See algorithm short description @ref cds_intrusive_MultilevelHashSet_hp "here" + + Template parameters: + - \p RCU - one of \ref cds_urcu_gc "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. + + @note Before including you should include appropriate RCU header file, + see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files. + + The set supports @ref cds_intrusive_MultilevelHashSet_rcu_iterators "bidirectional thread-safe iterators" + with some restrictions. + */ + template < + class RCU, + class T, +#ifdef CDS_DOXYGEN_INVOKED + class Traits = multilevel_hashset::traits +#else + class Traits +#endif + > + class MultiLevelHashSet< cds::urcu::gc< RCU >, T, Traits > + { + public: + 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 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 in Traits"); + + /// Hash type deduced from \p hash_accessor return type + typedef typename std::decay< + typename std::remove_reference< + decltype(hash_accessor()(std::declval())) + >::type + >::type hash_type; + //typedef typename std::result_of< hash_accessor( std::declval()) >::type hash_type; + static_assert(!std::is_pointer::value, "hash_accessor should return a reference to hash value"); + + typedef typename traits::disposer disposer; ///< data node disposer + +# 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< + hash_type, + traits, + multilevel_hashset::bitwise_compare< hash_type > + >::type hash_comparator; +# endif + + typedef typename traits::item_counter item_counter; ///< Item counter type + typedef typename traits::node_allocator node_allocator; ///< Array node allocator + typedef typename traits::memory_model memory_model; ///< Memory model + typedef typename traits::back_off back_off; ///< Backoff strategy + typedef typename traits::stat stat; ///< Internal statistics type + typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy + typedef typename gc::scoped_lock rcu_lock; ///< RCU scoped lock + static CDS_CONSTEXPR const bool c_bExtractLockExternal = false; ///< Group of \p extract_xxx functions does not require external locking + + using exempt_ptr = cds::urcu::exempt_ptr< gc, value_type, value_type, disposer, void >; ///< pointer to extracted node + + /// Node marked poiter + typedef cds::details::marked_ptr< value_type, 3 > node_ptr; + /// Array node element + typedef atomics::atomic< node_ptr > atomic_node_ptr; + + protected: + //@cond + enum node_flags { + flag_array_converting = 1, ///< the cell is converting from data node to an array node + flag_array_node = 2 ///< the cell is a pointer to an array node + }; + + struct array_node { + array_node * const pParent; ///< parent array node + size_t const idxParent; ///< index in parent array node + atomic_node_ptr nodes[1]; ///< node array + + array_node(array_node * parent, size_t idx) + : pParent(parent) + , idxParent(idx) + {} + + array_node() = delete; + array_node(array_node const&) = delete; + array_node(array_node&&) = delete; + }; + + typedef cds::details::Allocator< array_node, node_allocator > cxx_array_node_allocator; + typedef multilevel_hashset::details::hash_splitter< hash_type > hash_splitter; + typedef cds::urcu::details::check_deadlock_policy< gc, rcu_check_deadlock> check_deadlock_policy; + + //@endcond + + private: + //@cond + 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 + //@endcond + + public: + /// Creates empty set + /** + @param head_bits: 2head_bits specifies the size of head array, minimum is 4. + @param array_bits: 2array_bits specifies the size of array node, minimum is 2. + + Equation for \p head_bits and \p array_bits: + \code + sizeof(hash_type) * 8 == head_bits + N * array_bits + \endcode + where \p N is multi-level array depth. + */ + MultiLevelHashSet(size_t head_bits = 8, size_t array_bits = 4) + : m_Metrics(multilevel_hashset::details::metrics::make(head_bits, array_bits, sizeof(hash_type))) + , m_Head(alloc_head_node()) + {} + + /// Destructs the set and frees all data + ~MultiLevelHashSet() + { + destroy_tree(); + free_array_node(m_Head); + } + + /// Inserts new node + /** + 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. + + The function locks RCU internally. + */ + bool insert( value_type& val ) + { + return insert( val, [](value_type&) {} ); + } + + /// 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 \p f functor to initialize \p val. + + The functor signature is: + \code + void func( value_type& val ); + \endcode + where \p val is the item inserted. + + The user-defined functor is called only if the inserting is success. + + The function locks RCU internally. + @warning See \ref cds_intrusive_item_creating "insert item troubleshooting". + */ + template + bool insert( value_type& val, Func f ) + { + hash_type const& hash = hash_accessor()( val ); + hash_splitter splitter( hash ); + hash_comparator cmp; + back_off bkoff; + + size_t nOffset = m_Metrics.head_node_size_log; + 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 ); + 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 ); + + rcu_lock rcuLock; + if ( pArr->nodes[nSlot].load(memory_model::memory_order_acquire) == slot ) { + if ( slot.ptr() ) { + if ( cmp( hash, hash_accessor()( *slot.ptr() )) == 0 ) { + // the item with that hash value already exists + m_Stat.onInsertFailed(); + return false; + } + + // the slot must be expanded + expand_slot( pArr, nSlot, slot, nOffset ); + } + else { + // the slot is empty, try to insert data node + 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 ); + ++m_ItemCounter; + m_Stat.onInsertSuccess(); + m_Stat.height( nHeight ); + return true; + } + + // insert failed - slot has been changed by another thread + // retry inserting + m_Stat.onInsertRetry(); + } + } + else + m_Stat.onSlotChanged(); + } + } // while + } + + /// Updates the node + /** + Performs inserting or updating the item with hash value equal to \p val. + - If hash value is found then existing item is replaced with \p val, old item is disposed + with \p Traits::disposer. Note that the disposer is called by \p GC asynchronously. + The function returns std::pair + - If hash value is not found and \p bInsert is \p true then \p val is inserted, + the function returns std::pair + - If hash value is not found and \p bInsert is \p false then the set is unchanged, + the function returns std::pair + + Returns std::pair where \p first is \p true if operation is successfull + (i.e. the item has been inserted or updated), + \p second is \p true if new item has been added or \p false if the set contains that hash. + + The function locks RCU internally. + */ + std::pair update( value_type& val, bool bInsert = true ) + { + return do_update(val, [](value_type&, value_type *) {}, bInsert ); + } + + /// Unlinks the item \p val from the set + /** + The function searches the item \p val in the set and unlink it + if it is found and its address is equal to &val. + + The function returns \p true if success and \p false otherwise. + + RCU should not be locked. The function locks RCU internally. + */ + bool unlink( value_type const& val ) + { + check_deadlock_policy::check(); + + auto pred = [&val](value_type const& item) -> bool { return &item == &val; }; + value_type * p; + { + rcu_lock rcuLock; + p = do_erase( hash_accessor()( val ), std::ref( pred )); + } + if ( p ) { + gc::template retire_ptr( p ); + return true; + } + return false; + } + + /// 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. + + RCU should not be locked. The function locks RCU internally. + */ + bool erase( hash_type const& hash ) + { + return erase(hash, [](value_type const&) {} ); + } + + /// Deletes the item from the set + /** + The function searches \p hash in the set, + call \p f functor with item found, and unlinks it from the set. + The \ref disposer specified in \p Traits is called + by garbage collector \p GC asynchronously. + + The \p Func interface is + \code + struct functor { + void operator()( value_type& item ); + }; + \endcode + + If \p hash is not found the function returns \p false. + + RCU should not be locked. The function locks RCU internally. + */ + template + bool erase( hash_type const& hash, Func f ) + { + check_deadlock_policy::check(); + + value_type * p; + + { + rcu_lock rcuLock; + p = do_erase( hash, []( value_type const&) -> bool { return true; } ); + } + + // p is guarded by HP + if ( p ) { + f( *p ); + gc::template retire_ptr(p); + return true; + } + return false; + } + + /// Extracts the item with specified \p hash + /** + The function searches \p hash in the set, + unlinks it from the set, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found. + If the item with key equal to \p key is not found the function returns an empty \p exempt_ptr. + + RCU \p 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 \p release() member function is called. + Example: + \code + typedef cds::intrusive::MultiLevelHashSet< 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(); + } + \endcode + */ + exempt_ptr extract( hash_type const& hash ) + { + check_deadlock_policy::check(); + + value_type * p; + { + rcu_lock rcuLock; + p = do_erase( hash, []( value_type const&) -> bool {return true;} ); + } + return exempt_ptr( p ); + } + + /// Finds an item by it's \p hash + /** + The function searches the item by \p hash and calls the functor \p f for item found. + The interface of \p Func functor is: + \code + struct functor { + void operator()( value_type& item ); + }; + \endcode + where \p item is the item found. + + The functor may change non-key fields of \p item. Note that the functor is only guarantee + that \p item cannot be disposed during the functor is executing. + The functor does not serialize simultaneous access to the set's \p item. If such access is + possible you must provide your own synchronization schema on item level to prevent unsafe item modifications. + + The function returns \p true if \p hash is found, \p false otherwise. + + The function applies RCU lock internally. + */ + template + bool find( hash_type const& hash, Func f ) + { + rcu_lock rcuLock; + + value_type * p = search( hash ); + if ( p ) { + f( *p ); + return true; + } + return false; + } + + /// Checks whether the set contains \p hash + /** + The function searches the item by its \p hash + and returns \p true if it is found, or \p false otherwise. + + The function applies RCU lock internally. + */ + bool contains( hash_type const& hash ) + { + return find( hash, [](value_type&) {} ); + } + + /// Finds an item by it's \p hash and returns the item found + /** + The function searches the item by its \p hash + and returns the pointer to the item found. + If \p hash is not found the function returns \p nullptr. + + RCU should be locked before the function invocation. + Returned pointer is valid only while RCU is locked. + + Usage: + \code + typedef cds::intrusive::MultiLevelHashSet< your_template_params > my_set; + my_set theSet; + // ... + { + // lock RCU + my_set::rcu_lock + + foo * p = theSet.get( 5 ); + if ( p ) { + // Deal with p + //... + } + } + \endcode + */ + value_type * get( hash_type const& hash ) + { + assert( gc::is_locked()); + return search( hash ); + } + + /// Clears the set (non-atomic) + /** + The function unlink all data node from the set. + The function is not atomic but is thread-safe. + After \p %clear() the set may not be empty because another threads may insert items. + + For each item the \p disposer is called after unlinking. + */ + void clear() + { + clear_array( m_Head, head_size() ); + } + + /// 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. + */ + bool empty() const + { + return size() == 0; + } + + /// Returns item count in the set + size_t size() const + { + return m_ItemCounter; + } + + /// Returns const reference to internal statistics + stat const& statistics() const + { + return m_Stat; + } + + /// Returns the size of head node + size_t head_size() const + { + return m_Metrics.head_node_size; + } + + /// Returns the size of the array node + size_t array_node_size() const + { + return m_Metrics.array_node_size; + } + + protected: + //@cond + class iterator_base + { + friend class MultiLevelHashSet; + + protected: + array_node * m_pNode; ///< current array node + size_t m_idx; ///< current position in m_pNode + value_type * m_pValue; ///< current value + MultiLevelHashSet const* m_set; ///< Hash set + + public: + iterator_base() CDS_NOEXCEPT + : m_pNode(nullptr) + , m_idx(0) + , m_pValue(nullptr) + , m_set(nullptr) + {} + + iterator_base(iterator_base const& rhs) CDS_NOEXCEPT + : m_pNode(rhs.m_pNode) + , m_idx(rhs.m_idx) + , m_pValue(rhs.m_pValue) + , m_set(rhs.m_set) + {} + + iterator_base& operator=(iterator_base const& rhs) CDS_NOEXCEPT + { + m_pNode = rhs.m_pNode; + m_idx = rhs.m_idx; + m_pValue = rhs.m_pValue; + m_set = rhs.m_set; + return *this; + } + + iterator_base& operator++() + { + forward(); + return *this; + } + + iterator_base& operator--() + { + backward(); + return *this; + } + + 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; + } + + bool operator !=(iterator_base const& rhs) const CDS_NOEXCEPT + { + return !(*this == rhs); + } + + protected: + iterator_base(MultiLevelHashSet const& set, array_node * pNode, size_t idx, bool) + : m_pNode(pNode) + , m_idx(idx) + , m_pValue(nullptr) + , m_set(&set) + {} + + iterator_base(MultiLevelHashSet const& set, array_node * pNode, size_t idx) + : m_pNode(pNode) + , m_idx(idx) + , m_pValue(nullptr) + , m_set(&set) + { + forward(); + } + + value_type * pointer() const CDS_NOEXCEPT + { + assert(gc::is_locked()); + return m_pValue; + } + + void forward() + { + assert( gc::is_locked()); + assert(m_set != nullptr); + assert(m_pNode != nullptr); + + size_t const arrayNodeSize = m_set->array_node_size(); + size_t const headSize = m_set->head_size(); + array_node * pNode = m_pNode; + size_t idx = m_idx + 1; + size_t nodeSize = m_pNode->pParent ? arrayNodeSize : headSize; + + for (;;) { + if (idx < nodeSize) { + node_ptr slot = pNode->nodes[idx].load(memory_model::memory_order_acquire); + if (slot.bits() == flag_array_node) { + // array node, go down the tree + assert(slot.ptr() != nullptr); + pNode = to_array(slot.ptr()); + idx = 0; + nodeSize = arrayNodeSize; + } + else if (slot.bits() == flag_array_converting) { + // the slot is converting to array node right now - skip the node + ++idx; + } + else { + if (slot.ptr()) { + // data node + m_pNode = pNode; + m_idx = idx; + m_pValue = slot.ptr(); + return; + } + ++idx; + } + } + else { + // up to parent node + if (pNode->pParent) { + idx = pNode->idxParent + 1; + pNode = pNode->pParent; + nodeSize = pNode->pParent ? arrayNodeSize : headSize; + } + else { + // end() + assert(pNode == m_set->m_Head); + assert(idx == headSize); + m_pNode = pNode; + m_idx = idx; + m_pValue = nullptr; + return; + } + } + } + } + + void backward() + { + assert(gc::is_locked()); + assert(m_set != nullptr); + assert(m_pNode != nullptr); + + size_t const arrayNodeSize = m_set->array_node_size(); + size_t const headSize = m_set->head_size(); + size_t const endIdx = size_t(0) - 1; + + array_node * pNode = m_pNode; + size_t idx = m_idx - 1; + size_t nodeSize = m_pNode->pParent ? arrayNodeSize : headSize; + + for (;;) { + if (idx != endIdx) { + node_ptr slot = pNode->nodes[idx].load(memory_model::memory_order_acquire); + if (slot.bits() == flag_array_node) { + // array node, go down the tree + assert(slot.ptr() != nullptr); + pNode = to_array(slot.ptr()); + nodeSize = arrayNodeSize; + idx = nodeSize - 1; + } + else if (slot.bits() == flag_array_converting) { + // the slot is converting to array node right now - skip the node + --idx; + } + else { + if (slot.ptr()) { + // data node + m_pNode = pNode; + m_idx = idx; + m_pValue = slot.ptr(); + return; + } + --idx; + } + } + else { + // up to parent node + if (pNode->pParent) { + idx = pNode->idxParent - 1; + pNode = pNode->pParent; + nodeSize = pNode->pParent ? arrayNodeSize : headSize; + } + else { + // rend() + assert(pNode == m_set->m_Head); + assert(idx == endIdx); + m_pNode = pNode; + m_idx = idx; + m_pValue = nullptr; + return; + } + } + } + } + }; + + template + Iterator init_begin() const + { + return Iterator(*this, m_Head, size_t(0) - 1); + } + + template + Iterator init_end() const + { + return Iterator(*this, m_Head, head_size(), false); + } + + template + Iterator init_rbegin() const + { + return Iterator(*this, m_Head, head_size()); + } + + template + Iterator init_rend() const + { + return Iterator(*this, m_Head, size_t(0) - 1, false); + } + + /// Bidirectional iterator class + template + 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; + } + + template + bool operator ==(bidirectional_iterator const& rhs) const CDS_NOEXCEPT + { + return iterator_base::operator==(rhs); + } + + template + bool operator !=(bidirectional_iterator 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 + class reverse_bidirectional_iterator : public iterator_base + { + friend class MultiLevelHashSet; + + 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: + reverse_bidirectional_iterator() CDS_NOEXCEPT + : iterator_base() + {} + + reverse_bidirectional_iterator(reverse_bidirectional_iterator const& rhs) CDS_NOEXCEPT + : iterator_base(rhs) + {} + + reverse_bidirectional_iterator& operator=(reverse_bidirectional_iterator const& rhs) CDS_NOEXCEPT + { + iterator_base::operator=(rhs); + return *this; + } + + reverse_bidirectional_iterator& operator++() + { + iterator_base::operator--(); + return *this; + } + + reverse_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; + } + + template + bool operator ==(reverse_bidirectional_iterator const& rhs) const + { + return iterator_base::operator==(rhs); + } + + template + bool operator !=(reverse_bidirectional_iterator const& rhs) + { + return !(*this == rhs); + } + + 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) + : iterator_base(set, pNode, idx, false) + { + iterator_base::backward(); + } + }; + //@endcond + + public: +#ifdef CDS_DOXYGEN_INVOKED + typedef implementation_defined iterator; ///< @ref cds_intrusive_MultilevelHashSet_rcu_iterators "bidirectional iterator" type + typedef implementation_defined const_iterator; ///< @ref cds_intrusive_MultilevelHashSet_rcu_iterators "bidirectional const iterator" type + typedef implementation_defined reverse_iterator; ///< @ref cds_intrusive_MultilevelHashSet_rcu_iterators "bidirectional reverse iterator" type + typedef implementation_defined const_reverse_iterator; ///< @ref cds_intrusive_MultilevelHashSet_rcu_iterators "bidirectional reverse const iterator" type +#else + typedef bidirectional_iterator iterator; + typedef bidirectional_iterator const_iterator; + typedef reverse_bidirectional_iterator reverse_iterator; + typedef reverse_bidirectional_iterator const_reverse_iterator; +#endif + + ///@name Thread-safe iterators + /** @anchor cds_intrusive_MultilevelHashSet_rcu_iterators + 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 \p erase() safely + while your thread is iterating. + + A typical example is: + \code + struct foo { + uint32_t hash; + // ... other fields + uint32_t payload; // only for example + }; + struct set_traits: cds::intrusive::multilevel_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::intrusive::MultiLevelHashSet< 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 + /endcode + + 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 == and !=. + 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 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. + */ + ///@{ + + /// Returns an iterator to the beginning of the set + iterator begin() + { + return iterator(*this, m_Head, size_t(0) - 1); + } + + /// Returns an const iterator to the beginning of the set + const_iterator begin() const + { + return const_iterator(*this, m_Head, size_t(0) - 1); + } + + /// Returns an const iterator to the beginning of the set + const_iterator cbegin() + { + 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. + iterator end() + { + 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. + const_iterator end() const + { + 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. + const_iterator cend() + { + return const_iterator(*this, m_Head, head_size(), false); + } + + /// Returns a reverse iterator to the first element of the reversed set + reverse_iterator rbegin() + { + return reverse_iterator(*this, m_Head, head_size()); + } + + /// Returns a const reverse iterator to the first element of the reversed set + const_reverse_iterator rbegin() const + { + return const_reverse_iterator(*this, m_Head, head_size()); + } + + /// Returns a const reverse iterator to the first element of the reversed set + const_reverse_iterator crbegin() + { + return const_reverse_iterator(*this, m_Head, head_size()); + } + + /// 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. + */ + reverse_iterator rend() + { + 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. + */ + const_reverse_iterator rend() const + { + 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. + */ + const_reverse_iterator crend() + { + return const_reverse_iterator(*this, m_Head, size_t(0) - 1, false); + } + ///@} + + protected: + //@cond + template + std::pair do_update(value_type& val, Func f, bool bInsert = true) + { + hash_type const& hash = hash_accessor()(val); + hash_splitter splitter(hash); + hash_comparator cmp; + 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; + + 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); + + value_type * pOld = nullptr; + { + rcu_lock rcuLock; + + if ( pArr->nodes[nSlot].load(memory_model::memory_order_acquire) == slot ) { + 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()); + pOld = slot.ptr(); + m_Stat.onUpdateExisting(); + goto update_existing_done; + } + + 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(); + } + } + else + m_Stat.onSlotChanged(); + continue; + } // rcu_lock + + // update success + update_existing_done: + if ( pOld ) + gc::template retire_ptr( pOld ); + return std::make_pair(true, false); + } + } // while + } + + template + value_type * do_erase( hash_type const& hash, Predicate pred) + { + assert(gc::is_locked()); + + hash_splitter splitter(hash); + hash_comparator cmp; + 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); + + 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()); + } + 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); + + if ( pArr->nodes[nSlot].load(memory_model::memory_order_acquire) == slot ) { + 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)) { + --m_ItemCounter; + m_Stat.onEraseSuccess(); + + return slot.ptr(); + } + m_Stat.onEraseRetry(); + continue; + } + m_Stat.onEraseFailed(); + return nullptr; + } + else { + // the slot is empty + m_Stat.onEraseFailed(); + return nullptr; + } + } + else + m_Stat.onSlotChanged(); + } + } // while + } + + value_type * search(hash_type const& hash ) + { + assert( gc::is_locked() ); + + hash_splitter splitter(hash); + hash_comparator cmp; + 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); + + 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()); + } + 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 ( pArr->nodes[nSlot].load(memory_model::memory_order_acquire) != slot) { + // slot value has been changed - retry + m_Stat.onSlotChanged(); + } + else if (slot.ptr() && cmp(hash, hash_accessor()(*slot.ptr())) == 0) { + // item found + m_Stat.onFindSuccess(); + return slot.ptr(); + } + m_Stat.onFindFailed(); + return nullptr; + } + } // while + } + + //@endcond + + private: + //@cond + array_node * alloc_head_node() const + { + return alloc_array_node(head_size(), nullptr, 0); + } + + array_node * alloc_array_node(array_node * pParent, size_t idxParent) const + { + return alloc_array_node(array_node_size(), pParent, idxParent); + } + + static array_node * alloc_array_node(size_t nSize, array_node * pParent, size_t idxParent) + { + array_node * pNode = cxx_array_node_allocator().NewBlock(sizeof(array_node) + sizeof(atomic_node_ptr) * (nSize - 1), pParent, idxParent); + for (atomic_node_ptr * p = pNode->nodes, *pEnd = pNode->nodes + nSize; p < pEnd; ++p) + p->store(node_ptr(), memory_model::memory_order_release); + return pNode; + } + + static void free_array_node(array_node * parr) + { + cxx_array_node_allocator().Delete(parr); + } + + void destroy_tree() + { + // The function is not thread-safe. For use in dtor only + // Remove data node + clear(); + + // Destroy all array nodes + destroy_array_nodes(m_Head, head_size()); + } + + void destroy_array_nodes(array_node * pArr, size_t nSize) + { + for (atomic_node_ptr * p = pArr->nodes, *pLast = pArr->nodes + nSize; p != pLast; ++p) { + node_ptr slot = p->load(memory_model::memory_order_acquire); + if (slot.bits() == flag_array_node) { + destroy_array_nodes(to_array(slot.ptr()), array_node_size()); + free_array_node(to_array(slot.ptr())); + p->store(node_ptr(), memory_model::memory_order_relaxed); + } + } + } + + void clear_array(array_node * pArrNode, size_t nSize) + { + back_off bkoff; + + + for (atomic_node_ptr * pArr = pArrNode->nodes, *pLast = pArr + nSize; pArr != pLast; ++pArr) { + while (true) { + node_ptr slot = pArr->load(memory_model::memory_order_acquire); + if (slot.bits() == flag_array_node) { + // array node, go down the tree + assert(slot.ptr() != nullptr); + clear_array(to_array(slot.ptr()), array_node_size()); + break; + } + else if (slot.bits() == flag_array_converting) { + // the slot is converting to array node right now + while ((slot = pArr->load(memory_model::memory_order_acquire)).bits() == flag_array_converting) { + bkoff(); + m_Stat.onSlotConverting(); + } + bkoff.reset(); + + assert(slot.ptr() != nullptr); + assert(slot.bits() == flag_array_node); + clear_array(to_array(slot.ptr()), array_node_size()); + break; + } + else { + // data node + if (pArr->compare_exchange_strong(slot, node_ptr(), memory_model::memory_order_acquire, atomics::memory_order_relaxed)) { + if (slot.ptr()) { + gc::template retire_ptr(slot.ptr()); + --m_ItemCounter; + m_Stat.onEraseSuccess(); + } + break; + } + } + } + } + } + + bool expand_slot(array_node * pParent, size_t idxParent, node_ptr current, size_t nOffset) + { + assert(current.bits() == 0); + assert(current.ptr()); + + size_t idx = hash_splitter(hash_accessor()(*current.ptr()), nOffset).cut(m_Metrics.array_node_size_log); + array_node * pArr = alloc_array_node(pParent, idxParent); + + 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)) + { + m_Stat.onExpandNodeFailed(); + free_array_node(pArr); + return false; + } + + pArr->nodes[idx].store(current, memory_model::memory_order_release); + + cur = cur | flag_array_converting; + 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; + } + + union converter { + value_type * pData; + array_node * pArr; + + converter(value_type * p) + : pData(p) + {} + + converter(array_node * p) + : pArr(p) + {} + }; + + static array_node * to_array(value_type * p) + { + return converter(p).pArr; + } + static value_type * to_node(array_node * p) + { + return converter(p).pData; + } + //@endcond + }; + +}} // namespace cds::intrusive + +#endif // #ifndef CDSLIB_INTRUSIVE_MULTILEVEL_HASHSET_RCU_H diff --git a/projects/Win/vc12/cds.vcxproj b/projects/Win/vc12/cds.vcxproj index 503c4965..d4769161 100644 --- a/projects/Win/vc12/cds.vcxproj +++ b/projects/Win/vc12/cds.vcxproj @@ -781,6 +781,7 @@ + diff --git a/projects/Win/vc12/cds.vcxproj.filters b/projects/Win/vc12/cds.vcxproj.filters index 473a2fa6..c228d180 100644 --- a/projects/Win/vc12/cds.vcxproj.filters +++ b/projects/Win/vc12/cds.vcxproj.filters @@ -1217,5 +1217,8 @@ Header Files\cds\container + + Header Files\cds\intrusive + \ No newline at end of file diff --git a/projects/Win/vc12/hdr-test-set.vcxproj b/projects/Win/vc12/hdr-test-set.vcxproj index f45220ee..3d30e7a3 100644 --- a/projects/Win/vc12/hdr-test-set.vcxproj +++ b/projects/Win/vc12/hdr-test-set.vcxproj @@ -569,6 +569,11 @@ + + + + + diff --git a/projects/Win/vc12/hdr-test-set.vcxproj.filters b/projects/Win/vc12/hdr-test-set.vcxproj.filters index 7e76f8fe..f9c2520e 100644 --- a/projects/Win/vc12/hdr-test-set.vcxproj.filters +++ b/projects/Win/vc12/hdr-test-set.vcxproj.filters @@ -335,5 +335,20 @@ container\multilevel_hashset + + intrusive\multilevel_hashset + + + intrusive\multilevel_hashset + + + intrusive\multilevel_hashset + + + intrusive\multilevel_hashset + + + intrusive\multilevel_hashset + \ No newline at end of file diff --git a/projects/Win/vc14/cds.vcxproj b/projects/Win/vc14/cds.vcxproj index 20df773f..7be0c3f3 100644 --- a/projects/Win/vc14/cds.vcxproj +++ b/projects/Win/vc14/cds.vcxproj @@ -886,6 +886,7 @@ + diff --git a/projects/Win/vc14/cds.vcxproj.filters b/projects/Win/vc14/cds.vcxproj.filters index 473a2fa6..c228d180 100644 --- a/projects/Win/vc14/cds.vcxproj.filters +++ b/projects/Win/vc14/cds.vcxproj.filters @@ -1217,5 +1217,8 @@ Header Files\cds\container + + Header Files\cds\intrusive + \ No newline at end of file diff --git a/projects/Win/vc14/hdr-test-set.vcxproj b/projects/Win/vc14/hdr-test-set.vcxproj index 22cf55c4..a18d6719 100644 --- a/projects/Win/vc14/hdr-test-set.vcxproj +++ b/projects/Win/vc14/hdr-test-set.vcxproj @@ -668,6 +668,11 @@ + + + + + diff --git a/projects/Win/vc14/hdr-test-set.vcxproj.filters b/projects/Win/vc14/hdr-test-set.vcxproj.filters index 7e76f8fe..08d97627 100644 --- a/projects/Win/vc14/hdr-test-set.vcxproj.filters +++ b/projects/Win/vc14/hdr-test-set.vcxproj.filters @@ -335,5 +335,20 @@ container\multilevel_hashset + + intrusive\multilevel_hashset + + + intrusive\multilevel_hashset + + + intrusive\multilevel_hashset + + + intrusive\multilevel_hashset + + + intrusive\multilevel_hashset + \ No newline at end of file diff --git a/projects/source.test-hdr.mk b/projects/source.test-hdr.mk index de597449..3517c56f 100644 --- a/projects/source.test-hdr.mk +++ b/projects/source.test-hdr.mk @@ -133,6 +133,11 @@ CDS_TESTHDR_QUEUE := \ CDS_TESTHDR_SET := \ tests/test-hdr/set/hdr_intrusive_multilevel_hashset_hp.cpp \ tests/test-hdr/set/hdr_intrusive_multilevel_hashset_dhp.cpp \ + tests/test-hdr/set/hdr_intrusive_multilevel_hashset_rcu_gpi.cpp \ + tests/test-hdr/set/hdr_intrusive_multilevel_hashset_rcu_gpb.cpp \ + tests/test-hdr/set/hdr_intrusive_multilevel_hashset_rcu_gpt.cpp \ + tests/test-hdr/set/hdr_intrusive_multilevel_hashset_rcu_shb.cpp \ + tests/test-hdr/set/hdr_intrusive_multilevel_hashset_rcu_sht.cpp \ tests/test-hdr/set/hdr_intrusive_refinable_hashset_avlset.cpp \ tests/test-hdr/set/hdr_intrusive_refinable_hashset_list.cpp \ tests/test-hdr/set/hdr_intrusive_refinable_hashset_set.cpp \ diff --git a/tests/test-hdr/CMakeLists.txt b/tests/test-hdr/CMakeLists.txt index e8508ccc..55590de9 100644 --- a/tests/test-hdr/CMakeLists.txt +++ b/tests/test-hdr/CMakeLists.txt @@ -135,6 +135,11 @@ set(CDS_TESTHDR_QUEUE set(CDS_TESTHDR_SET set/hdr_intrusive_multilevel_hashset_hp.cpp set/hdr_intrusive_multilevel_hashset_dhp.cpp + set/hdr_intrusive_multilevel_hashset_rcu_gpi.cpp + set/hdr_intrusive_multilevel_hashset_rcu_gpb.cpp + set/hdr_intrusive_multilevel_hashset_rcu_gpt.cpp + set/hdr_intrusive_multilevel_hashset_rcu_shb.cpp + set/hdr_intrusive_multilevel_hashset_rcu_sht.cpp set/hdr_intrusive_refinable_hashset_avlset.cpp set/hdr_intrusive_refinable_hashset_list.cpp set/hdr_intrusive_refinable_hashset_set.cpp diff --git a/tests/test-hdr/set/hdr_intrusive_multilevel_hashset.h b/tests/test-hdr/set/hdr_intrusive_multilevel_hashset.h index d9622334..1c295ddb 100644 --- a/tests/test-hdr/set/hdr_intrusive_multilevel_hashset.h +++ b/tests/test-hdr/set/hdr_intrusive_multilevel_hashset.h @@ -346,6 +346,241 @@ namespace set { CPPUNIT_MSG( s.statistics() ); } + template + void test_rcu(size_t nHeadBits, size_t nArrayBits) + { + typedef typename Set::hash_type hash_type; + typedef typename Set::value_type value_type; + typedef typename Set::rcu_lock rcu_lock; + + Hash hasher; + + size_t const arrCapacity = 1000; + std::vector< value_type > arrValue; + arrValue.reserve(arrCapacity); + for (size_t i = 0; i < arrCapacity; ++i) { + arrValue.emplace_back(value_type()); + arrValue.back().hash = hasher(i); + } + CPPUNIT_ASSERT(arrValue.size() == arrCapacity); + + Set s(nHeadBits, nArrayBits); + CPPUNIT_MSG("Array size: head=" << s.head_size() << ", array_node=" << s.array_node_size()); + CPPUNIT_ASSERT(s.head_size() >= (size_t(1) << nHeadBits)); + CPPUNIT_ASSERT(s.array_node_size() == (size_t(1) << nArrayBits)); + + // insert() test + CPPUNIT_ASSERT(s.size() == 0); + CPPUNIT_ASSERT(s.empty()); + for (auto& el : arrValue) { + CPPUNIT_ASSERT(s.insert(el)); + CPPUNIT_ASSERT(s.contains(el.hash)); + } + CPPUNIT_ASSERT(s.size() == arrCapacity); + for (auto& el : arrValue) { + CPPUNIT_ASSERT(s.contains(el.hash)); + CPPUNIT_ASSERT(!s.insert(el)); + } + CPPUNIT_ASSERT(s.size() == arrCapacity); + CPPUNIT_ASSERT(!s.empty()); + + // Iterator test + { + rcu_lock l; + + typedef typename Set::iterator iterator; + for (iterator it = s.begin(), itEnd = s.end(); it != itEnd; ++it) + ++(it->nIteratorCall); + for (auto& el : arrValue) { + CPPUNIT_ASSERT(el.nIteratorCall == 1); + el.nIteratorCall = 0; + } + } + + { + // Const iterator test + rcu_lock l; + + for (typename Set::const_iterator it = s.cbegin(), itEnd = s.cend(); it != itEnd; ++it) + (*it).nIteratorCall += 1; + for (auto& el : arrValue) { + CPPUNIT_ASSERT(el.nIteratorCall == 1); + el.nIteratorCall = 0; + } + } + + { + // Reverse iterator test + rcu_lock l; + + for (typename Set::reverse_iterator it = s.rbegin(), itEnd = s.rend(); it != itEnd; ++it) + it->nIteratorCall += 1; + for (auto& el : arrValue) { + CPPUNIT_ASSERT(el.nIteratorCall == 1); + el.nIteratorCall = 0; + } + } + + { + // Reverse const iterator test + rcu_lock l; + + for (typename Set::const_reverse_iterator it = s.crbegin(), itEnd = s.crend(); it != itEnd; ++it) { + (*it).nIteratorCall += 1; + } + for (auto& el : arrValue) { + CPPUNIT_ASSERT(el.nIteratorCall == 1); + el.nIteratorCall = 0; + } + } + + // update() exists test + for (auto& el : arrValue) { + bool bOp, bInsert; + std::tie(bOp, bInsert) = s.update(el, false); + CPPUNIT_ASSERT(bOp); + CPPUNIT_ASSERT(!bInsert); + CPPUNIT_ASSERT(el.nFindCall == 0); + CPPUNIT_ASSERT(s.find(el.hash, [](value_type& v) { v.nFindCall++; })); + CPPUNIT_ASSERT(el.nFindCall == 1); + } + + // unlink test + CPPUNIT_ASSERT(s.size() == arrCapacity); + for (auto const& el : arrValue) { + CPPUNIT_ASSERT(s.unlink(el)); + CPPUNIT_ASSERT(!s.contains(el.hash)); + } + CPPUNIT_ASSERT(s.size() == 0); + Set::gc::force_dispose(); + for (auto const& el : arrValue) { + CPPUNIT_ASSERT(el.nDisposeCount == 1); + } + + // new hash values + for (auto& el : arrValue) + el.hash = hasher(el.hash); + + // insert( func ) + CPPUNIT_ASSERT(s.size() == 0); + for (auto& el : arrValue) { + CPPUNIT_ASSERT(s.insert(el, [](value_type& v) { ++v.nInsertCall; })); + CPPUNIT_ASSERT(s.contains(el.hash)); + CPPUNIT_ASSERT(el.nInsertCall == 1); + } + CPPUNIT_ASSERT(s.size() == arrCapacity); + for (auto& el : arrValue) { + CPPUNIT_ASSERT(s.contains(el.hash)); + CPPUNIT_ASSERT(!s.insert(el)); + } + CPPUNIT_ASSERT(s.size() == arrCapacity); + CPPUNIT_ASSERT(!s.empty()); + + for (auto& el : arrValue) + el.nDisposeCount = 0; + + s.clear(); + CPPUNIT_ASSERT(s.size() == 0); + Set::gc::force_dispose(); + for (auto const& el : arrValue) { + CPPUNIT_ASSERT(el.nDisposeCount == 1); + } + + // new hash values + for (auto& el : arrValue) + el.hash = hasher(el.hash); + + // update test + for (auto& el : arrValue) { + bool bOp, bInsert; + std::tie(bOp, bInsert) = s.update(el, false); + CPPUNIT_ASSERT(!bOp); + CPPUNIT_ASSERT(!bInsert); + CPPUNIT_ASSERT(!s.contains(el.hash)); + + std::tie(bOp, bInsert) = s.update(el, true); + CPPUNIT_ASSERT(bOp); + CPPUNIT_ASSERT(bInsert); + CPPUNIT_ASSERT(s.contains(el.hash)); + } + CPPUNIT_ASSERT(s.size() == arrCapacity); + + // erase test + for (auto& el : arrValue) { + el.nDisposeCount = 0; + CPPUNIT_ASSERT(s.contains(el.hash)); + CPPUNIT_ASSERT(s.erase(el.hash)); + CPPUNIT_ASSERT(!s.contains(el.hash)); + CPPUNIT_ASSERT(!s.erase(el.hash)); + } + CPPUNIT_ASSERT(s.size() == 0); + Set::gc::force_dispose(); + for (auto& el : arrValue) { + CPPUNIT_ASSERT(el.nDisposeCount == 1); + CPPUNIT_ASSERT(s.insert(el)); + } + + // erase with functor, get() test + for (auto& el : arrValue) { + el.nDisposeCount = 0; + CPPUNIT_ASSERT(s.contains(el.hash)); + value_type * p; + { + rcu_lock l; + p = s.get(el.hash); + CPPUNIT_ASSERT(p); + CPPUNIT_ASSERT(p->nEraseCall == 0); + } + // This is single-threaded test with faked disposer + // so we can dereference p outside RCU lock section + CPPUNIT_ASSERT(s.erase(p->hash, [](value_type& i) { ++i.nEraseCall; })); + CPPUNIT_ASSERT(p->nEraseCall == 1); + Set::gc::force_dispose(); + CPPUNIT_ASSERT(p->nDisposeCount == 1); + + CPPUNIT_ASSERT(!s.contains(el.hash)); + CPPUNIT_ASSERT(!s.erase(el.hash)); + CPPUNIT_ASSERT(el.nEraseCall == 1); + Set::gc::force_dispose(); + CPPUNIT_ASSERT(el.nDisposeCount == 1); + } + CPPUNIT_ASSERT(s.size() == 0); + + // new hash values + for (auto& el : arrValue) { + el.hash = hasher(el.hash); + el.nDisposeCount = 0; + bool bOp, bInsert; + std::tie(bOp, bInsert) = s.update(el); + CPPUNIT_ASSERT(bOp); + CPPUNIT_ASSERT(bInsert); + } + CPPUNIT_ASSERT(s.size() == arrCapacity); + + // extract test + for (auto& el : arrValue) { + CPPUNIT_ASSERT(s.contains(el.hash)); + typename Set::exempt_ptr xp = s.extract(el.hash); + CPPUNIT_ASSERT(xp); + Set::gc::force_dispose(); + CPPUNIT_ASSERT(el.nDisposeCount == 0); + CPPUNIT_ASSERT(xp->nDisposeCount == 0); + xp.release(); + { + rcu_lock l; + value_type * p = s.get(el.hash); + CPPUNIT_ASSERT(!p); + } + Set::gc::force_dispose(); + CPPUNIT_ASSERT(el.nDisposeCount == 1); + CPPUNIT_ASSERT(!s.contains(el.hash)); + } + CPPUNIT_ASSERT(s.size() == 0); + CPPUNIT_ASSERT(s.empty()); + + CPPUNIT_MSG(s.statistics()); + } + void hp_stdhash(); void hp_stdhash_stat(); void hp_stdhash_5_3(); @@ -364,6 +599,51 @@ namespace set { void dhp_hash128_4_3(); void dhp_hash128_4_3_stat(); + void rcu_gpi_stdhash(); + void rcu_gpi_stdhash_stat(); + void rcu_gpi_stdhash_5_3(); + void rcu_gpi_stdhash_5_3_stat(); + void rcu_gpi_hash128(); + void rcu_gpi_hash128_stat(); + void rcu_gpi_hash128_4_3(); + void rcu_gpi_hash128_4_3_stat(); + + void rcu_gpb_stdhash(); + void rcu_gpb_stdhash_stat(); + void rcu_gpb_stdhash_5_3(); + void rcu_gpb_stdhash_5_3_stat(); + void rcu_gpb_hash128(); + void rcu_gpb_hash128_stat(); + void rcu_gpb_hash128_4_3(); + void rcu_gpb_hash128_4_3_stat(); + + void rcu_gpt_stdhash(); + void rcu_gpt_stdhash_stat(); + void rcu_gpt_stdhash_5_3(); + void rcu_gpt_stdhash_5_3_stat(); + void rcu_gpt_hash128(); + void rcu_gpt_hash128_stat(); + void rcu_gpt_hash128_4_3(); + void rcu_gpt_hash128_4_3_stat(); + + void rcu_shb_stdhash(); + void rcu_shb_stdhash_stat(); + void rcu_shb_stdhash_5_3(); + void rcu_shb_stdhash_5_3_stat(); + void rcu_shb_hash128(); + void rcu_shb_hash128_stat(); + void rcu_shb_hash128_4_3(); + void rcu_shb_hash128_4_3_stat(); + + void rcu_sht_stdhash(); + void rcu_sht_stdhash_stat(); + void rcu_sht_stdhash_5_3(); + void rcu_sht_stdhash_5_3_stat(); + void rcu_sht_hash128(); + void rcu_sht_hash128_stat(); + void rcu_sht_hash128_4_3(); + void rcu_sht_hash128_4_3_stat(); + CPPUNIT_TEST_SUITE(IntrusiveMultiLevelHashSetHdrTest) CPPUNIT_TEST(hp_stdhash) CPPUNIT_TEST(hp_stdhash_stat) @@ -382,7 +662,54 @@ namespace set { CPPUNIT_TEST(dhp_hash128_stat) CPPUNIT_TEST(dhp_hash128_4_3) CPPUNIT_TEST(dhp_hash128_4_3_stat) + + CPPUNIT_TEST(rcu_gpi_stdhash) + CPPUNIT_TEST(rcu_gpi_stdhash_stat) + CPPUNIT_TEST(rcu_gpi_stdhash_5_3) + CPPUNIT_TEST(rcu_gpi_stdhash_5_3_stat) + CPPUNIT_TEST(rcu_gpi_hash128) + CPPUNIT_TEST(rcu_gpi_hash128_stat) + CPPUNIT_TEST(rcu_gpi_hash128_4_3) + CPPUNIT_TEST(rcu_gpi_hash128_4_3_stat) + + CPPUNIT_TEST(rcu_gpb_stdhash) + CPPUNIT_TEST(rcu_gpb_stdhash_stat) + CPPUNIT_TEST(rcu_gpb_stdhash_5_3) + CPPUNIT_TEST(rcu_gpb_stdhash_5_3_stat) + CPPUNIT_TEST(rcu_gpb_hash128) + CPPUNIT_TEST(rcu_gpb_hash128_stat) + CPPUNIT_TEST(rcu_gpb_hash128_4_3) + CPPUNIT_TEST(rcu_gpb_hash128_4_3_stat) + + CPPUNIT_TEST(rcu_gpt_stdhash) + CPPUNIT_TEST(rcu_gpt_stdhash_stat) + CPPUNIT_TEST(rcu_gpt_stdhash_5_3) + CPPUNIT_TEST(rcu_gpt_stdhash_5_3_stat) + CPPUNIT_TEST(rcu_gpt_hash128) + CPPUNIT_TEST(rcu_gpt_hash128_stat) + CPPUNIT_TEST(rcu_gpt_hash128_4_3) + CPPUNIT_TEST(rcu_gpt_hash128_4_3_stat) + + CPPUNIT_TEST(rcu_shb_stdhash) + CPPUNIT_TEST(rcu_shb_stdhash_stat) + CPPUNIT_TEST(rcu_shb_stdhash_5_3) + CPPUNIT_TEST(rcu_shb_stdhash_5_3_stat) + CPPUNIT_TEST(rcu_shb_hash128) + CPPUNIT_TEST(rcu_shb_hash128_stat) + CPPUNIT_TEST(rcu_shb_hash128_4_3) + CPPUNIT_TEST(rcu_shb_hash128_4_3_stat) + + CPPUNIT_TEST(rcu_sht_stdhash) + CPPUNIT_TEST(rcu_sht_stdhash_stat) + CPPUNIT_TEST(rcu_sht_stdhash_5_3) + CPPUNIT_TEST(rcu_sht_stdhash_5_3_stat) + CPPUNIT_TEST(rcu_sht_hash128) + CPPUNIT_TEST(rcu_sht_hash128_stat) + CPPUNIT_TEST(rcu_sht_hash128_4_3) + CPPUNIT_TEST(rcu_sht_hash128_4_3_stat) + CPPUNIT_TEST_SUITE_END() + }; } // namespace set diff --git a/tests/test-hdr/set/hdr_intrusive_multilevel_hashset_rcu_gpb.cpp b/tests/test-hdr/set/hdr_intrusive_multilevel_hashset_rcu_gpb.cpp new file mode 100644 index 00000000..ecf1640f --- /dev/null +++ b/tests/test-hdr/set/hdr_intrusive_multilevel_hashset_rcu_gpb.cpp @@ -0,0 +1,223 @@ +//$$CDS-header$$ + +#include "set/hdr_intrusive_multilevel_hashset.h" +#include +#include +#include "unit/print_multilevel_hashset_stat.h" + +namespace set { + namespace { + typedef cds::urcu::gc> rcu_type; + } // namespace + + void IntrusiveMultiLevelHashSetHdrTest::rcu_gpb_stdhash() + { + typedef size_t hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, size_t>::value, "set::hash_type != size_t!!!" ); + test_rcu>(4, 2); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + >::type + > set_type2; + test_rcu>(4, 2); + } + + void IntrusiveMultiLevelHashSetHdrTest::rcu_gpb_hash128() + { + typedef hash128 hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + typedef hash128::less less; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, hash_type>::value, "set::hash_type != hash128!!!" ); + test_rcu(4, 2); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + , ci::opt::less< hash_type::less > + >::type + > set_type2; + test_rcu(4, 2); + } + + void IntrusiveMultiLevelHashSetHdrTest::rcu_gpb_stdhash_stat() + { + typedef size_t hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + typedef ci::multilevel_hashset::stat<> stat; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, size_t>::value, "set::hash_type != size_t!!!" ); + test_rcu>(4, 2); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + ,co::stat< ci::multilevel_hashset::stat<>> + >::type + > set_type2; + test_rcu>(4, 2); + } + + void IntrusiveMultiLevelHashSetHdrTest::rcu_gpb_hash128_stat() + { + typedef hash128 hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + typedef hash128::cmp compare; + typedef ci::multilevel_hashset::stat<> stat; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, hash_type>::value, "set::hash_type != hash_type!!!" ); + test_rcu(4, 2); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + ,co::stat< ci::multilevel_hashset::stat<>> + ,co::compare< hash128::cmp > + >::type + > set_type2; + test_rcu(4, 2); + } + + void IntrusiveMultiLevelHashSetHdrTest::rcu_gpb_stdhash_5_3() + { + typedef size_t hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, size_t>::value, "set::hash_type != size_t!!!" ); + test_rcu>(5, 3); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + >::type + > set_type2; + test_rcu>(5, 3); + } + + void IntrusiveMultiLevelHashSetHdrTest::rcu_gpb_hash128_4_3() + { + typedef hash128 hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + typedef co::v::sequential_consistent memory_model; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, hash_type>::value, "set::hash_type != hash_type!!!" ); + test_rcu(4, 3); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + ,co::memory_model< co::v::sequential_consistent > + >::type + > set_type2; + test_rcu(4, 3); + } + + void IntrusiveMultiLevelHashSetHdrTest::rcu_gpb_stdhash_5_3_stat() + { + typedef size_t hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + typedef ci::multilevel_hashset::stat<> stat; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, size_t>::value, "set::hash_type != size_t!!!" ); + test_rcu>(5, 3); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + ,co::stat< ci::multilevel_hashset::stat<>> + >::type + > set_type2; + test_rcu>(5, 3); + } + + void IntrusiveMultiLevelHashSetHdrTest::rcu_gpb_hash128_4_3_stat() + { + typedef hash128 hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + typedef ci::multilevel_hashset::stat<> stat; + typedef hash128::less less; + typedef hash128::cmp compare; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, hash_type>::value, "set::hash_type != hash_type!!!" ); + test_rcu(4, 3); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + , co::stat< ci::multilevel_hashset::stat<>> + , co::less< hash_type::less > + , co::compare< hash128::cmp > + >::type + > set_type2; + test_rcu(4, 3); + } + +} // namespace set diff --git a/tests/test-hdr/set/hdr_intrusive_multilevel_hashset_rcu_gpi.cpp b/tests/test-hdr/set/hdr_intrusive_multilevel_hashset_rcu_gpi.cpp new file mode 100644 index 00000000..03df7148 --- /dev/null +++ b/tests/test-hdr/set/hdr_intrusive_multilevel_hashset_rcu_gpi.cpp @@ -0,0 +1,223 @@ +//$$CDS-header$$ + +#include "set/hdr_intrusive_multilevel_hashset.h" +#include +#include +#include "unit/print_multilevel_hashset_stat.h" + +namespace set { + namespace { + typedef cds::urcu::gc> rcu_type; + } // namespace + + void IntrusiveMultiLevelHashSetHdrTest::rcu_gpi_stdhash() + { + typedef size_t hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, size_t>::value, "set::hash_type != size_t!!!" ); + test_rcu>(4, 2); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + >::type + > set_type2; + test_rcu>(4, 2); + } + + void IntrusiveMultiLevelHashSetHdrTest::rcu_gpi_hash128() + { + typedef hash128 hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + typedef hash128::less less; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, hash_type>::value, "set::hash_type != hash128!!!" ); + test_rcu(4, 2); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + , ci::opt::less< hash_type::less > + >::type + > set_type2; + test_rcu(4, 2); + } + + void IntrusiveMultiLevelHashSetHdrTest::rcu_gpi_stdhash_stat() + { + typedef size_t hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + typedef ci::multilevel_hashset::stat<> stat; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, size_t>::value, "set::hash_type != size_t!!!" ); + test_rcu>(4, 2); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + ,co::stat< ci::multilevel_hashset::stat<>> + >::type + > set_type2; + test_rcu>(4, 2); + } + + void IntrusiveMultiLevelHashSetHdrTest::rcu_gpi_hash128_stat() + { + typedef hash128 hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + typedef hash128::cmp compare; + typedef ci::multilevel_hashset::stat<> stat; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, hash_type>::value, "set::hash_type != hash_type!!!" ); + test_rcu(4, 2); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + ,co::stat< ci::multilevel_hashset::stat<>> + ,co::compare< hash128::cmp > + >::type + > set_type2; + test_rcu(4, 2); + } + + void IntrusiveMultiLevelHashSetHdrTest::rcu_gpi_stdhash_5_3() + { + typedef size_t hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, size_t>::value, "set::hash_type != size_t!!!" ); + test_rcu>(5, 3); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + >::type + > set_type2; + test_rcu>(5, 3); + } + + void IntrusiveMultiLevelHashSetHdrTest::rcu_gpi_hash128_4_3() + { + typedef hash128 hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + typedef co::v::sequential_consistent memory_model; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, hash_type>::value, "set::hash_type != hash_type!!!" ); + test_rcu(4, 3); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + ,co::memory_model< co::v::sequential_consistent > + >::type + > set_type2; + test_rcu(4, 3); + } + + void IntrusiveMultiLevelHashSetHdrTest::rcu_gpi_stdhash_5_3_stat() + { + typedef size_t hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + typedef ci::multilevel_hashset::stat<> stat; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, size_t>::value, "set::hash_type != size_t!!!" ); + test_rcu>(5, 3); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + ,co::stat< ci::multilevel_hashset::stat<>> + >::type + > set_type2; + test_rcu>(5, 3); + } + + void IntrusiveMultiLevelHashSetHdrTest::rcu_gpi_hash128_4_3_stat() + { + typedef hash128 hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + typedef ci::multilevel_hashset::stat<> stat; + typedef hash128::less less; + typedef hash128::cmp compare; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, hash_type>::value, "set::hash_type != hash_type!!!" ); + test_rcu(4, 3); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + , co::stat< ci::multilevel_hashset::stat<>> + , co::less< hash_type::less > + , co::compare< hash128::cmp > + >::type + > set_type2; + test_rcu(4, 3); + } + +} // namespace set diff --git a/tests/test-hdr/set/hdr_intrusive_multilevel_hashset_rcu_gpt.cpp b/tests/test-hdr/set/hdr_intrusive_multilevel_hashset_rcu_gpt.cpp new file mode 100644 index 00000000..2f50bf57 --- /dev/null +++ b/tests/test-hdr/set/hdr_intrusive_multilevel_hashset_rcu_gpt.cpp @@ -0,0 +1,223 @@ +//$$CDS-header$$ + +#include "set/hdr_intrusive_multilevel_hashset.h" +#include +#include +#include "unit/print_multilevel_hashset_stat.h" + +namespace set { + namespace { + typedef cds::urcu::gc> rcu_type; + } // namespace + + void IntrusiveMultiLevelHashSetHdrTest::rcu_gpt_stdhash() + { + typedef size_t hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, size_t>::value, "set::hash_type != size_t!!!" ); + test_rcu>(4, 2); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + >::type + > set_type2; + test_rcu>(4, 2); + } + + void IntrusiveMultiLevelHashSetHdrTest::rcu_gpt_hash128() + { + typedef hash128 hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + typedef hash128::less less; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, hash_type>::value, "set::hash_type != hash128!!!" ); + test_rcu(4, 2); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + , ci::opt::less< hash_type::less > + >::type + > set_type2; + test_rcu(4, 2); + } + + void IntrusiveMultiLevelHashSetHdrTest::rcu_gpt_stdhash_stat() + { + typedef size_t hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + typedef ci::multilevel_hashset::stat<> stat; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, size_t>::value, "set::hash_type != size_t!!!" ); + test_rcu>(4, 2); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + ,co::stat< ci::multilevel_hashset::stat<>> + >::type + > set_type2; + test_rcu>(4, 2); + } + + void IntrusiveMultiLevelHashSetHdrTest::rcu_gpt_hash128_stat() + { + typedef hash128 hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + typedef hash128::cmp compare; + typedef ci::multilevel_hashset::stat<> stat; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, hash_type>::value, "set::hash_type != hash_type!!!" ); + test_rcu(4, 2); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + ,co::stat< ci::multilevel_hashset::stat<>> + ,co::compare< hash128::cmp > + >::type + > set_type2; + test_rcu(4, 2); + } + + void IntrusiveMultiLevelHashSetHdrTest::rcu_gpt_stdhash_5_3() + { + typedef size_t hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, size_t>::value, "set::hash_type != size_t!!!" ); + test_rcu>(5, 3); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + >::type + > set_type2; + test_rcu>(5, 3); + } + + void IntrusiveMultiLevelHashSetHdrTest::rcu_gpt_hash128_4_3() + { + typedef hash128 hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + typedef co::v::sequential_consistent memory_model; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, hash_type>::value, "set::hash_type != hash_type!!!" ); + test_rcu(4, 3); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + ,co::memory_model< co::v::sequential_consistent > + >::type + > set_type2; + test_rcu(4, 3); + } + + void IntrusiveMultiLevelHashSetHdrTest::rcu_gpt_stdhash_5_3_stat() + { + typedef size_t hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + typedef ci::multilevel_hashset::stat<> stat; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, size_t>::value, "set::hash_type != size_t!!!" ); + test_rcu>(5, 3); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + ,co::stat< ci::multilevel_hashset::stat<>> + >::type + > set_type2; + test_rcu>(5, 3); + } + + void IntrusiveMultiLevelHashSetHdrTest::rcu_gpt_hash128_4_3_stat() + { + typedef hash128 hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + typedef ci::multilevel_hashset::stat<> stat; + typedef hash128::less less; + typedef hash128::cmp compare; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, hash_type>::value, "set::hash_type != hash_type!!!" ); + test_rcu(4, 3); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + , co::stat< ci::multilevel_hashset::stat<>> + , co::less< hash_type::less > + , co::compare< hash128::cmp > + >::type + > set_type2; + test_rcu(4, 3); + } + +} // namespace set diff --git a/tests/test-hdr/set/hdr_intrusive_multilevel_hashset_rcu_shb.cpp b/tests/test-hdr/set/hdr_intrusive_multilevel_hashset_rcu_shb.cpp new file mode 100644 index 00000000..20cb604f --- /dev/null +++ b/tests/test-hdr/set/hdr_intrusive_multilevel_hashset_rcu_shb.cpp @@ -0,0 +1,242 @@ +//$$CDS-header$$ + +#include "set/hdr_intrusive_multilevel_hashset.h" +#include +#include +#include "unit/print_multilevel_hashset_stat.h" + +namespace set { + +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + namespace { + typedef cds::urcu::gc> rcu_type; + } // namespace +#endif + + void IntrusiveMultiLevelHashSetHdrTest::rcu_shb_stdhash() + { +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + typedef size_t hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, size_t>::value, "set::hash_type != size_t!!!" ); + test_rcu>(4, 2); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + >::type + > set_type2; + test_rcu>(4, 2); +#endif + } + + void IntrusiveMultiLevelHashSetHdrTest::rcu_shb_hash128() + { +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + typedef hash128 hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + typedef hash128::less less; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, hash_type>::value, "set::hash_type != hash128!!!" ); + test_rcu(4, 2); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + , ci::opt::less< hash_type::less > + >::type + > set_type2; + test_rcu(4, 2); +#endif + } + + void IntrusiveMultiLevelHashSetHdrTest::rcu_shb_stdhash_stat() + { +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + typedef size_t hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + typedef ci::multilevel_hashset::stat<> stat; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, size_t>::value, "set::hash_type != size_t!!!" ); + test_rcu>(4, 2); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + ,co::stat< ci::multilevel_hashset::stat<>> + >::type + > set_type2; + test_rcu>(4, 2); +#endif + } + + void IntrusiveMultiLevelHashSetHdrTest::rcu_shb_hash128_stat() + { +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + typedef hash128 hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + typedef hash128::cmp compare; + typedef ci::multilevel_hashset::stat<> stat; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, hash_type>::value, "set::hash_type != hash_type!!!" ); + test_rcu(4, 2); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + ,co::stat< ci::multilevel_hashset::stat<>> + ,co::compare< hash128::cmp > + >::type + > set_type2; + test_rcu(4, 2); +#endif + } + + void IntrusiveMultiLevelHashSetHdrTest::rcu_shb_stdhash_5_3() + { +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + typedef size_t hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, size_t>::value, "set::hash_type != size_t!!!" ); + test_rcu>(5, 3); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + >::type + > set_type2; + test_rcu>(5, 3); +#endif + } + + void IntrusiveMultiLevelHashSetHdrTest::rcu_shb_hash128_4_3() + { +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + typedef hash128 hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + typedef co::v::sequential_consistent memory_model; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, hash_type>::value, "set::hash_type != hash_type!!!" ); + test_rcu(4, 3); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + ,co::memory_model< co::v::sequential_consistent > + >::type + > set_type2; + test_rcu(4, 3); +#endif + } + + void IntrusiveMultiLevelHashSetHdrTest::rcu_shb_stdhash_5_3_stat() + { +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + typedef size_t hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + typedef ci::multilevel_hashset::stat<> stat; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, size_t>::value, "set::hash_type != size_t!!!" ); + test_rcu>(5, 3); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + ,co::stat< ci::multilevel_hashset::stat<>> + >::type + > set_type2; + test_rcu>(5, 3); +#endif + } + + void IntrusiveMultiLevelHashSetHdrTest::rcu_shb_hash128_4_3_stat() + { +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + typedef hash128 hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + typedef ci::multilevel_hashset::stat<> stat; + typedef hash128::less less; + typedef hash128::cmp compare; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, hash_type>::value, "set::hash_type != hash_type!!!" ); + test_rcu(4, 3); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + , co::stat< ci::multilevel_hashset::stat<>> + , co::less< hash_type::less > + , co::compare< hash128::cmp > + >::type + > set_type2; + test_rcu(4, 3); +#endif + } + +} // namespace set diff --git a/tests/test-hdr/set/hdr_intrusive_multilevel_hashset_rcu_sht.cpp b/tests/test-hdr/set/hdr_intrusive_multilevel_hashset_rcu_sht.cpp new file mode 100644 index 00000000..b662d2c9 --- /dev/null +++ b/tests/test-hdr/set/hdr_intrusive_multilevel_hashset_rcu_sht.cpp @@ -0,0 +1,242 @@ +//$$CDS-header$$ + +#include "set/hdr_intrusive_multilevel_hashset.h" +#include +#include +#include "unit/print_multilevel_hashset_stat.h" + +namespace set { + +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + namespace { + typedef cds::urcu::gc> rcu_type; + } // namespace +#endif + + void IntrusiveMultiLevelHashSetHdrTest::rcu_sht_stdhash() + { +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + typedef size_t hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, size_t>::value, "set::hash_type != size_t!!!" ); + test_rcu>(4, 2); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + >::type + > set_type2; + test_rcu>(4, 2); +#endif + } + + void IntrusiveMultiLevelHashSetHdrTest::rcu_sht_hash128() + { +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + typedef hash128 hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + typedef hash128::less less; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, hash_type>::value, "set::hash_type != hash128!!!" ); + test_rcu(4, 2); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + , ci::opt::less< hash_type::less > + >::type + > set_type2; + test_rcu(4, 2); +#endif + } + + void IntrusiveMultiLevelHashSetHdrTest::rcu_sht_stdhash_stat() + { +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + typedef size_t hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + typedef ci::multilevel_hashset::stat<> stat; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, size_t>::value, "set::hash_type != size_t!!!" ); + test_rcu>(4, 2); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + ,co::stat< ci::multilevel_hashset::stat<>> + >::type + > set_type2; + test_rcu>(4, 2); +#endif + } + + void IntrusiveMultiLevelHashSetHdrTest::rcu_sht_hash128_stat() + { +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + typedef hash128 hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + typedef hash128::cmp compare; + typedef ci::multilevel_hashset::stat<> stat; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, hash_type>::value, "set::hash_type != hash_type!!!" ); + test_rcu(4, 2); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + ,co::stat< ci::multilevel_hashset::stat<>> + ,co::compare< hash128::cmp > + >::type + > set_type2; + test_rcu(4, 2); +#endif + } + + void IntrusiveMultiLevelHashSetHdrTest::rcu_sht_stdhash_5_3() + { +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + typedef size_t hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, size_t>::value, "set::hash_type != size_t!!!" ); + test_rcu>(5, 3); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + >::type + > set_type2; + test_rcu>(5, 3); +#endif + } + + void IntrusiveMultiLevelHashSetHdrTest::rcu_sht_hash128_4_3() + { +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + typedef hash128 hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + typedef co::v::sequential_consistent memory_model; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, hash_type>::value, "set::hash_type != hash_type!!!" ); + test_rcu(4, 3); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + ,co::memory_model< co::v::sequential_consistent > + >::type + > set_type2; + test_rcu(4, 3); +#endif + } + + void IntrusiveMultiLevelHashSetHdrTest::rcu_sht_stdhash_5_3_stat() + { +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + typedef size_t hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + typedef ci::multilevel_hashset::stat<> stat; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, size_t>::value, "set::hash_type != size_t!!!" ); + test_rcu>(5, 3); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + ,co::stat< ci::multilevel_hashset::stat<>> + >::type + > set_type2; + test_rcu>(5, 3); +#endif + } + + void IntrusiveMultiLevelHashSetHdrTest::rcu_sht_hash128_4_3_stat() + { +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + typedef hash128 hash_type; + + struct traits: public ci::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef item_disposer disposer; + typedef ci::multilevel_hashset::stat<> stat; + typedef hash128::less less; + typedef hash128::cmp compare; + }; + typedef ci::MultiLevelHashSet< rcu_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, hash_type>::value, "set::hash_type != hash_type!!!" ); + test_rcu(4, 3); + + typedef ci::MultiLevelHashSet< + rcu_type, + Item, + typename ci::multilevel_hashset::make_traits< + ci::multilevel_hashset::hash_accessor< get_hash> + , ci::opt::disposer< item_disposer > + , co::stat< ci::multilevel_hashset::stat<>> + , co::less< hash_type::less > + , co::compare< hash128::cmp > + >::type + > set_type2; + test_rcu(4, 3); +#endif + } + +} // namespace set diff --git a/tests/unit/map2/map_insdelfind.h b/tests/unit/map2/map_insdelfind.h index 50bf2a18..e5c5caed 100644 --- a/tests/unit/map2/map_insdelfind.h +++ b/tests/unit/map2/map_insdelfind.h @@ -261,7 +261,7 @@ namespace map2 { CDSUNIT_DECLARE_CuckooMap CDSUNIT_DECLARE_StdMap - CPPUNIT_TEST_SUITE(Map_InsDel_int) + CPPUNIT_TEST_SUITE(Map_InsDelFind) CDSUNIT_TEST_MichaelMap CDSUNIT_TEST_SplitList CDSUNIT_TEST_SkipListMap diff --git a/tests/unit/print_multilevel_hashset_stat.h b/tests/unit/print_multilevel_hashset_stat.h index 2183328e..5fe06af3 100644 --- a/tests/unit/print_multilevel_hashset_stat.h +++ b/tests/unit/print_multilevel_hashset_stat.h @@ -28,7 +28,8 @@ namespace std { << "\t\t m_nExpandNodeFailed: " << s.m_nExpandNodeFailed.get() << "\n" << "\t\t m_nSlotChanged: " << s.m_nSlotChanged.get() << "\n" << "\t\t m_nSlotConverting: " << s.m_nSlotConverting.get() << "\n" - << "\t\t m_nArrayNodeCount: " << s.m_nArrayNodeCount.get() << "\n"; + << "\t\t m_nArrayNodeCount: " << s.m_nArrayNodeCount.get() << "\n" + << "\t\t m_nHeight: " << s.m_nHeight.get() << "\n"; } static inline ostream& operator <<( ostream& o, cds::intrusive::multilevel_hashset::empty_stat const& /*s*/ )