cds/intrusive/split_list.h

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