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