cds/intrusive/split_list_nogc.h

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