cds/intrusive/split_list_nogc.h

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