cds/container/split_list_set.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_CONTAINER_SPLIT_LIST_SET_H
  32 #define CDSLIB_CONTAINER_SPLIT_LIST_SET_H
  33
  34 #include <cds/intrusive/split_list.h>
  35 #include <cds/container/details/make_split_list_set.h>
  36 #include <cds/container/details/guarded_ptr_cast.h>
  37
  38 namespace cds { namespace container {
  39
  40     /// Split-ordered list set
  41     /** @ingroup cds_nonintrusive_set
  42         \anchor cds_nonintrusive_SplitListSet_hp
  43
  44         Hash table implementation based on split-ordered list algorithm discovered by Ori Shalev and Nir Shavit, see
  45         - [2003] Ori Shalev, Nir Shavit "Split-Ordered Lists - Lock-free Resizable Hash Tables"
  46         - [2008] Nir Shavit "The Art of Multiprocessor Programming"
  47
  48         See \p intrusive::SplitListSet for a brief description of the split-list algorithm.
  49
  50         Template parameters:
  51         - \p GC - Garbage collector used
  52         - \p T - type to be stored in the split-list.
  53         - \p Traits - type traits, default is \p split_list::traits. Instead of declaring \p split_list::traits -based
  54             struct you may apply option-based notation with \p split_list::make_traits metafunction.
  55
  56         There are the specializations:
  57         - for \ref cds_urcu_desc "RCU" - declared in <tt>cd/container/split_list_set_rcu.h</tt>,
  58             see \ref cds_nonintrusive_SplitListSet_rcu "SplitListSet<RCU>".
  59         - for \ref cds::gc::nogc declared in <tt>cds/container/split_list_set_nogc.h</tt>,
  60             see \ref cds_nonintrusive_SplitListSet_nogc "SplitListSet<gc::nogc>".
  61
  62         \par Usage
  63
  64         You should decide what garbage collector you want, and what ordered list you want to use as a base. Split-ordered list
  65         is original data structure based on an ordered list.
  66
  67         Suppose, you want construct split-list set based on \p gc::DHP GC
  68         and \p LazyList as ordered list implementation. So, you beginning your program with following include:
  69         \code
  70         #include <cds/container/lazy_list_dhp.h>
  71         #include <cds/container/split_list_set.h>
  72
  73         namespace cc = cds::container;
  74
  75         // The data belonged to split-ordered list
  76         sturuct foo {
  77             int     nKey;   // key field
  78             std::string strValue    ;   // value field
  79         };
  80         \endcode
  81         The inclusion order is important: first, include header for ordered-list implementation (for this example, <tt>cds/container/lazy_list_dhp.h</tt>),
  82         then the header for split-list set <tt>cds/container/split_list_set.h</tt>.
  83
  84         Now, you should declare traits for split-list set. The main parts of traits are a hash functor for the set and a comparing functor for ordered list.
  85         Note that we define several function in <tt>foo_hash</tt> and <tt>foo_less</tt> functors for different argument types since we want call our \p %SplitListSet
  86         object by the key of type <tt>int</tt> and by the value of type <tt>foo</tt>.
  87
  88         The second attention: instead of using \p %LazyList in \p %SplitListSet traits we use a tag \p cds::contaner::lazy_list_tag for the lazy list.
  89         The split-list requires significant support from underlying ordered list class and it is not good idea to dive you
  90         into deep implementation details of split-list and ordered list interrelations. The tag paradigm simplifies split-list interface.
  91
  92         \code
  93         // foo hash functor
  94         struct foo_hash {
  95             size_t operator()( int key ) const { return std::hash( key ) ; }
  96             size_t operator()( foo const& item ) const { return std::hash( item.nKey ) ; }
  97         };
  98
  99         // foo comparator
 100         struct foo_less {
 101             bool operator()(int i, foo const& f ) const { return i < f.nKey ; }
 102             bool operator()(foo const& f, int i ) const { return f.nKey < i ; }
 103             bool operator()(foo const& f1, foo const& f2) const { return f1.nKey < f2.nKey; }
 104         };
 105
 106         // SplitListSet traits
 107         struct foo_set_traits: public cc::split_list::traits
 108         {
 109             typedef cc::lazy_list_tag   ordered_list; // what type of ordered list we want to use
 110             typedef foo_hash            hash;         // hash functor for our data stored in split-list set
 111
 112             // Type traits for our LazyList class
 113             struct ordered_list_traits: public cc::lazy_list::traits
 114             {
 115                 typedef foo_less less   ;   // use our foo_less as comparator to order list nodes
 116             };
 117         };
 118         \endcode
 119
 120         Now you are ready to declare our set class based on \p %SplitListSet:
 121         \code
 122         typedef cc::SplitListSet< cds::gc::DHP, foo, foo_set_traits > foo_set;
 123         \endcode
 124
 125         You may use the modern option-based declaration instead of classic traits-based one:
 126         \code
 127         typedef cc::SplitListSet<
 128             cs::gc::DHP             // GC used
 129             ,foo                    // type of data stored
 130             ,cc::split_list::make_traits<      // metafunction to build split-list traits
 131                 cc::split_list::ordered_list<cc::lazy_list_tag>  // tag for underlying ordered list implementation
 132                 ,cc::opt::hash< foo_hash >               // hash functor
 133                 ,cc::split_list::ordered_list_traits<    // ordered list traits desired
 134                     cc::lazy_list::make_traits<          // metafunction to build lazy list traits
 135                         cc::opt::less< foo_less >        // less-based compare functor
 136                     >::type
 137                 >
 138             >::type
 139         >  foo_set;
 140         \endcode
 141         In case of option-based declaration using split_list::make_traits metafunction
 142         the struct \p foo_set_traits is not required.
 143
 144         Now, the set of type \p foo_set is ready to use in your program.
 145
 146         Note that in this example we show only mandatory \p traits parts, optional ones is the default and they are inherited
 147         from \p cds::container::split_list::traits.
 148         There are many other options for deep tuning the split-list and ordered-list containers.
 149     */
 150     template <
 151         class GC,
 152         class T,
 153 #ifdef CDS_DOXYGEN_INVOKED
 154         class Traits = split_list::traits
 155 #else
 156         class Traits
 157 #endif
 158     >
 159     class SplitListSet:
 160 #ifdef CDS_DOXYGEN_INVOKED
 161         protected intrusive::SplitListSet<GC, typename Traits::ordered_list, Traits>
 162 #else
 163         protected details::make_split_list_set< GC, T, typename Traits::ordered_list, split_list::details::wrap_set_traits<T, Traits> >::type
 164 #endif
 165     {
 166     protected:
 167         //@cond
 168         typedef details::make_split_list_set< GC, T, typename Traits::ordered_list, split_list::details::wrap_set_traits<T, Traits> > maker;
 169         typedef typename maker::type  base_class;
 170         //@endcond
 171
 172     public:
 173         typedef GC      gc;         ///< Garbage collector
 174         typedef T       value_type; ///< Type of vlue to be stored in split-list
 175         typedef Traits  traits;     ///< \p Traits template argument
 176         typedef typename maker::ordered_list ordered_list; ///< Underlying ordered list class
 177         typedef typename base_class::key_comparator key_comparator; ///< key compare functor
 178
 179         /// Hash functor for \p %value_type and all its derivatives that you use
 180         typedef typename base_class::hash         hash;
 181         typedef typename base_class::item_counter item_counter; ///< Item counter type
 182         typedef typename base_class::stat         stat; ///< Internal statistics
 183
 184         /// Count of hazard pointer required
 185         static CDS_CONSTEXPR const size_t c_nHazardPtrCount = base_class::c_nHazardPtrCount;
 186
 187     protected:
 188         //@cond
 189         typedef typename maker::cxx_node_allocator cxx_node_allocator;
 190         typedef typename maker::node_type          node_type;
 191         //@endcond
 192
 193     public:
 194         /// Guarded pointer
 195         typedef typename gc::template guarded_ptr< node_type, value_type, details::guarded_ptr_cast_set<node_type, value_type> > guarded_ptr;
 196
 197     protected:
 198         //@cond
 199         template <bool IsConst>
 200         class iterator_type: protected base_class::template iterator_type<IsConst>
 201         {
 202             typedef typename base_class::template iterator_type<IsConst> iterator_base_class;
 203             friend class SplitListSet;
 204
 205         public:
 206             /// Value pointer type (const for const iterator)
 207             typedef typename cds::details::make_const_type<value_type, IsConst>::pointer   value_ptr;
 208             /// Value reference type (const for const iterator)
 209             typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
 210
 211         public:
 212             /// Default ctor
 213             iterator_type()
 214             {}
 215
 216             /// Copy ctor
 217             iterator_type( iterator_type const& src )
 218                 : iterator_base_class( src )
 219             {}
 220
 221         protected:
 222             explicit iterator_type( iterator_base_class const& src )
 223                 : iterator_base_class( src )
 224             {}
 225
 226         public:
 227             /// Dereference operator
 228             value_ptr operator ->() const
 229             {
 230                 return &(iterator_base_class::operator->()->m_Value);
 231             }
 232
 233             /// Dereference operator
 234             value_ref operator *() const
 235             {
 236                 return iterator_base_class::operator*().m_Value;
 237             }
 238
 239             /// Pre-increment
 240             iterator_type& operator ++()
 241             {
 242                 iterator_base_class::operator++();
 243                 return *this;
 244             }
 245
 246             /// Assignment operator
 247             iterator_type& operator = (iterator_type const& src)
 248             {
 249                 iterator_base_class::operator=(src);
 250                 return *this;
 251             }
 252
 253             /// Equality operator
 254             template <bool C>
 255             bool operator ==(iterator_type<C> const& i ) const
 256             {
 257                 return iterator_base_class::operator==(i);
 258             }
 259
 260             /// Equality operator
 261             template <bool C>
 262             bool operator !=(iterator_type<C> const& i ) const
 263             {
 264                 return iterator_base_class::operator!=(i);
 265             }
 266         };
 267         //@endcond
 268
 269     public:
 270         /// Initializes split-ordered list of default capacity
 271         /**
 272             The default capacity is defined in bucket table constructor.
 273             See \p intrusive::split_list::expandable_bucket_table, \p intrusive::split_list::static_bucket_table
 274             which selects by \p split_list::dynamic_bucket_table option.
 275         */
 276         SplitListSet()
 277             : base_class()
 278         {}
 279
 280         /// Initializes split-ordered list
 281         SplitListSet(
 282             size_t nItemCount           ///< estimated average of item count
 283             , size_t nLoadFactor = 1    ///< the load factor - average item count per bucket. Small integer up to 8, default is 1.
 284             )
 285             : base_class( nItemCount, nLoadFactor )
 286         {}
 287
 288     public:
 289     ///@name Forward iterators (only for debugging purpose)
 290     //@{
 291         /// Forward iterator
 292         /**
 293             The forward iterator for a split-list has the following features:
 294             - it has no post-increment operator
 295             - it depends on underlying ordered list iterator
 296             - The iterator object cannot be moved across thread boundary because it contains GC's guard that is thread-private GC data.
 297             - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
 298               deleting operations it is no guarantee that you iterate all item in the split-list.
 299               Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
 300
 301               @warning Use this iterator on the concurrent container for debugging purpose only.
 302
 303               The iterator interface:
 304               \code
 305               class iterator {
 306               public:
 307                   // Default constructor
 308                   iterator();
 309
 310                   // Copy construtor
 311                   iterator( iterator const& src );
 312
 313                   // Dereference operator
 314                   value_type * operator ->() const;
 315
 316                   // Dereference operator
 317                   value_type& operator *() const;
 318
 319                   // Preincrement operator
 320                   iterator& operator ++();
 321
 322                   // Assignment operator
 323                   iterator& operator = (iterator const& src);
 324
 325                   // Equality operators
 326                   bool operator ==(iterator const& i ) const;
 327                   bool operator !=(iterator const& i ) const;
 328               };
 329               \endcode
 330         */
 331         typedef iterator_type<false>  iterator;
 332
 333         /// Const forward iterator
 334         typedef iterator_type<true>    const_iterator;
 335
 336         /// Returns a forward iterator addressing the first element in a set
 337         /**
 338             For empty set \code begin() == end() \endcode
 339         */
 340         iterator begin()
 341         {
 342             return iterator( base_class::begin());
 343         }
 344
 345         /// Returns an iterator that addresses the location succeeding the last element in a set
 346         /**
 347             Do not use the value returned by <tt>end</tt> function to access any item.
 348             The returned value can be used only to control reaching the end of the set.
 349             For empty set \code begin() == end() \endcode
 350         */
 351         iterator end()
 352         {
 353             return iterator( base_class::end());
 354         }
 355
 356         /// Returns a forward const iterator addressing the first element in a set
 357         const_iterator begin() const
 358         {
 359             return cbegin();
 360         }
 361         /// Returns a forward const iterator addressing the first element in a set
 362         const_iterator cbegin() const
 363         {
 364             return const_iterator( base_class::cbegin());
 365         }
 366
 367         /// Returns an const iterator that addresses the location succeeding the last element in a set
 368         const_iterator end() const
 369         {
 370             return cend();
 371         }
 372         /// Returns an const iterator that addresses the location succeeding the last element in a set
 373         const_iterator cend() const
 374         {
 375             return const_iterator( base_class::cend());
 376         }
 377     //@}
 378
 379     public:
 380         /// Inserts new node
 381         /**
 382             The function creates a node with copy of \p val value
 383             and then inserts the node created into the set.
 384
 385             The type \p Q should contain as minimum the complete key for the node.
 386             The object of \ref value_type should be constructible from a value of type \p Q.
 387             In trivial case, \p Q is equal to \ref value_type.
 388
 389             Returns \p true if \p val is inserted into the set, \p false otherwise.
 390         */
 391         template <typename Q>
 392         bool insert( Q&& val )
 393         {
 394             return insert_node( alloc_node( std::forward<Q>( val )));
 395         }
 396
 397         /// Inserts new node
 398         /**
 399             The function allows to split creating of new item into two part:
 400             - create item with key only
 401             - insert new item into the set
 402             - if inserting is success, calls  \p f functor to initialize value-field of \p val.
 403
 404             The functor signature is:
 405             \code
 406                 void func( value_type& val );
 407             \endcode
 408             where \p val is the item inserted.
 409
 410             The user-defined functor is called only if the inserting is success.
 411
 412             @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
 413             \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
 414             synchronization.
 415         */
 416         template <typename Q, typename Func>
 417         bool insert( Q&& val, Func f )
 418         {
 419             scoped_node_ptr pNode( alloc_node( std::forward<Q>( val )));
 420
 421             if ( base_class::insert( *pNode, [&f](node_type& node) { f( node.m_Value ) ; } )) {
 422                 pNode.release();
 423                 return true;
 424             }
 425             return false;
 426         }
 427
 428         /// Inserts data of type \p value_type created from \p args
 429         /**
 430             Returns \p true if inserting successful, \p false otherwise.
 431         */
 432         template <typename... Args>
 433         bool emplace( Args&&... args )
 434         {
 435             return insert_node( alloc_node( std::forward<Args>(args)...));
 436         }
 437
 438         /// Inserts or updates the node (only for \p IterableList -based set)
 439         /**
 440             The operation performs inserting or changing data with lock-free manner.
 441
 442             If the item \p val is not found in the set, then \p val is inserted iff \p bAllowInsert is \p true.
 443             Otherwise, the current element is changed to \p val, the old element will be retired later.
 444
 445             Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
 446             \p second is \p true if \p val has been added or \p false if the item with that key
 447             already in the set.
 448         */
 449         template <typename Q>
 450 #ifdef CDS_DOXYGEN_INVOKED
 451         std::pair<bool, bool>
 452 #else
 453         typename std::enable_if<
 454             std::is_same< Q, Q>::value && is_iterable_list< ordered_list >::value,
 455             std::pair<bool, bool>
 456         >::type
 457 #endif
 458         upsert( Q&& val, bool bAllowInsert = true )
 459         {
 460             scoped_node_ptr pNode( alloc_node( std::forward<Q>( val )));
 461
 462             auto bRet = base_class::upsert( *pNode, bAllowInsert );
 463
 464             if ( bRet.first )
 465                 pNode.release();
 466             return bRet;
 467         }
 468
 469         /// Updates the node
 470         /**
 471             The operation performs inserting or changing data with lock-free manner.
 472
 473             If \p key is not found in the set, then \p key is inserted iff \p bAllowInsert is \p true.
 474             Otherwise, the functor \p func is called with item found.
 475
 476             The functor \p func signature depends of ordered list:
 477
 478             <b>for \p MichaelList, \p LazyList</b>
 479             \code
 480                 struct functor {
 481                     void operator()( bool bNew, value_type& item, Q const& val );
 482                 };
 483             \endcode
 484             with arguments:
 485             - \p bNew - \p true if the item has been inserted, \p false otherwise
 486             - \p item - item of the set
 487             - \p val - argument \p val passed into the \p %update() function
 488
 489             The functor may change non-key fields of the \p item.
 490
 491             <b>for \p IterableList</b>
 492             \code
 493                 void func( value_type& val, value_type * old );
 494             \endcode
 495             where
 496             - \p val - a new data constructed from \p key
 497             - \p old - old value that will be retired. If new item has been inserted then \p old is \p nullptr.
 498
 499             Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successful,
 500             \p second is true if new item has been added or \p false if the item with \p key
 501             already is in the set.
 502
 503             @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" and \ref cds_nonintrusive_IterableList_gc "IterableList"
 504             as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
 505             \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
 506             synchronization.
 507         */
 508         template <typename Q, typename Func>
 509 #ifdef CDS_DOXYGEN_INVOKED
 510         std::pair<bool, bool>
 511 #else
 512         typename std::enable_if<
 513             std::is_same<Q, Q>::value && !is_iterable_list<ordered_list>::value,
 514             std::pair<bool, bool>
 515         >::type
 516 #endif
 517         update( Q&& val, Func func, bool bAllowInsert = true )
 518         {
 519             scoped_node_ptr pNode( alloc_node( std::forward<Q>( val )));
 520
 521             auto bRet = base_class::update( *pNode,
 522                 [&func, &val]( bool bNew, node_type& item,  node_type const& /*val*/ ) {
 523                     func( bNew, item.m_Value, val );
 524                 }, bAllowInsert );
 525
 526             if ( bRet.first && bRet.second )
 527                 pNode.release();
 528             return bRet;
 529         }
 530         //@cond
 531         template <typename Q, typename Func>
 532         typename std::enable_if<
 533             std::is_same<Q, Q>::value && is_iterable_list<ordered_list>::value,
 534             std::pair<bool, bool>
 535         >::type
 536         update( Q&& val, Func func, bool bAllowInsert = true )
 537         {
 538             scoped_node_ptr pNode( alloc_node( std::forward<Q>( val )));
 539
 540             auto bRet = base_class::update( *pNode,
 541                 [&func]( node_type& item, node_type* old ) {
 542                     func( item.m_Value, old ? &old->m_Value : nullptr );
 543                 }, bAllowInsert );
 544
 545             if ( bRet.first )
 546                 pNode.release();
 547             return bRet;
 548         }
 549         //@endcond
 550
 551         //@cond
 552         template <typename Q, typename Func>
 553         CDS_DEPRECATED("ensure() is deprecated, use update()")
 554         std::pair<bool, bool> ensure( Q const& val, Func func )
 555         {
 556             return update( val, func, true );
 557         }
 558         //@endcond
 559
 560         /// Deletes \p key from the set
 561         /** \anchor cds_nonintrusive_SplitListSet_erase_val
 562
 563             The item comparator should be able to compare the values of type \p value_type
 564             and the type \p Q.
 565
 566             Return \p true if key is found and deleted, \p false otherwise
 567         */
 568         template <typename Q>
 569         bool erase( Q const& key )
 570         {
 571             return base_class::erase( key );
 572         }
 573
 574         /// Deletes the item from the set using \p pred predicate for searching
 575         /**
 576             The function is an analog of \ref cds_nonintrusive_SplitListSet_erase_val "erase(Q const&)"
 577             but \p pred is used for key comparing.
 578             \p Less functor has the interface like \p std::less.
 579             \p Less must imply the same element order as the comparator used for building the set.
 580         */
 581         template <typename Q, typename Less>
 582         bool erase_with( Q const& key, Less pred )
 583         {
 584             CDS_UNUSED( pred );
 585             return base_class::erase_with( key, typename maker::template predicate_wrapper<Less>::type());
 586         }
 587
 588         /// Deletes \p key from the set
 589         /** \anchor cds_nonintrusive_SplitListSet_erase_func
 590
 591             The function searches an item with key \p key, calls \p f functor
 592             and deletes the item. If \p key is not found, the functor is not called.
 593
 594             The functor \p Func interface:
 595             \code
 596             struct extractor {
 597                 void operator()(value_type const& val);
 598             };
 599             \endcode
 600
 601             Since the key of split-list \p value_type is not explicitly specified,
 602             template parameter \p Q defines the key type searching in the list.
 603             The list item comparator should be able to compare the values of the type \p value_type
 604             and the type \p Q.
 605
 606             Return \p true if key is found and deleted, \p false otherwise
 607         */
 608         template <typename Q, typename Func>
 609         bool erase( Q const& key, Func f )
 610         {
 611             return base_class::erase( key, [&f](node_type& node) { f( node.m_Value ); } );
 612         }
 613
 614         /// Deletes the item from the set using \p pred predicate for searching
 615         /**
 616             The function is an analog of \ref cds_nonintrusive_SplitListSet_erase_func "erase(Q const&, Func)"
 617             but \p pred is used for key comparing.
 618             \p Less functor has the interface like \p std::less.
 619             \p Less must imply the same element order as the comparator used for building the set.
 620         */
 621         template <typename Q, typename Less, typename Func>
 622         bool erase_with( Q const& key, Less pred, Func f )
 623         {
 624             CDS_UNUSED( pred );
 625             return base_class::erase_with( key, typename maker::template predicate_wrapper<Less>::type(),
 626                 [&f](node_type& node) { f( node.m_Value ); } );
 627         }
 628
 629         /// Deletes the item pointed by iterator \p iter (only for \p IterableList based set)
 630         /**
 631             Returns \p true if the operation is successful, \p false otherwise.
 632             The function can return \p false if the node the iterator points to has already been deleted
 633             by other thread.
 634
 635             The function does not invalidate the iterator, it remains valid and can be used for further traversing.
 636
 637             @note \p %erase_at() is supported only for \p %SplitListSet based on \p IterableList.
 638         */
 639 #ifdef CDS_DOXYGEN_INVOKED
 640         bool erase_at( iterator const& iter )
 641 #else
 642         template <typename Iterator>
 643         typename std::enable_if< std::is_same<Iterator, iterator>::value && is_iterable_list< ordered_list >::value, bool >::type
 644         erase_at( Iterator const& iter )
 645 #endif
 646         {
 647             return base_class::erase_at( static_cast<iterator::iterator_base_class const&>( iter ));
 648         }
 649
 650
 651         /// Extracts the item with specified \p key
 652         /** \anchor cds_nonintrusive_SplitListSet_hp_extract
 653             The function searches an item with key equal to \p key,
 654             unlinks it from the set, and returns it as \p guarded_ptr.
 655             If \p key is not found the function returns an empty guarded pointer.
 656
 657             Note the compare functor should accept a parameter of type \p Q that may be not the same as \p value_type.
 658
 659             The extracted item is freed automatically when returned \p guarded_ptr object will be destroyed or released.
 660             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 661
 662             Usage:
 663             \code
 664             typedef cds::container::SplitListSet< your_template_args > splitlist_set;
 665             splitlist_set theSet;
 666             // ...
 667             {
 668                 splitlist_set::guarded_ptr gp(theSet.extract( 5 ));
 669                 if ( gp ) {
 670                     // Deal with gp
 671                     // ...
 672                 }
 673                 // Destructor of gp releases internal HP guard
 674             }
 675             \endcode
 676         */
 677         template <typename Q>
 678         guarded_ptr extract( Q const& key )
 679         {
 680             return extract_( key );
 681         }
 682
 683         /// Extracts the item using compare functor \p pred
 684         /**
 685             The function is an analog of \ref cds_nonintrusive_SplitListSet_hp_extract "extract(Q const&)"
 686             but \p pred predicate is used for key comparing.
 687
 688             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 689             in any order.
 690             \p pred must imply the same element order as the comparator used for building the set.
 691         */
 692         template <typename Q, typename Less>
 693         guarded_ptr extract_with( Q const& key, Less pred )
 694         {
 695             return extract_with_( key, pred );
 696         }
 697
 698         /// Finds the key \p key
 699         /** \anchor cds_nonintrusive_SplitListSet_find_func
 700
 701             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 702             The interface of \p Func functor is:
 703             \code
 704             struct functor {
 705                 void operator()( value_type& item, Q& key );
 706             };
 707             \endcode
 708             where \p item is the item found, \p key is the <tt>find</tt> function argument.
 709
 710             The functor may change non-key fields of \p item. Note that the functor is only guarantee
 711             that \p item cannot be disposed during functor is executing.
 712             The functor does not serialize simultaneous access to the set's \p item. If such access is
 713             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
 714
 715             The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
 716             may modify both arguments.
 717
 718             Note the hash functor specified for class \p Traits template parameter
 719             should accept a parameter of type \p Q that can be not the same as \p value_type.
 720
 721             The function returns \p true if \p key is found, \p false otherwise.
 722         */
 723         template <typename Q, typename Func>
 724         bool find( Q& key, Func f )
 725         {
 726             return find_( key, f );
 727         }
 728         //@cond
 729         template <typename Q, typename Func>
 730         bool find( Q const& key, Func f )
 731         {
 732             return find_( key, f );
 733         }
 734         //@endcond
 735
 736         /// Finds \p key and returns iterator pointed to the item found (only for \p IterableList -based set)
 737         /**
 738             If \p key is not found the function returns \p end().
 739
 740             @note This function is supported only for the set based on \p IterableList
 741         */
 742         template <typename Q>
 743 #ifdef CDS_DOXYGEN_INVOKED
 744         iterator
 745 #else
 746         typename std::enable_if< std::is_same<Q,Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
 747 #endif
 748         find( Q& key )
 749         {
 750             return find_iterator_( key );
 751         }
 752         //@cond
 753         template <typename Q>
 754         typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
 755         find( Q const& key )
 756         {
 757             return find_iterator_( key );
 758         }
 759         //@endcond
 760
 761
 762         /// Finds the key \p key using \p pred predicate for searching
 763         /**
 764             The function is an analog of \ref cds_nonintrusive_SplitListSet_find_func "find(Q&, Func)"
 765             but \p pred is used for key comparing.
 766             \p Less functor has the interface like \p std::less.
 767             \p Less must imply the same element order as the comparator used for building the set.
 768         */
 769         template <typename Q, typename Less, typename Func>
 770         bool find_with( Q& key, Less pred, Func f )
 771         {
 772             return find_with_( key, pred, f );
 773         }
 774         //@cond
 775         template <typename Q, typename Less, typename Func>
 776         bool find_with( Q const& key, Less pred, Func f )
 777         {
 778             return find_with_( key, pred, f );
 779         }
 780         //@endcond
 781
 782         /// Finds \p key using \p pred predicate and returns iterator pointed to the item found (only for \p IterableList -based set)
 783         /**
 784             The function is an analog of \p find(Q&) but \p pred is used for key comparing.
 785             \p Less functor has the interface like \p std::less.
 786             \p pred must imply the same element order as the comparator used for building the set.
 787
 788             If \p key is not found the function returns \p end().
 789
 790             @note This function is supported only for the set based on \p IterableList
 791         */
 792         template <typename Q, typename Less>
 793 #ifdef CDS_DOXYGEN_INVOKED
 794         iterator
 795 #else
 796         typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
 797 #endif
 798         find_with( Q& key, Less pred )
 799         {
 800             return find_iterator_with_( key, pred );
 801         }
 802         //@cond
 803         template <typename Q, typename Less>
 804         typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
 805         find_with( Q const& key, Less pred )
 806         {
 807             return find_iterator_with_( key, pred );
 808         }
 809         //@endcond
 810
 811         /// Checks whether the set contains \p key
 812         /**
 813             The function searches the item with key equal to \p key
 814             and returns \p true if it is found, and \p false otherwise.
 815
 816             Note the hash functor specified for class \p Traits template parameter
 817             should accept a parameter of type \p Q that can be not the same as \p value_type.
 818             Otherwise, you may use \p contains( Q const&, Less pred ) functions with explicit predicate for key comparing.
 819         */
 820         template <typename Q>
 821         bool contains( Q const& key )
 822         {
 823             return base_class::contains( key );
 824         }
 825
 826         /// Checks whether the map contains \p key using \p pred predicate for searching
 827         /**
 828             The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
 829             \p Less functor has the interface like \p std::less.
 830             \p Less must imply the same element order as the comparator used for building the map.
 831         */
 832         template <typename Q, typename Less>
 833         bool contains( Q const& key, Less pred )
 834         {
 835             CDS_UNUSED( pred );
 836             return base_class::contains( key, typename maker::template predicate_wrapper<Less>::type());
 837         }
 838
 839         /// Finds the key \p key and return the item found
 840         /** \anchor cds_nonintrusive_SplitListSet_hp_get
 841             The function searches the item with key equal to \p key
 842             and returns the item found as \p guarded_ptr.
 843             If \p key is not found the function returns an empty guarded pointer.
 844
 845             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
 846
 847             Usage:
 848             \code
 849             typedef cds::container::SplitListSet< your_template_params >  splitlist_set;
 850             splitlist_set theSet;
 851             // ...
 852             {
 853                 splitlist_set::guarded_ptr gp(theSet.get( 5 ));
 854                 if ( gp ) {
 855                     // Deal with gp
 856                     //...
 857                 }
 858                 // Destructor of guarded_ptr releases internal HP guard
 859             }
 860             \endcode
 861
 862             Note the compare functor specified for split-list set
 863             should accept a parameter of type \p Q that can be not the same as \p value_type.
 864         */
 865         template <typename Q>
 866         guarded_ptr get( Q const& key )
 867         {
 868             return get_( key );
 869         }
 870
 871         /// Finds \p key and return the item found
 872         /**
 873             The function is an analog of \ref cds_nonintrusive_SplitListSet_hp_get "get( Q const&)"
 874             but \p pred is used for comparing the keys.
 875
 876             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 877             in any order.
 878             \p pred must imply the same element order as the comparator used for building the set.
 879         */
 880         template <typename Q, typename Less>
 881         guarded_ptr get_with( Q const& key, Less pred )
 882         {
 883             return get_with_( key, pred );
 884         }
 885
 886         /// Clears the set (not atomic)
 887         void clear()
 888         {
 889             base_class::clear();
 890         }
 891
 892         /// Checks if the set is empty
 893         /**
 894             Emptiness is checked by item counting: if item count is zero then assume that the set is empty.
 895             Thus, the correct item counting feature is an important part of split-list set implementation.
 896         */
 897         bool empty() const
 898         {
 899             return base_class::empty();
 900         }
 901
 902         /// Returns item count in the set
 903         size_t size() const
 904         {
 905             return base_class::size();
 906         }
 907
 908         /// Returns internal statistics
 909         stat const& statistics() const
 910         {
 911             return base_class::statistics();
 912         }
 913
 914         /// Returns internal statistics for \p ordered_list
 915         typename ordered_list::stat const& list_statistics() const
 916         {
 917             return base_class::list_statistics();
 918         }
 919
 920     protected:
 921         //@cond
 922         using base_class::extract_;
 923         using base_class::get_;
 924
 925         template <typename... Args>
 926         static node_type * alloc_node( Args&&... args )
 927         {
 928             return cxx_node_allocator().MoveNew( std::forward<Args>( args )... );
 929         }
 930
 931         static void free_node( node_type * pNode )
 932         {
 933             cxx_node_allocator().Delete( pNode );
 934         }
 935
 936         template <typename Q, typename Func>
 937         bool find_( Q& val, Func f )
 938         {
 939             return base_class::find( val, [&f]( node_type& item, Q& val ) { f( item.m_Value, val ); } );
 940         }
 941
 942         template <typename Q>
 943         typename std::enable_if< std::is_same<Q,Q>::value && is_iterable_list< ordered_list >::value, iterator>::type
 944         find_iterator_( Q& val )
 945         {
 946             return iterator( base_class::find( val ));
 947         }
 948
 949         template <typename Q, typename Less, typename Func>
 950         bool find_with_( Q& val, Less pred, Func f )
 951         {
 952             CDS_UNUSED( pred );
 953             return base_class::find_with( val, typename maker::template predicate_wrapper<Less>::type(),
 954                 [&f]( node_type& item, Q& val ) { f( item.m_Value, val ); } );
 955         }
 956
 957         template <typename Q, typename Less>
 958         typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator>::type
 959         find_iterator_with_( Q& val, Less pred )
 960         {
 961             CDS_UNUSED( pred );
 962             return iterator( base_class::find_with( val, typename maker::template predicate_wrapper<Less>::type()));
 963         }
 964
 965         struct node_disposer {
 966             void operator()( node_type * pNode )
 967             {
 968                 free_node( pNode );
 969             }
 970         };
 971         typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
 972
 973         bool insert_node( node_type * pNode )
 974         {
 975             assert( pNode != nullptr );
 976             scoped_node_ptr p( pNode );
 977
 978             if ( base_class::insert( *pNode )) {
 979                 p.release();
 980                 return true;
 981             }
 982             return false;
 983         }
 984
 985         template <typename Q, typename Less>
 986         guarded_ptr extract_with_( Q const& key, Less pred )
 987         {
 988             CDS_UNUSED( pred );
 989             return base_class::extract_with_( key, typename maker::template predicate_wrapper<Less>::type());
 990         }
 991
 992         template <typename Q, typename Less>
 993         guarded_ptr get_with_( Q const& key, Less pred )
 994         {
 995             CDS_UNUSED( pred );
 996             return base_class::get_with_( key, typename maker::template predicate_wrapper<Less>::type());
 997         }
 998
 999         //@endcond
1000     };
1001
1002 }}  // namespace cds::container
1003
1004 #endif // #ifndef CDSLIB_CONTAINER_SPLIT_LIST_SET_H