cds/container/lazy_kvlist_nogc.h

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