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