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