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