cds/container/lazy_list_nogc.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_CONTAINER_LAZY_LIST_NOGC_H
   4 #define __CDS_CONTAINER_LAZY_LIST_NOGC_H
   5
   6 #include <memory>
   7 #include <cds/container/details/lazy_list_base.h>
   8 #include <cds/intrusive/lazy_list_nogc.h>
   9 #include <cds/container/details/make_lazy_list.h>
  10
  11 namespace cds { namespace container {
  12
  13     /// Lazy ordered single-linked list (template specialization for gc::nogc)
  14     /** @ingroup cds_nonintrusive_list
  15         \anchor cds_nonintrusive_LazyList_nogc
  16
  17         This specialization is so-called append-only when no item
  18         reclamation may be performed. The class does not support deleting of list item.
  19
  20         @copydetails cds_nonintrusive_LazyList_gc
  21     */
  22     template <
  23         typename T,
  24 #ifdef CDS_DOXYGEN_INVOKED
  25         typename Traits = lazy_list::traits
  26 #else
  27         typename Traits
  28 #endif
  29     >
  30     class LazyList<cds::gc::nogc, T, Traits>:
  31 #ifdef CDS_DOXYGEN_INVOKED
  32         protected intrusive::LazyList< gc::nogc, T, Traits >
  33 #else
  34         protected details::make_lazy_list< cds::gc::nogc, T, Traits >::type
  35 #endif
  36     {
  37         //@cond
  38         typedef details::make_lazy_list< cds::gc::nogc, T, Traits > maker;
  39         typedef typename maker::type  base_class;
  40         //@endcond
  41
  42     public:
  43         typedef cds::gc::nogc gc;  ///< Garbage collector
  44         typedef T      value_type; ///< Type of value stored in the list
  45         typedef Traits traits;     ///< List traits
  46
  47         typedef typename base_class::back_off     back_off;       ///< Back-off strategy used
  48         typedef typename maker::allocator_type    allocator_type; ///< Allocator type used for allocate/deallocate the nodes
  49         typedef typename base_class::item_counter item_counter;   ///< Item counting policy used
  50         typedef typename maker::key_comparator    key_comparator; ///< key comparison functor
  51         typedef typename base_class::memory_model memory_model;   ///< Memory ordering. See cds::opt::memory_model option
  52
  53     protected:
  54         //@cond
  55         typedef typename base_class::value_type   node_type;
  56         typedef typename maker::cxx_allocator     cxx_allocator;
  57         typedef typename maker::node_deallocator  node_deallocator;
  58         typedef typename maker::intrusive_traits::compare intrusive_key_comparator;
  59
  60         typedef typename base_class::node_type      head_type;
  61         //@endcond
  62
  63     protected:
  64         //@cond
  65         static node_type * alloc_node()
  66         {
  67             return cxx_allocator().New();
  68         }
  69
  70         static node_type * alloc_node( value_type const& v )
  71         {
  72             return cxx_allocator().New( v );
  73         }
  74
  75         template <typename... Args>
  76         static node_type * alloc_node( Args&&... args )
  77         {
  78             return cxx_allocator().MoveNew( std::forward<Args>(args)... );
  79         }
  80
  81         static void free_node( node_type * pNode )
  82         {
  83             cxx_allocator().Delete( pNode );
  84         }
  85
  86         struct node_disposer {
  87             void operator()( node_type * pNode )
  88             {
  89                 free_node( pNode );
  90             }
  91         };
  92         typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
  93
  94         head_type& head()
  95         {
  96             return base_class::m_Head;
  97         }
  98
  99         head_type const& head() const
 100         {
 101             return base_class::m_Head;
 102         }
 103
 104         head_type& tail()
 105         {
 106             return base_class::m_Tail;
 107         }
 108
 109         head_type const& tail() const
 110         {
 111             return base_class::m_Tail;
 112         }
 113         //@endcond
 114
 115     protected:
 116         //@cond
 117         template <bool IsConst>
 118         class iterator_type: protected base_class::template iterator_type<IsConst>
 119         {
 120             typedef typename base_class::template iterator_type<IsConst>    iterator_base;
 121
 122             iterator_type( head_type const& pNode )
 123                 : iterator_base( const_cast<head_type *>(&pNode) )
 124             {}
 125
 126             explicit iterator_type( const iterator_base& it )
 127                 : iterator_base( it )
 128             {}
 129
 130             friend class LazyList;
 131
 132         protected:
 133             explicit iterator_type( node_type& pNode )
 134                 : iterator_base( &pNode )
 135             {}
 136
 137         public:
 138             typedef typename cds::details::make_const_type<value_type, IsConst>::pointer   value_ptr;
 139             typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
 140
 141             iterator_type()
 142             {}
 143
 144             iterator_type( const iterator_type& src )
 145                 : iterator_base( src )
 146             {}
 147
 148             value_ptr operator ->() const
 149             {
 150                 typename iterator_base::value_ptr p = iterator_base::operator ->();
 151                 return p ? &(p->m_Value) : nullptr;
 152             }
 153
 154             value_ref operator *() const
 155             {
 156                 return (iterator_base::operator *()).m_Value;
 157             }
 158
 159             /// Pre-increment
 160             iterator_type& operator ++()
 161             {
 162                 iterator_base::operator ++();
 163                 return *this;
 164             }
 165
 166             /// Post-increment
 167             iterator_type operator ++(int)
 168             {
 169                 return iterator_base::operator ++(0);
 170             }
 171
 172             template <bool C>
 173             bool operator ==(iterator_type<C> const& i ) const
 174             {
 175                 return iterator_base::operator ==(i);
 176             }
 177             template <bool C>
 178             bool operator !=(iterator_type<C> const& i ) const
 179             {
 180                 return iterator_base::operator !=(i);
 181             }
 182         };
 183         //@endcond
 184
 185     public:
 186         /// Returns a forward iterator addressing the first element in a list
 187         /**
 188             For empty list \code begin() == end() \endcode
 189         */
 190         typedef iterator_type<false>    iterator;
 191
 192         /// Const forward iterator
 193         /**
 194             For iterator's features and requirements see \ref iterator
 195         */
 196         typedef iterator_type<true>     const_iterator;
 197
 198         /// Returns a forward iterator addressing the first element in a list
 199         /**
 200             For empty list \code begin() == end() \endcode
 201         */
 202         iterator begin()
 203         {
 204             iterator it( head() );
 205             ++it    ;   // skip dummy head node
 206             return it;
 207         }
 208
 209         /// Returns an iterator that addresses the location succeeding the last element in a list
 210         /**
 211             Do not use the value returned by <tt>end</tt> function to access any item.
 212
 213             The returned value can be used only to control reaching the end of the list.
 214             For empty list \code begin() == end() \endcode
 215         */
 216         iterator end()
 217         {
 218             return iterator( tail());
 219         }
 220
 221         /// Returns a forward const iterator addressing the first element in a list
 222         //@{
 223         const_iterator begin() const
 224         {
 225             const_iterator it( head() );
 226             ++it    ;   // skip dummy head node
 227             return it;
 228         }
 229         const_iterator cbegin() const
 230         {
 231             const_iterator it( head() );
 232             ++it    ;   // skip dummy head node
 233             return it;
 234         }
 235         //@}
 236
 237         /// Returns an const iterator that addresses the location succeeding the last element in a list
 238         //@{
 239         const_iterator end() const
 240         {
 241             return const_iterator( tail());
 242         }
 243         const_iterator cend() const
 244         {
 245             return const_iterator( tail());
 246         }
 247         //@}
 248
 249     protected:
 250         //@cond
 251         iterator node_to_iterator( node_type * pNode )
 252         {
 253             if ( pNode )
 254                 return iterator( *pNode );
 255             return end();
 256         }
 257         //@endcond
 258
 259     public:
 260         /// Default constructor
 261         LazyList()
 262         {}
 263
 264         /// Desctructor clears the list
 265         ~LazyList()
 266         {
 267             clear();
 268         }
 269
 270         /// Inserts new node
 271         /**
 272             The function inserts \p val in the list if the list does not contain
 273             an item with key equal to \p val.
 274
 275             Return an iterator pointing to inserted item if success \ref end() otherwise
 276         */
 277         template <typename Q>
 278         iterator insert( Q const& val )
 279         {
 280             return node_to_iterator( insert_at( head(), val ) );
 281         }
 282
 283         /// Inserts data of type \p value_type created from \p args
 284         /**
 285             Return an iterator pointing to inserted item if success \ref end() otherwise
 286         */
 287         template <typename... Args>
 288         iterator emplace( Args&&... args )
 289         {
 290             return node_to_iterator( emplace_at( head(), std::forward<Args>(args)... ));
 291         }
 292
 293         /// Ensures that the item \p val exists in the list
 294         /**
 295             The operation inserts new item if the key \p val is not found in the list.
 296             Otherwise, the function returns an iterator that points to item found.
 297
 298             Returns <tt> std::pair<iterator, bool>  </tt> where \p first is an iterator pointing to
 299             item found or inserted, \p second is \p true if new item has been added or \p false if the item
 300             already is in the list.
 301         */
 302         template <typename Q>
 303         std::pair<iterator, bool> ensure( Q const& val )
 304         {
 305             std::pair< node_type *, bool > ret = ensure_at( head(), val );
 306             return std::make_pair( node_to_iterator( ret.first ), ret.second );
 307         }
 308
 309         /// Find the key \p val
 310         /** \anchor cds_nonintrusive_LazyList_nogc_find
 311             The function searches the item with key equal to \p val
 312             and returns an iterator pointed to item found if the key is found,
 313             and \ref end() otherwise
 314         */
 315         template <typename Q>
 316         iterator find( Q const& key )
 317         {
 318             return node_to_iterator( find_at( head(), key, intrusive_key_comparator() ));
 319         }
 320
 321         /// Finds the key \p val using \p pred predicate for searching
 322         /**
 323             The function is an analog of \ref cds_nonintrusive_LazyList_nogc_find "find(Q const&)"
 324             but \p pred is used for key comparing.
 325             \p Less functor has the interface like \p std::less.
 326             \p pred must imply the same element order as the comparator used for building the list.
 327         */
 328         template <typename Q, typename Less>
 329         iterator find_with( Q const& key, Less pred )
 330         {
 331             CDS_UNUSED( pred );
 332             return node_to_iterator( find_at( head(), key, typename maker::template less_wrapper<Less>::type() ));
 333         }
 334
 335         /// Check if the list is empty
 336         bool empty() const
 337         {
 338             return base_class::empty();
 339         }
 340
 341         /// Returns list's item count
 342         /**
 343             The value returned depends on \p Traits::item_counter type. For \p atomicity::empty_item_counter,
 344             this function always returns 0.
 345
 346             @note Even if you use real item counter and it returns 0, this fact is not mean that the list
 347             is empty. To check list emptyness use \ref empty() method.
 348         */
 349         size_t size() const
 350         {
 351             return base_class::size();
 352         }
 353
 354         /// Clears the list
 355         void clear()
 356         {
 357             base_class::clear();
 358         }
 359
 360     protected:
 361         //@cond
 362         node_type * insert_node_at( head_type& refHead, node_type * pNode )
 363         {
 364             assert( pNode != nullptr );
 365             scoped_node_ptr p( pNode );
 366             if ( base_class::insert_at( &refHead, *p ))
 367                 return p.release();
 368
 369             return nullptr;
 370         }
 371
 372         template <typename Q>
 373         node_type * insert_at( head_type& refHead, Q const& val )
 374         {
 375             return insert_node_at( refHead, alloc_node( val ));
 376         }
 377
 378         template <typename... Args>
 379         node_type * emplace_at( head_type& refHead, Args&&... args )
 380         {
 381             return insert_node_at( refHead, alloc_node( std::forward<Args>(args)... ));
 382         }
 383
 384         template <typename Q>
 385         std::pair< node_type *, bool > ensure_at( head_type& refHead, Q const& val )
 386         {
 387             scoped_node_ptr pNode( alloc_node( val ));
 388             node_type * pItemFound = nullptr;
 389
 390             std::pair<bool, bool> ret = base_class::ensure_at( &refHead, *pNode,
 391                 [&pItemFound](bool, node_type& item, node_type&){ pItemFound = &item; });
 392             assert( pItemFound != nullptr );
 393
 394             if ( ret.first && ret.second )
 395                 pNode.release();
 396
 397             return std::make_pair( pItemFound, ret.second );
 398         }
 399
 400         template <typename Q, typename Compare>
 401         node_type * find_at( head_type& refHead, Q const& key, Compare cmp )
 402         {
 403             return base_class::find_at( &refHead, key, cmp );
 404         }
 405
 406         //@endcond
 407     };
 408 }} // namespace cds::container
 409
 410 #endif // #ifndef __CDS_CONTAINER_LAZY_LIST_NOGC_H