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