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