cds/intrusive/split_list_nogc.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-2016
   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_INTRUSIVE_SPLIT_LIST_NOGC_H
  32 #define CDSLIB_INTRUSIVE_SPLIT_LIST_NOGC_H
  33
  34 #include <limits>
  35
  36 #include <cds/intrusive/details/split_list_base.h>
  37 #include <cds/gc/nogc.h>
  38
  39 namespace cds { namespace intrusive {
  40
  41     /// Split-ordered list (template specialization for gc::nogc)
  42     /** @ingroup cds_intrusive_map
  43         \anchor cds_intrusive_SplitListSet_nogc
  44
  45         This specialization is intended for so-called persistent usage when no item
  46         reclamation may be performed. The class does not support deleting of list item.
  47
  48         See \ref cds_intrusive_SplitListSet_hp "SplitListSet" for description of template parameters.
  49         The template parameter \p OrderedList should be any gc::nogc-derived ordered list, for example,
  50         \ref cds_intrusive_MichaelList_nogc "persistent MichaelList",
  51         \ref cds_intrusive_LazyList_nogc "persistent LazyList"
  52     */
  53     template <
  54         class OrderedList,
  55 #ifdef CDS_DOXYGEN_INVOKED
  56         class Traits = split_list::traits
  57 #else
  58         class Traits
  59 #endif
  60     >
  61     class SplitListSet< cds::gc::nogc, OrderedList, Traits >
  62     {
  63     public:
  64         typedef cds::gc::nogc gc;     ///< Garbage collector
  65         typedef Traits        traits; ///< Traits template parameters
  66
  67         /// Hash functor for \p value_type and all its derivatives that you use
  68         typedef typename cds::opt::v::hash_selector< typename traits::hash >::type   hash;
  69
  70     protected:
  71         //@cond
  72         typedef split_list::details::rebind_list_traits<OrderedList, traits> wrapped_ordered_list;
  73         //@endcond
  74
  75     public:
  76 #   ifdef CDS_DOXYGEN_INVOKED
  77         typedef OrderedList ordered_list;   ///< type of ordered list used as base for split-list
  78 #   else
  79         typedef typename wrapped_ordered_list::result ordered_list;
  80 #   endif
  81         typedef typename ordered_list::value_type     value_type;     ///< type of value stored in the split-list
  82         typedef typename ordered_list::key_comparator key_comparator; ///< key comparison functor
  83         typedef typename ordered_list::disposer       disposer;       ///< Node disposer functor
  84
  85         typedef typename traits::item_counter item_counter; ///< Item counter type
  86         typedef typename traits::back_off     back_off;     ///< back-off strategy
  87         typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
  88         typedef typename traits::stat         stat;         ///< Internal statistics, see \p spit_list::stat
  89
  90     protected:
  91         typedef typename ordered_list::node_type  list_node_type;  ///< Node type as declared in ordered list
  92         typedef split_list::node<list_node_type>  node_type;       ///< split-list node type
  93         typedef node_type                         aux_node_type; ///< dummy node type
  94
  95         /// Split-list node traits
  96         /**
  97             This traits is intended for converting between underlying ordered list node type \ref list_node_type
  98             and split-list node type \ref node_type
  99         */
 100         typedef split_list::node_traits<typename ordered_list::node_traits>  node_traits;
 101
 102         //@cond
 103         /// Bucket table implementation
 104         typedef typename split_list::details::bucket_table_selector<
 105             traits::dynamic_bucket_table
 106             , gc
 107             , aux_node_type
 108             , opt::allocator< typename traits::allocator >
 109             , opt::memory_model< memory_model >
 110         >::type bucket_table;
 111
 112         typedef typename ordered_list::iterator list_iterator;
 113         typedef typename ordered_list::const_iterator list_const_iterator;
 114         //@endcond
 115
 116     protected:
 117         //@cond
 118         /// Ordered list wrapper to access protected members
 119         class ordered_list_wrapper: public ordered_list
 120         {
 121             typedef ordered_list base_class;
 122             typedef typename base_class::auxiliary_head bucket_head_type;
 123
 124         public:
 125             list_iterator insert_at_( aux_node_type * pHead, value_type& val )
 126             {
 127                 assert( pHead != nullptr );
 128                 bucket_head_type h(static_cast<list_node_type *>(pHead));
 129                 return base_class::insert_at_( h, val );
 130             }
 131
 132             template <typename Func>
 133             std::pair<list_iterator, bool> update_at_( aux_node_type * pHead, value_type& val, Func func, bool bAllowInsert )
 134             {
 135                 assert( pHead != nullptr );
 136                 bucket_head_type h(static_cast<list_node_type *>(pHead));
 137                 return base_class::update_at_( h, val, func, bAllowInsert );
 138             }
 139
 140             template <typename Q, typename Compare, typename Func>
 141             bool find_at( aux_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f )
 142             {
 143                 assert( pHead != nullptr );
 144                 bucket_head_type h(static_cast<list_node_type *>(pHead));
 145                 return base_class::find_at( h, val, cmp, f );
 146             }
 147
 148             template <typename Q, typename Compare>
 149             list_iterator find_at_( aux_node_type * pHead, split_list::details::search_value_type<Q> const & val, Compare cmp )
 150             {
 151                 assert( pHead != nullptr );
 152                 bucket_head_type h(static_cast<list_node_type *>(pHead));
 153                 return base_class::find_at_( h, val, cmp );
 154             }
 155
 156             bool insert_aux_node( aux_node_type * pNode )
 157             {
 158                 return base_class::insert_aux_node( pNode );
 159             }
 160             bool insert_aux_node( aux_node_type * pHead, aux_node_type * pNode )
 161             {
 162                 bucket_head_type h(static_cast<list_node_type *>(pHead));
 163                 return base_class::insert_aux_node( h, pNode );
 164             }
 165
 166             template <typename Predicate>
 167             void erase_for( Predicate pred )
 168             {
 169                 return base_class::erase_for( pred );
 170             }
 171         };
 172
 173         //@endcond
 174
 175     protected:
 176         ordered_list_wrapper    m_List;             ///< Ordered list containing split-list items
 177         bucket_table            m_Buckets;          ///< bucket table
 178         atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
 179         atomics::atomic<size_t> m_nMaxItemCount;    ///< number of items container can hold, before we have to resize
 180         item_counter            m_ItemCounter;      ///< Item counter
 181         hash                    m_HashFunctor;      ///< Hash functor
 182         stat                    m_Stat;             ///< Internal statistics
 183
 184     protected:
 185         //@cond
 186         typedef cds::details::Allocator< aux_node_type, typename traits::allocator >   aux_node_allocator;
 187
 188         aux_node_type * alloc_aux_node( size_t nHash )
 189         {
 190             m_Stat.onHeadNodeAllocated();
 191             return aux_node_allocator().New( nHash );
 192         }
 193         void free_aux_node( aux_node_type * p )
 194         {
 195             aux_node_allocator().Delete( p );
 196             m_Stat.onHeadNodeFreed();
 197         }
 198
 199         /// Calculates hash value of \p key
 200         template <typename Q>
 201         size_t hash_value( Q const& key ) const
 202         {
 203             return m_HashFunctor( key );
 204         }
 205
 206         size_t bucket_no( size_t nHash ) const
 207         {
 208             return nHash & ( (1 << m_nBucketCountLog2.load(memory_model::memory_order_relaxed)) - 1 );
 209         }
 210
 211         static size_t parent_bucket( size_t nBucket )
 212         {
 213             assert( nBucket > 0 );
 214             return nBucket & ~( 1 << bitop::MSBnz( nBucket ) );
 215         }
 216
 217         aux_node_type * init_bucket( size_t nBucket )
 218         {
 219             assert( nBucket > 0 );
 220             size_t nParent = parent_bucket( nBucket );
 221
 222             aux_node_type * pParentBucket = m_Buckets.bucket( nParent );
 223             if ( pParentBucket == nullptr ) {
 224                 pParentBucket = init_bucket( nParent );
 225                 m_Stat.onRecursiveInitBucket();
 226             }
 227
 228             assert( pParentBucket != nullptr );
 229
 230             // Allocate a dummy node for new bucket
 231             {
 232                 aux_node_type * pBucket = alloc_aux_node( split_list::dummy_hash( nBucket ) );
 233                 if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) {
 234                     m_Buckets.bucket( nBucket, pBucket );
 235                     m_Stat.onNewBucket();
 236                     return pBucket;
 237                 }
 238                 free_aux_node( pBucket );
 239             }
 240
 241             // Another thread set the bucket. Wait while it done
 242
 243             // In this point, we must wait while nBucket is empty.
 244             // The compiler can decide that waiting loop can be "optimized" (stripped)
 245             // To prevent this situation, we use waiting on volatile bucket_head_ptr pointer.
 246             //
 247             m_Stat.onBucketInitContenton();
 248             back_off bkoff;
 249             while ( true ) {
 250                 aux_node_type volatile * p = m_Buckets.bucket( nBucket );
 251                 if ( p && p != nullptr )
 252                     return const_cast<aux_node_type *>( p );
 253                 bkoff();
 254                 m_Stat.onBusyWaitBucketInit();
 255             }
 256         }
 257
 258         aux_node_type * get_bucket( size_t nHash )
 259         {
 260             size_t nBucket = bucket_no( nHash );
 261
 262             aux_node_type * pHead = m_Buckets.bucket( nBucket );
 263             if ( pHead == nullptr )
 264                 pHead = init_bucket( nBucket );
 265
 266             assert( pHead->is_dummy() );
 267
 268             return pHead;
 269         }
 270
 271         void init()
 272         {
 273             // GC and OrderedList::gc must be the same
 274             static_assert( std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
 275
 276             // atomicity::empty_item_counter is not allowed as a item counter
 277             static_assert( !std::is_same<item_counter, cds::atomicity::empty_item_counter>::value,
 278                            "cds::atomicity::empty_item_counter is not allowed as a item counter");
 279
 280             // Initialize bucket 0
 281             aux_node_type * pNode = alloc_aux_node( 0 /*split_list::dummy_hash(0)*/ );
 282
 283             // insert_aux_node cannot return false for empty list
 284             CDS_VERIFY( m_List.insert_aux_node( pNode ));
 285
 286             m_Buckets.bucket( 0, pNode );
 287         }
 288
 289         static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor )
 290         {
 291             return nBucketCount * nLoadFactor;
 292         }
 293
 294         void inc_item_count()
 295         {
 296             size_t nMaxCount = m_nMaxItemCount.load(memory_model::memory_order_relaxed);
 297             if ( ++m_ItemCounter <= nMaxCount )
 298                 return;
 299
 300             size_t sz = m_nBucketCountLog2.load(memory_model::memory_order_relaxed);
 301             const size_t nBucketCount = static_cast<size_t>(1) << sz;
 302             if ( nBucketCount < m_Buckets.capacity() ) {
 303                 // we may grow the bucket table
 304                 const size_t nLoadFactor = m_Buckets.load_factor();
 305                 if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ))
 306                     return; // someone already have updated m_nBucketCountLog2, so stop here
 307
 308                 m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ),
 309                                                          memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
 310                 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
 311             }
 312             else
 313                 m_nMaxItemCount.store( std::numeric_limits<size_t>::max(), memory_model::memory_order_relaxed );
 314         }
 315
 316         //@endcond
 317
 318     public:
 319         /// Initialize split-ordered list of default capacity
 320         /**
 321             The default capacity is defined in bucket table constructor.
 322             See split_list::expandable_bucket_table, split_list::static_ducket_table
 323             which selects by split_list::dynamic_bucket_table option.
 324         */
 325         SplitListSet()
 326             : m_nBucketCountLog2(1)
 327             , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) )
 328         {
 329             init();
 330         }
 331
 332         /// Initialize split-ordered list
 333         SplitListSet(
 334             size_t nItemCount           ///< estimate average of item count
 335             , size_t nLoadFactor = 1    ///< load factor - average item count per bucket. Small integer up to 10, default is 1.
 336             )
 337             : m_Buckets( nItemCount, nLoadFactor )
 338             , m_nBucketCountLog2(1)
 339             , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) )
 340         {
 341             init();
 342         }
 343
 344     public:
 345         /// Inserts new node
 346         /**
 347             The function inserts \p val in the set if it does not contain
 348             an item with key equal to \p val.
 349
 350             Returns \p true if \p val is placed into the set, \p false otherwise.
 351         */
 352         bool insert( value_type& val )
 353         {
 354             return insert_( val ) != end();
 355         }
 356
 357         /// Updates the node
 358         /**
 359             The operation performs inserting or changing data with lock-free manner.
 360
 361             If the item \p val is not found in the set, then \p val is inserted
 362             iff \p bAllowInsert is \p true.
 363             Otherwise, the functor \p func is called with item found.
 364             The functor signature is:
 365             \code
 366                 void func( bool bNew, value_type& item, value_type& val );
 367             \endcode
 368             with arguments:
 369             - \p bNew - \p true if the item has been inserted, \p false otherwise
 370             - \p item - item of the set
 371             - \p val - argument \p val passed into the \p update() function
 372             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 373             refers to the same thing.
 374
 375             The functor may change non-key fields of the \p item.
 376
 377             Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
 378             \p second is \p true if new item has been added or \p false if the item with \p key
 379             already is in the list.
 380
 381             @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
 382             \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
 383             synchronization.
 384         */
 385         template <typename Func>
 386         std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
 387         {
 388             std::pair<iterator, bool> ret = update_( val, func, bAllowInsert );
 389             return std::make_pair( ret.first != end(), ret.second );
 390         }
 391         //@cond
 392         template <typename Func>
 393         CDS_DEPRECATED("ensure() is deprecated, use update()")
 394         std::pair<bool, bool> ensure( value_type& val, Func func )
 395         {
 396             return update( val, func, true );
 397         }
 398         //@endcond
 399
 400         /// Checks whether the set contains \p key
 401         /**
 402             The function searches the item with key equal to \p key
 403             and returns \p true if it is found, and \p false otherwise.
 404
 405             Note the hash functor specified for class \p Traits template parameter
 406             should accept a parameter of type \p Q that can be not the same as \p value_type.
 407             Otherwise, you may use \p contains( Q const&, Less pred ) functions with explicit predicate for key comparing.
 408         */
 409         template <typename Q>
 410         value_type * contains( Q const& key )
 411         {
 412             iterator it = find_( key );
 413             if ( it == end() )
 414                 return nullptr;
 415             return &*it;
 416         }
 417         //@cond
 418         template <typename Q>
 419         CDS_DEPRECATED("deprecated, use contains()")
 420         value_type * find( Q const& key )
 421         {
 422             return contains( key );
 423         }
 424         //@endcond
 425
 426         /// Checks whether the set contains \p key using \p pred predicate for searching
 427         /**
 428             The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
 429             \p Less functor has the interface like \p std::less.
 430             \p Less must imply the same element order as the comparator used for building the list.
 431         */
 432         template <typename Q, typename Less>
 433         value_type * contains( Q const& key, Less pred )
 434         {
 435             iterator it = find_with_( key, pred );
 436             if ( it == end() )
 437                 return nullptr;
 438             return &*it;
 439         }
 440         //@cond
 441         template <typename Q, typename Less>
 442         CDS_DEPRECATED("deprecated, use contains()")
 443         value_type * find_with( Q const& key, Less pred )
 444         {
 445             return contains( key, pred );
 446         }
 447         //@endcond
 448
 449         /// Finds the key \p key
 450         /** \anchor cds_intrusive_SplitListSet_nogc_find_func
 451             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 452             The interface of \p Func functor is:
 453             \code
 454             struct functor {
 455                 void operator()( value_type& item, Q& key );
 456             };
 457             \endcode
 458             where \p item is the item found, \p key is the <tt>find</tt> function argument.
 459
 460             The functor can change non-key fields of \p item.
 461             The functor does not serialize simultaneous access to the set \p item. If such access is
 462             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
 463
 464             Note the hash functor specified for class \p Traits template parameter
 465             should accept a parameter of type \p Q that can be not the same as \p value_type.
 466
 467             The function returns \p true if \p key is found, \p false otherwise.
 468         */
 469         template <typename Q, typename Func>
 470         bool find( Q& key, Func f )
 471         {
 472             return find_( key, key_comparator(), f );
 473         }
 474         //@cond
 475         template <typename Q, typename Func>
 476         bool find( Q const& key, Func f )
 477         {
 478             return find_( key, key_comparator(), f );
 479         }
 480         //@endcond
 481
 482         /// Finds the key \p key with \p pred predicate for comparing
 483         /**
 484             The function is an analog of \ref cds_intrusive_SplitListSet_nogc_find_func "find(Q&, Func)"
 485             but \p cmp is used for key compare.
 486             \p Less has the interface like \p std::less.
 487             \p cmp must imply the same element order as the comparator used for building the set.
 488         */
 489         template <typename Q, typename Less, typename Func>
 490         bool find_with( Q& key, Less pred, Func f )
 491         {
 492             CDS_UNUSED( pred );
 493             return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
 494         }
 495         //@cond
 496         template <typename Q, typename Less, typename Func>
 497         bool find_with( Q const& key, Less pred, Func f )
 498         {
 499             CDS_UNUSED( pred );
 500             return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
 501         }
 502         //@endcond
 503
 504
 505         /// Clears the set (non-atomic, not thread-safe)
 506         /**
 507             The function unlink all items from the set.
 508             The function is not atomic. It cleans up each bucket and then resets the item counter to zero.
 509             If there are a thread that performs insertion while \p %clear() is working the result is undefined in general case:
 510             <tt> empty() </tt> may return \p true but the set may contain item(s).
 511             Therefore, \p %clear() may be used only for debugging purposes.
 512
 513             For each item the \p disposer is called after unlinking.
 514         */
 515         void clear()
 516         {
 517             m_List.erase_for( []( value_type const& val ) -> bool { return !node_traits::to_node_ptr( val )->is_dummy(); } );
 518             m_ItemCounter.reset();
 519         }
 520
 521         /// Checks if the set is empty
 522         /**
 523             Emptiness is checked by item counting: if item count is zero then the set is empty.
 524             Thus, the correct item counting feature is an important part of split-list implementation.
 525         */
 526         bool empty() const
 527         {
 528             return size() == 0;
 529         }
 530
 531         /// Returns item count in the set
 532         size_t size() const
 533         {
 534             return m_ItemCounter;
 535         }
 536
 537         /// Returns internal statistics
 538         stat const& statistics() const
 539         {
 540             return m_Stat;
 541         }
 542
 543     protected:
 544         //@cond
 545         template <bool IsConst>
 546         class iterator_type
 547             : public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
 548         {
 549             typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
 550             typedef typename iterator_base_class::list_iterator list_iterator;
 551         public:
 552             iterator_type()
 553                 : iterator_base_class()
 554             {}
 555
 556             iterator_type( iterator_type const& src )
 557                 : iterator_base_class( src )
 558             {}
 559
 560             // This ctor should be protected...
 561             iterator_type( list_iterator itCur, list_iterator itEnd )
 562                 : iterator_base_class( itCur, itEnd )
 563             {}
 564         };
 565         //@endcond
 566
 567     public:
 568     ///@name Forward iterators
 569     //@{
 570         /// Forward iterator
 571         /**
 572             The forward iterator for a split-list has some features:
 573             - it has no post-increment operator
 574             - it depends on iterator of underlying \p OrderedList
 575         */
 576         typedef iterator_type<false>    iterator;
 577
 578         /// Const forward iterator
 579         /**
 580             For iterator's features and requirements see \ref iterator
 581         */
 582         typedef iterator_type<true>     const_iterator;
 583
 584         /// Returns a forward iterator addressing the first element in a split-list
 585         /**
 586             For empty list \code begin() == end() \endcode
 587         */
 588         iterator begin()
 589         {
 590             return iterator( m_List.begin(), m_List.end() );
 591         }
 592
 593         /// Returns an iterator that addresses the location succeeding the last element in a split-list
 594         /**
 595             Do not use the value returned by <tt>end</tt> function to access any item.
 596
 597             The returned value can be used only to control reaching the end of the split-list.
 598             For empty list \code begin() == end() \endcode
 599         */
 600         iterator end()
 601         {
 602             return iterator( m_List.end(), m_List.end() );
 603         }
 604
 605         /// Returns a forward const iterator addressing the first element in a split-list
 606         const_iterator begin() const
 607         {
 608             return const_iterator( m_List.begin(), m_List.end() );
 609         }
 610
 611         /// Returns a forward const iterator addressing the first element in a split-list
 612         const_iterator cbegin() const
 613         {
 614             return const_iterator( m_List.cbegin(), m_List.cend() );
 615         }
 616
 617         /// Returns an const iterator that addresses the location succeeding the last element in a split-list
 618         const_iterator end() const
 619         {
 620             return const_iterator( m_List.end(), m_List.end() );
 621         }
 622
 623         /// Returns an const iterator that addresses the location succeeding the last element in a split-list
 624         const_iterator cend() const
 625         {
 626             return const_iterator( m_List.cend(), m_List.cend() );
 627         }
 628     //@}
 629
 630     protected:
 631         //@cond
 632         iterator insert_( value_type& val )
 633         {
 634             size_t nHash = hash_value( val );
 635             aux_node_type * pHead = get_bucket( nHash );
 636             assert( pHead != nullptr );
 637
 638             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
 639
 640             list_iterator it = m_List.insert_at_( pHead, val );
 641             if ( it != m_List.end() ) {
 642                 inc_item_count();
 643                 m_Stat.onInsertSuccess();
 644                 return iterator( it, m_List.end() );
 645             }
 646             m_Stat.onInsertFailed();
 647             return end();
 648         }
 649
 650         template <typename Func>
 651         std::pair<iterator, bool> update_( value_type& val, Func func, bool bAllowInsert )
 652         {
 653             size_t nHash = hash_value( val );
 654             aux_node_type * pHead = get_bucket( nHash );
 655             assert( pHead != nullptr );
 656
 657             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
 658
 659             std::pair<list_iterator, bool> ret = m_List.update_at_( pHead, val, func, bAllowInsert );
 660             if ( ret.first != m_List.end() ) {
 661                 if ( ret.second ) {
 662                     inc_item_count();
 663                     m_Stat.onUpdateNew();
 664                 }
 665                 else
 666                     m_Stat.onUpdateExist();
 667                 return std::make_pair( iterator(ret.first, m_List.end()), ret.second );
 668             }
 669             return std::make_pair( end(), ret.second );
 670         }
 671
 672         template <typename Q, typename Less >
 673         iterator find_with_( Q& val, Less pred )
 674         {
 675             CDS_UNUSED( pred );
 676             size_t nHash = hash_value( val );
 677             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
 678             aux_node_type * pHead = get_bucket( nHash );
 679             assert( pHead != nullptr );
 680
 681             auto it = m_List.find_at_( pHead, sv, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
 682             m_Stat.onFind( it != m_List.end() );
 683             return iterator( it, m_List.end() );
 684         }
 685
 686         template <typename Q>
 687         iterator find_( Q const& val )
 688         {
 689             size_t nHash = hash_value( val );
 690             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
 691             aux_node_type * pHead = get_bucket( nHash );
 692             assert( pHead != nullptr );
 693
 694             auto it = m_List.find_at_( pHead, sv, key_comparator() );
 695             m_Stat.onFind( it != m_List.end() );
 696             return iterator( it, m_List.end() );
 697         }
 698
 699         template <typename Q, typename Compare, typename Func>
 700         bool find_( Q& val, Compare cmp, Func f )
 701         {
 702             size_t nHash = hash_value( val );
 703             split_list::details::search_value_type<Q>  sv( val, split_list::regular_hash( nHash ));
 704             aux_node_type * pHead = get_bucket( nHash );
 705             assert( pHead != nullptr );
 706             return m_Stat.onFind( m_List.find_at( pHead, sv, cmp,
 707                 [&f](value_type& item, split_list::details::search_value_type<Q>& val){ f(item, val.val ); }));
 708         }
 709
 710         //@endcond
 711     };
 712
 713 }} // namespace cds::intrusive
 714
 715 #endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_NOGC_H