cds/container/michael_list_nogc.h

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