X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fcontainer%2Fsplit_list_map_rcu.h;h=99bf6c958060485718a77f22e8c82fcc54e46281;hb=e28f9419df082f58c24afa47c8202551e38be002;hp=3354a1f971d0d6e968cef654a2afe4f4616a1c08;hpb=68c4bb6ce67fc8fccf8d850868e1e95b91f334a4;p=libcds.git diff --git a/cds/container/split_list_map_rcu.h b/cds/container/split_list_map_rcu.h index 3354a1f9..99bf6c95 100644 --- a/cds/container/split_list_map_rcu.h +++ b/cds/container/split_list_map_rcu.h @@ -1,7 +1,35 @@ -//$$CDS-header$$ +/* + This file is a part of libcds - Concurrent Data Structures library -#ifndef __CDS_CONTAINER_SPLIT_LIST_MAP_RCU_H -#define __CDS_CONTAINER_SPLIT_LIST_MAP_RCU_H + (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017 + + Source code repo: http://github.com/khizmax/libcds/ + Download: http://sourceforge.net/projects/libcds/files/ + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +#ifndef CDSLIB_CONTAINER_SPLIT_LIST_MAP_RCU_H +#define CDSLIB_CONTAINER_SPLIT_LIST_MAP_RCU_H #include #include @@ -112,7 +140,7 @@ namespace cds { namespace container { You may use the modern option-based declaration instead of classic traits-based one: \code - typedef cc:SplitListMap< + typedef cc::SplitListMap< cds::urcu::gc > // RCU type ,int // key type ,std::string // value type @@ -178,6 +206,7 @@ namespace cds { namespace container { typedef typename base_class::exempt_ptr exempt_ptr; ///< pointer to extracted node /// Group of \p extract_xxx functions require external locking if underlying ordered list requires that static CDS_CONSTEXPR const bool c_bExtractLockExternal = base_class::c_bExtractLockExternal; + typedef typename base_class::raw_ptr raw_ptr; ///< type of \p get() return value protected: //@cond @@ -270,8 +299,7 @@ namespace cds { namespace container { template bool insert( K const& key ) { - //TODO: pass arguments by reference (make_pair makes copy) - return base_class::insert( std::make_pair( key, mapped_type() ) ); + return base_class::emplace( key_type( key ), mapped_type()); } /// Inserts new node @@ -291,7 +319,7 @@ namespace cds { namespace container { bool insert( K const& key, V const& val ) { //TODO: pass arguments by reference (make_pair makes copy) - return base_class::insert( std::make_pair(key, val) ); + return base_class::emplace( key_type( key ), mapped_type( val )); } /// Inserts new node and initialize it by a functor @@ -326,10 +354,10 @@ namespace cds { namespace container { The function applies RCU lock internally. */ template - bool insert_key( K const& key, Func func ) + bool insert_with( K const& key, Func func ) { //TODO: pass arguments by reference (make_pair makes copy) - return base_class::insert( std::make_pair( key, mapped_type() ), func ); + return base_class::insert( std::make_pair( key_type( key ), mapped_type()), func ); } /// For key \p key inserts data of type \p mapped_type created in-place from \p args @@ -343,17 +371,18 @@ namespace cds { namespace container { template bool emplace( K&& key, Args&&... args ) { - return base_class::emplace( std::forward(key), std::move(mapped_type(std::forward(args)...))); + return base_class::emplace( key_type( std::forward( key )), mapped_type( std::forward(args)... )); } - /// 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; in this case the \p key_type should be - constructible from type \p K. - Otherwise, the functor \p func is called with item found. + 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 { @@ -362,31 +391,40 @@ namespace cds { namespace container { \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; - however, \p func must guarantee that during changing no any other modifications - could be made on this item by concurrent threads. + 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, + Returns std::pair where \p first is true if operation is successful, \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 ordered list 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 ensure( K const& key, Func func ) + std::pair update( K const& key, Func func, bool bAllowInsert = true ) { //TODO: pass arguments by reference (make_pair makes copy) - return base_class::ensure( std::make_pair( key, mapped_type() ), - [&func](bool bNew, value_type& item, value_type const& /*val*/) { + typedef decltype( std::make_pair( key_type( key ), mapped_type())) arg_pair_type; + + return base_class::update( std::make_pair( key_type( key ), mapped_type()), + [&func]( bool bNew, value_type& item, arg_pair_type const& /*val*/ ) { func( bNew, item ); - } ); + }, + bAllowInsert ); } + //@cond + template + CDS_DEPRECATED("ensure() is deprecated, use update()") + std::pair ensure( K const& key, Func func ) + { + return update( key, func, true ); + } + //@endcond /// Deletes \p key from the map /** \anchor cds_nonintrusive_SplitListMap_rcu_erase_val @@ -412,7 +450,7 @@ namespace cds { namespace container { bool erase_with( K const& key, Less pred ) { CDS_UNUSED( pred ); - return base_class::erase_with( key, cds::details::predicate_wrapper() ); + return base_class::erase_with( key, cds::details::predicate_wrapper()); } /// Deletes \p key from the map @@ -458,31 +496,29 @@ namespace cds { namespace container { unlinks it from the map, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found. If the item with the key equal to \p key is not found the function returns an empty \p exempt_ptr. - @note The function does NOT call RCU read-side lock or synchronization, - and does NOT dispose the item found. It just excludes the item from the map - and returns a pointer to item found. - You should lock RCU before calling of the function, and you should synchronize RCU - outside the RCU lock to free extracted item + Depends on ordered list you should or should not lock RCU before calling of this function: + - for the set based on \ref cds_intrusive_MichaelList_rcu "MichaelList" RCU should not be locked + - for the set based on \ref cds_intrusive_LazyList_rcu "LazyList" RCU should be locked + See ordered list implementation for details. \code typedef cds::urcu::gc< general_buffered<> > rcu; + + // Split-list set based on MichaelList by default typedef cds::container::SplitListMap< rcu, int, Foo > splitlist_map; splitlist_map theMap; // ... typename splitlist_map::exempt_ptr p; - { - // first, we should lock RCU - typename splitlist_map::rcu_lock lock; - // Now, you can apply extract function - // Note that you must not delete the item found inside the RCU lock - p = theMap.extract( 10 ) - if ( p ) { - // do something with p - ... - } + // For MichaelList we should not lock RCU + + // Now, you can apply extract function + p = theMap.extract( 10 ) + if ( p ) { + // do something with p + ... } // We may safely release p here @@ -498,8 +534,7 @@ namespace cds { namespace container { /// Extracts an item from the map using \p pred predicate for searching /** - The function is an analog of \ref cds_nonintrusive_SplitListMap_rcu_extract "extract(exempt_ptr&, K const&)" - but \p pred is used for key comparing. + The function is an analog of \p extract(K const&) 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 map. */ @@ -553,38 +588,52 @@ namespace cds { namespace container { [&f](value_type& pair, K const&){ f( pair ); } ); } - /// Finds the key \p key - /** \anchor cds_nonintrusive_SplitListMap_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 base_class::contains( key ); + } + //@cond + template + CDS_DEPRECATED("deprecated, use contains()") bool find( K const& key ) { return base_class::find( 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_SplitListMap_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 find_with( K const& key, Less pred ) + bool contains( K const& key, Less pred ) { CDS_UNUSED( pred ); - return base_class::find_with( key, cds::details::predicate_wrapper() ); + return base_class::contains( key, cds::details::predicate_wrapper()); + } + //@cond + template + CDS_DEPRECATED("deprecated, use contains()") + bool find_with( K const& key, Less pred ) + { + return contains( key, pred ); } + //@endcond /// Finds \p key and return the item found /** \anchor cds_intrusive_SplitListMap_rcu_get The function searches the item with key equal to \p key and returns the pointer to item found. - If \p key is not found it returns \p nullptr. + If \p key is not found it returns empty \p raw_ptr. Note the compare functor should accept a parameter of type \p K that can be not the same as \p value_type. @@ -599,7 +648,7 @@ namespace cds { namespace container { // Lock RCU typename splitlist_map::rcu_lock lock; - typename splitlist_map::value_type * pVal = theMap.get( 5 ); + typename splitlist_map::raw_ptr pVal = theMap.get( 5 ); if ( pVal ) { // Deal with pVal //... @@ -610,7 +659,7 @@ namespace cds { namespace container { \endcode */ template - value_type * get( K const& key ) + raw_ptr get( K const& key ) { return base_class::get( key ); } @@ -625,7 +674,7 @@ namespace cds { namespace container { \p pred must imply the same element order as the comparator used for building the map. */ template - value_type * get_with( K const& key, Less pred ) + raw_ptr get_with( K const& key, Less pred ) { CDS_UNUSED( pred ); return base_class::get_with( key, cds::details::predicate_wrapper()); @@ -658,8 +707,14 @@ namespace cds { namespace container { { return base_class::statistics(); } + + /// Returns internal statistics for \p ordered_list + typename ordered_list::stat const& list_statistics() const + { + return base_class::list_statistics(); + } }; }} // namespace cds::container -#endif // #ifndef __CDS_CONTAINER_SPLIT_LIST_MAP_RCU_H +#endif // #ifndef CDSLIB_CONTAINER_SPLIT_LIST_MAP_RCU_H