cds/intrusive/split_list.h

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