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