cds/container/michael_kvlist_nogc.h

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