cds/container/lazy_list_nogc.h

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