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