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-2017
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_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> ordered_list_adapter;
 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 ordered_list_adapter::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 typename ordered_list_adapter::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             , typename ordered_list_adapter::aux_node
 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 ordered_list_adapter::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 ordered_list_adapter::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 ordered_list_adapter::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 ordered_list_adapter::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 ordered_list_adapter::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 ordered_list_adapter::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         /// Returns internal statistics for \p OrderedList
 783         typename OrderedList::stat const& list_statistics() const
 784         {
 785             return m_List.statistics();
 786         }
 787
 788     protected:
 789         //@cond
 790         template <bool IsConst>
 791         class iterator_type
 792             :public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
 793         {
 794             typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
 795             typedef typename iterator_base_class::list_iterator list_iterator;
 796         public:
 797             iterator_type()
 798                 : iterator_base_class()
 799             {}
 800
 801             iterator_type( iterator_type const& src )
 802                 : iterator_base_class( src )
 803             {}
 804
 805             // This ctor should be protected...
 806             iterator_type( list_iterator itCur, list_iterator itEnd )
 807                 : iterator_base_class( itCur, itEnd )
 808             {}
 809         };
 810         //@endcond
 811
 812     public:
 813     ///@name Forward iterators (thread-safe under RCU lock)
 814     //@{
 815         /// Forward iterator
 816         /**
 817             The forward iterator for a split-list has some features:
 818             - it has no post-increment operator
 819             - it depends on iterator of underlying \p OrderedList
 820
 821             You may safely use iterators in multi-threaded environment only under RCU lock.
 822             Otherwise, a crash is possible if another thread deletes the element the iterator points to.
 823         */
 824         typedef iterator_type<false>    iterator;
 825
 826         /// Const forward iterator
 827         /**
 828             For iterator's features and requirements see \ref iterator
 829         */
 830         typedef iterator_type<true>     const_iterator;
 831
 832         /// Returns a forward iterator addressing the first element in a split-list
 833         /**
 834             For empty list \code begin() == end() \endcode
 835         */
 836         iterator begin()
 837         {
 838             return iterator( m_List.begin(), m_List.end());
 839         }
 840
 841         /// Returns an iterator that addresses the location succeeding the last element in a split-list
 842         /**
 843             Do not use the value returned by <tt>end</tt> function to access any item.
 844
 845             The returned value can be used only to control reaching the end of the split-list.
 846             For empty list \code begin() == end() \endcode
 847         */
 848         iterator end()
 849         {
 850             return iterator( m_List.end(), m_List.end());
 851         }
 852
 853         /// Returns a forward const iterator addressing the first element in a split-list
 854         const_iterator begin() const
 855         {
 856             return cbegin();
 857         }
 858         /// Returns a forward const iterator addressing the first element in a split-list
 859         const_iterator cbegin() const
 860         {
 861             return const_iterator( m_List.cbegin(), m_List.cend());
 862         }
 863
 864         /// Returns an const iterator that addresses the location succeeding the last element in a split-list
 865         const_iterator end() const
 866         {
 867             return cend();
 868         }
 869         /// Returns an const iterator that addresses the location succeeding the last element in a split-list
 870         const_iterator cend() const
 871         {
 872             return const_iterator( m_List.cend(), m_List.cend());
 873         }
 874     //@}
 875
 876     protected:
 877         //@cond
 878         aux_node_type * alloc_aux_node( size_t nHash )
 879         {
 880             m_Stat.onHeadNodeAllocated();
 881             aux_node_type* p = m_Buckets.alloc_aux_node();
 882             if ( p )
 883                 p->m_nHash = nHash;
 884             return p;
 885         }
 886
 887         void free_aux_node( aux_node_type * p )
 888         {
 889             m_Buckets.free_aux_node( p );
 890             m_Stat.onHeadNodeFreed();
 891         }
 892
 893         /// Calculates hash value of \p key
 894         template <typename Q>
 895         size_t hash_value( Q const& key ) const
 896         {
 897             return m_HashFunctor( key );
 898         }
 899
 900         size_t bucket_no( size_t nHash ) const
 901         {
 902             return nHash & ( (1 << m_nBucketCountLog2.load(memory_model::memory_order_relaxed)) - 1 );
 903         }
 904
 905         static size_t parent_bucket( size_t nBucket )
 906         {
 907             assert( nBucket > 0 );
 908             return nBucket & ~( 1 << bitop::MSBnz( nBucket ));
 909         }
 910
 911         aux_node_type * init_bucket( size_t const nBucket )
 912         {
 913             assert( nBucket > 0 );
 914             size_t nParent = parent_bucket( nBucket );
 915
 916             aux_node_type * pParentBucket = m_Buckets.bucket( nParent );
 917             if ( pParentBucket == nullptr ) {
 918                 pParentBucket = init_bucket( nParent );
 919                 m_Stat.onRecursiveInitBucket();
 920             }
 921
 922             assert( pParentBucket != nullptr );
 923
 924             // Allocate an aux node for new bucket
 925             aux_node_type * pBucket = m_Buckets.bucket( nBucket );
 926
 927             back_off bkoff;
 928             for ( ;; pBucket = m_Buckets.bucket( nBucket )) {
 929                 if ( pBucket )
 930                     return pBucket;
 931
 932                 pBucket = alloc_aux_node( split_list::dummy_hash( nBucket ));
 933                 if ( pBucket ) {
 934                     if ( m_List.insert_aux_node( pParentBucket, pBucket )) {
 935                         m_Buckets.bucket( nBucket, pBucket );
 936                         m_Stat.onNewBucket();
 937                         return pBucket;
 938                     }
 939
 940                     // Another thread set the bucket. Wait while it done
 941                     free_aux_node( pBucket );
 942                     m_Stat.onBucketInitContenton();
 943                     break;
 944                 }
 945
 946                 // There are no free buckets. It means that the bucket table is full
 947                 // Wait while another thread set the bucket or a free bucket will be available
 948                 m_Stat.onBucketsExhausted();
 949                 bkoff();
 950             }
 951
 952             // Another thread set the bucket. Wait while it done
 953             for ( pBucket = m_Buckets.bucket( nBucket ); pBucket == nullptr; pBucket = m_Buckets.bucket( nBucket )) {
 954                 bkoff();
 955                 m_Stat.onBusyWaitBucketInit();
 956             }
 957
 958             return pBucket;
 959         }
 960
 961         aux_node_type * get_bucket( size_t nHash )
 962         {
 963             size_t nBucket = bucket_no( nHash );
 964
 965             aux_node_type * pHead = m_Buckets.bucket( nBucket );
 966             if ( pHead == nullptr )
 967                 pHead = init_bucket( nBucket );
 968
 969             assert( pHead->is_dummy());
 970
 971             return pHead;
 972         }
 973
 974         void init()
 975         {
 976             // Initialize bucket 0
 977             aux_node_type * pNode = alloc_aux_node( 0 /*split_list::dummy_hash(0)*/ );
 978
 979             // insert_aux_node cannot return false for empty list
 980             CDS_VERIFY( m_List.insert_aux_node( pNode ));
 981
 982             m_Buckets.bucket( 0, pNode );
 983         }
 984
 985         static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor )
 986         {
 987             return nBucketCount * nLoadFactor;
 988         }
 989
 990         void inc_item_count()
 991         {
 992             size_t nMaxCount = m_nMaxItemCount.load(memory_model::memory_order_relaxed);
 993             if ( ++m_ItemCounter <= nMaxCount )
 994                 return;
 995
 996             size_t sz = m_nBucketCountLog2.load(memory_model::memory_order_relaxed);
 997             const size_t nBucketCount = static_cast<size_t>(1) << sz;
 998             if ( nBucketCount < m_Buckets.capacity()) {
 999                 // we may grow the bucket table
1000                 const size_t nLoadFactor = m_Buckets.load_factor();
1001                 if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ))
1002                     return; // someone already have updated m_nBucketCountLog2, so stop here
1003
1004                 m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ),
1005                                                          memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
1006                 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
1007             }
1008             else
1009                 m_nMaxItemCount.store( std::numeric_limits<size_t>::max(), memory_model::memory_order_relaxed );
1010         }
1011
1012         template <typename Q, typename Compare, typename Func>
1013         bool find_( Q& val, Compare cmp, Func f )
1014         {
1015             size_t nHash = hash_value( val );
1016             split_list::details::search_value_type<Q>  sv( val, split_list::regular_hash( nHash ));
1017             aux_node_type * pHead = get_bucket( nHash );
1018             assert( pHead != nullptr );
1019
1020             return m_Stat.onFind( m_List.find_at( pHead, sv, cmp,
1021                 [&f](value_type& item, split_list::details::search_value_type<Q>& val){ f(item, val.val ); }));
1022         }
1023
1024         template <typename Q, typename Compare>
1025         bool find_value( Q const& val, Compare cmp )
1026         {
1027             size_t nHash = hash_value( val );
1028             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
1029             aux_node_type * pHead = get_bucket( nHash );
1030             assert( pHead != nullptr );
1031
1032             return m_Stat.onFind( m_List.find_at( pHead, sv, cmp ));
1033         }
1034
1035         template <typename Q, typename Compare>
1036         raw_ptr get_( Q const& val, Compare cmp )
1037         {
1038             size_t nHash = hash_value( val );
1039             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
1040             aux_node_type * pHead = get_bucket( nHash );
1041             assert( pHead != nullptr );
1042
1043             raw_ptr p = m_List.get_at( pHead, sv, cmp );
1044             m_Stat.onFind( !!p );
1045             return p;
1046         }
1047
1048         template <typename Q, typename Compare>
1049         value_type * extract_( Q const& val, Compare cmp )
1050         {
1051             size_t nHash = hash_value( val );
1052             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
1053             aux_node_type * pHead = get_bucket( nHash );
1054             assert( pHead != nullptr );
1055
1056             value_type * pNode = m_List.extract_at( pHead, sv, cmp );
1057             if ( pNode ) {
1058                 --m_ItemCounter;
1059                 m_Stat.onExtractSuccess();
1060             }
1061             else
1062                 m_Stat.onExtractFailed();
1063             return pNode;
1064         }
1065
1066         template <typename Q, typename Less>
1067         value_type * extract_with_( Q const& val, Less pred )
1068         {
1069             CDS_UNUSED( pred );
1070             return extract_( val, typename ordered_list_adapter::template make_compare_from_less<Less>());
1071         }
1072
1073         template <typename Q, typename Compare>
1074         bool erase_( const Q& val, Compare cmp )
1075         {
1076             size_t nHash = hash_value( val );
1077             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
1078             aux_node_type * pHead = get_bucket( nHash );
1079             assert( pHead != nullptr );
1080
1081             if ( m_List.erase_at( pHead, sv, cmp )) {
1082                 --m_ItemCounter;
1083                 m_Stat.onEraseSuccess();
1084                 return true;
1085             }
1086             m_Stat.onEraseFailed();
1087             return false;
1088         }
1089
1090         template <typename Q, typename Compare, typename Func>
1091         bool erase_( Q const& val, Compare cmp, Func f )
1092         {
1093             size_t nHash = hash_value( val );
1094             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
1095             aux_node_type * pHead = get_bucket( nHash );
1096             assert( pHead != nullptr );
1097
1098             if ( m_List.erase_at( pHead, sv, cmp, f )) {
1099                 --m_ItemCounter;
1100                 m_Stat.onEraseSuccess();
1101                 return true;
1102             }
1103             m_Stat.onEraseFailed();
1104             return false;
1105         }
1106         //@endcond
1107
1108     protected:
1109         //@cond
1110         static unsigned const c_padding = cds::opt::actual_padding< traits::padding >::value;
1111
1112         typedef typename cds::details::type_padding< bucket_table, c_padding >::type padded_bucket_table;
1113         padded_bucket_table     m_Buckets;          ///< bucket table
1114
1115         typedef typename cds::details::type_padding< ordered_list_wrapper, c_padding >::type padded_ordered_list;
1116         padded_ordered_list     m_List;             ///< Ordered list containing split-list items
1117
1118         atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
1119         atomics::atomic<size_t> m_nMaxItemCount;    ///< number of items container can hold, before we have to resize
1120         item_counter            m_ItemCounter;      ///< Item counter
1121         hash                    m_HashFunctor;      ///< Hash functor
1122         stat                    m_Stat;             ///< Internal statistics accumulator
1123         //@endcond
1124     };
1125
1126 }}  // namespace cds::intrusive
1127
1128 #endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_RCU_H