From bb3ab6816ad59712e8f425c787bae156dc3d51f4 Mon Sep 17 00:00:00 2001 From: khizmax Date: Sat, 29 Aug 2015 16:23:36 +0300 Subject: [PATCH] MichaelList, LazyList, MichaelMap: - replace ensure() with update() - replace find( key ) with contains( key ) Ordered list unit test: refactored with new update() and contains() functions Beginning of large refactoring of map MT-test: - simplified MapDelOdd test for MichaelHashMap --- .../details/multilevel_hashmap_base.h | 3 + .../details/multilevel_hashset_base.h | 3 + cds/container/impl/lazy_kvlist.h | 72 +++-- cds/container/impl/lazy_list.h | 71 +++-- cds/container/impl/michael_kvlist.h | 75 +++-- cds/container/impl/michael_list.h | 68 +++-- cds/container/lazy_kvlist_nogc.h | 71 +++-- cds/container/lazy_kvlist_rcu.h | 82 ++++-- cds/container/lazy_list_nogc.h | 76 +++-- cds/container/lazy_list_rcu.h | 66 +++-- cds/container/michael_kvlist_nogc.h | 60 ++-- cds/container/michael_kvlist_rcu.h | 86 +++++- cds/container/michael_list_nogc.h | 60 ++-- cds/container/michael_list_rcu.h | 73 +++-- cds/container/michael_map.h | 61 ++-- cds/container/michael_map_nogc.h | 60 ++-- cds/container/michael_map_rcu.h | 66 +++-- .../details/multilevel_hashset_base.h | 3 + cds/intrusive/impl/lazy_list.h | 65 +++-- cds/intrusive/impl/michael_list.h | 39 ++- cds/intrusive/lazy_list_nogc.h | 81 ++++-- cds/intrusive/lazy_list_rcu.h | 75 +++-- cds/intrusive/michael_list_nogc.h | 64 +++-- cds/intrusive/michael_list_rcu.h | 52 ++-- projects/Win/vc12/cds.sln | 1 + projects/Win/vc12/unit-map-delodd.vcxproj | 27 +- projects/source.unit.map.mk | 1 + tests/test-hdr/list/hdr_intrusive_lazy.h | 134 ++++----- tests/test-hdr/list/hdr_intrusive_michael.h | 104 +++---- tests/test-hdr/list/hdr_lazy.h | 100 +++---- tests/test-hdr/list/hdr_lazy_kv.h | 160 +++++------ tests/test-hdr/list/hdr_michael.h | 82 +++--- tests/test-hdr/list/hdr_michael_kv.h | 100 +++---- tests/unit/map2/CMakeLists.txt | 1 + tests/unit/map2/map_defs.h | 167 +++++------ tests/unit/map2/map_delodd.cpp | 32 +-- tests/unit/map2/map_delodd.h | 261 +++++++++++------- tests/unit/map2/map_delodd_michael.cpp | 11 +- .../map2/map_delodd_multilevel_hashmap.cpp | 12 + tests/unit/map2/map_type_michael.h | 215 ++++++++------- tests/unit/map2/map_type_multilevel_hashmap.h | 61 ++++ 41 files changed, 1806 insertions(+), 1095 deletions(-) create mode 100644 tests/unit/map2/map_delodd_multilevel_hashmap.cpp create mode 100644 tests/unit/map2/map_type_multilevel_hashmap.h diff --git a/cds/container/details/multilevel_hashmap_base.h b/cds/container/details/multilevel_hashmap_base.h index 7a3a7498..c9fcaaa5 100644 --- a/cds/container/details/multilevel_hashmap_base.h +++ b/cds/container/details/multilevel_hashmap_base.h @@ -12,6 +12,9 @@ namespace cds { namespace container { /** @ingroup cds_nonintrusive_helper */ namespace multilevel_hashmap { + //@cond + using cds::intrusive::multilevel_hashset::implementation_tag; + //@endcond /// \p MultiLevelHashMap internal statistics, see cds::intrusive::multilevel_hashset::stat template diff --git a/cds/container/details/multilevel_hashset_base.h b/cds/container/details/multilevel_hashset_base.h index f6656aff..cb804e4b 100644 --- a/cds/container/details/multilevel_hashset_base.h +++ b/cds/container/details/multilevel_hashset_base.h @@ -11,6 +11,9 @@ namespace cds { namespace container { /** @ingroup cds_nonintrusive_helper */ namespace multilevel_hashset { + //@cond + using cds::intrusive::multilevel_hashset::implementation_tag; + //@endcond /// Hash accessor option /** diff --git a/cds/container/impl/lazy_kvlist.h b/cds/container/impl/lazy_kvlist.h index cf26ec61..541e8534 100644 --- a/cds/container/impl/lazy_kvlist.h +++ b/cds/container/impl/lazy_kvlist.h @@ -421,36 +421,46 @@ namespace cds { namespace container { return emplace_at( head(), std::forward(args)... ); } - /// Ensures that the \p key exists in the list + /// Updates data by \p key /** - The operation performs inserting or changing data with lock-free manner. + The operation performs inserting or replacing the element with lock-free manner. If the \p key not found in the list, then the new item created from \p key - is inserted into the list (note that in this case the \p key_type should be - constructible from type \p K). - Otherwise, the functor \p func is called with item found. - The functor signature is: + will be inserted iff \p bAllowInsert 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, the functor \p func is called with item found. + + The functor \p Func signature is: \code struct my_functor { void operator()( bool bNew, value_type& item ); }; \endcode - with arguments: - \p bNew - \p true if the item has been inserted, \p false otherwise - - \p item - item of the list + - \p item - the item found or inserted - The functor may change any fields of the \p item.second that is \p mapped_type. + The functor may change any fields of the \p item.second of \p mapped_type; + during \p func call \p item is locked so it is safe to modify the item in + multi-threaded environment. Returns std::pair where \p first is true if operation is successfull, \p second is true if new item has been added or \p false if the item with \p key - already is in the list. + already exists. */ template + std::pair update( const K& key, Func f, bool bAllowInsert = true ) + { + return update_at( head(), key, f, bAllowInsert ); + } + //@cond + // Deprecated + template std::pair ensure( const K& key, Func f ) { - return ensure_at( head(), key, f ); + return update( key, f, true ); } + //@endcond /// Deletes \p key from the list /** \anchor cds_nonintrusive_LazyKVList_hp_erase_val @@ -562,30 +572,45 @@ namespace cds { namespace container { return gp; } - /// Finds the key \p key - /** \anchor cds_nonintrusive_LazyKVList_hp_find_val + /// Checks whether the list contains \p key + /** The function searches the item with key equal to \p key - and returns \p true if it is found, and \p false otherwise + and returns \p true if it is found, and \p false otherwise. */ template - bool find( Q const& key ) + bool contains( Q const& key ) { return find_at( head(), key, intrusive_key_comparator() ); } + //@cond + // Deprecated + template + bool find( Q const& key ) + { + return contains( key ); + } + //@endcond - /// Finds the key \p val using \p pred predicate for searching + /// Checks whether the map contains \p key using \p pred predicate for searching /** - The function is an analog of \ref cds_nonintrusive_LazyKVList_hp_find_val "find(Q const&)" - but \p pred is used for key comparing. + The function is an analog of contains( key ) but \p pred is used for key comparing. \p Less functor has the interface like \p std::less. - \p pred must imply the same element order as the comparator used for building the list. + \p Less must imply the same element order as the comparator used for building the list. */ template - bool find_with( Q const& key, Less pred ) + bool contains( Q const& key, Less pred ) { CDS_UNUSED( pred ); return find_at( head(), key, typename maker::template less_wrapper::type() ); } + //@cond + // Deprecated + template + bool find_with( Q const& key, Less pred ) + { + return contains( key, pred ); + } + //@endcond /// Finds the key \p key and performs an action with it /** \anchor cds_nonintrusive_LazyKVList_hp_find_func @@ -766,12 +791,13 @@ namespace cds { namespace container { } template - std::pair ensure_at( head_type& refHead, const K& key, Func f ) + std::pair update_at( head_type& refHead, const K& key, Func f, bool bAllowInsert ) { scoped_node_ptr pNode( alloc_node( key )); - std::pair ret = base_class::ensure_at( &refHead, *pNode, - [&f]( bool bNew, node_type& node, node_type& ){ f( bNew, node.m_Data ); }); + std::pair ret = base_class::update_at( &refHead, *pNode, + [&f]( bool bNew, node_type& node, node_type& ){ f( bNew, node.m_Data ); }, + bAllowInsert ); if ( ret.first && ret.second ) pNode.release(); diff --git a/cds/container/impl/lazy_list.h b/cds/container/impl/lazy_list.h index 1e13589e..c3a6f67d 100644 --- a/cds/container/impl/lazy_list.h +++ b/cds/container/impl/lazy_list.h @@ -386,36 +386,46 @@ namespace cds { namespace container { return emplace_at( head(), std::forward(args)... ); } - /// Ensures that the \p key exists in the list + /// Updates data by \p key /** - The operation performs inserting or changing data with lock-free manner. + The operation performs inserting or replacing the element with lock-free manner. If the \p key not found in the list, then the new item created from \p key - is inserted into the list. Otherwise, the functor \p f is called with the item found. - \p Func signature is: + will be inserted iff \p bAllowInsert is \p true. + Otherwise, if \p key is found, the functor \p func is called with item found. + + The functor \p Func signature is: \code struct my_functor { - void operator()( bool bNew, value_type& item, const Q& key ); + void operator()( bool bNew, value_type& item, Q const& val ); }; \endcode with arguments: - \p bNew - \p true if the item has been inserted, \p false otherwise - - \p item - an item of the list - - \p key - argument \p key passed into the \p %ensure() function + - \p item - item of the list + - \p val - argument \p key passed into the \p %update() function - The functor may change non-key fields of the \p item. - When \p func is called it has exclusive access to the item. + The functor may change non-key fields of the \p item; + during \p func call \p item is locked so it is safe to modify the item in + multi-threaded environment. Returns std::pair where \p first is true if operation is successfull, \p second is true if new item has been added or \p false if the item with \p key - already is in the list. + already exists. */ template + std::pair update( Q const& key, Func func, bool bAllowInsert = true ) + { + return update_at( head(), key, func, bAllowInsert ); + } + //@cond + template std::pair ensure( Q const& key, Func f ) { - return ensure_at( head(), key, f ); + return update( key, f, true ); } + //@endcond /// Deletes \p key from the list /** \anchor cds_nonintrusive_LazyList_hp_erase_val @@ -538,31 +548,45 @@ namespace cds { namespace container { return gp; } - /// Finds the key \p key - /** \anchor cds_nonintrusive_LazyList_hp_find_val + /// Checks whether the list contains \p key + /** The function searches the item with key equal to \p key - and returns \p true if it is found, and \p false otherwise + and returns \p true if it is found, and \p false otherwise. */ template - bool find( Q const& key ) + bool contains( Q const& key ) { return find_at( head(), key, intrusive_key_comparator() ); } + //@cond + // Deprecated, use contains() + template + bool find( Q const& key ) + { + return contains( key ); + } + //@endcond - /// Finds the key \p key using \p pred predicate for searching + /// Checks whether the list contains \p key using \p pred predicate for searching /** - The function is an analog of \ref cds_nonintrusive_LazyList_hp_find_val "find(Q const&)" - but \p pred is used for key comparing. + The function is an analog of contains( key ) but \p pred is used for key comparing. \p Less functor has the interface like \p std::less. \p pred must imply the same element order as the comparator used for building the list. */ template - bool find_with( Q const& key, Less pred ) + bool contains( Q const& key, Less pred ) { CDS_UNUSED( pred ); return find_at( head(), key, typename maker::template less_wrapper::type() ); } - + //@cond + // Deprecated, use contains() + template + bool find_with( Q const& key, Less pred ) + { + return contains( key, pred ); + } + //@endcond /// Finds the key \p key and performs an action with it /** \anchor cds_nonintrusive_LazyList_hp_find_func The function searches an item with key equal to \p key and calls the functor \p f for the item found. @@ -748,12 +772,13 @@ namespace cds { namespace container { } template - std::pair ensure_at( head_type& refHead, const Q& key, Func f ) + std::pair update_at( head_type& refHead, const Q& key, Func f, bool bAllowInsert ) { scoped_node_ptr pNode( alloc_node( key )); - std::pair ret = base_class::ensure_at( &refHead, *pNode, - [&f, &key](bool bNew, node_type& node, node_type&){f( bNew, node_to_value(node), key ); }); + std::pair ret = base_class::update_at( &refHead, *pNode, + [&f, &key](bool bNew, node_type& node, node_type&){f( bNew, node_to_value(node), key );}, + bAllowInsert ); if ( ret.first && ret.second ) pNode.release(); diff --git a/cds/container/impl/michael_kvlist.h b/cds/container/impl/michael_kvlist.h index 3c8b95de..229453ab 100644 --- a/cds/container/impl/michael_kvlist.h +++ b/cds/container/impl/michael_kvlist.h @@ -404,28 +404,24 @@ namespace cds { namespace container { return insert_with_at( head(), key, func ); } - /// Ensures that the \p key exists in the list + /// Updates data by \p key /** - The operation performs inserting or changing data with lock-free manner. + The operation performs inserting or replacing the element with lock-free manner. If the \p key not found in the list, then the new item created from \p key - is inserted into the list (note that in this case the \p key_type should be - copy-constructible from type \p K). - Otherwise, the functor \p func is called with item found. - The functor \p Func may be a function with signature: - \code - void func( bool bNew, value_type& item ); - \endcode - or a functor: + will be inserted iff \p bAllowInsert 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, the functor \p func is called with item found. + + The functor \p Func signature is: \code struct my_functor { void operator()( bool bNew, value_type& item ); }; \endcode - with arguments: - \p bNew - \p true if the item has been inserted, \p false otherwise - - \p item - item of the list + - \p item - the item found or inserted The functor may change any fields of the \p item.second of \p mapped_type; however, \p func must guarantee that during changing no any other modifications @@ -433,15 +429,23 @@ namespace cds { namespace container { Returns std::pair where \p first is true if operation is successfull, \p second is true if new item has been added or \p false if the item with \p key - already is in the list. + already exists. @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ template - std::pair ensure( const K& key, Func f ) + std::pair update( K const& key, Func f, bool bAllowInsert = true ) + { + return update_at( head(), key, f, bAllowInsert ); + } + //@cond + // Deprecated + template + std::pair ensure( K const& key, Func f ) { - return ensure_at( head(), key, f ); + return update( key, f, true ); } + //@endcond /// Inserts a new node using move semantics /** @@ -571,30 +575,46 @@ namespace cds { namespace container { return gp; } - /// Finds the key \p key - /** \anchor cds_nonintrusive_MichaelKVList_hp_find_val + /// Checks whether the list contains \p key + /** The function searches the item with key equal to \p key - and returns \p true if it is found, and \p false otherwise + and returns \p true if it is found, and \p false otherwise. */ template - bool find( Q const& key ) + bool contains( Q const& key ) { return find_at( head(), key, intrusive_key_comparator() ); } + //@cond + // Deprecated + template + bool find( Q const& key ) + { + return contains( key ); + } + //@endcond - /// Finds the key \p val using \p pred predicate for searching + /// Checks whether the map contains \p key using \p pred predicate for searching /** - The function is an analog of \ref cds_nonintrusive_MichaelKVList_hp_find_val "find(Q const&)" - but \p pred is used for key comparing. + The function is an analog of contains( key ) but \p pred is used for key comparing. \p Less functor has the interface like \p std::less. - \p pred must imply the same element order as the comparator used for building the list. + \p Less must imply the same element order as the comparator used for building the list. */ template - bool find_with( Q const& key, Less pred ) + bool contains( Q const& key, Less pred ) { CDS_UNUSED( pred ); return find_at( head(), key, typename maker::template less_wrapper::type() ); } + //@cond + // Deprecated + template + bool find_with( Q const& key, Less pred ) + { + CDS_UNUSED( pred ); + return contains( key, pred ); + } + //@endcond /// Finds the key \p key and performs an action with it /** \anchor cds_nonintrusive_MichaelKVList_hp_find_func @@ -758,12 +778,13 @@ namespace cds { namespace container { } template - std::pair ensure_at( head_type& refHead, const K& key, Func f ) + std::pair update_at( head_type& refHead, const K& key, Func f, bool bAllowInsert ) { scoped_node_ptr pNode( alloc_node( key )); - std::pair ret = base_class::ensure_at( refHead, *pNode, - [&f]( bool bNew, node_type& node, node_type& ){ f( bNew, node.m_Data ); }); + std::pair ret = base_class::update_at( refHead, *pNode, + [&f]( bool bNew, node_type& node, node_type& ){ f( bNew, node.m_Data ); }, + bAllowInsert ); if ( ret.first && ret.second ) pNode.release(); diff --git a/cds/container/impl/michael_list.h b/cds/container/impl/michael_list.h index aa3a7c8d..362f1f99 100644 --- a/cds/container/impl/michael_list.h +++ b/cds/container/impl/michael_list.h @@ -361,42 +361,48 @@ namespace cds { namespace container { return insert_at( head(), key, func ); } - /// Ensures that the \p key exists in the list + /// Updates data by \p key /** - The operation performs inserting or changing data with lock-free manner. + The operation performs inserting or replacing the element with lock-free manner. If the \p key not found in the list, then the new item created from \p key - is inserted into the list. Otherwise, the functor \p func is called with the item found. - The functor \p Func should be a function with signature: - \code - void func( bool bNew, value_type& item, const Q& val ); - \endcode - or a functor: + will be inserted iff \p bAllowInsert is \p true. + Otherwise, if \p key is found, the functor \p func is called with item found. + + The functor \p Func signature is: \code struct my_functor { - void operator()( bool bNew, value_type& item, const Q& val ); + void operator()( bool bNew, value_type& item, Q const& val ); }; \endcode with arguments: - \p bNew - \p true if the item has been inserted, \p false otherwise - \p item - item of the list - - \p val - argument \p key passed into the \p ensure function + - \p val - argument \p key passed into the \p %update() function The functor may change non-key fields of the \p item; however, \p func must guarantee that during changing no any other modifications could be made on this item by concurrent threads. Returns std::pair where \p first is true if operation is successfull, \p second is true if new item has been added or \p false if the item with \p key - already is in the list. + already exists. @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ template + std::pair update( Q const& key, Func func, bool bAllowInsert = true ) + { + return update_at( head(), key, func, bAllowInsert ); + } + //@cond + // Deprecated, use update() + template std::pair ensure( Q const& key, Func func ) { - return ensure_at( head(), key, func ); + return update( key, func ); } + //@endcond /// Inserts data of type \p value_type constructed with std::forward(args)... /** @@ -527,30 +533,45 @@ namespace cds { namespace container { return gp; } - /// Finds \p key - /** \anchor cds_nonintrusive_MichaelList_hp_find_val + /// Checks whether the list contains \p key + /** The function searches the item with key equal to \p key - and returns \p true if it is found, and \p false otherwise + and returns \p true if it is found, and \p false otherwise. */ template - bool find( Q const& key ) + bool contains( Q const& key ) { return find_at( head(), key, intrusive_key_comparator() ); } + //@cond + // Deprecated, use contains() + template + bool find( Q const& key ) + { + return contains( key ); + } + //@endcond - /// Finds \p key using \p pred predicate for searching + /// Checks whether the list contains \p key using \p pred predicate for searching /** - The function is an analog of \ref cds_nonintrusive_MichaelList_hp_find_val "find(Q const&)" - but \p pred is used for key comparing. + The function is an analog of contains( key ) but \p pred is used for key comparing. \p Less functor has the interface like \p std::less. \p pred must imply the same element order as the comparator used for building the list. */ template - bool find_with( Q const& key, Less pred ) + bool contains( Q const& key, Less pred ) { CDS_UNUSED( pred ); return find_at( head(), key, typename maker::template less_wrapper::type() ); } + //@cond + // Deprecated, use contains() + template + bool find_with( Q const& key, Less pred ) + { + return contains( key, pred ); + } + //@endcond /// Finds \p key and perform an action with it /** \anchor cds_nonintrusive_MichaelList_hp_find_func @@ -733,12 +754,13 @@ namespace cds { namespace container { } template - std::pair ensure_at( head_type& refHead, Q const& key, Func f ) + std::pair update_at( head_type& refHead, Q const& key, Func f, bool bAllowInsert ) { scoped_node_ptr pNode( alloc_node( key )); - std::pair ret = base_class::ensure_at( refHead, *pNode, - [&f, &key](bool bNew, node_type& node, node_type&){ f( bNew, node_to_value(node), key ); }); + std::pair ret = base_class::update_at( refHead, *pNode, + [&f, &key](bool bNew, node_type& node, node_type&){ f( bNew, node_to_value(node), key );}, + bAllowInsert ); if ( ret.first && ret.second ) pNode.release(); diff --git a/cds/container/lazy_kvlist_nogc.h b/cds/container/lazy_kvlist_nogc.h index 77d38897..0208637d 100644 --- a/cds/container/lazy_kvlist_nogc.h +++ b/cds/container/lazy_kvlist_nogc.h @@ -375,21 +375,30 @@ namespace cds { namespace container { return node_to_iterator( insert_with_at( head(), key, func )); } - /// Ensures that the key \p key exists in the list + /// Updates the item /** - The operation inserts new item if the key \p key is not found in the list. - Otherwise, the function returns an iterator that points to item found. + If \p key is not in the list and \p bAllowInsert is \p true, + the function inserts a new item. + Otherwise, the function returns an iterator pointing to the item found. Returns std::pair where \p first is an iterator pointing to item found or inserted, \p second is true if new item has been added or \p false if the item already is in the list. */ template - std::pair ensure( const K& key ) + std::pair update( const K& key, bool bAllowInsert = true ) { - std::pair< node_type *, bool > ret = ensure_at( head(), key ); + std::pair< node_type *, bool > ret = update_at( head(), key, bAllowInsert ); return std::make_pair( node_to_iterator( ret.first ), ret.second ); } + //@cond + // Deprecated, use update() + template + std::pair ensure( const K& key ) + { + return update( key, true ); + } + //@endcond /// Inserts data of type \ref mapped_type constructed with std::forward(args)... /** @@ -401,44 +410,66 @@ namespace cds { namespace container { return node_to_iterator( emplace_at( head(), std::forward(args)... )); } - /// Find the key \p key - /** \anchor cds_nonintrusive_LazyKVList_nogc_find + /// Checks whether the list contains \p key + /** The function searches the item with key equal to \p key and returns an iterator pointed to item found if the key is found, and \ref end() otherwise */ template - iterator find( Q const& key ) + iterator contains( Q const& key ) { return node_to_iterator( find_at( head(), key, intrusive_key_comparator() ) ); } + //@cond + // Deprecated, use contains() + template + iterator find( Q const& key ) + { + return contains( key ); + } + //@endcond - /// Finds the key \p val using \p pred predicate for searching (for ordered list only) + /// Checks whether the map contains \p key using \p pred predicate for searching (ordered list version) /** - The function is an analog of \ref cds_nonintrusive_LazyKVList_nogc_find "find(Q const&)" - but \p pred is used for key comparing. + The function is an analog of contains( key ) but \p pred is used for key comparing. \p Less functor has the interface like \p std::less. - \p pred must imply the same element order as the comparator used for building the list. + \p Less must imply the same element order as the comparator used for building the list. */ template - typename std::enable_if::type find_with( Q const& key, Less pred ) + typename std::enable_if::type contains( Q const& key, Less pred ) { CDS_UNUSED( pred ); return node_to_iterator( find_at( head(), key, typename maker::template less_wrapper::type() ) ); } + //@cond + // Deprecated, use contains() + template + typename std::enable_if::type find_with( Q const& key, Less pred ) + { + return contains( key, pred ); + } + //@endcond - /// Finds the key \p val using \p equal predicate for searching (for unordered list only) + /// Finds the key \p val using \p equal predicate for searching (unordered list version) /** - The function is an analog of \ref cds_nonintrusive_LazyKVList_nogc_find "find(Q const&)" - but \p equal is used for key comparing. + The function is an analog of contains( key ) but \p equal is used for key comparing. \p Equal functor has the interface like \p std::equal_to. */ template - typename std::enable_if::type find_with( Q const& key, Equal equal ) + typename std::enable_if::type contains( Q const& key, Equal equal ) { CDS_UNUSED( equal ); return node_to_iterator( find_at( head(), key, typename maker::template equal_to_wrapper::type() ) ); } + //@cond + // Deprecated, use contains() + template + typename std::enable_if::type find_with( Q const& key, Equal equal ) + { + return contains( key, equal ); + } + //@endcond /// Check if the list is empty bool empty() const @@ -507,12 +538,14 @@ namespace cds { namespace container { template - std::pair< node_type *, bool > ensure_at( head_type& refHead, const K& key ) + std::pair< node_type *, bool > update_at( head_type& refHead, const K& key, bool bAllowInsert ) { scoped_node_ptr pNode( alloc_node( key )); node_type * pItemFound = nullptr; - std::pair ret = base_class::ensure_at( &refHead, *pNode, [&pItemFound](bool, node_type& item, node_type&){ pItemFound = &item; } ); + std::pair ret = base_class::update_at( &refHead, *pNode, + [&pItemFound](bool, node_type& item, node_type&){ pItemFound = &item; }, + bAllowInsert ); if ( ret.first && ret.second ) pNode.release(); diff --git a/cds/container/lazy_kvlist_rcu.h b/cds/container/lazy_kvlist_rcu.h index c805ac02..2bb6eaca 100644 --- a/cds/container/lazy_kvlist_rcu.h +++ b/cds/container/lazy_kvlist_rcu.h @@ -411,44 +411,48 @@ namespace cds { namespace container { return emplace_at( head(), std::forward(args)... ); } - /// Ensures that the \p key exists in the list + /// Updates data by \p key /** - The operation performs inserting or changing data with lock-free manner. + The operation performs inserting or replacing the element with lock-free manner. If the \p key not found in the list, then the new item created from \p key - is inserted into the list (note that in this case the \ref key_type should be - copy-constructible from type \p K). - Otherwise, the functor \p func is called with item found. - The functor \p Func may be a function with signature: - \code - void func( bool bNew, value_type& item ); - \endcode - or a functor: + will be inserted iff \p bAllowInsert 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, the functor \p func is called with item found. + + The functor \p Func signature is: \code struct my_functor { void operator()( bool bNew, value_type& item ); }; \endcode - with arguments: - \p bNew - \p true if the item has been inserted, \p false otherwise - - \p item - item of the list + - \p item - the item found or inserted - The functor may change any fields of the \p item.second of type \p mapped_type. + The functor may change any fields of the \p item.second of \p mapped_type; + during \p func call \p item is locked so it is safe to modify the item in + multi-threaded environment. - The function makes RCU lock internally. + The function applies RCU lock internally. Returns std::pair where \p first is true if operation is successfull, \p second is true if new item has been added or \p false if the item with \p key - already is in the list. - - @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" + already exists. */ template + std::pair update( const K& key, Func func, bool bAllowInsert = true ) + { + return update_at( head(), key, func, bAllowInsert ); + } + //@cond + // Deprecated + template std::pair ensure( const K& key, Func f ) { - return ensure_at( head(), key, f ); + return update( head(), key, f, true ); } + //@endcond /// Deletes \p key from the list /** \anchor cds_nonintrusive_LazyKVList_rcu_erase @@ -573,32 +577,49 @@ namespace cds { namespace container { return exempt_ptr( extract_at( head(), key, typename maker::template less_wrapper::type() )); } - /// Finds the key \p key - /** \anchor cds_nonintrusive_LazyKVList_rcu_find_val + /// Checks whether the list contains \p key + /** The function searches the item with key equal to \p key - and returns \p true if it is found, and \p false otherwise + and returns \p true if it is found, and \p false otherwise. The function applies RCU lock internally. */ template - bool find( Q const& key ) const + bool contains( Q const& key ) const { return find_at( head(), key, intrusive_key_comparator() ); } + //@cond + // Deprecated + template + bool find( Q const& key ) const + { + return contains( key ); + } + //@endcond - /// Finds the key \p val using \p pred predicate for searching + /// Checks whether the map contains \p key using \p pred predicate for searching /** - The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_find_val "find(Q const&)" - but \p pred is used for key comparing. + The function is an analog of contains( key ) but \p pred is used for key comparing. \p Less functor has the interface like \p std::less. - \p pred must imply the same element order as the comparator used for building the list. + \p Less must imply the same element order as the comparator used for building the list. + + The function applies RCU lock internally. */ template - bool find_with( Q const& key, Less pred ) const + bool contains( Q const& key, Less pred ) const { CDS_UNUSED( pred ); return find_at( head(), key, typename maker::template less_wrapper::type() ); } + //@cond + // Deprecated + template + bool find_with( Q const& key, Less pred ) const + { + return contains( key, pred ); + } + //@endcond /// Finds the key \p key and performs an action with it /** \anchor cds_nonintrusive_LazyKVList_rcu_find_func @@ -772,12 +793,13 @@ namespace cds { namespace container { } template - std::pair ensure_at( head_type& refHead, const K& key, Func f ) + std::pair update_at( head_type& refHead, const K& key, Func f, bool bAllowInsert ) { scoped_node_ptr pNode( alloc_node( key )); - std::pair ret = base_class::ensure_at( &refHead, *pNode, - [&f]( bool bNew, node_type& node, node_type& ){ f( bNew, node.m_Data ); }); + std::pair ret = base_class::update_at( &refHead, *pNode, + [&f]( bool bNew, node_type& node, node_type& ){ f( bNew, node.m_Data ); }, + bAllowInsert ); if ( ret.first && ret.second ) pNode.release(); diff --git a/cds/container/lazy_list_nogc.h b/cds/container/lazy_list_nogc.h index 979d47ce..5dc5de09 100644 --- a/cds/container/lazy_list_nogc.h +++ b/cds/container/lazy_list_nogc.h @@ -296,60 +296,91 @@ namespace cds { namespace container { return node_to_iterator( emplace_at( head(), std::forward(args)... )); } - /// Ensures that the item \p val exists in the list + /// Updates the item /** - The operation inserts new item if the key \p val is not found in the list. - Otherwise, the function returns an iterator that points to item found. + If \p key is not in the list and \p bAllowInsert is \p true, + the function inserts a new item. + Otherwise, the function returns an iterator pointing to the item found. Returns std::pair where \p first is an iterator pointing to - item found or inserted, \p second is \p true if new item has been added or \p false if the item + item found or inserted, \p second is true if new item has been added or \p false if the item already is in the list. */ template - std::pair ensure( Q const& val ) + std::pair update( Q const& val, bool bAllowInsert = true ) { - std::pair< node_type *, bool > ret = ensure_at( head(), val ); + std::pair< node_type *, bool > ret = update_at( head(), val, bAllowInsert ); return std::make_pair( node_to_iterator( ret.first ), ret.second ); } + //@cond + // Deprecated, use update() + template + std::pair ensure( Q const& val ) + { + return update( val, true ); + } + //@endcond - /// Find the key \p val - /** \anchor cds_nonintrusive_LazyList_nogc_find - The function searches the item with key equal to \p val + /// Checks whether the list contains \p key + /** + The function searches the item with key equal to \p key and returns an iterator pointed to item found if the key is found, and \ref end() otherwise */ template - iterator find( Q const& key ) + iterator contains( Q const& key ) { return node_to_iterator( find_at( head(), key, intrusive_key_comparator() )); } + //@cond + // Deprecated, use contains() + template + iterator find( Q const& key ) + { + return contains( key ); + } + //@endcond - /// Finds the key \p val using \p pred predicate for searching (only for ordered list) + /// Checks whether the map contains \p key using \p pred predicate for searching (ordered list version) /** - The function is an analog of \ref cds_nonintrusive_LazyList_nogc_find "find(Q const&)" - but \p pred is used for key comparing. + The function is an analog of contains( key ) but \p pred is used for key comparing. \p Less functor has the interface like \p std::less. - \p pred must imply the same element order as the comparator used for building the list. + \p Less must imply the same element order as the comparator used for building the list. */ template - typename std::enable_if::type find_with( Q const& key, Less pred ) + typename std::enable_if::type contains( Q const& key, Less pred ) { CDS_UNUSED( pred ); return node_to_iterator( find_at( head(), key, typename maker::template less_wrapper::type() )); } + //@cond + // Deprecated, use contains() + template + typename std::enable_if::type find_with( Q const& key, Less pred ) + { + return contains( key, pred ); + } + //@endcond - /// Finds the key \p val using \p equal predicate for searching (only for unordered list) + /// Finds the key \p val using \p equal predicate for searching (unordered list version) /** - The function is an analog of \ref cds_nonintrusive_LazyList_nogc_find "find(Q const&)" - but \p pred is used for key comparing. + The function is an analog of contains( key ) but \p equal is used for key comparing. \p Equal functor has the interface like \p std::equal_to. */ template - typename std::enable_if::type find_with( Q const& key, Equal equal ) + typename std::enable_if::type contains( Q const& key, Equal equal ) { CDS_UNUSED( equal ); return node_to_iterator( find_at( head(), key, typename maker::template equal_to_wrapper::type() )); } + //@cond + // Deprecated, use contains() + template + typename std::enable_if::type find_with( Q const& key, Equal equal ) + { + return contains( key, equal ); + } + //@endcond /// Check if the list is empty bool empty() const @@ -401,13 +432,14 @@ namespace cds { namespace container { } template - std::pair< node_type *, bool > ensure_at( head_type& refHead, Q const& val ) + std::pair< node_type *, bool > update_at( head_type& refHead, Q const& val, bool bAllowInsert ) { scoped_node_ptr pNode( alloc_node( val )); node_type * pItemFound = nullptr; - std::pair ret = base_class::ensure_at( &refHead, *pNode, - [&pItemFound](bool, node_type& item, node_type&){ pItemFound = &item; }); + std::pair ret = base_class::update_at( &refHead, *pNode, + [&pItemFound](bool, node_type& item, node_type&){ pItemFound = &item; }, + bAllowInsert ); assert( pItemFound != nullptr ); if ( ret.first && ret.second ) diff --git a/cds/container/lazy_list_rcu.h b/cds/container/lazy_list_rcu.h index 67f9b292..91d1284a 100644 --- a/cds/container/lazy_list_rcu.h +++ b/cds/container/lazy_list_rcu.h @@ -384,12 +384,14 @@ namespace cds { namespace container { return emplace_at( head(), std::forward(args)... ); } - /// Ensures that the \p key exists in the list + /// Updates data by \p key /** - The operation performs inserting or changing data with lock-free manner. + The operation performs inserting or replacing the element with lock-free manner. If the \p key not found in the list, then the new item created from \p key - is inserted into the list. Otherwise, the functor \p func is called with the item found. + will be inserted iff \p bAllowInsert is \p true. + Otherwise, if \p key is found, the functor \p func is called with item found. + The functor \p Func signature is: \code struct my_functor { @@ -400,23 +402,31 @@ namespace cds { namespace container { with arguments: - \p bNew - \p true if the item has been inserted, \p false otherwise - \p item - item of the list - - \p val - argument \p key passed into the \p ensure function + - \p val - argument \p key passed into the \p %update() function - The functor may change non-key fields of the \p item. + The functor may change non-key fields of the \p item; + during \p func call \p item is locked so it is safe to modify the item in + multi-threaded environment. The function applies RCU lock internally. Returns std::pair where \p first is true if operation is successfull, \p second is true if new item has been added or \p false if the item with \p key - already is in the list. - - @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" + already exists. */ template + std::pair update( Q const& key, Func func, bool bAllowInsert = true ) + { + return update_at( head(), key, func, bAllowInsert ); + } + //@cond + // Deprecated, use update() + template std::pair ensure( Q const& key, Func f ) { - return ensure_at( head(), key, f ); + return update( key, f, true ); } + //@endcond /// Deletes \p key from the list /** \anchor cds_nonintrusive_LazyList_rcu_erase @@ -551,32 +561,47 @@ namespace cds { namespace container { return exempt_ptr( extract_at( head(), key, typename maker::template less_wrapper::type())); } - /// Finds the key \p key - /** \anchor cds_nonintrusive_LazyList_rcu_find_val + /// Checks whether the list contains \p key + /** The function searches the item with key equal to \p key and returns \p true if it is found, and \p false otherwise. - The function makes RCU lock internally. + The function applies RCU lock internally. */ template - bool find( Q const& key ) const + bool contains( Q const& key ) const { return find_at( head(), key, intrusive_key_comparator() ); } + //@cond + // Deprecated, use contains() + template + bool find( Q const& key ) const + { + return contains( key ); + } + //@endcond - /// Finds the key \p key using \p pred predicate for searching + /// Checks whether the list contains \p key using \p pred predicate for searching /** - The function is an analog of \ref cds_nonintrusive_LazyList_rcu_find_val "find(Q const&)" - but \p pred is used for key comparing. + The function is an analog of contains( key ) but \p pred is used for key comparing. \p Less functor has the interface like \p std::less. \p pred must imply the same element order as the comparator used for building the list. */ template - bool find_with( Q const& key, Less pred ) const + bool contains( Q const& key, Less pred ) const { CDS_UNUSED( pred ); return find_at( head(), key, typename maker::template less_wrapper::type() ); } + //@cond + // Deprecated, use contains() + template + bool find_with( Q const& key, Less pred ) const + { + return contains( key, pred ); + } + //@endcond /// Finds the key \p key and performs an action with it /** \anchor cds_nonintrusive_LazyList_rcu_find_func @@ -762,12 +787,13 @@ namespace cds { namespace container { } template - std::pair ensure_at( head_type& refHead, Q const& key, Func f ) + std::pair update_at( head_type& refHead, Q const& key, Func f, bool bAllowInsert ) { scoped_node_ptr pNode( alloc_node( key )); - std::pair ret = base_class::ensure_at( &refHead, *pNode, - [&f, &key](bool bNew, node_type& node, node_type&){f( bNew, node_to_value(node), key ); }); + std::pair ret = base_class::update_at( &refHead, *pNode, + [&f, &key](bool bNew, node_type& node, node_type&){f( bNew, node_to_value(node), key );}, + bAllowInsert ); if ( ret.first && ret.second ) pNode.release(); diff --git a/cds/container/michael_kvlist_nogc.h b/cds/container/michael_kvlist_nogc.h index bc5f3d84..ec55b9c6 100644 --- a/cds/container/michael_kvlist_nogc.h +++ b/cds/container/michael_kvlist_nogc.h @@ -391,21 +391,30 @@ namespace cds { namespace container { return node_to_iterator( insert_with_at( head(), key, func )); } - /// Ensures that the key \p key exists in the list + /// Updates the item /** - The operation inserts new item if the key \p key is not found in the list. - Otherwise, the function returns an iterator that points to item found. + If \p key is not in the list and \p bAllowInsert is \p true, + the function inserts a new item. + Otherwise, the function returns an iterator pointing to the item found. - Returns std::pair where \p first is an iterator pointing to + Returns std::pair where \p first is an iterator pointing to item found or inserted, \p second is true if new item has been added or \p false if the item already is in the list. */ template - std::pair ensure( const K& key ) + std::pair update( K const& key, bool bAllowInsert = true ) { - std::pair< node_type *, bool > ret = ensure_at( head(), key ); + std::pair< node_type *, bool > ret = update_at( head(), key, bAllowInsert ); return std::make_pair( node_to_iterator( ret.first ), ret.second ); } + //@cond + // Deprecated, use update() + template + std::pair ensure( K const& key ) + { + return update( key ); + } + //@endcond /// Inserts data of type \ref mapped_type constructed with std::forward(args)... /** @@ -417,32 +426,45 @@ namespace cds { namespace container { return node_to_iterator( emplace_at( head(), std::forward(key), std::forward(args)... )); } - /// Find the key \p key - /** \anchor cds_nonintrusive_MichaelKVList_nogc_find - + /// Checks whether the list contains \p key + /** The function searches the item with key equal to \p key - and returns an iterator pointed to item found if the key is found, - and \ref end() otherwise + and returns an iterator pointed to item found and \ref end() otherwise */ template - iterator find( Q const& key ) + iterator contains( Q const& key ) { return node_to_iterator( find_at( head(), key, intrusive_key_comparator() ) ); } + //@cond + // Deprecated, use contains() + template + iterator find( Q const& key ) + { + return contains( key ); + } + //@endcond - /// Finds the key \p key using \p pred predicate for searching + /// Checks whether the list contains \p key using \p pred predicate for searching /** - The function is an analog of \ref cds_nonintrusive_MichaelKVList_nogc_find "find(Q const&)" - but \p pred is used for key comparing. + The function is an analog of contains( key ) but \p pred is used for key comparing. \p Less functor has the interface like \p std::less. \p pred must imply the same element order as the comparator used for building the list. */ template - iterator find_with( Q const& key, Less pred ) + iterator contains( Q const& key, Less pred ) { CDS_UNUSED( pred ); return node_to_iterator( find_at( head(), key, typename maker::template less_wrapper::type() ) ); } + //@cond + // Deprecated, use contains() + template + iterator find_with( Q const& key, Less pred ) + { + return contains( key, pred ); + } + //@endcond /// Check if the list is empty bool empty() const @@ -505,12 +527,14 @@ namespace cds { namespace container { } template - std::pair< node_type *, bool > ensure_at( head_type& refHead, const K& key ) + std::pair< node_type *, bool > update_at( head_type& refHead, const K& key, bool bAllowInsert ) { scoped_node_ptr pNode( alloc_node( key )); node_type * pItemFound = nullptr; - std::pair ret = base_class::ensure_at( refHead, *pNode, [&pItemFound](bool, node_type& item, node_type&){ pItemFound = &item; }); + std::pair ret = base_class::update_at( refHead, *pNode, + [&pItemFound](bool, node_type& item, node_type&){ pItemFound = &item; }, + bAllowInsert ); assert( pItemFound != nullptr ); if ( ret.first && ret.second ) diff --git a/cds/container/michael_kvlist_rcu.h b/cds/container/michael_kvlist_rcu.h index 3efaf063..dc212d71 100644 --- a/cds/container/michael_kvlist_rcu.h +++ b/cds/container/michael_kvlist_rcu.h @@ -450,11 +450,50 @@ namespace cds { namespace container { @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ + /// 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 list, then the new item created from \p key + will be inserted iff \p bAllowInsert 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, the functor \p func is called with item found. + + The functor \p Func signature is: + \code + struct my_functor { + void operator()( bool bNew, value_type& item ); + }; + \endcode + with arguments: + - \p bNew - \p true if the item has been inserted, \p false otherwise + - \p item - the item found or inserted + + The functor may change any fields of the \p item.second that is \ref mapped_type; + however, \p func must guarantee that during changing no any other modifications + could be made on this item by concurrent threads. + + The function applies RCU lock internally. + + Returns std::pair where \p first is true if operation is successfull, + \p second is true if new item has been added or \p false if the item with \p key + already exists. + + @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" + */ + template + std::pair update( const K& key, Func func, bool bAllowInsert = true ) + { + return update_at( head(), key, func, bAllowInsert ); + } + //@cond + // Deprecated template std::pair ensure( const K& key, Func f ) { - return ensure_at( head(), key, f ); + return update( key, f, true ); } + //@endcond /// Inserts data of type \ref mapped_type constructed with std::forward(args)... /** @@ -591,33 +630,49 @@ namespace cds { namespace container { return exempt_ptr( extract_at( head(), key, typename maker::template less_wrapper::type() )); } - /// Finds the key \p key - /** \anchor cds_nonintrusive_MichaelKVList_rcu_find_val - + /// Checks whether the list contains \p key + /** The function searches the item with key equal to \p key - and returns \p true if it is found, and \p false otherwise + and returns \p true if it is found, and \p false otherwise. - The function makes RCU lock internally. + The function applies RCU lock internally. */ template - bool find( Q const& key ) + bool contains( Q const& key ) { return find_at( head(), key, intrusive_key_comparator() ); } + //@cond + // Deprecated + template + bool find( Q const& key ) + { + return contains( key ); + } + //@endcond - /// Finds the key \p key using \p pred predicate for searching + /// Checks whether the map contains \p key using \p pred predicate for searching /** - The function is an analog of \ref cds_nonintrusive_MichaelKVList_rcu_find_val "find(Q const&)" - but \p pred is used for key comparing. + The function is an analog of contains( key ) but \p pred is used for key comparing. \p Less functor has the interface like \p std::less. - \p pred must imply the same element order as the comparator used for building the list. + \p Less must imply the same element order as the comparator used for building the list. + + The function applies RCU lock internally. */ template - bool find_with( Q const& key, Less pred ) + bool contains( Q const& key, Less pred ) { CDS_UNUSED( pred ); return find_at( head(), key, typename maker::template less_wrapper::type() ); } + //@cond + // Deprecated + template + bool find_with( Q const& key, Less pred ) + { + return contains( key, pred ); + } + //@endcond /// Finds \p key and performs an action with it /** \anchor cds_nonintrusive_MichaelKVList_rcu_find_func @@ -782,12 +837,13 @@ namespace cds { namespace container { } template - std::pair ensure_at( head_type& refHead, const K& key, Func f ) + std::pair update_at( head_type& refHead, const K& key, Func f, bool bAllowInsert ) { scoped_node_ptr pNode( alloc_node( key )); - std::pair ret = base_class::ensure_at( refHead, *pNode, - [&f]( bool bNew, node_type& node, node_type& ){ f( bNew, node.m_Data ); }); + std::pair ret = base_class::update_at( refHead, *pNode, + [&f]( bool bNew, node_type& node, node_type& ){ f( bNew, node.m_Data ); }, + bAllowInsert ); if ( ret.first && ret.second ) pNode.release(); diff --git a/cds/container/michael_list_nogc.h b/cds/container/michael_list_nogc.h index 64af875f..a9c94b79 100644 --- a/cds/container/michael_list_nogc.h +++ b/cds/container/michael_list_nogc.h @@ -292,21 +292,30 @@ namespace cds { namespace container { return node_to_iterator( insert_at( head(), val ) ); } - /// Ensures that the item \p val exists in the list + /// Updates the item /** - The operation inserts new item if the key \p val is not found in the list. - Otherwise, the function returns an iterator that points to item found. + If \p key is not in the list and \p bAllowInsert is \p true, + the function inserts a new item. + Otherwise, the function returns an iterator pointing to the item found. - Returns std::pair where \p first is an iterator pointing to + Returns std::pair where \p first is an iterator pointing to item found or inserted, \p second is true if new item has been added or \p false if the item already is in the list. */ template - std::pair ensure( const Q& val ) + std::pair update( const Q& key, bool bAllowInsert = true ) { - std::pair< node_type *, bool > ret = ensure_at( head(), val ); + std::pair< node_type *, bool > ret = update_at( head(), key, bAllowInsert ); return std::make_pair( node_to_iterator( ret.first ), ret.second ); } + //@cond + // Deprecated, use update() + template + std::pair ensure( const Q& val ) + { + return update( val, true ); + } + //@endcond /// Inserts data of type \ref value_type constructed with std::forward(args)... /** @@ -318,31 +327,46 @@ namespace cds { namespace container { return node_to_iterator( emplace_at( head(), std::forward(args)... )); } - /// Find the key \p key - /** \anchor cds_nonintrusive_MichaelList_nogc_find_val + /// Checks whether the list contains \p key + /** The function searches the item with key equal to \p key and returns an iterator pointed to item found if the key is found, - and \p end() otherwise + and \ref end() otherwise */ template - iterator find( Q const& key ) + iterator contains( Q const& key ) { return node_to_iterator( find_at( head(), key, intrusive_key_comparator() )); } + //@cond + // Deprecated, ue contains() + template + iterator find( Q const& key ) + { + return contains( key ); + } + //@endcond - /// Finds the key \p key using \p pred predicate for searching + /// Checks whether the map contains \p key using \p pred predicate for searching /** - The function is an analog of \ref cds_nonintrusive_MichaelList_nogc_find_val "find(Q const&)" - but \p pred is used for key comparing. + The function is an analog of contains( key ) but \p pred is used for key comparing. \p Less functor has the interface like \p std::less. - \p pred must imply the same element order as the comparator used for building the list. + \p Less must imply the same element order as the comparator used for building the list. */ template - iterator find_with( Q const& key, Less pred ) + iterator contains( Q const& key, Less pred ) { CDS_UNUSED( pred ); return node_to_iterator( find_at( head(), key, typename maker::template less_wrapper::type() ) ); } + //@cond + // Deprecated, use contains() + template + iterator find_with( Q const& key, Less pred ) + { + return contains( key, pred ); + } + //@endcond /// Check if the list is empty bool empty() const @@ -388,12 +412,14 @@ namespace cds { namespace container { } template - std::pair< node_type *, bool > ensure_at( head_type& refHead, const Q& val ) + std::pair< node_type *, bool > update_at( head_type& refHead, const Q& val, bool bAllowInsert ) { scoped_node_ptr pNode( alloc_node( val )); node_type * pItemFound = nullptr; - std::pair ret = base_class::ensure_at( refHead, *pNode, [&pItemFound](bool, node_type& item, node_type&) { pItemFound = &item; }); + std::pair ret = base_class::update_at( refHead, *pNode, + [&pItemFound](bool, node_type& item, node_type&) { pItemFound = &item; }, + bAllowInsert ); assert( pItemFound != nullptr ); if ( ret.first && ret.second ) diff --git a/cds/container/michael_list_rcu.h b/cds/container/michael_list_rcu.h index d4558ddf..9cfaa1b7 100644 --- a/cds/container/michael_list_rcu.h +++ b/cds/container/michael_list_rcu.h @@ -388,44 +388,50 @@ namespace cds { namespace container { return insert_at( head(), key, func ); } - /// Ensures that the \p key exists in the list + /// Updates data by \p key /** - The operation performs inserting or changing data with lock-free manner. + The operation performs inserting or replacing the element with lock-free manner. If the \p key not found in the list, then the new item created from \p key - is inserted into the list. Otherwise, the functor \p func is called with the item found. - The functor \p Func should be a function with signature: - \code - void func( bool bNew, value_type& item, const Q& val ); - \endcode - or a functor: + will be inserted iff \p bAllowInsert is \p true. + Otherwise, if \p key is found, the functor \p func is called with item found. + + The functor \p Func signature is: \code struct my_functor { - void operator()( bool bNew, value_type& item, const Q& val ); + void operator()( bool bNew, value_type& item, Q const& val ); }; \endcode with arguments: - \p bNew - \p true if the item has been inserted, \p false otherwise - \p item - item of the list - - \p val - argument \p key passed into the \p ensure function + - \p val - argument \p key passed into the \p %update() function The functor may change non-key fields of the \p item; however, \p func must guarantee that during changing no any other modifications could be made on this item by concurrent threads. - The function makes RCU lock internally. + The function applies RCU lock internally. Returns std::pair where \p first is true if operation is successfull, \p second is true if new item has been added or \p false if the item with \p key - already is in the list. + already exists. @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ template - std::pair ensure( Q const& key, Func f ) + std::pair update( Q const& key, Func func, bool bAllowInsert = true ) { - return ensure_at( head(), key, f ); + return update_at( head(), key, func, bAllowInsert ); + } + //@cond + // Deprecated, use update() + template + std::pair ensure( Q const& key, Func f ) + {1 + return update( key, f, true ); } + //@endcond /// Inserts data of type \ref value_type constructed from \p args /** @@ -570,32 +576,48 @@ namespace cds { namespace container { return exempt_ptr( extract_at( head(), key, typename maker::template less_wrapper::type() )); } - /// Finds the key \p key - /** \anchor cds_nonintrusive_MichaelList_rcu_find_val + /// Checks whether the list contains \p key + /** The function searches the item with key equal to \p key and returns \p true if it is found, and \p false otherwise. - The function makes RCU lock internally. + The function applies RCU lock internally. */ template - bool find( Q const& key ) + bool contains( Q const& key ) { return find_at( head(), key, intrusive_key_comparator() ); } + //@cond + // Deprecated, use contains() + template + bool find( Q const& key ) + { + return contains( key ); + } + //@endcond - /// Finds the key \p val using \p pred predicate for searching + /// Checks whether the list contains \p key using \p pred predicate for searching /** - The function is an analog of \ref cds_nonintrusive_MichaelList_rcu_find_val "find(Q const&)" - but \p pred is used for key comparing. + The function is an analog of contains( key ) but \p pred is used for key comparing. \p Less functor has the interface like \p std::less. \p pred must imply the same element order as the comparator used for building the list. */ template - bool find_with( Q const& key, Less pred ) + bool contains( Q const& key, Less pred ) { CDS_UNUSED( pred ); return find_at( head(), key, typename maker::template less_wrapper::type() ); } + //@cond + // Deprecatd, use contains() + template + bool find_with( Q const& key, Less pred ) + { + CDS_UNUSED( pred ); + return contains( key, pred ); + } + //@endcond /// Finds the key \p key and performs an action with it /** \anchor cds_nonintrusive_MichaelList_rcu_find_func @@ -774,12 +796,13 @@ namespace cds { namespace container { } template - std::pair ensure_at( head_type& refHead, Q const& key, Func f ) + std::pair update_at( head_type& refHead, Q const& key, Func f, bool bAllowInsert ) { scoped_node_ptr pNode( alloc_node( key )); - std::pair ret = base_class::ensure_at( refHead, *pNode, - [&f, &key](bool bNew, node_type& node, node_type&){ f( bNew, node_to_value(node), key ); }); + std::pair ret = base_class::update_at( refHead, *pNode, + [&f, &key](bool bNew, node_type& node, node_type&){ f( bNew, node_to_value(node), key );}, + bAllowInsert ); if ( ret.first && ret.second ) pNode.release(); diff --git a/cds/container/michael_map.h b/cds/container/michael_map.h index 7e3c8e63..da76d2f2 100644 --- a/cds/container/michael_map.h +++ b/cds/container/michael_map.h @@ -474,44 +474,54 @@ namespace cds { namespace container { return bRet; } - - /// Ensures that the \p key exists in the map + /// Updates data by \p key /** - The operation performs inserting or changing data with lock-free manner. + 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 - is inserted into the map (note that in this case the \p key_type should be - constructible from type \p K). - Otherwise, the functor \p func is called with item found. - The functor \p Func may signature is: + will be inserted into the map iff \p bAllowInsert 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, the functor \p func is called with item found. + + The functor \p Func signature is: \code struct my_functor { void operator()( bool bNew, value_type& item ); }; \endcode - with arguments: - \p bNew - \p true if the item has been inserted, \p false otherwise - - \p item - item of the list + - \p item - the item found or inserted The functor may change any fields of the \p item.second that is \p mapped_type. Returns std::pair where \p first is true if operation is successfull, \p second is true if new item has been added or \p false if the item with \p key - already is in the list. + already exists. @warning For \ref cds_nonintrusive_MichaelKVList_gc "MichaelKVList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting". \ref cds_nonintrusive_LazyKVList_gc "LazyKVList" provides exclusive access to inserted item and does not require any node-level synchronization. */ + template + std::pair update( K const& key, Func func, bool bAllowInsert = true ) + { + std::pair bRet = bucket( key ).update( key, func, bAllowInsert ); + if ( bRet.first && bRet.second ) + ++m_ItemCounter; + return bRet; + } + //@cond + // Deprecated template std::pair ensure( K const& key, Func func ) { - std::pair bRet = bucket( key ).ensure( key, func ); + std::pair bRet = bucket( key ).update( key, func, true ); if ( bRet.first && bRet.second ) ++m_ItemCounter; return bRet; } + //@endcond /// For key \p key inserts data of type \p mapped_type created from \p args /** @@ -689,29 +699,44 @@ namespace cds { namespace container { return bucket( key ).find_with( key, pred, f ); } - /// Finds the key \p key - /** \anchor cds_nonintrusive_MichaelMap_find_val + /// Checks whether the map contains \p key + /** The function searches the item with key equal to \p key and returns \p true if it is found, and \p false otherwise. */ template + bool contains( K const& key ) + { + return bucket( key ).contains( key ); + } + //@cond + // Deprecated + template bool find( K const& key ) { - return bucket( key ).find( key ); + return bucket( key ).contains( key ); } + //@endcond - /// Finds the key \p val using \p pred predicate for searching + /// Checks whether the map contains \p key using \p pred predicate for searching /** - The function is an analog of \ref cds_nonintrusive_MichaelMap_find_val "find(K const&)" - but \p pred is used for key comparing. + The function is an analog of contains( key ) but \p pred is used for key comparing. \p Less functor has the interface like \p std::less. \p Less must imply the same element order as the comparator used for building the map. */ template + bool contains( K const& key, Less pred ) + { + return bucket( key ).contains( key, pred ); + } + //@cond + // Deprecated + template bool find_with( K const& key, Less pred ) { - return bucket( key ).find_with( key, pred ); + return bucket( key ).contains( key, pred ); } + //@endcond /// Finds \p key and return the item found /** \anchor cds_nonintrusive_MichaelHashMap_hp_get diff --git a/cds/container/michael_map_nogc.h b/cds/container/michael_map_nogc.h index f30af09e..7ed7747c 100644 --- a/cds/container/michael_map_nogc.h +++ b/cds/container/michael_map_nogc.h @@ -395,12 +395,13 @@ namespace cds { namespace container { return end(); } - /// Ensures that the key \p key exists in the map + /// Updates the item /** - The operation inserts new item if the key \p key is not found in the map. - Otherwise, the function returns an iterator that points to item found. + If \p key is not in the list and \p bAllowInsert is \p true, + the function inserts a new item. + Otherwise, the function returns an iterator pointing to the item found. - Returns std::pair where \p first is an iterator pointing to + Returns std::pair where \p first is an iterator pointing to item found or inserted, \p second is true if new item has been added or \p false if the item already is in the list. @@ -409,54 +410,75 @@ namespace cds { namespace container { synchronization. */ template - std::pair ensure( const K& key ) + std::pair update( const K& key, bool bAllowInsert = true ) { bucket_type& refBucket = bucket( key ); - std::pair ret = refBucket.ensure( key ); + std::pair ret = refBucket.update( key, bAllowInsert ); if ( ret.second ) ++m_ItemCounter; return std::make_pair( iterator( ret.first, &refBucket, m_Buckets + bucket_count() ), ret.second ); } + //@cond + // Deprecated, use update() + template + std::pair ensure( K const& key ) + { + return update( key, true ); + } + //@endcond - /// Find the key \p key - /** \anchor cds_nonintrusive_MichaelMap_nogc_find - + /// Checks whether the map contains \p key + /** The function searches the item with key equal to \p key - and returns an iterator pointed to item found if the key is found, - and \ref end() otherwise + and returns an iterator pointed to item found and \ref end() otherwise */ template - iterator find( const K& key ) + iterator find( K const& key ) { bucket_type& refBucket = bucket( key ); - bucket_iterator it = refBucket.find( key ); + bucket_iterator it = refBucket.contains( key ); if ( it != refBucket.end() ) return iterator( it, &refBucket, m_Buckets + bucket_count() ); return end(); } + //@cond + // Deprecated, use contains() + template + iterator find( K const& key ) + { + return contains( key ); + } + //@endcond - /// Finds the key \p val using \p pred predicate for searching + /// Checks whether the map contains \p key using \p pred predicate for searching /** - The function is an analog of \ref cds_nonintrusive_MichaelMap_nogc_find "find(K const&)" - but \p pred is used for key comparing. + The function is an analog of contains( key ) but \p pred is used for key comparing. \p Less functor has the interface like \p std::less. - \p Less must imply the same element order as the comparator used for building the map. + \p pred must imply the same element order as the comparator used for building the map. */ template - iterator find_with( const K& key, Less pred ) + iterator contains( K const& key, Less pred ) { bucket_type& refBucket = bucket( key ); - bucket_iterator it = refBucket.find_with( key, pred ); + bucket_iterator it = refBucket.contains( key, pred ); if ( it != refBucket.end() ) return iterator( it, &refBucket, m_Buckets + bucket_count() ); return end(); } + //@cond + // Deprecated, use contains() + template + iterator find_with( K const& key, Less pred ) + { + return contains( key, pred ); + } + //@endcond /// Clears the map (not atomic) void clear() diff --git a/cds/container/michael_map_rcu.h b/cds/container/michael_map_rcu.h index edd82bdc..03ba520d 100644 --- a/cds/container/michael_map_rcu.h +++ b/cds/container/michael_map_rcu.h @@ -403,43 +403,48 @@ namespace cds { namespace container { return bRet; } - - /// Ensures that the \p key exists in the map + /// Updates data by \p key /** - The operation performs inserting or changing data with lock-free manner. + 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 - is inserted into the map (note that in this case the \ref key_type should be - constructible from type \p K). - Otherwise, the functor \p func is called with item found. - The functor \p Func may be a function with signature: - \code - void func( bool bNew, value_type& item ); - \endcode - or a functor: + will be inserted into the map iff \p bAllowInsert 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, the functor \p func is called with item found. + + The functor \p Func signature is: \code struct my_functor { void operator()( bool bNew, value_type& item ); }; \endcode - with arguments: - \p bNew - \p true if the item has been inserted, \p false otherwise - - \p item - item of the list + - \p item - the item found or inserted - The functor may change any fields of the \p item.second that is \ref mapped_type. + The functor may change any fields of the \p item.second that is \p mapped_type. The function applies RCU lock internally. Returns std::pair where \p first is true if operation is successfull, \p second is true if new item has been added or \p false if the item with \p key - already is in the list. + already exists. @warning For \ref cds_nonintrusive_MichaelKVList_rcu "MichaelKVList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting". \ref cds_nonintrusive_LazyKVList_rcu "LazyKVList" provides exclusive access to inserted item and does not require any node-level synchronization. */ template + std::pair update( K const& key, Func func, bool bAllowInsert = true ) + { + std::pair bRet = bucket( key ).update( key, func ); + if ( bRet.first && bRet.second ) + ++m_ItemCounter; + return bRet; + } + //@cond + // Deprecated + template std::pair ensure( K const& key, Func func ) { std::pair bRet = bucket( key ).ensure( key, func ); @@ -447,6 +452,7 @@ namespace cds { namespace container { ++m_ItemCounter; return bRet; } + //@endcond /// For key \p key inserts data of type \p mapped_type created from \p args /** @@ -641,32 +647,46 @@ namespace cds { namespace container { return bucket( key ).find_with( key, pred, f ); } - /// Finds the key \p key - /** \anchor cds_nonintrusive_MichaelMap_rcu_find_val - + /// Checks whether the map contains \p key + /** The function searches the item with key equal to \p key and returns \p true if it is found, and \p false otherwise. The function applies RCU lock internally. */ template + bool contains( K const& key ) + { + return bucket( key ).contains( key ); + } + //@cond + // Deprecated + template bool find( K const& key ) { - return bucket( key ).find( key ); + return bucket( key ).contains( key ); } + //@endcond - /// Finds the key \p val using \p pred predicate for searching + /// Checks whether the map contains \p key using \p pred predicate for searching /** - The function is an analog of \ref cds_nonintrusive_MichaelMap_rcu_find_val "find(K const&)" - but \p pred is used for key comparing. + The function is an analog of contains( key ) but \p pred is used for key comparing. \p Less functor has the interface like \p std::less. \p Less must imply the same element order as the comparator used for building the map. */ template + bool contains( K const& key, Less pred ) + { + return bucket( key ).contains( key, pred ); + } + //@cond + // Deprecated + template bool find_with( K const& key, Less pred ) { - return bucket( key ).find_with( key, pred ); + return bucket( key ).contains( key, pred ); } + //@endcond /// Finds \p key and return the item found /** \anchor cds_nonintrusive_MichaelHashMap_rcu_get diff --git a/cds/intrusive/details/multilevel_hashset_base.h b/cds/intrusive/details/multilevel_hashset_base.h index e65168a3..c41a9974 100644 --- a/cds/intrusive/details/multilevel_hashset_base.h +++ b/cds/intrusive/details/multilevel_hashset_base.h @@ -19,6 +19,9 @@ namespace cds { namespace intrusive { /** @ingroup cds_intrusive_helper */ namespace multilevel_hashset { + //@cond + struct implementation_tag; + //@endcond /// Hash accessor option /** diff --git a/cds/intrusive/impl/lazy_list.h b/cds/intrusive/impl/lazy_list.h index da8a5f6a..d8372e84 100644 --- a/cds/intrusive/impl/lazy_list.h +++ b/cds/intrusive/impl/lazy_list.h @@ -526,36 +526,49 @@ namespace cds { namespace intrusive { return insert_at( &m_Head, val, f ); } - /// Ensures that the \p item exists in the list + /// Updates the item /** The operation performs inserting or changing data with lock-free manner. - If the item \p val not found in the list, then \p val is inserted into the list. + If the item \p val not found in the list, then \p val is inserted into the list + iff \p bAllowInsert is \p true. Otherwise, the functor \p func is called with item found. The functor signature is: \code - void func( bool bNew, value_type& item, value_type& val ); + struct functor { + void operator()( bool bNew, value_type& item, value_type& val ); + }; \endcode with arguments: - \p bNew - \p true if the item has been inserted, \p false otherwise - \p item - item of the list - - \p val - argument \p val passed into the \p ensure function + - \p val - argument \p val passed into the \p update() function If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments refer to the same thing. The functor may change non-key fields of the \p item. While the functor \p f is working the item \p item is locked, - so \p f has exclusive access to the item. + so \p func has exclusive access to the item. - Returns std::pair where \p first is \p true if operation is successfull, + 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 the item with \p key already is in the list. + + The function makes RCU lock internally. */ template + std::pair update( value_type& val, Func func, bool bAllowInsert = true ) + { + return update_at( &m_Head, val, func, bAllowInsert ); + } + //@cond + // Deprecated, use update() + template std::pair ensure( value_type& val, Func func ) { - return ensure_at( &m_Head, val, func ); + return update( val, func, true ); } + //@endcond /// Unlinks the item \p val from the list /** @@ -737,30 +750,45 @@ namespace cds { namespace intrusive { } //@endcond - /// Finds the key \p key - /** \anchor cds_intrusive_LazyList_hp_find_val + /// Checks whether the list contains \p key + /** The function searches the item with key equal to \p key - and returns \p true if it is found, and \p false otherwise + and returns \p true if it is found, and \p false otherwise. */ template - bool find( Q const& key ) + bool contains( Q const& key ) { return find_at( &m_Head, key, key_comparator() ); } + //@cond + // Deprecated, use contains() + template + bool find( Q const& key ) + { + return contains( key ); + } + //@cond - /// Finds \p key using \p pred predicate for searching + /// Checks whether the map contains \p key using \p pred predicate for searching /** - The function is an analog of \ref cds_intrusive_LazyList_hp_find_val "find(Q const&)" - but \p pred is used for key comparing. + The function is an analog of contains( key ) but \p pred is used for key comparing. \p Less functor has the interface like \p std::less. - \p pred must imply the same element order as the comparator used for building the list. + \p Less must imply the same element order as the comparator used for building the list. */ template - bool find_with( Q const& key, Less pred ) + bool contains( Q const& key, Less pred ) { CDS_UNUSED( pred ); return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less() ); } + //@cond + // Deprecated, use contains() + template + bool find_with( Q const& key, Less pred ) + { + return contains( key, pred ); + } + //@endcond /// Finds \p key and return the item found /** \anchor cds_intrusive_LazyList_hp_get @@ -930,7 +958,7 @@ namespace cds { namespace intrusive { } template - std::pair ensure_at( node_type * pHead, value_type& val, Func func ) + std::pair update_at( node_type * pHead, value_type& val, Func func, bool bAllowInsert ) { position pos; key_comparator cmp; @@ -948,6 +976,9 @@ namespace cds { namespace intrusive { } else { // new key + if ( !bAllowInsert ) + return std::make_pair( false, false ); + link_checker::is_empty( node_traits::to_node_ptr( val ) ); link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur ); diff --git a/cds/intrusive/impl/michael_list.h b/cds/intrusive/impl/michael_list.h index f66b185c..426242d6 100644 --- a/cds/intrusive/impl/michael_list.h +++ b/cds/intrusive/impl/michael_list.h @@ -751,30 +751,45 @@ namespace cds { namespace intrusive { } //@endcond - /// Finds the \p key - /** \anchor cds_intrusive_MichaelList_hp_find_val + /// Checks whether the list contains \p key + /** The function searches the item with key equal to \p key - and returns \p true if it is found, and \p false otherwise + and returns \p true if it is found, and \p false otherwise. */ template - bool find( Q const& key ) + bool contains( Q const& key ) { return find_at( m_pHead, key, key_comparator() ); } + //@cond + // Deprecated, use contains() + template + bool find( Q const& key ) + { + return contains( key ); + } + //@endcond - /// Finds the key \p val using \p pred predicate for searching + /// Checks whether the map contains \p key using \p pred predicate for searching /** - The function is an analog of \ref cds_intrusive_MichaelList_hp_find_val "find(Q const&)" - but \p pred is used for key comparing. + The function is an analog of contains( key ) but \p pred is used for key comparing. \p Less functor has the interface like \p std::less. - \p pred must imply the same element order as the comparator used for building the list. + \p Less must imply the same element order as the comparator used for building the list. */ template - bool find_with( Q const& key, Less pred ) + bool contains( Q const& key, Less pred ) { CDS_UNUSED( pred ); return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less() ); } + //@cond + // Deprecated, use contains() + template + bool find_with( Q const& key, Less pred ) + { + return contains( key, pred ); + } + //@endcond /// Finds the \p key and return the item found /** \anchor cds_intrusive_MichaelList_hp_get @@ -968,12 +983,6 @@ namespace cds { namespace intrusive { } } - template - std::pair ensure_at( atomic_node_ptr& refHead, value_type& val, Func func ) - { - return update_at( refHead, val, func, true ); - } - bool unlink_at( atomic_node_ptr& refHead, value_type& val ) { position pos; diff --git a/cds/intrusive/lazy_list_nogc.h b/cds/intrusive/lazy_list_nogc.h index 177d6819..40595f18 100644 --- a/cds/intrusive/lazy_list_nogc.h +++ b/cds/intrusive/lazy_list_nogc.h @@ -343,11 +343,12 @@ namespace cds { namespace intrusive { return insert_at( &m_Head, val ); } - /// Ensures that the \p item exists in the list + /// Updates the item /** The operation performs inserting or changing data with lock-free manner. - If the item \p val not found in the list, then \p val is inserted into the list. + If the item \p val not found in the list, then \p val is inserted into the list + iff \p bAllowInsert is \p true. Otherwise, the functor \p func is called with item found. The functor signature is: \code @@ -358,23 +359,30 @@ namespace cds { namespace intrusive { with arguments: - \p bNew - \p true if the item has been inserted, \p false otherwise - \p item - item of the list - - \p val - argument \p val passed into the \p ensure function + - \p val - argument \p val passed into the \p update() function If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments - refers to the same thing. + refer to the same thing. The functor may change non-key fields of the \p item. While the functor \p f is calling the item \p item is locked. - Returns std::pair where \p first is true if operation is successfull, - \p second is true if new item has been added or \p false if the item with \p key + 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 the item with \p key already is in the list. */ - + template + std::pair update( value_type& val, Func func, bool bAllowInsert = true ) + { + return update_at( &m_Head, val, func, bAllowInsert ); + } + //@cond + // Deprecated, use update() template std::pair ensure( value_type& val, Func func ) { - return ensure_at( &m_Head, val, func ); + return update( &m_Head, val, func, true ); } + //@endcond /// Finds the key \p key /** \anchor cds_intrusive_LazyList_nogc_find_func @@ -448,42 +456,64 @@ namespace cds { namespace intrusive { } //@endcond - /// Finds the key \p key - /** \anchor cds_intrusive_LazyList_nogc_find_val + /// Checks whether the list contains \p key + /** The function searches the item with key equal to \p key - and returns pointer to value found or \p nullptr. + and returns \p true if it is found, and \p false otherwise. */ template - value_type * find( Q const& key ) + value_type * contains( Q const& key ) { return find_at( &m_Head, key, key_comparator() ); } + //@cond + // Deprecated, use contains() + template + value_type * find( Q const& key ) + { + return contains( key ); + } + //@endcond - /// Finds the key \p key using \p pred predicate for searching. Disabled for unordered lists. + /// Checks whether the map contains \p key using \p pred predicate for searching (ordered list version) /** - The function is an analog of \ref cds_intrusive_LazyList_nogc_find_val "find(Q const&)" - but \p pred is used for key comparing. + The function is an analog of contains( key ) but \p pred is used for key comparing. \p Less functor has the interface like \p std::less. - \p pred must imply the same element order as the comparator used for building the list. + \p Less must imply the same element order as the comparator used for building the list. */ template - typename std::enable_if::type find_with( Q const& key, Less pred ) + typename std::enable_if::type contains( Q const& key, Less pred ) { CDS_UNUSED( pred ); return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less() ); } + //@cond + // Deprecated, use contains() + template + typename std::enable_if::type find_with( Q const& key, Less pred ) + { + return contains( key, pred ); + } + //@endcond - /// Finds the key \p key using \p equal predicate for searching. Disabled for ordered lists. + /// Checks whether the map contains \p key using \p equal predicate for searching (unordered list version) /** - The function is an analog of \ref cds_intrusive_LazyList_nogc_find_val "find(Q const&)" - but \p equal is used for key comparing. + The function is an analog of contains( key ) but \p equal is used for key comparing. \p Equal functor has the interface like \p std::equal_to. */ template - typename std::enable_if::type find_with( Q const& key, Equal equal ) + typename std::enable_if::type contains( Q const& key, Equal equal ) { return find_at( &m_Head, key, equal ); } + //@cond + // Deprecated, use contains() + template + typename std::enable_if::type find_with( Q const& key, Equal equal ) + { + return contains( key, equal ); + } + //@endcond /// Clears the list /** @@ -586,7 +616,7 @@ namespace cds { namespace intrusive { template - std::pair ensure_at_( node_type * pHead, value_type& val, Func func ) + std::pair update_at_( node_type * pHead, value_type& val, Func func, bool bAllowInsert ) { position pos; key_comparator pred; @@ -604,6 +634,9 @@ namespace cds { namespace intrusive { } else { // new key + if ( !bAllowInsert ) + return std::make_pair( end(), false ); + link_checker::is_empty( node_traits::to_node_ptr( val ) ); link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur ); @@ -617,9 +650,9 @@ namespace cds { namespace intrusive { } template - std::pair ensure_at( node_type * pHead, value_type& val, Func func ) + std::pair update_at( node_type * pHead, value_type& val, Func func, bool bAllowInsert ) { - std::pair ret = ensure_at_( pHead, val, func ); + std::pair ret = update_at_( pHead, val, func, bAllowInsert ); return std::make_pair( ret.first != end(), ret.second ); } diff --git a/cds/intrusive/lazy_list_rcu.h b/cds/intrusive/lazy_list_rcu.h index 908659a3..12486644 100644 --- a/cds/intrusive/lazy_list_rcu.h +++ b/cds/intrusive/lazy_list_rcu.h @@ -453,11 +453,12 @@ namespace cds { namespace intrusive { return insert_at( &m_Head, val, f ); } - /// Ensures that the \p item exists in the list + /// Updates the item /** The operation performs inserting or changing data with lock-free manner. - If the item \p val not found in the list, then \p val is inserted into the list. + If the item \p val not found in the list, then \p val is inserted into the list + iff \p bAllowInsert is \p true. Otherwise, the functor \p func is called with item found. The functor signature is: \code @@ -468,23 +469,32 @@ namespace cds { namespace intrusive { with arguments: - \p bNew - \p true if the item has been inserted, \p false otherwise - \p item - item of the list - - \p val - argument \p val passed into the \p ensure function + - \p val - argument \p val passed into the \p update() function If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments - refers to the same thing. + refer to the same thing. The functor may change non-key fields of the \p item. While the functor \p f is calling the item \p item is locked. - Returns std::pair where \p first is true if operation is successfull, - \p second is true if new item has been added or \p false if the item with \p key + 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 the item with \p key already is in the list. - */ + The function makes RCU lock internally. + */ + template + std::pair update( value_type& val, Func func, bool bAllowInsert = true ) + { + return update_at( &m_Head, val, func, bAllowInsert ); + } + //@cond + // Deprecated, use update() template std::pair ensure( value_type& val, Func func ) { - return ensure_at( &m_Head, val, func ); + return update( val, func, true ); } + //@cond /// Unlinks the item \p val from the list /** @@ -676,8 +686,7 @@ namespace cds { namespace intrusive { /// Finds the key \p key using \p pred predicate for searching /** - The function is an analog of \ref cds_intrusive_LazyList_rcu_find_func "find(Q&, Func)" - but \p pred is used for key comparing. + The function is an analog of contains( key ) but \p pred is used for key comparing. \p Less functor has the interface like \p std::less. \p pred must imply the same element order as the comparator used for building the list. */ @@ -696,30 +705,45 @@ namespace cds { namespace intrusive { } //@endcond - /// Finds the key \p key - /** \anchor cds_intrusive_LazyList_rcu_find_val + /// Checks whether the list contains \p key + /** The function searches the item with key equal to \p key - and returns \p true if \p key found or \p false otherwise. + and returns \p true if it is found, and \p false otherwise. */ template - bool find( Q const& key ) const + bool contains( Q const& key ) const { return find_at( const_cast( &m_Head ), key, key_comparator() ); } + //@cond + // Deprecated, use contains() + template + bool find( Q const& key ) const + { + return contains( key ); + } + //@endcond - /// Finds the key \p key using \p pred predicate for searching + /// Checks whether the map contains \p key using \p pred predicate for searching /** - The function is an analog of \ref cds_intrusive_LazyList_rcu_find_val "find(Q const&)" - but \p pred is used for key comparing. + The function is an analog of contains( key ) but \p pred is used for key comparing. \p Less functor has the interface like \p std::less. - \p pred must imply the same element order as the comparator used for building the list. + \p Less must imply the same element order as the comparator used for building the list. */ template - bool find_with( Q const& key, Less pred ) const + bool contains( Q const& key, Less pred ) const { CDS_UNUSED( pred ); return find_at( const_cast( &m_Head ), key, cds::opt::details::make_comparator_from_less() ); } + //@cond + // Deprecated, use contains() + template + bool find_with( Q const& key, Less pred ) const + { + return contains( key, pred ); + } + //@endcond /// Finds the key \p key and return the item found /** \anchor cds_intrusive_LazyList_rcu_get @@ -920,14 +944,14 @@ namespace cds { namespace intrusive { template - std::pair ensure_at_( node_type * pHead, value_type& val, Func func ) + std::pair update_at_( node_type * pHead, value_type& val, Func func, bool bAllowInsert ) { rcu_lock l; - return ensure_at_locked( pHead, val, func ); + return update_at_locked( pHead, val, func, bAllowInsert ); } template - std::pair ensure_at_locked( node_type * pHead, value_type& val, Func func ) + std::pair update_at_locked( node_type * pHead, value_type& val, Func func, bool bAllowInsert ) { // RCU lock should be locked!!! assert( gc::is_locked() ); @@ -948,6 +972,9 @@ namespace cds { namespace intrusive { } else { // new key + if ( !bAllowInsert ) + return std::make_pair( end(), false ); + link_checker::is_empty( node_traits::to_node_ptr( val ) ); link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur ); @@ -961,10 +988,10 @@ namespace cds { namespace intrusive { } template - std::pair ensure_at( node_type * pHead, value_type& val, Func func ) + std::pair update_at( node_type * pHead, value_type& val, Func func, bool bAllowInsert ) { rcu_lock l; - std::pair ret = ensure_at_locked( pHead, val, func ); + std::pair ret = update_at_locked( pHead, val, func, bAllowInsert ); return std::make_pair( ret.first != end(), ret.second ); } diff --git a/cds/intrusive/michael_list_nogc.h b/cds/intrusive/michael_list_nogc.h index 82b11fd5..c1fec7c1 100644 --- a/cds/intrusive/michael_list_nogc.h +++ b/cds/intrusive/michael_list_nogc.h @@ -299,11 +299,12 @@ namespace cds { namespace intrusive { return insert_at( m_pHead, val ); } - /// Ensures that the \p item exists in the list + /// Updates the item /** The operation performs inserting or changing data with lock-free manner. - If the item \p val not found in the list, then \p val is inserted into the list. + If the item \p val not found in the list, then \p val is inserted into the list + iff \p bAllowInsert is \p true. Otherwise, the functor \p func is called with item found. The functor signature is: \code @@ -314,23 +315,30 @@ namespace cds { namespace intrusive { with arguments: - \p bNew - \p true if the item has been inserted, \p false otherwise - \p item - item of the list - - \p val - argument \p val passed into the \p ensure function + - \p val - argument \p val passed into the \p update() function If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments refer to the same thing. The functor may change non-key fields of the \p item; however, \p func must guarantee that during changing no any other modifications could be made on this item by concurrent threads. - Returns std::pair where \p first is true if operation is successfull, - \p second is true if new item has been added or \p false if the item with \p key + 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 the item with \p key already is in the list. */ - + template + std::pair update( value_type& val, Func func, bool bAllowInsert = true ) + { + return update_at( m_pHead, val, func, bAllowInsert ); + } + //@cond + // Deprecated, use update() template std::pair ensure( value_type& val, Func func ) { - return ensure_at( m_pHead, val, func ); + return update( val, func ); } + //@endcond /// Finds the key \p val /** \anchor cds_intrusive_MichaelList_nogc_find_func @@ -385,30 +393,45 @@ namespace cds { namespace intrusive { } //@endcond - /// Finds \p key - /** \anchor cds_intrusive_MichaelList_nogc_find_val + /// Checks whether the list contains \p key + /** The function searches the item with key equal to \p key - and returns pointer to value found or \p nullptr. + and returns \p true if it is found, and \p false otherwise. */ template - value_type * find( Q const& key ) + value_type * contains( Q const& key ) { return find_at( m_pHead, key, key_comparator() ); } + //@cond + // Deprecated, use contains() + template + value_type * find( Q const& key ) + { + return contains( key ); + } + //@endcond - /// Finds \p key using \p pred predicate for searching + /// Checks whether the map contains \p key using \p pred predicate for searching /** - The function is an analog of \ref cds_intrusive_MichaelList_nogc_find_val "find(Q const&, Func)" - but \p pred is used for key comparing. + The function is an analog of contains( key ) but \p pred is used for key comparing. \p Less functor has the interface like \p std::less. - \p pred must imply the same element order as the comparator used for building the list. + \p Less must imply the same element order as the comparator used for building the list. */ template - value_type * find_with( Q const& key, Less pred ) + value_type * contains( Q const& key, Less pred ) { CDS_UNUSED( pred ); return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less()); } + //@cond + // Deprecated, use contains() + template + value_type * find_with( Q const& key, Less pred ) + { + return contains( key, pred ); + } + //@endcond /// Clears the list /** @@ -501,7 +524,7 @@ namespace cds { namespace intrusive { } template - std::pair ensure_at_( atomic_node_ptr& refHead, value_type& val, Func func ) + std::pair update_at_( atomic_node_ptr& refHead, value_type& val, Func func, bool bAllowInsert ) { position pos; @@ -513,6 +536,9 @@ namespace cds { namespace intrusive { return std::make_pair( iterator( pos.pCur ), false ); } else { + if ( !bAllowInsert ) + return std::make_pair( end(), false ); + link_checker::is_empty( node_traits::to_node_ptr( val ) ); if ( link_node( node_traits::to_node_ptr( val ), pos ) ) { @@ -525,9 +551,9 @@ namespace cds { namespace intrusive { } template - std::pair ensure_at( atomic_node_ptr& refHead, value_type& val, Func func ) + std::pair update_at( atomic_node_ptr& refHead, value_type& val, Func func, bool bAllowInsert ) { - std::pair ret = ensure_at_( refHead, val, func ); + std::pair ret = update_at_( refHead, val, func, bAllowInsert ); return std::make_pair( ret.first != end(), ret.second ); } diff --git a/cds/intrusive/michael_list_rcu.h b/cds/intrusive/michael_list_rcu.h index b8e61530..71f0b1d3 100644 --- a/cds/intrusive/michael_list_rcu.h +++ b/cds/intrusive/michael_list_rcu.h @@ -452,7 +452,7 @@ namespace cds { namespace intrusive { The operation performs inserting or changing data with lock-free manner. If the item \p val not found in the list, then \p val is inserted into the list - iff \p bInsert is \p true. + iff \p bAllowInsert is \p true. Otherwise, the functor \p func is called with item found. The functor signature is: \code @@ -479,11 +479,10 @@ namespace cds { namespace intrusive { @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ template - std::pair update( value_type& val, Func func, bool bInsert = true ) + std::pair update( value_type& val, Func func, bool bAllowInsert = true ) { - return update_at( m_pHead, val, func, bInsert ); + return update_at( m_pHead, val, func, bAllowInsert ); } - //@cond // Deprecated, use update() template @@ -702,30 +701,45 @@ namespace cds { namespace intrusive { } //@endcond - /// Finds \p key - /** \anchor cds_intrusive_MichaelList_rcu_find_val + /// Checks whether the list contains \p key + /** The function searches the item with key equal to \p key - and returns \p true if \p val found or \p false otherwise. + and returns \p true if it is found, and \p false otherwise. */ template - bool find( Q const& key ) + bool contains( Q const& key ) { return find_at( m_pHead, key, key_comparator() ); } + //@cond + // Deprecated, use contains() + template + bool find( Q const& key ) + { + return contains( key ); + } + //@endcond - /// Finds \p key using \p pred predicate for searching + /// Checks whether the map contains \p key using \p pred predicate for searching /** - The function is an analog of \ref cds_intrusive_MichaelList_rcu_find_val "find(Q const&)" - but \p pred is used for key comparing. + The function is an analog of contains( key ) but \p pred is used for key comparing. \p Less functor has the interface like \p std::less. - \p pred must imply the same element order as the comparator used for building the list. + \p Less must imply the same element order as the comparator used for building the list. */ template - bool find_with( Q const& key, Less pred ) + bool contains( Q const& key, Less pred ) { CDS_UNUSED( pred ); return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less() ); } + //@cond + // Deprecated + template + bool find_with( Q const& key, Less pred ) + { + return contains( key, pred ); + } + //@endcond /// Finds \p key and return the item found /** \anchor cds_intrusive_MichaelList_rcu_get @@ -904,12 +918,6 @@ namespace cds { namespace intrusive { } } - template - std::pair ensure_at_( atomic_node_ptr& refHead, value_type& val, Func func ) - { - return update_at_( refHead, val, func, true ); - } - template std::pair update_at( atomic_node_ptr& refHead, value_type& val, Func func, bool bInsert ) { @@ -921,12 +929,6 @@ namespace cds { namespace intrusive { } } - template - std::pair ensure_at( atomic_node_ptr& refHead, value_type& val, Func func ) - { - return update_at( refHead, val, func, true ); - } - bool unlink_at( atomic_node_ptr& refHead, value_type& val ) { position pos( refHead ); diff --git a/projects/Win/vc12/cds.sln b/projects/Win/vc12/cds.sln index c63ed1af..8f96230c 100644 --- a/projects/Win/vc12/cds.sln +++ b/projects/Win/vc12/cds.sln @@ -80,6 +80,7 @@ Project("{2150E333-8FDC-42A3-9474-1A3956D46DE8}") = "map", "map", "{6BB7A27F-FC5 ..\..\..\tests\unit\map2\map_type_lazy_list.h = ..\..\..\tests\unit\map2\map_type_lazy_list.h ..\..\..\tests\unit\map2\map_type_michael.h = ..\..\..\tests\unit\map2\map_type_michael.h ..\..\..\tests\unit\map2\map_type_michael_list.h = ..\..\..\tests\unit\map2\map_type_michael_list.h + ..\..\..\tests\unit\map2\map_type_multilevel_hashmap.h = ..\..\..\tests\unit\map2\map_type_multilevel_hashmap.h ..\..\..\tests\unit\map2\map_type_skip_list.h = ..\..\..\tests\unit\map2\map_type_skip_list.h ..\..\..\tests\unit\map2\map_type_split_list.h = ..\..\..\tests\unit\map2\map_type_split_list.h ..\..\..\tests\unit\map2\map_type_std.h = ..\..\..\tests\unit\map2\map_type_std.h diff --git a/projects/Win/vc12/unit-map-delodd.vcxproj b/projects/Win/vc12/unit-map-delodd.vcxproj index 1dfcb487..61c48744 100644 --- a/projects/Win/vc12/unit-map-delodd.vcxproj +++ b/projects/Win/vc12/unit-map-delodd.vcxproj @@ -44,12 +44,27 @@ - - - - - - + + true + + + true + + + true + + + false + + + true + + + true + + + true + diff --git a/projects/source.unit.map.mk b/projects/source.unit.map.mk index abbe9446..98b927fb 100644 --- a/projects/source.unit.map.mk +++ b/projects/source.unit.map.mk @@ -90,6 +90,7 @@ CDSUNIT_MAP_SOURCES := \ tests/unit/map2/map_delodd_michael.cpp \ tests/unit/map2/map_delodd_bronsonavltree.cpp \ tests/unit/map2/map_delodd_ellentree.cpp \ + tests/unit/map2/map_delodd_multilevel_hashmap.cpp \ tests/unit/map2/map_delodd_split.cpp \ tests/unit/map2/map_delodd_skip.cpp \ tests/unit/map2/map_delodd_cuckoo.cpp \ diff --git a/tests/test-hdr/list/hdr_intrusive_lazy.h b/tests/test-hdr/list/hdr_intrusive_lazy.h index 802bfbbf..f3ebb3e0 100644 --- a/tests/test-hdr/list/hdr_intrusive_lazy.h +++ b/tests/test-hdr/list/hdr_intrusive_lazy.h @@ -16,15 +16,15 @@ namespace ordlist { struct stat { int nDisposeCount; - int nEnsureExistsCall; - int nEnsureNewCall; + int nUpdateExistsCall; + int nUpdateNewCall; int nFindCall; int nEraseCall; stat() : nDisposeCount(0) - , nEnsureExistsCall(0) - , nEnsureNewCall(0) + , nUpdateExistsCall(0) + , nUpdateNewCall(0) , nFindCall(0) , nEraseCall(0) {} @@ -201,15 +201,15 @@ namespace ordlist { } }; - struct ensure_functor + struct update_functor { template void operator ()(bool bNew, T& item, T& /*val*/ ) { if ( bNew ) - ++item.s.nEnsureNewCall; + ++item.s.nUpdateNewCall; else - ++item.s.nEnsureExistsCall; + ++item.s.nUpdateExistsCall; } }; @@ -244,13 +244,13 @@ namespace ordlist { CPPUNIT_ASSERT( l.empty() ); CPPUNIT_ASSERT( l.insert( v1 )) ; // true - CPPUNIT_ASSERT( l.find( v1.key() )); + CPPUNIT_ASSERT( l.contains( v1.key() )); CPPUNIT_ASSERT( v1.s.nFindCall == 0 ); CPPUNIT_ASSERT( l.find( v1.key(), find_functor() )); CPPUNIT_ASSERT( v1.s.nFindCall == 1 ); - CPPUNIT_ASSERT( !l.find_with( v2.key(), less() )); + CPPUNIT_ASSERT( !l.contains( v2.key(), less() )); CPPUNIT_ASSERT( !l.find( v3.key(), find_functor() )); CPPUNIT_ASSERT( !l.empty() ); @@ -261,56 +261,56 @@ namespace ordlist { CPPUNIT_ASSERT( !l.insert( v )) ; // false } - std::pair ret = l.ensure( v2, ensure_functor() ); + std::pair ret = l.update( v2, update_functor() ); CPPUNIT_ASSERT( ret.first ); CPPUNIT_ASSERT( ret.second ); - CPPUNIT_ASSERT( v2.s.nEnsureNewCall == 1 ); - CPPUNIT_ASSERT( v2.s.nEnsureExistsCall == 0 ); + CPPUNIT_ASSERT( v2.s.nUpdateNewCall == 1 ); + CPPUNIT_ASSERT( v2.s.nUpdateExistsCall == 0 ); //CPPUNIT_ASSERT( !l.insert( v2 )) ; // assertion "is_empty" - CPPUNIT_ASSERT( l.find( v1.key() )) ; // true + CPPUNIT_ASSERT( l.contains( v1.key() )) ; // true CPPUNIT_ASSERT( v1.s.nFindCall == 1 ); CPPUNIT_ASSERT( l.find( v1.key(), find_functor() )); CPPUNIT_ASSERT( v1.s.nFindCall == 2 ); - CPPUNIT_ASSERT( l.find( v2.key() )); + CPPUNIT_ASSERT( l.contains( v2.key() )); CPPUNIT_ASSERT( v2.s.nFindCall == 0 ); CPPUNIT_ASSERT( l.find_with( v2.key(), less(), find_functor() )); CPPUNIT_ASSERT( v2.s.nFindCall == 1 ); - CPPUNIT_ASSERT( !l.find( v3.key() )); + CPPUNIT_ASSERT( !l.contains( v3.key() )); { - CPPUNIT_ASSERT( v2.s.nEnsureExistsCall == 0 ); - CPPUNIT_ASSERT( v2.s.nEnsureNewCall == 1 ); + CPPUNIT_ASSERT( v2.s.nUpdateExistsCall == 0 ); + CPPUNIT_ASSERT( v2.s.nUpdateNewCall == 1 ); value_type v( v2 ); - ret = l.ensure( v, ensure_functor() ); + ret = l.update( v, update_functor() ); CPPUNIT_ASSERT( ret.first ); CPPUNIT_ASSERT( !ret.second ); - CPPUNIT_ASSERT( v2.s.nEnsureExistsCall == 1 ); - CPPUNIT_ASSERT( v2.s.nEnsureNewCall == 1 ); - CPPUNIT_ASSERT( v.s.nEnsureExistsCall == 0 ); - CPPUNIT_ASSERT( v.s.nEnsureNewCall == 0 ); + CPPUNIT_ASSERT( v2.s.nUpdateExistsCall == 1 ); + CPPUNIT_ASSERT( v2.s.nUpdateNewCall == 1 ); + CPPUNIT_ASSERT( v.s.nUpdateExistsCall == 0 ); + CPPUNIT_ASSERT( v.s.nUpdateNewCall == 0 ); } CPPUNIT_ASSERT( !l.empty() ); CPPUNIT_ASSERT( l.insert( v3 )) ; // true - CPPUNIT_ASSERT( l.find( v3.key() )); + CPPUNIT_ASSERT( l.contains( v3.key() )); CPPUNIT_ASSERT( v3.s.nFindCall == 0 ); CPPUNIT_ASSERT( l.find( v3.key(), find_functor() )); CPPUNIT_ASSERT( v3.s.nFindCall == 1 ); CPPUNIT_ASSERT( l.unlink( v2 ) ); - CPPUNIT_ASSERT( l.find( v1.key() )) ; // true - CPPUNIT_ASSERT( !l.find( v2.key() )) ; // true - CPPUNIT_ASSERT( l.find( v3.key() )) ; // true + CPPUNIT_ASSERT( l.contains( v1.key() )) ; // true + CPPUNIT_ASSERT( !l.contains( v2.key() )) ; // true + CPPUNIT_ASSERT( l.contains( v3.key() )) ; // true CPPUNIT_ASSERT( !l.empty() ); CPPUNIT_ASSERT( !l.unlink( v2 ) ); @@ -322,17 +322,17 @@ namespace ordlist { CPPUNIT_ASSERT( l.unlink( v1 ) ); CPPUNIT_ASSERT( !l.unlink( v1 ) ); - CPPUNIT_ASSERT( !l.find( v1.key() )); - CPPUNIT_ASSERT( !l.find( v2.key() )); - CPPUNIT_ASSERT( l.find( v3.key() )); + CPPUNIT_ASSERT( !l.contains( v1.key() )); + CPPUNIT_ASSERT( !l.contains( v2.key() )); + CPPUNIT_ASSERT( l.contains( v3.key() )); CPPUNIT_ASSERT( !l.empty() ); CPPUNIT_ASSERT( !l.unlink( v1 ) ); CPPUNIT_ASSERT( !l.unlink( v2 ) ); CPPUNIT_ASSERT( l.unlink( v3 ) ); - CPPUNIT_ASSERT( !l.find( v1.key() )); - CPPUNIT_ASSERT( !l.find_with( v2.key(), less() )); - CPPUNIT_ASSERT( !l.find( v3.key() )); + CPPUNIT_ASSERT( !l.contains( v1.key() )); + CPPUNIT_ASSERT( !l.contains( v2.key(), less() )); + CPPUNIT_ASSERT( !l.contains( v3.key() )); CPPUNIT_ASSERT( l.empty() ); CPPUNIT_ASSERT( !l.unlink( v1 ) ); CPPUNIT_ASSERT( !l.unlink( v2 ) ); @@ -342,27 +342,27 @@ namespace ordlist { OrdList::gc::force_dispose(); stat s( v3.s ); - ret = l.ensure( v3, ensure_functor() ); + ret = l.update( v3, update_functor() ); CPPUNIT_ASSERT( ret.first ); CPPUNIT_ASSERT( ret.second ); - CPPUNIT_ASSERT( v3.s.nEnsureNewCall == s.nEnsureNewCall + 1); - CPPUNIT_ASSERT( v3.s.nEnsureExistsCall == s.nEnsureExistsCall ); + CPPUNIT_ASSERT( v3.s.nUpdateNewCall == s.nUpdateNewCall + 1); + CPPUNIT_ASSERT( v3.s.nUpdateExistsCall == s.nUpdateExistsCall ); CPPUNIT_ASSERT( !l.empty() ); s = v2.s; - ret = l.ensure( v2, ensure_functor() ); + ret = l.update( v2, update_functor() ); CPPUNIT_ASSERT( ret.first ); CPPUNIT_ASSERT( ret.second ); - CPPUNIT_ASSERT( v2.s.nEnsureNewCall == s.nEnsureNewCall + 1); - CPPUNIT_ASSERT( v2.s.nEnsureExistsCall == s.nEnsureExistsCall ); + CPPUNIT_ASSERT( v2.s.nUpdateNewCall == s.nUpdateNewCall + 1); + CPPUNIT_ASSERT( v2.s.nUpdateExistsCall == s.nUpdateExistsCall ); CPPUNIT_ASSERT( !l.empty() ); s = v1.s; - ret = l.ensure( v1, ensure_functor() ); + ret = l.update( v1, update_functor() ); CPPUNIT_ASSERT( ret.first ); CPPUNIT_ASSERT( ret.second ); - CPPUNIT_ASSERT( v1.s.nEnsureNewCall == s.nEnsureNewCall + 1); - CPPUNIT_ASSERT( v1.s.nEnsureExistsCall == s.nEnsureExistsCall ); + CPPUNIT_ASSERT( v1.s.nUpdateNewCall == s.nUpdateNewCall + 1); + CPPUNIT_ASSERT( v1.s.nUpdateExistsCall == s.nUpdateExistsCall ); CPPUNIT_ASSERT( !l.empty() ); // Erase test @@ -670,14 +670,14 @@ namespace ordlist { CPPUNIT_ASSERT( l.empty() ); CPPUNIT_ASSERT( l.insert( v1 )) ; // true - CPPUNIT_ASSERT( l.find( v1.key() ) == &v1 ); + CPPUNIT_ASSERT( l.contains( v1.key() ) == &v1 ); CPPUNIT_ASSERT( v1.s.nFindCall == 0 ); CPPUNIT_ASSERT( l.find( v1.key(), find_functor() )); CPPUNIT_ASSERT( v1.s.nFindCall == 1 ); - CPPUNIT_ASSERT( l.find_with( v2.key(), less() ) == nullptr ); - CPPUNIT_ASSERT( l.find( v3.key() ) == nullptr ); + CPPUNIT_ASSERT( l.contains( v2.key(), less() ) == nullptr ); + CPPUNIT_ASSERT( l.contains( v3.key() ) == nullptr ); CPPUNIT_ASSERT( !l.empty() ); //CPPUNIT_ASSERT( !l.insert( v1 )) ; // assertion "is_empty" is raised @@ -687,42 +687,42 @@ namespace ordlist { CPPUNIT_ASSERT( !l.insert( v )) ; // false } - std::pair ret = l.ensure( v2, ensure_functor() ); + std::pair ret = l.update( v2, update_functor() ); CPPUNIT_ASSERT( ret.first ); CPPUNIT_ASSERT( ret.second ); - CPPUNIT_ASSERT( v2.s.nEnsureNewCall == 1 ); - CPPUNIT_ASSERT( v2.s.nEnsureExistsCall == 0 ); + CPPUNIT_ASSERT( v2.s.nUpdateNewCall == 1 ); + CPPUNIT_ASSERT( v2.s.nUpdateExistsCall == 0 ); //CPPUNIT_ASSERT( !l.insert( v2 )) ; // assertion "is_empty" - CPPUNIT_ASSERT( l.find( v1.key() ) == &v1 ) ; // true + CPPUNIT_ASSERT( l.contains( v1.key() ) == &v1 ) ; // true CPPUNIT_ASSERT( v1.s.nFindCall == 1 ); CPPUNIT_ASSERT( l.find( v1.key(), find_functor() )); CPPUNIT_ASSERT( v1.s.nFindCall == 2 ); - CPPUNIT_ASSERT( l.find_with( v2.key(), less() ) == &v2 ); + CPPUNIT_ASSERT( l.contains( v2.key(), less() ) == &v2 ); CPPUNIT_ASSERT( v2.s.nFindCall == 0 ); CPPUNIT_ASSERT( l.find_with( v2.key(), less(), find_functor() )); CPPUNIT_ASSERT( v2.s.nFindCall == 1 ); - CPPUNIT_ASSERT( !l.find( v3.key() )); + CPPUNIT_ASSERT( !l.contains( v3.key() )); { value_type v( v2 ); - ret = l.ensure( v, ensure_functor() ); + ret = l.update( v, update_functor() ); CPPUNIT_ASSERT( ret.first ); CPPUNIT_ASSERT( !ret.second ); - CPPUNIT_ASSERT( v2.s.nEnsureExistsCall == 1 ); - CPPUNIT_ASSERT( v.s.nEnsureExistsCall == 0 && v.s.nEnsureNewCall == 0 ); + CPPUNIT_ASSERT( v2.s.nUpdateExistsCall == 1 ); + CPPUNIT_ASSERT( v.s.nUpdateExistsCall == 0 && v.s.nUpdateNewCall == 0 ); } CPPUNIT_ASSERT( !l.empty() ); CPPUNIT_ASSERT( l.insert( v3 )) ; // true - CPPUNIT_ASSERT( l.find( v3.key() ) == &v3 ); + CPPUNIT_ASSERT( l.contains( v3.key() ) == &v3 ); CPPUNIT_ASSERT( v3.s.nFindCall == 0 ); CPPUNIT_ASSERT( l.find( v3.key(), find_functor() )); @@ -786,14 +786,14 @@ namespace ordlist { CPPUNIT_ASSERT( l.empty() ); CPPUNIT_ASSERT( l.insert( v1 )); // true - CPPUNIT_ASSERT( l.find( v1.key() ) == &v1 ); + CPPUNIT_ASSERT( l.contains( v1.key() ) == &v1 ); CPPUNIT_ASSERT( v1.s.nFindCall == 0 ); CPPUNIT_ASSERT( l.find( v1.key(), find_functor() )); CPPUNIT_ASSERT( v1.s.nFindCall == 1 ); - CPPUNIT_ASSERT( l.find_with( v2.key(), equal_to() ) == nullptr ); - CPPUNIT_ASSERT( l.find( v3.key() ) == nullptr ); + CPPUNIT_ASSERT( l.contains( v2.key(), equal_to() ) == nullptr ); + CPPUNIT_ASSERT( l.contains( v3.key() ) == nullptr ); CPPUNIT_ASSERT( !l.empty() ); //CPPUNIT_ASSERT( !l.insert( v1 )) ; // assertion "is_empty" is raised @@ -803,42 +803,42 @@ namespace ordlist { CPPUNIT_ASSERT( !l.insert( v )) ; // false } - std::pair ret = l.ensure( v2, ensure_functor() ); + std::pair ret = l.update( v2, update_functor() ); CPPUNIT_ASSERT( ret.first ); CPPUNIT_ASSERT( ret.second ); - CPPUNIT_ASSERT( v2.s.nEnsureNewCall == 1 ); - CPPUNIT_ASSERT( v2.s.nEnsureExistsCall == 0 ); + CPPUNIT_ASSERT( v2.s.nUpdateNewCall == 1 ); + CPPUNIT_ASSERT( v2.s.nUpdateExistsCall == 0 ); //CPPUNIT_ASSERT( !l.insert( v2 )) ; // assertion "is_empty" - CPPUNIT_ASSERT( l.find( v1.key() ) == &v1 ) ; // true + CPPUNIT_ASSERT( l.contains( v1.key() ) == &v1 ) ; // true CPPUNIT_ASSERT( v1.s.nFindCall == 1 ); CPPUNIT_ASSERT( l.find( v1.key(), find_functor() )); CPPUNIT_ASSERT( v1.s.nFindCall == 2 ); - CPPUNIT_ASSERT( l.find_with( v2.key(), equal_to() ) == &v2 ); + CPPUNIT_ASSERT( l.contains( v2.key(), equal_to() ) == &v2 ); CPPUNIT_ASSERT( v2.s.nFindCall == 0 ); CPPUNIT_ASSERT( l.find_with( v2.key(), equal_to(), find_functor() )); CPPUNIT_ASSERT( v2.s.nFindCall == 1 ); - CPPUNIT_ASSERT( !l.find( v3.key() )); + CPPUNIT_ASSERT( !l.contains( v3.key() )); { value_type v( v2 ); - ret = l.ensure( v, ensure_functor() ); + ret = l.update( v, update_functor() ); CPPUNIT_ASSERT( ret.first ); CPPUNIT_ASSERT( !ret.second ); - CPPUNIT_ASSERT( v2.s.nEnsureExistsCall == 1 ); - CPPUNIT_ASSERT( v.s.nEnsureExistsCall == 0 && v.s.nEnsureNewCall == 0 ); + CPPUNIT_ASSERT( v2.s.nUpdateExistsCall == 1 ); + CPPUNIT_ASSERT( v.s.nUpdateExistsCall == 0 && v.s.nUpdateNewCall == 0 ); } CPPUNIT_ASSERT( !l.empty() ); CPPUNIT_ASSERT( l.insert( v3 )) ; // true - CPPUNIT_ASSERT( l.find( v3.key() ) == &v3 ); + CPPUNIT_ASSERT( l.contains( v3.key() ) == &v3 ); CPPUNIT_ASSERT( v3.s.nFindCall == 0 ); CPPUNIT_ASSERT( l.find( v3.key(), find_functor() )); diff --git a/tests/test-hdr/list/hdr_intrusive_michael.h b/tests/test-hdr/list/hdr_intrusive_michael.h index de018341..05afb3fc 100644 --- a/tests/test-hdr/list/hdr_intrusive_michael.h +++ b/tests/test-hdr/list/hdr_intrusive_michael.h @@ -16,15 +16,15 @@ namespace ordlist { struct stat { int nDisposeCount; - int nEnsureExistsCall; - int nEnsureNewCall; + int nUpdateExistsCall; + int nUpdateNewCall; int nFindCall; int nEraseCall; stat() : nDisposeCount(0) - , nEnsureExistsCall(0) - , nEnsureNewCall(0) + , nUpdateExistsCall(0) + , nUpdateNewCall(0) , nFindCall(0) , nEraseCall(0) {} @@ -173,15 +173,15 @@ namespace ordlist { } }; - struct ensure_functor + struct update_functor { template void operator ()(bool bNew, T& item, T& /*val*/ ) { if ( bNew ) - ++item.s.nEnsureNewCall; + ++item.s.nUpdateNewCall; else - ++item.s.nEnsureExistsCall; + ++item.s.nUpdateExistsCall; } }; @@ -216,14 +216,14 @@ namespace ordlist { CPPUNIT_ASSERT( l.empty() ); CPPUNIT_ASSERT( l.insert( v1 )) ; // true - CPPUNIT_ASSERT( l.find( v1.key() )); + CPPUNIT_ASSERT( l.contains( v1.key() )); CPPUNIT_ASSERT( v1.s.nFindCall == 0 ); CPPUNIT_ASSERT( l.find( v1.key(), find_functor() )); CPPUNIT_ASSERT( v1.s.nFindCall == 1 ); - CPPUNIT_ASSERT( !l.find( v2.key() )); - CPPUNIT_ASSERT( !l.find_with( v3.key(), less() )); + CPPUNIT_ASSERT( !l.contains( v2.key() )); + CPPUNIT_ASSERT( !l.contains( v3.key(), less() )); CPPUNIT_ASSERT( !l.empty() ); CPPUNIT_ASSERT( !l.insert( v1 )) ; // assertion "is_empty" is not raised since pNext is nullptr @@ -233,56 +233,56 @@ namespace ordlist { CPPUNIT_ASSERT( !l.insert( v )) ; // false } - std::pair ret = l.ensure( v2, ensure_functor() ); + std::pair ret = l.update( v2, update_functor() ); CPPUNIT_ASSERT( ret.first ); CPPUNIT_ASSERT( ret.second ); - CPPUNIT_ASSERT( v2.s.nEnsureNewCall == 1 ); - CPPUNIT_ASSERT( v2.s.nEnsureExistsCall == 0 ); + CPPUNIT_ASSERT( v2.s.nUpdateNewCall == 1 ); + CPPUNIT_ASSERT( v2.s.nUpdateExistsCall == 0 ); //CPPUNIT_ASSERT( !l.insert( v2 )) ; // assertion "is_empty" - CPPUNIT_ASSERT( l.find_with( v1.key(), less() )) ; // true + CPPUNIT_ASSERT( l.contains( v1.key(), less() )) ; // true CPPUNIT_ASSERT( v1.s.nFindCall == 1 ); CPPUNIT_ASSERT( l.find_with( v1.key(), less(), find_functor() )); CPPUNIT_ASSERT( v1.s.nFindCall == 2 ); - CPPUNIT_ASSERT( l.find( v2.key() )); + CPPUNIT_ASSERT( l.contains( v2.key() )); CPPUNIT_ASSERT( v2.s.nFindCall == 0 ); CPPUNIT_ASSERT( l.find( v2.key(), find_functor() )); CPPUNIT_ASSERT( v2.s.nFindCall == 1 ); - CPPUNIT_ASSERT( !l.find( v3.key() )); + CPPUNIT_ASSERT( !l.contains( v3.key() )); { - CPPUNIT_ASSERT( v2.s.nEnsureExistsCall == 0 ); - CPPUNIT_ASSERT( v2.s.nEnsureNewCall == 1 ); + CPPUNIT_ASSERT( v2.s.nUpdateExistsCall == 0 ); + CPPUNIT_ASSERT( v2.s.nUpdateNewCall == 1 ); value_type v( v2 ); - ret = l.ensure( v, ensure_functor() ); + ret = l.update( v, update_functor() ); CPPUNIT_ASSERT( ret.first ); CPPUNIT_ASSERT( !ret.second ); - CPPUNIT_ASSERT( v2.s.nEnsureExistsCall == 1 ); - CPPUNIT_ASSERT( v2.s.nEnsureNewCall == 1 ); - CPPUNIT_ASSERT( v.s.nEnsureExistsCall == 0 ); - CPPUNIT_ASSERT( v.s.nEnsureNewCall == 0 ); + CPPUNIT_ASSERT( v2.s.nUpdateExistsCall == 1 ); + CPPUNIT_ASSERT( v2.s.nUpdateNewCall == 1 ); + CPPUNIT_ASSERT( v.s.nUpdateExistsCall == 0 ); + CPPUNIT_ASSERT( v.s.nUpdateNewCall == 0 ); } CPPUNIT_ASSERT( !l.empty() ); CPPUNIT_ASSERT( l.insert( v3 )) ; // true - CPPUNIT_ASSERT( l.find( v3.key() )); + CPPUNIT_ASSERT( l.contains( v3.key() )); CPPUNIT_ASSERT( v3.s.nFindCall == 0 ); CPPUNIT_ASSERT( l.find( v3.key(), find_functor() )); CPPUNIT_ASSERT( v3.s.nFindCall == 1 ); CPPUNIT_ASSERT( l.unlink( v2 ) ); - CPPUNIT_ASSERT( l.find( v1.key() )) ; // true - CPPUNIT_ASSERT( !l.find( v2.key() )) ; // true - CPPUNIT_ASSERT( l.find( v3.key() )) ; // true + CPPUNIT_ASSERT( l.contains( v1.key() )) ; // true + CPPUNIT_ASSERT( !l.contains( v2.key() )) ; // true + CPPUNIT_ASSERT( l.contains( v3.key() )) ; // true CPPUNIT_ASSERT( !l.empty() ); CPPUNIT_ASSERT( !l.unlink( v2 ) ); @@ -294,15 +294,15 @@ namespace ordlist { CPPUNIT_ASSERT( l.unlink( v1 ) ); CPPUNIT_ASSERT( !l.unlink( v1 ) ); - CPPUNIT_ASSERT( !l.find( v1.key() )); - CPPUNIT_ASSERT( !l.find( v2.key() )); - CPPUNIT_ASSERT( l.find( v3.key() )); + CPPUNIT_ASSERT( !l.contains( v1.key() )); + CPPUNIT_ASSERT( !l.contains( v2.key() )); + CPPUNIT_ASSERT( l.contains( v3.key() )); CPPUNIT_ASSERT( !l.empty() ); CPPUNIT_ASSERT( !l.unlink( v1 ) ); CPPUNIT_ASSERT( !l.unlink( v2 ) ); CPPUNIT_ASSERT( l.unlink( v3 ) ); - CPPUNIT_ASSERT( !l.find_with( v1.key(), less() )); + CPPUNIT_ASSERT( !l.contains( v1.key(), less() )); CPPUNIT_ASSERT( !l.find_with( v2.key(), less(), find_functor() )); CPPUNIT_ASSERT( !l.find( v3.key(), find_functor() )); CPPUNIT_ASSERT( l.empty() ); @@ -314,27 +314,27 @@ namespace ordlist { OrdList::gc::force_dispose(); stat s( v3.s ); - ret = l.ensure( v3, ensure_functor() ); + ret = l.update( v3, update_functor() ); CPPUNIT_ASSERT( ret.first ); CPPUNIT_ASSERT( ret.second ); - CPPUNIT_ASSERT( v3.s.nEnsureNewCall == s.nEnsureNewCall + 1); - CPPUNIT_ASSERT( v3.s.nEnsureExistsCall == s.nEnsureExistsCall ); + CPPUNIT_ASSERT( v3.s.nUpdateNewCall == s.nUpdateNewCall + 1); + CPPUNIT_ASSERT( v3.s.nUpdateExistsCall == s.nUpdateExistsCall ); CPPUNIT_ASSERT( !l.empty() ); s = v2.s; - ret = l.ensure( v2, ensure_functor() ); + ret = l.update( v2, update_functor() ); CPPUNIT_ASSERT( ret.first ); CPPUNIT_ASSERT( ret.second ); - CPPUNIT_ASSERT( v2.s.nEnsureNewCall == s.nEnsureNewCall + 1); - CPPUNIT_ASSERT( v2.s.nEnsureExistsCall == s.nEnsureExistsCall ); + CPPUNIT_ASSERT( v2.s.nUpdateNewCall == s.nUpdateNewCall + 1); + CPPUNIT_ASSERT( v2.s.nUpdateExistsCall == s.nUpdateExistsCall ); CPPUNIT_ASSERT( !l.empty() ); s = v1.s; - ret = l.ensure( v1, ensure_functor() ); + ret = l.update( v1, update_functor() ); CPPUNIT_ASSERT( ret.first ); CPPUNIT_ASSERT( ret.second ); - CPPUNIT_ASSERT( v1.s.nEnsureNewCall == s.nEnsureNewCall + 1); - CPPUNIT_ASSERT( v1.s.nEnsureExistsCall == s.nEnsureExistsCall ); + CPPUNIT_ASSERT( v1.s.nUpdateNewCall == s.nUpdateNewCall + 1); + CPPUNIT_ASSERT( v1.s.nUpdateExistsCall == s.nUpdateExistsCall ); CPPUNIT_ASSERT( !l.empty() ); // Erase test @@ -672,13 +672,13 @@ namespace ordlist { CPPUNIT_ASSERT( l.empty() ); CPPUNIT_ASSERT( l.insert( v1 )) ; // true - CPPUNIT_ASSERT( l.find( v1.key() ) == &v1 ); + CPPUNIT_ASSERT( l.contains( v1.key() ) == &v1 ); CPPUNIT_ASSERT( v1.s.nFindCall == 0 ); CPPUNIT_ASSERT( l.find( v1.key(), find_functor() )); CPPUNIT_ASSERT( v1.s.nFindCall == 1 ); - CPPUNIT_ASSERT( l.find_with( v2.key(), less() ) == nullptr ); + CPPUNIT_ASSERT( l.contains( v2.key(), less() ) == nullptr ); CPPUNIT_ASSERT( !l.find_with( v3.key(), less(), find_functor() )); CPPUNIT_ASSERT( !l.empty() ); @@ -689,42 +689,42 @@ namespace ordlist { CPPUNIT_ASSERT( !l.insert( v )) ; // false } - std::pair ret = l.ensure( v2, ensure_functor() ); + std::pair ret = l.update( v2, update_functor() ); CPPUNIT_ASSERT( ret.first ); CPPUNIT_ASSERT( ret.second ); - CPPUNIT_ASSERT( v2.s.nEnsureNewCall == 1 ); - CPPUNIT_ASSERT( v2.s.nEnsureExistsCall == 0 ); + CPPUNIT_ASSERT( v2.s.nUpdateNewCall == 1 ); + CPPUNIT_ASSERT( v2.s.nUpdateExistsCall == 0 ); //CPPUNIT_ASSERT( !l.insert( v2 )) ; // assertion "is_empty" - CPPUNIT_ASSERT( l.find( v1.key() ) == &v1 ) ; // true + CPPUNIT_ASSERT( l.contains( v1.key() ) == &v1 ) ; // true CPPUNIT_ASSERT( v1.s.nFindCall == 1 ); CPPUNIT_ASSERT( l.find( v1.key(), find_functor() )); CPPUNIT_ASSERT( v1.s.nFindCall == 2 ); - CPPUNIT_ASSERT( l.find( v2.key() ) == &v2 ); + CPPUNIT_ASSERT( l.contains( v2.key() ) == &v2 ); CPPUNIT_ASSERT( v2.s.nFindCall == 0 ); CPPUNIT_ASSERT( l.find( v2.key(), find_functor() )); CPPUNIT_ASSERT( v2.s.nFindCall == 1 ); - CPPUNIT_ASSERT( !l.find( v3.key() )); + CPPUNIT_ASSERT( !l.contains( v3.key() )); { value_type v( v2 ); - ret = l.ensure( v, ensure_functor() ); + ret = l.update( v, update_functor() ); CPPUNIT_ASSERT( ret.first ); CPPUNIT_ASSERT( !ret.second ); - CPPUNIT_ASSERT( v2.s.nEnsureExistsCall == 1 ); - CPPUNIT_ASSERT( v.s.nEnsureExistsCall == 0 && v.s.nEnsureNewCall == 0 ); + CPPUNIT_ASSERT( v2.s.nUpdateExistsCall == 1 ); + CPPUNIT_ASSERT( v.s.nUpdateExistsCall == 0 && v.s.nUpdateNewCall == 0 ); } CPPUNIT_ASSERT( !l.empty() ); CPPUNIT_ASSERT( l.insert( v3 )) ; // true - CPPUNIT_ASSERT( l.find( v3.key() ) == &v3 ); + CPPUNIT_ASSERT( l.contains( v3.key() ) == &v3 ); CPPUNIT_ASSERT( v3.s.nFindCall == 0 ); CPPUNIT_ASSERT( l.find( v3.key(), find_functor() )); diff --git a/tests/test-hdr/list/hdr_lazy.h b/tests/test-hdr/list/hdr_lazy.h index e7fb9bb6..c5834ef4 100644 --- a/tests/test-hdr/list/hdr_lazy.h +++ b/tests/test-hdr/list/hdr_lazy.h @@ -14,13 +14,13 @@ namespace ordlist { { public: struct stat { - int nEnsureExistsCall; - int nEnsureNewCall; + int nUpdateExistsCall; + int nUpdateNewCall; stat() { - nEnsureExistsCall - = nEnsureNewCall + nUpdateExistsCall + = nUpdateNewCall = 0; } }; @@ -202,14 +202,14 @@ namespace ordlist { } }; - struct ensure_functor { + struct update_functor { void operator()( bool /*bNew*/, item& i, int /*n*/ ) { i.nVal = i.nKey * 1024; } }; - static void ensure_func( bool /*bNew*/, item& i, int n ) + static void update_func( bool /*bNew*/, item& i, int n ) { i.nVal = n * 1033; } @@ -283,26 +283,26 @@ namespace ordlist { int i; i = 100; - CPPUNIT_ASSERT( l.find( 100 )); + CPPUNIT_ASSERT( l.contains( 100 )); CPPUNIT_ASSERT( l.find( i, check_value(1033) )); { check_value f(1033); i = 25; - CPPUNIT_ASSERT( l.find_with( 25, lt() )); + CPPUNIT_ASSERT( l.contains( 25, lt() )); CPPUNIT_ASSERT( l.find_with( i, lt(), std::ref( f ) ) ); } i = 50; - CPPUNIT_ASSERT( l.find( 50 )); + CPPUNIT_ASSERT( l.contains( 50 )); CPPUNIT_ASSERT( l.find( i, check_value(1024) )); i = 10; - CPPUNIT_ASSERT( !l.find_with( 10, lt() )); + CPPUNIT_ASSERT( !l.contains( 10, lt() )); CPPUNIT_ASSERT( !l.find_with( i, lt(), dummy_check_value() )); i = 75; - CPPUNIT_ASSERT( !l.find( 75 )); + CPPUNIT_ASSERT( !l.contains( 75 )); CPPUNIT_ASSERT( !l.find( i, dummy_check_value() )); i = 150; - CPPUNIT_ASSERT( !l.find( 150 )); + CPPUNIT_ASSERT( !l.contains( 150 )); CPPUNIT_ASSERT( !l.find( i, dummy_check_value() )); } @@ -312,21 +312,21 @@ namespace ordlist { // and now the list is empty CPPUNIT_ASSERT( l.empty() ); - // Ensure test + // Update test { - std::pair ensureResult; - ensure_functor f; - ensureResult = l.ensure( 100, ensure_functor() ); - CPPUNIT_ASSERT( ensureResult.first ); - CPPUNIT_ASSERT( ensureResult.second ); + std::pair updateResult; + update_functor f; + updateResult = l.update( 100, update_functor() ); + CPPUNIT_ASSERT( updateResult.first ); + CPPUNIT_ASSERT( updateResult.second ); - ensureResult = l.ensure( 200, std::ref( f ) ); - CPPUNIT_ASSERT( ensureResult.first ); - CPPUNIT_ASSERT( ensureResult.second ); + updateResult = l.update( 200, std::ref( f ) ); + CPPUNIT_ASSERT( updateResult.first ); + CPPUNIT_ASSERT( updateResult.second ); - ensureResult = l.ensure( 50, ensure_func ); - CPPUNIT_ASSERT( ensureResult.first ); - CPPUNIT_ASSERT( ensureResult.second ); + updateResult = l.update( 50, update_func ); + CPPUNIT_ASSERT( updateResult.first ); + CPPUNIT_ASSERT( updateResult.second ); int i; i = 100; @@ -336,16 +336,16 @@ namespace ordlist { i = 200; CPPUNIT_ASSERT( l.find( i, check_value(1024) )); - // ensure existing key - ensureResult = l.ensure( 200, ensure_func ); - CPPUNIT_ASSERT( ensureResult.first ); - CPPUNIT_ASSERT( !ensureResult.second ); + // update existing key + updateResult = l.update( 200, update_func ); + CPPUNIT_ASSERT( updateResult.first ); + CPPUNIT_ASSERT( !updateResult.second ); i = 200; CPPUNIT_ASSERT( l.find( i, check_value(1033) )); - ensureResult = l.ensure( 50, ensure_functor() ); - CPPUNIT_ASSERT( ensureResult.first ); - CPPUNIT_ASSERT( !ensureResult.second ); + updateResult = l.update( 50, update_functor() ); + CPPUNIT_ASSERT( updateResult.first ); + CPPUNIT_ASSERT( !updateResult.second ); i = 50; CPPUNIT_ASSERT( l.find( i, check_value(1024) )); } @@ -658,7 +658,7 @@ namespace ordlist { { typedef OrdList list; typedef typename list::value_type value_type; - typedef std::pair ensure_result; + typedef std::pair update_result; typename list::iterator it; @@ -667,31 +667,31 @@ namespace ordlist { CPPUNIT_ASSERT( l.insert(50) != l.end() ); CPPUNIT_ASSERT( !l.empty() ); - ensure_result eres = l.ensure( item(100, 33) ); + update_result eres = l.update( item(100, 33) ); CPPUNIT_ASSERT( eres.second ); CPPUNIT_ASSERT( eres.first != l.end() ); CPPUNIT_ASSERT( l.insert( item(150) ) != l.end() ); CPPUNIT_ASSERT( l.insert(100) == l.end() ); - eres = l.ensure( item(50, 33) ); + eres = l.update( item(50, 33) ); CPPUNIT_ASSERT( !eres.second ); CPPUNIT_ASSERT( eres.first->nVal == eres.first->nKey * 2 ); eres.first->nVal = 63; - it = l.find( 33 ); + it = l.contains( 33 ); CPPUNIT_ASSERT( it == l.end() ); - it = l.find( 50 ); + it = l.contains( 50 ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it->nKey == 50 ); CPPUNIT_ASSERT( it->nVal == 63 ); - it = l.find( 100 ); + it = l.contains( 100 ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it->nKey == 100 ); CPPUNIT_ASSERT( it->nVal == 33 ); - it = l.find_with( 150, lt() ); + it = l.contains( 150, lt() ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it->nKey == 150 ); CPPUNIT_ASSERT( it->nVal == it->nKey * 2 ); @@ -709,17 +709,17 @@ namespace ordlist { CPPUNIT_ASSERT( l.emplace( 501, 2 ) == l.end()); CPPUNIT_ASSERT( l.emplace( 251, 10) == l.end()); - it = l.find( 501 ); + it = l.contains( 501 ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it->nKey == 501 ); CPPUNIT_ASSERT( it->nVal == 501 * 2 ); - it = l.find_with( 251, lt() ); + it = l.contains( 251, lt() ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it->nKey == 251 ); CPPUNIT_ASSERT( it->nVal == 152 ); - it = l.find( 1001 ); + it = l.contains( 1001 ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it->nKey == 1001 ); CPPUNIT_ASSERT( it->nVal == 1001 * 2 ); @@ -756,7 +756,7 @@ namespace ordlist { { typedef UnordList list; typedef typename list::value_type value_type; - typedef std::pair ensure_result; + typedef std::pair update_result; typename list::iterator it; @@ -765,31 +765,31 @@ namespace ordlist { CPPUNIT_ASSERT( l.insert(50) != l.end() ); CPPUNIT_ASSERT( !l.empty() ); - ensure_result eres = l.ensure( item(100, 33) ); + update_result eres = l.update( item(100, 33) ); CPPUNIT_ASSERT( eres.second ); CPPUNIT_ASSERT( eres.first != l.end() ); CPPUNIT_ASSERT( l.insert( item(150) ) != l.end() ); CPPUNIT_ASSERT( l.insert(100) == l.end() ); - eres = l.ensure( item(50, 33) ); + eres = l.update( item(50, 33) ); CPPUNIT_ASSERT( !eres.second ); CPPUNIT_ASSERT( eres.first->nVal == eres.first->nKey * 2 ); eres.first->nVal = 63; - it = l.find( 33 ); + it = l.contains( 33 ); CPPUNIT_ASSERT( it == l.end() ); - it = l.find( 50 ); + it = l.contains( 50 ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it->nKey == 50 ); CPPUNIT_ASSERT( it->nVal == 63 ); - it = l.find( 100 ); + it = l.contains( 100 ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it->nKey == 100 ); CPPUNIT_ASSERT( it->nVal == 33 ); - it = l.find_with( 150, equal_to() ); + it = l.contains( 150, equal_to() ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it->nKey == 150 ); CPPUNIT_ASSERT( it->nVal == it->nKey * 2 ); @@ -807,12 +807,12 @@ namespace ordlist { CPPUNIT_ASSERT( l.emplace( 501, 2 ) == l.end()); CPPUNIT_ASSERT( l.emplace( 251, 10) == l.end()); - it = l.find( 501 ); + it = l.contains( 501 ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it->nKey == 501 ); CPPUNIT_ASSERT( it->nVal == 501 * 2 ); - it = l.find( 1001 ); + it = l.contains( 1001 ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it->nKey == 1001 ); CPPUNIT_ASSERT( it->nVal == 1001 * 2 ); diff --git a/tests/test-hdr/list/hdr_lazy_kv.h b/tests/test-hdr/list/hdr_lazy_kv.h index 4eeef280..ad2bb521 100644 --- a/tests/test-hdr/list/hdr_lazy_kv.h +++ b/tests/test-hdr/list/hdr_lazy_kv.h @@ -75,7 +75,7 @@ namespace ordlist { } }; - struct ensure_functor { + struct update_functor { template void operator()( bool /*bNew*/, T& pair ) { @@ -124,17 +124,17 @@ namespace ordlist { CPPUNIT_ASSERT( l.empty() ); // insert / find test - CPPUNIT_ASSERT( !l.find( 100 )); + CPPUNIT_ASSERT( !l.contains( 100 )); CPPUNIT_ASSERT( l.insert( 100 )); CPPUNIT_ASSERT( !l.empty() ); - CPPUNIT_ASSERT( l.find( 100 )); + CPPUNIT_ASSERT( l.contains( 100 )); check_value chk(0); CPPUNIT_ASSERT( l.find( 100, std::ref( chk ) ) ); - CPPUNIT_ASSERT( !l.find_with( 50, lt() )); + CPPUNIT_ASSERT( !l.contains( 50, lt() )); CPPUNIT_ASSERT( l.insert( 50, 500 )); - CPPUNIT_ASSERT( l.find_with( 50, lt() )); + CPPUNIT_ASSERT( l.contains( 50, lt() )); CPPUNIT_ASSERT( !l.insert( 50, 5 )); chk.m_nExpected = 500; CPPUNIT_ASSERT( l.find( 50, std::ref( chk ) ) ); @@ -142,9 +142,9 @@ namespace ordlist { CPPUNIT_ASSERT( l.find( 100, std::ref( chk ) ) ); CPPUNIT_ASSERT( !l.empty() ); - CPPUNIT_ASSERT( !l.find( 150 )); + CPPUNIT_ASSERT( !l.contains( 150 )); CPPUNIT_ASSERT( l.insert_with( 150, insert_functor() )); - CPPUNIT_ASSERT( l.find( 150 )); + CPPUNIT_ASSERT( l.contains( 150 )); chk.m_nExpected = 1500; CPPUNIT_ASSERT( l.find_with( 150, lt(), std::ref( chk ) ) ); chk.m_nExpected = 0; @@ -158,29 +158,29 @@ namespace ordlist { CPPUNIT_ASSERT( !l.erase( 500 )); CPPUNIT_ASSERT( !l.empty() ); - CPPUNIT_ASSERT( l.find( 50 )); + CPPUNIT_ASSERT( l.contains( 50 )); { erase_functor ef; l.erase( 50, std::ref( ef ) ); CPPUNIT_ASSERT( ef.nKey == 50 ); CPPUNIT_ASSERT( ef.nVal == 500 ); } - CPPUNIT_ASSERT( !l.find( 50 )); + CPPUNIT_ASSERT( !l.contains( 50 )); - // ensure test - std::pair bEnsureResult; - bEnsureResult = l.ensure( 100, ensure_functor() ); - CPPUNIT_ASSERT( bEnsureResult.first ); - CPPUNIT_ASSERT( !bEnsureResult.second ); + // update test + std::pair bUpdateResult; + bUpdateResult = l.update( 100, update_functor() ); + CPPUNIT_ASSERT( bUpdateResult.first ); + CPPUNIT_ASSERT( !bUpdateResult.second ); chk.m_nExpected = 5000; CPPUNIT_ASSERT( l.find( 100, std::ref( chk ) ) ); { - ensure_functor ef; - bEnsureResult = l.ensure( 50, std::ref( ef ) ); + update_functor ef; + bUpdateResult = l.update( 50, std::ref( ef ) ); } - CPPUNIT_ASSERT( bEnsureResult.first ); - CPPUNIT_ASSERT( bEnsureResult.second ); + CPPUNIT_ASSERT( bUpdateResult.first ); + CPPUNIT_ASSERT( bUpdateResult.second ); chk.m_nExpected = 2500; CPPUNIT_ASSERT( l.find( 50, std::ref( chk ) ) ); @@ -480,73 +480,73 @@ namespace ordlist { CPPUNIT_ASSERT( l.empty() ); // insert / find test - CPPUNIT_ASSERT( l.find( 100 ) == l.end() ); + CPPUNIT_ASSERT( l.contains( 100 ) == l.end() ); CPPUNIT_ASSERT( l.insert( 100 ) != l.end() ); CPPUNIT_ASSERT( !l.empty() ); - it = l.find( 100 ); + it = l.contains( 100 ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it.key() == 100 ); CPPUNIT_ASSERT( it.val().m_val == 0 ); - CPPUNIT_ASSERT( l.find_with( 50, lt() ) == l.end() ); + CPPUNIT_ASSERT( l.contains( 50, lt() ) == l.end() ); CPPUNIT_ASSERT( l.insert( 50, 500 ) != l.end()); - it = l.find( 50 ); + it = l.contains( 50 ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it.key() == 50 ); CPPUNIT_ASSERT( it.val().m_val == 500 ); CPPUNIT_ASSERT( l.insert( 50, 5 ) == l.end() ); - it = l.find( 50 ); + it = l.contains( 50 ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it.key() == 50 ); CPPUNIT_ASSERT( it.val().m_val == 500 ); CPPUNIT_ASSERT( !l.empty() ); - CPPUNIT_ASSERT( l.find( 150 ) == l.end() ); + CPPUNIT_ASSERT( l.contains( 150 ) == l.end() ); CPPUNIT_ASSERT( l.insert_with( 150, insert_functor() ) != l.end() ); - it = l.find( 150 ); + it = l.contains( 150 ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it.key() == 150 ); CPPUNIT_ASSERT( it.val().m_val == 1500 ); - it = l.find( 100 ); + it = l.contains( 100 ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it.key() == 100 ); CPPUNIT_ASSERT( it.val().m_val == 0 ); - it = l.find( 50 ); + it = l.contains( 50 ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it.key() == 50 ); CPPUNIT_ASSERT( it.val().m_val == 500 ); it.val().m_val = 25; - it = l.find( 50 ); + it = l.contains( 50 ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it.key() == 50 ); CPPUNIT_ASSERT( it.val().m_val == 25 ); CPPUNIT_ASSERT( !l.empty() ); - // ensure existing item - std::pair ensureResult; - ensureResult = l.ensure( 100 ); - CPPUNIT_ASSERT( !ensureResult.second ); - CPPUNIT_ASSERT( ensureResult.first.key() == 100 ); - CPPUNIT_ASSERT( ensureResult.first.val().m_val == 0 ); - ensureResult.first.val().m_val = 5; - it = l.find( 100 ); + // update existing item + std::pair updateResult; + updateResult = l.update( 100 ); + CPPUNIT_ASSERT( !updateResult.second ); + CPPUNIT_ASSERT( updateResult.first.key() == 100 ); + CPPUNIT_ASSERT( updateResult.first.val().m_val == 0 ); + updateResult.first.val().m_val = 5; + it = l.contains( 100 ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it.key() == 100 ); CPPUNIT_ASSERT( it.val().m_val == 5 ); CPPUNIT_ASSERT( !l.empty() ); - // ensure new item - ensureResult = l.ensure( 1000 ); - CPPUNIT_ASSERT( ensureResult.second ); - CPPUNIT_ASSERT( ensureResult.first.key() == 1000 ); - CPPUNIT_ASSERT( ensureResult.first.val().m_val == 0 ); - ensureResult.first.val().m_val = 33; - ensureResult = l.ensure( 1000 ); - CPPUNIT_ASSERT( !ensureResult.second ); - CPPUNIT_ASSERT( ensureResult.first.key() == 1000 ); - CPPUNIT_ASSERT( ensureResult.first.val().m_val == 33 ); + // update new item + updateResult = l.update( 1000 ); + CPPUNIT_ASSERT( updateResult.second ); + CPPUNIT_ASSERT( updateResult.first.key() == 1000 ); + CPPUNIT_ASSERT( updateResult.first.val().m_val == 0 ); + updateResult.first.val().m_val = 33; + updateResult = l.update( 1000 ); + CPPUNIT_ASSERT( !updateResult.second ); + CPPUNIT_ASSERT( updateResult.first.key() == 1000 ); + CPPUNIT_ASSERT( updateResult.first.val().m_val == 33 ); // clear test l.clear(); @@ -560,12 +560,12 @@ namespace ordlist { CPPUNIT_ASSERT( l.emplace( 501, 2 ) == l.end()); CPPUNIT_ASSERT( l.emplace( 251, 10) == l.end()); - it = l.find(501); + it = l.contains(501); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it.key() == 501 ); CPPUNIT_ASSERT( it.val().m_val == 0 ); - it = l.find(251); + it = l.contains(251); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it.key() == 251 ); CPPUNIT_ASSERT( it.val().m_val == 152 ); @@ -616,7 +616,7 @@ namespace ordlist { // Check that we have visited all items for ( int i = 0; i < nCount; ++i ) { - it = l.find( i ); + it = l.contains( i ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it.key() == i ); CPPUNIT_ASSERT( it.val().m_val == i * 3 ); @@ -662,73 +662,73 @@ namespace ordlist { CPPUNIT_ASSERT( l.empty() ); // insert / find test - CPPUNIT_ASSERT( l.find( 100 ) == l.end() ); + CPPUNIT_ASSERT( l.contains( 100 ) == l.end() ); CPPUNIT_ASSERT( l.insert( 100 ) != l.end() ); CPPUNIT_ASSERT( !l.empty() ); - it = l.find( 100 ); + it = l.contains( 100 ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it.key() == 100 ); CPPUNIT_ASSERT( it.val().m_val == 0 ); - CPPUNIT_ASSERT( l.find_with( 50, eq() ) == l.end() ); + CPPUNIT_ASSERT( l.contains( 50, eq() ) == l.end() ); CPPUNIT_ASSERT( l.insert( 50, 500 ) != l.end()); - it = l.find( 50 ); + it = l.contains( 50 ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it.key() == 50 ); CPPUNIT_ASSERT( it.val().m_val == 500 ); CPPUNIT_ASSERT( l.insert( 50, 5 ) == l.end() ); - it = l.find( 50 ); + it = l.contains( 50 ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it.key() == 50 ); CPPUNIT_ASSERT( it.val().m_val == 500 ); CPPUNIT_ASSERT( !l.empty() ); - CPPUNIT_ASSERT( l.find( 150 ) == l.end() ); + CPPUNIT_ASSERT( l.contains( 150 ) == l.end() ); CPPUNIT_ASSERT( l.insert_with( 150, insert_functor() ) != l.end() ); - it = l.find( 150 ); + it = l.contains( 150 ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it.key() == 150 ); CPPUNIT_ASSERT( it.val().m_val == 1500 ); - it = l.find( 100 ); + it = l.contains( 100 ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it.key() == 100 ); CPPUNIT_ASSERT( it.val().m_val == 0 ); - it = l.find( 50 ); + it = l.contains( 50 ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it.key() == 50 ); CPPUNIT_ASSERT( it.val().m_val == 500 ); it.val().m_val = 25; - it = l.find( 50 ); + it = l.contains( 50 ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it.key() == 50 ); CPPUNIT_ASSERT( it.val().m_val == 25 ); CPPUNIT_ASSERT( !l.empty() ); - // ensure existing item - std::pair ensureResult; - ensureResult = l.ensure( 100 ); - CPPUNIT_ASSERT( !ensureResult.second ); - CPPUNIT_ASSERT( ensureResult.first.key() == 100 ); - CPPUNIT_ASSERT( ensureResult.first.val().m_val == 0 ); - ensureResult.first.val().m_val = 5; - it = l.find( 100 ); + // update existing item + std::pair updateResult; + updateResult = l.update( 100 ); + CPPUNIT_ASSERT( !updateResult.second ); + CPPUNIT_ASSERT( updateResult.first.key() == 100 ); + CPPUNIT_ASSERT( updateResult.first.val().m_val == 0 ); + updateResult.first.val().m_val = 5; + it = l.contains( 100 ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it.key() == 100 ); CPPUNIT_ASSERT( it.val().m_val == 5 ); CPPUNIT_ASSERT( !l.empty() ); - // ensure new item - ensureResult = l.ensure( 1000 ); - CPPUNIT_ASSERT( ensureResult.second ); - CPPUNIT_ASSERT( ensureResult.first.key() == 1000 ); - CPPUNIT_ASSERT( ensureResult.first.val().m_val == 0 ); - ensureResult.first.val().m_val = 33; - ensureResult = l.ensure( 1000 ); - CPPUNIT_ASSERT( !ensureResult.second ); - CPPUNIT_ASSERT( ensureResult.first.key() == 1000 ); - CPPUNIT_ASSERT( ensureResult.first.val().m_val == 33 ); + // update new item + updateResult = l.update( 1000 ); + CPPUNIT_ASSERT( updateResult.second ); + CPPUNIT_ASSERT( updateResult.first.key() == 1000 ); + CPPUNIT_ASSERT( updateResult.first.val().m_val == 0 ); + updateResult.first.val().m_val = 33; + updateResult = l.update( 1000 ); + CPPUNIT_ASSERT( !updateResult.second ); + CPPUNIT_ASSERT( updateResult.first.key() == 1000 ); + CPPUNIT_ASSERT( updateResult.first.val().m_val == 33 ); // clear test l.clear(); @@ -742,12 +742,12 @@ namespace ordlist { CPPUNIT_ASSERT( l.emplace( 501, 2 ) == l.end()); CPPUNIT_ASSERT( l.emplace( 251, 10) == l.end()); - it = l.find(501); + it = l.contains(501); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it.key() == 501 ); CPPUNIT_ASSERT( it.val().m_val == 0 ); - it = l.find(251); + it = l.contains(251); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it.key() == 251 ); CPPUNIT_ASSERT( it.val().m_val == 152 ); @@ -798,7 +798,7 @@ namespace ordlist { // Check that we have visited all items for ( int i = 0; i < nCount; ++i ) { - it = l.find( i ); + it = l.contains( i ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it.key() == i ); CPPUNIT_ASSERT( it.val().m_val == i * 3 ); diff --git a/tests/test-hdr/list/hdr_michael.h b/tests/test-hdr/list/hdr_michael.h index ec1307aa..5e002b66 100644 --- a/tests/test-hdr/list/hdr_michael.h +++ b/tests/test-hdr/list/hdr_michael.h @@ -14,13 +14,13 @@ namespace ordlist { { public: struct stat { - int nEnsureExistsCall; - int nEnsureNewCall; + int nUpdateExistsCall; + int nUpdateNewCall; stat() { - nEnsureExistsCall - = nEnsureNewCall + nUpdateExistsCall + = nUpdateNewCall = 0; } }; @@ -182,14 +182,14 @@ namespace ordlist { } }; - struct ensure_functor { + struct update_functor { void operator()( bool /*bNew*/, item& i, int /*n*/ ) { i.nVal = i.nKey * 1024; } }; - static void ensure_func( bool /*bNew*/, item& i, int n ) + static void update_func( bool /*bNew*/, item& i, int n ) { i.nVal = n * 1033; } @@ -262,26 +262,26 @@ namespace ordlist { { int i; i = 100; - CPPUNIT_ASSERT( l.find( 100 )); + CPPUNIT_ASSERT( l.contains( 100 )); CPPUNIT_ASSERT( l.find( i, check_value(1033) )); { check_value f(1033); i = 25; - CPPUNIT_ASSERT( l.find_with( 25, lt() )); + CPPUNIT_ASSERT( l.contains( 25, lt() )); CPPUNIT_ASSERT( l.find_with( i, lt(), std::ref( f ) ) ); } i = 50; - CPPUNIT_ASSERT( l.find( 50 )); + CPPUNIT_ASSERT( l.contains( 50 )); CPPUNIT_ASSERT( l.find( i, check_value(1024) )); i = 10; - CPPUNIT_ASSERT( !l.find_with( 10, lt() )); + CPPUNIT_ASSERT( !l.contains( 10, lt() )); CPPUNIT_ASSERT( !l.find_with( i, lt(), dummy_check_value() )); i = 75; - CPPUNIT_ASSERT( !l.find( 75 )); + CPPUNIT_ASSERT( !l.contains( 75 )); CPPUNIT_ASSERT( !l.find( i, dummy_check_value() )); i = 150; - CPPUNIT_ASSERT( !l.find( 150 )); + CPPUNIT_ASSERT( !l.contains( 150 )); CPPUNIT_ASSERT( !l.find( i, dummy_check_value() )); } @@ -291,21 +291,21 @@ namespace ordlist { // and now the list is empty CPPUNIT_ASSERT( l.empty() ); - // Ensure test + // Update test { - std::pair ensureResult; - ensure_functor f; - ensureResult = l.ensure( 100, ensure_functor() ); - CPPUNIT_ASSERT( ensureResult.first ); - CPPUNIT_ASSERT( ensureResult.second ); + std::pair updateResult; + update_functor f; + updateResult = l.update( 100, update_functor() ); + CPPUNIT_ASSERT( updateResult.first ); + CPPUNIT_ASSERT( updateResult.second ); - ensureResult = l.ensure( 200, std::ref( f ) ); - CPPUNIT_ASSERT( ensureResult.first ); - CPPUNIT_ASSERT( ensureResult.second ); + updateResult = l.update( 200, std::ref( f ) ); + CPPUNIT_ASSERT( updateResult.first ); + CPPUNIT_ASSERT( updateResult.second ); - ensureResult = l.ensure( 50, ensure_func ); - CPPUNIT_ASSERT( ensureResult.first ); - CPPUNIT_ASSERT( ensureResult.second ); + updateResult = l.update( 50, update_func ); + CPPUNIT_ASSERT( updateResult.first ); + CPPUNIT_ASSERT( updateResult.second ); int i; i = 100; @@ -315,16 +315,16 @@ namespace ordlist { i = 200; CPPUNIT_ASSERT( l.find( i, check_value(1024) )); - // ensure existing key - ensureResult = l.ensure( 200, ensure_func ); - CPPUNIT_ASSERT( ensureResult.first ); - CPPUNIT_ASSERT( !ensureResult.second ); + // update existing key + updateResult = l.update( 200, update_func ); + CPPUNIT_ASSERT( updateResult.first ); + CPPUNIT_ASSERT( !updateResult.second ); i = 200; CPPUNIT_ASSERT( l.find( i, check_value(1033) )); - ensureResult = l.ensure( 50, ensure_functor() ); - CPPUNIT_ASSERT( ensureResult.first ); - CPPUNIT_ASSERT( !ensureResult.second ); + updateResult = l.update( 50, update_functor() ); + CPPUNIT_ASSERT( updateResult.first ); + CPPUNIT_ASSERT( !updateResult.second ); i = 50; CPPUNIT_ASSERT( l.find( i, check_value(1024) )); } @@ -644,7 +644,7 @@ namespace ordlist { { typedef OrdList list; typedef typename list::value_type value_type; - typedef std::pair ensure_result; + typedef std::pair update_result; typename list::iterator it; @@ -653,31 +653,31 @@ namespace ordlist { CPPUNIT_ASSERT( l.insert(50) != l.end() ); CPPUNIT_ASSERT( !l.empty() ); - ensure_result eres = l.ensure( item(100, 33) ); + update_result eres = l.update( item(100, 33) ); CPPUNIT_ASSERT( eres.second ); CPPUNIT_ASSERT( eres.first != l.end() ); CPPUNIT_ASSERT( l.insert( item(150) ) != l.end() ); CPPUNIT_ASSERT( l.insert(100) == l.end() ); - eres = l.ensure( item(50, 33) ); + eres = l.update( item(50, 33) ); CPPUNIT_ASSERT( !eres.second ); CPPUNIT_ASSERT( eres.first->nVal == eres.first->nKey * 2 ); eres.first->nVal = 63; - it = l.find( 33 ); + it = l.contains( 33 ); CPPUNIT_ASSERT( it == l.end() ); - it = l.find( 50 ); + it = l.contains( 50 ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it->nKey == 50 ); CPPUNIT_ASSERT( it->nVal == 63 ); - it = l.find_with( 100, lt() ); + it = l.contains( 100, lt() ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it->nKey == 100 ); CPPUNIT_ASSERT( it->nVal == 33 ); - it = l.find( 150 ); + it = l.contains( 150 ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it->nKey == 150 ); CPPUNIT_ASSERT( it->nVal == it->nKey * 2 ); @@ -695,17 +695,17 @@ namespace ordlist { CPPUNIT_ASSERT( l.emplace( 501, 2 ) == l.end() ); CPPUNIT_ASSERT( l.emplace( 251, 10) == l.end() ); - it = l.find( 501 ); + it = l.contains( 501 ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it->nKey == 501 ); CPPUNIT_ASSERT( it->nVal == 501 * 2 ); - it = l.find( 251 ); + it = l.contains( 251 ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it->nKey == 251 ); CPPUNIT_ASSERT( it->nVal == 152 ); - it = l.find( 1001 ); + it = l.contains( 1001 ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it->nKey == 1001 ); CPPUNIT_ASSERT( it->nVal == 1001 * 2 ); diff --git a/tests/test-hdr/list/hdr_michael_kv.h b/tests/test-hdr/list/hdr_michael_kv.h index 07f8d19c..c9356bf4 100644 --- a/tests/test-hdr/list/hdr_michael_kv.h +++ b/tests/test-hdr/list/hdr_michael_kv.h @@ -67,7 +67,7 @@ namespace ordlist { } }; - struct ensure_functor { + struct update_functor { template void operator()( bool /*bNew*/, T& pair ) { @@ -115,18 +115,18 @@ namespace ordlist { CPPUNIT_ASSERT( l.empty() ); - // insert / find test - CPPUNIT_ASSERT( !l.find( 100 )); + // insert / contains test + CPPUNIT_ASSERT( !l.contains( 100 )); CPPUNIT_ASSERT( l.insert( 100 )); CPPUNIT_ASSERT( !l.empty() ); - CPPUNIT_ASSERT( l.find( 100 )); + CPPUNIT_ASSERT( l.contains( 100 )); check_value chk(0); CPPUNIT_ASSERT( l.find( 100, std::ref( chk ) ) ); - CPPUNIT_ASSERT( !l.find_with( 50, lt() )); + CPPUNIT_ASSERT( !l.contains( 50, lt() )); CPPUNIT_ASSERT( l.insert( 50, 500 )); - CPPUNIT_ASSERT( l.find_with( 50, lt() )); + CPPUNIT_ASSERT( l.contains( 50, lt() )); CPPUNIT_ASSERT( !l.insert( 50, 5 )); chk.m_nExpected = 500; CPPUNIT_ASSERT( l.find_with( 50, lt(), std::ref( chk ) ) ); @@ -134,9 +134,9 @@ namespace ordlist { CPPUNIT_ASSERT( l.find_with( 100, lt(), std::ref( chk ) ) ); CPPUNIT_ASSERT( !l.empty() ); - CPPUNIT_ASSERT( !l.find( 150 )); + CPPUNIT_ASSERT( !l.contains( 150 )); CPPUNIT_ASSERT( l.insert_with( 150, insert_functor() )); - CPPUNIT_ASSERT( l.find( 150 )); + CPPUNIT_ASSERT( l.contains( 150 )); chk.m_nExpected = 1500; CPPUNIT_ASSERT( l.find( 150, std::ref( chk ) ) ); chk.m_nExpected = 0; @@ -150,29 +150,29 @@ namespace ordlist { CPPUNIT_ASSERT( !l.erase( 500 )); CPPUNIT_ASSERT( !l.empty() ); - CPPUNIT_ASSERT( l.find( 50 )); + CPPUNIT_ASSERT( l.contains( 50 )); { erase_functor ef; l.erase( 50, std::ref( ef ) ); CPPUNIT_ASSERT( ef.nKey == 50 ); CPPUNIT_ASSERT( ef.nVal == 500 ); } - CPPUNIT_ASSERT( !l.find( 50 )); + CPPUNIT_ASSERT( !l.contains( 50 )); - // ensure test - std::pair bEnsureResult; - bEnsureResult = l.ensure( 100, ensure_functor() ); - CPPUNIT_ASSERT( bEnsureResult.first ); - CPPUNIT_ASSERT( !bEnsureResult.second ); + // update test + std::pair bupdateResult; + bupdateResult = l.update( 100, update_functor() ); + CPPUNIT_ASSERT( bupdateResult.first ); + CPPUNIT_ASSERT( !bupdateResult.second ); chk.m_nExpected = 5000; CPPUNIT_ASSERT( l.find( 100, std::ref( chk ) ) ); { - ensure_functor ef; - bEnsureResult = l.ensure( 50, std::ref( ef ) ); + update_functor ef; + bupdateResult = l.update( 50, std::ref( ef ) ); } - CPPUNIT_ASSERT( bEnsureResult.first ); - CPPUNIT_ASSERT( bEnsureResult.second ); + CPPUNIT_ASSERT( bupdateResult.first ); + CPPUNIT_ASSERT( bupdateResult.second ); chk.m_nExpected = 2500; CPPUNIT_ASSERT( l.find( 50, std::ref( chk ) ) ); @@ -487,73 +487,73 @@ namespace ordlist { CPPUNIT_ASSERT( l.empty() ); // insert / find test - CPPUNIT_ASSERT( l.find( 100 ) == l.end() ); + CPPUNIT_ASSERT( l.contains( 100 ) == l.end() ); CPPUNIT_ASSERT( l.insert( 100 ) != l.end() ); CPPUNIT_ASSERT( !l.empty() ); - it = l.find_with( 100, lt() ); + it = l.contains( 100, lt() ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it.key() == 100 ); CPPUNIT_ASSERT( it.val().m_val == 0 ); - CPPUNIT_ASSERT( l.find_with( 50, lt() ) == l.end() ); + CPPUNIT_ASSERT( l.contains( 50, lt() ) == l.end() ); CPPUNIT_ASSERT( l.insert( 50, 500 ) != l.end()); - it = l.find( 50 ); + it = l.contains( 50 ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it.key() == 50 ); CPPUNIT_ASSERT( it.val().m_val == 500 ); CPPUNIT_ASSERT( l.insert( 50, 5 ) == l.end() ); - it = l.find( 50 ); + it = l.contains( 50 ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it.key() == 50 ); CPPUNIT_ASSERT( it.val().m_val == 500 ); CPPUNIT_ASSERT( !l.empty() ); - CPPUNIT_ASSERT( l.find( 150 ) == l.end() ); + CPPUNIT_ASSERT( l.contains( 150 ) == l.end() ); CPPUNIT_ASSERT( l.insert_with( 150, insert_functor() ) != l.end() ); - it = l.find( 150 ); + it = l.contains( 150 ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it.key() == 150 ); CPPUNIT_ASSERT( it.val().m_val == 1500 ); - it = l.find( 100 ); + it = l.contains( 100 ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it.key() == 100 ); CPPUNIT_ASSERT( it.val().m_val == 0 ); - it = l.find( 50 ); + it = l.contains( 50 ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it.key() == 50 ); CPPUNIT_ASSERT( it.val().m_val == 500 ); it.val().m_val = 25; - it = l.find( 50 ); + it = l.contains( 50 ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it.key() == 50 ); CPPUNIT_ASSERT( it.val().m_val == 25 ); CPPUNIT_ASSERT( !l.empty() ); - // ensure existing item - std::pair ensureResult; - ensureResult = l.ensure( 100 ); - CPPUNIT_ASSERT( !ensureResult.second ); - CPPUNIT_ASSERT( ensureResult.first.key() == 100 ); - CPPUNIT_ASSERT( ensureResult.first.val().m_val == 0 ); - ensureResult.first.val().m_val = 5; - it = l.find( 100 ); + // update existing item + std::pair updateResult; + updateResult = l.update( 100 ); + CPPUNIT_ASSERT( !updateResult.second ); + CPPUNIT_ASSERT( updateResult.first.key() == 100 ); + CPPUNIT_ASSERT( updateResult.first.val().m_val == 0 ); + updateResult.first.val().m_val = 5; + it = l.contains( 100 ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it.key() == 100 ); CPPUNIT_ASSERT( it.val().m_val == 5 ); CPPUNIT_ASSERT( !l.empty() ); - // ensure new item - ensureResult = l.ensure( 1000 ); - CPPUNIT_ASSERT( ensureResult.second ); - CPPUNIT_ASSERT( ensureResult.first.key() == 1000 ); - CPPUNIT_ASSERT( ensureResult.first.val().m_val == 0 ); - ensureResult.first.val().m_val = 33; - ensureResult = l.ensure( 1000 ); - CPPUNIT_ASSERT( !ensureResult.second ); - CPPUNIT_ASSERT( ensureResult.first.key() == 1000 ); - CPPUNIT_ASSERT( ensureResult.first.val().m_val == 33 ); + // update new item + updateResult = l.update( 1000 ); + CPPUNIT_ASSERT( updateResult.second ); + CPPUNIT_ASSERT( updateResult.first.key() == 1000 ); + CPPUNIT_ASSERT( updateResult.first.val().m_val == 0 ); + updateResult.first.val().m_val = 33; + updateResult = l.update( 1000 ); + CPPUNIT_ASSERT( !updateResult.second ); + CPPUNIT_ASSERT( updateResult.first.key() == 1000 ); + CPPUNIT_ASSERT( updateResult.first.val().m_val == 33 ); // clear test l.clear(); @@ -567,12 +567,12 @@ namespace ordlist { CPPUNIT_ASSERT( l.emplace( 501, 2 ) == l.end()); CPPUNIT_ASSERT( l.emplace( 251, 10) == l.end()); - it = l.find( 501 ); + it = l.contains( 501 ); CPPUNIT_ASSERT( it != l.end()); CPPUNIT_ASSERT( it.key() == 501 ); CPPUNIT_ASSERT( it.val().m_val == 0 ); - it = l.find( 251 ); + it = l.contains( 251 ); CPPUNIT_ASSERT( it != l.end()); CPPUNIT_ASSERT( it.key() == 251 ); CPPUNIT_ASSERT( it.val().m_val == 152 ); @@ -623,7 +623,7 @@ namespace ordlist { // Check that we have visited all items for ( int i = 0; i < nCount; ++i ) { - it = l.find( i ); + it = l.contains( i ); CPPUNIT_ASSERT( it != l.end() ); CPPUNIT_ASSERT( it.key() == i ); CPPUNIT_ASSERT( it.val().m_val == i * 3 ); diff --git a/tests/unit/map2/CMakeLists.txt b/tests/unit/map2/CMakeLists.txt index 9cd5700c..96887a5d 100644 --- a/tests/unit/map2/CMakeLists.txt +++ b/tests/unit/map2/CMakeLists.txt @@ -91,6 +91,7 @@ set(CDSUNIT_MAP_SOURCES map_delodd_michael.cpp map_delodd_bronsonavltree.cpp map_delodd_ellentree.cpp + map_delodd_multilevel_hashmap.cpp map_delodd_split.cpp map_delodd_skip.cpp map_delodd_cuckoo.cpp diff --git a/tests/unit/map2/map_defs.h b/tests/unit/map2/map_defs.h index dcfb329f..69a0fa07 100644 --- a/tests/unit/map2/map_defs.h +++ b/tests/unit/map2/map_defs.h @@ -1,8 +1,5 @@ //$$CDS-header$$ -#ifndef CDSUNIT_MAP_DEFS_H -#define CDSUNIT_MAP_DEFS_H - #define CDSUNIT_DECLARE_StdMap \ CDSUNIT_DECLARE_TEST(StdMap_Spin) \ CDSUNIT_DECLARE_TEST(StdHashMap_Spin) @@ -13,26 +10,23 @@ CPPUNIT_TEST(StdMap_Spin) \ CPPUNIT_TEST(StdHashMap_Spin) \ + +// ************************************************************************************** +// MichaelMap + +#undef CDSUNIT_DECLARE_MichaelMap_RCU_signal +#undef CDSUNIT_TEST_MichaelMap_RCU_signal #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED # define CDSUNIT_DECLARE_MichaelMap_RCU_signal \ - CDSUNIT_DECLARE_TEST(MichaelMap_RCU_SHB_cmp_stdAlloc) \ - CDSUNIT_DECLARE_TEST(MichaelMap_RCU_SHB_less_michaelAlloc) \ - CDSUNIT_DECLARE_TEST(MichaelMap_RCU_SHT_cmp_stdAlloc) \ - CDSUNIT_DECLARE_TEST(MichaelMap_RCU_SHT_less_michaelAlloc) \ - CDSUNIT_DECLARE_TEST(MichaelMap_Lazy_RCU_SHB_cmp_stdAlloc) \ - CDSUNIT_DECLARE_TEST(MichaelMap_Lazy_RCU_SHB_less_michaelAlloc) \ - CDSUNIT_DECLARE_TEST(MichaelMap_Lazy_RCU_SHT_cmp_stdAlloc) \ - CDSUNIT_DECLARE_TEST(MichaelMap_Lazy_RCU_SHT_less_michaelAlloc) - -# define CDSUNIT_DEFINE_MichaelMap_RCU_signal(IMPL, C) \ - TEST_MAP_EXTRACT(IMPL, C, MichaelMap_RCU_SHB_cmp_stdAlloc) \ - TEST_MAP_EXTRACT(IMPL, C, MichaelMap_RCU_SHB_less_michaelAlloc) \ - TEST_MAP_EXTRACT(IMPL, C, MichaelMap_RCU_SHT_cmp_stdAlloc) \ - TEST_MAP_EXTRACT(IMPL, C, MichaelMap_RCU_SHT_less_michaelAlloc) \ - TEST_MAP_EXTRACT(IMPL, C, MichaelMap_Lazy_RCU_SHB_cmp_stdAlloc) \ - TEST_MAP_EXTRACT(IMPL, C, MichaelMap_Lazy_RCU_SHB_less_michaelAlloc) \ - TEST_MAP_EXTRACT(IMPL, C, MichaelMap_Lazy_RCU_SHT_cmp_stdAlloc) \ - TEST_MAP_EXTRACT(IMPL, C, MichaelMap_Lazy_RCU_SHT_less_michaelAlloc) + TEST_CASE(tag_MichaelHashMap, MichaelMap_RCU_SHB_cmp_stdAlloc) \ + TEST_CASE(tag_MichaelHashMap, MichaelMap_RCU_SHB_cmp_stdAlloc) \ + TEST_CASE(tag_MichaelHashMap, MichaelMap_RCU_SHB_less_michaelAlloc) \ + TEST_CASE(tag_MichaelHashMap, MichaelMap_RCU_SHT_cmp_stdAlloc) \ + TEST_CASE(tag_MichaelHashMap, MichaelMap_RCU_SHT_less_michaelAlloc) \ + TEST_CASE(tag_MichaelHashMap, MichaelMap_Lazy_RCU_SHB_cmp_stdAlloc) \ + TEST_CASE(tag_MichaelHashMap, MichaelMap_Lazy_RCU_SHB_less_michaelAlloc) \ + TEST_CASE(tag_MichaelHashMap, MichaelMap_Lazy_RCU_SHT_cmp_stdAlloc) \ + TEST_CASE(tag_MichaelHashMap, MichaelMap_Lazy_RCU_SHT_less_michaelAlloc) # define CDSUNIT_TEST_MichaelMap_RCU_signal \ CPPUNIT_TEST(MichaelMap_RCU_SHB_cmp_stdAlloc) \ @@ -46,57 +40,34 @@ #else # define CDSUNIT_DECLARE_MichaelMap_RCU_signal -# define CDSUNIT_DEFINE_MichaelMap_RCU_signal(IMPL, C) # define CDSUNIT_TEST_MichaelMap_RCU_signal #endif - +#undef CDSUNIT_DECLARE_MichaelMap #define CDSUNIT_DECLARE_MichaelMap \ - CDSUNIT_DECLARE_TEST(MichaelMap_HP_cmp_stdAlloc) \ - CDSUNIT_DECLARE_TEST(MichaelMap_HP_less_michaelAlloc) \ - CDSUNIT_DECLARE_TEST(MichaelMap_DHP_cmp_stdAlloc) \ - CDSUNIT_DECLARE_TEST(MichaelMap_DHP_less_michaelAlloc) \ - CDSUNIT_DECLARE_TEST(MichaelMap_RCU_GPI_cmp_stdAlloc) \ - CDSUNIT_DECLARE_TEST(MichaelMap_RCU_GPI_less_michaelAlloc) \ - CDSUNIT_DECLARE_TEST(MichaelMap_RCU_GPB_cmp_stdAlloc) \ - CDSUNIT_DECLARE_TEST(MichaelMap_RCU_GPB_less_michaelAlloc) \ - CDSUNIT_DECLARE_TEST(MichaelMap_RCU_GPT_cmp_stdAlloc) \ - CDSUNIT_DECLARE_TEST(MichaelMap_RCU_GPT_less_michaelAlloc) \ - CDSUNIT_DECLARE_TEST(MichaelMap_Lazy_HP_cmp_stdAlloc) \ - CDSUNIT_DECLARE_TEST(MichaelMap_Lazy_HP_less_michaelAlloc) \ - CDSUNIT_DECLARE_TEST(MichaelMap_Lazy_DHP_cmp_stdAlloc) \ - CDSUNIT_DECLARE_TEST(MichaelMap_Lazy_DHP_less_michaelAlloc) \ - CDSUNIT_DECLARE_TEST(MichaelMap_Lazy_RCU_GPI_cmp_stdAlloc) \ - CDSUNIT_DECLARE_TEST(MichaelMap_Lazy_RCU_GPI_less_michaelAlloc) \ - CDSUNIT_DECLARE_TEST(MichaelMap_Lazy_RCU_GPB_cmp_stdAlloc) \ - CDSUNIT_DECLARE_TEST(MichaelMap_Lazy_RCU_GPB_less_michaelAlloc) \ - CDSUNIT_DECLARE_TEST(MichaelMap_Lazy_RCU_GPT_cmp_stdAlloc) \ - CDSUNIT_DECLARE_TEST(MichaelMap_Lazy_RCU_GPT_less_michaelAlloc)\ + TEST_CASE(tag_MichaelHashMap, MichaelMap_HP_cmp_stdAlloc) \ + TEST_CASE(tag_MichaelHashMap, MichaelMap_HP_less_michaelAlloc) \ + TEST_CASE(tag_MichaelHashMap, MichaelMap_DHP_cmp_stdAlloc) \ + TEST_CASE(tag_MichaelHashMap, MichaelMap_DHP_less_michaelAlloc) \ + TEST_CASE(tag_MichaelHashMap, MichaelMap_RCU_GPI_cmp_stdAlloc) \ + TEST_CASE(tag_MichaelHashMap, MichaelMap_RCU_GPI_less_michaelAlloc) \ + TEST_CASE(tag_MichaelHashMap, MichaelMap_RCU_GPB_cmp_stdAlloc) \ + TEST_CASE(tag_MichaelHashMap, MichaelMap_RCU_GPB_less_michaelAlloc) \ + TEST_CASE(tag_MichaelHashMap, MichaelMap_RCU_GPT_cmp_stdAlloc) \ + TEST_CASE(tag_MichaelHashMap, MichaelMap_RCU_GPT_less_michaelAlloc) \ + TEST_CASE(tag_MichaelHashMap, MichaelMap_Lazy_HP_cmp_stdAlloc) \ + TEST_CASE(tag_MichaelHashMap, MichaelMap_Lazy_HP_less_michaelAlloc) \ + TEST_CASE(tag_MichaelHashMap, MichaelMap_Lazy_DHP_cmp_stdAlloc) \ + TEST_CASE(tag_MichaelHashMap, MichaelMap_Lazy_DHP_less_michaelAlloc) \ + TEST_CASE(tag_MichaelHashMap, MichaelMap_Lazy_RCU_GPI_cmp_stdAlloc) \ + TEST_CASE(tag_MichaelHashMap, MichaelMap_Lazy_RCU_GPI_less_michaelAlloc) \ + TEST_CASE(tag_MichaelHashMap, MichaelMap_Lazy_RCU_GPB_cmp_stdAlloc) \ + TEST_CASE(tag_MichaelHashMap, MichaelMap_Lazy_RCU_GPB_less_michaelAlloc) \ + TEST_CASE(tag_MichaelHashMap, MichaelMap_Lazy_RCU_GPT_cmp_stdAlloc) \ + TEST_CASE(tag_MichaelHashMap, MichaelMap_Lazy_RCU_GPT_less_michaelAlloc)\ CDSUNIT_DECLARE_MichaelMap_RCU_signal -#define CDSUNIT_DEFINE_MichaelMap( IMPL, C ) \ - TEST_MAP_EXTRACT(IMPL, C, MichaelMap_HP_cmp_stdAlloc) \ - TEST_MAP_EXTRACT(IMPL, C, MichaelMap_HP_less_michaelAlloc) \ - TEST_MAP_EXTRACT(IMPL, C, MichaelMap_DHP_cmp_stdAlloc) \ - TEST_MAP_EXTRACT(IMPL, C, MichaelMap_DHP_less_michaelAlloc) \ - TEST_MAP_EXTRACT(IMPL, C, MichaelMap_RCU_GPI_cmp_stdAlloc) \ - TEST_MAP_EXTRACT(IMPL, C, MichaelMap_RCU_GPI_less_michaelAlloc) \ - TEST_MAP_EXTRACT(IMPL, C, MichaelMap_RCU_GPB_cmp_stdAlloc) \ - TEST_MAP_EXTRACT(IMPL, C, MichaelMap_RCU_GPB_less_michaelAlloc) \ - TEST_MAP_EXTRACT(IMPL, C, MichaelMap_RCU_GPT_cmp_stdAlloc) \ - TEST_MAP_EXTRACT(IMPL, C, MichaelMap_RCU_GPT_less_michaelAlloc) \ - TEST_MAP_EXTRACT(IMPL, C, MichaelMap_Lazy_HP_cmp_stdAlloc) \ - TEST_MAP_EXTRACT(IMPL, C, MichaelMap_Lazy_HP_less_michaelAlloc) \ - TEST_MAP_EXTRACT(IMPL, C, MichaelMap_Lazy_DHP_cmp_stdAlloc) \ - TEST_MAP_EXTRACT(IMPL, C, MichaelMap_Lazy_DHP_less_michaelAlloc) \ - TEST_MAP_EXTRACT(IMPL, C, MichaelMap_Lazy_RCU_GPI_cmp_stdAlloc) \ - TEST_MAP_EXTRACT(IMPL, C, MichaelMap_Lazy_RCU_GPI_less_michaelAlloc) \ - TEST_MAP_EXTRACT(IMPL, C, MichaelMap_Lazy_RCU_GPB_cmp_stdAlloc) \ - TEST_MAP_EXTRACT(IMPL, C, MichaelMap_Lazy_RCU_GPB_less_michaelAlloc) \ - TEST_MAP_EXTRACT(IMPL, C, MichaelMap_Lazy_RCU_GPT_cmp_stdAlloc) \ - TEST_MAP_EXTRACT(IMPL, C, MichaelMap_Lazy_RCU_GPT_less_michaelAlloc)\ - CDSUNIT_DEFINE_MichaelMap_RCU_signal( IMPL, C ) - +#undef CDSUNIT_TEST_MichaelMap #define CDSUNIT_TEST_MichaelMap \ CPPUNIT_TEST(MichaelMap_HP_cmp_stdAlloc) \ CPPUNIT_TEST(MichaelMap_HP_less_michaelAlloc) \ @@ -120,20 +91,15 @@ CPPUNIT_TEST(MichaelMap_Lazy_RCU_GPT_less_michaelAlloc)\ CDSUNIT_TEST_MichaelMap_RCU_signal +#undef CDSUNIT_DECLARE_MichaelMap_nogc #define CDSUNIT_DECLARE_MichaelMap_nogc \ - CDSUNIT_DECLARE_TEST(MichaelMap_NOGC_cmp_stdAlloc) \ - CDSUNIT_DECLARE_TEST(MichaelMap_NOGC_less_michaelAlloc) \ - CDSUNIT_DECLARE_TEST(MichaelMap_Lazy_NOGC_cmp_stdAlloc) \ - CDSUNIT_DECLARE_TEST(MichaelMap_Lazy_NOGC_unord_stdAlloc) \ - CDSUNIT_DECLARE_TEST(MichaelMap_Lazy_NOGC_less_michaelAlloc) - -#define CDSUNIT_DEFINE_MichaelMap_nogc( IMPL, C ) \ - TEST_MAP(IMPL, C, MichaelMap_NOGC_cmp_stdAlloc) \ - TEST_MAP(IMPL, C, MichaelMap_NOGC_less_michaelAlloc) \ - TEST_MAP(IMPL, C, MichaelMap_Lazy_NOGC_cmp_stdAlloc) \ - TEST_MAP(IMPL, C, MichaelMap_Lazy_NOGC_unord_stdAlloc) \ - TEST_MAP(IMPL, C, MichaelMap_Lazy_NOGC_less_michaelAlloc) + TEST_CASE(tag_MichaelHashMap, MichaelMap_NOGC_cmp_stdAlloc) \ + TEST_CASE(tag_MichaelHashMap, MichaelMap_NOGC_less_michaelAlloc) \ + TEST_CASE(tag_MichaelHashMap, MichaelMap_Lazy_NOGC_cmp_stdAlloc) \ + TEST_CASE(tag_MichaelHashMap, MichaelMap_Lazy_NOGC_unord_stdAlloc) \ + TEST_CASE(tag_MichaelHashMap, MichaelMap_Lazy_NOGC_less_michaelAlloc) +#undef CDSUNIT_TEST_MichaelMap_nogc #define CDSUNIT_TEST_MichaelMap_nogc \ CPPUNIT_TEST(MichaelMap_NOGC_cmp_stdAlloc) \ CPPUNIT_TEST(MichaelMap_NOGC_less_michaelAlloc) \ @@ -141,6 +107,10 @@ CPPUNIT_TEST(MichaelMap_Lazy_NOGC_unord_stdAlloc) \ CPPUNIT_TEST(MichaelMap_Lazy_NOGC_less_michaelAlloc) \ + +// ************************************************************************************** +// SplitListMap + #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED # define CDSUNIT_DECLARE_SplitList_RCU_signal \ CDSUNIT_DECLARE_TEST(SplitList_Michael_RCU_SHB_dyn_cmp)\ @@ -445,6 +415,10 @@ CPPUNIT_TEST(SplitList_Lazy_NOGC_dyn_less)\ CPPUNIT_TEST(SplitList_Lazy_NOGC_st_less) + +// ************************************************************************************** +// SkipListMap + #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED # define CDSUNIT_DECLARE_SkipListMap_RCU_signal \ CDSUNIT_DECLARE_TEST(SkipListMap_rcu_shb_less_pascal)\ @@ -569,6 +543,10 @@ CPPUNIT_TEST(SkipListMap_nogc_less_xorshift)\ CPPUNIT_TEST(SkipListMap_nogc_cmp_xorshift_stat) + +// ************************************************************************************** +// EllenBinTreeMap + #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED # define CDSUNIT_DECLARE_EllenBinTreeMap_RCU_signal \ CDSUNIT_DECLARE_TEST(EllenBinTreeMap_rcu_shb)\ @@ -641,6 +619,10 @@ CPPUNIT_TEST(EllenBinTreeMap_rcu_gpt_stat)\ CDSUNIT_TEST_EllenBinTreeMap_RCU_signal + +// ************************************************************************************** +// BronsonACLTreeMap + #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED # define CDSUNIT_DECLARE_BronsonAVLTreeMap_RCU_signal \ CDSUNIT_DECLARE_TEST(BronsonAVLTreeMap_rcu_shb_less) \ @@ -783,6 +765,10 @@ CPPUNIT_TEST(BronsonAVLTreeMap_rcu_gpt_less_pool_bounded_stat)\ CDSUNIT_TEST_BronsonAVLTreeMap_RCU_signal + +// ************************************************************************************** +// StripedMap + #define CDSUNIT_DECLARE_StripedMap_common \ CDSUNIT_DECLARE_TEST(StripedMap_list) \ CDSUNIT_DECLARE_TEST(StripedMap_map) \ @@ -847,6 +833,8 @@ CDSUNIT_TEST_StripedMap_boost_flat_container +// ************************************************************************************** +// RefinableMap #define CDSUNIT_DECLARE_RefinableMap_common \ CDSUNIT_DECLARE_TEST(RefinableMap_list) \ @@ -909,6 +897,10 @@ CDSUNIT_TEST_RefinableMap_boost_container \ CDSUNIT_TEST_RefinableMap_boost_flat_container + +// ************************************************************************************** +// CuckooMap + #define CDSUNIT_DECLARE_CuckooMap \ CDSUNIT_DECLARE_TEST(CuckooStripedMap_list_unord)\ CDSUNIT_DECLARE_TEST(CuckooStripedMap_list_ord)\ @@ -987,4 +979,21 @@ CPPUNIT_TEST(CuckooRefinableMap_vector_ord_stat)\ CPPUNIT_TEST(CuckooRefinableMap_vector_ord_storehash) -#endif // #ifndef CDSUNIT_MAP_DEFS_H + +// ************************************************************************************** +// MultiLevelHashMap + +#undef CDSUNIT_DECLARE_MultiLevelHashMap +#define CDSUNIT_DECLARE_MultiLevelHashMap \ + TEST_CASE(tag_MultiLevelHashMap, MultiLevelHashMap_hp_stdhash) \ + TEST_CASE(tag_MultiLevelHashMap, MultiLevelHashMap_hp_stdhash_stat) \ + TEST_CASE(tag_MultiLevelHashMap, MultiLevelHashMap_dhp_stdhash) \ + TEST_CASE(tag_MultiLevelHashMap, MultiLevelHashMap_dhp_stdhash_stat) + +#undef CDSUNIT_TEST_MultiLevelHashMap +#define CDSUNIT_TEST_MultiLevelHashMap \ + CPPUNIT_TEST(MultiLevelHashMap_hp_stdhash) \ + CPPUNIT_TEST(MultiLevelHashMap_hp_stdhash_stat) \ + CPPUNIT_TEST(MultiLevelHashMap_dhp_stdhash) \ + CPPUNIT_TEST(MultiLevelHashMap_dhp_stdhash_stat) + diff --git a/tests/unit/map2/map_delodd.cpp b/tests/unit/map2/map_delodd.cpp index 7c65caf2..7a3b1dde 100644 --- a/tests/unit/map2/map_delodd.cpp +++ b/tests/unit/map2/map_delodd.cpp @@ -5,12 +5,12 @@ namespace map2 { CPPUNIT_TEST_SUITE_REGISTRATION( Map_DelOdd ); - size_t Map_DelOdd::c_nMapSize = 1000000 ; // max map size - size_t Map_DelOdd::c_nInsThreadCount = 4 ; // insert thread count - size_t Map_DelOdd::c_nDelThreadCount = 4 ; // delete thread count - size_t Map_DelOdd::c_nExtractThreadCount = 4 ; // extract thread count - size_t Map_DelOdd::c_nMaxLoadFactor = 8 ; // maximum load factor - bool Map_DelOdd::c_bPrintGCState = true; + //size_t Map_DelOdd::c_nMapSize = 1000000 ; // max map size + //size_t Map_DelOdd::c_nInsThreadCount = 4 ; // insert thread count + //size_t Map_DelOdd::c_nDelThreadCount = 4 ; // delete thread count + //size_t Map_DelOdd::c_nExtractThreadCount = 4 ; // extract thread count + //size_t Map_DelOdd::c_nMaxLoadFactor = 8 ; // maximum load factor + //bool Map_DelOdd::c_bPrintGCState = true; void Map_DelOdd::setUpParams( const CppUnitMini::TestCfg& cfg ) { c_nMapSize = cfg.getULong("MapSize", static_cast(c_nMapSize) ); @@ -19,6 +19,9 @@ namespace map2 { c_nExtractThreadCount = cfg.getULong("ExtractThreadCount", static_cast(c_nExtractThreadCount) ); c_nMaxLoadFactor = cfg.getULong("MaxLoadFactor", static_cast(c_nMaxLoadFactor) ); c_bPrintGCState = cfg.getBool("PrintGCStateFlag", true ); + c_nMultiLevelMap_HeadBits = cfg.getULong("MultiLevelMap_HeadBits", static_cast(c_nMultiLevelMap_HeadBits) ); + c_nMultiLevelMap_ArrayBits = cfg.getULong("MultiLevelMap_ArrayBits", static_cast(c_nMultiLevelMap_ArrayBits) ); + if ( c_nInsThreadCount == 0 ) c_nInsThreadCount = cds::OS::topology::processor_count(); @@ -37,21 +40,4 @@ namespace map2 { shuffle( m_arrRemove.begin(), m_arrRemove.end() ); } - void Map_DelOdd::myRun(const char *in_name, bool invert /*= false*/) - { - setUpParams( m_Cfg.get( "Map_DelOdd" )); - - run_MichaelMap(in_name, invert); - run_SplitList(in_name, invert); - run_SkipListMap(in_name, invert); - run_EllenBinTreeMap(in_name, invert); - run_BronsonAVLTreeMap(in_name, invert); - //run_StripedMap(in_name, invert); - //run_RefinableMap(in_name, invert); - run_CuckooMap(in_name, invert); - //run_StdMap(in_name, invert); - - endTestCase(); - } - } // namespace map2 diff --git a/tests/unit/map2/map_delodd.h b/tests/unit/map2/map_delodd.h index 4cda89e1..836c10c7 100644 --- a/tests/unit/map2/map_delodd.h +++ b/tests/unit/map2/map_delodd.h @@ -6,10 +6,13 @@ namespace map2 { -# define TEST_MAP(IMPL, C, X) void C::X() { test::X >(); } -# define TEST_MAP_EXTRACT(IMPL, C, X) void C::X() { test_extract::X >(); } -# define TEST_MAP_NOLF(IMPL, C, X) void C::X() { test_nolf::X >(); } -# define TEST_MAP_NOLF_EXTRACT(IMPL, C, X) void C::X() { test_nolf_extract::X >(); } +//# define TEST_MAP(IMPL, C, X) void C::X() { test::X >(); } +//# define TEST_MAP_DEFAULT_CONSTRUCTIBLE(IMPL, C, X) void C::X() { test_default_constructible::X >(); } +//# define TEST_MAP_EXTRACT(IMPL, C, X) void C::X() { test_extract::X >(); } +//# define TEST_MAP_NOLF(IMPL, C, X) void C::X() { test_nolf::X >(); } +//# define TEST_MAP_NOLF_EXTRACT(IMPL, C, X) void C::X() { test_nolf_extract::X >(); } + +# define TEST_CASE(TAG, X) void X(); namespace { struct key_thread @@ -25,8 +28,6 @@ namespace map2 { key_thread() {} }; - - //typedef MapTypes::key_val key_value_pair; } template <> @@ -119,13 +120,20 @@ namespace map2 { class Map_DelOdd: public CppUnitMini::TestCase { - static size_t c_nMapSize; // max map size - static size_t c_nInsThreadCount; // insert thread count - static size_t c_nDelThreadCount; // delete thread count - static size_t c_nExtractThreadCount; // extract thread count - static size_t c_nMaxLoadFactor; // maximum load factor - static bool c_bPrintGCState; + public: + size_t c_nInsThreadCount = 4; // insert thread count + size_t c_nDelThreadCount = 4; // delete thread count + size_t c_nExtractThreadCount = 4; // extract thread count + size_t c_nMapSize = 1000000; // max map size + size_t c_nMaxLoadFactor = 8; // maximum load factor + size_t c_nMultiLevelMap_HeadBits = 10; // for MultiLevelHashMap - log2(size of head array) + size_t c_nMultiLevelMap_ArrayBits = 8; // for MultiLevelHashMap - log2(size of array node) + + bool c_bPrintGCState = true; + size_t c_nLoadFactor; // current load factor + + private: std::vector m_arrInsert; std::vector m_arrRemove; @@ -157,6 +165,11 @@ namespace map2 { template void operator()( bool /*bNew*/, Q const&, V& ) {} + + // MultiLevelHashMap + template + void operator()( Q&, Q*) + {} }; public: size_t m_nInsertSuccess; @@ -198,7 +211,7 @@ namespace map2 { ensure_func f; for ( size_t i = arrData.size() - 1; i > 0; --i ) { if ( arrData[i] & 1 ) { - rMap.ensure( key_type( arrData[i], m_nThreadNo ), f ); + rMap.update( key_type( arrData[i], m_nThreadNo ), f ); } } @@ -277,10 +290,12 @@ namespace map2 { m_nDeleteSuccess = m_nDeleteFailed = 0; + size_t const nInsThreadCount = getTest().c_nInsThreadCount; + for ( size_t pass = 0; pass < 2; pass++ ) { std::vector& arrData = getTest().m_arrRemove; if ( m_nThreadNo & 1 ) { - for ( size_t k = 0; k < c_nInsThreadCount; ++k ) { + for ( size_t k = 0; k < nInsThreadCount; ++k ) { for ( size_t i = 0; i < arrData.size(); ++i ) { if ( arrData[i] & 1 ) { if ( rMap.erase_with( arrData[i], key_less() )) @@ -294,7 +309,7 @@ namespace map2 { } } else { - for ( size_t k = 0; k < c_nInsThreadCount; ++k ) { + for ( size_t k = 0; k < nInsThreadCount; ++k ) { for ( size_t i = arrData.size() - 1; i > 0; --i ) { if ( arrData[i] & 1 ) { if ( rMap.erase_with( arrData[i], key_less() )) @@ -351,11 +366,12 @@ namespace map2 { m_nDeleteFailed = 0; typename Map::guarded_ptr gp; + size_t const nInsThreadCount = getTest().c_nInsThreadCount; for ( size_t pass = 0; pass < 2; ++pass ) { std::vector& arrData = getTest().m_arrRemove; if ( m_nThreadNo & 1 ) { - for ( size_t k = 0; k < c_nInsThreadCount; ++k ) { + for ( size_t k = 0; k < nInsThreadCount; ++k ) { for ( size_t i = 0; i < arrData.size(); ++i ) { if ( arrData[i] & 1 ) { gp = rMap.extract_with( arrData[i], key_less()); @@ -371,7 +387,7 @@ namespace map2 { } } else { - for ( size_t k = 0; k < c_nInsThreadCount; ++k ) { + for ( size_t k = 0; k < nInsThreadCount; ++k ) { for ( size_t i = arrData.size() - 1; i > 0; --i ) { if ( arrData[i] & 1 ) { gp = rMap.extract_with( arrData[i], key_less()); @@ -429,10 +445,11 @@ namespace map2 { m_nDeleteFailed = 0; typename Map::exempt_ptr xp; + size_t const nInsThreadCount = getTest().c_nInsThreadCount; std::vector& arrData = getTest().m_arrRemove; if ( m_nThreadNo & 1 ) { - for ( size_t k = 0; k < c_nInsThreadCount; ++k ) { + for ( size_t k = 0; k < nInsThreadCount; ++k ) { for ( size_t i = 0; i < arrData.size(); ++i ) { if ( arrData[i] & 1 ) { if ( Map::c_bExtractLockExternal ) { @@ -460,7 +477,7 @@ namespace map2 { } } else { - for ( size_t k = 0; k < c_nInsThreadCount; ++k ) { + for ( size_t k = 0; k < nInsThreadCount; ++k ) { for ( size_t i = arrData.size() - 1; i > 0; --i ) { if ( arrData[i] & 1 ) { if ( Map::c_bExtractLockExternal ) { @@ -492,16 +509,16 @@ namespace map2 { protected: template - void do_test( size_t nLoadFactor ) + void do_test() { - Map testMap( c_nMapSize, nLoadFactor ); + Map testMap( *this ); do_test_with( testMap ); } template - void do_test_extract( size_t nLoadFactor ) + void do_test_extract() { - Map testMap( c_nMapSize, nLoadFactor ); + Map testMap( *this ); do_test_extract_with( testMap ); } @@ -613,7 +630,7 @@ namespace map2 { CPPUNIT_MSG( " Check even keys..." ); for ( size_t n = 0; n < c_nMapSize; n +=2 ) { for ( size_t i = 0; i < c_nInsThreadCount; ++i ) { - if ( !testMap.find( key_type(n, i) ) ) { + if ( !testMap.contains( key_type(n, i) ) ) { if ( ++nErrorCount < 10 ) { CPPUNIT_MSG( "key " << n << "-" << i << " is not found!"); } @@ -637,91 +654,139 @@ namespace map2 { additional_cleanup( testMap ); } - template - void test() - { - CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount - << " delete thread count=" << c_nDelThreadCount - << " set size=" << c_nMapSize - ); - - for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) { - CPPUNIT_MSG( "Load factor=" << nLoadFactor ); - do_test( nLoadFactor ); - if ( c_bPrintGCState ) - print_gc_state(); - } - } + //template + //void test() + //{ + // CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount + // << " delete thread count=" << c_nDelThreadCount + // << " set size=" << c_nMapSize + // ); + + // for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) { + // CPPUNIT_MSG( "Load factor=" << nLoadFactor ); + // do_test( nLoadFactor ); + // if ( c_bPrintGCState ) + // print_gc_state(); + // } + //} + + //template + //void test_extract() + //{ + // CPPUNIT_MSG( "Thread count: insert=" << c_nInsThreadCount + // << ", delete=" << c_nDelThreadCount + // << ", extract=" << c_nExtractThreadCount + // << "; set size=" << c_nMapSize + // ); + + // for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) { + // CPPUNIT_MSG( "Load factor=" << nLoadFactor ); + // do_test_extract( nLoadFactor ); + // if ( c_bPrintGCState ) + // print_gc_state(); + // } + //} + + //template + //void test_nolf() + //{ + // CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount + // << " delete thread count=" << c_nDelThreadCount + // << " set size=" << c_nMapSize + // ); + + // Map s; + // do_test_with( s ); + // if ( c_bPrintGCState ) + // print_gc_state(); + //} + + //template + //void test_nolf_extract() + //{ + // CPPUNIT_MSG( "Thread count: insert=" << c_nInsThreadCount + // << ", delete=" << c_nDelThreadCount + // << ", extract=" << c_nExtractThreadCount + // << "; set size=" << c_nMapSize + // ); + + // Map s; + // do_test_extract_with( s ); + // if ( c_bPrintGCState ) + // print_gc_state(); + //} template - void test_extract() + void run_test() { - CPPUNIT_MSG( "Thread count: insert=" << c_nInsThreadCount - << ", delete=" << c_nDelThreadCount - << ", extract=" << c_nExtractThreadCount - << "; set size=" << c_nMapSize - ); - - for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) { - CPPUNIT_MSG( "Load factor=" << nLoadFactor ); - do_test_extract( nLoadFactor ); - if ( c_bPrintGCState ) - print_gc_state(); + if ( Map::c_bExtractSupported ) { + CPPUNIT_MSG( "Thread count: insert=" << c_nInsThreadCount + << ", delete=" << c_nDelThreadCount + << ", extract=" << c_nExtractThreadCount + << "; set size=" << c_nMapSize + ); + if ( Map::c_bLoadFactorDepended ) { + for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) { + CPPUNIT_MSG( "Load factor=" << c_nLoadFactor ); + do_test_extract(); + if ( c_bPrintGCState ) + print_gc_state(); + } + } + else + do_test_extract(); + } + else { + CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount + << " delete thread count=" << c_nDelThreadCount + << " set size=" << c_nMapSize + ); + if ( Map::c_bLoadFactorDepended ) { + for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) { + CPPUNIT_MSG( "Load factor=" << c_nLoadFactor ); + do_test(); + if ( c_bPrintGCState ) + print_gc_state(); + } + } + else + do_test(); } - } - - template - void test_nolf() - { - CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount - << " delete thread count=" << c_nDelThreadCount - << " set size=" << c_nMapSize - ); - - Map s; - do_test_with( s ); - if ( c_bPrintGCState ) - print_gc_state(); - } - - template - void test_nolf_extract() - { - CPPUNIT_MSG( "Thread count: insert=" << c_nInsThreadCount - << ", delete=" << c_nDelThreadCount - << ", extract=" << c_nExtractThreadCount - << "; set size=" << c_nMapSize - ); - - Map s; - do_test_extract_with( s ); - if ( c_bPrintGCState ) - print_gc_state(); } void setUpParams( const CppUnitMini::TestCfg& cfg ); - void run_MichaelMap(const char *in_name, bool invert = false); - void run_SplitList(const char *in_name, bool invert = false); - //void run_StripedMap(const char *in_name, bool invert = false); - //void run_RefinableMap(const char *in_name, bool invert = false); - void run_CuckooMap(const char *in_name, bool invert = false); - void run_SkipListMap(const char *in_name, bool invert = false); - void run_EllenBinTreeMap(const char *in_name, bool invert = false); - void run_BronsonAVLTreeMap(const char *in_name, bool invert = false); - //void run_StdMap(const char *in_name, bool invert = false); + //void run_MichaelMap(const char *in_name, bool invert = false); + //void run_SplitList(const char *in_name, bool invert = false); + ////void run_StripedMap(const char *in_name, bool invert = false); + ////void run_RefinableMap(const char *in_name, bool invert = false); + //void run_CuckooMap(const char *in_name, bool invert = false); + //void run_SkipListMap(const char *in_name, bool invert = false); + //void run_EllenBinTreeMap(const char *in_name, bool invert = false); + //void run_BronsonAVLTreeMap(const char *in_name, bool invert = false); + //void run_MultiLevelHashMap(const char *in_name, bool invert = false); + ////void run_StdMap(const char *in_name, bool invert = false); - virtual void myRun(const char *in_name, bool invert = false); + //virtual void myRun(const char *in_name, bool invert = false); # include "map2/map_defs.h" CDSUNIT_DECLARE_MichaelMap - CDSUNIT_DECLARE_SplitList - //CDSUNIT_DECLARE_StripedMap - //CDSUNIT_DECLARE_RefinableMap - CDSUNIT_DECLARE_CuckooMap - CDSUNIT_DECLARE_SkipListMap - CDSUNIT_DECLARE_EllenBinTreeMap - CDSUNIT_DECLARE_BronsonAVLTreeMap - //CDSUNIT_DECLARE_StdMap + CDSUNIT_DECLARE_MultiLevelHashMap + + CPPUNIT_TEST_SUITE(Map_DelOdd) + CDSUNIT_TEST_MichaelMap + //CDSUNIT_TEST_MultiLevelHashMap + CPPUNIT_TEST_SUITE_END(); + + //CDSUNIT_DECLARE_MichaelMap + //CDSUNIT_DECLARE_SplitList + ////CDSUNIT_DECLARE_StripedMap + ////CDSUNIT_DECLARE_RefinableMap + //CDSUNIT_DECLARE_CuckooMap + //CDSUNIT_DECLARE_SkipListMap + //CDSUNIT_DECLARE_EllenBinTreeMap + //CDSUNIT_DECLARE_BronsonAVLTreeMap + //CDSUNIT_DECLARE_MultiLevelHashMap + ////CDSUNIT_DECLARE_StdMap }; } // namespace map2 diff --git a/tests/unit/map2/map_delodd_michael.cpp b/tests/unit/map2/map_delodd_michael.cpp index de5a6f64..2abd4968 100644 --- a/tests/unit/map2/map_delodd_michael.cpp +++ b/tests/unit/map2/map_delodd_michael.cpp @@ -3,10 +3,11 @@ #include "map2/map_delodd.h" #include "map2/map_type_michael.h" -namespace map2 { - CDSUNIT_DEFINE_MichaelMap( cc::michael_map::implementation_tag, Map_DelOdd ) +#undef TEST_CASE +#define TEST_CASE(TAG, X) void Map_DelOdd::X() { run_test::X>(); } +#include "map2/map_defs.h" - CPPUNIT_TEST_SUITE_PART( Map_DelOdd, run_MichaelMap ) - CDSUNIT_TEST_MichaelMap - CPPUNIT_TEST_SUITE_END_PART() +namespace map2 { + CDSUNIT_DECLARE_MichaelMap } // namespace map2 + diff --git a/tests/unit/map2/map_delodd_multilevel_hashmap.cpp b/tests/unit/map2/map_delodd_multilevel_hashmap.cpp new file mode 100644 index 00000000..8cdf9795 --- /dev/null +++ b/tests/unit/map2/map_delodd_multilevel_hashmap.cpp @@ -0,0 +1,12 @@ +//$$CDS-header$$ + +#include "map2/map_delodd.h" +#include "map2/map_type_multilevel_hashmap.h" + +#undef TEST_CASE +#define TEST_CASE(TAG, X) void Map_DelOdd::X() { run_test::X>(); } +#include "map2/map_defs.h" + +namespace map2 { + CDSUNIT_DECLARE_MultiLevelHashMap +} // namespace map2 diff --git a/tests/unit/map2/map_type_michael.h b/tests/unit/map2/map_type_michael.h index 8e9cfd8d..095c5b73 100644 --- a/tests/unit/map2/map_type_michael.h +++ b/tests/unit/map2/map_type_michael.h @@ -12,8 +12,27 @@ namespace map2 { + template + class MichaelHashMap : public cc::MichaelHashMap< GC, List, Traits > + { + typedef cc::MichaelHashMap< GC, List, Traits > base_class; + public: + template + MichaelHashMap( Config const& cfg) + : base_class( cfg.c_nMapSize, cfg.c_nLoadFactor ) + {} + + // for testing + static CDS_CONSTEXPR bool const c_bExtractSupported = true; + static CDS_CONSTEXPR bool const c_bLoadFactorDepended = true; + static CDS_CONSTEXPR bool const c_erase_with_supported = true; + static CDS_CONSTEXPR bool const c_extract_with_supported = true; + }; + + struct tag_MichaelHashMap; + template - struct map_type< cc::michael_map::implementation_tag, Key, Value >: public map_type_base< Key, Value > + struct map_type< tag_MichaelHashMap, Key, Value >: public map_type_base< Key, Value > { typedef map_type_base< Key, Value > base_class; typedef typename base_class::compare compare; @@ -32,48 +51,48 @@ namespace map2 { co::hash< hash > >::type {}; - typedef cc::MichaelHashMap< cds::gc::HP, typename ml::MichaelList_HP_cmp_stdAlloc, traits_MichaelMap_hash > MichaelMap_HP_cmp_stdAlloc; - typedef cc::MichaelHashMap< cds::gc::DHP, typename ml::MichaelList_DHP_cmp_stdAlloc, traits_MichaelMap_hash > MichaelMap_DHP_cmp_stdAlloc; - typedef cc::MichaelHashMap< cds::gc::nogc, typename ml::MichaelList_NOGC_cmp_stdAlloc, traits_MichaelMap_hash > MichaelMap_NOGC_cmp_stdAlloc; - typedef cc::MichaelHashMap< rcu_gpi, typename ml::MichaelList_RCU_GPI_cmp_stdAlloc, traits_MichaelMap_hash > MichaelMap_RCU_GPI_cmp_stdAlloc; - typedef cc::MichaelHashMap< rcu_gpb, typename ml::MichaelList_RCU_GPB_cmp_stdAlloc, traits_MichaelMap_hash > MichaelMap_RCU_GPB_cmp_stdAlloc; - typedef cc::MichaelHashMap< rcu_gpt, typename ml::MichaelList_RCU_GPT_cmp_stdAlloc, traits_MichaelMap_hash > MichaelMap_RCU_GPT_cmp_stdAlloc; + typedef MichaelHashMap< cds::gc::HP, typename ml::MichaelList_HP_cmp_stdAlloc, traits_MichaelMap_hash > MichaelMap_HP_cmp_stdAlloc; + typedef MichaelHashMap< cds::gc::DHP, typename ml::MichaelList_DHP_cmp_stdAlloc, traits_MichaelMap_hash > MichaelMap_DHP_cmp_stdAlloc; + typedef MichaelHashMap< cds::gc::nogc, typename ml::MichaelList_NOGC_cmp_stdAlloc, traits_MichaelMap_hash > MichaelMap_NOGC_cmp_stdAlloc; + typedef MichaelHashMap< rcu_gpi, typename ml::MichaelList_RCU_GPI_cmp_stdAlloc, traits_MichaelMap_hash > MichaelMap_RCU_GPI_cmp_stdAlloc; + typedef MichaelHashMap< rcu_gpb, typename ml::MichaelList_RCU_GPB_cmp_stdAlloc, traits_MichaelMap_hash > MichaelMap_RCU_GPB_cmp_stdAlloc; + typedef MichaelHashMap< rcu_gpt, typename ml::MichaelList_RCU_GPT_cmp_stdAlloc, traits_MichaelMap_hash > MichaelMap_RCU_GPT_cmp_stdAlloc; #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED - typedef cc::MichaelHashMap< rcu_shb, typename ml::MichaelList_RCU_SHB_cmp_stdAlloc, traits_MichaelMap_hash > MichaelMap_RCU_SHB_cmp_stdAlloc; - typedef cc::MichaelHashMap< rcu_sht, typename ml::MichaelList_RCU_SHT_cmp_stdAlloc, traits_MichaelMap_hash > MichaelMap_RCU_SHT_cmp_stdAlloc; + typedef MichaelHashMap< rcu_shb, typename ml::MichaelList_RCU_SHB_cmp_stdAlloc, traits_MichaelMap_hash > MichaelMap_RCU_SHB_cmp_stdAlloc; + typedef MichaelHashMap< rcu_sht, typename ml::MichaelList_RCU_SHT_cmp_stdAlloc, traits_MichaelMap_hash > MichaelMap_RCU_SHT_cmp_stdAlloc; #endif - typedef cc::MichaelHashMap< cds::gc::HP, typename ml::MichaelList_HP_less_stdAlloc, traits_MichaelMap_hash > MichaelMap_HP_less_stdAlloc; - typedef cc::MichaelHashMap< cds::gc::DHP, typename ml::MichaelList_DHP_less_stdAlloc, traits_MichaelMap_hash > MichaelMap_DHP_less_stdAlloc; - typedef cc::MichaelHashMap< cds::gc::nogc, typename ml::MichaelList_NOGC_less_stdAlloc, traits_MichaelMap_hash > MichaelMap_NOGC_less_stdAlloc; - typedef cc::MichaelHashMap< rcu_gpi, typename ml::MichaelList_RCU_GPI_less_stdAlloc, traits_MichaelMap_hash > MichaelMap_RCU_GPI_less_stdAlloc; - typedef cc::MichaelHashMap< rcu_gpb, typename ml::MichaelList_RCU_GPB_less_stdAlloc, traits_MichaelMap_hash > MichaelMap_RCU_GPB_less_stdAlloc; - typedef cc::MichaelHashMap< rcu_gpt, typename ml::MichaelList_RCU_GPT_less_stdAlloc, traits_MichaelMap_hash > MichaelMap_RCU_GPT_less_stdAlloc; + typedef MichaelHashMap< cds::gc::HP, typename ml::MichaelList_HP_less_stdAlloc, traits_MichaelMap_hash > MichaelMap_HP_less_stdAlloc; + typedef MichaelHashMap< cds::gc::DHP, typename ml::MichaelList_DHP_less_stdAlloc, traits_MichaelMap_hash > MichaelMap_DHP_less_stdAlloc; + typedef MichaelHashMap< cds::gc::nogc, typename ml::MichaelList_NOGC_less_stdAlloc, traits_MichaelMap_hash > MichaelMap_NOGC_less_stdAlloc; + typedef MichaelHashMap< rcu_gpi, typename ml::MichaelList_RCU_GPI_less_stdAlloc, traits_MichaelMap_hash > MichaelMap_RCU_GPI_less_stdAlloc; + typedef MichaelHashMap< rcu_gpb, typename ml::MichaelList_RCU_GPB_less_stdAlloc, traits_MichaelMap_hash > MichaelMap_RCU_GPB_less_stdAlloc; + typedef MichaelHashMap< rcu_gpt, typename ml::MichaelList_RCU_GPT_less_stdAlloc, traits_MichaelMap_hash > MichaelMap_RCU_GPT_less_stdAlloc; #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED - typedef cc::MichaelHashMap< rcu_shb, typename ml::MichaelList_RCU_SHB_less_stdAlloc, traits_MichaelMap_hash > MichaelMap_RCU_SHB_less_stdAlloc; - typedef cc::MichaelHashMap< rcu_sht, typename ml::MichaelList_RCU_SHT_less_stdAlloc, traits_MichaelMap_hash > MichaelMap_RCU_SHT_less_stdAlloc; + typedef MichaelHashMap< rcu_shb, typename ml::MichaelList_RCU_SHB_less_stdAlloc, traits_MichaelMap_hash > MichaelMap_RCU_SHB_less_stdAlloc; + typedef MichaelHashMap< rcu_sht, typename ml::MichaelList_RCU_SHT_less_stdAlloc, traits_MichaelMap_hash > MichaelMap_RCU_SHT_less_stdAlloc; #endif - typedef cc::MichaelHashMap< cds::gc::HP, typename ml::MichaelList_HP_cmp_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_HP_cmp_stdAlloc_seqcst; - typedef cc::MichaelHashMap< cds::gc::DHP, typename ml::MichaelList_DHP_cmp_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_DHP_cmp_stdAlloc_seqcst; - typedef cc::MichaelHashMap< cds::gc::nogc, typename ml::MichaelList_NOGC_cmp_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_NOGC_cmp_stdAlloc_seqcst; - typedef cc::MichaelHashMap< rcu_gpi, typename ml::MichaelList_RCU_GPI_cmp_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_RCU_GPI_cmp_stdAlloc_seqcst; - typedef cc::MichaelHashMap< rcu_gpb, typename ml::MichaelList_RCU_GPB_cmp_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_RCU_GPB_cmp_stdAlloc_seqcst; - typedef cc::MichaelHashMap< rcu_gpt, typename ml::MichaelList_RCU_GPT_cmp_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_RCU_GPT_cmp_stdAlloc_seqcst; + typedef MichaelHashMap< cds::gc::HP, typename ml::MichaelList_HP_cmp_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_HP_cmp_stdAlloc_seqcst; + typedef MichaelHashMap< cds::gc::DHP, typename ml::MichaelList_DHP_cmp_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_DHP_cmp_stdAlloc_seqcst; + typedef MichaelHashMap< cds::gc::nogc, typename ml::MichaelList_NOGC_cmp_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_NOGC_cmp_stdAlloc_seqcst; + typedef MichaelHashMap< rcu_gpi, typename ml::MichaelList_RCU_GPI_cmp_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_RCU_GPI_cmp_stdAlloc_seqcst; + typedef MichaelHashMap< rcu_gpb, typename ml::MichaelList_RCU_GPB_cmp_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_RCU_GPB_cmp_stdAlloc_seqcst; + typedef MichaelHashMap< rcu_gpt, typename ml::MichaelList_RCU_GPT_cmp_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_RCU_GPT_cmp_stdAlloc_seqcst; #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED - typedef cc::MichaelHashMap< rcu_shb, typename ml::MichaelList_RCU_SHB_cmp_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_RCU_SHB_cmp_stdAlloc_seqcst; - typedef cc::MichaelHashMap< rcu_sht, typename ml::MichaelList_RCU_SHT_cmp_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_RCU_SHT_cmp_stdAlloc_seqcst; + typedef MichaelHashMap< rcu_shb, typename ml::MichaelList_RCU_SHB_cmp_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_RCU_SHB_cmp_stdAlloc_seqcst; + typedef MichaelHashMap< rcu_sht, typename ml::MichaelList_RCU_SHT_cmp_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_RCU_SHT_cmp_stdAlloc_seqcst; #endif - typedef cc::MichaelHashMap< cds::gc::HP, typename ml::MichaelList_HP_less_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_HP_less_stdAlloc_seqcst; - typedef cc::MichaelHashMap< cds::gc::DHP, typename ml::MichaelList_DHP_less_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_DHP_less_stdAlloc_seqcst; - typedef cc::MichaelHashMap< cds::gc::nogc, typename ml::MichaelList_NOGC_less_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_NOGC_less_stdAlloc_seqcst; - typedef cc::MichaelHashMap< rcu_gpi, typename ml::MichaelList_RCU_GPI_less_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_RCU_GPI_less_stdAlloc_seqcst; - typedef cc::MichaelHashMap< rcu_gpb, typename ml::MichaelList_RCU_GPB_less_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_RCU_GPB_less_stdAlloc_seqcst; - typedef cc::MichaelHashMap< rcu_gpt, typename ml::MichaelList_RCU_GPT_less_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_RCU_GPT_less_stdAlloc_seqcst; + typedef MichaelHashMap< cds::gc::HP, typename ml::MichaelList_HP_less_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_HP_less_stdAlloc_seqcst; + typedef MichaelHashMap< cds::gc::DHP, typename ml::MichaelList_DHP_less_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_DHP_less_stdAlloc_seqcst; + typedef MichaelHashMap< cds::gc::nogc, typename ml::MichaelList_NOGC_less_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_NOGC_less_stdAlloc_seqcst; + typedef MichaelHashMap< rcu_gpi, typename ml::MichaelList_RCU_GPI_less_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_RCU_GPI_less_stdAlloc_seqcst; + typedef MichaelHashMap< rcu_gpb, typename ml::MichaelList_RCU_GPB_less_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_RCU_GPB_less_stdAlloc_seqcst; + typedef MichaelHashMap< rcu_gpt, typename ml::MichaelList_RCU_GPT_less_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_RCU_GPT_less_stdAlloc_seqcst; #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED - typedef cc::MichaelHashMap< rcu_shb, typename ml::MichaelList_RCU_SHB_less_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_RCU_SHB_less_stdAlloc_seqcst; - typedef cc::MichaelHashMap< rcu_sht, typename ml::MichaelList_RCU_SHT_less_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_RCU_SHT_less_stdAlloc_seqcst; + typedef MichaelHashMap< rcu_shb, typename ml::MichaelList_RCU_SHB_less_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_RCU_SHB_less_stdAlloc_seqcst; + typedef MichaelHashMap< rcu_sht, typename ml::MichaelList_RCU_SHT_less_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_RCU_SHT_less_stdAlloc_seqcst; #endif struct traits_MichaelSet_michaelAlloc : @@ -81,25 +100,25 @@ namespace map2 { { typedef memory::MichaelAllocator allocator; }; - typedef cc::MichaelHashMap< cds::gc::HP, typename ml::MichaelList_HP_cmp_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_HP_cmp_michaelAlloc; - typedef cc::MichaelHashMap< cds::gc::DHP, typename ml::MichaelList_DHP_cmp_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_DHP_cmp_michaelAlloc; - typedef cc::MichaelHashMap< cds::gc::nogc, typename ml::MichaelList_NOGC_cmp_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_NOGC_cmp_michaelAlloc; - typedef cc::MichaelHashMap< rcu_gpi, typename ml::MichaelList_RCU_GPI_cmp_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_RCU_GPI_cmp_michaelAlloc; - typedef cc::MichaelHashMap< rcu_gpb, typename ml::MichaelList_RCU_GPB_cmp_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_RCU_GPB_cmp_michaelAlloc; - typedef cc::MichaelHashMap< rcu_gpt, typename ml::MichaelList_RCU_GPT_cmp_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_RCU_GPT_cmp_michaelAlloc; + typedef MichaelHashMap< cds::gc::HP, typename ml::MichaelList_HP_cmp_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_HP_cmp_michaelAlloc; + typedef MichaelHashMap< cds::gc::DHP, typename ml::MichaelList_DHP_cmp_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_DHP_cmp_michaelAlloc; + typedef MichaelHashMap< cds::gc::nogc, typename ml::MichaelList_NOGC_cmp_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_NOGC_cmp_michaelAlloc; + typedef MichaelHashMap< rcu_gpi, typename ml::MichaelList_RCU_GPI_cmp_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_RCU_GPI_cmp_michaelAlloc; + typedef MichaelHashMap< rcu_gpb, typename ml::MichaelList_RCU_GPB_cmp_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_RCU_GPB_cmp_michaelAlloc; + typedef MichaelHashMap< rcu_gpt, typename ml::MichaelList_RCU_GPT_cmp_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_RCU_GPT_cmp_michaelAlloc; #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED - typedef cc::MichaelHashMap< rcu_shb, typename ml::MichaelList_RCU_SHB_cmp_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_RCU_SHB_cmp_michaelAlloc; - typedef cc::MichaelHashMap< rcu_sht, typename ml::MichaelList_RCU_SHT_cmp_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_RCU_SHT_cmp_michaelAlloc; + typedef MichaelHashMap< rcu_shb, typename ml::MichaelList_RCU_SHB_cmp_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_RCU_SHB_cmp_michaelAlloc; + typedef MichaelHashMap< rcu_sht, typename ml::MichaelList_RCU_SHT_cmp_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_RCU_SHT_cmp_michaelAlloc; #endif - typedef cc::MichaelHashMap< cds::gc::HP, typename ml::MichaelList_HP_less_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_HP_less_michaelAlloc; - typedef cc::MichaelHashMap< cds::gc::DHP, typename ml::MichaelList_DHP_less_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_DHP_less_michaelAlloc; - typedef cc::MichaelHashMap< cds::gc::nogc, typename ml::MichaelList_NOGC_less_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_NOGC_less_michaelAlloc; - typedef cc::MichaelHashMap< rcu_gpi, typename ml::MichaelList_RCU_GPI_less_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_RCU_GPI_less_michaelAlloc; - typedef cc::MichaelHashMap< rcu_gpb, typename ml::MichaelList_RCU_GPB_less_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_RCU_GPB_less_michaelAlloc; - typedef cc::MichaelHashMap< rcu_gpt, typename ml::MichaelList_RCU_GPT_less_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_RCU_GPT_less_michaelAlloc; + typedef MichaelHashMap< cds::gc::HP, typename ml::MichaelList_HP_less_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_HP_less_michaelAlloc; + typedef MichaelHashMap< cds::gc::DHP, typename ml::MichaelList_DHP_less_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_DHP_less_michaelAlloc; + typedef MichaelHashMap< cds::gc::nogc, typename ml::MichaelList_NOGC_less_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_NOGC_less_michaelAlloc; + typedef MichaelHashMap< rcu_gpi, typename ml::MichaelList_RCU_GPI_less_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_RCU_GPI_less_michaelAlloc; + typedef MichaelHashMap< rcu_gpb, typename ml::MichaelList_RCU_GPB_less_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_RCU_GPB_less_michaelAlloc; + typedef MichaelHashMap< rcu_gpt, typename ml::MichaelList_RCU_GPT_less_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_RCU_GPT_less_michaelAlloc; #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED - typedef cc::MichaelHashMap< rcu_shb, typename ml::MichaelList_RCU_SHB_less_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_RCU_SHB_less_michaelAlloc; - typedef cc::MichaelHashMap< rcu_sht, typename ml::MichaelList_RCU_SHT_less_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_RCU_SHT_less_michaelAlloc; + typedef MichaelHashMap< rcu_shb, typename ml::MichaelList_RCU_SHB_less_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_RCU_SHB_less_michaelAlloc; + typedef MichaelHashMap< rcu_sht, typename ml::MichaelList_RCU_SHT_less_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_RCU_SHT_less_michaelAlloc; #endif @@ -107,71 +126,71 @@ namespace map2 { // MichaelHashMap based on LazyKVList typedef lazy_list_type< Key, Value > ll; - typedef cc::MichaelHashMap< cds::gc::HP, typename ll::LazyList_HP_cmp_stdAlloc, traits_MichaelMap_hash > MichaelMap_Lazy_HP_cmp_stdAlloc; - typedef cc::MichaelHashMap< cds::gc::DHP, typename ll::LazyList_DHP_cmp_stdAlloc, traits_MichaelMap_hash > MichaelMap_Lazy_DHP_cmp_stdAlloc; - typedef cc::MichaelHashMap< cds::gc::nogc, typename ll::LazyList_NOGC_cmp_stdAlloc, traits_MichaelMap_hash > MichaelMap_Lazy_NOGC_cmp_stdAlloc; - typedef cc::MichaelHashMap< rcu_gpi, typename ll::LazyList_RCU_GPI_cmp_stdAlloc, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_GPI_cmp_stdAlloc; - typedef cc::MichaelHashMap< rcu_gpb, typename ll::LazyList_RCU_GPB_cmp_stdAlloc, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_GPB_cmp_stdAlloc; - typedef cc::MichaelHashMap< rcu_gpt, typename ll::LazyList_RCU_GPT_cmp_stdAlloc, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_GPT_cmp_stdAlloc; + typedef MichaelHashMap< cds::gc::HP, typename ll::LazyList_HP_cmp_stdAlloc, traits_MichaelMap_hash > MichaelMap_Lazy_HP_cmp_stdAlloc; + typedef MichaelHashMap< cds::gc::DHP, typename ll::LazyList_DHP_cmp_stdAlloc, traits_MichaelMap_hash > MichaelMap_Lazy_DHP_cmp_stdAlloc; + typedef MichaelHashMap< cds::gc::nogc, typename ll::LazyList_NOGC_cmp_stdAlloc, traits_MichaelMap_hash > MichaelMap_Lazy_NOGC_cmp_stdAlloc; + typedef MichaelHashMap< rcu_gpi, typename ll::LazyList_RCU_GPI_cmp_stdAlloc, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_GPI_cmp_stdAlloc; + typedef MichaelHashMap< rcu_gpb, typename ll::LazyList_RCU_GPB_cmp_stdAlloc, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_GPB_cmp_stdAlloc; + typedef MichaelHashMap< rcu_gpt, typename ll::LazyList_RCU_GPT_cmp_stdAlloc, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_GPT_cmp_stdAlloc; #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED - typedef cc::MichaelHashMap< rcu_shb, typename ll::LazyList_RCU_SHB_cmp_stdAlloc, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_SHB_cmp_stdAlloc; - typedef cc::MichaelHashMap< rcu_sht, typename ll::LazyList_RCU_SHT_cmp_stdAlloc, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_SHT_cmp_stdAlloc; + typedef MichaelHashMap< rcu_shb, typename ll::LazyList_RCU_SHB_cmp_stdAlloc, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_SHB_cmp_stdAlloc; + typedef MichaelHashMap< rcu_sht, typename ll::LazyList_RCU_SHT_cmp_stdAlloc, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_SHT_cmp_stdAlloc; #endif - typedef cc::MichaelHashMap< cds::gc::nogc, typename ll::LazyList_NOGC_unord_stdAlloc, traits_MichaelMap_hash > MichaelMap_Lazy_NOGC_unord_stdAlloc; + typedef MichaelHashMap< cds::gc::nogc, typename ll::LazyList_NOGC_unord_stdAlloc, traits_MichaelMap_hash > MichaelMap_Lazy_NOGC_unord_stdAlloc; - typedef cc::MichaelHashMap< cds::gc::HP, typename ll::LazyList_HP_less_stdAlloc, traits_MichaelMap_hash > MichaelMap_Lazy_HP_less_stdAlloc; - typedef cc::MichaelHashMap< cds::gc::DHP, typename ll::LazyList_DHP_less_stdAlloc, traits_MichaelMap_hash > MichaelMap_Lazy_DHP_less_stdAlloc; - typedef cc::MichaelHashMap< cds::gc::nogc, typename ll::LazyList_NOGC_less_stdAlloc, traits_MichaelMap_hash > MichaelMap_Lazy_NOGC_less_stdAlloc; - typedef cc::MichaelHashMap< rcu_gpi, typename ll::LazyList_RCU_GPI_less_stdAlloc, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_GPI_less_stdAlloc; - typedef cc::MichaelHashMap< rcu_gpb, typename ll::LazyList_RCU_GPB_less_stdAlloc, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_GPB_less_stdAlloc; - typedef cc::MichaelHashMap< rcu_gpt, typename ll::LazyList_RCU_GPT_less_stdAlloc, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_GPT_less_stdAlloc; + typedef MichaelHashMap< cds::gc::HP, typename ll::LazyList_HP_less_stdAlloc, traits_MichaelMap_hash > MichaelMap_Lazy_HP_less_stdAlloc; + typedef MichaelHashMap< cds::gc::DHP, typename ll::LazyList_DHP_less_stdAlloc, traits_MichaelMap_hash > MichaelMap_Lazy_DHP_less_stdAlloc; + typedef MichaelHashMap< cds::gc::nogc, typename ll::LazyList_NOGC_less_stdAlloc, traits_MichaelMap_hash > MichaelMap_Lazy_NOGC_less_stdAlloc; + typedef MichaelHashMap< rcu_gpi, typename ll::LazyList_RCU_GPI_less_stdAlloc, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_GPI_less_stdAlloc; + typedef MichaelHashMap< rcu_gpb, typename ll::LazyList_RCU_GPB_less_stdAlloc, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_GPB_less_stdAlloc; + typedef MichaelHashMap< rcu_gpt, typename ll::LazyList_RCU_GPT_less_stdAlloc, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_GPT_less_stdAlloc; #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED - typedef cc::MichaelHashMap< rcu_shb, typename ll::LazyList_RCU_SHB_less_stdAlloc, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_SHB_less_stdAlloc; - typedef cc::MichaelHashMap< rcu_sht, typename ll::LazyList_RCU_SHT_less_stdAlloc, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_SHT_less_stdAlloc; + typedef MichaelHashMap< rcu_shb, typename ll::LazyList_RCU_SHB_less_stdAlloc, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_SHB_less_stdAlloc; + typedef MichaelHashMap< rcu_sht, typename ll::LazyList_RCU_SHT_less_stdAlloc, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_SHT_less_stdAlloc; #endif - typedef cc::MichaelHashMap< cds::gc::HP, typename ll::LazyList_HP_cmp_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_Lazy_HP_cmp_stdAlloc_seqcst; - typedef cc::MichaelHashMap< cds::gc::DHP, typename ll::LazyList_DHP_cmp_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_Lazy_DHP_cmp_stdAlloc_seqcst; - typedef cc::MichaelHashMap< cds::gc::nogc, typename ll::LazyList_NOGC_cmp_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_Lazy_NOGC_cmp_stdAlloc_seqcst; - typedef cc::MichaelHashMap< rcu_gpi, typename ll::LazyList_RCU_GPI_cmp_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_GPI_cmp_stdAlloc_seqcst; - typedef cc::MichaelHashMap< rcu_gpb, typename ll::LazyList_RCU_GPB_cmp_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_GPB_cmp_stdAlloc_seqcst; - typedef cc::MichaelHashMap< rcu_gpt, typename ll::LazyList_RCU_GPT_cmp_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_GPT_cmp_stdAlloc_seqcst; + typedef MichaelHashMap< cds::gc::HP, typename ll::LazyList_HP_cmp_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_Lazy_HP_cmp_stdAlloc_seqcst; + typedef MichaelHashMap< cds::gc::DHP, typename ll::LazyList_DHP_cmp_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_Lazy_DHP_cmp_stdAlloc_seqcst; + typedef MichaelHashMap< cds::gc::nogc, typename ll::LazyList_NOGC_cmp_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_Lazy_NOGC_cmp_stdAlloc_seqcst; + typedef MichaelHashMap< rcu_gpi, typename ll::LazyList_RCU_GPI_cmp_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_GPI_cmp_stdAlloc_seqcst; + typedef MichaelHashMap< rcu_gpb, typename ll::LazyList_RCU_GPB_cmp_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_GPB_cmp_stdAlloc_seqcst; + typedef MichaelHashMap< rcu_gpt, typename ll::LazyList_RCU_GPT_cmp_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_GPT_cmp_stdAlloc_seqcst; #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED - typedef cc::MichaelHashMap< rcu_shb, typename ll::LazyList_RCU_SHB_cmp_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_SHB_cmp_stdAlloc_seqcst; - typedef cc::MichaelHashMap< rcu_sht, typename ll::LazyList_RCU_SHT_cmp_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_SHT_cmp_stdAlloc_seqcst; + typedef MichaelHashMap< rcu_shb, typename ll::LazyList_RCU_SHB_cmp_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_SHB_cmp_stdAlloc_seqcst; + typedef MichaelHashMap< rcu_sht, typename ll::LazyList_RCU_SHT_cmp_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_SHT_cmp_stdAlloc_seqcst; #endif - typedef cc::MichaelHashMap< cds::gc::HP, typename ll::LazyList_HP_less_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_Lazy_HP_less_stdAlloc_seqcst; - typedef cc::MichaelHashMap< cds::gc::DHP, typename ll::LazyList_DHP_less_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_Lazy_DHP_less_stdAlloc_seqcst; - typedef cc::MichaelHashMap< cds::gc::nogc, typename ll::LazyList_NOGC_less_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_Lazy_NOGC_less_stdAlloc_seqcst; - typedef cc::MichaelHashMap< rcu_gpi, typename ll::LazyList_RCU_GPI_less_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_GPI_less_stdAlloc_seqcst; - typedef cc::MichaelHashMap< rcu_gpb, typename ll::LazyList_RCU_GPB_less_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_GPB_less_stdAlloc_seqcst; - typedef cc::MichaelHashMap< rcu_gpt, typename ll::LazyList_RCU_GPT_less_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_GPT_less_stdAlloc_seqcst; + typedef MichaelHashMap< cds::gc::HP, typename ll::LazyList_HP_less_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_Lazy_HP_less_stdAlloc_seqcst; + typedef MichaelHashMap< cds::gc::DHP, typename ll::LazyList_DHP_less_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_Lazy_DHP_less_stdAlloc_seqcst; + typedef MichaelHashMap< cds::gc::nogc, typename ll::LazyList_NOGC_less_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_Lazy_NOGC_less_stdAlloc_seqcst; + typedef MichaelHashMap< rcu_gpi, typename ll::LazyList_RCU_GPI_less_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_GPI_less_stdAlloc_seqcst; + typedef MichaelHashMap< rcu_gpb, typename ll::LazyList_RCU_GPB_less_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_GPB_less_stdAlloc_seqcst; + typedef MichaelHashMap< rcu_gpt, typename ll::LazyList_RCU_GPT_less_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_GPT_less_stdAlloc_seqcst; #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED - typedef cc::MichaelHashMap< rcu_shb, typename ll::LazyList_RCU_SHB_less_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_SHB_less_stdAlloc_seqcst; - typedef cc::MichaelHashMap< rcu_sht, typename ll::LazyList_RCU_SHT_less_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_SHT_less_stdAlloc_seqcst; + typedef MichaelHashMap< rcu_shb, typename ll::LazyList_RCU_SHB_less_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_SHB_less_stdAlloc_seqcst; + typedef MichaelHashMap< rcu_sht, typename ll::LazyList_RCU_SHT_less_stdAlloc_seqcst, traits_MichaelMap_hash > MichaelMap_Lazy_RCU_SHT_less_stdAlloc_seqcst; #endif - typedef cc::MichaelHashMap< cds::gc::HP, typename ll::LazyList_HP_cmp_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_Lazy_HP_cmp_michaelAlloc; - typedef cc::MichaelHashMap< cds::gc::DHP, typename ll::LazyList_DHP_cmp_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_Lazy_DHP_cmp_michaelAlloc; - typedef cc::MichaelHashMap< cds::gc::nogc, typename ll::LazyList_NOGC_cmp_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_Lazy_NOGC_cmp_michaelAlloc; - typedef cc::MichaelHashMap< rcu_gpi, typename ll::LazyList_RCU_GPI_cmp_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_Lazy_RCU_GPI_cmp_michaelAlloc; - typedef cc::MichaelHashMap< rcu_gpb, typename ll::LazyList_RCU_GPB_cmp_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_Lazy_RCU_GPB_cmp_michaelAlloc; - typedef cc::MichaelHashMap< rcu_gpt, typename ll::LazyList_RCU_GPT_cmp_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_Lazy_RCU_GPT_cmp_michaelAlloc; + typedef MichaelHashMap< cds::gc::HP, typename ll::LazyList_HP_cmp_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_Lazy_HP_cmp_michaelAlloc; + typedef MichaelHashMap< cds::gc::DHP, typename ll::LazyList_DHP_cmp_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_Lazy_DHP_cmp_michaelAlloc; + typedef MichaelHashMap< cds::gc::nogc, typename ll::LazyList_NOGC_cmp_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_Lazy_NOGC_cmp_michaelAlloc; + typedef MichaelHashMap< rcu_gpi, typename ll::LazyList_RCU_GPI_cmp_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_Lazy_RCU_GPI_cmp_michaelAlloc; + typedef MichaelHashMap< rcu_gpb, typename ll::LazyList_RCU_GPB_cmp_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_Lazy_RCU_GPB_cmp_michaelAlloc; + typedef MichaelHashMap< rcu_gpt, typename ll::LazyList_RCU_GPT_cmp_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_Lazy_RCU_GPT_cmp_michaelAlloc; #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED - typedef cc::MichaelHashMap< rcu_shb, typename ll::LazyList_RCU_SHB_cmp_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_Lazy_RCU_SHB_cmp_michaelAlloc; - typedef cc::MichaelHashMap< rcu_sht, typename ll::LazyList_RCU_SHT_cmp_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_Lazy_RCU_SHT_cmp_michaelAlloc; + typedef MichaelHashMap< rcu_shb, typename ll::LazyList_RCU_SHB_cmp_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_Lazy_RCU_SHB_cmp_michaelAlloc; + typedef MichaelHashMap< rcu_sht, typename ll::LazyList_RCU_SHT_cmp_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_Lazy_RCU_SHT_cmp_michaelAlloc; #endif - typedef cc::MichaelHashMap< cds::gc::HP, typename ll::LazyList_HP_less_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_Lazy_HP_less_michaelAlloc; - typedef cc::MichaelHashMap< cds::gc::DHP, typename ll::LazyList_DHP_less_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_Lazy_DHP_less_michaelAlloc; - typedef cc::MichaelHashMap< cds::gc::nogc, typename ll::LazyList_NOGC_less_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_Lazy_NOGC_less_michaelAlloc; - typedef cc::MichaelHashMap< rcu_gpi, typename ll::LazyList_RCU_GPI_less_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_Lazy_RCU_GPI_less_michaelAlloc; - typedef cc::MichaelHashMap< rcu_gpb, typename ll::LazyList_RCU_GPB_less_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_Lazy_RCU_GPB_less_michaelAlloc; - typedef cc::MichaelHashMap< rcu_gpt, typename ll::LazyList_RCU_GPT_less_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_Lazy_RCU_GPT_less_michaelAlloc; + typedef MichaelHashMap< cds::gc::HP, typename ll::LazyList_HP_less_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_Lazy_HP_less_michaelAlloc; + typedef MichaelHashMap< cds::gc::DHP, typename ll::LazyList_DHP_less_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_Lazy_DHP_less_michaelAlloc; + typedef MichaelHashMap< cds::gc::nogc, typename ll::LazyList_NOGC_less_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_Lazy_NOGC_less_michaelAlloc; + typedef MichaelHashMap< rcu_gpi, typename ll::LazyList_RCU_GPI_less_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_Lazy_RCU_GPI_less_michaelAlloc; + typedef MichaelHashMap< rcu_gpb, typename ll::LazyList_RCU_GPB_less_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_Lazy_RCU_GPB_less_michaelAlloc; + typedef MichaelHashMap< rcu_gpt, typename ll::LazyList_RCU_GPT_less_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_Lazy_RCU_GPT_less_michaelAlloc; #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED - typedef cc::MichaelHashMap< rcu_shb, typename ll::LazyList_RCU_SHB_less_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_Lazy_RCU_SHB_less_michaelAlloc; - typedef cc::MichaelHashMap< rcu_sht, typename ll::LazyList_RCU_SHT_less_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_Lazy_RCU_SHT_less_michaelAlloc; + typedef MichaelHashMap< rcu_shb, typename ll::LazyList_RCU_SHB_less_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_Lazy_RCU_SHB_less_michaelAlloc; + typedef MichaelHashMap< rcu_sht, typename ll::LazyList_RCU_SHT_less_michaelAlloc, traits_MichaelSet_michaelAlloc > MichaelMap_Lazy_RCU_SHT_less_michaelAlloc; #endif }; diff --git a/tests/unit/map2/map_type_multilevel_hashmap.h b/tests/unit/map2/map_type_multilevel_hashmap.h new file mode 100644 index 00000000..0e0b10fc --- /dev/null +++ b/tests/unit/map2/map_type_multilevel_hashmap.h @@ -0,0 +1,61 @@ +//$$CDS-header$$ + +#ifndef CDSUNIT_MAP_TYPE_MULTILEVEL_HASHMAP_H +#define CDSUNIT_MAP_TYPE_MULTILEVEL_HASHMAP_H + +#include "map2/map_type.h" + +#include +#include + +#include "print_multilevel_hashset_stat.h" + +namespace map2 { + + template + class MultiLevelHashMap : public cc::MultiLevelHashMap< GC, Key, T, Traits > + { + typedef cc::MultiLevelHashMap< GC, Key, T, Traits > base_class; + public: + template + MultiLevelHashMap( Config const& cfg) + : base_class( cfg.c_nMultiLevelMap_HeadBits, cfg.c_nMultiLevelMap_ArrayBits ) + {} + + // for testing + static CDS_CONSTEXPR bool const c_bExtractSupported = true; + static CDS_CONSTEXPR bool const c_bLoadFactorDepended = false; + static CDS_CONSTEXPR bool const c_erase_with_supported = false; + static CDS_CONSTEXPR bool const c_extract_with_supported = false; + }; + + struct tag_MultiLevelHashMap; + + template + struct map_type< map2::tag_MultiLevelHashMap, Key, Value >: public map_type_base< Key, Value > + { + typedef map_type_base< Key, Value > base_class; + typedef typename base_class::compare compare; + typedef typename base_class::less less; + + typedef MultiLevelHashMap< cds::gc::HP, Key, Value > MultiLevelHashMap_hp_stdhash; + typedef MultiLevelHashMap< cds::gc::DHP, Key, Value > MultiLevelHashMap_dhp_stdhash; + + struct traits_MultiLevelHashMap_stat: public cc::multilevel_hashmap::make_traits< + co::stat< cc::multilevel_hashmap::stat<>> + >::type + {}; + + typedef MultiLevelHashMap< cds::gc::HP, Key, Value, traits_MultiLevelHashMap_stat > MultiLevelHashMap_hp_stdhash_stat; + typedef MultiLevelHashMap< cds::gc::DHP, Key, Value, traits_MultiLevelHashMap_stat > MultiLevelHashMap_dhp_stdhash_stat; + }; + + template + static inline void print_stat( cc::MultiLevelHashMap< GC, K, T, Traits > const& m ) + { + CPPUNIT_MSG( m.statistics() ); + } + +} // namespace map2 + +#endif // #ifndef CDSUNIT_MAP_TYPE_MULTILEVEL_HASHMAP_H -- 2.34.1