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