cds/container/lazy_list_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_LIST_NOGC_H
  32 #define CDSLIB_CONTAINER_LAZY_LIST_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_list.h>
  38
  39 namespace cds { namespace container {
  40
  41     /// Lazy ordered single-linked list (template specialization for gc::nogc)
  42     /** @ingroup cds_nonintrusive_list
  43         \anchor cds_nonintrusive_LazyList_nogc
  44
  45         This specialization is so-called append-only when no item
  46         reclamation may be performed. The class does not support deleting of list item.
  47
  48         The list can be ordered if \p Traits::sort is \p true that is default
  49         or unordered otherwise. Unordered list can be maintained by \p equal_to
  50         relationship (\p Traits::equal_to), but for the ordered list \p less
  51         or \p compare relations should be specified in \p Traits.
  52
  53         See @ref cds_nonintrusive_LazyList_gc "cds::container::LazyList<cds::gc::nogc, T, Traits>"
  54     */
  55     template <
  56         typename T,
  57 #ifdef CDS_DOXYGEN_INVOKED
  58         typename Traits = lazy_list::traits
  59 #else
  60         typename Traits
  61 #endif
  62     >
  63     class LazyList<cds::gc::nogc, T, Traits>:
  64 #ifdef CDS_DOXYGEN_INVOKED
  65         protected intrusive::LazyList< gc::nogc, T, Traits >
  66 #else
  67         protected details::make_lazy_list< cds::gc::nogc, T, Traits >::type
  68 #endif
  69     {
  70         //@cond
  71         typedef details::make_lazy_list< cds::gc::nogc, T, Traits > maker;
  72         typedef typename maker::type  base_class;
  73         //@endcond
  74
  75     public:
  76         typedef cds::gc::nogc gc;  ///< Garbage collector
  77         typedef T      value_type; ///< Type of value stored in the list
  78         typedef Traits traits;     ///< List traits
  79
  80         typedef typename base_class::back_off     back_off;         ///< Back-off strategy used
  81         typedef typename maker::allocator_type    allocator_type;   ///< Allocator type used for allocate/deallocate the nodes
  82         typedef typename base_class::item_counter item_counter;     ///< Item counting policy used
  83         typedef typename maker::key_comparator    key_comparator;   ///< key comparing functor
  84         typedef typename base_class::memory_model memory_model;     ///< Memory ordering. See cds::opt::memory_model option
  85         typedef typename base_class::stat         stat;             ///< Internal statistics
  86
  87         static CDS_CONSTEXPR bool const c_bSort = base_class::c_bSort; ///< List type: ordered (\p true) or unordered (\p false)
  88
  89     protected:
  90         //@cond
  91         typedef typename base_class::value_type     node_type;
  92         typedef typename maker::cxx_allocator       cxx_allocator;
  93         typedef typename maker::node_deallocator    node_deallocator;
  94         typedef typename base_class::key_comparator intrusive_key_comparator;
  95
  96         typedef typename base_class::node_type      head_type;
  97         //@endcond
  98
  99     protected:
 100         //@cond
 101         static value_type& node_to_value( node_type& n )
 102         {
 103             return n.m_Value;
 104         }
 105
 106         static node_type * alloc_node()
 107         {
 108             return cxx_allocator().New();
 109         }
 110
 111         static node_type * alloc_node( value_type const& v )
 112         {
 113             return cxx_allocator().New( v );
 114         }
 115
 116         template <typename... Args>
 117         static node_type * alloc_node( Args&&... args )
 118         {
 119             return cxx_allocator().MoveNew( std::forward<Args>(args)... );
 120         }
 121
 122         static void free_node( node_type * pNode )
 123         {
 124             cxx_allocator().Delete( pNode );
 125         }
 126
 127         struct node_disposer {
 128             void operator()( node_type * pNode )
 129             {
 130                 free_node( pNode );
 131             }
 132         };
 133         typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
 134
 135         head_type& head()
 136         {
 137             return base_class::m_Head;
 138         }
 139
 140         head_type const& head() const
 141         {
 142             return base_class::m_Head;
 143         }
 144
 145         head_type& tail()
 146         {
 147             return base_class::m_Tail;
 148         }
 149
 150         head_type const& tail() const
 151         {
 152             return base_class::m_Tail;
 153         }
 154         //@endcond
 155
 156     protected:
 157         //@cond
 158         template <bool IsConst>
 159         class iterator_type: protected base_class::template iterator_type<IsConst>
 160         {
 161             typedef typename base_class::template iterator_type<IsConst>    iterator_base;
 162
 163             iterator_type( head_type const& pNode )
 164                 : iterator_base( const_cast<head_type *>(&pNode) )
 165             {}
 166
 167             explicit iterator_type( const iterator_base& it )
 168                 : iterator_base( it )
 169             {}
 170
 171             friend class LazyList;
 172
 173         protected:
 174             explicit iterator_type( node_type& pNode )
 175                 : iterator_base( &pNode )
 176             {}
 177
 178         public:
 179             typedef typename cds::details::make_const_type<value_type, IsConst>::pointer   value_ptr;
 180             typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
 181
 182             iterator_type()
 183             {}
 184
 185             iterator_type( const iterator_type& src )
 186                 : iterator_base( src )
 187             {}
 188
 189             value_ptr operator ->() const
 190             {
 191                 typename iterator_base::value_ptr p = iterator_base::operator ->();
 192                 return p ? &(p->m_Value) : nullptr;
 193             }
 194
 195             value_ref operator *() const
 196             {
 197                 return (iterator_base::operator *()).m_Value;
 198             }
 199
 200             /// Pre-increment
 201             iterator_type& operator ++()
 202             {
 203                 iterator_base::operator ++();
 204                 return *this;
 205             }
 206
 207             /// Post-increment
 208             iterator_type operator ++(int)
 209             {
 210                 return iterator_base::operator ++(0);
 211             }
 212
 213             template <bool C>
 214             bool operator ==(iterator_type<C> const& i ) const
 215             {
 216                 return iterator_base::operator ==(i);
 217             }
 218             template <bool C>
 219             bool operator !=(iterator_type<C> const& i ) const
 220             {
 221                 return iterator_base::operator !=(i);
 222             }
 223         };
 224         //@endcond
 225
 226     public:
 227     ///@name Forward iterators
 228     //@{
 229         /// Returns a forward iterator addressing the first element in a list
 230         /**
 231             For empty list \code begin() == end() \endcode
 232         */
 233         typedef iterator_type<false>    iterator;
 234
 235         /// Const forward iterator
 236         /**
 237             For iterator's features and requirements see \ref iterator
 238         */
 239         typedef iterator_type<true>     const_iterator;
 240
 241         /// Returns a forward iterator addressing the first element in a list
 242         /**
 243             For empty list \code begin() == end() \endcode
 244         */
 245         iterator begin()
 246         {
 247             iterator it( head() );
 248             ++it    ;   // skip dummy head node
 249             return it;
 250         }
 251
 252         /// Returns an iterator that addresses the location succeeding the last element in a list
 253         /**
 254             Do not use the value returned by <tt>end</tt> function to access any item.
 255
 256             The returned value can be used only to control reaching the end of the list.
 257             For empty list \code begin() == end() \endcode
 258         */
 259         iterator end()
 260         {
 261             return iterator( tail());
 262         }
 263
 264         /// Returns a forward const iterator addressing the first element in a list
 265         const_iterator begin() const
 266         {
 267             const_iterator it( head() );
 268             ++it    ;   // skip dummy head node
 269             return it;
 270         }
 271
 272         /// Returns a forward const iterator addressing the first element in a list
 273         const_iterator cbegin() const
 274         {
 275             const_iterator it( head() );
 276             ++it    ;   // skip dummy head node
 277             return it;
 278         }
 279
 280         /// Returns an const iterator that addresses the location succeeding the last element in a list
 281         const_iterator end() const
 282         {
 283             return const_iterator( tail());
 284         }
 285
 286         /// Returns an const iterator that addresses the location succeeding the last element in a list
 287         const_iterator cend() const
 288         {
 289             return const_iterator( tail());
 290         }
 291     //@}
 292
 293     protected:
 294         //@cond
 295         iterator node_to_iterator( node_type * pNode )
 296         {
 297             if ( pNode )
 298                 return iterator( *pNode );
 299             return end();
 300         }
 301         //@endcond
 302
 303     public:
 304         /// Default constructor
 305         LazyList()
 306         {}
 307
 308         //@cond
 309         template <typename Stat, typename = std::enable_if<std::is_same<stat, lazy_list::wrapped_stat<Stat>>::value >>
 310         explicit LazyList( Stat& st )
 311             : base_class( st )
 312         {}
 313         //@endcond
 314
 315         /// Desctructor clears the list
 316         ~LazyList()
 317         {
 318             clear();
 319         }
 320
 321         /// Inserts new node
 322         /**
 323             The function inserts \p val in the list if the list does not contain
 324             an item with key equal to \p val.
 325
 326             Return an iterator pointing to inserted item if success \ref end() otherwise
 327         */
 328         template <typename Q>
 329         iterator insert( Q const& val )
 330         {
 331             return node_to_iterator( insert_at( head(), val ) );
 332         }
 333
 334         /// Inserts data of type \p value_type created from \p args
 335         /**
 336             Return an iterator pointing to inserted item if success \ref end() otherwise
 337         */
 338         template <typename... Args>
 339         iterator emplace( Args&&... args )
 340         {
 341             return node_to_iterator( emplace_at( head(), std::forward<Args>(args)... ));
 342         }
 343
 344         /// Updates the item
 345         /**
 346             If \p key is not in the list and \p bAllowInsert is \p true,
 347
 348             the function inserts a new item.
 349             Otherwise, the function returns an iterator pointing to the item found.
 350
 351             Returns <tt> std::pair<iterator, bool>  </tt> where \p first is an iterator pointing to
 352             item found or inserted, \p second is true if new item has been added or \p false if the item
 353             already is in the list.
 354         */
 355         template <typename Q>
 356         std::pair<iterator, bool> update( Q const& val, bool bAllowInsert = true )
 357         {
 358             std::pair< node_type *, bool > ret = update_at( head(), val, bAllowInsert );
 359             return std::make_pair( node_to_iterator( ret.first ), ret.second );
 360         }
 361         //@cond
 362         template <typename Q>
 363         CDS_DEPRECATED("ensure() is deprecated, use update()")
 364         std::pair<iterator, bool> ensure( Q const& val )
 365         {
 366             return update( val, true );
 367         }
 368         //@endcond
 369
 370         /// Checks whether the list contains \p key
 371         /**
 372             The function searches the item with key equal to \p key
 373             and returns an iterator pointed to item found if the key is found,
 374             and \ref end() otherwise
 375         */
 376         template <typename Q>
 377         iterator contains( Q const& key )
 378         {
 379             return node_to_iterator( find_at( head(), key, intrusive_key_comparator() ));
 380         }
 381         //@cond
 382         template <typename Q>
 383         CDS_DEPRECATED("deprecated, use contains()")
 384         iterator find( Q const& key )
 385         {
 386             return contains( key );
 387         }
 388         //@endcond
 389
 390         /// Checks whether the map contains \p key using \p pred predicate for searching (ordered list version)
 391         /**
 392             The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
 393             \p Less functor has the interface like \p std::less.
 394             \p Less must imply the same element order as the comparator used for building the list.
 395         */
 396         template <typename Q, typename Less, bool Sort = c_bSort>
 397         typename std::enable_if<Sort, iterator>::type contains( Q const& key, Less pred )
 398         {
 399             CDS_UNUSED( pred );
 400             return node_to_iterator( find_at( head(), key, typename maker::template less_wrapper<Less>::type() ));
 401         }
 402         //@cond
 403         template <typename Q, typename Less, bool Sort = c_bSort>
 404         CDS_DEPRECATED("deprecated, use contains()")
 405         typename std::enable_if<Sort, iterator>::type find_with( Q const& key, Less pred )
 406         {
 407             return contains( key, pred );
 408         }
 409         //@endcond
 410
 411         /// Finds the key \p val using \p equal predicate for searching (unordered list version)
 412         /**
 413             The function is an analog of <tt>contains( key )</tt> but \p equal is used for key comparing.
 414             \p Equal functor has the interface like \p std::equal_to.
 415         */
 416         template <typename Q, typename Equal, bool Sort = c_bSort>
 417         typename std::enable_if<!Sort, iterator>::type contains( Q const& key, Equal equal )
 418         {
 419             CDS_UNUSED( equal );
 420             return node_to_iterator( find_at( head(), key, typename maker::template equal_to_wrapper<Equal>::type() ));
 421         }
 422         //@cond
 423         template <typename Q, typename Equal, bool Sort = c_bSort>
 424         CDS_DEPRECATED("deprecated, use contains()")
 425         typename std::enable_if<!Sort, iterator>::type find_with( Q const& key, Equal equal )
 426         {
 427             return contains( key, equal );
 428         }
 429         //@endcond
 430
 431         /// Check if the list is empty
 432         bool empty() const
 433         {
 434             return base_class::empty();
 435         }
 436
 437         /// Returns list's item count
 438         /**
 439             The value returned depends on \p Traits::item_counter type. For \p atomicity::empty_item_counter,
 440             this function always returns 0.
 441
 442             @note Even if you use real item counter and it returns 0, this fact is not mean that the list
 443             is empty. To check list emptyness use \ref empty() method.
 444         */
 445         size_t size() const
 446         {
 447             return base_class::size();
 448         }
 449
 450         /// Returns const reference to internal statistics
 451         stat const& statistics() const
 452         {
 453             return base_class::statistics();
 454         }
 455
 456         /// Clears the list
 457         void clear()
 458         {
 459             base_class::clear();
 460         }
 461
 462     protected:
 463         //@cond
 464         iterator insert_node( node_type * pNode )
 465         {
 466             return node_to_iterator( insert_node_at( head(), pNode ));
 467         }
 468
 469         node_type * insert_node_at( head_type& refHead, node_type * pNode )
 470         {
 471             assert( pNode != nullptr );
 472             scoped_node_ptr p( pNode );
 473             if ( base_class::insert_at( &refHead, *p ))
 474                 return p.release();
 475
 476             return nullptr;
 477         }
 478
 479         template <typename Q>
 480         node_type * insert_at( head_type& refHead, Q const& val )
 481         {
 482             return insert_node_at( refHead, alloc_node( val ));
 483         }
 484
 485         template <typename... Args>
 486         node_type * emplace_at( head_type& refHead, Args&&... args )
 487         {
 488             return insert_node_at( refHead, alloc_node( std::forward<Args>(args)... ));
 489         }
 490
 491         template <typename Q>
 492         std::pair< node_type *, bool > update_at( head_type& refHead, Q const& val, bool bAllowInsert )
 493         {
 494             scoped_node_ptr pNode( alloc_node( val ));
 495             node_type * pItemFound = nullptr;
 496
 497             std::pair<bool, bool> ret = base_class::update_at( &refHead, *pNode,
 498                 [&pItemFound](bool, node_type& item, node_type&){ pItemFound = &item; },
 499                 bAllowInsert );
 500
 501             if ( ret.second )
 502                 pNode.release();
 503
 504             return std::make_pair( pItemFound, ret.second );
 505         }
 506
 507         template <typename Q, typename Compare>
 508         node_type * find_at( head_type& refHead, Q const& key, Compare cmp )
 509         {
 510             return base_class::find_at( &refHead, key, cmp );
 511         }
 512
 513         //@endcond
 514     };
 515 }} // namespace cds::container
 516
 517 #endif // #ifndef CDSLIB_CONTAINER_LAZY_LIST_NOGC_H