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         /// Ensures that the item \p val exists in the list
 300         /**
 301             The operation inserts new item if the key \p val is not found in the list.
 302             Otherwise, the function returns an iterator that points to item found.
 303
 304             Returns <tt> std::pair<iterator, bool>  </tt> where \p first is an iterator pointing to
 305             item found or inserted, \p second is \p true if new item has been added or \p false if the item
 306             already is in the list.
 307         */
 308         template <typename Q>
 309         std::pair<iterator, bool> ensure( Q const& val )
 310         {
 311             std::pair< node_type *, bool > ret = ensure_at( head(), val );
 312             return std::make_pair( node_to_iterator( ret.first ), ret.second );
 313         }
 314
 315         /// Find the key \p val
 316         /** \anchor cds_nonintrusive_LazyList_nogc_find
 317             The function searches the item with key equal to \p val
 318             and returns an iterator pointed to item found if the key is found,
 319             and \ref end() otherwise
 320         */
 321         template <typename Q>
 322         iterator find( Q const& key )
 323         {
 324             return node_to_iterator( find_at( head(), key, intrusive_key_comparator() ));
 325         }
 326
 327         /// Finds the key \p val using \p pred predicate for searching (only for ordered list)
 328         /**
 329             The function is an analog of \ref cds_nonintrusive_LazyList_nogc_find "find(Q const&)"
 330             but \p pred is used for key comparing.
 331             \p Less functor has the interface like \p std::less.
 332             \p pred must imply the same element order as the comparator used for building the list.
 333         */
 334         template <typename Q, typename Less, bool Sort = c_bSort>
 335         typename std::enable_if<Sort, iterator>::type find_with( Q const& key, Less pred )
 336         {
 337             CDS_UNUSED( pred );
 338             return node_to_iterator( find_at( head(), key, typename maker::template less_wrapper<Less>::type() ));
 339         }
 340
 341         /// Finds the key \p val using \p equal predicate for searching (only for unordered list)
 342         /**
 343             The function is an analog of \ref cds_nonintrusive_LazyList_nogc_find "find(Q const&)"
 344             but \p pred is used for key comparing.
 345             \p Equal functor has the interface like \p std::equal_to.
 346         */
 347         template <typename Q, typename Equal, bool Sort = c_bSort>
 348         typename std::enable_if<!Sort, iterator>::type find_with( Q const& key, Equal equal )
 349         {
 350             CDS_UNUSED( equal );
 351             return node_to_iterator( find_at( head(), key, typename maker::template equal_to_wrapper<Equal>::type() ));
 352         }
 353
 354         /// Check if the list is empty
 355         bool empty() const
 356         {
 357             return base_class::empty();
 358         }
 359
 360         /// Returns list's item count
 361         /**
 362             The value returned depends on \p Traits::item_counter type. For \p atomicity::empty_item_counter,
 363             this function always returns 0.
 364
 365             @note Even if you use real item counter and it returns 0, this fact is not mean that the list
 366             is empty. To check list emptyness use \ref empty() method.
 367         */
 368         size_t size() const
 369         {
 370             return base_class::size();
 371         }
 372
 373         /// Clears the list
 374         void clear()
 375         {
 376             base_class::clear();
 377         }
 378
 379     protected:
 380         //@cond
 381         node_type * insert_node_at( head_type& refHead, node_type * pNode )
 382         {
 383             assert( pNode != nullptr );
 384             scoped_node_ptr p( pNode );
 385             if ( base_class::insert_at( &refHead, *p ))
 386                 return p.release();
 387
 388             return nullptr;
 389         }
 390
 391         template <typename Q>
 392         node_type * insert_at( head_type& refHead, Q const& val )
 393         {
 394             return insert_node_at( refHead, alloc_node( val ));
 395         }
 396
 397         template <typename... Args>
 398         node_type * emplace_at( head_type& refHead, Args&&... args )
 399         {
 400             return insert_node_at( refHead, alloc_node( std::forward<Args>(args)... ));
 401         }
 402
 403         template <typename Q>
 404         std::pair< node_type *, bool > ensure_at( head_type& refHead, Q const& val )
 405         {
 406             scoped_node_ptr pNode( alloc_node( val ));
 407             node_type * pItemFound = nullptr;
 408
 409             std::pair<bool, bool> ret = base_class::ensure_at( &refHead, *pNode,
 410                 [&pItemFound](bool, node_type& item, node_type&){ pItemFound = &item; });
 411             assert( pItemFound != nullptr );
 412
 413             if ( ret.first && ret.second )
 414                 pNode.release();
 415
 416             return std::make_pair( pItemFound, ret.second );
 417         }
 418
 419         template <typename Q, typename Compare>
 420         node_type * find_at( head_type& refHead, Q const& key, Compare cmp )
 421         {
 422             return base_class::find_at( &refHead, key, cmp );
 423         }
 424
 425         //@endcond
 426     };
 427 }} // namespace cds::container
 428
 429 #endif // #ifndef CDSLIB_CONTAINER_LAZY_LIST_NOGC_H