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