cds/container/lazy_kvlist_nogc.h

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