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         template <typename K, typename... Args>
 146         static node_type * alloc_node( K&& key, Args&&... args )
 147         {
 148             return cxx_allocator().MoveNew( std::forward<K>(key), std::forward<Args>(args)... );
 149         }
 150
 151         static void free_node( node_type * pNode )
 152         {
 153             cxx_allocator().Delete( pNode );
 154         }
 155
 156         struct node_disposer {
 157             void operator()( node_type * pNode )
 158             {
 159                 free_node( pNode );
 160             }
 161         };
 162         typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
 163
 164         head_type& head()
 165         {
 166             return base_class::m_pHead;
 167         }
 168
 169         head_type const& head() const
 170         {
 171             return base_class::m_pHead;
 172         }
 173         //@endcond
 174
 175     protected:
 176         //@cond
 177         template <bool IsConst>
 178         class iterator_type: protected base_class::template iterator_type<IsConst>
 179         {
 180             typedef typename base_class::template iterator_type<IsConst>    iterator_base;
 181
 182             iterator_type( head_type const& refNode )
 183                 : iterator_base( refNode )
 184             {}
 185
 186             explicit iterator_type( const iterator_base& it )
 187                 : iterator_base( it )
 188             {}
 189
 190             friend class MichaelKVList;
 191
 192         protected:
 193             explicit iterator_type( node_type& pNode )
 194                 : iterator_base( &pNode )
 195             {}
 196
 197         public:
 198             typedef typename cds::details::make_const_type<mapped_type, IsConst>::reference  value_ref;
 199             typedef typename cds::details::make_const_type<mapped_type, IsConst>::pointer    value_ptr;
 200
 201             typedef typename cds::details::make_const_type<value_type,  IsConst>::reference  pair_ref;
 202             typedef typename cds::details::make_const_type<value_type,  IsConst>::pointer    pair_ptr;
 203
 204             iterator_type()
 205                 : iterator_base()
 206             {}
 207
 208             iterator_type( const iterator_type& src )
 209                 : iterator_base( src )
 210             {}
 211
 212             key_type const& key() const
 213             {
 214                 typename iterator_base::value_ptr p = iterator_base::operator ->();
 215                 assert( p != nullptr );
 216                 return p->m_Data.first;
 217             }
 218
 219             value_ref val() const
 220             {
 221                 typename iterator_base::value_ptr p = iterator_base::operator ->();
 222                 assert( p != nullptr );
 223                 return p->m_Data.second;
 224             }
 225
 226             pair_ptr operator ->() const
 227             {
 228                 typename iterator_base::value_ptr p = iterator_base::operator ->();
 229                 return p ? &(p->m_Data) : nullptr;
 230             }
 231
 232             pair_ref operator *() const
 233             {
 234                 typename iterator_base::value_ref p = iterator_base::operator *();
 235                 return p.m_Data;
 236             }
 237
 238             /// Pre-increment
 239             iterator_type& operator ++()
 240             {
 241                 iterator_base::operator ++();
 242                 return *this;
 243             }
 244
 245             /// Post-increment
 246             iterator_type operator ++(int)
 247             {
 248                 return iterator_base::operator ++(0);
 249             }
 250
 251             template <bool C>
 252             bool operator ==(iterator_type<C> const& i ) const
 253             {
 254                 return iterator_base::operator ==(i);
 255             }
 256             template <bool C>
 257             bool operator !=(iterator_type<C> const& i ) const
 258             {
 259                 return iterator_base::operator !=(i);
 260             }
 261         };
 262         //@endcond
 263
 264     public:
 265         /// Forward iterator
 266         /**
 267             The forward iterator for Michael's list based on gc::nogc has pre- and post-increment operators.
 268
 269             The iterator interface to access item data:
 270             - <tt> operator -> </tt> - returns a pointer to \ref value_type for iterator
 271             - <tt> operator *</tt> - returns a reference (a const reference for \p const_iterator) to \ref value_type for iterator
 272             - <tt> const key_type& key() </tt> - returns a key reference for iterator
 273             - <tt> mapped_type& val() </tt> - retuns a value reference for iterator (const reference for \p const_iterator)
 274
 275             For both functions the iterator should not be equal to <tt> end() </tt>
 276         */
 277         typedef iterator_type<false>    iterator;
 278
 279         /// Const forward iterator
 280         /**
 281             For iterator's features and requirements see \ref iterator
 282         */
 283         typedef iterator_type<true>     const_iterator;
 284
 285         /// Returns a forward iterator addressing the first element in a list
 286         /**
 287             For empty list \code begin() == end() \endcode
 288         */
 289         iterator begin()
 290         {
 291             return iterator( head() );
 292         }
 293
 294         /// Returns an iterator that addresses the location succeeding the last element in a list
 295         /**
 296             Do not use the value returned by <tt>end</tt> function to access any item.
 297             Internally, <tt>end</tt> returning value equals to \p nullptr.
 298
 299             The returned value can be used only to control reaching the end of the list.
 300             For empty list \code begin() == end() \endcode
 301         */
 302         iterator end()
 303         {
 304             return iterator();
 305         }
 306
 307         /// Returns a forward const iterator addressing the first element in a list
 308         //@{
 309         const_iterator begin() const
 310         {
 311             return const_iterator( head() );
 312         }
 313         const_iterator cbegin()
 314         {
 315             return const_iterator( head() );
 316         }
 317         //@}
 318
 319         /// Returns an const iterator that addresses the location succeeding the last element in a list
 320         //@{
 321         const_iterator end() const
 322         {
 323             return const_iterator();
 324         }
 325         const_iterator cend()
 326         {
 327             return const_iterator();
 328         }
 329         //@}
 330
 331     protected:
 332         //@cond
 333         iterator node_to_iterator( node_type * pNode )
 334         {
 335             if ( pNode )
 336                 return iterator( *pNode );
 337             return end();
 338         }
 339         //@endcond
 340
 341     public:
 342         /// Default constructor
 343         /**
 344             Initialize empty list
 345         */
 346         MichaelKVList()
 347         {}
 348
 349         /// List desctructor
 350         /**
 351             Clears the list
 352         */
 353         ~MichaelKVList()
 354         {
 355             clear();
 356         }
 357
 358         /// Inserts new node with key and default value
 359         /**
 360             The function creates a node with \p key and default value, and then inserts the node created into the list.
 361
 362             Preconditions:
 363             - The \ref key_type should be constructible from value of type \p K.
 364                 In trivial case, \p K is equal to \ref key_type.
 365             - The \ref mapped_type should be default-constructible.
 366
 367             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 368         */
 369         template <typename K>
 370         iterator insert( const K& key )
 371         {
 372             return node_to_iterator( insert_at( head(), key ));
 373         }
 374
 375         /// Inserts new node with a key and a value
 376         /**
 377             The function creates a node with \p key and value \p val, and then inserts the node created into the list.
 378
 379             Preconditions:
 380             - The \ref key_type should be constructible from \p key of type \p K.
 381             - The \ref mapped_type should be constructible from \p val of type \p V.
 382
 383             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 384         */
 385         template <typename K, typename V>
 386         iterator insert( const K& key, const V& val )
 387         {
 388             // We cannot use insert with functor here
 389             // because we cannot lock inserted node for updating
 390             // Therefore, we use separate function
 391             return node_to_iterator( insert_at( head(), key, val ));
 392         }
 393
 394         /// Inserts new node and initialize it by a functor
 395         /**
 396             This function inserts new node with key \p key and if inserting is successful then it calls
 397             \p func functor with signature
 398             \code void func( value_type& item );
 399                 struct functor {
 400                     void operator()( value_type& item );
 401                 };
 402             \endcode
 403
 404             The argument \p item of user-defined functor \p func is the reference
 405             to the list's item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
 406             User-defined functor \p func should guarantee that during changing item's value no any other changes
 407             could be made on this list's item by concurrent threads.
 408             The user-defined functor can be passed by reference using <tt>boost::ref</tt>
 409             and it is called only if the inserting is successful.
 410
 411             The key_type should be constructible from value of type \p K.
 412
 413             The function allows to split creating of new item into two part:
 414             - create item from \p key;
 415             - insert new item into the list;
 416             - if inserting is successful, initialize the value of item by calling \p f functor
 417
 418             This can be useful if complete initialization of object of \p mapped_type is heavyweight and
 419             it is preferable that the initialization should be completed only if inserting is successful.
 420
 421             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 422         */
 423         template <typename K, typename Func>
 424         iterator insert_key( const K& key, Func func )
 425         {
 426             return node_to_iterator( insert_key_at( head(), key, func ));
 427         }
 428
 429         /// Ensures that the key \p key exists in the list
 430         /**
 431             The operation inserts new item if the key \p key is not found in the list.
 432             Otherwise, the function returns an iterator that points to item found.
 433
 434             Returns <tt> std::pair<iterator, bool>  </tt> where \p first is an iterator pointing to
 435             item found or inserted, \p second is true if new item has been added or \p false if the item
 436             already is in the list.
 437         */
 438         template <typename K>
 439         std::pair<iterator, bool> ensure( const K& key )
 440         {
 441             std::pair< node_type *, bool > ret = ensure_at( head(), key );
 442             return std::make_pair( node_to_iterator( ret.first ), ret.second );
 443         }
 444
 445         /// Inserts data of type \ref mapped_type constructed with <tt>std::forward<Args>(args)...</tt>
 446         /**
 447             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 448         */
 449         template <typename K, typename... Args>
 450         iterator emplace( K&& key, Args&&... args )
 451         {
 452             return node_to_iterator( emplace_at( head(), std::forward<K>(key), std::forward<Args>(args)... ));
 453         }
 454
 455         /// Find the key \p key
 456         /** \anchor cds_nonintrusive_MichaelKVList_nogc_find
 457
 458             The function searches the item with key equal to \p key
 459             and returns an iterator pointed to item found if the key is found,
 460             and \ref end() otherwise
 461         */
 462         template <typename Q>
 463         iterator find( Q const& key )
 464         {
 465             return node_to_iterator( find_at( head(), key, intrusive_key_comparator() ) );
 466         }
 467
 468         /// Finds the key \p val using \p pred predicate for searching
 469         /**
 470             The function is an analog of \ref cds_nonintrusive_MichaelKVList_nogc_find "find(Q const&)"
 471             but \p pred is used for key comparing.
 472             \p Less functor has the interface like \p std::less.
 473             \p pred must imply the same element order as the comparator used for building the list.
 474         */
 475         template <typename Q, typename Less>
 476         iterator find_with( Q const& key, Less pred )
 477         {
 478             return node_to_iterator( find_at( head(), key, typename options::template less_wrapper<Less>::type() ) );
 479         }
 480
 481         /// Check if the list is empty
 482         bool empty() const
 483         {
 484             return base_class::empty();
 485         }
 486
 487         /// Returns list's item count
 488         /**
 489             The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
 490             this function always returns 0.
 491
 492             <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
 493             is empty. To check list emptyness use \ref empty() method.
 494         */
 495         size_t size() const
 496         {
 497             return base_class::size();
 498         }
 499
 500         /// Clears the list
 501         /**
 502             Post-condition: the list is empty
 503         */
 504         void clear()
 505         {
 506             base_class::clear();
 507         }
 508
 509     protected:
 510         //@cond
 511         node_type * insert_node_at( head_type& refHead, node_type * pNode )
 512         {
 513             assert( pNode != nullptr );
 514             scoped_node_ptr p( pNode );
 515             if ( base_class::insert_at( refHead, *pNode ))
 516                 return p.release();
 517             return nullptr;
 518         }
 519
 520         template <typename K>
 521         node_type * insert_at( head_type& refHead, const K& key )
 522         {
 523             return insert_node_at( refHead, alloc_node( key ));
 524         }
 525
 526         template <typename K, typename V>
 527         node_type * insert_at( head_type& refHead, const K& key, const V& val )
 528         {
 529             return insert_node_at( refHead, alloc_node( key, val ));
 530         }
 531
 532         template <typename K, typename Func>
 533         node_type * insert_key_at( head_type& refHead, const K& key, Func f )
 534         {
 535             scoped_node_ptr pNode( alloc_node( key ));
 536
 537             if ( base_class::insert_at( refHead, *pNode )) {
 538                 cds::unref(f)( pNode->m_Data );
 539                 return pNode.release();
 540             }
 541             return nullptr;
 542         }
 543
 544         template <typename K>
 545         std::pair< node_type *, bool > ensure_at( head_type& refHead, const K& key )
 546         {
 547             scoped_node_ptr pNode( alloc_node( key ));
 548             node_type * pItemFound = nullptr;
 549
 550 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 551             std::pair<bool, bool> ret = base_class::ensure_at( refHead, *pNode, [&pItemFound](bool, node_type& item, node_type&){ pItemFound = &item; });
 552 #       else
 553             ensure_functor func;
 554             std::pair<bool, bool> ret = base_class::ensure_at( refHead, *pNode, boost::ref(func) );
 555             pItemFound = func.m_pItemFound;
 556 #       endif
 557             assert( pItemFound != nullptr );
 558
 559             if ( ret.first && ret.second )
 560                 pNode.release();
 561             return std::make_pair( pItemFound, ret.second );
 562         }
 563
 564         template <typename K, typename... Args>
 565         node_type * emplace_at( head_type& refHead, K&& key, Args&&... args )
 566         {
 567             return insert_node_at( refHead, alloc_node( std::forward<K>(key), std::forward<Args>(args)... ));
 568         }
 569
 570         template <typename K, typename Compare>
 571         node_type * find_at( head_type& refHead, K const& key, Compare cmp )
 572         {
 573             return base_class::find_at( refHead, key, cmp );
 574         }
 575
 576         /*
 577         template <typename K, typename Compare typename Func>
 578         bool find_at( head_type& refHead, K& key, Compare cmp, Func f )
 579         {
 580 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 581             return base_class::find_at( refHead, key, cmp, [&f]( node_type& node, K const& ){ cds::unref(f)( node.m_Data ); });
 582 #       else
 583             find_functor<Func>  wrapper( f );
 584             return base_class::find_at( refHead, key, cmp, cds::ref(wrapper) );
 585 #       endif
 586         }
 587         */
 588         //@endcond
 589     };
 590
 591 }} // namespace cds::container
 592
 593 #endif // #ifndef __CDS_CONTAINER_MICHAEL_KVLIST_NOGC_H