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