cds/intrusive/split_list.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_H
   4 #define CDSLIB_INTRUSIVE_SPLIT_LIST_H
   5
   6 #include <limits>
   7 #include <cds/intrusive/details/split_list_base.h>
   8
   9 namespace cds { namespace intrusive {
  10
  11     /// Split-ordered list
  12     /** @ingroup cds_intrusive_map
  13         \anchor cds_intrusive_SplitListSet_hp
  14
  15         Hash table implementation based on split-ordered list algorithm discovered by Ori Shalev and Nir Shavit, see
  16         - [2003] Ori Shalev, Nir Shavit "Split-Ordered Lists - Lock-free Resizable Hash Tables"
  17         - [2008] Nir Shavit "The Art of Multiprocessor Programming"
  18
  19         The split-ordered list is a lock-free implementation of an extensible unbounded hash table. It uses original
  20         recursive split-ordering algorithm discovered by Ori Shalev and Nir Shavit that allows to split buckets
  21         without item moving on resizing.
  22
  23         \anchor cds_SplitList_algo_desc
  24         <b>Short description</b>
  25         [from [2003] Ori Shalev, Nir Shavit "Split-Ordered Lists - Lock-free Resizable Hash Tables"]
  26
  27         The algorithm keeps all the items in one lock-free linked list, and gradually assigns the bucket pointers to
  28         the places in the list where a sublist of \93correct\94 items can be found. A bucket is initialized upon first
  29         access by assigning it to a new \93dummy\94 node (dashed contour) in the list, preceding all items that should be
  30         in that bucket. A newly created bucket splits an older bucket\92s chain, reducing the access cost to its items. The
  31         table uses a modulo 2**i hash (there are known techniques for \93pre-hashing\94 before a modulo 2**i hash
  32         to overcome possible binary correlations among values). The table starts at size 2 and repeatedly doubles in size.
  33
  34         Unlike moving an item, the operation of directing a bucket pointer can be done
  35         in a single CAS operation, and since items are not moved, they are never \93lost\94.
  36         However, to make this approach work, one must be able to keep the items in the
  37         list sorted in such a way that any bucket\92s sublist can be \93split\94 by directing a new
  38         bucket pointer within it. This operation must be recursively repeatable, as every
  39         split bucket may be split again and again as the hash table grows. To achieve this
  40         goal the authors introduced recursive split-ordering, a new ordering on keys that keeps items
  41         in a given bucket adjacent in the list throughout the repeated splitting process.
  42
  43         Magically, yet perhaps not surprisingly, recursive split-ordering is achieved by
  44         simple binary reversal: reversing the bits of the hash key so that the new key\92s
  45         most significant bits (MSB) are those that were originally its least significant.
  46         The split-order keys of regular nodes are exactly the bit-reverse image of the original
  47         keys after turning on their MSB. For example, items 9 and 13 are in the <tt>1 mod
  48         4</tt> bucket, which can be recursively split in two by inserting a new node between
  49         them.
  50
  51         To insert (respectively delete or search for) an item in the hash table, hash its
  52         key to the appropriate bucket using recursive split-ordering, follow the pointer to
  53         the appropriate location in the sorted items list, and traverse the list until the key\92s
  54         proper location in the split-ordering (respectively until the key or a key indicating
  55         the item is not in the list is found). Because of the combinatorial structure induced
  56         by the split-ordering, this will require traversal of no more than an expected constant number of items.
  57
  58         The design is modular: to implement the ordered items list, you can use one of several
  59         non-blocking list-based set algorithms: MichaelList, LazyList.
  60
  61         <b>Implementation</b>
  62
  63         Template parameters are:
  64         - \p GC - Garbage collector. Note the \p GC must be the same as the \p GC used for \p OrderedList
  65         - \p OrderedList - ordered list implementation used as a bucket for hash set, for example, \p MichaelList, \p LazyList.
  66             The intrusive ordered list implementation specifies the type \p T stored in the hash-set, the reclamation
  67             schema \p GC used by hash-set, the comparison functor for the type \p T and other features specific for
  68             the ordered list.
  69         - \p Traits - split-list traits, default is \p split_list::traits.
  70             Instead of defining \p Traits struct you may use option-based syntax with \p split_list::make_traits metafunction.
  71
  72         There are several specialization of the split-list class for different \p GC:
  73         - for \ref cds_urcu_gc "RCU type" include <tt><cds/intrusive/split_list_rcu.h></tt> - see
  74             \ref cds_intrusive_SplitListSet_rcu "RCU-based split-list"
  75         - for cds::gc::nogc include <tt><cds/intrusive/split_list_nogc.h></tt> - see
  76             \ref cds_intrusive_SplitListSet_nogc "persistent SplitListSet".
  77
  78         \anchor cds_SplitList_hash_functor
  79         <b>Hash functor</b>
  80
  81         Some member functions of split-ordered list accept the key parameter of type \p Q which differs from \p value_type.
  82         It is expected that type \p Q contains full key of \p value_type, and for equal keys of type \p Q and \p value_type
  83         the hash values of these keys must be equal too.
  84         The hash functor \p Traits::hash should accept parameters of both type:
  85         \code
  86         // Our node type
  87         struct Foo {
  88             std::string     key_    ;   // key field
  89             // ... other fields
  90         };
  91
  92         // Hash functor
  93         struct fooHash {
  94             size_t operator()( const std::string& s ) const
  95             {
  96                 return std::hash( s );
  97             }
  98
  99             size_t operator()( const Foo& f ) const
 100             {
 101                 return (*this)( f.key_ );
 102             }
 103         };
 104         \endcode
 105
 106         <b>How to use</b>
 107
 108         First, you should choose ordered list type to use in your split-list set:
 109         \code
 110         // For gc::HP-based MichaelList implementation
 111         #include <cds/intrusive/michael_list_hp.h>
 112
 113         // cds::intrusive::SplitListSet declaration
 114         #include <cds/intrusive/split_list.h>
 115
 116         // Type of set items
 117             //  Note you should declare your struct based on cds::intrusive::split_list::node
 118             //  which is a wrapper for ordered-list node struct.
 119             //  In our case, the node type for HP-based MichaelList is cds::intrusive::michael_list::node< cds::gc::HP >
 120         struct Foo: public cds::intrusive::split_list::node< cds::intrusive::michael_list::node< cds::gc::HP > >
 121         {
 122             std::string     key_    ;   // key field
 123             unsigned        val_    ;   // value field
 124             // ...  other value fields
 125         };
 126
 127         // Declare comparator for the item
 128         struct FooCmp
 129         {
 130             int operator()( const Foo& f1, const Foo& f2 ) const
 131             {
 132                 return f1.key_.compare( f2.key_ );
 133             }
 134         };
 135
 136         // Declare base ordered-list type for split-list
 137         typedef cds::intrusive::MichaelList< cds::gc::HP, Foo,
 138             typename cds::intrusive::michael_list::make_traits<
 139                 // hook option
 140                 cds::intrusive::opt::hook< cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::HP > > >
 141                 // item comparator option
 142                 ,cds::opt::compare< FooCmp >
 143             >::type
 144         >  Foo_list;
 145         \endcode
 146
 147         Second, you should declare split-list set container:
 148         \code
 149
 150         // Declare hash functor
 151         // Note, the hash functor accepts parameter type Foo and std::string
 152         struct FooHash {
 153             size_t operator()( const Foo& f ) const
 154             {
 155                 return cds::opt::v::hash<std::string>()( f.key_ );
 156             }
 157             size_t operator()( const std::string& s ) const
 158             {
 159                 return cds::opt::v::hash<std::string>()( s );
 160             }
 161         };
 162
 163         // Split-list set typedef
 164         typedef cds::intrusive::SplitListSet<
 165             cds::gc::HP
 166             ,Foo_list
 167             ,typename cds::intrusive::split_list::make_traits<
 168                 cds::opt::hash< FooHash >
 169             >::type
 170         > Foo_set;
 171         \endcode
 172
 173         Now, you can use \p Foo_set in your application.
 174         \code
 175             Foo_set    fooSet;
 176             Foo * foo = new Foo;
 177             foo->key_ = "First";
 178
 179             fooSet.insert( *foo );
 180
 181             // and so on ...
 182         \endcode
 183     */
 184     template <
 185         class GC,
 186         class OrderedList,
 187 #   ifdef CDS_DOXYGEN_INVOKED
 188         class Traits = split_list::traits
 189 #   else
 190         class Traits
 191 #   endif
 192     >
 193     class SplitListSet
 194     {
 195     public:
 196         typedef GC     gc;     ///< Garbage collector
 197         typedef Traits traits; ///< Set traits
 198
 199     protected:
 200         //@cond
 201         typedef split_list::details::rebind_list_traits<OrderedList, traits> wrapped_ordered_list;
 202         //@endcond
 203
 204     public:
 205 #   ifdef CDS_DOXYGEN_INVOKED
 206         typedef OrderedList         ordered_list;   ///< type of ordered list used as a base for split-list
 207 #   else
 208         typedef typename wrapped_ordered_list::result   ordered_list;
 209 #   endif
 210         typedef typename ordered_list::value_type       value_type;     ///< type of value stored in the split-list
 211         typedef typename ordered_list::key_comparator   key_comparator; ///< key comparison functor
 212         typedef typename ordered_list::disposer         disposer;       ///< Node disposer functor
 213
 214         /// Hash functor for \p %value_type and all its derivatives that you use
 215         typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
 216
 217         typedef typename traits::item_counter      item_counter; ///< Item counter type
 218         typedef typename traits::back_off          back_off;     ///< back-off strategy for spinning
 219         typedef typename traits::memory_model      memory_model; ///< Memory ordering. See cds::opt::memory_model option
 220         typedef typename traits::stat              stat;         ///< Internal statistics, see \p spit_list::stat
 221         typedef typename ordered_list::guarded_ptr guarded_ptr;  ///< Guarded pointer
 222
 223     protected:
 224         typedef typename ordered_list::node_type    list_node_type;  ///< Node type as declared in ordered list
 225         typedef split_list::node<list_node_type>    node_type;       ///< split-list node type
 226         typedef node_type                           dummy_node_type; ///< dummy node type
 227
 228         /// Split-list node traits
 229         /**
 230             This traits is intended for converting between underlying ordered list node type \p list_node_type
 231             and split-list node type \p node_type
 232         */
 233         typedef split_list::node_traits<typename ordered_list::node_traits>  node_traits;
 234
 235         //@cond
 236         /// Bucket table implementation
 237         typedef typename split_list::details::bucket_table_selector<
 238             traits::dynamic_bucket_table
 239             , gc
 240             , dummy_node_type
 241             , opt::allocator< typename traits::allocator >
 242             , opt::memory_model< memory_model >
 243         >::type bucket_table;
 244         //@endcond
 245
 246     protected:
 247         //@cond
 248         /// Ordered list wrapper to access protected members
 249         class ordered_list_wrapper: public ordered_list
 250         {
 251             typedef ordered_list base_class;
 252             typedef typename base_class::auxiliary_head       bucket_head_type;
 253
 254         public:
 255             bool insert_at( dummy_node_type * pHead, value_type& val )
 256             {
 257                 assert( pHead != nullptr );
 258                 bucket_head_type h(pHead);
 259                 return base_class::insert_at( h, val );
 260             }
 261
 262             template <typename Func>
 263             bool insert_at( dummy_node_type * pHead, value_type& val, Func f )
 264             {
 265                 assert( pHead != nullptr );
 266                 bucket_head_type h(pHead);
 267                 return base_class::insert_at( h, val, f );
 268             }
 269
 270             template <typename Func>
 271             std::pair<bool, bool> update_at( dummy_node_type * pHead, value_type& val, Func func, bool bAllowInsert )
 272             {
 273                 assert( pHead != nullptr );
 274                 bucket_head_type h(pHead);
 275                 return base_class::update_at( h, val, func, bAllowInsert );
 276             }
 277
 278             bool unlink_at( dummy_node_type * pHead, value_type& val )
 279             {
 280                 assert( pHead != nullptr );
 281                 bucket_head_type h(pHead);
 282                 return base_class::unlink_at( h, val );
 283             }
 284
 285             template <typename Q, typename Compare, typename Func>
 286             bool erase_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp, Func f )
 287             {
 288                 assert( pHead != nullptr );
 289                 bucket_head_type h(pHead);
 290                 return base_class::erase_at( h, val, cmp, f );
 291             }
 292
 293             template <typename Q, typename Compare>
 294             bool erase_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
 295             {
 296                 assert( pHead != nullptr );
 297                 bucket_head_type h(pHead);
 298                 return base_class::erase_at( h, val, cmp );
 299             }
 300
 301             template <typename Q, typename Compare>
 302             bool extract_at( dummy_node_type * pHead, typename guarded_ptr::native_guard& guard, split_list::details::search_value_type<Q> const& val, Compare cmp )
 303             {
 304                 assert( pHead != nullptr );
 305                 bucket_head_type h(pHead);
 306                 return base_class::extract_at( h, guard, val, cmp );
 307             }
 308
 309             template <typename Q, typename Compare, typename Func>
 310             bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f )
 311             {
 312                 assert( pHead != nullptr );
 313                 bucket_head_type h(pHead);
 314                 return base_class::find_at( h, val, cmp, f );
 315             }
 316
 317             template <typename Q, typename Compare>
 318             bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
 319             {
 320                 assert( pHead != nullptr );
 321                 bucket_head_type h(pHead);
 322                 return base_class::find_at( h, val, cmp );
 323             }
 324
 325             template <typename Q, typename Compare>
 326             bool get_at( dummy_node_type * pHead, typename guarded_ptr::native_guard& guard, split_list::details::search_value_type<Q> const& val, Compare cmp )
 327             {
 328                 assert( pHead != nullptr );
 329                 bucket_head_type h(pHead);
 330                 return base_class::get_at( h, guard, val, cmp );
 331             }
 332
 333             bool insert_aux_node( dummy_node_type * pNode )
 334             {
 335                 return base_class::insert_aux_node( pNode );
 336             }
 337             bool insert_aux_node( dummy_node_type * pHead, dummy_node_type * pNode )
 338             {
 339                 bucket_head_type h(pHead);
 340                 return base_class::insert_aux_node( h, pNode );
 341             }
 342         };
 343         //@endcond
 344
 345     protected:
 346         ordered_list_wrapper    m_List;             ///< Ordered list containing split-list items
 347         bucket_table            m_Buckets;          ///< bucket table
 348         atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
 349         atomics::atomic<size_t> m_nMaxItemCount;    ///< number of items container can hold, before we have to resize
 350         item_counter            m_ItemCounter;      ///< Item counter
 351         hash                    m_HashFunctor;      ///< Hash functor
 352         stat                    m_Stat;             ///< Internal statistics
 353
 354     protected:
 355         //@cond
 356         typedef cds::details::Allocator< dummy_node_type, typename traits::allocator >   dummy_node_allocator;
 357
 358         dummy_node_type * alloc_dummy_node( size_t nHash )
 359         {
 360             m_Stat.onHeadNodeAllocated();
 361             return dummy_node_allocator().New( nHash );
 362         }
 363         void free_dummy_node( dummy_node_type * p )
 364         {
 365             dummy_node_allocator().Delete( p );
 366             m_Stat.onHeadNodeFreed();
 367         }
 368
 369         /// Calculates hash value of \p key
 370         template <typename Q>
 371         size_t hash_value( Q const& key ) const
 372         {
 373             return m_HashFunctor( key );
 374         }
 375
 376         size_t bucket_no( size_t nHash ) const
 377         {
 378             return nHash & ( (1 << m_nBucketCountLog2.load(memory_model::memory_order_relaxed)) - 1 );
 379         }
 380
 381         static size_t parent_bucket( size_t nBucket )
 382         {
 383             assert( nBucket > 0 );
 384             return nBucket & ~( 1 << bitop::MSBnz( nBucket ));
 385         }
 386
 387         dummy_node_type * init_bucket( size_t nBucket )
 388         {
 389             assert( nBucket > 0 );
 390             size_t nParent = parent_bucket( nBucket );
 391
 392             dummy_node_type * pParentBucket = m_Buckets.bucket( nParent );
 393             if ( pParentBucket == nullptr ) {
 394                 pParentBucket = init_bucket( nParent );
 395                 m_Stat.onRecursiveInitBucket();
 396             }
 397
 398             assert( pParentBucket != nullptr );
 399
 400             // Allocate a dummy node for new bucket
 401             {
 402                 dummy_node_type * pBucket = alloc_dummy_node( split_list::dummy_hash( nBucket ));
 403                 if ( m_List.insert_aux_node( pParentBucket, pBucket )) {
 404                     m_Buckets.bucket( nBucket, pBucket );
 405                     m_Stat.onNewBucket();
 406                     return pBucket;
 407                 }
 408                 free_dummy_node( pBucket );
 409             }
 410
 411             // Another thread set the bucket. Wait while it done
 412
 413             // In this point, we must wait while nBucket is empty.
 414             // The compiler can decide that waiting loop can be "optimized" (stripped)
 415             // To prevent this situation, we use waiting on volatile bucket_head_ptr pointer.
 416             m_Stat.onBucketInitContenton();
 417             back_off bkoff;
 418             while ( true ) {
 419                 dummy_node_type volatile * p = m_Buckets.bucket( nBucket );
 420                 if ( p != nullptr )
 421                     return const_cast<dummy_node_type *>( p );
 422                 bkoff();
 423                 m_Stat.onBusyWaitBucketInit();
 424             }
 425         }
 426
 427         dummy_node_type * get_bucket( size_t nHash )
 428         {
 429             size_t nBucket = bucket_no( nHash );
 430
 431             dummy_node_type * pHead = m_Buckets.bucket( nBucket );
 432             if ( pHead == nullptr )
 433                 pHead = init_bucket( nBucket );
 434
 435             assert( pHead->is_dummy());
 436
 437             return pHead;
 438         }
 439
 440         void init()
 441         {
 442             // GC and OrderedList::gc must be the same
 443             static_assert( std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
 444
 445             // atomicity::empty_item_counter is not allowed as a item counter
 446             static_assert( !std::is_same<item_counter, cds::atomicity::empty_item_counter>::value,
 447                            "cds::atomicity::empty_item_counter is not allowed as a item counter");
 448
 449             // Initialize bucket 0
 450             dummy_node_type * pNode = alloc_dummy_node( 0 /*split_list::dummy_hash(0)*/ );
 451
 452             // insert_aux_node cannot return false for empty list
 453             CDS_VERIFY( m_List.insert_aux_node( pNode ));
 454
 455             m_Buckets.bucket( 0, pNode );
 456         }
 457
 458         static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor )
 459         {
 460             return nBucketCount * nLoadFactor;
 461         }
 462
 463         void inc_item_count()
 464         {
 465             size_t nMaxCount = m_nMaxItemCount.load(memory_model::memory_order_relaxed);
 466             if ( ++m_ItemCounter <= nMaxCount )
 467                 return;
 468
 469             size_t sz = m_nBucketCountLog2.load(memory_model::memory_order_relaxed);
 470             const size_t nBucketCount = static_cast<size_t>(1) << sz;
 471             if ( nBucketCount < m_Buckets.capacity()) {
 472                 // we may grow the bucket table
 473                 const size_t nLoadFactor = m_Buckets.load_factor();
 474                 if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ))
 475                     return; // someone already have updated m_nBucketCountLog2, so stop here
 476
 477                 m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ),
 478                                                          memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
 479                 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
 480             }
 481             else
 482                 m_nMaxItemCount.store( std::numeric_limits<size_t>::max(), memory_model::memory_order_relaxed );
 483         }
 484
 485         template <typename Q, typename Compare, typename Func>
 486         bool find_( Q& val, Compare cmp, Func f )
 487         {
 488             size_t nHash = hash_value( val );
 489             split_list::details::search_value_type<Q>  sv( val, split_list::regular_hash( nHash ));
 490             dummy_node_type * pHead = get_bucket( nHash );
 491             assert( pHead != nullptr );
 492
 493             return m_Stat.onFind(
 494                 m_List.find_at( pHead, sv, cmp,
 495                     [&f](value_type& item, split_list::details::search_value_type<Q>& val){ f(item, val.val ); })
 496             );
 497         }
 498
 499         template <typename Q, typename Compare>
 500         bool find_( Q const& val, Compare cmp )
 501         {
 502             size_t nHash = hash_value( val );
 503             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
 504             dummy_node_type * pHead = get_bucket( nHash );
 505             assert( pHead != nullptr );
 506
 507             return m_Stat.onFind( m_List.find_at( pHead, sv, cmp ));
 508         }
 509
 510         template <typename Q, typename Compare>
 511         bool get_( typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp )
 512         {
 513             size_t nHash = hash_value( val );
 514             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
 515             dummy_node_type * pHead = get_bucket( nHash );
 516             assert( pHead != nullptr );
 517
 518             return m_Stat.onFind( m_List.get_at( pHead, guard, sv, cmp ));
 519         }
 520
 521         template <typename Q>
 522         bool get_( typename guarded_ptr::native_guard& guard, Q const& key )
 523         {
 524             return get_( guard, key, key_comparator());
 525         }
 526
 527         template <typename Q, typename Less>
 528         bool get_with_( typename guarded_ptr::native_guard& guard, Q const& key, Less )
 529         {
 530             return get_( guard, key, typename wrapped_ordered_list::template make_compare_from_less<Less>());
 531         }
 532
 533         template <typename Q, typename Compare, typename Func>
 534         bool erase_( Q const& val, Compare cmp, Func f )
 535         {
 536             size_t nHash = hash_value( val );
 537             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
 538             dummy_node_type * pHead = get_bucket( nHash );
 539             assert( pHead != nullptr );
 540
 541             if ( m_List.erase_at( pHead, sv, cmp, f )) {
 542                 --m_ItemCounter;
 543                 m_Stat.onEraseSuccess();
 544                 return true;
 545             }
 546             m_Stat.onEraseFailed();
 547             return false;
 548         }
 549
 550         template <typename Q, typename Compare>
 551         bool erase_( Q const& val, Compare cmp )
 552         {
 553             size_t nHash = hash_value( val );
 554             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
 555             dummy_node_type * pHead = get_bucket( nHash );
 556             assert( pHead != nullptr );
 557
 558             if ( m_List.erase_at( pHead, sv, cmp )) {
 559                 --m_ItemCounter;
 560                 m_Stat.onEraseSuccess();
 561                 return true;
 562             }
 563             m_Stat.onEraseFailed();
 564             return false;
 565         }
 566
 567         template <typename Q, typename Compare>
 568         bool extract_( typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp )
 569         {
 570             size_t nHash = hash_value( val );
 571             split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
 572             dummy_node_type * pHead = get_bucket( nHash );
 573             assert( pHead != nullptr );
 574
 575             if ( m_List.extract_at( pHead, guard, sv, cmp )) {
 576                 --m_ItemCounter;
 577                 m_Stat.onExtractSuccess();
 578                 return true;
 579             }
 580             m_Stat.onExtractFailed();
 581             return false;
 582         }
 583
 584         template <typename Q>
 585         bool extract_( typename guarded_ptr::native_guard& guard, Q const& key )
 586         {
 587             return extract_( guard, key, key_comparator());
 588         }
 589
 590         template <typename Q, typename Less>
 591         bool extract_with_( typename guarded_ptr::native_guard& guard, Q const& key, Less )
 592         {
 593             return extract_( guard, key, typename wrapped_ordered_list::template make_compare_from_less<Less>());
 594         }
 595         //@endcond
 596
 597     public:
 598         /// Initialize split-ordered list of default capacity
 599         /**
 600             The default capacity is defined in bucket table constructor.
 601             See \p split_list::expandable_bucket_table, \p split_list::static_bucket_table
 602             which selects by \p split_list::dynamic_bucket_table option.
 603         */
 604         SplitListSet()
 605             : m_nBucketCountLog2(1)
 606             , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()))
 607         {
 608             init();
 609         }
 610
 611         /// Initialize split-ordered list
 612         SplitListSet(
 613             size_t nItemCount           ///< estimate average of item count
 614             , size_t nLoadFactor = 1    ///< load factor - average item count per bucket. Small integer up to 8, default is 1.
 615             )
 616             : m_Buckets( nItemCount, nLoadFactor )
 617             , m_nBucketCountLog2(1)
 618             , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()))
 619         {
 620             init();
 621         }
 622
 623     public:
 624         /// Inserts new node
 625         /**
 626             The function inserts \p val in the set if it does not contain
 627             an item with key equal to \p val.
 628
 629             Returns \p true if \p val is placed into the set, \p false otherwise.
 630         */
 631         bool insert( value_type& val )
 632         {
 633             size_t nHash = hash_value( val );
 634             dummy_node_type * pHead = get_bucket( nHash );
 635             assert( pHead != nullptr );
 636
 637             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
 638
 639             if ( m_List.insert_at( pHead, val )) {
 640                 inc_item_count();
 641                 m_Stat.onInsertSuccess();
 642                 return true;
 643             }
 644             m_Stat.onInsertFailed();
 645             return false;
 646         }
 647
 648         /// Inserts new node
 649         /**
 650             This function is intended for derived non-intrusive containers.
 651
 652             The function allows to split creating of new item into two part:
 653             - create item with key only
 654             - insert new item into the set
 655             - if inserting is success, calls  \p f functor to initialize value-field of \p val.
 656
 657             The functor signature is:
 658             \code
 659                 void func( value_type& val );
 660             \endcode
 661             where \p val is the item inserted.
 662             The user-defined functor is called only if the inserting is success.
 663
 664             @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
 665             \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
 666             synchronization.
 667         */
 668         template <typename Func>
 669         bool insert( value_type& val, Func f )
 670         {
 671             size_t nHash = hash_value( val );
 672             dummy_node_type * pHead = get_bucket( nHash );
 673             assert( pHead != nullptr );
 674
 675             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
 676
 677             if ( m_List.insert_at( pHead, val, f )) {
 678                 inc_item_count();
 679                 m_Stat.onInsertSuccess();
 680                 return true;
 681             }
 682             m_Stat.onInsertFailed();
 683             return false;
 684         }
 685
 686         /// Updates the node
 687         /**
 688             The operation performs inserting or changing data with lock-free manner.
 689
 690             If the item \p val is not found in the set, then \p val is inserted
 691             iff \p bAllowInsert is \p true.
 692             Otherwise, the functor \p func is called with item found.
 693             The functor signature is:
 694             \code
 695                 void func( bool bNew, value_type& item, value_type& val );
 696             \endcode
 697             with arguments:
 698             - \p bNew - \p true if the item has been inserted, \p false otherwise
 699             - \p item - item of the set
 700             - \p val - argument \p val passed into the \p update() function
 701             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 702             refers to the same thing.
 703
 704             The functor may change non-key fields of the \p item.
 705
 706             Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
 707             \p second is \p true if new item has been added or \p false if the item with \p val
 708             already is in the list.
 709
 710             @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
 711             \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
 712             synchronization.
 713         */
 714         template <typename Func>
 715         std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
 716         {
 717             size_t nHash = hash_value( val );
 718             dummy_node_type * pHead = get_bucket( nHash );
 719             assert( pHead != nullptr );
 720
 721             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
 722
 723             std::pair<bool, bool> bRet = m_List.update_at( pHead, val, func, bAllowInsert );
 724             if ( bRet.first && bRet.second ) {
 725                 inc_item_count();
 726                 m_Stat.onEnsureNew();
 727             }
 728             else
 729                 m_Stat.onEnsureExist();
 730             return bRet;
 731         }
 732         //@cond
 733         template <typename Func>
 734         CDS_DEPRECATED("ensure() is deprecated, use update()")
 735         std::pair<bool, bool> ensure( value_type& val, Func func )
 736         {
 737             return update( val, func, true );
 738         }
 739         //@endcond
 740
 741         /// Unlinks the item \p val from the set
 742         /**
 743             The function searches the item \p val in the set and unlinks it from the set
 744             if it is found and is equal to \p val.
 745
 746             Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
 747             and deletes the item found. \p unlink finds an item by key and deletes it
 748             only if \p val is an item of that set, i.e. the pointer to item found
 749             is equal to <tt> &val </tt>.
 750
 751             The function returns \p true if success and \p false otherwise.
 752         */
 753         bool unlink( value_type& val )
 754         {
 755             size_t nHash = hash_value( val );
 756             dummy_node_type * pHead = get_bucket( nHash );
 757             assert( pHead != nullptr );
 758
 759             if ( m_List.unlink_at( pHead, val )) {
 760                 --m_ItemCounter;
 761                 m_Stat.onEraseSuccess();
 762                 return true;
 763             }
 764             m_Stat.onEraseFailed();
 765             return false;
 766         }
 767
 768         /// Deletes the item from the set
 769         /** \anchor cds_intrusive_SplitListSet_hp_erase
 770             The function searches an item with key equal to \p key in the set,
 771             unlinks it from the set, and returns \p true.
 772             If the item with key equal to \p key is not found the function return \p false.
 773
 774             Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
 775             and deletes the item found. \p unlink finds an item by key and deletes it
 776             only if \p key is an item of that set, i.e. the pointer to item found
 777             is equal to <tt> &key </tt>.
 778
 779             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 780         */
 781         template <typename Q>
 782         bool erase( Q const& key )
 783         {
 784             return erase_( key, key_comparator());
 785         }
 786
 787         /// Deletes the item from the set with comparing functor \p pred
 788         /**
 789
 790             The function is an analog of \ref cds_intrusive_SplitListSet_hp_erase "erase(Q const&)"
 791             but \p pred predicate is used for key comparing.
 792             \p Less has the interface like \p std::less.
 793             \p pred must imply the same element order as the comparator used for building the set.
 794         */
 795         template <typename Q, typename Less>
 796         bool erase_with( const Q& key, Less pred )
 797         {
 798             CDS_UNUSED( pred );
 799             return erase_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>());
 800         }
 801
 802         /// Deletes the item from the set
 803         /** \anchor cds_intrusive_SplitListSet_hp_erase_func
 804             The function searches an item with key equal to \p key in the set,
 805             call \p f functor with item found, unlinks it from the set, and returns \p true.
 806             The \ref disposer specified by \p OrderedList class template parameter is called
 807             by garbage collector \p GC asynchronously.
 808
 809             The \p Func interface is
 810             \code
 811             struct functor {
 812                 void operator()( value_type const& item );
 813             };
 814             \endcode
 815
 816             If the item with key equal to \p key is not found the function return \p false.
 817
 818             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 819         */
 820         template <typename Q, typename Func>
 821         bool erase( Q const& key, Func f )
 822         {
 823             return erase_( key, key_comparator(), f );
 824         }
 825
 826         /// Deletes the item from the set with comparing functor \p pred
 827         /**
 828             The function is an analog of \ref cds_intrusive_SplitListSet_hp_erase_func "erase(Q const&, Func)"
 829             but \p pred predicate is used for key comparing.
 830             \p Less has the interface like \p std::less.
 831             \p pred must imply the same element order as the comparator used for building the set.
 832         */
 833         template <typename Q, typename Less, typename Func>
 834         bool erase_with( Q const& key, Less pred, Func f )
 835         {
 836             CDS_UNUSED( pred );
 837             return erase_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
 838         }
 839
 840         /// Extracts the item with specified \p key
 841         /** \anchor cds_intrusive_SplitListSet_hp_extract
 842             The function searches an item with key equal to \p key,
 843             unlinks it from the set, and returns it as \p guarded_ptr.
 844             If \p key is not found the function returns an empty guarded pointer.
 845
 846             Note the compare functor should accept a parameter of type \p Q that may be not the same as \p value_type.
 847
 848             The \p disposer specified in \p OrderedList class' template parameter is called automatically
 849             by garbage collector \p GC when returned \p guarded_ptr object will be destroyed or released.
 850             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 851
 852             Usage:
 853             \code
 854             typedef cds::intrusive::SplitListSet< your_template_args > splitlist_set;
 855             splitlist_set theSet;
 856             // ...
 857             {
 858                 splitlist_set::guarded_ptr gp( theSet.extract( 5 ));
 859                 if ( gp) {
 860                     // Deal with gp
 861                     // ...
 862                 }
 863                 // Destructor of gp releases internal HP guard
 864             }
 865             \endcode
 866         */
 867         template <typename Q>
 868         guarded_ptr extract( Q const& key )
 869         {
 870             guarded_ptr gp;
 871             extract_( gp.guard(), key );
 872             return gp;
 873         }
 874
 875         /// Extracts the item using compare functor \p pred
 876         /**
 877             The function is an analog of \ref cds_intrusive_SplitListSet_hp_extract "extract(Q const&)"
 878             but \p pred predicate is used for key comparing.
 879
 880             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 881             in any order.
 882             \p pred must imply the same element order as the comparator used for building the set.
 883         */
 884         template <typename Q, typename Less>
 885         guarded_ptr extract_with( Q const& key, Less pred )
 886         {
 887             guarded_ptr gp;
 888             extract_with_( gp.guard(), key, pred );
 889             return gp;
 890         }
 891
 892         /// Finds the key \p key
 893         /** \anchor cds_intrusive_SplitListSet_hp_find_func
 894             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 895             The interface of \p Func functor is:
 896             \code
 897             struct functor {
 898                 void operator()( value_type& item, Q& key );
 899             };
 900             \endcode
 901             where \p item is the item found, \p key is the <tt>find</tt> function argument.
 902
 903             The functor can change non-key fields of \p item. Note that the functor is only guarantee
 904             that \p item cannot be disposed during functor is executing.
 905             The functor does not serialize simultaneous access to the set \p item. If such access is
 906             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
 907
 908             Note the hash functor specified for class \p Traits template parameter
 909             should accept a parameter of type \p Q that can be not the same as \p value_type.
 910
 911             The function returns \p true if \p key is found, \p false otherwise.
 912         */
 913         template <typename Q, typename Func>
 914         bool find( Q& key, Func f )
 915         {
 916             return find_( key, key_comparator(), f );
 917         }
 918         //@cond
 919         template <typename Q, typename Func>
 920         bool find( Q const& key, Func f )
 921         {
 922             return find_( key, key_comparator(), f );
 923         }
 924         //@endcond
 925
 926         /// Finds the key \p key with \p pred predicate for comparing
 927         /**
 928             The function is an analog of \ref cds_intrusive_SplitListSet_hp_find_func "find(Q&, Func)"
 929             but \p cmp is used for key compare.
 930             \p Less has the interface like \p std::less.
 931             \p cmp must imply the same element order as the comparator used for building the set.
 932         */
 933         template <typename Q, typename Less, typename Func>
 934         bool find_with( Q& key, Less pred, Func f )
 935         {
 936             CDS_UNUSED( pred );
 937             return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
 938         }
 939         //@cond
 940         template <typename Q, typename Less, typename Func>
 941         bool find_with( Q const& key, Less pred, Func f )
 942         {
 943             CDS_UNUSED( pred );
 944             return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
 945         }
 946         //@endcond
 947
 948         /// Checks whether the set contains \p key
 949         /**
 950             The function searches the item with key equal to \p key
 951             and returns \p true if it is found, and \p false otherwise.
 952
 953             Note the hash functor specified for class \p Traits template parameter
 954             should accept a parameter of type \p Q that can be not the same as \p value_type.
 955             Otherwise, you may use \p contains( Q const&, Less pred ) functions with explicit predicate for key comparing.
 956         */
 957         template <typename Q>
 958         bool contains( Q const& key )
 959         {
 960             return find_( key, key_comparator());
 961         }
 962         //@cond
 963         template <typename Q>
 964         CDS_DEPRECATED("deprecated, use contains()")
 965         bool find( Q const& key )
 966         {
 967             return contains( key );
 968         }
 969         //@endcond
 970
 971         /// Checks whether the set contains \p key using \p pred predicate for searching
 972         /**
 973             The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
 974             \p Less functor has the interface like \p std::less.
 975             \p Less must imply the same element order as the comparator used for building the set.
 976         */
 977         template <typename Q, typename Less>
 978         bool contains( Q const& key, Less pred )
 979         {
 980             CDS_UNUSED( pred );
 981             return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>());
 982         }
 983         //@cond
 984         template <typename Q, typename Less>
 985         CDS_DEPRECATED("deprecated, use contains()")
 986         bool find_with( Q const& key, Less pred )
 987         {
 988             return contains( key, pred );
 989         }
 990         //@endcond
 991
 992         /// Finds the key \p key and return the item found
 993         /** \anchor cds_intrusive_SplitListSet_hp_get
 994             The function searches the item with key equal to \p key
 995             and returns the item found as \p guarded_ptr.
 996             If \p key is not found the function returns an empty guarded pointer.
 997
 998             The \p disposer specified in \p OrderedList class' template parameter is called
 999             by garbage collector \p GC automatically when returned \p guarded_ptr object
1000             will be destroyed or released.
1001             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
1002
1003             Usage:
1004             \code
1005             typedef cds::intrusive::SplitListSet< your_template_params >  splitlist_set;
1006             splitlist_set theSet;
1007             // ...
1008             {
1009                 splitlist_set::guarded_ptr gp = theSet.get( 5 );
1010                 if ( gp ) {
1011                     // Deal with gp
1012                     //...
1013                 }
1014                 // Destructor of guarded_ptr releases internal HP guard
1015             }
1016             \endcode
1017
1018             Note the compare functor specified for \p OrderedList template parameter
1019             should accept a parameter of type \p Q that can be not the same as \p value_type.
1020         */
1021         template <typename Q>
1022         guarded_ptr get( Q const& key )
1023         {
1024             guarded_ptr gp;
1025             get_( gp.guard(), key );
1026             return gp;
1027         }
1028
1029         /// Finds the key \p key and return the item found
1030         /**
1031             The function is an analog of \ref cds_intrusive_SplitListSet_hp_get "get( Q const&)"
1032             but \p pred is used for comparing the keys.
1033
1034             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1035             in any order.
1036             \p pred must imply the same element order as the comparator used for building the set.
1037         */
1038         template <typename Q, typename Less>
1039         guarded_ptr get_with( Q const& key, Less pred )
1040         {
1041             guarded_ptr gp;
1042             get_with_( gp.guard(), key, pred );
1043             return gp;
1044         }
1045
1046         /// Returns item count in the set
1047         size_t size() const
1048         {
1049             return m_ItemCounter;
1050         }
1051
1052         /// Checks if the set is empty
1053         /**
1054             Emptiness is checked by item counting: if item count is zero then the set is empty.
1055             Thus, the correct item counting feature is an important part of split-list set implementation.
1056         */
1057         bool empty() const
1058         {
1059             return size() == 0;
1060         }
1061
1062         /// Clears the set (non-atomic)
1063         /**
1064             The function unlink all items from the set.
1065             The function is not atomic. Therefore, \p clear may be used only for debugging purposes.
1066
1067             For each item the \p disposer is called after unlinking.
1068         */
1069         void clear()
1070         {
1071             iterator it = begin();
1072             while ( it != end()) {
1073                 iterator i(it);
1074                 ++i;
1075                 unlink( *it );
1076                 it = i;
1077             }
1078         }
1079
1080         /// Returns internal statistics
1081         stat const& statistics() const
1082         {
1083             return m_Stat;
1084         }
1085
1086     protected:
1087         //@cond
1088         template <bool IsConst>
1089         class iterator_type
1090             :public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
1091         {
1092             typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
1093             typedef typename iterator_base_class::list_iterator list_iterator;
1094         public:
1095             iterator_type()
1096                 : iterator_base_class()
1097             {}
1098
1099             iterator_type( iterator_type const& src )
1100                 : iterator_base_class( src )
1101             {}
1102
1103             // This ctor should be protected...
1104             iterator_type( list_iterator itCur, list_iterator itEnd )
1105                 : iterator_base_class( itCur, itEnd )
1106             {}
1107         };
1108         //@endcond
1109     public:
1110         /// Forward iterator
1111         /**
1112             The forward iterator for a split-list has some features:
1113             - it has no post-increment operator
1114             - it depends on iterator of underlying \p OrderedList
1115             - The iterator cannot be moved across thread boundary since it may contain GC's guard that is thread-private GC data.
1116             - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
1117               deleting operations it is no guarantee that you iterate all item in the split-list.
1118
1119             Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
1120             for debug purpose only.
1121         */
1122         typedef iterator_type<false>    iterator;
1123         /// Const forward iterator
1124         /**
1125             For iterator's features and requirements see \ref iterator
1126         */
1127         typedef iterator_type<true>     const_iterator;
1128
1129         /// Returns a forward iterator addressing the first element in a split-list
1130         /**
1131             For empty list \code begin() == end() \endcode
1132         */
1133         iterator begin()
1134         {
1135             return iterator( m_List.begin(), m_List.end());
1136         }
1137
1138         /// Returns an iterator that addresses the location succeeding the last element in a split-list
1139         /**
1140             Do not use the value returned by <tt>end</tt> function to access any item.
1141
1142             The returned value can be used only to control reaching the end of the split-list.
1143             For empty list \code begin() == end() \endcode
1144         */
1145         iterator end()
1146         {
1147             return iterator( m_List.end(), m_List.end());
1148         }
1149
1150         /// Returns a forward const iterator addressing the first element in a split-list
1151         const_iterator begin() const
1152         {
1153             return cbegin();
1154         }
1155         /// Returns a forward const iterator addressing the first element in a split-list
1156         const_iterator cbegin() const
1157         {
1158             return const_iterator( m_List.cbegin(), m_List.cend());
1159         }
1160
1161         /// Returns an const iterator that addresses the location succeeding the last element in a split-list
1162         const_iterator end() const
1163         {
1164             return cend();
1165         }
1166         /// Returns an const iterator that addresses the location succeeding the last element in a split-list
1167         const_iterator cend() const
1168         {
1169             return const_iterator( m_List.cend(), m_List.cend());
1170         }
1171
1172     };
1173
1174 }}  // namespace cds::intrusive
1175
1176 #endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_H