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
 395         /// Finds the key \p key with \p pred predicate for comparing
 396         /**
 397             The function is an analog of \ref cds_intrusive_SplitListSet_nogc_find_func "find(Q&, Func)"
 398             but \p cmp is used for key compare.
 399             \p Less has the interface like \p std::less.
 400             \p cmp must imply the same element order as the comparator used for building the set.
 401         */
 402         template <typename Q, typename Less, typename Func>
 403         bool find_with( Q& key, Less pred, Func f )
 404         {
 405             return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
 406         }
 407
 408         /// Checks if the set is empty
 409         /**
 410             Emptiness is checked by item counting: if item count is zero then the set is empty.
 411             Thus, the correct item counting feature is an important part of split-list implementation.
 412         */
 413         bool empty() const
 414         {
 415             return size() == 0;
 416         }
 417
 418         /// Returns item count in the set
 419         size_t size() const
 420         {
 421             return m_ItemCounter;
 422         }
 423
 424         /// Returns internal statistics
 425         stat const& statistics() const
 426         {
 427             return m_Stat;
 428         }
 429
 430     protected:
 431         //@cond
 432         template <bool IsConst>
 433         class iterator_type
 434             : public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
 435         {
 436             typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
 437             typedef typename iterator_base_class::list_iterator list_iterator;
 438         public:
 439             iterator_type()
 440                 : iterator_base_class()
 441             {}
 442
 443             iterator_type( iterator_type const& src )
 444                 : iterator_base_class( src )
 445             {}
 446
 447             // This ctor should be protected...
 448             iterator_type( list_iterator itCur, list_iterator itEnd )
 449                 : iterator_base_class( itCur, itEnd )
 450             {}
 451         };
 452         //@endcond
 453
 454     public:
 455         /// Forward iterator
 456         /**
 457             The forward iterator for a split-list has some features:
 458             - it has no post-increment operator
 459             - it depends on iterator of underlying \p OrderedList
 460         */
 461         typedef iterator_type<false>    iterator;
 462         /// Const forward iterator
 463         /**
 464             For iterator's features and requirements see \ref iterator
 465         */
 466         typedef iterator_type<true>     const_iterator;
 467
 468         /// Returns a forward iterator addressing the first element in a split-list
 469         /**
 470             For empty list \code begin() == end() \endcode
 471         */
 472         iterator begin()
 473         {
 474             return iterator( m_List.begin(), m_List.end() );
 475         }
 476
 477         /// Returns an iterator that addresses the location succeeding the last element in a split-list
 478         /**
 479             Do not use the value returned by <tt>end</tt> function to access any item.
 480
 481             The returned value can be used only to control reaching the end of the split-list.
 482             For empty list \code begin() == end() \endcode
 483         */
 484         iterator end()
 485         {
 486             return iterator( m_List.end(), m_List.end() );
 487         }
 488
 489         /// Returns a forward const iterator addressing the first element in a split-list
 490         //@{
 491         const_iterator begin() const
 492         {
 493             return const_iterator( m_List.begin(), m_List.end() );
 494         }
 495         const_iterator cbegin()
 496         {
 497             return const_iterator( m_List.cbegin(), m_List.cend() );
 498         }
 499         //@}
 500
 501         /// Returns an const iterator that addresses the location succeeding the last element in a split-list
 502         //@{
 503         const_iterator end() const
 504         {
 505             return const_iterator( m_List.end(), m_List.end() );
 506         }
 507         const_iterator cend()
 508         {
 509             return const_iterator( m_List.cend(), m_List.cend() );
 510         }
 511         //@}
 512
 513     protected:
 514         //@cond
 515         iterator insert_( value_type& val )
 516         {
 517             size_t nHash = hash_value( val );
 518             dummy_node_type * pHead = get_bucket( nHash );
 519             assert( pHead != nullptr );
 520
 521             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
 522
 523             list_iterator it = m_List.insert_at_( pHead, val );
 524             if ( it != m_List.end() ) {
 525                 inc_item_count();
 526                 m_Stat.onInsertSuccess();
 527                 return iterator( it, m_List.end() );
 528             }
 529             m_Stat.onInsertFailed();
 530             return end();
 531         }
 532
 533         template <typename Func>
 534         std::pair<iterator, bool> ensure_( value_type& val, Func func )
 535         {
 536             size_t nHash = hash_value( val );
 537             dummy_node_type * pHead = get_bucket( nHash );
 538             assert( pHead != nullptr );
 539
 540             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
 541
 542             std::pair<list_iterator, bool> ret = m_List.ensure_at_( pHead, val, func );
 543             if ( ret.first != m_List.end() ) {
 544                 if ( ret.second ) {
 545                     inc_item_count();
 546                     m_Stat.onEnsureNew();
 547                 }
 548                 else
 549                     m_Stat.onEnsureExist();
 550                 return std::make_pair( iterator(ret.first, m_List.end()), ret.second );
 551             }
 552             return std::make_pair( end(), ret.second );
 553         }
 554
 555         template <typename Q, typename Less >
 556         iterator find_with_( Q& val, Less pred )
 557         {
 558             size_t nHash = hash_value( val );
 559             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
 560             dummy_node_type * pHead = get_bucket( nHash );
 561             assert( pHead != nullptr );
 562
 563             auto it = m_List.find_at_( pHead, sv, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
 564             m_Stat.onFind( it != m_List.end() );
 565             return iterator( it, m_List.end() );
 566         }
 567
 568         template <typename Q>
 569         iterator find_( Q const& val )
 570         {
 571             size_t nHash = hash_value( val );
 572             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
 573             dummy_node_type * pHead = get_bucket( nHash );
 574             assert( pHead != nullptr );
 575
 576             auto it = m_List.find_at_( pHead, sv, key_comparator() );
 577             m_Stat.onFind( it != m_List.end() );
 578             return iterator( it, m_List.end() );
 579         }
 580
 581         template <typename Q, typename Compare, typename Func>
 582         bool find_( Q& val, Compare cmp, Func f )
 583         {
 584             size_t nHash = hash_value( val );
 585             split_list::details::search_value_type<Q>  sv( val, split_list::regular_hash( nHash ));
 586             dummy_node_type * pHead = get_bucket( nHash );
 587             assert( pHead != nullptr );
 588             return m_Stat.onFind( m_List.find_at( pHead, sv, cmp,
 589                 [&f](value_type& item, split_list::details::search_value_type<Q>& val){ f(item, val.val ); }));
 590         }
 591
 592         //@endcond
 593     };
 594
 595 }} // namespace cds::intrusive
 596
 597 #endif // #ifndef __CDS_INTRUSIVE_SPLIT_LIST_NOGC_H