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