cds/intrusive/split_list.h

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