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