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