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