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