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