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