cds/container/michael_kvlist_nogc.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_CONTAINER_MICHAEL_KVLIST_NOGC_H
   4 #define __CDS_CONTAINER_MICHAEL_KVLIST_NOGC_H
   5
   6 #include <memory>
   7 #include <cds/container/michael_list_base.h>
   8 #include <cds/intrusive/michael_list_nogc.h>
   9 #include <cds/container/details/make_michael_kvlist.h>
  10 #include <cds/details/functor_wrapper.h>
  11
  12 namespace cds { namespace container {
  13
  14     //@cond
  15     namespace details {
  16
  17         template <typename K, typename T, class Traits>
  18         struct make_michael_kvlist_nogc: public make_michael_kvlist<gc::nogc, K, T, Traits>
  19         {
  20             typedef make_michael_kvlist<cds::gc::nogc, K, T, Traits>  base_maker;
  21             typedef typename base_maker::node_type node_type;
  22
  23             struct type_traits: public base_maker::type_traits
  24             {
  25                 typedef typename base_maker::node_deallocator    disposer;
  26             };
  27
  28             typedef intrusive::MichaelList<cds::gc::nogc, node_type, type_traits>  type;
  29         };
  30
  31     }   // namespace details
  32     //@endcond
  33
  34     /// Michael's ordered list (key-value pair, template specialization for gc::nogc)
  35     /** @ingroup cds_nonintrusive_list
  36
  37         This specialization is intended for so-called persistent usage when no item
  38         reclamation may be performed. The class does not support deleting of list item.
  39
  40         Usually, ordered single-linked list is used as a building block for the hash table implementation.
  41         The complexity of searching is <tt>O(N)</tt>.
  42
  43         See \ref cds_nonintrusive_MichaelList_gc "MichaelList" for description of template parameters.
  44
  45         The interface of the specialization is a little different.
  46     */
  47     template <
  48         typename Key,
  49         typename Value,
  50 #ifdef CDS_DOXYGEN_INVOKED
  51         typename Traits = michael_list::type_traits
  52 #else
  53         typename Traits
  54 #endif
  55     >
  56     class MichaelKVList<gc::nogc, Key, Value, Traits>:
  57 #ifdef CDS_DOXYGEN_INVOKED
  58         protected intrusive::MichaelList< gc::nogc, implementation_defined, Traits >
  59 #else
  60         protected details::make_michael_kvlist_nogc< Key, Value, Traits >::type
  61 #endif
  62     {
  63         //@cond
  64         typedef details::make_michael_kvlist_nogc< Key, Value, Traits > options;
  65         typedef typename options::type  base_class;
  66         //@endcond
  67
  68     public:
  69 #ifdef CDS_DOXYGEN_INVOKED
  70         typedef Key                                 key_type        ;   ///< Key type
  71         typedef Value                               mapped_type     ;   ///< Type of value stored in the list
  72         typedef std::pair<key_type const, mapped_type> value_type   ;   ///< key/value pair stored in the list
  73 #else
  74         typedef typename options::key_type          key_type;
  75         typedef typename options::value_type        mapped_type;
  76         typedef typename options::pair_type         value_type;
  77 #endif
  78
  79         typedef typename base_class::gc             gc              ;   ///< Garbage collector used
  80         typedef typename base_class::back_off       back_off        ;   ///< Back-off strategy used
  81         typedef typename options::allocator_type    allocator_type  ;   ///< Allocator type used for allocate/deallocate the nodes
  82         typedef typename base_class::item_counter   item_counter    ;   ///< Item counting policy used
  83         typedef typename options::key_comparator    key_comparator  ;   ///< key comparison functor
  84         typedef typename base_class::memory_model   memory_model    ;   ///< Memory ordering. See cds::opt::memory_model option
  85
  86     protected:
  87         //@cond
  88         typedef typename base_class::value_type     node_type;
  89         typedef typename options::cxx_allocator     cxx_allocator;
  90         typedef typename options::node_deallocator  node_deallocator;
  91         typedef typename options::type_traits::compare  intrusive_key_comparator;
  92
  93         typedef typename base_class::atomic_node_ptr head_type;
  94         //@endcond
  95
  96     private:
  97         //@cond
  98 #   ifndef CDS_CXX11_LAMBDA_SUPPORT
  99         struct ensure_functor
 100         {
 101             node_type * m_pItemFound;
 102
 103             ensure_functor()
 104                 : m_pItemFound( nullptr )
 105             {}
 106
 107             void operator ()(bool, node_type& item, node_type& )
 108             {
 109                 m_pItemFound = &item;
 110             }
 111         };
 112
 113         template <typename Func>
 114         class find_functor: protected cds::details::functor_wrapper<Func>
 115         {
 116             typedef cds::details::functor_wrapper<Func> base_class;
 117         public:
 118             find_functor( Func f )
 119                 : base_class(f)
 120             {}
 121
 122             template <typename Q>
 123             void operator ()( node_type& node, Q&  )
 124             {
 125                 base_class::get()( node.m_Data );
 126             }
 127         };
 128 #   endif
 129         //@endcond
 130
 131     protected:
 132         //@cond
 133         template <typename K>
 134         static node_type * alloc_node(const K& key)
 135         {
 136             return cxx_allocator().New( key );
 137         }
 138
 139         template <typename K, typename V>
 140         static node_type * alloc_node( const K& key, const V& val )
 141         {
 142             return cxx_allocator().New( key, val );
 143         }
 144
 145 #ifdef CDS_EMPLACE_SUPPORT
 146         template <typename K, typename... Args>
 147         static node_type * alloc_node( K&& key, Args&&... args )
 148         {
 149             return cxx_allocator().MoveNew( std::forward<K>(key), std::forward<Args>(args)... );
 150         }
 151 #endif
 152
 153         static void free_node( node_type * pNode )
 154         {
 155             cxx_allocator().Delete( pNode );
 156         }
 157
 158         struct node_disposer {
 159             void operator()( node_type * pNode )
 160             {
 161                 free_node( pNode );
 162             }
 163         };
 164         typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
 165
 166         head_type& head()
 167         {
 168             return base_class::m_pHead;
 169         }
 170
 171         head_type const& head() const
 172         {
 173             return base_class::m_pHead;
 174         }
 175         //@endcond
 176
 177     protected:
 178         //@cond
 179         template <bool IsConst>
 180         class iterator_type: protected base_class::template iterator_type<IsConst>
 181         {
 182             typedef typename base_class::template iterator_type<IsConst>    iterator_base;
 183
 184             iterator_type( head_type const& refNode )
 185                 : iterator_base( refNode )
 186             {}
 187
 188             explicit iterator_type( const iterator_base& it )
 189                 : iterator_base( it )
 190             {}
 191
 192             friend class MichaelKVList;
 193
 194         protected:
 195             explicit iterator_type( node_type& pNode )
 196                 : iterator_base( &pNode )
 197             {}
 198
 199         public:
 200             typedef typename cds::details::make_const_type<mapped_type, IsConst>::reference  value_ref;
 201             typedef typename cds::details::make_const_type<mapped_type, IsConst>::pointer    value_ptr;
 202
 203             typedef typename cds::details::make_const_type<value_type,  IsConst>::reference  pair_ref;
 204             typedef typename cds::details::make_const_type<value_type,  IsConst>::pointer    pair_ptr;
 205
 206             iterator_type()
 207                 : iterator_base()
 208             {}
 209
 210             iterator_type( const iterator_type& src )
 211                 : iterator_base( src )
 212             {}
 213
 214             key_type const& key() const
 215             {
 216                 typename iterator_base::value_ptr p = iterator_base::operator ->();
 217                 assert( p != nullptr );
 218                 return p->m_Data.first;
 219             }
 220
 221             value_ref val() const
 222             {
 223                 typename iterator_base::value_ptr p = iterator_base::operator ->();
 224                 assert( p != nullptr );
 225                 return p->m_Data.second;
 226             }
 227
 228             pair_ptr operator ->() const
 229             {
 230                 typename iterator_base::value_ptr p = iterator_base::operator ->();
 231                 return p ? &(p->m_Data) : nullptr;
 232             }
 233
 234             pair_ref operator *() const
 235             {
 236                 typename iterator_base::value_ref p = iterator_base::operator *();
 237                 return p.m_Data;
 238             }
 239
 240             /// Pre-increment
 241             iterator_type& operator ++()
 242             {
 243                 iterator_base::operator ++();
 244                 return *this;
 245             }
 246
 247             /// Post-increment
 248             iterator_type operator ++(int)
 249             {
 250                 return iterator_base::operator ++(0);
 251             }
 252
 253             template <bool C>
 254             bool operator ==(iterator_type<C> const& i ) const
 255             {
 256                 return iterator_base::operator ==(i);
 257             }
 258             template <bool C>
 259             bool operator !=(iterator_type<C> const& i ) const
 260             {
 261                 return iterator_base::operator !=(i);
 262             }
 263         };
 264         //@endcond
 265
 266     public:
 267         /// Forward iterator
 268         /**
 269             The forward iterator for Michael's list based on gc::nogc has pre- and post-increment operators.
 270
 271             The iterator interface to access item data:
 272             - <tt> operator -> </tt> - returns a pointer to \ref value_type for iterator
 273             - <tt> operator *</tt> - returns a reference (a const reference for \p const_iterator) to \ref value_type for iterator
 274             - <tt> const key_type& key() </tt> - returns a key reference for iterator
 275             - <tt> mapped_type& val() </tt> - retuns a value reference for iterator (const reference for \p const_iterator)
 276
 277             For both functions the iterator should not be equal to <tt> end() </tt>
 278         */
 279         typedef iterator_type<false>    iterator;
 280
 281         /// Const forward iterator
 282         /**
 283             For iterator's features and requirements see \ref iterator
 284         */
 285         typedef iterator_type<true>     const_iterator;
 286
 287         /// Returns a forward iterator addressing the first element in a list
 288         /**
 289             For empty list \code begin() == end() \endcode
 290         */
 291         iterator begin()
 292         {
 293             return iterator( head() );
 294         }
 295
 296         /// Returns an iterator that addresses the location succeeding the last element in a list
 297         /**
 298             Do not use the value returned by <tt>end</tt> function to access any item.
 299             Internally, <tt>end</tt> returning value equals to <tt>NULL</tt>.
 300
 301             The returned value can be used only to control reaching the end of the list.
 302             For empty list \code begin() == end() \endcode
 303         */
 304         iterator end()
 305         {
 306             return iterator();
 307         }
 308
 309         /// Returns a forward const iterator addressing the first element in a list
 310         //@{
 311         const_iterator begin() const
 312         {
 313             return const_iterator( head() );
 314         }
 315         const_iterator cbegin()
 316         {
 317             return const_iterator( head() );
 318         }
 319         //@}
 320
 321         /// Returns an const iterator that addresses the location succeeding the last element in a list
 322         //@{
 323         const_iterator end() const
 324         {
 325             return const_iterator();
 326         }
 327         const_iterator cend()
 328         {
 329             return const_iterator();
 330         }
 331         //@}
 332
 333     protected:
 334         //@cond
 335         iterator node_to_iterator( node_type * pNode )
 336         {
 337             if ( pNode )
 338                 return iterator( *pNode );
 339             return end();
 340         }
 341         //@endcond
 342
 343     public:
 344         /// Default constructor
 345         /**
 346             Initialize empty list
 347         */
 348         MichaelKVList()
 349         {}
 350
 351         /// List desctructor
 352         /**
 353             Clears the list
 354         */
 355         ~MichaelKVList()
 356         {
 357             clear();
 358         }
 359
 360         /// Inserts new node with key and default value
 361         /**
 362             The function creates a node with \p key and default value, and then inserts the node created into the list.
 363
 364             Preconditions:
 365             - The \ref key_type should be constructible from value of type \p K.
 366                 In trivial case, \p K is equal to \ref key_type.
 367             - The \ref mapped_type should be default-constructible.
 368
 369             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 370         */
 371         template <typename K>
 372         iterator insert( const K& key )
 373         {
 374             return node_to_iterator( insert_at( head(), key ));
 375         }
 376
 377         /// Inserts new node with a key and a value
 378         /**
 379             The function creates a node with \p key and value \p val, and then inserts the node created into the list.
 380
 381             Preconditions:
 382             - The \ref key_type should be constructible from \p key of type \p K.
 383             - The \ref mapped_type should be constructible from \p val of type \p V.
 384
 385             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 386         */
 387         template <typename K, typename V>
 388         iterator insert( const K& key, const V& val )
 389         {
 390             // We cannot use insert with functor here
 391             // because we cannot lock inserted node for updating
 392             // Therefore, we use separate function
 393             return node_to_iterator( insert_at( head(), key, val ));
 394         }
 395
 396         /// Inserts new node and initialize it by a functor
 397         /**
 398             This function inserts new node with key \p key and if inserting is successful then it calls
 399             \p func functor with signature
 400             \code void func( value_type& item );
 401                 struct functor {
 402                     void operator()( value_type& item );
 403                 };
 404             \endcode
 405
 406             The argument \p item of user-defined functor \p func is the reference
 407             to the list's item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
 408             User-defined functor \p func should guarantee that during changing item's value no any other changes
 409             could be made on this list's item by concurrent threads.
 410             The user-defined functor can be passed by reference using <tt>boost::ref</tt>
 411             and it is called only if the inserting is successful.
 412
 413             The key_type should be constructible from value of type \p K.
 414
 415             The function allows to split creating of new item into two part:
 416             - create item from \p key;
 417             - insert new item into the list;
 418             - if inserting is successful, initialize the value of item by calling \p f functor
 419
 420             This can be useful if complete initialization of object of \p mapped_type is heavyweight and
 421             it is preferable that the initialization should be completed only if inserting is successful.
 422
 423             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 424         */
 425         template <typename K, typename Func>
 426         iterator insert_key( const K& key, Func func )
 427         {
 428             return node_to_iterator( insert_key_at( head(), key, func ));
 429         }
 430
 431         /// Ensures that the key \p key exists in the list
 432         /**
 433             The operation inserts new item if the key \p key is not found in the list.
 434             Otherwise, the function returns an iterator that points to item found.
 435
 436             Returns <tt> std::pair<iterator, bool>  </tt> where \p first is an iterator pointing to
 437             item found or inserted, \p second is true if new item has been added or \p false if the item
 438             already is in the list.
 439         */
 440         template <typename K>
 441         std::pair<iterator, bool> ensure( const K& key )
 442         {
 443             std::pair< node_type *, bool > ret = ensure_at( head(), key );
 444             return std::make_pair( node_to_iterator( ret.first ), ret.second );
 445         }
 446
 447 #   ifdef CDS_EMPLACE_SUPPORT
 448         /// Inserts data of type \ref mapped_type constructed with <tt>std::forward<Args>(args)...</tt>
 449         /**
 450             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 451
 452             This function is available only for compiler that supports
 453             variadic template and move semantics
 454         */
 455         template <typename K, typename... Args>
 456         iterator emplace( K&& key, Args&&... args )
 457         {
 458             return node_to_iterator( emplace_at( head(), std::forward<K>(key), std::forward<Args>(args)... ));
 459         }
 460 #   endif
 461
 462         /// Find the key \p key
 463         /** \anchor cds_nonintrusive_MichaelKVList_nogc_find
 464
 465             The function searches the item with key equal to \p key
 466             and returns an iterator pointed to item found if the key is found,
 467             and \ref end() otherwise
 468         */
 469         template <typename Q>
 470         iterator find( Q const& key )
 471         {
 472             return node_to_iterator( find_at( head(), key, intrusive_key_comparator() ) );
 473         }
 474
 475         /// Finds the key \p val using \p pred predicate for searching
 476         /**
 477             The function is an analog of \ref cds_nonintrusive_MichaelKVList_nogc_find "find(Q const&)"
 478             but \p pred is used for key comparing.
 479             \p Less functor has the interface like \p std::less.
 480             \p pred must imply the same element order as the comparator used for building the list.
 481         */
 482         template <typename Q, typename Less>
 483         iterator find_with( Q const& key, Less pred )
 484         {
 485             return node_to_iterator( find_at( head(), key, typename options::template less_wrapper<Less>::type() ) );
 486         }
 487
 488         /// Check if the list is empty
 489         bool empty() const
 490         {
 491             return base_class::empty();
 492         }
 493
 494         /// Returns list's item count
 495         /**
 496             The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
 497             this function always returns 0.
 498
 499             <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
 500             is empty. To check list emptyness use \ref empty() method.
 501         */
 502         size_t size() const
 503         {
 504             return base_class::size();
 505         }
 506
 507         /// Clears the list
 508         /**
 509             Post-condition: the list is empty
 510         */
 511         void clear()
 512         {
 513             base_class::clear();
 514         }
 515
 516     protected:
 517         //@cond
 518         node_type * insert_node_at( head_type& refHead, node_type * pNode )
 519         {
 520             assert( pNode != nullptr );
 521             scoped_node_ptr p( pNode );
 522             if ( base_class::insert_at( refHead, *pNode ))
 523                 return p.release();
 524             return nullptr;
 525         }
 526
 527         template <typename K>
 528         node_type * insert_at( head_type& refHead, const K& key )
 529         {
 530             return insert_node_at( refHead, alloc_node( key ));
 531         }
 532
 533         template <typename K, typename V>
 534         node_type * insert_at( head_type& refHead, const K& key, const V& val )
 535         {
 536             return insert_node_at( refHead, alloc_node( key, val ));
 537         }
 538
 539         template <typename K, typename Func>
 540         node_type * insert_key_at( head_type& refHead, const K& key, Func f )
 541         {
 542             scoped_node_ptr pNode( alloc_node( key ));
 543
 544             if ( base_class::insert_at( refHead, *pNode )) {
 545                 cds::unref(f)( pNode->m_Data );
 546                 return pNode.release();
 547             }
 548             return nullptr;
 549         }
 550
 551         template <typename K>
 552         std::pair< node_type *, bool > ensure_at( head_type& refHead, const K& key )
 553         {
 554             scoped_node_ptr pNode( alloc_node( key ));
 555             node_type * pItemFound = nullptr;
 556
 557 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 558             std::pair<bool, bool> ret = base_class::ensure_at( refHead, *pNode, [&pItemFound](bool, node_type& item, node_type&){ pItemFound = &item; });
 559 #       else
 560             ensure_functor func;
 561             std::pair<bool, bool> ret = base_class::ensure_at( refHead, *pNode, boost::ref(func) );
 562             pItemFound = func.m_pItemFound;
 563 #       endif
 564             assert( pItemFound != nullptr );
 565
 566             if ( ret.first && ret.second )
 567                 pNode.release();
 568             return std::make_pair( pItemFound, ret.second );
 569         }
 570
 571 #   ifdef CDS_EMPLACE_SUPPORT
 572         template <typename K, typename... Args>
 573         node_type * emplace_at( head_type& refHead, K&& key, Args&&... args )
 574         {
 575             return insert_node_at( refHead, alloc_node( std::forward<K>(key), std::forward<Args>(args)... ));
 576         }
 577 #endif
 578
 579         template <typename K, typename Compare>
 580         node_type * find_at( head_type& refHead, K const& key, Compare cmp )
 581         {
 582             return base_class::find_at( refHead, key, cmp );
 583         }
 584
 585         /*
 586         template <typename K, typename Compare typename Func>
 587         bool find_at( head_type& refHead, K& key, Compare cmp, Func f )
 588         {
 589 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 590             return base_class::find_at( refHead, key, cmp, [&f]( node_type& node, K const& ){ cds::unref(f)( node.m_Data ); });
 591 #       else
 592             find_functor<Func>  wrapper( f );
 593             return base_class::find_at( refHead, key, cmp, cds::ref(wrapper) );
 594 #       endif
 595         }
 596         */
 597         //@endcond
 598     };
 599
 600 }} // namespace cds::container
 601
 602 #endif // #ifndef __CDS_CONTAINER_MICHAEL_KVLIST_NOGC_H