cds/intrusive/split_list_rcu.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_RCU_H
  32 #define CDSLIB_INTRUSIVE_SPLIT_LIST_RCU_H
  33
  34 #include <limits>
  35
  36 #include <cds/intrusive/details/split_list_base.h>
  37 #include <cds/details/binary_functor_wrapper.h>
  38 #include <cds/details/type_padding.h>
  39
  40 namespace cds { namespace intrusive {
  41
  42     /// Split-ordered list RCU specialization
  43     /** @ingroup cds_intrusive_map
  44         \anchor cds_intrusive_SplitListSet_rcu
  45
  46         Hash table implementation based on split-ordered list algorithm discovered by Ori Shalev and Nir Shavit, see
  47         - [2003] Ori Shalev, Nir Shavit "Split-Ordered Lists - Lock-free Resizable Hash Tables"
  48         - [2008] Nir Shavit "The Art of Multiprocessor Programming"
  49
  50         The split-ordered list is a lock-free implementation of an extensible unbounded hash table. It uses original
  51         recursive split-ordering algorithm discovered by Ori Shalev and Nir Shavit that allows to split buckets
  52         without moving an item on resizing, see \ref cds_SplitList_algo_desc "short algo description".
  53
  54         <b>Implementation</b>
  55
  56         Template parameters are:
  57         - \p RCU - one of \ref cds_urcu_gc "RCU type"
  58         - \p OrderedList - ordered list implementation used as bucket for hash set, for example, MichaelList, LazyList.
  59             The intrusive ordered list implementation specifies the type \p T stored in the hash-set,
  60             the comparing functor for the type \p T and other features specific for the ordered list.
  61         - \p Traits - set traits, default isd \p split_list::traits.
  62             Instead of defining \p Traits struct you can use option-based syntax provided by \p split_list::make_traits metafunction.
  63
  64         @note About required features of hash functor see \ref cds_SplitList_hash_functor "SplitList general description".
  65
  66         \par How to use
  67         Before including <tt><cds/intrusive/split_list_rcu.h></tt> you should include appropriate RCU header file,
  68         see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
  69         For example, for \ref cds_urcu_general_buffered_gc "general-purpose buffered RCU" and
  70         MichaelList-based split-list you should include:
  71         \code
  72         #include <cds/urcu/general_buffered.h>
  73         #include <cds/intrusive/michael_list_rcu.h>
  74         #include <cds/intrusive/split_list_rcu.h>
  75
  76         // Declare Michael's list for type Foo and default traits:
  77         typedef cds::intrusive::MichaelList< cds::urcu::gc< cds::urcu::general_buffered<> >, Foo > rcu_michael_list;
  78
  79         // Declare split-list based on rcu_michael_list
  80         typedef cds::intrusive::SplitListSet< cds::urcu::gc< cds::urcu::general_buffered<> >, rcu_michael_list > rcu_split_list;
  81         \endcode
  82
  83     */
  84     template <
  85         class RCU,
  86         class OrderedList,
  87 #   ifdef CDS_DOXYGEN_INVOKED
  88         class Traits = split_list::traits
  89 #   else
  90         class Traits
  91 #   endif
  92     >
  93     class SplitListSet< cds::urcu::gc< RCU >, OrderedList, Traits >
  94     {
  95     public:
  96         typedef cds::urcu::gc< RCU > gc;   ///< RCU garbage collector
  97         typedef Traits           traits;   ///< Traits template parameters
  98
  99         /// Hash functor for \ref value_type and all its derivatives that you use
 100         typedef typename cds::opt::v::hash_selector< typename traits::hash >::type   hash;
 101
 102     protected:
 103         //@cond
 104         typedef split_list::details::rebind_list_traits<OrderedList, traits> wrapped_ordered_list;
 105         //@endcond
 106
 107     public:
 108 #   ifdef CDS_DOXYGEN_INVOKED
 109         typedef OrderedList         ordered_list;   ///< type of ordered list used as base for split-list
 110 #   else
 111         typedef typename wrapped_ordered_list::result    ordered_list;
 112 #   endif
 113         typedef typename ordered_list::value_type     value_type;     ///< type of value stored in the split-list
 114         typedef typename ordered_list::key_comparator key_comparator; ///< key compare functor
 115         typedef typename ordered_list::disposer       disposer;       ///< Node disposer functor
 116         typedef typename ordered_list::rcu_lock       rcu_lock;       ///< RCU scoped lock
 117         typedef typename ordered_list::exempt_ptr     exempt_ptr;     ///< pointer to extracted node
 118         typedef typename ordered_list::raw_ptr        raw_ptr;        ///< pointer to the node for \p get() function
 119         /// Group of \p extract_xxx functions require external locking if underlying ordered list requires that
 120         static CDS_CONSTEXPR const bool c_bExtractLockExternal = ordered_list::c_bExtractLockExternal;
 121
 122         typedef typename traits::item_counter item_counter; ///< Item counter type
 123         typedef typename traits::back_off     back_off;     ///< back-off strategy for spinning
 124         typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
 125         typedef typename traits::stat         stat;         ///< Internal statistics
 126
 127         // GC and OrderedList::gc must be the same
 128         static_assert( std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
 129
 130         // atomicity::empty_item_counter is not allowed as a item counter
 131         static_assert( !std::is_same<item_counter, cds::atomicity::empty_item_counter>::value,
 132                         "cds::atomicity::empty_item_counter is not allowed as a item counter");
 133
 134     protected:
 135         //@cond
 136         typedef typename ordered_list::node_type    list_node_type;  ///< Node type as declared in ordered list
 137         typedef split_list::node<list_node_type>    node_type;       ///< split-list node type
 138
 139         /// Split-list node traits
 140         /**
 141             This traits is intended for converting between underlying ordered list node type \ref list_node_type
 142             and split-list node type \ref node_type
 143         */
 144         typedef split_list::node_traits<typename ordered_list::node_traits>  node_traits;
 145
 146         /// Bucket table implementation
 147         typedef typename split_list::details::bucket_table_selector<
 148             traits::dynamic_bucket_table
 149             , gc
 150             , node_type
 151             , opt::allocator< typename traits::allocator >
 152             , opt::memory_model< memory_model >
 153             , opt::free_list< typename traits::free_list >
 154         >::type bucket_table;
 155
 156         typedef typename bucket_table::aux_node_type aux_node_type; ///< auxiliary node type
 157
 158         //@endcond
 159
 160     protected:
 161         //@cond
 162         /// Ordered list wrapper to access protected members of OrderedList
 163         class ordered_list_wrapper: public ordered_list
 164         {
 165             typedef ordered_list base_class;
 166             typedef typename base_class::auxiliary_head bucket_head_type;
 167
 168         public:
 169             bool insert_at( aux_node_type * pHead, value_type& val )
 170             {
 171                 assert( pHead != nullptr );
 172                 bucket_head_type h(pHead);
 173                 return base_class::insert_at( h, val );
 174             }
 175
 176             template <typename Func>
 177             bool insert_at( aux_node_type * pHead, value_type& val, Func f )
 178             {
 179                 assert( pHead != nullptr );
 180                 bucket_head_type h(pHead);
 181                 return base_class::insert_at( h, val, f );
 182             }
 183
 184             template <typename Func>
 185             std::pair<bool, bool> update_at( aux_node_type * pHead, value_type& val, Func func, bool bAllowInsert )
 186             {
 187                 assert( pHead != nullptr );
 188                 bucket_head_type h(pHead);
 189                 return base_class::update_at( h, val, func, bAllowInsert );
 190             }
 191
 192             bool unlink_at( aux_node_type * pHead, value_type& val )
 193             {
 194                 assert( pHead != nullptr );
 195                 bucket_head_type h(pHead);
 196                 return base_class::unlink_at( h, val );
 197             }
 198
 199             template <typename Q, typename Compare, typename Func>
 200             bool erase_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp, Func f )
 201             {
 202                 assert( pHead != nullptr );
 203                 bucket_head_type h(pHead);
 204                 return base_class::erase_at( h, val, cmp, f );
 205             }
 206
 207             template <typename Q, typename Compare>
 208             bool erase_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
 209             {
 210                 assert( pHead != nullptr );
 211                 bucket_head_type h(pHead);
 212                 return base_class::erase_at( h, val, cmp );
 213             }
 214
 215             template <typename Q, typename Compare>
 216             value_type * extract_at( aux_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp )
 217             {
 218                 assert( pHead != nullptr );
 219                 bucket_head_type h(pHead);
 220                 return base_class::extract_at( h, val, cmp );
 221             }
 222
 223             template <typename Q, typename Compare, typename Func>
 224             bool find_at( aux_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f )
 225             {
 226                 assert( pHead != nullptr );
 227                 bucket_head_type h(pHead);
 228                 return base_class::find_at( h, val, cmp, f );
 229             }
 230
 231             template <typename Q, typename Compare>
 232             bool find_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const & val, Compare cmp )
 233             {
 234                 assert( pHead != nullptr );
 235                 bucket_head_type h(pHead);
 236                 return base_class::find_at( h, val, cmp );
 237             }
 238
 239             template <typename Q, typename Compare>
 240             raw_ptr get_at( aux_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp )
 241             {
 242                 assert( pHead != nullptr );
 243                 bucket_head_type h(pHead);
 244                 return base_class::get_at( h, val, cmp );
 245             }
 246
 247             bool insert_aux_node( aux_node_type * pNode )
 248             {
 249                 return base_class::insert_aux_node( pNode );
 250             }
 251             bool insert_aux_node( aux_node_type * pHead, aux_node_type * pNode )
 252             {
 253                 bucket_head_type h(pHead);
 254                 return base_class::insert_aux_node( h, pNode );
 255             }
 256         };
 257
 258         template <typename Less>
 259         struct less_wrapper: public cds::opt::details::make_comparator_from_less<Less>
 260         {
 261             typedef cds::opt::details::make_comparator_from_less<Less> base_wrapper;
 262
 263             template <typename Q1, typename Q2>
 264             int operator()( split_list::details::search_value_type<Q1> const& v1, Q2 const& v2 ) const
 265             {
 266                 return base_wrapper::operator()( v1.val, v2 );
 267             }
 268
 269             template <typename Q1, typename Q2>
 270             int operator()( Q1 const& v1, split_list::details::search_value_type<Q2> const& v2 ) const
 271             {
 272                 return base_wrapper::operator()( v1, v2.val );
 273             }
 274         };
 275         //@endcond
 276
 277     public:
 278         /// Initialize split-ordered list of default capacity
 279         /**
 280             The default capacity is defined in bucket table constructor.
 281             See split_list::expandable_bucket_table, split_list::static_ducket_table
 282             which selects by split_list::dynamic_bucket_table option.
 283         */
 284         SplitListSet()
 285             : m_nBucketCountLog2(1)
 286             , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) )
 287         {
 288             init();
 289         }
 290
 291         /// Initialize split-ordered list
 292         SplitListSet(
 293             size_t nItemCount           ///< estimate average of item count
 294             , size_t nLoadFactor = 1    ///< load factor - average item count per bucket. Small integer up to 8, default is 1.
 295             )
 296             : m_Buckets( nItemCount, nLoadFactor )
 297             , m_nBucketCountLog2(1)
 298             , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) )
 299         {
 300             init();
 301         }
 302
 303         /// Destroys split-list
 304         ~SplitListSet()
 305         {
 306             m_List.clear();
 307             gc::force_dispose();
 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             The function makes RCU lock internally.
 317
 318             Returns \p true if \p val is placed into the set, \p false otherwise.
 319         */
 320         bool insert( value_type& val )
 321         {
 322             size_t nHash = hash_value( val );
 323             aux_node_type * pHead = get_bucket( nHash );
 324             assert( pHead != nullptr );
 325
 326             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
 327
 328             if ( m_List.insert_at( pHead, val )) {
 329                 inc_item_count();
 330                 m_Stat.onInsertSuccess();
 331                 return true;
 332             }
 333             m_Stat.onInsertFailed();
 334             return false;
 335         }
 336
 337         /// Inserts new node
 338         /**
 339             This function is intended for derived non-intrusive containers.
 340
 341             The function allows to split creating of new item into two part:
 342             - create item with key only
 343             - insert new item into the set
 344             - if inserting is success, calls  \p f functor to initialize value-field of \p val.
 345
 346             The functor signature is:
 347             \code
 348                 void func( value_type& val );
 349             \endcode
 350             where \p val is the item inserted.
 351
 352             The function makes RCU lock internally.
 353
 354             @warning For \ref cds_intrusive_MichaelList_rcu "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
 355             \ref cds_intrusive_LazyList_rcu "LazyList" provides exclusive access to inserted item and does not require any node-level
 356             synchronization.
 357             */
 358         template <typename Func>
 359         bool insert( value_type& val, Func f )
 360         {
 361             size_t nHash = hash_value( val );
 362             aux_node_type * pHead = get_bucket( nHash );
 363             assert( pHead != nullptr );
 364
 365             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
 366
 367             if ( m_List.insert_at( pHead, val, f )) {
 368                 inc_item_count();
 369                 m_Stat.onInsertSuccess();
 370                 return true;
 371             }
 372             m_Stat.onInsertFailed();
 373             return false;
 374         }
 375
 376         /// Updates the node
 377         /**
 378             The operation performs inserting or changing data with lock-free manner.
 379
 380             If the item \p val is not found in the set, then \p val is inserted
 381             iff \p bAllowInsert is \p true.
 382             Otherwise, the functor \p func is called with item found.
 383             The functor signature is:
 384             \code
 385                 void func( bool bNew, value_type& item, value_type& val );
 386             \endcode
 387             with arguments:
 388             - \p bNew - \p true if the item has been inserted, \p false otherwise
 389             - \p item - item of the set
 390             - \p val - argument \p val passed into the \p update() function
 391             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 392             refers to the same stuff.
 393
 394             The functor may change non-key fields of the \p item.
 395
 396             The function applies RCU lock internally.
 397
 398             Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
 399             \p second is \p true if new item has been added or \p false if the item with \p key
 400             already is in the list.
 401
 402             @warning For \ref cds_intrusive_MichaelList_rcu "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
 403             \ref cds_intrusive_LazyList_rcu "LazyList" provides exclusive access to inserted item and does not require any node-level
 404             synchronization.
 405         */
 406         template <typename Func>
 407         std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
 408         {
 409             size_t nHash = hash_value( val );
 410             aux_node_type * pHead = get_bucket( nHash );
 411             assert( pHead != nullptr );
 412
 413             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
 414
 415             std::pair<bool, bool> bRet = m_List.update_at( pHead, val, func, bAllowInsert );
 416             if ( bRet.first && bRet.second ) {
 417                 inc_item_count();
 418                 m_Stat.onUpdateNew();
 419             }
 420             else
 421                 m_Stat.onUpdateExist();
 422             return bRet;
 423         }
 424         //@cond
 425         template <typename Func>
 426         CDS_DEPRECATED("ensure() is deprecated, use update()")
 427         std::pair<bool, bool> ensure( value_type& val, Func func )
 428         {
 429             return update( val, func, true );
 430         }
 431         //@endcond
 432
 433         /// Unlinks the item \p val from the set
 434         /**
 435             The function searches the item \p val in the set and unlinks it from the set
 436             if it is found and is equal to \p val.
 437
 438             Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
 439             and deletes the item found. \p unlink finds an item by key and deletes it
 440             only if \p val is an item of that set, i.e. the pointer to item found
 441             is equal to <tt> &val </tt>.
 442
 443             RCU \p synchronize method can be called, therefore, RCU should not be locked.
 444
 445             The function returns \p true if success and \p false otherwise.
 446         */
 447         bool unlink( value_type& val )
 448         {
 449             size_t nHash = hash_value( val );
 450             aux_node_type * pHead = get_bucket( nHash );
 451             assert( pHead != nullptr );
 452
 453             if ( m_List.unlink_at( pHead, val ) ) {
 454                 --m_ItemCounter;
 455                 m_Stat.onEraseSuccess();
 456                 return true;
 457             }
 458             m_Stat.onEraseFailed();
 459             return false;
 460         }
 461
 462         /// Deletes the item from the set
 463         /** \anchor cds_intrusive_SplitListSet_rcu_erase
 464             The function searches an item with key equal to \p key in the set,
 465             unlinks it from the set, and returns \p true.
 466             If the item with key equal to \p key is not found the function return \p false.
 467
 468             Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
 469             and deletes the item found. \p unlink finds an item by key and deletes it
 470             only if \p key is an item of that set, i.e. the pointer to item found
 471             is equal to <tt> &key </tt>.
 472
 473             RCU \p synchronize method can be called, therefore, RCU should not be locked.
 474
 475             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 476         */
 477         template <typename Q>
 478         bool erase( Q const& key )
 479         {
 480             return erase_( key, key_comparator() );
 481         }
 482
 483         /// Deletes the item from the set using \p pred for searching
 484         /**
 485             The function is an analog of \ref cds_intrusive_SplitListSet_rcu_erase "erase(Q const&)"
 486             but \p cmp is used for key compare.
 487             \p Less has the interface like \p std::less.
 488             \p pred must imply the same element order as the comparator used for building the set.
 489         */
 490         template <typename Q, typename Less>
 491         bool erase_with( Q const& key, Less pred )
 492         {
 493             CDS_UNUSED( pred );
 494             return erase_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
 495         }
 496
 497         /// Deletes the item from the set
 498         /** \anchor cds_intrusive_SplitListSet_rcu_erase_func
 499             The function searches an item with key equal to \p key in the set,
 500             call \p f functor with item found, unlinks it from the set, and returns \p true.
 501             The \ref disposer specified by \p OrderedList class template parameter is called
 502             by garbage collector \p GC asynchronously.
 503
 504             The \p Func interface is
 505             \code
 506             struct functor {
 507                 void operator()( value_type const& item );
 508             };
 509             \endcode
 510
 511             If the item with key equal to \p key is not found the function return \p false.
 512
 513             RCU \p synchronize method can be called, therefore, RCU should not be locked.
 514
 515             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 516         */
 517         template <typename Q, typename Func>
 518         bool erase( Q const& key, Func f )
 519         {
 520             return erase_( key, key_comparator(), f );
 521         }
 522
 523         /// Deletes the item from the set using \p pred for searching
 524         /**
 525             The function is an analog of \ref cds_intrusive_SplitListSet_rcu_erase_func "erase(Q const&, Func)"
 526             but \p cmp is used for key compare.
 527             \p Less has the interface like \p std::less.
 528             \p pred must imply the same element order as the comparator used for building the set.
 529         */
 530         template <typename Q, typename Less, typename Func>
 531         bool erase_with( Q const& key, Less pred, Func f )
 532         {
 533             CDS_UNUSED( pred );
 534             return erase_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
 535         }
 536
 537         /// Extracts an item from the set
 538         /** \anchor cds_intrusive_SplitListSet_rcu_extract
 539             The function searches an item with key equal to \p key in the set,
 540             unlinks it, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
 541             If the item with the key equal to \p key is not found the function returns an empty \p exempt_ptr.
 542
 543             Depends on \p bucket_type you should or should not lock RCU before calling of this function:
 544             - for the set based on \ref cds_intrusive_MichaelList_rcu "MichaelList" RCU should not be locked
 545             - for the set based on \ref cds_intrusive_LazyList_rcu "LazyList" RCU should be locked
 546             See ordered list implementation for details.
 547
 548             \code
 549             typedef cds::urcu::gc< general_buffered<> > rcu;
 550             typedef cds::intrusive::MichaelList< rcu, Foo > rcu_michael_list;
 551             typedef cds::intrusive::SplitListSet< rcu, rcu_michael_list, foo_traits > rcu_splitlist_set;
 552
 553             rcu_splitlist_set theSet;
 554             // ...
 555
 556             rcu_splitlist_set::exempt_ptr p;
 557
 558             // For MichaelList we should not lock RCU
 559
 560             // Now, you can apply extract function
 561             // Note that you must not delete the item found inside the RCU lock
 562             p = theList.extract( 10 );
 563             if ( p ) {
 564                 // do something with p
 565                 ...
 566             }
 567
 568             // We may safely release p here
 569             // release() passes the pointer to RCU reclamation cycle:
 570             // it invokes RCU retire_ptr function with the disposer you provided for rcu_michael_list.
 571             p.release();
 572             \endcode
 573         */
 574         template <typename Q>
 575         exempt_ptr extract( Q const& key )
 576         {
 577             return exempt_ptr(extract_( key, key_comparator() ));
 578         }
 579
 580         /// Extracts an item from the set using \p pred for searching
 581         /**
 582             The function is an analog of \p extract(Q const&) but \p pred is used for key compare.
 583             \p Less functor has the interface like \p std::less.
 584             \p pred must imply the same element order as the comparator used for building the set.
 585         */
 586         template <typename Q, typename Less>
 587         exempt_ptr extract_with( Q const& key, Less pred )
 588         {
 589             return exempt_ptr( extract_with_( key, pred ));
 590         }
 591
 592         /// Finds the key \p key
 593         /** \anchor cds_intrusive_SplitListSet_rcu_find_func
 594             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 595             The interface of \p Func functor is:
 596             \code
 597             struct functor {
 598                 void operator()( value_type& item, Q& key );
 599             };
 600             \endcode
 601             where \p item is the item found, \p key is the <tt>find</tt> function argument.
 602
 603             The functor can change non-key fields of \p item. Note that the functor is only guarantee
 604             that \p item cannot be disposed during functor is executing.
 605             The functor does not serialize simultaneous access to the set \p item. If such access is
 606             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
 607
 608             The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
 609             can modify both arguments.
 610
 611             Note the hash functor specified for class \p Traits template parameter
 612             should accept a parameter of type \p Q that can be not the same as \p value_type.
 613
 614             The function applies RCU lock internally.
 615
 616             The function returns \p true if \p key is found, \p false otherwise.
 617         */
 618         template <typename Q, typename Func>
 619         bool find( Q& key, Func f )
 620         {
 621             return find_( key, key_comparator(), f );
 622         }
 623         //@cond
 624         template <typename Q, typename Func>
 625         bool find( Q const& key, Func f )
 626         {
 627             return find_( key, key_comparator(), f );
 628         }
 629         //@endcond
 630
 631         /// Finds the key \p key with \p pred predicate for comparing
 632         /**
 633             The function is an analog of \ref cds_intrusive_SplitListSet_rcu_find_func "find(Q&, Func)"
 634             but \p cmp is used for key compare.
 635             \p Less has the interface like \p std::less.
 636             \p cmp must imply the same element order as the comparator used for building the set.
 637         */
 638         template <typename Q, typename Less, typename Func>
 639         bool find_with( Q& key, Less pred, Func f )
 640         {
 641             CDS_UNUSED( pred );
 642             return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
 643         }
 644         //@cond
 645         template <typename Q, typename Less, typename Func>
 646         bool find_with( Q const& key, Less pred, Func f )
 647         {
 648             CDS_UNUSED( pred );
 649             return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
 650         }
 651         //@endcond
 652
 653         /// Checks whether the set contains \p key
 654         /**
 655             The function searches the item with key equal to \p key
 656             and returns \p true if it is found, and \p false otherwise.
 657
 658             Note the hash functor specified for class \p Traits template parameter
 659             should accept a parameter of type \p Q that can be not the same as \p value_type.
 660             Otherwise, you may use \p contains( Q const&, Less pred ) functions with explicit predicate for key comparing.
 661         */
 662         template <typename Q>
 663         bool contains( Q const& key )
 664         {
 665             return find_value( key, key_comparator() );
 666         }
 667         //@cond
 668         template <typename Q>
 669         CDS_DEPRECATED("deprecated, use contains()")
 670         bool find( Q const& key )
 671         {
 672             return contains( key );
 673         }
 674         //@endcond
 675
 676         /// Checks whether the set contains \p key using \p pred predicate for searching
 677         /**
 678             The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
 679             \p Less functor has the interface like \p std::less.
 680             \p Less must imply the same element order as the comparator used for building the list.
 681         */
 682         template <typename Q, typename Less>
 683         bool contains( Q const& key, Less pred )
 684         {
 685             CDS_UNUSED( pred );
 686             return find_value( key, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
 687         }
 688         //@cond
 689         template <typename Q, typename Less>
 690         CDS_DEPRECATED("deprecated, use contains()")
 691         bool find_with( Q const& key, Less pred )
 692         {
 693             return contains( key, pred );
 694         }
 695         //@endcond
 696
 697         /// Finds the key \p key and return the item found
 698         /** \anchor cds_intrusive_SplitListSet_rcu_get
 699             The function searches the item with key equal to \p key and returns the pointer to item found.
 700             If \p key is not found it returns \p nullptr.
 701
 702             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 703
 704             RCU should be locked before call of this function.
 705             Returned item is valid only while RCU is locked:
 706             \code
 707             typedef cds::intrusive::SplitListSet< your_template_parameters > set_class;
 708             set_class theSet;
 709             // ...
 710             typename set_class::raw_ptr rp;
 711             {
 712                 // Lock RCU
 713                 hash_set::rcu_lock lock;
 714
 715                 rp = theSet.get( 5 );
 716                 if ( rp ) {
 717                     // Deal with rp
 718                     //...
 719                 }
 720                 // Unlock RCU by rcu_lock destructor
 721                 // rp can be retired by disposer at any time after RCU has been unlocked
 722             }
 723             \endcode
 724         */
 725         template <typename Q>
 726         raw_ptr get( Q const& key )
 727         {
 728             return get_( key, key_comparator() );
 729         }
 730
 731         /// Finds the key \p key and return the item found
 732         /**
 733             The function is an analog of \ref cds_intrusive_SplitListSet_rcu_get "get(Q const&)"
 734             but \p pred is used for comparing the keys.
 735
 736             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 737             in any order.
 738             \p pred must imply the same element order as the comparator used for building the set.
 739         */
 740         template <typename Q, typename Less>
 741         raw_ptr get_with( Q const& key, Less pred )
 742         {
 743             CDS_UNUSED( pred );
 744             return get_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>());
 745         }
 746
 747
 748         /// Returns item count in the set
 749         size_t size() const
 750         {
 751             return m_ItemCounter;
 752         }
 753
 754         /// Checks if the set is empty
 755         /**
 756             Emptiness is checked by item counting: if item count is zero then the set is empty.
 757             Thus, the correct item counting feature is an important part of split-list set implementation.
 758         */
 759         bool empty() const
 760         {
 761             return size() == 0;
 762         }
 763
 764         /// Clears the set (not atomic)
 765         void clear()
 766         {
 767             iterator it = begin();
 768             while ( it != end() ) {
 769                 iterator i(it);
 770                 ++i;
 771                 unlink( *it );
 772                 it = i;
 773             }
 774         }
 775
 776         /// Returns internal statistics
 777         stat const& statistics() const
 778         {
 779             return m_Stat;
 780         }
 781
 782     protected:
 783         //@cond
 784         template <bool IsConst>
 785         class iterator_type
 786             :public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
 787         {
 788             typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
 789             typedef typename iterator_base_class::list_iterator list_iterator;
 790         public:
 791             iterator_type()
 792                 : iterator_base_class()
 793             {}
 794
 795             iterator_type( iterator_type const& src )
 796                 : iterator_base_class( src )
 797             {}
 798
 799             // This ctor should be protected...
 800             iterator_type( list_iterator itCur, list_iterator itEnd )
 801                 : iterator_base_class( itCur, itEnd )
 802             {}
 803         };
 804         //@endcond
 805
 806     public:
 807     ///@name Forward iterators (thread-safe under RCU lock)
 808     //@{
 809         /// Forward iterator
 810         /**
 811             The forward iterator for a split-list has some features:
 812             - it has no post-increment operator
 813             - it depends on iterator of underlying \p OrderedList
 814
 815             You may safely use iterators in multi-threaded environment only under RCU lock.
 816             Otherwise, a crash is possible if another thread deletes the element the iterator points to.
 817         */
 818         typedef iterator_type<false>    iterator;
 819
 820         /// Const forward iterator
 821         /**
 822             For iterator's features and requirements see \ref iterator
 823         */
 824         typedef iterator_type<true>     const_iterator;
 825
 826         /// Returns a forward iterator addressing the first element in a split-list
 827         /**
 828             For empty list \code begin() == end() \endcode
 829         */
 830         iterator begin()
 831         {
 832             return iterator( m_List.begin(), m_List.end() );
 833         }
 834
 835         /// Returns an iterator that addresses the location succeeding the last element in a split-list
 836         /**
 837             Do not use the value returned by <tt>end</tt> function to access any item.
 838
 839             The returned value can be used only to control reaching the end of the split-list.
 840             For empty list \code begin() == end() \endcode
 841         */
 842         iterator end()
 843         {
 844             return iterator( m_List.end(), m_List.end() );
 845         }
 846
 847         /// Returns a forward const iterator addressing the first element in a split-list
 848         const_iterator begin() const
 849         {
 850             return cbegin();
 851         }
 852         /// Returns a forward const iterator addressing the first element in a split-list
 853         const_iterator cbegin() const
 854         {
 855             return const_iterator( m_List.cbegin(), m_List.cend() );
 856         }
 857
 858         /// Returns an const iterator that addresses the location succeeding the last element in a split-list
 859         const_iterator end() const
 860         {
 861             return cend();
 862         }
 863         /// Returns an const iterator that addresses the location succeeding the last element in a split-list
 864         const_iterator cend() const
 865         {
 866             return const_iterator( m_List.cend(), m_List.cend() );
 867         }
 868     //@}
 869
 870     protected:
 871         //@cond
 872         aux_node_type * alloc_aux_node( size_t nHash )
 873         {
 874             m_Stat.onHeadNodeAllocated();
 875             aux_node_type* p = m_Buckets.alloc_aux_node();
 876             if ( p )
 877                 p->m_nHash = nHash;
 878             return p;
 879         }
 880
 881         void free_aux_node( aux_node_type * p )
 882         {
 883             m_Buckets.free_aux_node( p );
 884             m_Stat.onHeadNodeFreed();
 885         }
 886
 887         /// Calculates hash value of \p key
 888         template <typename Q>
 889         size_t hash_value( Q const& key ) const
 890         {
 891             return m_HashFunctor( key );
 892         }
 893
 894         size_t bucket_no( size_t nHash ) const
 895         {
 896             return nHash & ( (1 << m_nBucketCountLog2.load(memory_model::memory_order_relaxed)) - 1 );
 897         }
 898
 899         static size_t parent_bucket( size_t nBucket )
 900         {
 901             assert( nBucket > 0 );
 902             return nBucket & ~( 1 << bitop::MSBnz( nBucket ) );
 903         }
 904
 905         aux_node_type * init_bucket( size_t const nBucket )
 906         {
 907             assert( nBucket > 0 );
 908             size_t nParent = parent_bucket( nBucket );
 909
 910             aux_node_type * pParentBucket = m_Buckets.bucket( nParent );
 911             if ( pParentBucket == nullptr ) {
 912                 pParentBucket = init_bucket( nParent );
 913                 m_Stat.onRecursiveInitBucket();
 914             }
 915
 916             assert( pParentBucket != nullptr );
 917
 918             // Allocate an aux node for new bucket
 919             aux_node_type * pBucket = m_Buckets.bucket( nBucket );
 920
 921             back_off bkoff;
 922             for ( ;; pBucket = m_Buckets.bucket( nBucket ) ) {
 923                 if ( pBucket )
 924                     return pBucket;
 925
 926                 pBucket = alloc_aux_node( split_list::dummy_hash( nBucket ) );
 927                 if ( pBucket ) {
 928                     if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) {
 929                         m_Buckets.bucket( nBucket, pBucket );
 930                         m_Stat.onNewBucket();
 931                         return pBucket;
 932                     }
 933
 934                     // Another thread set the bucket. Wait while it done
 935                     free_aux_node( pBucket );
 936                     m_Stat.onBucketInitContenton();
 937                     break;
 938                 }
 939
 940                 // There are no free buckets. It means that the bucket table is full
 941                 // Wait while another thread set the bucket or a free bucket will be available
 942                 m_Stat.onBucketsExhausted();
 943                 bkoff();
 944             }
 945
 946             // Another thread set the bucket. Wait while it done
 947             for ( pBucket = m_Buckets.bucket( nBucket ); pBucket == nullptr; pBucket = m_Buckets.bucket( nBucket ) ) {
 948                 bkoff();
 949                 m_Stat.onBusyWaitBucketInit();
 950             }
 951
 952             return pBucket;
 953         }
 954
 955         aux_node_type * get_bucket( size_t nHash )
 956         {
 957             size_t nBucket = bucket_no( nHash );
 958
 959             aux_node_type * pHead = m_Buckets.bucket( nBucket );
 960             if ( pHead == nullptr )
 961                 pHead = init_bucket( nBucket );
 962
 963             assert( pHead->is_dummy() );
 964
 965             return pHead;
 966         }
 967
 968         void init()
 969         {
 970             // Initialize bucket 0
 971             aux_node_type * pNode = alloc_aux_node( 0 /*split_list::dummy_hash(0)*/ );
 972
 973             // insert_aux_node cannot return false for empty list
 974             CDS_VERIFY( m_List.insert_aux_node( pNode ));
 975
 976             m_Buckets.bucket( 0, pNode );
 977         }
 978
 979         static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor )
 980         {
 981             return nBucketCount * nLoadFactor;
 982         }
 983
 984         void inc_item_count()
 985         {
 986             size_t nMaxCount = m_nMaxItemCount.load(memory_model::memory_order_relaxed);
 987             if ( ++m_ItemCounter <= nMaxCount )
 988                 return;
 989
 990             size_t sz = m_nBucketCountLog2.load(memory_model::memory_order_relaxed);
 991             const size_t nBucketCount = static_cast<size_t>(1) << sz;
 992             if ( nBucketCount < m_Buckets.capacity() ) {
 993                 // we may grow the bucket table
 994                 const size_t nLoadFactor = m_Buckets.load_factor();
 995                 if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ))
 996                     return; // someone already have updated m_nBucketCountLog2, so stop here
 997
 998                 m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ),
 999                                                          memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
1000                 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
1001             }
1002             else
1003                 m_nMaxItemCount.store( std::numeric_limits<size_t>::max(), memory_model::memory_order_relaxed );
1004         }
1005
1006         template <typename Q, typename Compare, typename Func>
1007         bool find_( Q& val, Compare cmp, Func f )
1008         {
1009             size_t nHash = hash_value( val );
1010             split_list::details::search_value_type<Q>  sv( val, split_list::regular_hash( nHash ));
1011             aux_node_type * pHead = get_bucket( nHash );
1012             assert( pHead != nullptr );
1013
1014             return m_Stat.onFind( m_List.find_at( pHead, sv, cmp,
1015                 [&f](value_type& item, split_list::details::search_value_type<Q>& val){ f(item, val.val ); }));
1016         }
1017
1018         template <typename Q, typename Compare>
1019         bool find_value( Q const& val, Compare cmp )
1020         {
1021             size_t nHash = hash_value( val );
1022             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
1023             aux_node_type * pHead = get_bucket( nHash );
1024             assert( pHead != nullptr );
1025
1026             return m_Stat.onFind( m_List.find_at( pHead, sv, cmp ));
1027         }
1028
1029         template <typename Q, typename Compare>
1030         raw_ptr get_( Q const& val, Compare cmp )
1031         {
1032             size_t nHash = hash_value( val );
1033             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
1034             aux_node_type * pHead = get_bucket( nHash );
1035             assert( pHead != nullptr );
1036
1037             raw_ptr p = m_List.get_at( pHead, sv, cmp );
1038             m_Stat.onFind( !!p );
1039             return p;
1040         }
1041
1042         template <typename Q, typename Compare>
1043         value_type * extract_( Q const& val, Compare cmp )
1044         {
1045             size_t nHash = hash_value( val );
1046             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
1047             aux_node_type * pHead = get_bucket( nHash );
1048             assert( pHead != nullptr );
1049
1050             value_type * pNode = m_List.extract_at( pHead, sv, cmp );
1051             if ( pNode ) {
1052                 --m_ItemCounter;
1053                 m_Stat.onExtractSuccess();
1054             }
1055             else
1056                 m_Stat.onExtractFailed();
1057             return pNode;
1058         }
1059
1060         template <typename Q, typename Less>
1061         value_type * extract_with_( Q const& val, Less pred )
1062         {
1063             CDS_UNUSED( pred );
1064             return extract_( val, typename wrapped_ordered_list::template make_compare_from_less<Less>());
1065         }
1066
1067         template <typename Q, typename Compare>
1068         bool erase_( const Q& val, Compare cmp )
1069         {
1070             size_t nHash = hash_value( val );
1071             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
1072             aux_node_type * pHead = get_bucket( nHash );
1073             assert( pHead != nullptr );
1074
1075             if ( m_List.erase_at( pHead, sv, cmp ) ) {
1076                 --m_ItemCounter;
1077                 m_Stat.onEraseSuccess();
1078                 return true;
1079             }
1080             m_Stat.onEraseFailed();
1081             return false;
1082         }
1083
1084         template <typename Q, typename Compare, typename Func>
1085         bool erase_( Q const& val, Compare cmp, Func f )
1086         {
1087             size_t nHash = hash_value( val );
1088             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
1089             aux_node_type * pHead = get_bucket( nHash );
1090             assert( pHead != nullptr );
1091
1092             if ( m_List.erase_at( pHead, sv, cmp, f )) {
1093                 --m_ItemCounter;
1094                 m_Stat.onEraseSuccess();
1095                 return true;
1096             }
1097             m_Stat.onEraseFailed();
1098             return false;
1099         }
1100         //@endcond
1101
1102     protected:
1103         //@cond
1104         static unsigned const c_padding = cds::opt::actual_padding< traits::padding >::value;
1105
1106         typedef typename cds::details::type_padding< bucket_table, c_padding >::type padded_bucket_table;
1107         padded_bucket_table     m_Buckets;          ///< bucket table
1108
1109         typedef typename cds::details::type_padding< ordered_list_wrapper, c_padding >::type padded_ordered_list;
1110         padded_ordered_list     m_List;             ///< Ordered list containing split-list items
1111
1112         atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
1113         atomics::atomic<size_t> m_nMaxItemCount;    ///< number of items container can hold, before we have to resize
1114         item_counter            m_ItemCounter;      ///< Item counter
1115         hash                    m_HashFunctor;      ///< Hash functor
1116         stat                    m_Stat;             ///< Internal statistics accumulator
1117         //@endcond
1118     };
1119
1120 }}  // namespace cds::intrusive
1121
1122 #endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_RCU_H