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     ///@name Forward iterators
 244     //@{
 245         /// Forward iterator
 246         /**
 247         The forward iterator is safe: you may use it in multi-threaded enviromnent without any synchronization.
 248
 249         The forward iterator for lazy list based on \p gc::nogc has pre- and post-increment operators.
 250
 251             The iterator interface to access item data:
 252             - <tt> operator -> </tt> - returns a pointer to \p value_type
 253             - <tt> operator *</tt> - returns a reference (a const reference for \p const_iterator) to \p value_type
 254             - <tt> const key_type& key() </tt> - returns a key reference for iterator
 255             - <tt> mapped_type& val() </tt> - retuns a value reference for iterator (const reference for \p const_iterator)
 256
 257             For both functions the iterator should not be equal to \p end()
 258         */
 259         typedef iterator_type<false>    iterator;
 260
 261         /// Const forward iterator
 262         /**
 263             For iterator's features and requirements see \ref iterator
 264         */
 265         typedef iterator_type<true>     const_iterator;
 266
 267         /// Returns a forward iterator addressing the first element in a list
 268         /**
 269             For empty list \code begin() == end() \endcode
 270         */
 271         iterator begin()
 272         {
 273             iterator it( head() );
 274             ++it ;  // skip dummy head
 275             return it;
 276         }
 277
 278         /// Returns an iterator that addresses the location succeeding the last element in a list
 279         /**
 280             Do not use the value returned by <tt>end</tt> function to access any item.
 281             Internally, <tt>end</tt> returning value equals to nullptr.
 282
 283             The returned value can be used only to control reaching the end of the list.
 284             For empty list \code begin() == end() \endcode
 285         */
 286         iterator end()
 287         {
 288             return iterator( tail());
 289         }
 290
 291         /// Returns a forward const iterator addressing the first element in a list
 292         const_iterator begin() const
 293         {
 294             const_iterator it( head() );
 295             ++it ;  // skip dummy head
 296             return it;
 297         }
 298         /// Returns a forward const iterator addressing the first element in a list
 299         const_iterator cbegin() const
 300         {
 301             const_iterator it( head() );
 302             ++it ;  // skip dummy head
 303             return it;
 304         }
 305
 306         /// Returns an const iterator that addresses the location succeeding the last element in a list
 307         const_iterator end() const
 308         {
 309             return const_iterator( tail());
 310         }
 311         /// Returns an const iterator that addresses the location succeeding the last element in a list
 312         const_iterator cend() const
 313         {
 314             return const_iterator( tail());
 315         }
 316     //@}
 317
 318     protected:
 319         //@cond
 320         iterator node_to_iterator( node_type * pNode )
 321         {
 322             if ( pNode )
 323                 return iterator( *pNode );
 324             return end();
 325         }
 326         //@endcond
 327
 328     public:
 329         /// Default constructor
 330         LazyKVList()
 331         {}
 332
 333         /// Desctructor clears the list
 334         ~LazyKVList()
 335         {
 336             clear();
 337         }
 338
 339         /// Inserts new node with key and default value
 340         /**
 341             The function creates a node with \p key and default value, and then inserts the node created into the list.
 342
 343             Preconditions:
 344             - The \ref key_type should be constructible from value of type \p K.
 345                 In trivial case, \p K is equal to \ref key_type.
 346             - The \ref mapped_type should be default-constructible.
 347
 348             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 349         */
 350         template <typename K>
 351         iterator insert( const K& key )
 352         {
 353             return node_to_iterator( insert_at( head(), key ));
 354         }
 355
 356         /// Inserts new node with a key and a value
 357         /**
 358             The function creates a node with \p key and value \p val, and then inserts the node created into the list.
 359
 360             Preconditions:
 361             - The \ref key_type should be constructible from \p key of type \p K.
 362             - The \ref mapped_type should be constructible from \p val of type \p V.
 363
 364             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 365         */
 366         template <typename K, typename V>
 367         iterator insert( const K& key, const V& val )
 368         {
 369             // We cannot use insert with functor here
 370             // because we cannot lock inserted node for updating
 371             // Therefore, we use separate function
 372             return node_to_iterator( insert_at( head(), key, val ));
 373         }
 374
 375         /// Inserts new node and initialize it by a functor
 376         /**
 377             This function inserts new node with key \p key and if inserting is successful then it calls
 378             \p func functor with signature
 379             \code void func( value_type& item ) ; endcode
 380             or
 381             \code
 382             struct functor {
 383                 void operator()( value_type& item );
 384             };
 385             \endcode
 386
 387             The argument \p item of user-defined functor \p func is the reference
 388             to the list's item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
 389             The user-defined functor is called only if the inserting is successful.
 390
 391             The key_type should be constructible from value of type \p K.
 392
 393             The function allows to split creating of new item into two part:
 394             - create item from \p key;
 395             - insert new item into the list;
 396             - if inserting is successful, initialize the value of item by calling \p f functor
 397
 398             This can be useful if complete initialization of object of \p mapped_type is heavyweight and
 399             it is preferable that the initialization should be completed only if inserting is successful.
 400
 401             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 402         */
 403         template <typename K, typename Func>
 404         iterator insert_with( const K& key, Func func )
 405         {
 406             return node_to_iterator( insert_with_at( head(), key, func ));
 407         }
 408
 409         /// Updates the item
 410         /**
 411             If \p key is not in the list and \p bAllowInsert is \p true,
 412
 413             the function inserts a new item.
 414             Otherwise, the function returns an iterator pointing to the 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> update( const K& key, bool bAllowInsert = true )
 422         {
 423             std::pair< node_type *, bool > ret = update_at( head(), key, bAllowInsert );
 424             return std::make_pair( node_to_iterator( ret.first ), ret.second );
 425         }
 426         //@cond
 427         template <typename K>
 428         CDS_DEPRECATED("ensure() is deprecated, use update()")
 429         std::pair<iterator, bool> ensure( const K& key )
 430         {
 431             return update( key, true );
 432         }
 433         //@endcond
 434
 435         /// Inserts data of type \ref mapped_type constructed with <tt>std::forward<Args>(args)...</tt>
 436         /**
 437             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 438         */
 439         template <typename... Args>
 440         iterator emplace( Args&&... args )
 441         {
 442             return node_to_iterator( emplace_at( head(), std::forward<Args>(args)... ));
 443         }
 444
 445         /// Checks whether the list contains \p key
 446         /**
 447             The function searches the item with key equal to \p key
 448             and returns an iterator pointed to item found if the key is found,
 449             and \ref end() otherwise
 450         */
 451         template <typename Q>
 452         iterator contains( Q const& key )
 453         {
 454             return node_to_iterator( find_at( head(), key, intrusive_key_comparator() ) );
 455         }
 456         //@cond
 457         template <typename Q>
 458         CDS_DEPRECATED("deprecated, use contains()")
 459         iterator find( Q const& key )
 460         {
 461             return contains( key );
 462         }
 463         //@endcond
 464
 465         /// Checks whether the map contains \p key using \p pred predicate for searching (ordered list version)
 466         /**
 467             The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
 468             \p Less functor has the interface like \p std::less.
 469             \p Less must imply the same element order as the comparator used for building the list.
 470         */
 471         template <typename Q, typename Less, bool Sort = c_bSort>
 472         typename std::enable_if<Sort, iterator>::type contains( Q const& key, Less pred )
 473         {
 474             CDS_UNUSED( pred );
 475             return node_to_iterator( find_at( head(), key, typename maker::template less_wrapper<Less>::type() ) );
 476         }
 477         //@cond
 478         template <typename Q, typename Less, bool Sort = c_bSort>
 479         CDS_DEPRECATED("deprecated, use contains()")
 480         typename std::enable_if<Sort, iterator>::type find_with( Q const& key, Less pred )
 481         {
 482             return contains( key, pred );
 483         }
 484         //@endcond
 485
 486         /// Finds the key \p val using \p equal predicate for searching (unordered list version)
 487         /**
 488             The function is an analog of <tt>contains( key )</tt> but \p equal is used for key comparing.
 489             \p Equal functor has the interface like \p std::equal_to.
 490         */
 491         template <typename Q, typename Equal, bool Sort = c_bSort>
 492         typename std::enable_if<!Sort, iterator>::type contains( Q const& key, Equal equal )
 493         {
 494             CDS_UNUSED( equal );
 495             return node_to_iterator( find_at( head(), key, typename maker::template equal_to_wrapper<Equal>::type() ) );
 496         }
 497         //@cond
 498         template <typename Q, typename Equal, bool Sort = c_bSort>
 499         CDS_DEPRECATED("deprecated, use contains()")
 500         typename std::enable_if<!Sort, iterator>::type find_with( Q const& key, Equal equal )
 501         {
 502             return contains( key, equal );
 503         }
 504         //@endcond
 505
 506         /// Check if the list is empty
 507         bool empty() const
 508         {
 509             return base_class::empty();
 510         }
 511
 512         /// Returns list's item count
 513         /**
 514             The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
 515             this function always returns 0.
 516
 517             @note Even if you use real item counter and it returns 0, this fact is not mean that the list
 518             is empty. To check list emptyness use \ref empty() method.
 519         */
 520         size_t size() const
 521         {
 522             return base_class::size();
 523         }
 524
 525         /// Clears the list
 526         /**
 527             Post-condition: the list is empty
 528         */
 529         void clear()
 530         {
 531             base_class::clear();
 532         }
 533
 534     protected:
 535         //@cond
 536         node_type * insert_node_at( head_type& refHead, node_type * pNode )
 537         {
 538             assert( pNode != nullptr );
 539             scoped_node_ptr p( pNode );
 540             if ( base_class::insert_at( &refHead, *p ))
 541                 return p.release();
 542
 543             return nullptr;
 544         }
 545
 546         template <typename K>
 547         node_type * insert_at( head_type& refHead, const K& key )
 548         {
 549             return insert_node_at( refHead, alloc_node( key ));
 550         }
 551
 552         template <typename K, typename V>
 553         node_type * insert_at( head_type& refHead, const K& key, const V& val )
 554         {
 555             return insert_node_at( refHead, alloc_node( key, val ));
 556         }
 557
 558         template <typename K, typename Func>
 559         node_type * insert_with_at( head_type& refHead, const K& key, Func f )
 560         {
 561             scoped_node_ptr pNode( alloc_node( key ));
 562
 563             if ( base_class::insert_at( &refHead, *pNode )) {
 564                 f( pNode->m_Data );
 565                 return pNode.release();
 566             }
 567
 568             return nullptr;
 569         }
 570
 571
 572         template <typename K>
 573         std::pair< node_type *, bool > update_at( head_type& refHead, const K& key, bool bAllowInsert )
 574         {
 575             scoped_node_ptr pNode( alloc_node( key ));
 576             node_type * pItemFound = nullptr;
 577
 578             std::pair<bool, bool> ret = base_class::update_at( &refHead, *pNode,
 579                 [&pItemFound](bool, node_type& item, node_type&){ pItemFound = &item; },
 580                 bAllowInsert );
 581
 582             if ( ret.second )
 583                 pNode.release();
 584
 585             return std::make_pair( pItemFound, ret.second );
 586         }
 587
 588         template <typename... Args>
 589         node_type * emplace_at( head_type& refHead, Args&&... args )
 590         {
 591             return insert_node_at( refHead, alloc_node( std::forward<Args>(args)... ));
 592         }
 593
 594         template <typename K, typename Compare>
 595         node_type * find_at( head_type& refHead, const K& key, Compare cmp )
 596         {
 597             return base_class::find_at( &refHead, key, cmp );
 598         }
 599
 600         /*
 601         template <typename K, typenam Compare, typename Func>
 602         bool find_at( head_type& refHead, K& key, Compare cmp, Func f )
 603         {
 604             return base_class::find_at( &refHead, key, cmp, [&f]( node_type& node, K const& ){ f( node.m_Data ); });
 605         }
 606         */
 607         //@endcond
 608     };
 609
 610 }} // namespace cds::container
 611
 612 #endif // #ifndef CDSLIB_CONTAINER_LAZY_KVLIST_NOGC_H