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                         dummy_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             , dummy_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_( dummy_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_( dummy_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( dummy_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_( dummy_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( dummy_node_type * pNode )
 157             {
 158                 return base_class::insert_aux_node( pNode );
 159             }
 160             bool insert_aux_node( dummy_node_type * pHead, dummy_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
 167         //@endcond
 168
 169     protected:
 170         ordered_list_wrapper    m_List;             ///< Ordered list containing split-list items
 171         bucket_table            m_Buckets;          ///< bucket table
 172         atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
 173         atomics::atomic<size_t> m_nMaxItemCount;    ///< number of items container can hold, before we have to resize
 174         item_counter            m_ItemCounter;      ///< Item counter
 175         hash                    m_HashFunctor;      ///< Hash functor
 176         stat                    m_Stat;             ///< Internal statistics
 177
 178     protected:
 179         //@cond
 180         typedef cds::details::Allocator< dummy_node_type, typename traits::allocator >   dummy_node_allocator;
 181
 182         dummy_node_type * alloc_dummy_node( size_t nHash )
 183         {
 184             m_Stat.onHeadNodeAllocated();
 185             return dummy_node_allocator().New( nHash );
 186         }
 187         void free_dummy_node( dummy_node_type * p )
 188         {
 189             dummy_node_allocator().Delete( p );
 190             m_Stat.onHeadNodeFreed();
 191         }
 192
 193         /// Calculates hash value of \p key
 194         template <typename Q>
 195         size_t hash_value( Q const& key ) const
 196         {
 197             return m_HashFunctor( key );
 198         }
 199
 200         size_t bucket_no( size_t nHash ) const
 201         {
 202             return nHash & ( (1 << m_nBucketCountLog2.load(memory_model::memory_order_relaxed)) - 1 );
 203         }
 204
 205         static size_t parent_bucket( size_t nBucket )
 206         {
 207             assert( nBucket > 0 );
 208             return nBucket & ~( 1 << bitop::MSBnz( nBucket ) );
 209         }
 210
 211         dummy_node_type * init_bucket( size_t nBucket )
 212         {
 213             assert( nBucket > 0 );
 214             size_t nParent = parent_bucket( nBucket );
 215
 216             dummy_node_type * pParentBucket = m_Buckets.bucket( nParent );
 217             if ( pParentBucket == nullptr ) {
 218                 pParentBucket = init_bucket( nParent );
 219                 m_Stat.onRecursiveInitBucket();
 220             }
 221
 222             assert( pParentBucket != nullptr );
 223
 224             // Allocate a dummy node for new bucket
 225             {
 226                 dummy_node_type * pBucket = alloc_dummy_node( split_list::dummy_hash( nBucket ) );
 227                 if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) {
 228                     m_Buckets.bucket( nBucket, pBucket );
 229                     m_Stat.onNewBucket();
 230                     return pBucket;
 231                 }
 232                 free_dummy_node( pBucket );
 233             }
 234
 235             // Another thread set the bucket. Wait while it done
 236
 237             // In this point, we must wait while nBucket is empty.
 238             // The compiler can decide that waiting loop can be "optimized" (stripped)
 239             // To prevent this situation, we use waiting on volatile bucket_head_ptr pointer.
 240             //
 241             m_Stat.onBucketInitContenton();
 242             back_off bkoff;
 243             while ( true ) {
 244                 dummy_node_type volatile * p = m_Buckets.bucket( nBucket );
 245                 if ( p && p != nullptr )
 246                     return const_cast<dummy_node_type *>( p );
 247                 bkoff();
 248                 m_Stat.onBusyWaitBucketInit();
 249             }
 250         }
 251
 252         dummy_node_type * get_bucket( size_t nHash )
 253         {
 254             size_t nBucket = bucket_no( nHash );
 255
 256             dummy_node_type * pHead = m_Buckets.bucket( nBucket );
 257             if ( pHead == nullptr )
 258                 pHead = init_bucket( nBucket );
 259
 260             assert( pHead->is_dummy() );
 261
 262             return pHead;
 263         }
 264
 265         void init()
 266         {
 267             // GC and OrderedList::gc must be the same
 268             static_assert( std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
 269
 270             // atomicity::empty_item_counter is not allowed as a item counter
 271             static_assert( !std::is_same<item_counter, cds::atomicity::empty_item_counter>::value,
 272                            "cds::atomicity::empty_item_counter is not allowed as a item counter");
 273
 274             // Initialize bucket 0
 275             dummy_node_type * pNode = alloc_dummy_node( 0 /*split_list::dummy_hash(0)*/ );
 276
 277             // insert_aux_node cannot return false for empty list
 278             CDS_VERIFY( m_List.insert_aux_node( pNode ));
 279
 280             m_Buckets.bucket( 0, pNode );
 281         }
 282
 283         static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor )
 284         {
 285             return nBucketCount * nLoadFactor;
 286         }
 287
 288         void inc_item_count()
 289         {
 290             size_t nMaxCount = m_nMaxItemCount.load(memory_model::memory_order_relaxed);
 291             if ( ++m_ItemCounter <= nMaxCount )
 292                 return;
 293
 294             size_t sz = m_nBucketCountLog2.load(memory_model::memory_order_relaxed);
 295             const size_t nBucketCount = static_cast<size_t>(1) << sz;
 296             if ( nBucketCount < m_Buckets.capacity() ) {
 297                 // we may grow the bucket table
 298                 const size_t nLoadFactor = m_Buckets.load_factor();
 299                 if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ))
 300                     return; // someone already have updated m_nBucketCountLog2, so stop here
 301
 302                 m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ),
 303                                                          memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
 304                 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
 305             }
 306             else
 307                 m_nMaxItemCount.store( std::numeric_limits<size_t>::max(), memory_model::memory_order_relaxed );
 308         }
 309
 310         //@endcond
 311
 312     public:
 313         /// Initialize split-ordered list of default capacity
 314         /**
 315             The default capacity is defined in bucket table constructor.
 316             See split_list::expandable_bucket_table, split_list::static_ducket_table
 317             which selects by split_list::dynamic_bucket_table option.
 318         */
 319         SplitListSet()
 320             : m_nBucketCountLog2(1)
 321             , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) )
 322         {
 323             init();
 324         }
 325
 326         /// Initialize split-ordered list
 327         SplitListSet(
 328             size_t nItemCount           ///< estimate average of item count
 329             , size_t nLoadFactor = 1    ///< load factor - average item count per bucket. Small integer up to 10, default is 1.
 330             )
 331             : m_Buckets( nItemCount, nLoadFactor )
 332             , m_nBucketCountLog2(1)
 333             , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) )
 334         {
 335             init();
 336         }
 337
 338     public:
 339         /// Inserts new node
 340         /**
 341             The function inserts \p val in the set if it does not contain
 342             an item with key equal to \p val.
 343
 344             Returns \p true if \p val is placed into the set, \p false otherwise.
 345         */
 346         bool insert( value_type& val )
 347         {
 348             return insert_( val ) != end();
 349         }
 350
 351         /// Updates the node
 352         /**
 353             The operation performs inserting or changing data with lock-free manner.
 354
 355             If the item \p val is not found in the set, then \p val is inserted
 356             iff \p bAllowInsert is \p true.
 357             Otherwise, the functor \p func is called with item found.
 358             The functor signature is:
 359             \code
 360                 void func( bool bNew, value_type& item, value_type& val );
 361             \endcode
 362             with arguments:
 363             - \p bNew - \p true if the item has been inserted, \p false otherwise
 364             - \p item - item of the set
 365             - \p val - argument \p val passed into the \p update() function
 366             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 367             refers to the same thing.
 368
 369             The functor may change non-key fields of the \p item.
 370
 371             Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
 372             \p second is \p true if new item has been added or \p false if the item with \p key
 373             already is in the list.
 374
 375             @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
 376             \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
 377             synchronization.
 378         */
 379         template <typename Func>
 380         std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
 381         {
 382             std::pair<iterator, bool> ret = update_( val, func, bAllowInsert );
 383             return std::make_pair( ret.first != end(), ret.second );
 384         }
 385         //@cond
 386         template <typename Func>
 387         CDS_DEPRECATED("ensure() is deprecated, use update()")
 388         std::pair<bool, bool> ensure( value_type& val, Func func )
 389         {
 390             return update( val, func, true );
 391         }
 392         //@endcond
 393
 394         /// Checks whether the set contains \p key
 395         /**
 396             The function searches the item with key equal to \p key
 397             and returns \p true if it is found, and \p false otherwise.
 398
 399             Note the hash functor specified for class \p Traits template parameter
 400             should accept a parameter of type \p Q that can be not the same as \p value_type.
 401             Otherwise, you may use \p contains( Q const&, Less pred ) functions with explicit predicate for key comparing.
 402         */
 403         template <typename Q>
 404         value_type * contains( Q const& key )
 405         {
 406             iterator it = find_( key );
 407             if ( it == end() )
 408                 return nullptr;
 409             return &*it;
 410         }
 411         //@cond
 412         template <typename Q>
 413         CDS_DEPRECATED("deprecated, use contains()")
 414         value_type * find( Q const& key )
 415         {
 416             return contains( key );
 417         }
 418         //@endcond
 419
 420         /// Checks whether the set contains \p key using \p pred predicate for searching
 421         /**
 422             The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
 423             \p Less functor has the interface like \p std::less.
 424             \p Less must imply the same element order as the comparator used for building the list.
 425         */
 426         template <typename Q, typename Less>
 427         value_type * contains( Q const& key, Less pred )
 428         {
 429             iterator it = find_with_( key, pred );
 430             if ( it == end() )
 431                 return nullptr;
 432             return &*it;
 433         }
 434         //@cond
 435         template <typename Q, typename Less>
 436         CDS_DEPRECATED("deprecated, use contains()")
 437         value_type * find_with( Q const& key, Less pred )
 438         {
 439             return contains( key, pred );
 440         }
 441         //@endcond
 442
 443         /// Finds the key \p key
 444         /** \anchor cds_intrusive_SplitListSet_nogc_find_func
 445             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 446             The interface of \p Func functor is:
 447             \code
 448             struct functor {
 449                 void operator()( value_type& item, Q& key );
 450             };
 451             \endcode
 452             where \p item is the item found, \p key is the <tt>find</tt> function argument.
 453
 454             The functor can change non-key fields of \p item.
 455             The functor does not serialize simultaneous access to the set \p item. If such access is
 456             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
 457
 458             Note the hash functor specified for class \p Traits template parameter
 459             should accept a parameter of type \p Q that can be not the same as \p value_type.
 460
 461             The function returns \p true if \p key is found, \p false otherwise.
 462         */
 463         template <typename Q, typename Func>
 464         bool find( Q& key, Func f )
 465         {
 466             return find_( key, key_comparator(), f );
 467         }
 468         //@cond
 469         template <typename Q, typename Func>
 470         bool find( Q const& key, Func f )
 471         {
 472             return find_( key, key_comparator(), f );
 473         }
 474         //@endcond
 475
 476         /// Finds the key \p key with \p pred predicate for comparing
 477         /**
 478             The function is an analog of \ref cds_intrusive_SplitListSet_nogc_find_func "find(Q&, Func)"
 479             but \p cmp is used for key compare.
 480             \p Less has the interface like \p std::less.
 481             \p cmp must imply the same element order as the comparator used for building the set.
 482         */
 483         template <typename Q, typename Less, typename Func>
 484         bool find_with( Q& key, Less pred, Func f )
 485         {
 486             CDS_UNUSED( pred );
 487             return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
 488         }
 489         //@cond
 490         template <typename Q, typename Less, typename Func>
 491         bool find_with( Q const& key, Less pred, Func f )
 492         {
 493             CDS_UNUSED( pred );
 494             return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
 495         }
 496         //@endcond
 497
 498         /// Checks if the set is empty
 499         /**
 500             Emptiness is checked by item counting: if item count is zero then the set is empty.
 501             Thus, the correct item counting feature is an important part of split-list implementation.
 502         */
 503         bool empty() const
 504         {
 505             return size() == 0;
 506         }
 507
 508         /// Returns item count in the set
 509         size_t size() const
 510         {
 511             return m_ItemCounter;
 512         }
 513
 514         /// Returns internal statistics
 515         stat const& statistics() const
 516         {
 517             return m_Stat;
 518         }
 519
 520     protected:
 521         //@cond
 522         template <bool IsConst>
 523         class iterator_type
 524             : public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
 525         {
 526             typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
 527             typedef typename iterator_base_class::list_iterator list_iterator;
 528         public:
 529             iterator_type()
 530                 : iterator_base_class()
 531             {}
 532
 533             iterator_type( iterator_type const& src )
 534                 : iterator_base_class( src )
 535             {}
 536
 537             // This ctor should be protected...
 538             iterator_type( list_iterator itCur, list_iterator itEnd )
 539                 : iterator_base_class( itCur, itEnd )
 540             {}
 541         };
 542         //@endcond
 543
 544     public:
 545         /// Forward iterator
 546         /**
 547             The forward iterator for a split-list has some features:
 548             - it has no post-increment operator
 549             - it depends on iterator of underlying \p OrderedList
 550         */
 551         typedef iterator_type<false>    iterator;
 552         /// Const forward iterator
 553         /**
 554             For iterator's features and requirements see \ref iterator
 555         */
 556         typedef iterator_type<true>     const_iterator;
 557
 558         /// Returns a forward iterator addressing the first element in a split-list
 559         /**
 560             For empty list \code begin() == end() \endcode
 561         */
 562         iterator begin()
 563         {
 564             return iterator( m_List.begin(), m_List.end() );
 565         }
 566
 567         /// Returns an iterator that addresses the location succeeding the last element in a split-list
 568         /**
 569             Do not use the value returned by <tt>end</tt> function to access any item.
 570
 571             The returned value can be used only to control reaching the end of the split-list.
 572             For empty list \code begin() == end() \endcode
 573         */
 574         iterator end()
 575         {
 576             return iterator( m_List.end(), m_List.end() );
 577         }
 578
 579         /// Returns a forward const iterator addressing the first element in a split-list
 580         //@{
 581         const_iterator begin() const
 582         {
 583             return const_iterator( m_List.begin(), m_List.end() );
 584         }
 585         const_iterator cbegin() const
 586         {
 587             return const_iterator( m_List.cbegin(), m_List.cend() );
 588         }
 589         //@}
 590
 591         /// Returns an const iterator that addresses the location succeeding the last element in a split-list
 592         //@{
 593         const_iterator end() const
 594         {
 595             return const_iterator( m_List.end(), m_List.end() );
 596         }
 597         const_iterator cend() const
 598         {
 599             return const_iterator( m_List.cend(), m_List.cend() );
 600         }
 601         //@}
 602
 603     protected:
 604         //@cond
 605         iterator insert_( value_type& val )
 606         {
 607             size_t nHash = hash_value( val );
 608             dummy_node_type * pHead = get_bucket( nHash );
 609             assert( pHead != nullptr );
 610
 611             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
 612
 613             list_iterator it = m_List.insert_at_( pHead, val );
 614             if ( it != m_List.end() ) {
 615                 inc_item_count();
 616                 m_Stat.onInsertSuccess();
 617                 return iterator( it, m_List.end() );
 618             }
 619             m_Stat.onInsertFailed();
 620             return end();
 621         }
 622
 623         template <typename Func>
 624         std::pair<iterator, bool> update_( value_type& val, Func func, bool bAllowInsert )
 625         {
 626             size_t nHash = hash_value( val );
 627             dummy_node_type * pHead = get_bucket( nHash );
 628             assert( pHead != nullptr );
 629
 630             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
 631
 632             std::pair<list_iterator, bool> ret = m_List.update_at_( pHead, val, func, bAllowInsert );
 633             if ( ret.first != m_List.end() ) {
 634                 if ( ret.second ) {
 635                     inc_item_count();
 636                     m_Stat.onEnsureNew();
 637                 }
 638                 else
 639                     m_Stat.onEnsureExist();
 640                 return std::make_pair( iterator(ret.first, m_List.end()), ret.second );
 641             }
 642             return std::make_pair( end(), ret.second );
 643         }
 644
 645         template <typename Q, typename Less >
 646         iterator find_with_( Q& val, Less pred )
 647         {
 648             CDS_UNUSED( pred );
 649             size_t nHash = hash_value( val );
 650             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
 651             dummy_node_type * pHead = get_bucket( nHash );
 652             assert( pHead != nullptr );
 653
 654             auto it = m_List.find_at_( pHead, sv, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
 655             m_Stat.onFind( it != m_List.end() );
 656             return iterator( it, m_List.end() );
 657         }
 658
 659         template <typename Q>
 660         iterator find_( Q const& val )
 661         {
 662             size_t nHash = hash_value( val );
 663             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
 664             dummy_node_type * pHead = get_bucket( nHash );
 665             assert( pHead != nullptr );
 666
 667             auto it = m_List.find_at_( pHead, sv, key_comparator() );
 668             m_Stat.onFind( it != m_List.end() );
 669             return iterator( it, m_List.end() );
 670         }
 671
 672         template <typename Q, typename Compare, typename Func>
 673         bool find_( Q& val, Compare cmp, Func f )
 674         {
 675             size_t nHash = hash_value( val );
 676             split_list::details::search_value_type<Q>  sv( val, split_list::regular_hash( nHash ));
 677             dummy_node_type * pHead = get_bucket( nHash );
 678             assert( pHead != nullptr );
 679             return m_Stat.onFind( m_List.find_at( pHead, sv, cmp,
 680                 [&f](value_type& item, split_list::details::search_value_type<Q>& val){ f(item, val.val ); }));
 681         }
 682
 683         //@endcond
 684     };
 685
 686 }} // namespace cds::intrusive
 687
 688 #endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_NOGC_H