cds/intrusive/split_list_nogc.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_INTRUSIVE_SPLIT_LIST_NOGC_H
   4 #define __CDS_INTRUSIVE_SPLIT_LIST_NOGC_H
   5
   6 #include <cds/intrusive/details/split_list_base.h>
   7 #include <cds/gc/nogc.h>
   8
   9 namespace cds { namespace intrusive {
  10
  11     /// Split-ordered list (template specialization for gc::nogc)
  12     /** @ingroup cds_intrusive_map
  13         \anchor cds_intrusive_SplitListSet_nogc
  14
  15         This specialization is intended for so-called persistent usage when no item
  16         reclamation may be performed. The class does not support deleting of list item.
  17
  18         See \ref cds_intrusive_SplitListSet_hp "SplitListSet" for description of template parameters.
  19         The template parameter \p OrderedList should be any gc::nogc-derived ordered list, for example,
  20         \ref cds_intrusive_MichaelList_nogc "persistent MichaelList",
  21         \ref cds_intrusive_LazyList_nogc "persistent LazyList"
  22     */
  23     template <
  24         class OrderedList,
  25 #ifdef CDS_DOXYGEN_INVOKED
  26         class Traits = split_list::traits
  27 #else
  28         class Traits
  29 #endif
  30     >
  31     class SplitListSet< cds::gc::nogc, OrderedList, Traits >
  32     {
  33     public:
  34         typedef cds::gc::nogc gc;     ///< Garbage collector
  35         typedef Traits        traits; ///< Traits template parameters
  36
  37         /// Hash functor for \p value_type and all its derivatives that you use
  38         typedef typename cds::opt::v::hash_selector< typename traits::hash >::type   hash;
  39
  40     protected:
  41         //@cond
  42         typedef split_list::details::rebind_list_traits<OrderedList, traits> wrapped_ordered_list;
  43         //@endcond
  44
  45     public:
  46 #   ifdef CDS_DOXYGEN_INVOKED
  47         typedef OrderedList ordered_list;   ///< type of ordered list used as base for split-list
  48 #   else
  49         typedef typename wrapped_ordered_list::result ordered_list;
  50 #   endif
  51         typedef typename ordered_list::value_type     value_type;     ///< type of value stored in the split-list
  52         typedef typename ordered_list::key_comparator key_comparator; ///< key comparison functor
  53         typedef typename ordered_list::disposer       disposer;       ///< Node disposer functor
  54
  55         typedef typename traits::item_counter item_counter; ///< Item counter type
  56         typedef typename traits::back_off     back_off;     ///< back-off strategy
  57         typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
  58         typedef typename traits::stat         stat;         ///< Internal statistics, see \p spit_list::stat
  59
  60     protected:
  61         typedef typename ordered_list::node_type  list_node_type;  ///< Node type as declared in ordered list
  62         typedef split_list::node<list_node_type>  node_type;       ///< split-list node type
  63         typedef node_type                         dummy_node_type; ///< dummy node type
  64
  65         /// Split-list node traits
  66         /**
  67             This traits is intended for converting between underlying ordered list node type \ref list_node_type
  68             and split-list node type \ref node_type
  69         */
  70         typedef split_list::node_traits<typename ordered_list::node_traits>  node_traits;
  71
  72         //@cond
  73         /// Bucket table implementation
  74         typedef typename split_list::details::bucket_table_selector<
  75             traits::dynamic_bucket_table
  76             , gc
  77             , dummy_node_type
  78             , opt::allocator< typename traits::allocator >
  79             , opt::memory_model< memory_model >
  80         >::type bucket_table;
  81
  82         typedef typename ordered_list::iterator list_iterator;
  83         typedef typename ordered_list::const_iterator list_const_iterator;
  84         //@endcond
  85
  86     protected:
  87         //@cond
  88         /// Ordered list wrapper to access protected members
  89         class ordered_list_wrapper: public ordered_list
  90         {
  91             typedef ordered_list base_class;
  92             typedef typename base_class::auxiliary_head       bucket_head_type;
  93
  94         public:
  95             list_iterator insert_at_( dummy_node_type * pHead, value_type& val )
  96             {
  97                 assert( pHead != nullptr );
  98                 bucket_head_type h(static_cast<list_node_type *>(pHead));
  99                 return base_class::insert_at_( h, val );
 100             }
 101
 102             template <typename Func>
 103             std::pair<list_iterator, bool> ensure_at_( dummy_node_type * pHead, value_type& val, Func func )
 104             {
 105                 assert( pHead != nullptr );
 106                 bucket_head_type h(static_cast<list_node_type *>(pHead));
 107                 return base_class::ensure_at_( h, val, func );
 108             }
 109
 110             template <typename Q, typename Compare, typename Func>
 111             bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f )
 112             {
 113                 assert( pHead != nullptr );
 114                 bucket_head_type h(static_cast<list_node_type *>(pHead));
 115                 return base_class::find_at( h, val, cmp, f );
 116             }
 117
 118             template <typename Q, typename Compare>
 119             list_iterator find_at_( dummy_node_type * pHead, split_list::details::search_value_type<Q> const & val, Compare cmp )
 120             {
 121                 assert( pHead != nullptr );
 122                 bucket_head_type h(static_cast<list_node_type *>(pHead));
 123                 return base_class::find_at_( h, val, cmp );
 124             }
 125
 126             bool insert_aux_node( dummy_node_type * pNode )
 127             {
 128                 return base_class::insert_aux_node( pNode );
 129             }
 130             bool insert_aux_node( dummy_node_type * pHead, dummy_node_type * pNode )
 131             {
 132                 bucket_head_type h(static_cast<list_node_type *>(pHead));
 133                 return base_class::insert_aux_node( h, pNode );
 134             }
 135         };
 136
 137         //@endcond
 138
 139     protected:
 140         ordered_list_wrapper    m_List;             ///< Ordered list containing split-list items
 141         bucket_table            m_Buckets;          ///< bucket table
 142         atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
 143         item_counter            m_ItemCounter;      ///< Item counter
 144         hash                    m_HashFunctor;      ///< Hash functor
 145         stat                    m_Stat;             ///< Internal statistics
 146
 147     protected:
 148         //@cond
 149         typedef cds::details::Allocator< dummy_node_type, typename traits::allocator >   dummy_node_allocator;
 150
 151         dummy_node_type * alloc_dummy_node( size_t nHash )
 152         {
 153             m_Stat.onHeadNodeAllocated();
 154             return dummy_node_allocator().New( nHash );
 155         }
 156         void free_dummy_node( dummy_node_type * p )
 157         {
 158             dummy_node_allocator().Delete( p );
 159             m_Stat.onHeadNodeFreed();
 160         }
 161
 162         /// Calculates hash value of \p key
 163         template <typename Q>
 164         size_t hash_value( Q const& key ) const
 165         {
 166             return m_HashFunctor( key );
 167         }
 168
 169         size_t bucket_no( size_t nHash ) const
 170         {
 171             return nHash & ( (1 << m_nBucketCountLog2.load(atomics::memory_order_relaxed)) - 1 );
 172         }
 173
 174         static size_t parent_bucket( size_t nBucket )
 175         {
 176             assert( nBucket > 0 );
 177             return nBucket & ~( 1 << bitop::MSBnz( nBucket ) );
 178         }
 179
 180         dummy_node_type * init_bucket( size_t nBucket )
 181         {
 182             assert( nBucket > 0 );
 183             size_t nParent = parent_bucket( nBucket );
 184
 185             dummy_node_type * pParentBucket = m_Buckets.bucket( nParent );
 186             if ( pParentBucket == nullptr ) {
 187                 pParentBucket = init_bucket( nParent );
 188                 m_Stat.onRecursiveInitBucket();
 189             }
 190
 191             assert( pParentBucket != nullptr );
 192
 193             // Allocate a dummy node for new bucket
 194             {
 195                 dummy_node_type * pBucket = alloc_dummy_node( split_list::dummy_hash( nBucket ) );
 196                 if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) {
 197                     m_Buckets.bucket( nBucket, pBucket );
 198                     m_Stat.onNewBucket();
 199                     return pBucket;
 200                 }
 201                 free_dummy_node( pBucket );
 202             }
 203
 204             // Another thread set the bucket. Wait while it done
 205
 206             // In this point, we must wait while nBucket is empty.
 207             // The compiler can decide that waiting loop can be "optimized" (stripped)
 208             // To prevent this situation, we use waiting on volatile bucket_head_ptr pointer.
 209             //
 210             m_Stat.onBucketInitContenton();
 211             back_off bkoff;
 212             while ( true ) {
 213                 dummy_node_type volatile * p = m_Buckets.bucket( nBucket );
 214                 if ( p && p != nullptr )
 215                     return const_cast<dummy_node_type *>( p );
 216                 bkoff();
 217                 m_Stat.onBusyWaitBucketInit();
 218             }
 219         }
 220
 221         dummy_node_type * get_bucket( size_t nHash )
 222         {
 223             size_t nBucket = bucket_no( nHash );
 224
 225             dummy_node_type * pHead = m_Buckets.bucket( nBucket );
 226             if ( pHead == nullptr )
 227                 pHead = init_bucket( nBucket );
 228
 229             assert( pHead->is_dummy() );
 230
 231             return pHead;
 232         }
 233
 234         void init()
 235         {
 236             // GC and OrderedList::gc must be the same
 237             static_assert( std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
 238
 239             // atomicity::empty_item_counter is not allowed as a item counter
 240             static_assert( !std::is_same<item_counter, cds::atomicity::empty_item_counter>::value,
 241                            "cds::atomicity::empty_item_counter is not allowed as a item counter");
 242
 243             // Initialize bucket 0
 244             dummy_node_type * pNode = alloc_dummy_node( 0 /*split_list::dummy_hash(0)*/ );
 245
 246             // insert_aux_node cannot return false for empty list
 247             CDS_VERIFY( m_List.insert_aux_node( pNode ));
 248
 249             m_Buckets.bucket( 0, pNode );
 250         }
 251
 252         void    inc_item_count()
 253         {
 254             size_t sz = m_nBucketCountLog2.load(atomics::memory_order_relaxed);
 255             if ( ( ++m_ItemCounter >> sz ) > m_Buckets.load_factor() && ((size_t)(1 << sz )) < m_Buckets.capacity() )
 256             {
 257                 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, atomics::memory_order_seq_cst, atomics::memory_order_relaxed );
 258             }
 259         }
 260
 261         //@endcond
 262
 263     public:
 264         /// Initialize split-ordered list of default capacity
 265         /**
 266             The default capacity is defined in bucket table constructor.
 267             See split_list::expandable_bucket_table, split_list::static_ducket_table
 268             which selects by split_list::dynamic_bucket_table option.
 269         */
 270         SplitListSet()
 271             : m_nBucketCountLog2(1)
 272         {
 273             init();
 274         }
 275
 276         /// Initialize split-ordered list
 277         SplitListSet(
 278             size_t nItemCount           ///< estimate average of item count
 279             , size_t nLoadFactor = 1    ///< load factor - average item count per bucket. Small integer up to 10, default is 1.
 280             )
 281             : m_Buckets( nItemCount, nLoadFactor )
 282             , m_nBucketCountLog2(1)
 283         {
 284             init();
 285         }
 286
 287     public:
 288         /// Inserts new node
 289         /**
 290             The function inserts \p val in the set if it does not contain
 291             an item with key equal to \p val.
 292
 293             Returns \p true if \p val is placed into the set, \p false otherwise.
 294         */
 295         bool insert( value_type& val )
 296         {
 297             return insert_( val ) != end();
 298         }
 299
 300         /// Ensures that the \p item exists in the set
 301         /**
 302             The operation performs inserting or changing data with lock-free manner.
 303
 304             If the item \p val not found in the set, then \p val is inserted into the set.
 305             Otherwise, the functor \p func is called with item found.
 306             The functor signature is:
 307             \code
 308             struct ensure_functor {
 309                 void operator()( bool bNew, value_type& item, value_type& val );
 310             };
 311             \endcode
 312             with arguments:
 313             - \p bNew - \p true if the item has been inserted, \p false otherwise
 314             - \p item - item of the set
 315             - \p val - argument \p val passed into the \p ensure function
 316             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 317             refers to the same thing.
 318
 319             The functor can change non-key fields of the \p item.
 320
 321             Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
 322             \p second is \p true if new item has been added or \p false if the item with given key
 323             already is in the set.
 324
 325             @warning For \ref cds_intrusive_MichaelList_nogc "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
 326             \ref cds_intrusive_LazyList_nogc "LazyList" provides exclusive access to inserted item and does not require any node-level
 327             synchronization.
 328         */
 329         template <typename Func>
 330         std::pair<bool, bool> ensure( value_type& val, Func func )
 331         {
 332             std::pair<iterator, bool> ret = ensure_( val, func );
 333             return std::make_pair( ret.first != end(), ret.second );
 334         }
 335
 336         /// Finds the key \p key
 337         /** \anchor cds_intrusive_SplitListSet_nogc_find_val
 338             The function searches the item with key equal to \p key
 339             and returns pointer to item found or , and \p nullptr otherwise.
 340
 341             Note the hash functor specified for class \p Traits template parameter
 342             should accept a parameter of type \p Q that can be not the same as \p value_type.
 343         */
 344         template <typename Q>
 345         value_type * find( Q const& key )
 346         {
 347             iterator it = find_( key );
 348             if ( it == end() )
 349                 return nullptr;
 350             return &*it;
 351         }
 352
 353         /// Finds the key \p key with \p pred predicate for comparing
 354         /**
 355             The function is an analog of \ref cds_intrusive_SplitListSet_nogc_find_val "find(Q const&)"
 356             but \p cmp is used for key compare.
 357             \p Less has the interface like \p std::less.
 358             \p cmp must imply the same element order as the comparator used for building the set.
 359         */
 360         template <typename Q, typename Less>
 361         value_type * find_with( Q const& key, Less pred )
 362         {
 363             iterator it = find_with_( key, pred );
 364             if ( it == end() )
 365                 return nullptr;
 366             return &*it;
 367         }
 368
 369         /// Finds the key \p key
 370         /** \anchor cds_intrusive_SplitListSet_nogc_find_func
 371             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 372             The interface of \p Func functor is:
 373             \code
 374             struct functor {
 375                 void operator()( value_type& item, Q& key );
 376             };
 377             \endcode
 378             where \p item is the item found, \p key is the <tt>find</tt> function argument.
 379
 380             The functor can change non-key fields of \p item.
 381             The functor does not serialize simultaneous access to the set \p item. If such access is
 382             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
 383
 384             Note the hash functor specified for class \p Traits template parameter
 385             should accept a parameter of type \p Q that can be not the same as \p value_type.
 386
 387             The function returns \p true if \p key is found, \p false otherwise.
 388         */
 389         template <typename Q, typename Func>
 390         bool find( Q& key, Func f )
 391         {
 392             return find_( key, key_comparator(), f );
 393         }
 394         //@cond
 395         template <typename Q, typename Func>
 396         bool find( Q const& key, Func f )
 397         {
 398             return find_( key, key_comparator(), f );
 399         }
 400         //@endcond
 401
 402         /// Finds the key \p key with \p pred predicate for comparing
 403         /**
 404             The function is an analog of \ref cds_intrusive_SplitListSet_nogc_find_func "find(Q&, Func)"
 405             but \p cmp is used for key compare.
 406             \p Less has the interface like \p std::less.
 407             \p cmp must imply the same element order as the comparator used for building the set.
 408         */
 409         template <typename Q, typename Less, typename Func>
 410         bool find_with( Q& key, Less pred, Func f )
 411         {
 412             return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
 413         }
 414         //@cond
 415         template <typename Q, typename Less, typename Func>
 416         bool find_with( Q const& key, Less pred, Func f )
 417         {
 418             return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
 419         }
 420         //@endcond
 421
 422         /// Checks if the set is empty
 423         /**
 424             Emptiness is checked by item counting: if item count is zero then the set is empty.
 425             Thus, the correct item counting feature is an important part of split-list implementation.
 426         */
 427         bool empty() const
 428         {
 429             return size() == 0;
 430         }
 431
 432         /// Returns item count in the set
 433         size_t size() const
 434         {
 435             return m_ItemCounter;
 436         }
 437
 438         /// Returns internal statistics
 439         stat const& statistics() const
 440         {
 441             return m_Stat;
 442         }
 443
 444     protected:
 445         //@cond
 446         template <bool IsConst>
 447         class iterator_type
 448             : public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
 449         {
 450             typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
 451             typedef typename iterator_base_class::list_iterator list_iterator;
 452         public:
 453             iterator_type()
 454                 : iterator_base_class()
 455             {}
 456
 457             iterator_type( iterator_type const& src )
 458                 : iterator_base_class( src )
 459             {}
 460
 461             // This ctor should be protected...
 462             iterator_type( list_iterator itCur, list_iterator itEnd )
 463                 : iterator_base_class( itCur, itEnd )
 464             {}
 465         };
 466         //@endcond
 467
 468     public:
 469         /// Forward iterator
 470         /**
 471             The forward iterator for a split-list has some features:
 472             - it has no post-increment operator
 473             - it depends on iterator of underlying \p OrderedList
 474         */
 475         typedef iterator_type<false>    iterator;
 476         /// Const forward iterator
 477         /**
 478             For iterator's features and requirements see \ref iterator
 479         */
 480         typedef iterator_type<true>     const_iterator;
 481
 482         /// Returns a forward iterator addressing the first element in a split-list
 483         /**
 484             For empty list \code begin() == end() \endcode
 485         */
 486         iterator begin()
 487         {
 488             return iterator( m_List.begin(), m_List.end() );
 489         }
 490
 491         /// Returns an iterator that addresses the location succeeding the last element in a split-list
 492         /**
 493             Do not use the value returned by <tt>end</tt> function to access any item.
 494
 495             The returned value can be used only to control reaching the end of the split-list.
 496             For empty list \code begin() == end() \endcode
 497         */
 498         iterator end()
 499         {
 500             return iterator( m_List.end(), m_List.end() );
 501         }
 502
 503         /// Returns a forward const iterator addressing the first element in a split-list
 504         //@{
 505         const_iterator begin() const
 506         {
 507             return const_iterator( m_List.begin(), m_List.end() );
 508         }
 509         const_iterator cbegin() const
 510         {
 511             return const_iterator( m_List.cbegin(), m_List.cend() );
 512         }
 513         //@}
 514
 515         /// Returns an const iterator that addresses the location succeeding the last element in a split-list
 516         //@{
 517         const_iterator end() const
 518         {
 519             return const_iterator( m_List.end(), m_List.end() );
 520         }
 521         const_iterator cend() const
 522         {
 523             return const_iterator( m_List.cend(), m_List.cend() );
 524         }
 525         //@}
 526
 527     protected:
 528         //@cond
 529         iterator insert_( value_type& val )
 530         {
 531             size_t nHash = hash_value( val );
 532             dummy_node_type * pHead = get_bucket( nHash );
 533             assert( pHead != nullptr );
 534
 535             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
 536
 537             list_iterator it = m_List.insert_at_( pHead, val );
 538             if ( it != m_List.end() ) {
 539                 inc_item_count();
 540                 m_Stat.onInsertSuccess();
 541                 return iterator( it, m_List.end() );
 542             }
 543             m_Stat.onInsertFailed();
 544             return end();
 545         }
 546
 547         template <typename Func>
 548         std::pair<iterator, bool> ensure_( value_type& val, Func func )
 549         {
 550             size_t nHash = hash_value( val );
 551             dummy_node_type * pHead = get_bucket( nHash );
 552             assert( pHead != nullptr );
 553
 554             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
 555
 556             std::pair<list_iterator, bool> ret = m_List.ensure_at_( pHead, val, func );
 557             if ( ret.first != m_List.end() ) {
 558                 if ( ret.second ) {
 559                     inc_item_count();
 560                     m_Stat.onEnsureNew();
 561                 }
 562                 else
 563                     m_Stat.onEnsureExist();
 564                 return std::make_pair( iterator(ret.first, m_List.end()), ret.second );
 565             }
 566             return std::make_pair( end(), ret.second );
 567         }
 568
 569         template <typename Q, typename Less >
 570         iterator find_with_( Q& val, Less pred )
 571         {
 572             size_t nHash = hash_value( val );
 573             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
 574             dummy_node_type * pHead = get_bucket( nHash );
 575             assert( pHead != nullptr );
 576
 577             auto it = m_List.find_at_( pHead, sv, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
 578             m_Stat.onFind( it != m_List.end() );
 579             return iterator( it, m_List.end() );
 580         }
 581
 582         template <typename Q>
 583         iterator find_( Q const& val )
 584         {
 585             size_t nHash = hash_value( val );
 586             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
 587             dummy_node_type * pHead = get_bucket( nHash );
 588             assert( pHead != nullptr );
 589
 590             auto it = m_List.find_at_( pHead, sv, key_comparator() );
 591             m_Stat.onFind( it != m_List.end() );
 592             return iterator( it, m_List.end() );
 593         }
 594
 595         template <typename Q, typename Compare, typename Func>
 596         bool find_( Q& val, Compare cmp, Func f )
 597         {
 598             size_t nHash = hash_value( val );
 599             split_list::details::search_value_type<Q>  sv( val, split_list::regular_hash( nHash ));
 600             dummy_node_type * pHead = get_bucket( nHash );
 601             assert( pHead != nullptr );
 602             return m_Stat.onFind( m_List.find_at( pHead, sv, cmp,
 603                 [&f](value_type& item, split_list::details::search_value_type<Q>& val){ f(item, val.val ); }));
 604         }
 605
 606         //@endcond
 607     };
 608
 609 }} // namespace cds::intrusive
 610
 611 #endif // #ifndef __CDS_INTRUSIVE_SPLIT_LIST_NOGC_H