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