cds/container/lazy_kvlist_nogc.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_CONTAINER_LAZY_KVLIST_NOGC_H
  32 #define CDSLIB_CONTAINER_LAZY_KVLIST_NOGC_H
  33
  34 #include <memory>
  35 #include <cds/container/details/lazy_list_base.h>
  36 #include <cds/intrusive/lazy_list_nogc.h>
  37 #include <cds/container/details/make_lazy_kvlist.h>
  38
  39 namespace cds { namespace container {
  40
  41     /// Lazy ordered list (key-value pair, template specialization for gc::nogc)
  42     /** @ingroup cds_nonintrusive_list
  43         @anchor cds_nonintrusive_LazyKVList_nogc
  44
  45         This specialization is append-only list when no item
  46         reclamation may be performed. The class does not support deleting of list's item.
  47
  48         See @ref cds_nonintrusive_LazyList_gc "cds::container::LazyList<cds::gc::nogc, T, Traits>"
  49     */
  50     template <
  51         typename Key,
  52         typename Value,
  53 #ifdef CDS_DOXYGEN_INVOKED
  54         typename Traits = lazy_list::traits
  55 #else
  56         typename Traits
  57 #endif
  58     >
  59     class LazyKVList<gc::nogc, Key, Value, Traits>:
  60 #ifdef CDS_DOXYGEN_INVOKED
  61         protected intrusive::LazyList< gc::nogc, implementation_defined, Traits >
  62 #else
  63         protected details::make_lazy_kvlist< cds::gc::nogc, Key, Value, Traits >::type
  64 #endif
  65     {
  66         //@cond
  67         typedef details::make_lazy_kvlist< cds::gc::nogc, Key, Value, Traits > maker;
  68         typedef typename maker::type  base_class;
  69         //@endcond
  70
  71     public:
  72         typedef Traits traits;    ///< List traits
  73         typedef cds::gc::nogc gc; ///< Garbage collector
  74 #ifdef CDS_DOXYGEN_INVOKED
  75         typedef Key                                 key_type        ;   ///< Key type
  76         typedef Value                               mapped_type     ;   ///< Type of value stored in the list
  77         typedef std::pair<key_type const, mapped_type> value_type   ;   ///< key/value pair stored in the list
  78 #else
  79         typedef typename maker::key_type    key_type;
  80         typedef typename maker::mapped_type mapped_type;
  81         typedef typename maker::value_type  value_type;
  82 #endif
  83         typedef typename base_class::back_off     back_off;       ///< Back-off strategy used
  84         typedef typename maker::allocator_type    allocator_type; ///< Allocator type used for allocate/deallocate the nodes
  85         typedef typename base_class::item_counter item_counter;   ///< Item counting policy used
  86         typedef typename maker::key_comparator    key_comparator; ///< key comparison functor
  87         typedef typename base_class::memory_model memory_model;   ///< Memory ordering. See cds::opt::memory_model option
  88         static CDS_CONSTEXPR bool const c_bSort = base_class::c_bSort; ///< List type: ordered (\p true) or unordered (\p false)
  89
  90     protected:
  91         //@cond
  92         typedef typename base_class::value_type     node_type;
  93         typedef typename maker::cxx_allocator       cxx_allocator;
  94         typedef typename maker::node_deallocator    node_deallocator;
  95         typedef typename base_class::key_comparator intrusive_key_comparator;
  96         typedef typename base_class::node_type      head_type;
  97         //@endcond
  98
  99     protected:
 100         //@cond
 101         template <typename K>
 102         static node_type * alloc_node(const K& key)
 103         {
 104             return cxx_allocator().New( key );
 105         }
 106
 107         template <typename K, typename V>
 108         static node_type * alloc_node( const K& key, const V& val )
 109         {
 110             return cxx_allocator().New( key, val );
 111         }
 112
 113         template <typename... Args>
 114         static node_type * alloc_node( Args&&... args )
 115         {
 116             return cxx_allocator().MoveNew( std::forward<Args>(args)... );
 117         }
 118
 119         static void free_node( node_type * pNode )
 120         {
 121             cxx_allocator().Delete( pNode );
 122         }
 123
 124         struct node_disposer {
 125             void operator()( node_type * pNode )
 126             {
 127                 free_node( pNode );
 128             }
 129         };
 130         typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
 131
 132         head_type& head()
 133         {
 134             return base_class::m_Head;
 135         }
 136
 137         head_type const& head() const
 138         {
 139             return base_class::m_Head;
 140         }
 141
 142         head_type& tail()
 143         {
 144             return base_class::m_Tail;
 145         }
 146
 147         head_type const& tail() const
 148         {
 149             return base_class::m_Tail;
 150         }
 151         //@endcond
 152
 153     protected:
 154         //@cond
 155         template <bool IsConst>
 156         class iterator_type: protected base_class::template iterator_type<IsConst>
 157         {
 158             typedef typename base_class::template iterator_type<IsConst>    iterator_base;
 159
 160             iterator_type( head_type const& refNode )
 161                 : iterator_base( const_cast<head_type *>( &refNode ))
 162             {}
 163
 164             explicit iterator_type( const iterator_base& it )
 165                 : iterator_base( it )
 166             {}
 167
 168             friend class LazyKVList;
 169
 170         protected:
 171             explicit iterator_type( node_type& pNode )
 172                 : iterator_base( &pNode )
 173             {}
 174
 175         public:
 176             typedef typename cds::details::make_const_type<mapped_type, IsConst>::reference  value_ref;
 177             typedef typename cds::details::make_const_type<mapped_type, IsConst>::pointer    value_ptr;
 178
 179             typedef typename cds::details::make_const_type<value_type,  IsConst>::reference  pair_ref;
 180             typedef typename cds::details::make_const_type<value_type,  IsConst>::pointer    pair_ptr;
 181
 182             iterator_type()
 183                 : iterator_base()
 184             {}
 185
 186             iterator_type( const iterator_type& src )
 187                 : iterator_base( src )
 188             {}
 189
 190             key_type const& key() const
 191             {
 192                 typename iterator_base::value_ptr p = iterator_base::operator ->();
 193                 assert( p != nullptr );
 194                 return p->m_Data.first;
 195             }
 196
 197             value_ref val() const
 198             {
 199                 typename iterator_base::value_ptr p = iterator_base::operator ->();
 200                 assert( p != nullptr );
 201                 return p->m_Data.second;
 202             }
 203
 204             pair_ptr operator ->() const
 205             {
 206                 typename iterator_base::value_ptr p = iterator_base::operator ->();
 207                 return p ? &(p->m_Data) : nullptr;
 208             }
 209
 210             pair_ref operator *() const
 211             {
 212                 typename iterator_base::value_ref p = iterator_base::operator *();
 213                 return p.m_Data;
 214             }
 215
 216             /// Pre-increment
 217             iterator_type& operator ++()
 218             {
 219                 iterator_base::operator ++();
 220                 return *this;
 221             }
 222
 223             /// Post-increment
 224             iterator_type operator ++(int)
 225             {
 226                 return iterator_base::operator ++(0);
 227             }
 228
 229             template <bool C>
 230             bool operator ==(iterator_type<C> const& i ) const
 231             {
 232                 return iterator_base::operator ==(i);
 233             }
 234             template <bool C>
 235             bool operator !=(iterator_type<C> const& i ) const
 236             {
 237                 return iterator_base::operator !=(i);
 238             }
 239         };
 240         //@endcond
 241
 242     public:
 243         /// Forward iterator
 244         /**
 245             The forward iterator for lazy list based on gc::nogc has pre- and post-increment operators.
 246
 247             The iterator interface to access item data:
 248             - <tt> operator -> </tt> - returns a pointer to \ref value_type for iterator
 249             - <tt> operator *</tt> - returns a reference (a const reference for \p const_iterator) to \ref value_type for iterator
 250             - <tt> const key_type& key() </tt> - returns a key reference for iterator
 251             - <tt> mapped_type& val() </tt> - retuns a value reference for iterator (const reference for \p const_iterator)
 252
 253             For both functions the iterator should not be equal to <tt> end() </tt>
 254         */
 255         typedef iterator_type<false>    iterator;
 256
 257         /// Const forward iterator
 258         /**
 259             For iterator's features and requirements see \ref iterator
 260         */
 261         typedef iterator_type<true>     const_iterator;
 262
 263         /// Returns a forward iterator addressing the first element in a list
 264         /**
 265             For empty list \code begin() == end() \endcode
 266         */
 267         iterator begin()
 268         {
 269             iterator it( head() );
 270             ++it ;  // skip dummy head
 271             return it;
 272         }
 273
 274         /// Returns an iterator that addresses the location succeeding the last element in a list
 275         /**
 276             Do not use the value returned by <tt>end</tt> function to access any item.
 277             Internally, <tt>end</tt> returning value equals to nullptr.
 278
 279             The returned value can be used only to control reaching the end of the list.
 280             For empty list \code begin() == end() \endcode
 281         */
 282         iterator end()
 283         {
 284             return iterator( tail());
 285         }
 286
 287         /// Returns a forward const iterator addressing the first element in a list
 288         //@{
 289         const_iterator begin() const
 290         {
 291             const_iterator it( head() );
 292             ++it ;  // skip dummy head
 293             return it;
 294         }
 295         const_iterator cbegin() const
 296         {
 297             const_iterator it( head() );
 298             ++it ;  // skip dummy head
 299             return it;
 300         }
 301         //@}
 302
 303         /// Returns an const iterator that addresses the location succeeding the last element in a list
 304         //@{
 305         const_iterator end() const
 306         {
 307             return const_iterator( tail());
 308         }
 309         const_iterator cend() const
 310         {
 311             return const_iterator( tail());
 312         }
 313         //@}
 314
 315     protected:
 316         //@cond
 317         iterator node_to_iterator( node_type * pNode )
 318         {
 319             if ( pNode )
 320                 return iterator( *pNode );
 321             return end();
 322         }
 323         //@endcond
 324
 325     public:
 326         /// Default constructor
 327         LazyKVList()
 328         {}
 329
 330         /// Desctructor clears the list
 331         ~LazyKVList()
 332         {
 333             clear();
 334         }
 335
 336         /// Inserts new node with key and default value
 337         /**
 338             The function creates a node with \p key and default value, and then inserts the node created into the list.
 339
 340             Preconditions:
 341             - The \ref key_type should be constructible from value of type \p K.
 342                 In trivial case, \p K is equal to \ref key_type.
 343             - The \ref mapped_type should be default-constructible.
 344
 345             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 346         */
 347         template <typename K>
 348         iterator insert( const K& key )
 349         {
 350             return node_to_iterator( insert_at( head(), key ));
 351         }
 352
 353         /// Inserts new node with a key and a value
 354         /**
 355             The function creates a node with \p key and value \p val, and then inserts the node created into the list.
 356
 357             Preconditions:
 358             - The \ref key_type should be constructible from \p key of type \p K.
 359             - The \ref mapped_type should be constructible from \p val of type \p V.
 360
 361             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 362         */
 363         template <typename K, typename V>
 364         iterator insert( const K& key, const V& val )
 365         {
 366             // We cannot use insert with functor here
 367             // because we cannot lock inserted node for updating
 368             // Therefore, we use separate function
 369             return node_to_iterator( insert_at( head(), key, val ));
 370         }
 371
 372         /// Inserts new node and initialize it by a functor
 373         /**
 374             This function inserts new node with key \p key and if inserting is successful then it calls
 375             \p func functor with signature
 376             \code void func( value_type& item ) ; endcode
 377             or
 378             \code
 379             struct functor {
 380                 void operator()( value_type& item );
 381             };
 382             \endcode
 383
 384             The argument \p item of user-defined functor \p func is the reference
 385             to the list's item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
 386             The user-defined functor is called only if the inserting is successful.
 387
 388             The key_type should be constructible from value of type \p K.
 389
 390             The function allows to split creating of new item into two part:
 391             - create item from \p key;
 392             - insert new item into the list;
 393             - if inserting is successful, initialize the value of item by calling \p f functor
 394
 395             This can be useful if complete initialization of object of \p mapped_type is heavyweight and
 396             it is preferable that the initialization should be completed only if inserting is successful.
 397
 398             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 399         */
 400         template <typename K, typename Func>
 401         iterator insert_with( const K& key, Func func )
 402         {
 403             return node_to_iterator( insert_with_at( head(), key, func ));
 404         }
 405
 406         /// Updates the item
 407         /**
 408             If \p key is not in the list and \p bAllowInsert is \p true,
 409
 410             the function inserts a new item.
 411             Otherwise, the function returns an iterator pointing to the item found.
 412
 413             Returns <tt> std::pair<iterator, bool>  </tt> where \p first is an iterator pointing to
 414             item found or inserted, \p second is true if new item has been added or \p false if the item
 415             already is in the list.
 416         */
 417         template <typename K>
 418         std::pair<iterator, bool> update( const K& key, bool bAllowInsert = true )
 419         {
 420             std::pair< node_type *, bool > ret = update_at( head(), key, bAllowInsert );
 421             return std::make_pair( node_to_iterator( ret.first ), ret.second );
 422         }
 423         //@cond
 424         template <typename K>
 425         CDS_DEPRECATED("ensure() is deprecated, use update()")
 426         std::pair<iterator, bool> ensure( const K& key )
 427         {
 428             return update( key, true );
 429         }
 430         //@endcond
 431
 432         /// Inserts data of type \ref mapped_type constructed with <tt>std::forward<Args>(args)...</tt>
 433         /**
 434             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 435         */
 436         template <typename... Args>
 437         iterator emplace( Args&&... args )
 438         {
 439             return node_to_iterator( emplace_at( head(), std::forward<Args>(args)... ));
 440         }
 441
 442         /// Checks whether the list contains \p key
 443         /**
 444             The function searches the item with key equal to \p key
 445             and returns an iterator pointed to item found if the key is found,
 446             and \ref end() otherwise
 447         */
 448         template <typename Q>
 449         iterator contains( Q const& key )
 450         {
 451             return node_to_iterator( find_at( head(), key, intrusive_key_comparator() ) );
 452         }
 453         //@cond
 454         template <typename Q>
 455         CDS_DEPRECATED("deprecated, use contains()")
 456         iterator find( Q const& key )
 457         {
 458             return contains( key );
 459         }
 460         //@endcond
 461
 462         /// Checks whether the map contains \p key using \p pred predicate for searching (ordered list version)
 463         /**
 464             The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
 465             \p Less functor has the interface like \p std::less.
 466             \p Less must imply the same element order as the comparator used for building the list.
 467         */
 468         template <typename Q, typename Less, bool Sort = c_bSort>
 469         typename std::enable_if<Sort, iterator>::type contains( Q const& key, Less pred )
 470         {
 471             CDS_UNUSED( pred );
 472             return node_to_iterator( find_at( head(), key, typename maker::template less_wrapper<Less>::type() ) );
 473         }
 474         //@cond
 475         template <typename Q, typename Less, bool Sort = c_bSort>
 476         CDS_DEPRECATED("deprecated, use contains()")
 477         typename std::enable_if<Sort, iterator>::type find_with( Q const& key, Less pred )
 478         {
 479             return contains( key, pred );
 480         }
 481         //@endcond
 482
 483         /// Finds the key \p val using \p equal predicate for searching (unordered list version)
 484         /**
 485             The function is an analog of <tt>contains( key )</tt> but \p equal is used for key comparing.
 486             \p Equal functor has the interface like \p std::equal_to.
 487         */
 488         template <typename Q, typename Equal, bool Sort = c_bSort>
 489         typename std::enable_if<!Sort, iterator>::type contains( Q const& key, Equal equal )
 490         {
 491             CDS_UNUSED( equal );
 492             return node_to_iterator( find_at( head(), key, typename maker::template equal_to_wrapper<Equal>::type() ) );
 493         }
 494         //@cond
 495         template <typename Q, typename Equal, bool Sort = c_bSort>
 496         CDS_DEPRECATED("deprecated, use contains()")
 497         typename std::enable_if<!Sort, iterator>::type find_with( Q const& key, Equal equal )
 498         {
 499             return contains( key, equal );
 500         }
 501         //@endcond
 502
 503         /// Check if the list is empty
 504         bool empty() const
 505         {
 506             return base_class::empty();
 507         }
 508
 509         /// Returns list's item count
 510         /**
 511             The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
 512             this function always returns 0.
 513
 514             @note Even if you use real item counter and it returns 0, this fact is not mean that the list
 515             is empty. To check list emptyness use \ref empty() method.
 516         */
 517         size_t size() const
 518         {
 519             return base_class::size();
 520         }
 521
 522         /// Clears the list
 523         /**
 524             Post-condition: the list is empty
 525         */
 526         void clear()
 527         {
 528             base_class::clear();
 529         }
 530
 531     protected:
 532         //@cond
 533         node_type * insert_node_at( head_type& refHead, node_type * pNode )
 534         {
 535             assert( pNode != nullptr );
 536             scoped_node_ptr p( pNode );
 537             if ( base_class::insert_at( &refHead, *p ))
 538                 return p.release();
 539
 540             return nullptr;
 541         }
 542
 543         template <typename K>
 544         node_type * insert_at( head_type& refHead, const K& key )
 545         {
 546             return insert_node_at( refHead, alloc_node( key ));
 547         }
 548
 549         template <typename K, typename V>
 550         node_type * insert_at( head_type& refHead, const K& key, const V& val )
 551         {
 552             return insert_node_at( refHead, alloc_node( key, val ));
 553         }
 554
 555         template <typename K, typename Func>
 556         node_type * insert_with_at( head_type& refHead, const K& key, Func f )
 557         {
 558             scoped_node_ptr pNode( alloc_node( key ));
 559
 560             if ( base_class::insert_at( &refHead, *pNode )) {
 561                 f( pNode->m_Data );
 562                 return pNode.release();
 563             }
 564
 565             return nullptr;
 566         }
 567
 568
 569         template <typename K>
 570         std::pair< node_type *, bool > update_at( head_type& refHead, const K& key, bool bAllowInsert )
 571         {
 572             scoped_node_ptr pNode( alloc_node( key ));
 573             node_type * pItemFound = nullptr;
 574
 575             std::pair<bool, bool> ret = base_class::update_at( &refHead, *pNode,
 576                 [&pItemFound](bool, node_type& item, node_type&){ pItemFound = &item; },
 577                 bAllowInsert );
 578
 579             if ( ret.second )
 580                 pNode.release();
 581
 582             return std::make_pair( pItemFound, ret.second );
 583         }
 584
 585         template <typename... Args>
 586         node_type * emplace_at( head_type& refHead, Args&&... args )
 587         {
 588             return insert_node_at( refHead, alloc_node( std::forward<Args>(args)... ));
 589         }
 590
 591         template <typename K, typename Compare>
 592         node_type * find_at( head_type& refHead, const K& key, Compare cmp )
 593         {
 594             return base_class::find_at( &refHead, key, cmp );
 595         }
 596
 597         /*
 598         template <typename K, typenam Compare, typename Func>
 599         bool find_at( head_type& refHead, K& key, Compare cmp, Func f )
 600         {
 601             return base_class::find_at( &refHead, key, cmp, [&f]( node_type& node, K const& ){ f( node.m_Data ); });
 602         }
 603         */
 604         //@endcond
 605     };
 606
 607 }} // namespace cds::container
 608
 609 #endif // #ifndef CDSLIB_CONTAINER_LAZY_KVLIST_NOGC_H