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