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