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