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(memory_model::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             m_Stat.onBucketInitContenton();
 419             back_off bkoff;
 420             while ( true ) {
 421                 dummy_node_type volatile * p = m_Buckets.bucket( nBucket );
 422                 if ( p != nullptr )
 423                     return const_cast<dummy_node_type *>( p );
 424                 bkoff();
 425                 m_Stat.onBusyWaitBucketInit();
 426             }
 427         }
 428
 429         dummy_node_type * get_bucket( size_t nHash )
 430         {
 431             size_t nBucket = bucket_no( nHash );
 432
 433             dummy_node_type * pHead = m_Buckets.bucket( nBucket );
 434             if ( pHead == nullptr )
 435                 pHead = init_bucket( nBucket );
 436
 437             assert( pHead->is_dummy() );
 438
 439             return pHead;
 440         }
 441
 442         void init()
 443         {
 444             // GC and OrderedList::gc must be the same
 445             static_assert( std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
 446
 447             // atomicity::empty_item_counter is not allowed as a item counter
 448             static_assert( !std::is_same<item_counter, cds::atomicity::empty_item_counter>::value,
 449                            "cds::atomicity::empty_item_counter is not allowed as a item counter");
 450
 451             // Initialize bucket 0
 452             dummy_node_type * pNode = alloc_dummy_node( 0 /*split_list::dummy_hash(0)*/ );
 453
 454             // insert_aux_node cannot return false for empty list
 455             CDS_VERIFY( m_List.insert_aux_node( pNode ));
 456
 457             m_Buckets.bucket( 0, pNode );
 458         }
 459
 460         void inc_item_count()
 461         {
 462             size_t sz = m_nBucketCountLog2.load(atomics::memory_order_relaxed);
 463             if ( ( ++m_ItemCounter >> sz ) > m_Buckets.load_factor() && (static_cast<size_t>(1) << sz ) < m_Buckets.capacity() )
 464             {
 465                 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
 466             }
 467         }
 468
 469         template <typename Q, typename Compare, typename Func>
 470         bool find_( Q& val, Compare cmp, Func f )
 471         {
 472             size_t nHash = hash_value( val );
 473             split_list::details::search_value_type<Q>  sv( val, split_list::regular_hash( nHash ));
 474             dummy_node_type * pHead = get_bucket( nHash );
 475             assert( pHead != nullptr );
 476
 477             return m_Stat.onFind(
 478                 m_List.find_at( pHead, sv, cmp,
 479                     [&f](value_type& item, split_list::details::search_value_type<Q>& val){ f(item, val.val ); })
 480             );
 481         }
 482
 483         template <typename Q, typename Compare>
 484         bool find_( Q const& val, Compare cmp )
 485         {
 486             size_t nHash = hash_value( val );
 487             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
 488             dummy_node_type * pHead = get_bucket( nHash );
 489             assert( pHead != nullptr );
 490
 491             return m_Stat.onFind( m_List.find_at( pHead, sv, cmp ));
 492         }
 493
 494         template <typename Q, typename Compare>
 495         bool get_( typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp )
 496         {
 497             size_t nHash = hash_value( val );
 498             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
 499             dummy_node_type * pHead = get_bucket( nHash );
 500             assert( pHead != nullptr );
 501
 502             return m_Stat.onFind( m_List.get_at( pHead, guard, sv, cmp ));
 503         }
 504
 505         template <typename Q>
 506         bool get_( typename guarded_ptr::native_guard& guard, Q const& key )
 507         {
 508             return get_( guard, key, key_comparator());
 509         }
 510
 511         template <typename Q, typename Less>
 512         bool get_with_( typename guarded_ptr::native_guard& guard, Q const& key, Less )
 513         {
 514             return get_( guard, key, typename wrapped_ordered_list::template make_compare_from_less<Less>());
 515         }
 516
 517         template <typename Q, typename Compare, typename Func>
 518         bool erase_( Q const& val, Compare cmp, Func f )
 519         {
 520             size_t nHash = hash_value( val );
 521             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
 522             dummy_node_type * pHead = get_bucket( nHash );
 523             assert( pHead != nullptr );
 524
 525             if ( m_List.erase_at( pHead, sv, cmp, f )) {
 526                 --m_ItemCounter;
 527                 m_Stat.onEraseSuccess();
 528                 return true;
 529             }
 530             m_Stat.onEraseFailed();
 531             return false;
 532         }
 533
 534         template <typename Q, typename Compare>
 535         bool erase_( Q const& val, Compare cmp )
 536         {
 537             size_t nHash = hash_value( val );
 538             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
 539             dummy_node_type * pHead = get_bucket( nHash );
 540             assert( pHead != nullptr );
 541
 542             if ( m_List.erase_at( pHead, sv, cmp ) ) {
 543                 --m_ItemCounter;
 544                 m_Stat.onEraseSuccess();
 545                 return true;
 546             }
 547             m_Stat.onEraseFailed();
 548             return false;
 549         }
 550
 551         template <typename Q, typename Compare>
 552         bool extract_( typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp )
 553         {
 554             size_t nHash = hash_value( val );
 555             split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
 556             dummy_node_type * pHead = get_bucket( nHash );
 557             assert( pHead != nullptr );
 558
 559             if ( m_List.extract_at( pHead, guard, sv, cmp ) ) {
 560                 --m_ItemCounter;
 561                 m_Stat.onExtractSuccess();
 562                 return true;
 563             }
 564             m_Stat.onExtractFailed();
 565             return false;
 566         }
 567
 568         template <typename Q>
 569         bool extract_( typename guarded_ptr::native_guard& guard, Q const& key )
 570         {
 571             return extract_( guard, key, key_comparator());
 572         }
 573
 574         template <typename Q, typename Less>
 575         bool extract_with_( typename guarded_ptr::native_guard& guard, Q const& key, Less )
 576         {
 577             return extract_( guard, key, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
 578         }
 579         //@endcond
 580
 581     public:
 582         /// Initialize split-ordered list of default capacity
 583         /**
 584             The default capacity is defined in bucket table constructor.
 585             See \p split_list::expandable_bucket_table, \p split_list::static_bucket_table
 586             which selects by \p split_list::dynamic_bucket_table option.
 587         */
 588         SplitListSet()
 589             : m_nBucketCountLog2(1)
 590         {
 591             init();
 592         }
 593
 594         /// Initialize split-ordered list
 595         SplitListSet(
 596             size_t nItemCount           ///< estimate average of item count
 597             , size_t nLoadFactor = 1    ///< load factor - average item count per bucket. Small integer up to 8, default is 1.
 598             )
 599             : m_Buckets( nItemCount, nLoadFactor )
 600             , m_nBucketCountLog2(1)
 601         {
 602             init();
 603         }
 604
 605     public:
 606         /// Inserts new node
 607         /**
 608             The function inserts \p val in the set if it does not contain
 609             an item with key equal to \p val.
 610
 611             Returns \p true if \p val is placed into the set, \p false otherwise.
 612         */
 613         bool insert( value_type& val )
 614         {
 615             size_t nHash = hash_value( val );
 616             dummy_node_type * pHead = get_bucket( nHash );
 617             assert( pHead != nullptr );
 618
 619             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
 620
 621             if ( m_List.insert_at( pHead, val )) {
 622                 inc_item_count();
 623                 m_Stat.onInsertSuccess();
 624                 return true;
 625             }
 626             m_Stat.onInsertFailed();
 627             return false;
 628         }
 629
 630         /// Inserts new node
 631         /**
 632             This function is intended for derived non-intrusive containers.
 633
 634             The function allows to split creating of new item into two part:
 635             - create item with key only
 636             - insert new item into the set
 637             - if inserting is success, calls  \p f functor to initialize value-field of \p val.
 638
 639             The functor signature is:
 640             \code
 641                 void func( value_type& val );
 642             \endcode
 643             where \p val is the item inserted.
 644             The user-defined functor is called only if the inserting is success.
 645
 646             @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
 647             \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
 648             synchronization.
 649         */
 650         template <typename Func>
 651         bool insert( value_type& val, Func f )
 652         {
 653             size_t nHash = hash_value( val );
 654             dummy_node_type * pHead = get_bucket( nHash );
 655             assert( pHead != nullptr );
 656
 657             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
 658
 659             if ( m_List.insert_at( pHead, val, f )) {
 660                 inc_item_count();
 661                 m_Stat.onInsertSuccess();
 662                 return true;
 663             }
 664             m_Stat.onInsertFailed();
 665             return false;
 666         }
 667
 668         /// Ensures that the \p val exists in the set
 669         /**
 670             The operation performs inserting or changing data with lock-free manner.
 671
 672             If the item \p val is not found in the set, then \p val is inserted into the set.
 673             Otherwise, the functor \p func is called with item found.
 674             The functor signature is:
 675             \code
 676                 void func( bool bNew, value_type& item, value_type& val );
 677             \endcode
 678             with arguments:
 679             - \p bNew - \p true if the item has been inserted, \p false otherwise
 680             - \p item - item of the set
 681             - \p val - argument \p val passed into the \p ensure function
 682             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 683             refers to the same thing.
 684
 685             The functor can change non-key fields of the \p item.
 686
 687             Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
 688             \p second is \p true if new item has been added or \p false if the item with \p key
 689             already is in the set.
 690
 691             @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
 692             \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
 693             synchronization.
 694         */
 695         template <typename Func>
 696         std::pair<bool, bool> ensure( value_type& val, Func func )
 697         {
 698             size_t nHash = hash_value( val );
 699             dummy_node_type * pHead = get_bucket( nHash );
 700             assert( pHead != nullptr );
 701
 702             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
 703
 704             std::pair<bool, bool> bRet = m_List.ensure_at( pHead, val, func );
 705             if ( bRet.first && bRet.second ) {
 706                 inc_item_count();
 707                 m_Stat.onEnsureNew();
 708             }
 709             else
 710                 m_Stat.onEnsureExist();
 711             return bRet;
 712         }
 713
 714         /// Unlinks the item \p val from the set
 715         /**
 716             The function searches the item \p val in the set and unlinks it from the set
 717             if it is found and is equal to \p val.
 718
 719             Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
 720             and deletes the item found. \p unlink finds an item by key and deletes it
 721             only if \p val is an item of that set, i.e. the pointer to item found
 722             is equal to <tt> &val </tt>.
 723
 724             The function returns \p true if success and \p false otherwise.
 725         */
 726         bool unlink( value_type& val )
 727         {
 728             size_t nHash = hash_value( val );
 729             dummy_node_type * pHead = get_bucket( nHash );
 730             assert( pHead != nullptr );
 731
 732             if ( m_List.unlink_at( pHead, val ) ) {
 733                 --m_ItemCounter;
 734                 m_Stat.onEraseSuccess();
 735                 return true;
 736             }
 737             m_Stat.onEraseFailed();
 738             return false;
 739         }
 740
 741         /// Deletes the item from the set
 742         /** \anchor cds_intrusive_SplitListSet_hp_erase
 743             The function searches an item with key equal to \p key in the set,
 744             unlinks it from the set, and returns \p true.
 745             If the item with key equal to \p key is not found the function return \p false.
 746
 747             Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
 748             and deletes the item found. \p unlink finds an item by key and deletes it
 749             only if \p key is an item of that set, i.e. the pointer to item found
 750             is equal to <tt> &key </tt>.
 751
 752             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 753         */
 754         template <typename Q>
 755         bool erase( Q const& key )
 756         {
 757             return erase_( key, key_comparator() );
 758         }
 759
 760         /// Deletes the item from the set with comparing functor \p pred
 761         /**
 762
 763             The function is an analog of \ref cds_intrusive_SplitListSet_hp_erase "erase(Q const&)"
 764             but \p pred predicate is used for key comparing.
 765             \p Less has the interface like \p std::less.
 766             \p pred must imply the same element order as the comparator used for building the set.
 767         */
 768         template <typename Q, typename Less>
 769         bool erase_with( const Q& key, Less pred )
 770         {
 771             CDS_UNUSED( pred );
 772             return erase_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
 773         }
 774
 775         /// Deletes the item from the set
 776         /** \anchor cds_intrusive_SplitListSet_hp_erase_func
 777             The function searches an item with key equal to \p key in the set,
 778             call \p f functor with item found, unlinks it from the set, and returns \p true.
 779             The \ref disposer specified by \p OrderedList class template parameter is called
 780             by garbage collector \p GC asynchronously.
 781
 782             The \p Func interface is
 783             \code
 784             struct functor {
 785                 void operator()( value_type const& item );
 786             };
 787             \endcode
 788
 789             If the item with key equal to \p key is not found the function return \p false.
 790
 791             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 792         */
 793         template <typename Q, typename Func>
 794         bool erase( Q const& key, Func f )
 795         {
 796             return erase_( key, key_comparator(), f );
 797         }
 798
 799         /// Deletes the item from the set with comparing functor \p pred
 800         /**
 801             The function is an analog of \ref cds_intrusive_SplitListSet_hp_erase_func "erase(Q const&, Func)"
 802             but \p pred predicate is used for key comparing.
 803             \p Less has the interface like \p std::less.
 804             \p pred must imply the same element order as the comparator used for building the set.
 805         */
 806         template <typename Q, typename Less, typename Func>
 807         bool erase_with( Q const& key, Less pred, Func f )
 808         {
 809             CDS_UNUSED( pred );
 810             return erase_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
 811         }
 812
 813         /// Extracts the item with specified \p key
 814         /** \anchor cds_intrusive_SplitListSet_hp_extract
 815             The function searches an item with key equal to \p key,
 816             unlinks it from the set, and returns it as \p guarded_ptr.
 817             If \p key is not found the function returns an empty guarded pointer.
 818
 819             Note the compare functor should accept a parameter of type \p Q that may be not the same as \p value_type.
 820
 821             The \p disposer specified in \p OrderedList class' template parameter is called automatically
 822             by garbage collector \p GC when returned \p guarded_ptr object will be destroyed or released.
 823             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 824
 825             Usage:
 826             \code
 827             typedef cds::intrusive::SplitListSet< your_template_args > splitlist_set;
 828             splitlist_set theSet;
 829             // ...
 830             {
 831                 splitlist_set::guarded_ptr gp( theSet.extract( 5 ));
 832                 if ( gp) {
 833                     // Deal with gp
 834                     // ...
 835                 }
 836                 // Destructor of gp releases internal HP guard
 837             }
 838             \endcode
 839         */
 840         template <typename Q>
 841         guarded_ptr extract( Q const& key )
 842         {
 843             guarded_ptr gp;
 844             extract_( gp.guard(), key );
 845             return gp;
 846         }
 847
 848         /// Extracts the item using compare functor \p pred
 849         /**
 850             The function is an analog of \ref cds_intrusive_SplitListSet_hp_extract "extract(Q const&)"
 851             but \p pred predicate is used for key comparing.
 852
 853             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 854             in any order.
 855             \p pred must imply the same element order as the comparator used for building the set.
 856         */
 857         template <typename Q, typename Less>
 858         guarded_ptr extract_with( Q const& key, Less pred )
 859         {
 860             guarded_ptr gp;
 861             extract_with_( gp.guard(), key, pred );
 862             return gp;
 863         }
 864
 865         /// Finds the key \p key
 866         /** \anchor cds_intrusive_SplitListSet_hp_find_func
 867             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 868             The interface of \p Func functor is:
 869             \code
 870             struct functor {
 871                 void operator()( value_type& item, Q& key );
 872             };
 873             \endcode
 874             where \p item is the item found, \p key is the <tt>find</tt> function argument.
 875
 876             The functor can change non-key fields of \p item. Note that the functor is only guarantee
 877             that \p item cannot be disposed during functor is executing.
 878             The functor does not serialize simultaneous access to the set \p item. If such access is
 879             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
 880
 881             Note the hash functor specified for class \p Traits template parameter
 882             should accept a parameter of type \p Q that can be not the same as \p value_type.
 883
 884             The function returns \p true if \p key is found, \p false otherwise.
 885         */
 886         template <typename Q, typename Func>
 887         bool find( Q& key, Func f )
 888         {
 889             return find_( key, key_comparator(), f );
 890         }
 891         //@cond
 892         template <typename Q, typename Func>
 893         bool find( Q const& key, Func f )
 894         {
 895             return find_( key, key_comparator(), f );
 896         }
 897         //@endcond
 898
 899         /// Finds the key \p key with \p pred predicate for comparing
 900         /**
 901             The function is an analog of \ref cds_intrusive_SplitListSet_hp_find_func "find(Q&, Func)"
 902             but \p cmp is used for key compare.
 903             \p Less has the interface like \p std::less.
 904             \p cmp must imply the same element order as the comparator used for building the set.
 905         */
 906         template <typename Q, typename Less, typename Func>
 907         bool find_with( Q& key, Less pred, Func f )
 908         {
 909             CDS_UNUSED( pred );
 910             return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
 911         }
 912         //@cond
 913         template <typename Q, typename Less, typename Func>
 914         bool find_with( Q const& key, Less pred, Func f )
 915         {
 916             CDS_UNUSED( pred );
 917             return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
 918         }
 919         //@endcond
 920
 921         /// Finds the key \p key
 922         /** \anchor cds_intrusive_SplitListSet_hp_find_val
 923             The function searches the item with key equal to \p key
 924             and returns \p true if it is found, and \p false otherwise.
 925
 926             Note the hash functor specified for class \p Traits template parameter
 927             should accept a parameter of type \p Q that can be not the same as \p value_type.
 928             Otherwise, you may use \p find_with functions with explicit predicate for key comparing.
 929         */
 930         template <typename Q>
 931         bool find( Q const& key )
 932         {
 933             return find_( key, key_comparator() );
 934         }
 935
 936         /// Finds the key \p key with \p pred predicate for comparing
 937         /**
 938             The function is an analog of \ref cds_intrusive_SplitListSet_hp_find_val "find(Q const&)"
 939             but \p cmp is used for key compare.
 940             \p Less has the interface like \p std::less.
 941             \p cmp must imply the same element order as the comparator used for building the set.
 942         */
 943         template <typename Q, typename Less>
 944         bool find_with( Q const& key, Less pred )
 945         {
 946             CDS_UNUSED( pred );
 947             return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
 948         }
 949
 950         /// Finds the key \p key and return the item found
 951         /** \anchor cds_intrusive_SplitListSet_hp_get
 952             The function searches the item with key equal to \p key
 953             and returns the item found as \p guarded_ptr.
 954             If \p key is not found the function returns an empty guarded pointer.
 955
 956             The \p disposer specified in \p OrderedList class' template parameter is called
 957             by garbage collector \p GC automatically when returned \p guarded_ptr object
 958             will be destroyed or released.
 959             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
 960
 961             Usage:
 962             \code
 963             typedef cds::intrusive::SplitListSet< your_template_params >  splitlist_set;
 964             splitlist_set theSet;
 965             // ...
 966             {
 967                 splitlist_set::guarded_ptr gp = theSet.get( 5 );
 968                 if ( gp ) {
 969                     // Deal with gp
 970                     //...
 971                 }
 972                 // Destructor of guarded_ptr releases internal HP guard
 973             }
 974             \endcode
 975
 976             Note the compare functor specified for \p OrderedList template parameter
 977             should accept a parameter of type \p Q that can be not the same as \p value_type.
 978         */
 979         template <typename Q>
 980         guarded_ptr get( Q const& key )
 981         {
 982             guarded_ptr gp;
 983             get_( gp.guard(), key );
 984             return gp;
 985         }
 986
 987         /// Finds the key \p key and return the item found
 988         /**
 989             The function is an analog of \ref cds_intrusive_SplitListSet_hp_get "get( Q const&)"
 990             but \p pred is used for comparing the keys.
 991
 992             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 993             in any order.
 994             \p pred must imply the same element order as the comparator used for building the set.
 995         */
 996         template <typename Q, typename Less>
 997         guarded_ptr get_with( Q const& key, Less pred )
 998         {
 999             guarded_ptr gp;
1000             get_with_( gp.guard(), key, pred );
1001             return gp;
1002         }
1003
1004         /// Returns item count in the set
1005         size_t size() const
1006         {
1007             return m_ItemCounter;
1008         }
1009
1010         /// Checks if the set is empty
1011         /**
1012             Emptiness is checked by item counting: if item count is zero then the set is empty.
1013             Thus, the correct item counting feature is an important part of split-list set implementation.
1014         */
1015         bool empty() const
1016         {
1017             return size() == 0;
1018         }
1019
1020         /// Clears the set (non-atomic)
1021         /**
1022             The function unlink all items from the set.
1023             The function is not atomic. Therefore, \p clear may be used only for debugging purposes.
1024
1025             For each item the \p disposer is called after unlinking.
1026         */
1027         void clear()
1028         {
1029             iterator it = begin();
1030             while ( it != end() ) {
1031                 iterator i(it);
1032                 ++i;
1033                 unlink( *it );
1034                 it = i;
1035             }
1036         }
1037
1038         /// Returns internal statistics
1039         stat const& statistics() const
1040         {
1041             return m_Stat;
1042         }
1043
1044     protected:
1045         //@cond
1046         template <bool IsConst>
1047         class iterator_type
1048             :public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
1049         {
1050             typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
1051             typedef typename iterator_base_class::list_iterator list_iterator;
1052         public:
1053             iterator_type()
1054                 : iterator_base_class()
1055             {}
1056
1057             iterator_type( iterator_type const& src )
1058                 : iterator_base_class( src )
1059             {}
1060
1061             // This ctor should be protected...
1062             iterator_type( list_iterator itCur, list_iterator itEnd )
1063                 : iterator_base_class( itCur, itEnd )
1064             {}
1065         };
1066         //@endcond
1067     public:
1068         /// Forward iterator
1069         /**
1070             The forward iterator for a split-list has some features:
1071             - it has no post-increment operator
1072             - it depends on iterator of underlying \p OrderedList
1073             - The iterator cannot be moved across thread boundary since it may contain GC's guard that is thread-private GC data.
1074             - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
1075               deleting operations it is no guarantee that you iterate all item in the split-list.
1076
1077             Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
1078             for debug purpose only.
1079         */
1080         typedef iterator_type<false>    iterator;
1081         /// Const forward iterator
1082         /**
1083             For iterator's features and requirements see \ref iterator
1084         */
1085         typedef iterator_type<true>     const_iterator;
1086
1087         /// Returns a forward iterator addressing the first element in a split-list
1088         /**
1089             For empty list \code begin() == end() \endcode
1090         */
1091         iterator begin()
1092         {
1093             return iterator( m_List.begin(), m_List.end() );
1094         }
1095
1096         /// Returns an iterator that addresses the location succeeding the last element in a split-list
1097         /**
1098             Do not use the value returned by <tt>end</tt> function to access any item.
1099
1100             The returned value can be used only to control reaching the end of the split-list.
1101             For empty list \code begin() == end() \endcode
1102         */
1103         iterator end()
1104         {
1105             return iterator( m_List.end(), m_List.end() );
1106         }
1107
1108         /// Returns a forward const iterator addressing the first element in a split-list
1109         const_iterator begin() const
1110         {
1111             return cbegin();
1112         }
1113         /// Returns a forward const iterator addressing the first element in a split-list
1114         const_iterator cbegin() const
1115         {
1116             return const_iterator( m_List.cbegin(), m_List.cend() );
1117         }
1118
1119         /// Returns an const iterator that addresses the location succeeding the last element in a split-list
1120         const_iterator end() const
1121         {
1122             return cend();
1123         }
1124         /// Returns an const iterator that addresses the location succeeding the last element in a split-list
1125         const_iterator cend() const
1126         {
1127             return const_iterator( m_List.cend(), m_List.cend() );
1128         }
1129
1130     };
1131
1132 }}  // namespace cds::intrusive
1133
1134 #endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_H