X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fcontainer%2Fsplit_list_map.h;h=29cd7fc8c7a7ac840323a924fda0db4125cf7946;hb=c14ae188467d82f4b9227dcfc1052fcd113ad459;hp=d9af00eb83f1aca845f4a39591d037994d12be47;hpb=6e2784d24f15873dc5b971499276cc8e4147fd46;p=libcds.git diff --git a/cds/container/split_list_map.h b/cds/container/split_list_map.h index d9af00eb..29cd7fc8 100644 --- a/cds/container/split_list_map.h +++ b/cds/container/split_list_map.h @@ -1,7 +1,35 @@ -//$$CDS-header$$ - -#ifndef __CDS_CONTAINER_SPLIT_LIST_MAP_H -#define __CDS_CONTAINER_SPLIT_LIST_MAP_H +/* + This file is a part of libcds - Concurrent Data Structures library + + (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016 + + 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_H +#define CDSLIB_CONTAINER_SPLIT_LIST_MAP_H #include #include @@ -19,7 +47,7 @@ namespace cds { namespace container { See intrusive::SplitListSet for a brief description of the split-list algorithm. Template parameters: - - \p GC - Garbage collector used + - \p GC - Garbage collector used like \p cds::gc::HP or \p cds::gc::DHP - \p Key - key type of an item stored in the map. It should be copy-constructible - \p Value - value type stored in the map - \p Traits - map traits, default is \p split_list::traits. Instead of declaring \p %split_list::traits -based @@ -75,7 +103,7 @@ namespace cds { namespace container { You may use the modern option-based declaration instead of classic type-traits-based one: \code - typedef cc:SplitListMap< + typedef cc::SplitListMap< cs::gc::DHP // GC used ,int // key type ,std::string // value type @@ -127,7 +155,7 @@ namespace cds { namespace container { typedef GC gc; ///< Garbage collector typedef Key key_type; ///< key type typedef Value mapped_type; ///< type of value to be stored in the map - typedef Traits options; ///< Map traits + typedef Traits traits; ///< Map traits typedef std::pair value_type ; ///< key-value pair type typedef typename base_class::ordered_list ordered_list; ///< Underlying ordered list class @@ -137,6 +165,9 @@ namespace cds { namespace container { typedef typename base_class::item_counter item_counter; ///< Item counter type typedef typename base_class::stat stat; ///< Internal statistics + /// Count of hazard pointer required + static CDS_CONSTEXPR const size_t c_nHazardPtrCount = base_class::c_nHazardPtrCount; + protected: //@cond typedef typename base_class::maker::traits::key_accessor key_accessor; @@ -145,17 +176,54 @@ namespace cds { namespace container { public: /// Guarded pointer - typedef cds::gc::guarded_ptr< gc, node_type, value_type, details::guarded_ptr_cast_set > guarded_ptr; + typedef typename gc::template guarded_ptr< node_type, value_type, details::guarded_ptr_cast_set > guarded_ptr; public: - /// Forward iterator (see \p SplitListSet::iterator) + ///@name Forward iterators (only for debugging purpose) + //@{ + /// Forward iterator /** - Remember, the iterator operator -> and operator * returns \ref value_type pointer and reference. - To access item key and value use it->first and it->second respectively. + The forward iterator for a split-list has the following features: + - it has no post-increment operator + - it depends on underlying ordered list iterator + - The iterator object cannot be moved across thread boundary because it contains GC's guard that is thread-private GC data. + - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent + deleting operations it is no guarantee that you iterate all item in the split-list. + Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread. + + @warning Use this iterator on the concurrent container for debugging purpose only. + + The iterator interface: + \code + class iterator { + public: + // Default constructor + iterator(); + + // Copy construtor + iterator( iterator const& src ); + + // Dereference operator + value_type * operator ->() const; + + // Dereference operator + value_type& operator *() const; + + // Preincrement operator + iterator& operator ++(); + + // Assignment operator + iterator& operator = (iterator const& src); + + // Equality operators + bool operator ==(iterator const& i ) const; + bool operator !=(iterator const& i ) const; + }; + \endcode */ typedef typename base_class::iterator iterator; - /// Const forward iterator (see SplitListSet::const_iterator) + /// Const forward iterator typedef typename base_class::const_iterator const_iterator; /// Returns a forward iterator addressing the first element in a map @@ -179,28 +247,29 @@ namespace cds { namespace container { } /// Returns a forward const iterator addressing the first element in a map - //@{ const_iterator begin() const { return base_class::begin(); } + + /// Returns a forward const iterator addressing the first element in a map const_iterator cbegin() const { return base_class::cbegin(); } - //@} /// Returns an const iterator that addresses the location succeeding the last element in a map - //@{ const_iterator end() const { return base_class::end(); } + + /// Returns an const iterator that addresses the location succeeding the last element in a map const_iterator cend() const { return base_class::cend(); } - //@} + //@} public: /// Initializes split-ordered map of default capacity @@ -236,8 +305,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 @@ -254,8 +322,7 @@ namespace cds { namespace container { template 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 @@ -290,10 +357,10 @@ namespace cds { namespace container { synchronization. */ 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 from \p args @@ -305,22 +372,17 @@ 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 the node /** The operation performs inserting or changing data 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). + If \p key is not found in the map, then \p key is inserted iff \p bAllowInsert is \p true. 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: + + The functor signature is: \code struct my_functor { void operator()( bool bNew, value_type& item ); @@ -329,25 +391,36 @@ 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 item - item of the map - 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 is in the map. @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_erase_val @@ -371,7 +444,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 @@ -412,12 +485,12 @@ namespace cds { namespace container { /// Extracts the item with specified \p key /** \anchor cds_nonintrusive_SplitListMap_hp_extract The function searches an item with key equal to \p key, - unlinks it from the map, and returns it in \p dest parameter. - If the item with key equal to \p key is not found the function returns \p false. + unlinks it from the map, and returns it as \p guarded_ptr. + If \p key is not found the function returns an empty guarded pointer. Note the compare functor should accept a parameter of type \p K that may be not the same as \p value_type. - The extracted item is freed automatically when returned \ref guarded_ptr object will be destroyed or released. + The extracted item is freed automatically when returned \p guarded_ptr object will be destroyed or released. @note Each \p guarded_ptr object uses the GC's guard that can be limited resource. Usage: @@ -426,24 +499,24 @@ namespace cds { namespace container { splitlist_map theMap; // ... { - splitlist_map::guarded_ptr gp; - theMap.extract( gp, 5 ); - // Deal with gp - // ... - + splitlist_map::guarded_ptr gp(theMap.extract( 5 )); + if ( gp ) { + // Deal with gp + // ... + } // Destructor of gp releases internal HP guard } \endcode */ template - bool extract( guarded_ptr& dest, K const& key ) + guarded_ptr extract( K const& key ) { - return base_class::extract_( dest.guard(), key ); + return base_class::extract_( key ); } /// Extracts the item using compare functor \p pred /** - The function is an analog of \ref cds_nonintrusive_SplitListMap_hp_extract "extract(guarded_ptr&, K const&)" + The function is an analog of \ref cds_nonintrusive_SplitListMap_hp_extract "extract(K const&)" but \p pred predicate is used for key comparing. \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p K @@ -451,10 +524,10 @@ namespace cds { namespace container { \p pred must imply the same element order as the comparator used for building the map. */ template - bool extract_with( guarded_ptr& dest, K const& key, Less pred ) + guarded_ptr extract_with( K const& key, Less pred ) { CDS_UNUSED( pred ); - return base_class::extract_with_( dest.guard(), key, cds::details::predicate_wrapper() ); + return base_class::extract_with_( key, cds::details::predicate_wrapper()); } /// Finds the key \p key @@ -498,38 +571,55 @@ namespace cds { namespace container { [&f](value_type& pair, K const&){ f( pair ); } ); } - /// Finds the key \p key - /** \anchor cds_nonintrusive_SplitListMap_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. + + Note the hash functor specified for class \p Traits template parameter + should accept a parameter of type \p Q that can be not the same as \p value_type. + Otherwise, you may use \p contains( Q const&, Less pred ) functions with explicit predicate for key comparing. */ 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 ); + 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_SplitListMap_find_val "find(K const&)" - but \p pred is used for key comparing. + The function is similar to 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( 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_nonintrusive_SplitListMap_hp_get The function searches the item with key equal to \p key - and assigns the item found to guarded pointer \p ptr. - The function returns \p true if \p key is found, and \p false otherwise. - If \p key is not found the \p ptr parameter is not changed. + and returns the item found as a guarded pointer. + If \p key is not found the function returns an empty guarded pointer. @note Each \p guarded_ptr object uses one GC's guard which can be limited resource. @@ -539,8 +629,8 @@ namespace cds { namespace container { splitlist_map theMap; // ... { - splitlist_map::guarded_ptr gp; - if ( theMap.get( gp, 5 )) { + splitlist_map::guarded_ptr gp(theMap.get( 5 )); + if ( gp ) { // Deal with gp //... } @@ -552,14 +642,14 @@ namespace cds { namespace container { should accept a parameter of type \p K that can be not the same as \p value_type. */ template - bool get( guarded_ptr& ptr, K const& key ) + guarded_ptr get( K const& key ) { - return base_class::get_( ptr.guard(), key ); + return base_class::get_( key ); } /// Finds \p key and return the item found /** - The function is an analog of \ref cds_nonintrusive_SplitListMap_hp_get "get( guarded_ptr&, K const&)" + The function is an analog of \ref cds_nonintrusive_SplitListMap_hp_get "get( K const&)" but \p pred is used for comparing the keys. \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p K @@ -567,10 +657,10 @@ namespace cds { namespace container { \p pred must imply the same element order as the comparator used for building the map. */ template - bool get_with( guarded_ptr& ptr, K const& key, Less pred ) + guarded_ptr get_with( K const& key, Less pred ) { CDS_UNUSED( pred ); - return base_class::get_with_( ptr.guard(), key, cds::details::predicate_wrapper() ); + return base_class::get_with_( key, cds::details::predicate_wrapper()); } /// Clears the map (not atomic) @@ -605,4 +695,4 @@ namespace cds { namespace container { }} // namespace cds::container -#endif // #ifndef __CDS_CONTAINER_SPLIT_LIST_MAP_H +#endif // #ifndef CDSLIB_CONTAINER_SPLIT_LIST_MAP_H