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