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     ///@name Forward iterators
 221     //@{
 222         /// Returns a forward iterator addressing the first element in a list
 223         /**
 224             For empty list \code begin() == end() \endcode
 225         */
 226         typedef iterator_type<false>    iterator;
 227
 228         /// Const forward iterator
 229         /**
 230             For iterator's features and requirements see \ref iterator
 231         */
 232         typedef iterator_type<true>     const_iterator;
 233
 234         /// Returns a forward iterator addressing the first element in a list
 235         /**
 236             For empty list \code begin() == end() \endcode
 237         */
 238         iterator begin()
 239         {
 240             iterator it( head() );
 241             ++it    ;   // skip dummy head node
 242             return it;
 243         }
 244
 245         /// Returns an iterator that addresses the location succeeding the last element in a list
 246         /**
 247             Do not use the value returned by <tt>end</tt> function to access any item.
 248
 249             The returned value can be used only to control reaching the end of the list.
 250             For empty list \code begin() == end() \endcode
 251         */
 252         iterator end()
 253         {
 254             return iterator( tail());
 255         }
 256
 257         /// Returns a forward const iterator addressing the first element in a list
 258         const_iterator begin() const
 259         {
 260             const_iterator it( head() );
 261             ++it    ;   // skip dummy head node
 262             return it;
 263         }
 264
 265         /// Returns a forward const iterator addressing the first element in a list
 266         const_iterator cbegin() const
 267         {
 268             const_iterator it( head() );
 269             ++it    ;   // skip dummy head node
 270             return it;
 271         }
 272
 273         /// Returns an const iterator that addresses the location succeeding the last element in a list
 274         const_iterator end() const
 275         {
 276             return const_iterator( tail());
 277         }
 278
 279         /// Returns an const iterator that addresses the location succeeding the last element in a list
 280         const_iterator cend() const
 281         {
 282             return const_iterator( tail());
 283         }
 284     //@}
 285
 286     protected:
 287         //@cond
 288         iterator node_to_iterator( node_type * pNode )
 289         {
 290             if ( pNode )
 291                 return iterator( *pNode );
 292             return end();
 293         }
 294         //@endcond
 295
 296     public:
 297         /// Default constructor
 298         LazyList()
 299         {}
 300
 301         /// Desctructor clears the list
 302         ~LazyList()
 303         {
 304             clear();
 305         }
 306
 307         /// Inserts new node
 308         /**
 309             The function inserts \p val in the list if the list does not contain
 310             an item with key equal to \p val.
 311
 312             Return an iterator pointing to inserted item if success \ref end() otherwise
 313         */
 314         template <typename Q>
 315         iterator insert( Q const& val )
 316         {
 317             return node_to_iterator( insert_at( head(), val ) );
 318         }
 319
 320         /// Inserts data of type \p value_type created from \p args
 321         /**
 322             Return an iterator pointing to inserted item if success \ref end() otherwise
 323         */
 324         template <typename... Args>
 325         iterator emplace( Args&&... args )
 326         {
 327             return node_to_iterator( emplace_at( head(), std::forward<Args>(args)... ));
 328         }
 329
 330         /// Updates the item
 331         /**
 332             If \p key is not in the list and \p bAllowInsert is \p true,
 333
 334             the function inserts a new item.
 335             Otherwise, the function returns an iterator pointing to the item found.
 336
 337             Returns <tt> std::pair<iterator, bool>  </tt> where \p first is an iterator pointing to
 338             item found or inserted, \p second is true if new item has been added or \p false if the item
 339             already is in the list.
 340         */
 341         template <typename Q>
 342         std::pair<iterator, bool> update( Q const& val, bool bAllowInsert = true )
 343         {
 344             std::pair< node_type *, bool > ret = update_at( head(), val, bAllowInsert );
 345             return std::make_pair( node_to_iterator( ret.first ), ret.second );
 346         }
 347         //@cond
 348         template <typename Q>
 349         CDS_DEPRECATED("ensure() is deprecated, use update()")
 350         std::pair<iterator, bool> ensure( Q const& val )
 351         {
 352             return update( val, true );
 353         }
 354         //@endcond
 355
 356         /// Checks whether the list contains \p key
 357         /**
 358             The function searches the item with key equal to \p key
 359             and returns an iterator pointed to item found if the key is found,
 360             and \ref end() otherwise
 361         */
 362         template <typename Q>
 363         iterator contains( Q const& key )
 364         {
 365             return node_to_iterator( find_at( head(), key, intrusive_key_comparator() ));
 366         }
 367         //@cond
 368         template <typename Q>
 369         CDS_DEPRECATED("deprecated, use contains()")
 370         iterator find( Q const& key )
 371         {
 372             return contains( key );
 373         }
 374         //@endcond
 375
 376         /// Checks whether the map contains \p key using \p pred predicate for searching (ordered list version)
 377         /**
 378             The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
 379             \p Less functor has the interface like \p std::less.
 380             \p Less must imply the same element order as the comparator used for building the list.
 381         */
 382         template <typename Q, typename Less, bool Sort = c_bSort>
 383         typename std::enable_if<Sort, iterator>::type contains( Q const& key, Less pred )
 384         {
 385             CDS_UNUSED( pred );
 386             return node_to_iterator( find_at( head(), key, typename maker::template less_wrapper<Less>::type() ));
 387         }
 388         //@cond
 389         template <typename Q, typename Less, bool Sort = c_bSort>
 390         CDS_DEPRECATED("deprecated, use contains()")
 391         typename std::enable_if<Sort, iterator>::type find_with( Q const& key, Less pred )
 392         {
 393             return contains( key, pred );
 394         }
 395         //@endcond
 396
 397         /// Finds the key \p val using \p equal predicate for searching (unordered list version)
 398         /**
 399             The function is an analog of <tt>contains( key )</tt> but \p equal is used for key comparing.
 400             \p Equal functor has the interface like \p std::equal_to.
 401         */
 402         template <typename Q, typename Equal, bool Sort = c_bSort>
 403         typename std::enable_if<!Sort, iterator>::type contains( Q const& key, Equal equal )
 404         {
 405             CDS_UNUSED( equal );
 406             return node_to_iterator( find_at( head(), key, typename maker::template equal_to_wrapper<Equal>::type() ));
 407         }
 408         //@cond
 409         template <typename Q, typename Equal, bool Sort = c_bSort>
 410         CDS_DEPRECATED("deprecated, use contains()")
 411         typename std::enable_if<!Sort, iterator>::type find_with( Q const& key, Equal equal )
 412         {
 413             return contains( key, equal );
 414         }
 415         //@endcond
 416
 417         /// Check if the list is empty
 418         bool empty() const
 419         {
 420             return base_class::empty();
 421         }
 422
 423         /// Returns list's item count
 424         /**
 425             The value returned depends on \p Traits::item_counter type. For \p atomicity::empty_item_counter,
 426             this function always returns 0.
 427
 428             @note Even if you use real item counter and it returns 0, this fact is not mean that the list
 429             is empty. To check list emptyness use \ref empty() method.
 430         */
 431         size_t size() const
 432         {
 433             return base_class::size();
 434         }
 435
 436         /// Clears the list
 437         void clear()
 438         {
 439             base_class::clear();
 440         }
 441
 442     protected:
 443         //@cond
 444         node_type * insert_node_at( head_type& refHead, node_type * pNode )
 445         {
 446             assert( pNode != nullptr );
 447             scoped_node_ptr p( pNode );
 448             if ( base_class::insert_at( &refHead, *p ))
 449                 return p.release();
 450
 451             return nullptr;
 452         }
 453
 454         template <typename Q>
 455         node_type * insert_at( head_type& refHead, Q const& val )
 456         {
 457             return insert_node_at( refHead, alloc_node( val ));
 458         }
 459
 460         template <typename... Args>
 461         node_type * emplace_at( head_type& refHead, Args&&... args )
 462         {
 463             return insert_node_at( refHead, alloc_node( std::forward<Args>(args)... ));
 464         }
 465
 466         template <typename Q>
 467         std::pair< node_type *, bool > update_at( head_type& refHead, Q const& val, bool bAllowInsert )
 468         {
 469             scoped_node_ptr pNode( alloc_node( val ));
 470             node_type * pItemFound = nullptr;
 471
 472             std::pair<bool, bool> ret = base_class::update_at( &refHead, *pNode,
 473                 [&pItemFound](bool, node_type& item, node_type&){ pItemFound = &item; },
 474                 bAllowInsert );
 475
 476             if ( ret.second )
 477                 pNode.release();
 478
 479             return std::make_pair( pItemFound, ret.second );
 480         }
 481
 482         template <typename Q, typename Compare>
 483         node_type * find_at( head_type& refHead, Q const& key, Compare cmp )
 484         {
 485             return base_class::find_at( &refHead, key, cmp );
 486         }
 487
 488         //@endcond
 489     };
 490 }} // namespace cds::container
 491
 492 #endif // #ifndef CDSLIB_CONTAINER_LAZY_LIST_NOGC_H