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
 382             the function inserts a new item.
 383             Otherwise, the function returns an iterator pointing to the item found.
 384
 385             Returns <tt> std::pair<iterator, bool>  </tt> where \p first is an iterator pointing to
 386             item found or inserted, \p second is true if new item has been added or \p false if the item
 387             already is in the list.
 388         */
 389         template <typename K>
 390         std::pair<iterator, bool> update( const K& key, bool bAllowInsert = true )
 391         {
 392             std::pair< node_type *, bool > ret = update_at( head(), key, bAllowInsert );
 393             return std::make_pair( node_to_iterator( ret.first ), ret.second );
 394         }
 395         //@cond
 396         template <typename K>
 397         CDS_DEPRECATED("ensure() is deprecated, use update()")
 398         std::pair<iterator, bool> ensure( const K& key )
 399         {
 400             return update( key, true );
 401         }
 402         //@endcond
 403
 404         /// Inserts data of type \ref mapped_type constructed with <tt>std::forward<Args>(args)...</tt>
 405         /**
 406             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 407         */
 408         template <typename... Args>
 409         iterator emplace( Args&&... args )
 410         {
 411             return node_to_iterator( emplace_at( head(), std::forward<Args>(args)... ));
 412         }
 413
 414         /// Checks whether the list contains \p key
 415         /**
 416             The function searches the item with key equal to \p key
 417             and returns an iterator pointed to item found if the key is found,
 418             and \ref end() otherwise
 419         */
 420         template <typename Q>
 421         iterator contains( Q const& key )
 422         {
 423             return node_to_iterator( find_at( head(), key, intrusive_key_comparator() ) );
 424         }
 425         //@cond
 426         template <typename Q>
 427         CDS_DEPRECATED("deprecated, use contains()")
 428         iterator find( Q const& key )
 429         {
 430             return contains( key );
 431         }
 432         //@endcond
 433
 434         /// Checks whether the map contains \p key using \p pred predicate for searching (ordered list version)
 435         /**
 436             The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
 437             \p Less functor has the interface like \p std::less.
 438             \p Less must imply the same element order as the comparator used for building the list.
 439         */
 440         template <typename Q, typename Less, bool Sort = c_bSort>
 441         typename std::enable_if<Sort, iterator>::type contains( Q const& key, Less pred )
 442         {
 443             CDS_UNUSED( pred );
 444             return node_to_iterator( find_at( head(), key, typename maker::template less_wrapper<Less>::type() ) );
 445         }
 446         //@cond
 447         template <typename Q, typename Less, bool Sort = c_bSort>
 448         CDS_DEPRECATED("deprecated, use contains()")
 449         typename std::enable_if<Sort, iterator>::type find_with( Q const& key, Less pred )
 450         {
 451             return contains( key, pred );
 452         }
 453         //@endcond
 454
 455         /// Finds the key \p val using \p equal predicate for searching (unordered list version)
 456         /**
 457             The function is an analog of <tt>contains( key )</tt> but \p equal is used for key comparing.
 458             \p Equal functor has the interface like \p std::equal_to.
 459         */
 460         template <typename Q, typename Equal, bool Sort = c_bSort>
 461         typename std::enable_if<!Sort, iterator>::type contains( Q const& key, Equal equal )
 462         {
 463             CDS_UNUSED( equal );
 464             return node_to_iterator( find_at( head(), key, typename maker::template equal_to_wrapper<Equal>::type() ) );
 465         }
 466         //@cond
 467         template <typename Q, typename Equal, bool Sort = c_bSort>
 468         CDS_DEPRECATED("deprecated, use contains()")
 469         typename std::enable_if<!Sort, iterator>::type find_with( Q const& key, Equal equal )
 470         {
 471             return contains( key, equal );
 472         }
 473         //@endcond
 474
 475         /// Check if the list is empty
 476         bool empty() const
 477         {
 478             return base_class::empty();
 479         }
 480
 481         /// Returns list's item count
 482         /**
 483             The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
 484             this function always returns 0.
 485
 486             @note Even if you use real item counter and it returns 0, this fact is not mean that the list
 487             is empty. To check list emptyness use \ref empty() method.
 488         */
 489         size_t size() const
 490         {
 491             return base_class::size();
 492         }
 493
 494         /// Clears the list
 495         /**
 496             Post-condition: the list is empty
 497         */
 498         void clear()
 499         {
 500             base_class::clear();
 501         }
 502
 503     protected:
 504         //@cond
 505         node_type * insert_node_at( head_type& refHead, node_type * pNode )
 506         {
 507             assert( pNode != nullptr );
 508             scoped_node_ptr p( pNode );
 509             if ( base_class::insert_at( &refHead, *p ))
 510                 return p.release();
 511
 512             return nullptr;
 513         }
 514
 515         template <typename K>
 516         node_type * insert_at( head_type& refHead, const K& key )
 517         {
 518             return insert_node_at( refHead, alloc_node( key ));
 519         }
 520
 521         template <typename K, typename V>
 522         node_type * insert_at( head_type& refHead, const K& key, const V& val )
 523         {
 524             return insert_node_at( refHead, alloc_node( key, val ));
 525         }
 526
 527         template <typename K, typename Func>
 528         node_type * insert_with_at( head_type& refHead, const K& key, Func f )
 529         {
 530             scoped_node_ptr pNode( alloc_node( key ));
 531
 532             if ( base_class::insert_at( &refHead, *pNode )) {
 533                 f( pNode->m_Data );
 534                 return pNode.release();
 535             }
 536
 537             return nullptr;
 538         }
 539
 540
 541         template <typename K>
 542         std::pair< node_type *, bool > update_at( head_type& refHead, const K& key, bool bAllowInsert )
 543         {
 544             scoped_node_ptr pNode( alloc_node( key ));
 545             node_type * pItemFound = nullptr;
 546
 547             std::pair<bool, bool> ret = base_class::update_at( &refHead, *pNode,
 548                 [&pItemFound](bool, node_type& item, node_type&){ pItemFound = &item; },
 549                 bAllowInsert );
 550
 551             if ( ret.second )
 552                 pNode.release();
 553
 554             return std::make_pair( pItemFound, ret.second );
 555         }
 556
 557         template <typename... Args>
 558         node_type * emplace_at( head_type& refHead, Args&&... args )
 559         {
 560             return insert_node_at( refHead, alloc_node( std::forward<Args>(args)... ));
 561         }
 562
 563         template <typename K, typename Compare>
 564         node_type * find_at( head_type& refHead, const K& key, Compare cmp )
 565         {
 566             return base_class::find_at( &refHead, key, cmp );
 567         }
 568
 569         /*
 570         template <typename K, typenam Compare, typename Func>
 571         bool find_at( head_type& refHead, K& key, Compare cmp, Func f )
 572         {
 573             return base_class::find_at( &refHead, key, cmp, [&f]( node_type& node, K const& ){ f( node.m_Data ); });
 574         }
 575         */
 576         //@endcond
 577     };
 578
 579 }} // namespace cds::container
 580
 581 #endif // #ifndef CDSLIB_CONTAINER_LAZY_KVLIST_NOGC_H