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 <cds/container/lazy_list_base.h>
   7 #include <cds/intrusive/lazy_list_nogc.h>
   8 #include <cds/container/details/make_lazy_list.h>
   9 #include <cds/details/std/memory.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 #   ifndef CDS_CXX11_LAMBDA_SUPPORT
  82         struct ensure_functor
  83         {
  84             node_type * m_pItemFound;
  85
  86             ensure_functor()
  87                 : m_pItemFound( nullptr )
  88             {}
  89
  90             void operator ()(bool, node_type& item, node_type& )
  91             {
  92                 m_pItemFound = &item;
  93             }
  94         };
  95 #   endif
  96         //@endcond
  97
  98     protected:
  99         //@cond
 100         static node_type * alloc_node()
 101         {
 102             return cxx_allocator().New();
 103         }
 104
 105         static node_type * alloc_node( value_type const& v )
 106         {
 107             return cxx_allocator().New( v );
 108         }
 109
 110 #   ifdef CDS_EMPLACE_SUPPORT
 111         template <typename... Args>
 112         static node_type * alloc_node( Args&&... args )
 113         {
 114             return cxx_allocator().MoveNew( std::forward<Args>(args)... );
 115         }
 116 #   endif
 117
 118         static void free_node( node_type * pNode )
 119         {
 120             cxx_allocator().Delete( pNode );
 121         }
 122
 123         struct node_disposer {
 124             void operator()( node_type * pNode )
 125             {
 126                 free_node( pNode );
 127             }
 128         };
 129         typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
 130
 131         head_type& head()
 132         {
 133             return base_class::m_Head;
 134         }
 135
 136         head_type const& head() const
 137         {
 138             return base_class::m_Head;
 139         }
 140
 141         head_type& tail()
 142         {
 143             return base_class::m_Tail;
 144         }
 145
 146         head_type const& tail() const
 147         {
 148             return base_class::m_Tail;
 149         }
 150         //@endcond
 151
 152     protected:
 153         //@cond
 154         template <bool IsConst>
 155         class iterator_type: protected base_class::template iterator_type<IsConst>
 156         {
 157             typedef typename base_class::template iterator_type<IsConst>    iterator_base;
 158
 159             iterator_type( head_type const& pNode )
 160                 : iterator_base( const_cast<head_type *>(&pNode) )
 161             {}
 162
 163             explicit iterator_type( const iterator_base& it )
 164                 : iterator_base( it )
 165             {}
 166
 167             friend class LazyList;
 168
 169         protected:
 170             explicit iterator_type( node_type& pNode )
 171                 : iterator_base( &pNode )
 172             {}
 173
 174         public:
 175             typedef typename cds::details::make_const_type<value_type, IsConst>::pointer   value_ptr;
 176             typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
 177
 178             iterator_type()
 179             {}
 180
 181             iterator_type( const iterator_type& src )
 182                 : iterator_base( src )
 183             {}
 184
 185             value_ptr operator ->() const
 186             {
 187                 typename iterator_base::value_ptr p = iterator_base::operator ->();
 188                 return p ? &(p->m_Value) : nullptr;
 189             }
 190
 191             value_ref operator *() const
 192             {
 193                 return (iterator_base::operator *()).m_Value;
 194             }
 195
 196             /// Pre-increment
 197             iterator_type& operator ++()
 198             {
 199                 iterator_base::operator ++();
 200                 return *this;
 201             }
 202
 203             /// Post-increment
 204             iterator_type operator ++(int)
 205             {
 206                 return iterator_base::operator ++(0);
 207             }
 208
 209             template <bool C>
 210             bool operator ==(iterator_type<C> const& i ) const
 211             {
 212                 return iterator_base::operator ==(i);
 213             }
 214             template <bool C>
 215             bool operator !=(iterator_type<C> const& i ) const
 216             {
 217                 return iterator_base::operator !=(i);
 218             }
 219         };
 220         //@endcond
 221
 222     public:
 223         /// Returns a forward iterator addressing the first element in a list
 224         /**
 225             For empty list \code begin() == end() \endcode
 226         */
 227         typedef iterator_type<false>    iterator;
 228
 229         /// Const forward iterator
 230         /**
 231             For iterator's features and requirements see \ref iterator
 232         */
 233         typedef iterator_type<true>     const_iterator;
 234
 235         /// Returns a forward iterator addressing the first element in a list
 236         /**
 237             For empty list \code begin() == end() \endcode
 238         */
 239         iterator begin()
 240         {
 241             iterator it( head() );
 242             ++it    ;   // skip dummy head node
 243             return it;
 244         }
 245
 246         /// Returns an iterator that addresses the location succeeding the last element in a list
 247         /**
 248             Do not use the value returned by <tt>end</tt> function to access any item.
 249
 250             The returned value can be used only to control reaching the end of the list.
 251             For empty list \code begin() == end() \endcode
 252         */
 253         iterator end()
 254         {
 255             return iterator( tail());
 256         }
 257
 258         /// Returns a forward const iterator addressing the first element in a list
 259         //@{
 260         const_iterator begin() const
 261         {
 262             const_iterator it( head() );
 263             ++it    ;   // skip dummy head node
 264             return it;
 265         }
 266         const_iterator cbegin()
 267         {
 268             const_iterator it( head() );
 269             ++it    ;   // skip dummy head node
 270             return it;
 271         }
 272         //@}
 273
 274         /// Returns an const iterator that addresses the location succeeding the last element in a list
 275         //@{
 276         const_iterator end() const
 277         {
 278             return const_iterator( tail());
 279         }
 280         const_iterator cend()
 281         {
 282             return const_iterator( tail());
 283         }
 284         //@}
 285
 286     protected:
 287         //@cond
 288         iterator node_to_iterator( node_type * pNode )
 289         {
 290             if ( pNode )
 291                 return iterator( *pNode );
 292             return end();
 293         }
 294         //@endcond
 295
 296     public:
 297         /// Default constructor
 298         /**
 299             Initialize empty list
 300         */
 301         LazyList()
 302         {}
 303
 304         /// List desctructor
 305         /**
 306             Clears the list
 307         */
 308         ~LazyList()
 309         {
 310             clear();
 311         }
 312
 313         /// Inserts new node
 314         /**
 315             The function inserts \p val in the list if the list does not contain
 316             an item with key equal to \p val.
 317
 318             Return an iterator pointing to inserted item if success \ref end() otherwise
 319         */
 320         template <typename Q>
 321         iterator insert( Q const& val )
 322         {
 323             return node_to_iterator( insert_at( head(), val ) );
 324         }
 325
 326 #   ifdef CDS_EMPLACE_SUPPORT
 327         /// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
 328         /**
 329             Return an iterator pointing to inserted item if success \ref end() otherwise
 330
 331             This function is available only for compiler that supports
 332             variadic template and move semantics
 333         */
 334         template <typename... Args>
 335         iterator emplace( Args&&... args )
 336         {
 337             return node_to_iterator( emplace_at( head(), std::forward<Args>(args)... ));
 338         }
 339 #   endif
 340
 341         /// Ensures that the item \p val exists in the list
 342         /**
 343             The operation inserts new item if the key \p val is not found in the list.
 344             Otherwise, the function returns an iterator that points to item found.
 345
 346             Returns <tt> std::pair<iterator, bool>  </tt> where \p first is an iterator pointing to
 347             item found or inserted, \p second is true if new item has been added or \p false if the item
 348             already is in the list.
 349         */
 350         template <typename Q>
 351         std::pair<iterator, bool> ensure( Q const& val )
 352         {
 353             std::pair< node_type *, bool > ret = ensure_at( head(), val );
 354             return std::make_pair( node_to_iterator( ret.first ), ret.second );
 355         }
 356
 357         /// Find the key \p val
 358         /** \anchor cds_nonintrusive_LazyList_nogc_find
 359             The function searches the item with key equal to \p val
 360             and returns an iterator pointed to item found if the key is found,
 361             and \ref end() otherwise
 362         */
 363         template <typename Q>
 364         iterator find( Q const& key )
 365         {
 366             return node_to_iterator( find_at( head(), key, intrusive_key_comparator() ));
 367         }
 368
 369         /// Finds the key \p val using \p pred predicate for searching
 370         /**
 371             The function is an analog of \ref cds_nonintrusive_LazyList_nogc_find "find(Q const&)"
 372             but \p pred is used for key comparing.
 373             \p Less functor has the interface like \p std::less.
 374             \p pred must imply the same element order as the comparator used for building the list.
 375         */
 376         template <typename Q, typename Less>
 377         iterator find_with( Q const& key, Less pred )
 378         {
 379             return node_to_iterator( find_at( head(), key, typename options::template less_wrapper<Less>::type() ));
 380         }
 381
 382         /// Check if the list is empty
 383         bool empty() const
 384         {
 385             return base_class::empty();
 386         }
 387
 388         /// Returns list's item count
 389         /**
 390             The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
 391             this function always returns 0.
 392
 393             <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
 394             is empty. To check list emptyness use \ref empty() method.
 395         */
 396         size_t size() const
 397         {
 398             return base_class::size();
 399         }
 400
 401         /// Clears the list
 402         /**
 403             Post-condition: the list is empty
 404         */
 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 #   ifdef CDS_EMPLACE_SUPPORT
 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 #   endif
 435         template <typename Q>
 436         std::pair< node_type *, bool > ensure_at( head_type& refHead, Q const& val )
 437         {
 438             scoped_node_ptr pNode( alloc_node( val ));
 439             node_type * pItemFound = nullptr;
 440
 441 #   ifdef CDS_CXX11_LAMBDA_SUPPORT
 442             std::pair<bool, bool> ret = base_class::ensure_at( &refHead, *pNode,
 443                 [&pItemFound](bool, node_type& item, node_type&){ pItemFound = &item; });
 444 #   else
 445             ensure_functor func;
 446             std::pair<bool, bool> ret = base_class::ensure_at( &refHead, *pNode, boost::ref(func) );
 447             pItemFound = func.m_pItemFound;
 448 #   endif
 449             assert( pItemFound != nullptr );
 450
 451             if ( ret.first && ret.second )
 452                 pNode.release();
 453
 454             return std::make_pair( pItemFound, ret.second );
 455         }
 456
 457         template <typename Q, typename Compare>
 458         node_type * find_at( head_type& refHead, Q const& key, Compare cmp )
 459         {
 460             return base_class::find_at( &refHead, key, cmp );
 461         }
 462
 463         //@endcond
 464     };
 465 }} // namespace cds::container
 466
 467 #endif // #ifndef __CDS_CONTAINER_LAZY_LIST_NOGC_H