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