cds/container/michael_kvlist_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_KVLIST_NOGC_H
  32 #define CDSLIB_CONTAINER_MICHAEL_KVLIST_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_kvlist.h>
  38
  39 namespace cds { namespace container {
  40
  41     //@cond
  42     namespace details {
  43
  44         template <typename K, typename T, class Traits>
  45         struct make_michael_kvlist_nogc: public make_michael_kvlist<gc::nogc, K, T, Traits>
  46         {
  47             typedef make_michael_kvlist<cds::gc::nogc, K, 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 ordered list (key-value pair, template specialization for gc::nogc)
  62     /** @ingroup cds_nonintrusive_list
  63         @anchor cds_nonintrusive_MichaelKVList_nogc
  64
  65         This specialization is intended for so-called persistent usage when no item
  66         reclamation may be performed. The class does not support deleting of list item.
  67
  68         Usually, ordered single-linked list is used as a building block for the hash table implementation.
  69         The complexity of searching is <tt>O(N)</tt>.
  70
  71         See \ref cds_nonintrusive_MichaelList_gc "MichaelList" for description of template parameters.
  72
  73         The interface of the specialization is a little different.
  74     */
  75     template <
  76         typename Key,
  77         typename Value,
  78 #ifdef CDS_DOXYGEN_INVOKED
  79         typename Traits = michael_list::traits
  80 #else
  81         typename Traits
  82 #endif
  83     >
  84     class MichaelKVList<gc::nogc, Key, Value, Traits>:
  85 #ifdef CDS_DOXYGEN_INVOKED
  86         protected intrusive::MichaelList< gc::nogc, implementation_defined, Traits >
  87 #else
  88         protected details::make_michael_kvlist_nogc< Key, Value, Traits >::type
  89 #endif
  90     {
  91         //@cond
  92         typedef details::make_michael_kvlist_nogc< Key, Value, Traits > maker;
  93         typedef typename maker::type  base_class;
  94         //@endcond
  95
  96     public:
  97         typedef cds::gc::nogc gc;         ///< Garbage collector used
  98         typedef Traits        traits;     ///< List traits
  99
 100 #ifdef CDS_DOXYGEN_INVOKED
 101         typedef Key                                 key_type        ;   ///< Key type
 102         typedef Value                               mapped_type     ;   ///< Type of value stored in the list
 103         typedef std::pair<key_type const, mapped_type> value_type   ;   ///< key/value pair stored in the list
 104 #else
 105         typedef typename maker::key_type          key_type;
 106         typedef typename maker::value_type        mapped_type;
 107         typedef typename maker::pair_type         value_type;
 108 #endif
 109
 110         typedef typename base_class::back_off     back_off;       ///< Back-off strategy used
 111         typedef typename maker::allocator_type    allocator_type; ///< Allocator type used for allocate/deallocate the nodes
 112         typedef typename base_class::item_counter item_counter;   ///< Item counting policy used
 113         typedef typename maker::key_comparator    key_comparator; ///< key comparison functor
 114         typedef typename base_class::memory_model memory_model;   ///< Memory ordering. See cds::opt::memory_model option
 115
 116     protected:
 117         //@cond
 118         typedef typename base_class::value_type   node_type;
 119         typedef typename maker::cxx_allocator     cxx_allocator;
 120         typedef typename maker::node_deallocator  node_deallocator;
 121         typedef typename maker::intrusive_traits::compare  intrusive_key_comparator;
 122
 123         typedef typename base_class::atomic_node_ptr head_type;
 124         //@endcond
 125
 126     protected:
 127         //@cond
 128         template <typename K>
 129         static node_type * alloc_node(const K& key)
 130         {
 131             return cxx_allocator().New( key );
 132         }
 133
 134         template <typename K, typename V>
 135         static node_type * alloc_node( const K& key, const V& val )
 136         {
 137             return cxx_allocator().New( key, val );
 138         }
 139
 140         template <typename K, typename... Args>
 141         static node_type * alloc_node( K&& key, Args&&... args )
 142         {
 143             return cxx_allocator().MoveNew( std::forward<K>(key), std::forward<Args>(args)... );
 144         }
 145
 146         static void free_node( node_type * pNode )
 147         {
 148             cxx_allocator().Delete( pNode );
 149         }
 150
 151         struct node_disposer {
 152             void operator()( node_type * pNode )
 153             {
 154                 free_node( pNode );
 155             }
 156         };
 157         typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
 158
 159         head_type& head()
 160         {
 161             return base_class::m_pHead;
 162         }
 163
 164         head_type const& head() const
 165         {
 166             return base_class::m_pHead;
 167         }
 168         //@endcond
 169
 170     protected:
 171         //@cond
 172         template <bool IsConst>
 173         class iterator_type: protected base_class::template iterator_type<IsConst>
 174         {
 175             typedef typename base_class::template iterator_type<IsConst>    iterator_base;
 176
 177             iterator_type( head_type const& refNode )
 178                 : iterator_base( refNode )
 179             {}
 180
 181             explicit iterator_type( const iterator_base& it )
 182                 : iterator_base( it )
 183             {}
 184
 185             friend class MichaelKVList;
 186
 187         protected:
 188             explicit iterator_type( node_type& pNode )
 189                 : iterator_base( &pNode )
 190             {}
 191
 192         public:
 193             typedef typename cds::details::make_const_type<mapped_type, IsConst>::reference  value_ref;
 194             typedef typename cds::details::make_const_type<mapped_type, IsConst>::pointer    value_ptr;
 195
 196             typedef typename cds::details::make_const_type<value_type,  IsConst>::reference  pair_ref;
 197             typedef typename cds::details::make_const_type<value_type,  IsConst>::pointer    pair_ptr;
 198
 199             iterator_type()
 200                 : iterator_base()
 201             {}
 202
 203             iterator_type( const iterator_type& src )
 204                 : iterator_base( src )
 205             {}
 206
 207             key_type const& key() const
 208             {
 209                 typename iterator_base::value_ptr p = iterator_base::operator ->();
 210                 assert( p != nullptr );
 211                 return p->m_Data.first;
 212             }
 213
 214             value_ref val() const
 215             {
 216                 typename iterator_base::value_ptr p = iterator_base::operator ->();
 217                 assert( p != nullptr );
 218                 return p->m_Data.second;
 219             }
 220
 221             pair_ptr operator ->() const
 222             {
 223                 typename iterator_base::value_ptr p = iterator_base::operator ->();
 224                 return p ? &(p->m_Data) : nullptr;
 225             }
 226
 227             pair_ref operator *() const
 228             {
 229                 typename iterator_base::value_ref p = iterator_base::operator *();
 230                 return p.m_Data;
 231             }
 232
 233             /// Pre-increment
 234             iterator_type& operator ++()
 235             {
 236                 iterator_base::operator ++();
 237                 return *this;
 238             }
 239
 240             /// Post-increment
 241             iterator_type operator ++(int)
 242             {
 243                 return iterator_base::operator ++(0);
 244             }
 245
 246             template <bool C>
 247             bool operator ==(iterator_type<C> const& i ) const
 248             {
 249                 return iterator_base::operator ==(i);
 250             }
 251             template <bool C>
 252             bool operator !=(iterator_type<C> const& i ) const
 253             {
 254                 return iterator_base::operator !=(i);
 255             }
 256         };
 257         //@endcond
 258
 259     public:
 260         /// Forward iterator
 261         /**
 262             The forward iterator for Michael's list based on gc::nogc has pre- and post-increment operators.
 263
 264             The iterator interface to access item data:
 265             - <tt> operator -> </tt> - returns a pointer to \ref value_type for iterator
 266             - <tt> operator *</tt> - returns a reference (a const reference for \p const_iterator) to \ref value_type for iterator
 267             - <tt> const key_type& key() </tt> - returns a key reference for iterator
 268             - <tt> mapped_type& val() </tt> - retuns a value reference for iterator (const reference for \p const_iterator)
 269
 270             For both functions the iterator should not be equal to <tt> end() </tt>
 271         */
 272         typedef iterator_type<false>    iterator;
 273
 274         /// Const forward iterator
 275         /**
 276             For iterator's features and requirements see \ref iterator
 277         */
 278         typedef iterator_type<true>     const_iterator;
 279
 280         /// Returns a forward iterator addressing the first element in a list
 281         /**
 282             For empty list \code begin() == end() \endcode
 283         */
 284         iterator begin()
 285         {
 286             return iterator( head() );
 287         }
 288
 289         /// Returns an iterator that addresses the location succeeding the last element in a list
 290         /**
 291             Do not use the value returned by <tt>end</tt> function to access any item.
 292             Internally, <tt>end</tt> returning value equals to \p nullptr.
 293
 294             The returned value can be used only to control reaching the end of the list.
 295             For empty list \code begin() == end() \endcode
 296         */
 297         iterator end()
 298         {
 299             return iterator();
 300         }
 301
 302         /// Returns a forward const iterator addressing the first element in a list
 303         //@{
 304         const_iterator begin() const
 305         {
 306             return const_iterator( head() );
 307         }
 308         const_iterator cbegin() const
 309         {
 310             return const_iterator( head() );
 311         }
 312         //@}
 313
 314         /// Returns an const iterator that addresses the location succeeding the last element in a list
 315         //@{
 316         const_iterator end() const
 317         {
 318             return const_iterator();
 319         }
 320         const_iterator cend() const
 321         {
 322             return const_iterator();
 323         }
 324         //@}
 325
 326     protected:
 327         //@cond
 328         iterator node_to_iterator( node_type * pNode )
 329         {
 330             if ( pNode )
 331                 return iterator( *pNode );
 332             return end();
 333         }
 334         //@endcond
 335
 336     public:
 337         /// Default constructor
 338         /**
 339             Initialize empty list
 340         */
 341         MichaelKVList()
 342         {}
 343
 344         /// List desctructor
 345         /**
 346             Clears the list
 347         */
 348         ~MichaelKVList()
 349         {
 350             clear();
 351         }
 352
 353         /// Inserts new node with key and default value
 354         /**
 355             The function creates a node with \p key and default value, and then inserts the node created into the list.
 356
 357             Preconditions:
 358             - The \ref key_type should be constructible from value of type \p K.
 359                 In trivial case, \p K is equal to \ref key_type.
 360             - The \ref mapped_type should be default-constructible.
 361
 362             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 363         */
 364         template <typename K>
 365         iterator insert( const K& key )
 366         {
 367             return node_to_iterator( insert_at( head(), key ));
 368         }
 369
 370         /// Inserts new node with a key and a value
 371         /**
 372             The function creates a node with \p key and value \p val, and then inserts the node created into the list.
 373
 374             Preconditions:
 375             - The \ref key_type should be constructible from \p key of type \p K.
 376             - The \ref mapped_type should be constructible from \p val of type \p V.
 377
 378             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 379         */
 380         template <typename K, typename V>
 381         iterator insert( const K& key, const V& val )
 382         {
 383             // We cannot use insert with functor here
 384             // because we cannot lock inserted node for updating
 385             // Therefore, we use separate function
 386             return node_to_iterator( insert_at( head(), key, val ));
 387         }
 388
 389         /// Inserts new node and initialize it by a functor
 390         /**
 391             This function inserts new node with key \p key and if inserting is successful then it calls
 392             \p func functor with signature
 393             \code void func( value_type& item );
 394                 struct functor {
 395                     void operator()( value_type& item );
 396                 };
 397             \endcode
 398
 399             The argument \p item of user-defined functor \p func is the reference
 400             to the list's item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
 401             User-defined functor \p func should guarantee that during changing item's value no any other changes
 402             could be made on this list's item by concurrent threads.
 403
 404             The key_type should be constructible from value of type \p K.
 405
 406             The function allows to split creating of new item into two part:
 407             - create item from \p key;
 408             - insert new item into the list;
 409             - if inserting is successful, initialize the value of item by calling \p f functor
 410
 411             This can be useful if complete initialization of object of \p mapped_type is heavyweight and
 412             it is preferable that the initialization should be completed only if inserting is successful.
 413
 414             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 415         */
 416         template <typename K, typename Func>
 417         iterator insert_with( const K& key, Func func )
 418         {
 419             return node_to_iterator( insert_with_at( head(), key, func ));
 420         }
 421
 422         /// Updates the item
 423         /**
 424             If \p key is not in the list and \p bAllowInsert is \p true,
 425
 426             the function inserts a new item.
 427             Otherwise, the function returns an iterator pointing to the item found.
 428
 429             Returns <tt> std::pair<iterator, bool> </tt> where \p first is an iterator pointing to
 430             item found or inserted, \p second is true if new item has been added or \p false if the item
 431             already is in the list.
 432         */
 433         template <typename K>
 434         std::pair<iterator, bool> update( K const& key, bool bAllowInsert = true )
 435         {
 436             std::pair< node_type *, bool > ret = update_at( head(), key, bAllowInsert );
 437             return std::make_pair( node_to_iterator( ret.first ), ret.second );
 438         }
 439         //@cond
 440         template <typename K>
 441         CDS_DEPRECATED("ensure() is deprecated, use update()")
 442         std::pair<iterator, bool> ensure( K const& key )
 443         {
 444             return update( key );
 445         }
 446         //@endcond
 447
 448         /// Inserts data of type \ref mapped_type constructed with <tt>std::forward<Args>(args)...</tt>
 449         /**
 450             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 451         */
 452         template <typename K, typename... Args>
 453         iterator emplace( K&& key, Args&&... args )
 454         {
 455             return node_to_iterator( emplace_at( head(), std::forward<K>(key), std::forward<Args>(args)... ));
 456         }
 457
 458         /// Checks whether the list contains \p key
 459         /**
 460             The function searches the item with key equal to \p key
 461             and returns an iterator pointed to item found and \ref end() otherwise
 462         */
 463         template <typename Q>
 464         iterator contains( Q const& key )
 465         {
 466             return node_to_iterator( find_at( head(), key, intrusive_key_comparator() ) );
 467         }
 468         //@cond
 469         template <typename Q>
 470         CDS_DEPRECATED("deprecated, use contains()")
 471         iterator find( Q const& key )
 472         {
 473             return contains( key );
 474         }
 475         //@endcond
 476
 477         /// Checks whether the list contains \p key using \p pred predicate for searching
 478         /**
 479             The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
 480             \p Less functor has the interface like \p std::less.
 481             \p pred must imply the same element order as the comparator used for building the list.
 482         */
 483         template <typename Q, typename Less>
 484         iterator contains( Q const& key, Less pred )
 485         {
 486             CDS_UNUSED( pred );
 487             return node_to_iterator( find_at( head(), key, typename maker::template less_wrapper<Less>::type() ) );
 488         }
 489         //@cond
 490         template <typename Q, typename Less>
 491         CDS_DEPRECATED("deprecated, use contains()")
 492         iterator find_with( Q const& key, Less pred )
 493         {
 494             return contains( key, pred );
 495         }
 496         //@endcond
 497
 498         /// Check if the list is empty
 499         bool empty() const
 500         {
 501             return base_class::empty();
 502         }
 503
 504         /// Returns list's item count
 505         /**
 506             The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
 507             this function always returns 0.
 508
 509             @note Even if you use real item counter and it returns 0, this fact does not mean that the list
 510             is empty. To check list emptyness use \p empty() method.
 511         */
 512         size_t size() const
 513         {
 514             return base_class::size();
 515         }
 516
 517         /// Clears the list
 518         void clear()
 519         {
 520             base_class::clear();
 521         }
 522
 523     protected:
 524         //@cond
 525         node_type * insert_node_at( head_type& refHead, node_type * pNode )
 526         {
 527             assert( pNode != nullptr );
 528             scoped_node_ptr p( pNode );
 529             if ( base_class::insert_at( refHead, *pNode ))
 530                 return p.release();
 531             return nullptr;
 532         }
 533
 534         template <typename K>
 535         node_type * insert_at( head_type& refHead, const K& key )
 536         {
 537             return insert_node_at( refHead, alloc_node( key ));
 538         }
 539
 540         template <typename K, typename V>
 541         node_type * insert_at( head_type& refHead, const K& key, const V& val )
 542         {
 543             return insert_node_at( refHead, alloc_node( key, val ));
 544         }
 545
 546         template <typename K, typename Func>
 547         node_type * insert_with_at( head_type& refHead, const K& key, Func f )
 548         {
 549             scoped_node_ptr pNode( alloc_node( key ));
 550
 551             if ( base_class::insert_at( refHead, *pNode )) {
 552                 f( pNode->m_Data );
 553                 return pNode.release();
 554             }
 555             return nullptr;
 556         }
 557
 558         template <typename K>
 559         std::pair< node_type *, bool > update_at( head_type& refHead, const K& key, bool bAllowInsert )
 560         {
 561             scoped_node_ptr pNode( alloc_node( key ));
 562             node_type * pItemFound = nullptr;
 563
 564             std::pair<bool, bool> ret = base_class::update_at( refHead, *pNode,
 565
 566                 [&pItemFound](bool, node_type& item, node_type&){ pItemFound = &item; },
 567                 bAllowInsert );
 568
 569             if ( ret.second )
 570                 pNode.release();
 571             return std::make_pair( pItemFound, ret.second );
 572         }
 573
 574         template <typename K, typename... Args>
 575         node_type * emplace_at( head_type& refHead, K&& key, Args&&... args )
 576         {
 577             return insert_node_at( refHead, alloc_node( std::forward<K>(key), std::forward<Args>(args)... ));
 578         }
 579
 580         template <typename K, typename Compare>
 581         node_type * find_at( head_type& refHead, K const& key, Compare cmp )
 582         {
 583             return base_class::find_at( refHead, key, cmp );
 584         }
 585         //@endcond
 586     };
 587
 588 }} // namespace cds::container
 589
 590 #endif // #ifndef CDSLIB_CONTAINER_MICHAEL_KVLIST_NOGC_H