cds/container/lazy_kvlist_nogc.h

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