From bd0c53a9b88b0d75044b6ce83c3cee49bb992aeb Mon Sep 17 00:00:00 2001 From: khizmax Date: Sun, 4 Oct 2015 22:46:50 +0300 Subject: [PATCH] Added container::MultiLevelHashMap specialization --- cds/container/impl/multilevel_hashmap.h | 2 +- cds/container/multilevel_hashmap_rcu.h | 780 ++++++++++++++++++ cds/container/multilevel_hashset_rcu.h | 6 +- projects/Win/vc12/cds.vcxproj | 1 + projects/Win/vc12/cds.vcxproj.filters | 3 + projects/Win/vc12/hdr-test-map.vcxproj | 5 + .../Win/vc12/hdr-test-map.vcxproj.filters | 15 + projects/Win/vc14/cds.vcxproj | 1 + projects/Win/vc14/cds.vcxproj.filters | 3 + projects/Win/vc14/hdr-test-map.vcxproj | 5 + .../Win/vc14/hdr-test-map.vcxproj.filters | 15 + projects/source.test-hdr.mk | 5 + tests/test-hdr/CMakeLists.txt | 5 + tests/test-hdr/map/hdr_multilevel_hashmap.h | 339 ++++++++ .../map/hdr_multilevel_hashmap_rcu_gpb.cpp | 139 ++++ .../map/hdr_multilevel_hashmap_rcu_gpi.cpp | 139 ++++ .../map/hdr_multilevel_hashmap_rcu_gpt.cpp | 139 ++++ .../map/hdr_multilevel_hashmap_rcu_shb.cpp | 157 ++++ .../map/hdr_multilevel_hashmap_rcu_sht.cpp | 157 ++++ 19 files changed, 1914 insertions(+), 2 deletions(-) create mode 100644 cds/container/multilevel_hashmap_rcu.h create mode 100644 tests/test-hdr/map/hdr_multilevel_hashmap_rcu_gpb.cpp create mode 100644 tests/test-hdr/map/hdr_multilevel_hashmap_rcu_gpi.cpp create mode 100644 tests/test-hdr/map/hdr_multilevel_hashmap_rcu_gpt.cpp create mode 100644 tests/test-hdr/map/hdr_multilevel_hashmap_rcu_shb.cpp create mode 100644 tests/test-hdr/map/hdr_multilevel_hashmap_rcu_sht.cpp diff --git a/cds/container/impl/multilevel_hashmap.h b/cds/container/impl/multilevel_hashmap.h index 09fadc16..1ed1b4ee 100644 --- a/cds/container/impl/multilevel_hashmap.h +++ b/cds/container/impl/multilevel_hashmap.h @@ -57,7 +57,7 @@ namespace cds { namespace container { @note Two important things you should keep in mind when you're using \p %MultiLevelHashMap: - all keys is converted to fixed-size bit-string by hash functor provided. You can use variable-length keys, for example, \p std::string as a key for \p %MultiLevelHashMap, - but real key in the map will be fixed-ize hash values of your keys. + but real key in the map will be fixed-size hash values of your keys. For the strings you may use well-known hashing algorithms like SHA1, SHA2, MurmurHash, CityHash or its successor FarmHash and so on, which diff --git a/cds/container/multilevel_hashmap_rcu.h b/cds/container/multilevel_hashmap_rcu.h new file mode 100644 index 00000000..c120b344 --- /dev/null +++ b/cds/container/multilevel_hashmap_rcu.h @@ -0,0 +1,780 @@ +//$$CDS-header$$ + +#ifndef CDSLIB_CONTAINER_MULTILEVEL_HASHMAP_RCU_H +#define CDSLIB_CONTAINER_MULTILEVEL_HASHMAP_RCU_H + +#include +#include + +namespace cds { namespace container { + + /// Hash map based on multi-level array + /** @ingroup cds_nonintrusive_map + @anchor cds_container_MultilevelHashMap_rcu + + Source: + - [2013] Steven Feldman, Pierre LaBorde, Damian Dechev "Concurrent Multi-level Arrays: + Wait-free Extensible Hash Maps" + + See algorithm short description @ref cds_container_MultilevelHashMap_hp "here" + + @note Two important things you should keep in mind when you're using \p %MultiLevelHashMap: + - all keys is converted to fixed-size bit-string by hash functor provided. + You can use variable-length keys, for example, \p std::string as a key for \p %MultiLevelHashMap, + but real key in the map will be fixed-size hash values of your keys. + For the strings you may use well-known hashing algorithms like SHA1, SHA2, + MurmurHash, CityHash + or its successor FarmHash and so on, which + converts variable-length strings to fixed-length bit-strings, and such hash values will be the keys in \p %MultiLevelHashMap. + - \p %MultiLevelHashMap uses a perfect hashing. It means that if two different keys, for example, of type \p std::string, + have identical hash then you cannot insert both that keys in the map. \p %MultiLevelHashMap does not maintain the key, + it maintains its fixed-size hash value. + + The map supports @ref cds_container_MultilevelHashMap_rcu_iterators "bidirectional thread-safe iterators". + + Template parameters: + - \p RCU - one of \ref cds_urcu_gc "RCU type" + - \p Key - a key type to be stored in the map + - \p T - a value type to be stored in the map + - \p Traits - type traits, the structure based on \p multilevel_hashmap::traits or result of \p multilevel_hashmap::make_traits metafunction. + + @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. + */ + template < + class RCU + ,typename Key + ,typename T +#ifdef CDS_DOXYGEN_INVOKED + ,class Traits = multilevel_hashmap::traits +#else + ,class Traits +#endif + > + class MultiLevelHashMap< cds::urcu::gc< RCU >, Key, T, Traits > +#ifdef CDS_DOXYGEN_INVOKED + : protected cds::intrusive::MultiLevelHashSet< cds::urcu::gc< RCU >, std::pair, Traits > +#else + : protected cds::container::details::make_multilevel_hashmap< cds::urcu::gc< RCU >, Key, T, Traits >::type +#endif + { + //@cond + typedef cds::container::details::make_multilevel_hashmap< cds::urcu::gc< RCU >, Key, T, Traits > maker; + typedef typename maker::type base_class; + //@endcond + public: + typedef cds::urcu::gc< RCU > gc; ///< RCU garbage collector + typedef Key key_type; ///< Key type + typedef T mapped_type; ///< Mapped type + typedef std::pair< key_type const, mapped_type> value_type; ///< Key-value pair to be stored in the map + typedef Traits traits; ///< Map traits +#ifdef CDS_DOXYGEN_INVOKED + typedef typename traits::hash hasher; ///< Hash functor, see \p multilevel_hashmap::traits::hash +#else + typedef typename maker::hasher hasher; +#endif + + typedef typename maker::hash_type hash_type; ///< Hash type deduced from \p hasher return type + typedef typename base_class::hash_comparator hash_comparator; ///< hash compare functor based on \p Traits::compare and \p Traits::less + typedef typename traits::item_counter item_counter; ///< Item counter type + typedef typename traits::allocator allocator; ///< Element allocator + 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 + + protected: + //@cond + typedef typename maker::node_type node_type; + typedef typename maker::cxx_node_allocator cxx_node_allocator; + typedef std::unique_ptr< node_type, typename maker::node_disposer > scoped_node_ptr; + + struct node_cast + { + value_type * operator()(node_type * p) const + { + return p ? &p->m_Value : nullptr; + } + }; + + public: + /// pointer to extracted node + using exempt_ptr = cds::urcu::exempt_ptr< gc, node_type, value_type, typename base_class::disposer, node_cast >; + + protected: + template + class bidirectional_iterator: public base_class::iterator_base + { + friend class MultiLevelHashMap; + typedef typename base_class::iterator_base iterator_base; + + 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 + { + node_type * p = iterator_base::pointer(); + return p ? &p->m_Value : nullptr; + } + + value_ref operator *() const CDS_NOEXCEPT + { + node_type * p = iterator_base::pointer(); + assert( p ); + return p->m_Value; + } + + void release() + { + iterator_base::release(); + } + + 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 ); + } + + public: // for internal use only! + bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx, bool ) + : iterator_base( set, pNode, idx, false ) + {} + + bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx ) + : iterator_base( set, pNode, idx ) + {} + }; + + /// Reverse bidirectional iterator + template + class reverse_bidirectional_iterator : public base_class::iterator_base + { + friend class MultiLevelHashMap; + typedef typename base_class::iterator_base iterator_base; + + 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 + { + node_type * p = iterator_base::pointer(); + return p ? &p->m_Value : nullptr; + } + + value_ref operator *() const CDS_NOEXCEPT + { + node_type * p = iterator_base::pointer(); + assert( p ); + return p->m_Value; + } + + void release() + { + iterator_base::release(); + } + + 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 ); + } + + public: // for internal use only! + reverse_bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx, bool ) + : iterator_base( set, pNode, idx, false ) + {} + + reverse_bidirectional_iterator( base_class const& set, typename base_class::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_container_MultilevelHashMap_rcu_iterators "bidirectional iterator" type + typedef implementation_defined const_iterator; ///< @ref cds_container_MultilevelHashMap_rcu_iterators "bidirectional const iterator" type + typedef implementation_defined reverse_iterator; ///< @ref cds_container_MultilevelHashMap_rcu_iterators "bidirectional reverse iterator" type + typedef implementation_defined const_reverse_iterator; ///< @ref cds_container_MultilevelHashMap_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 + + protected: + //@cond + hasher m_Hasher; + //@endcond + + public: + /// Creates empty map + /** + @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. + */ + MultiLevelHashMap( size_t head_bits = 8, size_t array_bits = 4 ) + : base_class( head_bits, array_bits ) + {} + + /// Destructs the map and frees all data + ~MultiLevelHashMap() + {} + + /// Inserts new element with key and default value + /** + The function creates an element with \p key and default value, and then inserts the node created into the map. + + Preconditions: + - The \p key_type should be constructible from a value of type \p K. + In trivial case, \p K is equal to \p key_type. + - The \p mapped_type should be default-constructible. + + Returns \p true if inserting successful, \p false otherwise. + + The function locks RCU internally. + */ + template + bool insert( K&& key ) + { + scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward(key) )); + if ( base_class::insert( *sp )) { + sp.release(); + return true; + } + return false; + } + + /// Inserts new element + /** + The function creates a node with copy of \p val value + and then inserts the node created into the map. + + Preconditions: + - The \p key_type should be constructible from \p key of type \p K. + - The \p value_type should be constructible from \p val of type \p V. + + Returns \p true if \p val is inserted into the map, \p false otherwise. + + The function locks RCU internally. + */ + template + bool insert( K&& key, V&& val ) + { + scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward(key), std::forward(val))); + if ( base_class::insert( *sp )) { + sp.release(); + return true; + } + return false; + } + + /// Inserts new element and initialize it by a functor + /** + This function inserts new element with key \p key and if inserting is successful then it calls + \p func functor with signature + \code + struct functor { + void operator()( value_type& item ); + }; + \endcode + + The argument \p item of user-defined functor \p func is the reference + to the map's item inserted: + - item.first is a const reference to item's key that cannot be changed. + - item.second is a reference to item's value that may be changed. + + \p key_type should be constructible from value of type \p K. + + The function allows to split creating of new item into two part: + - create item from \p key; + - insert new item into the map; + - if inserting is successful, initialize the value of item by calling \p func functor + + This can be useful if complete initialization of object of \p value_type is heavyweight and + it is preferable that the initialization should be completed only if inserting is successful. + + The function locks RCU internally. + */ + template + bool insert_with( K&& key, Func func ) + { + scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward(key))); + if ( base_class::insert( *sp, [&func]( node_type& item ) { func( item.m_Value ); } )) { + sp.release(); + return true; + } + return false; + } + + /// For key \p key inserts data of type \p value_type created in-place from std::forward(args)... + /** + Returns \p true if inserting successful, \p false otherwise. + + The function locks RCU internally. + */ + template + bool emplace( K&& key, Args&&... args ) + { + scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward(key), std::forward(args)... )); + if ( base_class::insert( *sp )) { + sp.release(); + return true; + } + return false; + } + + /// Updates data by \p key + /** + The operation performs inserting or replacing the element with lock-free manner. + + If the \p key not found in the map, then the new item created from \p key + will be inserted into the map iff \p bInsert is \p true + (note that in this case the \ref key_type should be constructible from type \p K). + Otherwise, if \p key is found, it is replaced with a new item created from + \p key. + The functor \p Func signature: + \code + struct my_functor { + void operator()( value_type& item, value_type * old ); + }; + \endcode + where: + - \p item - item of the map + - \p old - old item of the map, if \p nullptr - the new item was inserted + + The functor may change any fields of the \p item.second. + + Returns std::pair where \p first is \p true if operation is successfull, + \p second is \p true if new item has been added or \p false if \p key already exists. + + The function locks RCU internally. + + @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" + */ + template + std::pair update( K&& key, Func func, bool bInsert = true ) + { + scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward(key))); + std::pair result = base_class::do_update( *sp, + [&func]( node_type& node, node_type * old ) { func( node.m_Value, old ? &old->m_Value : nullptr );}, + bInsert ); + if ( result.first ) + sp.release(); + return result; + } + + /// Delete \p key from the map + /** + \p key_type must be constructible from value of type \p K. + The function deeltes the element with hash value equal to hash( key_type( key )) + + Return \p true if \p key is found and deleted, \p false otherwise. + + RCU should not be locked. The function locks RCU internally. + */ + template + bool erase( K const& key ) + { + hash_type h = m_Hasher( key_type( key )); + return base_class::erase( h ); + } + + /// Delete \p key from the map + /** + The function searches an item with hash value equal to hash( key_type( key )), + calls \p f functor and deletes the item. If \p key is not found, the functor is not called. + + The functor \p Func interface: + \code + struct extractor { + void operator()(value_type& item) { ... } + }; + \endcode + where \p item is the element found. + + \p key_type must be constructible from value of type \p K. + + Return \p true if key is found and deleted, \p false otherwise + + RCU should not be locked. The function locks RCU internally. + */ + template + bool erase( K const& key, Func f ) + { + hash_type h = m_Hasher( key_type( key )); + return base_class::erase( h, [&f]( node_type& node) { f( node.m_Value ); } ); + } + + /// Extracts the item from the map with specified \p key + /** + The function searches an item with key equal to hash( key_type( key )) in the map, + unlinks it from the map, and returns a guarded pointer to the item found. + If \p key is not found the function returns an empty guarded pointer. + + 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::container::MultiLevelHashMap< cds::urcu::gc< cds::urcu::general_buffered<>>, int, foo, my_traits > map_type; + map_type theMap; + // ... + + typename map_type::exempt_ptr ep( theMap.extract( 5 )); + if ( ep ) { + // Deal with ep + //... + + // Dispose returned item. + ep.release(); + } + \endcode + */ + template + exempt_ptr extract( K const& key ) + { + check_deadlock_policy::check(); + + node_type * p; + { + rcu_lock rcuLock; + p = base_class::do_erase( m_Hasher( key_type(key)), [](node_type const&) -> bool {return true;}); + } + return exempt_ptr(p); + } + + /// Checks whether the map contains \p key + /** + The function searches the item by its hash that is equal to hash( key_type( key )) + and returns \p true if it is found, or \p false otherwise. + */ + template + bool contains( K const& key ) + { + return base_class::contains( m_Hasher( key_type( key )) ); + } + + /// Find the key \p key + /** + + The function searches the item by its hash that is equal to hash( key_type( key )) + 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 \p item.second. + + The function returns \p true if \p key is found, \p false otherwise. + */ + template + bool find( K const& key, Func f ) + { + return base_class::find( m_Hasher( key_type( key )), [&f](node_type& node) { f( node.m_Value );}); + } + + /// Finds the key \p key and return 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::container::MultiLevelHashMap< your_template_params > my_map; + my_map theMap; + // ... + { + // lock RCU + my_map::rcu_lock; + + foo * p = theMap.get( 5 ); + if ( p ) { + // Deal with p + //... + } + } + \endcode + */ + template + value_type * get( K const& key ) + { + node_type * p = base_class::get( m_Hasher( key_type( key ))); + return p ? &p->m_Value : nullptr; + } + + /// Clears the map (non-atomic) + /** + The function unlink all data node from the map. + The function is not atomic but is thread-safe. + After \p %clear() the map may not be empty because another threads may insert items. + */ + void clear() + { + base_class::clear(); + } + + /// Checks if the map is empty + /** + Emptiness is checked by item counting: if item count is zero then the map is empty. + Thus, the correct item counting feature is an important part of the map implementation. + */ + bool empty() const + { + return base_class::empty(); + } + + /// Returns item count in the map + size_t size() const + { + return base_class::size(); + } + + /// Returns const reference to internal statistics + stat const& statistics() const + { + return base_class::statistics(); + } + + /// Returns the size of head node + size_t head_size() const + { + return base_class::head_size(); + } + + /// Returns the size of the array node + size_t array_node_size() const + { + return base_class::array_node_size(); + } + + public: + ///@name Thread-safe iterators + /** @anchor cds_container_MultilevelHashMap_rcu_iterators + The map supports thread-safe iterators: you may iterate over the map 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 map + 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 { + // ... other fields + uint32_t payload; // only for example + }; + typedef cds::urcu::gc< cds::urcu::general_buffered<>> rcu; + typedef cds::container::MultiLevelHashMap< rcu, std::string, foo> map_type; + + map_type m; + + // ... + + // iterate over the map + { + // lock the RCU. + typename set_type::rcu_lock l; // scoped RCU lock + + // traverse the map + for ( auto i = m.begin(); i != s.end(); ++i ) { + // deal with i. Remember, erasing is prohibited here! + i->second.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 map + iterator begin() + { + return base_class::template init_begin(); + } + + /// Returns an const iterator to the beginning of the map + const_iterator begin() const + { + return base_class::template init_begin(); + } + + /// Returns an const iterator to the beginning of the map + const_iterator cbegin() + { + return base_class::template init_begin(); + } + + /// Returns an iterator to the element following the last element of the map. This element acts as a placeholder; attempting to access it results in undefined behavior. + iterator end() + { + return base_class::template init_end(); + } + + /// Returns a const iterator to the element following the last element of the map. This element acts as a placeholder; attempting to access it results in undefined behavior. + const_iterator end() const + { + return base_class::template init_end(); + } + + /// Returns a const iterator to the element following the last element of the map. This element acts as a placeholder; attempting to access it results in undefined behavior. + const_iterator cend() + { + return base_class::template init_end(); + } + + /// Returns a reverse iterator to the first element of the reversed map + reverse_iterator rbegin() + { + return base_class::template init_rbegin(); + } + + /// Returns a const reverse iterator to the first element of the reversed map + const_reverse_iterator rbegin() const + { + return base_class::template init_rbegin(); + } + + /// Returns a const reverse iterator to the first element of the reversed map + const_reverse_iterator crbegin() + { + return base_class::template init_rbegin(); + } + + /// Returns a reverse iterator to the element following the last element of the reversed map + /** + 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 base_class::template init_rend(); + } + + /// Returns a const reverse iterator to the element following the last element of the reversed map + /** + 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 base_class::template init_rend(); + } + + /// Returns a const reverse iterator to the element following the last element of the reversed map + /** + 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 base_class::template init_rend(); + } + ///@} + }; +}} // namespace cds::container + +#endif // #ifndef CDSLIB_CONTAINER_MULTILEVEL_HASHMAP_RCU_H diff --git a/cds/container/multilevel_hashset_rcu.h b/cds/container/multilevel_hashset_rcu.h index b84e344a..fdd1f5ed 100644 --- a/cds/container/multilevel_hashset_rcu.h +++ b/cds/container/multilevel_hashset_rcu.h @@ -16,7 +16,7 @@ namespace cds { namespace container { - [2013] Steven Feldman, Pierre LaBorde, Damian Dechev "Concurrent Multi-level Arrays: Wait-free Extensible Hash Maps" - See algorithm short description @ref cds_intrusive_MultilevelHashSet_RCU "here" + See algorithm short description @ref cds_intrusive_MultilevelHashSet_hp "here" @note Two important things you should keep in mind when you're using \p %MultiLevelHashSet: - all keys must be fixed-size. It means that you cannot use \p std::string as a key for \p %MultiLevelHashSet. @@ -225,6 +225,8 @@ namespace cds { namespace container { The function searches \p hash in the set, deletes the item found, and returns \p true. If that item is not found the function returns \p false. + + RCU should not be locked. The function locks RCU internally. */ bool erase( hash_type const& hash ) { @@ -244,6 +246,8 @@ namespace cds { namespace container { \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 ) diff --git a/projects/Win/vc12/cds.vcxproj b/projects/Win/vc12/cds.vcxproj index f83e634d..0ec0c295 100644 --- a/projects/Win/vc12/cds.vcxproj +++ b/projects/Win/vc12/cds.vcxproj @@ -704,6 +704,7 @@ + diff --git a/projects/Win/vc12/cds.vcxproj.filters b/projects/Win/vc12/cds.vcxproj.filters index dff39dfa..7ecba805 100644 --- a/projects/Win/vc12/cds.vcxproj.filters +++ b/projects/Win/vc12/cds.vcxproj.filters @@ -1223,5 +1223,8 @@ Header Files\cds\container + + Header Files\cds\container + \ No newline at end of file diff --git a/projects/Win/vc12/hdr-test-map.vcxproj b/projects/Win/vc12/hdr-test-map.vcxproj index a298e9a4..674216bc 100644 --- a/projects/Win/vc12/hdr-test-map.vcxproj +++ b/projects/Win/vc12/hdr-test-map.vcxproj @@ -569,6 +569,11 @@ + + + + + diff --git a/projects/Win/vc12/hdr-test-map.vcxproj.filters b/projects/Win/vc12/hdr-test-map.vcxproj.filters index 22112b2f..a8e47dce 100644 --- a/projects/Win/vc12/hdr-test-map.vcxproj.filters +++ b/projects/Win/vc12/hdr-test-map.vcxproj.filters @@ -181,6 +181,21 @@ multilvel_hashmap + + multilvel_hashmap + + + multilvel_hashmap + + + multilvel_hashmap + + + multilvel_hashmap + + + multilvel_hashmap + diff --git a/projects/Win/vc14/cds.vcxproj b/projects/Win/vc14/cds.vcxproj index b194cbc4..997771d8 100644 --- a/projects/Win/vc14/cds.vcxproj +++ b/projects/Win/vc14/cds.vcxproj @@ -809,6 +809,7 @@ + diff --git a/projects/Win/vc14/cds.vcxproj.filters b/projects/Win/vc14/cds.vcxproj.filters index dff39dfa..7ecba805 100644 --- a/projects/Win/vc14/cds.vcxproj.filters +++ b/projects/Win/vc14/cds.vcxproj.filters @@ -1223,5 +1223,8 @@ Header Files\cds\container + + Header Files\cds\container + \ No newline at end of file diff --git a/projects/Win/vc14/hdr-test-map.vcxproj b/projects/Win/vc14/hdr-test-map.vcxproj index 280939d0..fc21891d 100644 --- a/projects/Win/vc14/hdr-test-map.vcxproj +++ b/projects/Win/vc14/hdr-test-map.vcxproj @@ -668,6 +668,11 @@ + + + + + diff --git a/projects/Win/vc14/hdr-test-map.vcxproj.filters b/projects/Win/vc14/hdr-test-map.vcxproj.filters index 22112b2f..a8e47dce 100644 --- a/projects/Win/vc14/hdr-test-map.vcxproj.filters +++ b/projects/Win/vc14/hdr-test-map.vcxproj.filters @@ -181,6 +181,21 @@ multilvel_hashmap + + multilvel_hashmap + + + multilvel_hashmap + + + multilvel_hashmap + + + multilvel_hashmap + + + multilvel_hashmap + diff --git a/projects/source.test-hdr.mk b/projects/source.test-hdr.mk index 696dfadc..3e202ed4 100644 --- a/projects/source.test-hdr.mk +++ b/projects/source.test-hdr.mk @@ -17,6 +17,11 @@ CDS_TESTHDR_MAP := \ tests/test-hdr/map/hdr_michael_map_lazy_nogc.cpp \ tests/test-hdr/map/hdr_multilevel_hashmap_hp.cpp \ tests/test-hdr/map/hdr_multilevel_hashmap_dhp.cpp \ + tests/test-hdr/map/hdr_multilevel_hashmap_rcu_gpb.cpp \ + tests/test-hdr/map/hdr_multilevel_hashmap_rcu_gpi.cpp \ + tests/test-hdr/map/hdr_multilevel_hashmap_rcu_gpt.cpp \ + tests/test-hdr/map/hdr_multilevel_hashmap_rcu_shb.cpp \ + tests/test-hdr/map/hdr_multilevel_hashmap_rcu_sht.cpp \ tests/test-hdr/map/hdr_refinable_hashmap_hashmap_std.cpp \ tests/test-hdr/map/hdr_refinable_hashmap_boost_list.cpp \ tests/test-hdr/map/hdr_refinable_hashmap_list.cpp \ diff --git a/tests/test-hdr/CMakeLists.txt b/tests/test-hdr/CMakeLists.txt index f6a4ccd1..e90e9462 100644 --- a/tests/test-hdr/CMakeLists.txt +++ b/tests/test-hdr/CMakeLists.txt @@ -19,6 +19,11 @@ set(CDS_TESTHDR_MAP map/hdr_michael_map_lazy_nogc.cpp map/hdr_multilevel_hashmap_hp.cpp map/hdr_multilevel_hashmap_dhp.cpp + map/hdr_multilevel_hashmap_rcu_gpb.cpp + map/hdr_multilevel_hashmap_rcu_gpi.cpp + map/hdr_multilevel_hashmap_rcu_gpt.cpp + map/hdr_multilevel_hashmap_rcu_shb.cpp + map/hdr_multilevel_hashmap_rcu_sht.cpp map/hdr_refinable_hashmap_hashmap_std.cpp map/hdr_refinable_hashmap_boost_list.cpp map/hdr_refinable_hashmap_list.cpp diff --git a/tests/test-hdr/map/hdr_multilevel_hashmap.h b/tests/test-hdr/map/hdr_multilevel_hashmap.h index d8f0a05c..559c87d8 100644 --- a/tests/test-hdr/map/hdr_multilevel_hashmap.h +++ b/tests/test-hdr/map/hdr_multilevel_hashmap.h @@ -359,6 +359,255 @@ namespace map { CPPUNIT_MSG( m.statistics() ); } + template + void test_rcu(size_t nHeadBits, size_t nArrayBits) + { + typedef typename Map::hash_type hash_type; + typedef typename Map::key_type key_type; + typedef typename Map::mapped_type mapped_type; + typedef typename Map::value_type value_type; + typedef typename Map::exempt_ptr exempt_ptr; + typedef typename Map::rcu_lock rcu_lock; + + size_t const capacity = 1000; + + Map m(nHeadBits, nArrayBits); + CPPUNIT_MSG("Array size: head=" << m.head_size() << ", array_node=" << m.array_node_size()); + CPPUNIT_ASSERT(m.head_size() >= (size_t(1) << nHeadBits)); + CPPUNIT_ASSERT(m.array_node_size() == (size_t(1) << nArrayBits)); + + CPPUNIT_ASSERT(m.empty()); + CPPUNIT_ASSERT(m.size() == 0); + + // insert( key )/update()/get()/find() + for (size_t i = 0; i < capacity; ++i) { + size_t key = i * 57; + CPPUNIT_ASSERT(!m.contains(key)) + CPPUNIT_ASSERT(m.insert(key)); + CPPUNIT_ASSERT(m.contains(key)); + CPPUNIT_ASSERT(m.size() == i + 1); + + auto ret = m.update(key, [](value_type& v, value_type * old) { + CPPUNIT_ASSERT_CURRENT(old != nullptr); + ++v.second.nInsertCall; + }, false); + CPPUNIT_ASSERT(ret.first); + CPPUNIT_ASSERT(!ret.second); + + CPPUNIT_ASSERT(m.find(key, [](value_type& v) { ++v.second.nFindCall;})); + + { + rcu_lock l; + value_type* p{ m.get(key) }; + CPPUNIT_ASSERT(p); + CPPUNIT_ASSERT(p->first == key); + CPPUNIT_ASSERT(p->second.nInsertCall == 1); + CPPUNIT_ASSERT(p->second.nFindCall == 1); + } + } + CPPUNIT_ASSERT(!m.empty()); + CPPUNIT_ASSERT(m.size() == capacity); + + // iterator test + size_t nCount = 0; + { + rcu_lock l; + for (auto it = m.begin(), itEnd = m.end(); it != itEnd; ++it) { + CPPUNIT_ASSERT(it->second.nIteratorCall == 0); + CPPUNIT_ASSERT(it->second.nInsertCall == 1); + CPPUNIT_ASSERT((*it).second.nFindCall == 1); + it->second.nIteratorCall += 1; + ++nCount; + } + } + CPPUNIT_ASSERT(nCount == capacity); + + nCount = 0; + { + rcu_lock l; + for (auto it = m.rbegin(), itEnd = m.rend(); it != itEnd; ++it) { + CPPUNIT_ASSERT(it->second.nInsertCall == 1); + CPPUNIT_ASSERT((*it).second.nFindCall == 1); + CPPUNIT_ASSERT(it->second.nIteratorCall == 1); + (*it).second.nIteratorCall += 1; + ++nCount; + } + } + CPPUNIT_ASSERT(nCount == capacity); + + nCount = 0; + { + rcu_lock l; + for (auto it = m.cbegin(), itEnd = m.cend(); it != itEnd; ++it) { + CPPUNIT_ASSERT(it->second.nInsertCall == 1); + CPPUNIT_ASSERT((*it).second.nFindCall == 1); + CPPUNIT_ASSERT(it->second.nIteratorCall == 2); + (*it).second.nIteratorCall += 1; + ++nCount; + } + } + CPPUNIT_ASSERT(nCount == capacity); + + nCount = 0; + { + rcu_lock l; + for (auto it = m.crbegin(), itEnd = m.crend(); it != itEnd; ++it) { + CPPUNIT_ASSERT(it->second.nInsertCall == 1); + CPPUNIT_ASSERT((*it).second.nFindCall == 1); + CPPUNIT_ASSERT(it->second.nIteratorCall == 3); + (*it).second.nIteratorCall += 1; + ++nCount; + } + } + CPPUNIT_ASSERT(nCount == capacity); + + // find + for (size_t i = 0; i < capacity; i++) { + size_t key = i * 57; + CPPUNIT_ASSERT(m.find(key, [key](value_type& v) { + CPPUNIT_ASSERT_CURRENT(v.first == key); + CPPUNIT_ASSERT_CURRENT(v.second.nInsertCall == 1); + CPPUNIT_ASSERT_CURRENT(v.second.nFindCall == 1); + CPPUNIT_ASSERT_CURRENT(v.second.nIteratorCall == 4); + })); + } + + // erase + for (size_t i = capacity; i > 0; --i) { + size_t key = (i - 1) * 57; + { + rcu_lock l; + value_type* p = m.get(key); + CPPUNIT_ASSERT(p); + CPPUNIT_ASSERT(p->first == key); + CPPUNIT_ASSERT(p->second.nInsertCall == 1); + CPPUNIT_ASSERT(p->second.nFindCall == 1); + CPPUNIT_ASSERT(p->second.nIteratorCall == 4); + } + + CPPUNIT_ASSERT(m.erase(key)); + + { + rcu_lock l; + value_type* p = m.get(key); + CPPUNIT_ASSERT(!p); + } + CPPUNIT_ASSERT(!m.contains(key)); + } + CPPUNIT_ASSERT(m.empty()); + CPPUNIT_ASSERT(m.size() == 0); + + // Iterators on empty map + { + rcu_lock l; + CPPUNIT_ASSERT(m.begin() == m.end()); + CPPUNIT_ASSERT(m.cbegin() == m.cend()); + CPPUNIT_ASSERT(m.rbegin() == m.rend()); + CPPUNIT_ASSERT(m.crbegin() == m.crend()); + } + + // insert( key, val ) + for (size_t i = 0; i < capacity; ++i) { + CPPUNIT_ASSERT(!m.contains(i)); + CPPUNIT_ASSERT(m.insert(i, (unsigned int)i * 100)); + CPPUNIT_ASSERT(m.contains(i)); + CPPUNIT_ASSERT(m.find(i, [i](value_type& v) { + CPPUNIT_ASSERT_CURRENT(v.first == i); + CPPUNIT_ASSERT_CURRENT(v.second.nInsertCall == i * 100); + })); + } + CPPUNIT_ASSERT(!m.empty()); + CPPUNIT_ASSERT(m.size() == capacity); + + // erase( key, func ) + for (size_t i = 0; i < capacity; ++i) { + CPPUNIT_ASSERT(m.contains(i)); + CPPUNIT_ASSERT(m.erase(i, [i](value_type& v) { + CPPUNIT_ASSERT_CURRENT(v.first == i); + CPPUNIT_ASSERT_CURRENT(v.second.nInsertCall == i * 100); + v.second.nInsertCall = 0; + })); + } + CPPUNIT_ASSERT(m.empty()); + CPPUNIT_ASSERT(m.size() == 0); + + // insert_with + for (size_t i = 0; i < capacity; ++i) { + size_t key = i * 121; + CPPUNIT_ASSERT(!m.contains(key)); + CPPUNIT_ASSERT(m.insert_with(key, [key](value_type& v) { + CPPUNIT_ASSERT_CURRENT(v.first == key); + CPPUNIT_ASSERT_CURRENT(v.second.nInsertCall == 0); + v.second.nInsertCall = decltype(v.second.nInsertCall)(key); + })); + CPPUNIT_ASSERT(m.find(key, [key](value_type& v) { + CPPUNIT_ASSERT_CURRENT(v.first == key); + CPPUNIT_ASSERT_CURRENT(v.second.nInsertCall == key); + })); + CPPUNIT_ASSERT(m.size() == i + 1); + } + CPPUNIT_ASSERT(!m.empty()); + CPPUNIT_ASSERT(m.size() == capacity); + + nCount = 0; + { + rcu_lock l; + for (auto it = m.begin(), itEnd = m.end(); it != itEnd; ++it) { + CPPUNIT_ASSERT(it->first == it->second.nInsertCall); + CPPUNIT_ASSERT(it->second.nIteratorCall == 0); + it->second.nIteratorCall += 1; + ++nCount; + } + } + CPPUNIT_ASSERT(nCount == capacity); + + nCount = 0; + { + rcu_lock l; + for (auto it = m.rbegin(), itEnd = m.rend(); it != itEnd; ++it) { + CPPUNIT_ASSERT(it->first == it->second.nInsertCall); + CPPUNIT_ASSERT(it->second.nIteratorCall == 1); + it->second.nIteratorCall += 1; + ++nCount; + } + } + CPPUNIT_ASSERT(nCount == capacity); + + // clear() + m.clear(); + CPPUNIT_ASSERT(m.empty()); + CPPUNIT_ASSERT(m.size() == 0); + + // emplace + for (size_t i = 0; i < capacity; ++i) { + size_t key = i * 1023; + CPPUNIT_ASSERT(!m.contains(key)); + CPPUNIT_ASSERT(m.emplace(key, static_cast(i))); + CPPUNIT_ASSERT(m.find(key, [key](value_type& v) { + CPPUNIT_ASSERT_CURRENT(v.first == key); + CPPUNIT_ASSERT_CURRENT(v.second.nInsertCall * 1023 == key); + })); + CPPUNIT_ASSERT(m.size() == i + 1); + } + CPPUNIT_ASSERT(!m.empty()); + CPPUNIT_ASSERT(m.size() == capacity); + + // extract + for (size_t i = capacity; i > 0; --i) { + size_t key = (i - 1) * 1023; + exempt_ptr xp{ m.extract(key) }; + CPPUNIT_ASSERT(xp); + CPPUNIT_ASSERT(xp->first == key); + CPPUNIT_ASSERT((*xp).second.nInsertCall == static_cast(i - 1)); + xp = m.extract(key); + CPPUNIT_ASSERT(!xp); + } + CPPUNIT_ASSERT(m.empty()); + CPPUNIT_ASSERT(m.size() == 0); + + CPPUNIT_MSG(m.statistics()); + } + void hp_stdhash(); void hp_stdhash_stat(); void hp_stdhash_5_3(); @@ -377,6 +626,51 @@ namespace map { void dhp_hash128_4_3(); void dhp_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_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_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(MultiLevelHashMapHdrTest) CPPUNIT_TEST(hp_stdhash) CPPUNIT_TEST(hp_stdhash_stat) @@ -395,6 +689,51 @@ namespace map { CPPUNIT_TEST(dhp_hash128_stat) CPPUNIT_TEST(dhp_hash128_4_3) CPPUNIT_TEST(dhp_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_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_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() }; diff --git a/tests/test-hdr/map/hdr_multilevel_hashmap_rcu_gpb.cpp b/tests/test-hdr/map/hdr_multilevel_hashmap_rcu_gpb.cpp new file mode 100644 index 00000000..51c90957 --- /dev/null +++ b/tests/test-hdr/map/hdr_multilevel_hashmap_rcu_gpb.cpp @@ -0,0 +1,139 @@ +//$$CDS-header$$ + +#include "map/hdr_multilevel_hashmap.h" +#include +#include +#include "unit/print_multilevel_hashset_stat.h" + +namespace map { + namespace { + typedef cds::urcu::gc< cds::urcu::general_buffered<>> rcu_type; + } // namespace + + void MultiLevelHashMapHdrTest::rcu_gpb_stdhash() + { + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item > map_type; + + test_rcu(4, 2); + } + + void MultiLevelHashMapHdrTest::rcu_gpb_hash128() + { + struct traits : public cc::multilevel_hashmap::traits { + typedef hash128::make hash; + typedef hash128::less less; + }; + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, traits > map_type; + test_rcu(4, 2); + + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::hash< hash128::make > + , co::less< hash128::less > + >::type + > map_type2; + test_rcu(4, 2); + } + + void MultiLevelHashMapHdrTest::rcu_gpb_stdhash_stat() + { + struct traits : public cc::multilevel_hashmap::traits { + typedef cc::multilevel_hashmap::stat<> stat; + }; + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, traits > map_type; + test_rcu(4, 2); + + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::stat< cc::multilevel_hashmap::stat<>> + >::type + > map_type2; + test_rcu(4, 2); + } + + void MultiLevelHashMapHdrTest::rcu_gpb_hash128_stat() + { + struct traits : public cc::multilevel_hashmap::traits { + typedef cc::multilevel_hashmap::stat<> stat; + typedef hash128::make hash; + typedef hash128::cmp compare; + }; + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, traits > map_type; + test_rcu(4, 2); + + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::stat< cc::multilevel_hashmap::stat<>> + , co::hash< hash128::make > + , co::compare< hash128::cmp > + >::type + > map_type2; + test_rcu(4, 2); + } + + void MultiLevelHashMapHdrTest::rcu_gpb_stdhash_5_3() + { + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item > map_type; + + test_rcu(5, 3); + } + + void MultiLevelHashMapHdrTest::rcu_gpb_stdhash_5_3_stat() + { + struct traits : public cc::multilevel_hashmap::traits { + typedef cc::multilevel_hashmap::stat<> stat; + typedef cds::backoff::empty back_off; + }; + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, traits > map_type; + test_rcu(5, 3); + + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::stat< cc::multilevel_hashmap::stat<>> + ,co::back_off< cds::backoff::empty > + >::type + > map_type2; + test_rcu(5, 3); + } + + void MultiLevelHashMapHdrTest::rcu_gpb_hash128_4_3() + { + struct traits : public cc::multilevel_hashmap::traits { + typedef hash128::make hash; + typedef hash128::less less; + }; + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, traits > map_type; + test_rcu(4, 3); + + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::hash< hash128::make > + , co::less< hash128::less > + >::type + > map_type2; + test_rcu(4, 3); + } + + void MultiLevelHashMapHdrTest::rcu_gpb_hash128_4_3_stat() + { + struct traits : public cc::multilevel_hashmap::traits { + typedef hash128::make hash; + typedef hash128::less less; + typedef cc::multilevel_hashmap::stat<> stat; + typedef co::v::sequential_consistent memory_model; + }; + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, traits > map_type; + test_rcu(4, 3); + + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::hash< hash128::make > + , co::less< hash128::less > + , co::stat< cc::multilevel_hashmap::stat<>> + , co::memory_model< co::v::sequential_consistent > + >::type + > map_type2; + test_rcu(4, 3); + } + +} // namespace map diff --git a/tests/test-hdr/map/hdr_multilevel_hashmap_rcu_gpi.cpp b/tests/test-hdr/map/hdr_multilevel_hashmap_rcu_gpi.cpp new file mode 100644 index 00000000..134eae2c --- /dev/null +++ b/tests/test-hdr/map/hdr_multilevel_hashmap_rcu_gpi.cpp @@ -0,0 +1,139 @@ +//$$CDS-header$$ + +#include "map/hdr_multilevel_hashmap.h" +#include +#include +#include "unit/print_multilevel_hashset_stat.h" + +namespace map { + namespace { + typedef cds::urcu::gc< cds::urcu::general_instant<>> rcu_type; + } // namespace + + void MultiLevelHashMapHdrTest::rcu_gpi_stdhash() + { + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item > map_type; + + test_rcu(4, 2); + } + + void MultiLevelHashMapHdrTest::rcu_gpi_hash128() + { + struct traits : public cc::multilevel_hashmap::traits { + typedef hash128::make hash; + typedef hash128::less less; + }; + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, traits > map_type; + test_rcu(4, 2); + + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::hash< hash128::make > + , co::less< hash128::less > + >::type + > map_type2; + test_rcu(4, 2); + } + + void MultiLevelHashMapHdrTest::rcu_gpi_stdhash_stat() + { + struct traits : public cc::multilevel_hashmap::traits { + typedef cc::multilevel_hashmap::stat<> stat; + }; + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, traits > map_type; + test_rcu(4, 2); + + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::stat< cc::multilevel_hashmap::stat<>> + >::type + > map_type2; + test_rcu(4, 2); + } + + void MultiLevelHashMapHdrTest::rcu_gpi_hash128_stat() + { + struct traits : public cc::multilevel_hashmap::traits { + typedef cc::multilevel_hashmap::stat<> stat; + typedef hash128::make hash; + typedef hash128::cmp compare; + }; + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, traits > map_type; + test_rcu(4, 2); + + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::stat< cc::multilevel_hashmap::stat<>> + , co::hash< hash128::make > + , co::compare< hash128::cmp > + >::type + > map_type2; + test_rcu(4, 2); + } + + void MultiLevelHashMapHdrTest::rcu_gpi_stdhash_5_3() + { + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item > map_type; + + test_rcu(5, 3); + } + + void MultiLevelHashMapHdrTest::rcu_gpi_stdhash_5_3_stat() + { + struct traits : public cc::multilevel_hashmap::traits { + typedef cc::multilevel_hashmap::stat<> stat; + typedef cds::backoff::empty back_off; + }; + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, traits > map_type; + test_rcu(5, 3); + + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::stat< cc::multilevel_hashmap::stat<>> + ,co::back_off< cds::backoff::empty > + >::type + > map_type2; + test_rcu(5, 3); + } + + void MultiLevelHashMapHdrTest::rcu_gpi_hash128_4_3() + { + struct traits : public cc::multilevel_hashmap::traits { + typedef hash128::make hash; + typedef hash128::less less; + }; + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, traits > map_type; + test_rcu(4, 3); + + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::hash< hash128::make > + , co::less< hash128::less > + >::type + > map_type2; + test_rcu(4, 3); + } + + void MultiLevelHashMapHdrTest::rcu_gpi_hash128_4_3_stat() + { + struct traits : public cc::multilevel_hashmap::traits { + typedef hash128::make hash; + typedef hash128::less less; + typedef cc::multilevel_hashmap::stat<> stat; + typedef co::v::sequential_consistent memory_model; + }; + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, traits > map_type; + test_rcu(4, 3); + + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::hash< hash128::make > + , co::less< hash128::less > + , co::stat< cc::multilevel_hashmap::stat<>> + , co::memory_model< co::v::sequential_consistent > + >::type + > map_type2; + test_rcu(4, 3); + } + +} // namespace map diff --git a/tests/test-hdr/map/hdr_multilevel_hashmap_rcu_gpt.cpp b/tests/test-hdr/map/hdr_multilevel_hashmap_rcu_gpt.cpp new file mode 100644 index 00000000..32d85b3c --- /dev/null +++ b/tests/test-hdr/map/hdr_multilevel_hashmap_rcu_gpt.cpp @@ -0,0 +1,139 @@ +//$$CDS-header$$ + +#include "map/hdr_multilevel_hashmap.h" +#include +#include +#include "unit/print_multilevel_hashset_stat.h" + +namespace map { + namespace { + typedef cds::urcu::gc< cds::urcu::general_threaded<>> rcu_type; + } // namespace + + void MultiLevelHashMapHdrTest::rcu_gpt_stdhash() + { + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item > map_type; + + test_rcu(4, 2); + } + + void MultiLevelHashMapHdrTest::rcu_gpt_hash128() + { + struct traits : public cc::multilevel_hashmap::traits { + typedef hash128::make hash; + typedef hash128::less less; + }; + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, traits > map_type; + test_rcu(4, 2); + + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::hash< hash128::make > + , co::less< hash128::less > + >::type + > map_type2; + test_rcu(4, 2); + } + + void MultiLevelHashMapHdrTest::rcu_gpt_stdhash_stat() + { + struct traits : public cc::multilevel_hashmap::traits { + typedef cc::multilevel_hashmap::stat<> stat; + }; + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, traits > map_type; + test_rcu(4, 2); + + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::stat< cc::multilevel_hashmap::stat<>> + >::type + > map_type2; + test_rcu(4, 2); + } + + void MultiLevelHashMapHdrTest::rcu_gpt_hash128_stat() + { + struct traits : public cc::multilevel_hashmap::traits { + typedef cc::multilevel_hashmap::stat<> stat; + typedef hash128::make hash; + typedef hash128::cmp compare; + }; + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, traits > map_type; + test_rcu(4, 2); + + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::stat< cc::multilevel_hashmap::stat<>> + , co::hash< hash128::make > + , co::compare< hash128::cmp > + >::type + > map_type2; + test_rcu(4, 2); + } + + void MultiLevelHashMapHdrTest::rcu_gpt_stdhash_5_3() + { + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item > map_type; + + test_rcu(5, 3); + } + + void MultiLevelHashMapHdrTest::rcu_gpt_stdhash_5_3_stat() + { + struct traits : public cc::multilevel_hashmap::traits { + typedef cc::multilevel_hashmap::stat<> stat; + typedef cds::backoff::empty back_off; + }; + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, traits > map_type; + test_rcu(5, 3); + + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::stat< cc::multilevel_hashmap::stat<>> + ,co::back_off< cds::backoff::empty > + >::type + > map_type2; + test_rcu(5, 3); + } + + void MultiLevelHashMapHdrTest::rcu_gpt_hash128_4_3() + { + struct traits : public cc::multilevel_hashmap::traits { + typedef hash128::make hash; + typedef hash128::less less; + }; + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, traits > map_type; + test_rcu(4, 3); + + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::hash< hash128::make > + , co::less< hash128::less > + >::type + > map_type2; + test_rcu(4, 3); + } + + void MultiLevelHashMapHdrTest::rcu_gpt_hash128_4_3_stat() + { + struct traits : public cc::multilevel_hashmap::traits { + typedef hash128::make hash; + typedef hash128::less less; + typedef cc::multilevel_hashmap::stat<> stat; + typedef co::v::sequential_consistent memory_model; + }; + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, traits > map_type; + test_rcu(4, 3); + + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::hash< hash128::make > + , co::less< hash128::less > + , co::stat< cc::multilevel_hashmap::stat<>> + , co::memory_model< co::v::sequential_consistent > + >::type + > map_type2; + test_rcu(4, 3); + } + +} // namespace map diff --git a/tests/test-hdr/map/hdr_multilevel_hashmap_rcu_shb.cpp b/tests/test-hdr/map/hdr_multilevel_hashmap_rcu_shb.cpp new file mode 100644 index 00000000..b553661e --- /dev/null +++ b/tests/test-hdr/map/hdr_multilevel_hashmap_rcu_shb.cpp @@ -0,0 +1,157 @@ +//$$CDS-header$$ + +#include "map/hdr_multilevel_hashmap.h" +#include +#include +#include "unit/print_multilevel_hashset_stat.h" + +namespace map { +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + namespace { + typedef cds::urcu::gc< cds::urcu::signal_buffered<>> rcu_type; + } // namespace +#endif + + void MultiLevelHashMapHdrTest::rcu_shb_stdhash() + { +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item > map_type; + + test_rcu(4, 2); +#endif + } + + void MultiLevelHashMapHdrTest::rcu_shb_hash128() + { +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + struct traits : public cc::multilevel_hashmap::traits { + typedef hash128::make hash; + typedef hash128::less less; + }; + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, traits > map_type; + test_rcu(4, 2); + + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::hash< hash128::make > + , co::less< hash128::less > + >::type + > map_type2; + test_rcu(4, 2); +#endif + } + + void MultiLevelHashMapHdrTest::rcu_shb_stdhash_stat() + { +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + struct traits : public cc::multilevel_hashmap::traits { + typedef cc::multilevel_hashmap::stat<> stat; + }; + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, traits > map_type; + test_rcu(4, 2); + + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::stat< cc::multilevel_hashmap::stat<>> + >::type + > map_type2; + test_rcu(4, 2); +#endif + } + + void MultiLevelHashMapHdrTest::rcu_shb_hash128_stat() + { +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + struct traits : public cc::multilevel_hashmap::traits { + typedef cc::multilevel_hashmap::stat<> stat; + typedef hash128::make hash; + typedef hash128::cmp compare; + }; + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, traits > map_type; + test_rcu(4, 2); + + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::stat< cc::multilevel_hashmap::stat<>> + , co::hash< hash128::make > + , co::compare< hash128::cmp > + >::type + > map_type2; + test_rcu(4, 2); +#endif + } + + void MultiLevelHashMapHdrTest::rcu_shb_stdhash_5_3() + { +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item > map_type; + + test_rcu(5, 3); +#endif + } + + void MultiLevelHashMapHdrTest::rcu_shb_stdhash_5_3_stat() + { +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + struct traits : public cc::multilevel_hashmap::traits { + typedef cc::multilevel_hashmap::stat<> stat; + typedef cds::backoff::empty back_off; + }; + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, traits > map_type; + test_rcu(5, 3); + + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::stat< cc::multilevel_hashmap::stat<>> + ,co::back_off< cds::backoff::empty > + >::type + > map_type2; + test_rcu(5, 3); +#endif + } + + void MultiLevelHashMapHdrTest::rcu_shb_hash128_4_3() + { +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + struct traits : public cc::multilevel_hashmap::traits { + typedef hash128::make hash; + typedef hash128::less less; + }; + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, traits > map_type; + test_rcu(4, 3); + + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::hash< hash128::make > + , co::less< hash128::less > + >::type + > map_type2; + test_rcu(4, 3); +#endif + } + + void MultiLevelHashMapHdrTest::rcu_shb_hash128_4_3_stat() + { +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + struct traits : public cc::multilevel_hashmap::traits { + typedef hash128::make hash; + typedef hash128::less less; + typedef cc::multilevel_hashmap::stat<> stat; + typedef co::v::sequential_consistent memory_model; + }; + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, traits > map_type; + test_rcu(4, 3); + + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::hash< hash128::make > + , co::less< hash128::less > + , co::stat< cc::multilevel_hashmap::stat<>> + , co::memory_model< co::v::sequential_consistent > + >::type + > map_type2; + test_rcu(4, 3); +#endif + } + +} // namespace map diff --git a/tests/test-hdr/map/hdr_multilevel_hashmap_rcu_sht.cpp b/tests/test-hdr/map/hdr_multilevel_hashmap_rcu_sht.cpp new file mode 100644 index 00000000..0fc205f3 --- /dev/null +++ b/tests/test-hdr/map/hdr_multilevel_hashmap_rcu_sht.cpp @@ -0,0 +1,157 @@ +//$$CDS-header$$ + +#include "map/hdr_multilevel_hashmap.h" +#include +#include +#include "unit/print_multilevel_hashset_stat.h" + +namespace map { +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + namespace { + typedef cds::urcu::gc< cds::urcu::signal_threaded<>> rcu_type; + } // namespace +#endif + + void MultiLevelHashMapHdrTest::rcu_sht_stdhash() + { +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item > map_type; + + test_rcu(4, 2); +#endif + } + + void MultiLevelHashMapHdrTest::rcu_sht_hash128() + { +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + struct traits : public cc::multilevel_hashmap::traits { + typedef hash128::make hash; + typedef hash128::less less; + }; + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, traits > map_type; + test_rcu(4, 2); + + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::hash< hash128::make > + , co::less< hash128::less > + >::type + > map_type2; + test_rcu(4, 2); +#endif + } + + void MultiLevelHashMapHdrTest::rcu_sht_stdhash_stat() + { +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + struct traits : public cc::multilevel_hashmap::traits { + typedef cc::multilevel_hashmap::stat<> stat; + }; + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, traits > map_type; + test_rcu(4, 2); + + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::stat< cc::multilevel_hashmap::stat<>> + >::type + > map_type2; + test_rcu(4, 2); +#endif + } + + void MultiLevelHashMapHdrTest::rcu_sht_hash128_stat() + { +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + struct traits : public cc::multilevel_hashmap::traits { + typedef cc::multilevel_hashmap::stat<> stat; + typedef hash128::make hash; + typedef hash128::cmp compare; + }; + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, traits > map_type; + test_rcu(4, 2); + + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::stat< cc::multilevel_hashmap::stat<>> + , co::hash< hash128::make > + , co::compare< hash128::cmp > + >::type + > map_type2; + test_rcu(4, 2); +#endif + } + + void MultiLevelHashMapHdrTest::rcu_sht_stdhash_5_3() + { +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item > map_type; + + test_rcu(5, 3); +#endif + } + + void MultiLevelHashMapHdrTest::rcu_sht_stdhash_5_3_stat() + { +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + struct traits : public cc::multilevel_hashmap::traits { + typedef cc::multilevel_hashmap::stat<> stat; + typedef cds::backoff::empty back_off; + }; + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, traits > map_type; + test_rcu(5, 3); + + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::stat< cc::multilevel_hashmap::stat<>> + ,co::back_off< cds::backoff::empty > + >::type + > map_type2; + test_rcu(5, 3); +#endif + } + + void MultiLevelHashMapHdrTest::rcu_sht_hash128_4_3() + { +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + struct traits : public cc::multilevel_hashmap::traits { + typedef hash128::make hash; + typedef hash128::less less; + }; + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, traits > map_type; + test_rcu(4, 3); + + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::hash< hash128::make > + , co::less< hash128::less > + >::type + > map_type2; + test_rcu(4, 3); +#endif + } + + void MultiLevelHashMapHdrTest::rcu_sht_hash128_4_3_stat() + { +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + struct traits : public cc::multilevel_hashmap::traits { + typedef hash128::make hash; + typedef hash128::less less; + typedef cc::multilevel_hashmap::stat<> stat; + typedef co::v::sequential_consistent memory_model; + }; + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, traits > map_type; + test_rcu(4, 3); + + typedef cc::MultiLevelHashMap< rcu_type, size_t, Item, + typename cc::multilevel_hashmap::make_traits< + co::hash< hash128::make > + , co::less< hash128::less > + , co::stat< cc::multilevel_hashmap::stat<>> + , co::memory_model< co::v::sequential_consistent > + >::type + > map_type2; + test_rcu(4, 3); +#endif + } + +} // namespace map -- 2.34.1