cds/container/michael_list_nogc.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_CONTAINER_MICHAEL_LIST_NOGC_H
  32 #define CDSLIB_CONTAINER_MICHAEL_LIST_NOGC_H
  33
  34 #include <memory>
  35 #include <cds/container/details/michael_list_base.h>
  36 #include <cds/intrusive/michael_list_nogc.h>
  37 #include <cds/container/details/make_michael_list.h>
  38
  39 namespace cds { namespace container {
  40
  41     //@cond
  42     namespace details {
  43
  44         template <typename T, class Traits>
  45         struct make_michael_list_nogc: public make_michael_list<gc::nogc, T, Traits>
  46         {
  47             typedef make_michael_list<cds::gc::nogc, T, Traits>  base_maker;
  48             typedef typename base_maker::node_type node_type;
  49
  50             struct intrusive_traits: public base_maker::intrusive_traits
  51             {
  52                 typedef typename base_maker::node_deallocator    disposer;
  53             };
  54
  55             typedef intrusive::MichaelList<cds::gc::nogc, node_type, intrusive_traits>  type;
  56         };
  57
  58     }   // namespace details
  59     //@endcond
  60
  61     /// Michael's lock-free ordered single-linked list (template specialization for \p gc::nogc)
  62     /** @ingroup cds_nonintrusive_list
  63         \anchor cds_nonintrusive_MichaelList_nogc
  64
  65         This specialization is intended for so-called append-only usage when no item
  66         reclamation may be performed. The class does not support deleting of list item.
  67         Usually, ordered single-linked list is used as a building block for the hash table implementation.
  68         The complexity of searching is <tt>O(N)</tt>.
  69
  70         See \ref cds_nonintrusive_MichaelList_gc "MichaelList" for description of template parameters.
  71     */
  72     template <typename T,
  73 #ifdef CDS_DOXYGEN_INVOKED
  74         class Traits = michael_list::traits
  75 #else
  76         class Traits
  77 #endif
  78     >
  79     class MichaelList<gc::nogc, T, Traits>:
  80 #ifdef CDS_DOXYGEN_INVOKED
  81         protected intrusive::MichaelList< gc::nogc, T, Traits >
  82 #else
  83         protected details::make_michael_list_nogc< T, Traits >::type
  84 #endif
  85     {
  86         //@cond
  87         typedef details::make_michael_list_nogc< T, Traits > maker;
  88         typedef typename maker::type  base_class;
  89         //@endcond
  90
  91     public:
  92         typedef cds::gc::nogc gc;         ///< Garbage collector used
  93         typedef T             value_type; ///< Type of value stored in the list
  94         typedef Traits        traits;     ///< List traits
  95
  96         typedef typename base_class::back_off     back_off;       ///< Back-off strategy used
  97         typedef typename maker::allocator_type    allocator_type; ///< Allocator type used for allocate/deallocate the nodes
  98         typedef typename base_class::item_counter item_counter;   ///< Item counting policy used
  99         typedef typename maker::key_comparator    key_comparator; ///< key comparison functor
 100         typedef typename base_class::memory_model memory_model;   ///< Memory ordering. See cds::opt::memory_model option
 101
 102     protected:
 103         //@cond
 104         typedef typename base_class::value_type   node_type;
 105         typedef typename maker::cxx_allocator     cxx_allocator;
 106         typedef typename maker::node_deallocator  node_deallocator;
 107         typedef typename maker::intrusive_traits::compare  intrusive_key_comparator;
 108
 109         typedef typename base_class::atomic_node_ptr head_type;
 110         //@endcond
 111
 112     protected:
 113         //@cond
 114         static node_type * alloc_node()
 115         {
 116             return cxx_allocator().New();
 117         }
 118
 119         static node_type * alloc_node( value_type const& v )
 120         {
 121             return cxx_allocator().New( v );
 122         }
 123
 124         template <typename... Args>
 125         static node_type * alloc_node( Args&&... args )
 126         {
 127             return cxx_allocator().MoveNew( std::forward<Args>(args)... );
 128         }
 129
 130         static void free_node( node_type * pNode )
 131         {
 132             cxx_allocator().Delete( pNode );
 133         }
 134
 135         struct node_disposer {
 136             void operator()( node_type * pNode )
 137             {
 138                 free_node( pNode );
 139             }
 140         };
 141         typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
 142
 143         head_type& head()
 144         {
 145             return base_class::m_pHead;
 146         }
 147
 148         head_type const& head() const
 149         {
 150             return base_class::m_pHead;
 151         }
 152         //@endcond
 153
 154     protected:
 155         //@cond
 156         template <bool IsConst>
 157         class iterator_type: protected base_class::template iterator_type<IsConst>
 158         {
 159             typedef typename base_class::template iterator_type<IsConst>    iterator_base;
 160
 161             iterator_type( head_type const& pNode )
 162                 : iterator_base( pNode )
 163             {}
 164
 165             explicit iterator_type( const iterator_base& it )
 166                 : iterator_base( it )
 167             {}
 168
 169             friend class MichaelList;
 170
 171         protected:
 172             explicit iterator_type( node_type& pNode )
 173                 : iterator_base( &pNode )
 174             {}
 175
 176         public:
 177             typedef typename cds::details::make_const_type<value_type, IsConst>::pointer   value_ptr;
 178             typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
 179
 180             iterator_type()
 181             {}
 182
 183             iterator_type( const iterator_type& src )
 184                 : iterator_base( src )
 185             {}
 186
 187             value_ptr operator ->() const
 188             {
 189                 typename iterator_base::value_ptr p = iterator_base::operator ->();
 190                 return p ? &(p->m_Value) : nullptr;
 191             }
 192
 193             value_ref operator *() const
 194             {
 195                 return (iterator_base::operator *()).m_Value;
 196             }
 197
 198             /// Pre-increment
 199             iterator_type& operator ++()
 200             {
 201                 iterator_base::operator ++();
 202                 return *this;
 203             }
 204
 205             /// Post-increment
 206             iterator_type operator ++(int)
 207             {
 208                 return iterator_base::operator ++(0);
 209             }
 210
 211             template <bool C>
 212             bool operator ==(iterator_type<C> const& i ) const
 213             {
 214                 return iterator_base::operator ==(i);
 215             }
 216             template <bool C>
 217             bool operator !=(iterator_type<C> const& i ) const
 218             {
 219                 return iterator_base::operator !=(i);
 220             }
 221         };
 222         //@endcond
 223
 224     public:
 225    ///@name Forward iterators
 226    //@{
 227         /// Returns a forward iterator addressing the first element in a list
 228         /**
 229             For empty list \code begin() == end() \endcode
 230         */
 231         typedef iterator_type<false>    iterator;
 232
 233         /// Const forward iterator
 234         /**
 235             For iterator's features and requirements see \ref iterator
 236         */
 237         typedef iterator_type<true>     const_iterator;
 238
 239         /// Returns a forward iterator addressing the first element in a list
 240         /**
 241             For empty list \code begin() == end() \endcode
 242         */
 243         iterator begin()
 244         {
 245             return iterator( head() );
 246         }
 247
 248         /// Returns an iterator that addresses the location succeeding the last element in a list
 249         /**
 250             Do not use the value returned by <tt>end</tt> function to access any item.
 251             Internally, <tt>end</tt> returning value equals to \p nullptr.
 252
 253             The returned value can be used only to control reaching the end of the list.
 254             For empty list \code begin() == end() \endcode
 255         */
 256         iterator end()
 257         {
 258             return iterator();
 259         }
 260
 261         /// Returns a forward const iterator addressing the first element in a list
 262         const_iterator begin() const
 263         {
 264             return const_iterator( head() );
 265         }
 266
 267         /// Returns a forward const iterator addressing the first element in a list
 268         const_iterator cbegin() const
 269         {
 270             return const_iterator( head() );
 271         }
 272
 273         /// Returns an const iterator that addresses the location succeeding the last element in a list
 274         const_iterator end() const
 275         {
 276             return const_iterator();
 277         }
 278
 279         /// Returns an const iterator that addresses the location succeeding the last element in a list
 280         const_iterator cend() const
 281         {
 282             return const_iterator();
 283         }
 284     //@}
 285
 286     protected:
 287         //@cond
 288         iterator node_to_iterator( node_type * pNode )
 289         {
 290             if ( pNode )
 291                 return iterator( *pNode );
 292             return end();
 293         }
 294         //@endcond
 295
 296     public:
 297         /// Default constructor
 298         /**
 299             Initialize empty list
 300         */
 301         MichaelList()
 302         {}
 303
 304         /// List desctructor
 305         /**
 306             Clears the list
 307         */
 308         ~MichaelList()
 309         {
 310             clear();
 311         }
 312
 313         /// Inserts new node
 314         /**
 315             The function inserts \p val in the list if the list does not contain
 316             an item with key equal to \p val.
 317
 318             Return an iterator pointing to inserted item if success \ref end() otherwise
 319         */
 320         template <typename Q>
 321         iterator insert( const Q& val )
 322         {
 323             return node_to_iterator( insert_at( head(), val ) );
 324         }
 325
 326         /// Updates the item
 327         /**
 328             If \p key is not in the list and \p bAllowInsert is \p true,
 329             the function inserts a new item.
 330             Otherwise, the function returns an iterator pointing to the item found.
 331
 332             Returns <tt> std::pair<iterator, bool>  </tt> where \p first is an iterator pointing to
 333             item found or inserted, \p second is true if new item has been added or \p false if the item
 334             already is in the list.
 335         */
 336         template <typename Q>
 337         std::pair<iterator, bool> update( const Q& key, bool bAllowInsert = true )
 338         {
 339             std::pair< node_type *, bool > ret = update_at( head(), key, bAllowInsert );
 340             return std::make_pair( node_to_iterator( ret.first ), ret.second );
 341         }
 342         //@cond
 343         template <typename Q>
 344         CDS_DEPRECATED("ensure() is deprecated, use update()")
 345         std::pair<iterator, bool> ensure( const Q& val )
 346         {
 347             return update( val, true );
 348         }
 349         //@endcond
 350
 351         /// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
 352         /**
 353             Return an iterator pointing to inserted item if success \ref end() otherwise
 354         */
 355         template <typename... Args>
 356         iterator emplace( Args&&... args )
 357         {
 358             return node_to_iterator( emplace_at( head(), std::forward<Args>(args)... ));
 359         }
 360
 361         /// Checks whether the list contains \p key
 362         /**
 363             The function searches the item with key equal to \p key
 364             and returns an iterator pointed to item found if the key is found,
 365             and \ref end() otherwise
 366         */
 367         template <typename Q>
 368         iterator contains( Q const& key )
 369         {
 370             return node_to_iterator( find_at( head(), key, intrusive_key_comparator() ));
 371         }
 372         //@cond
 373         template <typename Q>
 374         CDS_DEPRECATED("deprecated, use contains()")
 375         iterator find( Q const& key )
 376         {
 377             return contains( key );
 378         }
 379         //@endcond
 380
 381         /// Checks whether the map contains \p key using \p pred predicate for searching
 382         /**
 383             The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
 384             \p Less functor has the interface like \p std::less.
 385             \p Less must imply the same element order as the comparator used for building the list.
 386         */
 387         template <typename Q, typename Less>
 388         iterator contains( Q const& key, Less pred )
 389         {
 390             CDS_UNUSED( pred );
 391             return node_to_iterator( find_at( head(), key, typename maker::template less_wrapper<Less>::type() ) );
 392         }
 393         //@cond
 394         template <typename Q, typename Less>
 395         CDS_DEPRECATED("deprecated, use contains()")
 396         iterator find_with( Q const& key, Less pred )
 397         {
 398             return contains( key, pred );
 399         }
 400         //@endcond
 401
 402         /// Check if the list is empty
 403         bool empty() const
 404         {
 405             return base_class::empty();
 406         }
 407
 408         /// Returns list's item count
 409         /**
 410             The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
 411             this function always returns 0.
 412
 413             @note Even if you use real item counter and it returns 0, this fact does not mean that the list
 414             is empty. To check list emptyness use \p empty() method.
 415         */
 416         size_t size() const
 417         {
 418             return base_class::size();
 419         }
 420
 421         /// Clears the list
 422         void clear()
 423         {
 424             base_class::clear();
 425         }
 426
 427     protected:
 428         //@cond
 429         node_type * insert_node_at( head_type& refHead, node_type * pNode )
 430         {
 431             assert( pNode != nullptr );
 432             scoped_node_ptr p(pNode);
 433             if ( base_class::insert_at( refHead, *pNode ))
 434                 return p.release();
 435
 436             return nullptr;
 437         }
 438
 439         template <typename Q>
 440         node_type * insert_at( head_type& refHead, const Q& val )
 441         {
 442             return insert_node_at( refHead, alloc_node( val ));
 443         }
 444
 445         template <typename Q>
 446         std::pair< node_type *, bool > update_at( head_type& refHead, const Q& val, bool bAllowInsert )
 447         {
 448             scoped_node_ptr pNode( alloc_node( val ));
 449             node_type * pItemFound = nullptr;
 450
 451             std::pair<bool, bool> ret = base_class::update_at( refHead, *pNode,
 452                 [&pItemFound](bool, node_type& item, node_type&) { pItemFound = &item; },
 453                 bAllowInsert );
 454
 455             if ( ret.second )
 456                 pNode.release();
 457             return std::make_pair( pItemFound, ret.second );
 458         }
 459
 460         template <typename... Args>
 461         node_type * emplace_at( head_type& refHead, Args&&... args )
 462         {
 463             return insert_node_at( refHead, alloc_node( std::forward<Args>(args)...));
 464         }
 465
 466         template <typename Q, typename Compare>
 467         node_type * find_at( head_type& refHead, Q const& key, Compare cmp )
 468         {
 469             return base_class::find_at( refHead, key, cmp );
 470         }
 471
 472         //@endcond
 473     };
 474 }} // namespace cds::container
 475
 476 #endif // #ifndef CDSLIB_CONTAINER_MICHAEL_LIST_NOGC_H