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