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     ///@name Forward iterators
 261     //@{
 262         /// Forward iterator
 263         /**
 264             The forward iterator is safe: you may use it in multi-threaded enviromnent without any synchronization.
 265
 266             The forward iterator for Michael's list based on \p gc::nogc has pre- and post-increment operators.
 267
 268             The iterator interface to access item data:
 269             - <tt> operator -> </tt> - returns a pointer to \p value_type
 270             - <tt> operator *</tt> - returns a reference (a const reference for \p const_iterator) to \p value_type
 271             - <tt> const key_type& key() </tt> - returns a key reference for iterator
 272             - <tt> mapped_type& val() </tt> - retuns a value reference for iterator (const reference for \p const_iterator)
 273
 274             For both functions the iterator should not be equal to \p end().
 275
 276             @note \p end() iterator is not dereferenceable
 277         */
 278         typedef iterator_type<false>    iterator;
 279
 280         /// Const forward iterator
 281         /**
 282             For iterator's features and requirements see \ref iterator
 283         */
 284         typedef iterator_type<true>     const_iterator;
 285
 286         /// Returns a forward iterator addressing the first element in a list
 287         /**
 288             For empty list \code begin() == end() \endcode
 289         */
 290         iterator begin()
 291         {
 292             return iterator( head() );
 293         }
 294
 295         /// Returns an iterator that addresses the location succeeding the last element in a list
 296         /**
 297             Do not use the value returned by <tt>end</tt> function to access any item.
 298             Internally, <tt>end</tt> returning value equals to \p nullptr.
 299
 300             The returned value can be used only to control reaching the end of the list.
 301             For empty list \code begin() == end() \endcode
 302         */
 303         iterator end()
 304         {
 305             return iterator();
 306         }
 307
 308         /// Returns a forward const iterator addressing the first element in a list
 309         const_iterator begin() const
 310         {
 311             return const_iterator( head() );
 312         }
 313         /// Returns a forward const iterator addressing the first element in a list
 314         const_iterator cbegin() const
 315         {
 316             return const_iterator( head() );
 317         }
 318
 319         /// Returns an const iterator that addresses the location succeeding the last element in a list
 320         const_iterator end() const
 321         {
 322             return const_iterator();
 323         }
 324         /// Returns an const iterator that addresses the location succeeding the last element in a list
 325         const_iterator cend() const
 326         {
 327             return const_iterator();
 328         }
 329     //@}
 330
 331     protected:
 332         //@cond
 333         iterator node_to_iterator( node_type * pNode )
 334         {
 335             if ( pNode )
 336                 return iterator( *pNode );
 337             return end();
 338         }
 339         //@endcond
 340
 341     public:
 342         /// Default constructor
 343         /**
 344             Initialize empty list
 345         */
 346         MichaelKVList()
 347         {}
 348
 349         /// List desctructor
 350         /**
 351             Clears the list
 352         */
 353         ~MichaelKVList()
 354         {
 355             clear();
 356         }
 357
 358         /// Inserts new node with key and default value
 359         /**
 360             The function creates a node with \p key and default value, and then inserts the node created into the list.
 361
 362             Preconditions:
 363             - The \ref key_type should be constructible from value of type \p K.
 364                 In trivial case, \p K is equal to \ref key_type.
 365             - The \ref mapped_type should be default-constructible.
 366
 367             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 368         */
 369         template <typename K>
 370         iterator insert( const K& key )
 371         {
 372             return node_to_iterator( insert_at( head(), key ));
 373         }
 374
 375         /// Inserts new node with a key and a value
 376         /**
 377             The function creates a node with \p key and value \p val, and then inserts the node created into the list.
 378
 379             Preconditions:
 380             - The \ref key_type should be constructible from \p key of type \p K.
 381             - The \ref mapped_type should be constructible from \p val of type \p V.
 382
 383             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 384         */
 385         template <typename K, typename V>
 386         iterator insert( const K& key, const V& val )
 387         {
 388             // We cannot use insert with functor here
 389             // because we cannot lock inserted node for updating
 390             // Therefore, we use separate function
 391             return node_to_iterator( insert_at( head(), key, val ));
 392         }
 393
 394         /// Inserts new node and initialize it by a functor
 395         /**
 396             This function inserts new node with key \p key and if inserting is successful then it calls
 397             \p func functor with signature
 398             \code void func( value_type& item );
 399                 struct functor {
 400                     void operator()( value_type& item );
 401                 };
 402             \endcode
 403
 404             The argument \p item of user-defined functor \p func is the reference
 405             to the list's item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
 406             User-defined functor \p func should guarantee that during changing item's value no any other changes
 407             could be made on this list's item by concurrent threads.
 408
 409             The key_type should be constructible from value of type \p K.
 410
 411             The function allows to split creating of new item into two part:
 412             - create item from \p key;
 413             - insert new item into the list;
 414             - if inserting is successful, initialize the value of item by calling \p f functor
 415
 416             This can be useful if complete initialization of object of \p mapped_type is heavyweight and
 417             it is preferable that the initialization should be completed only if inserting is successful.
 418
 419             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 420         */
 421         template <typename K, typename Func>
 422         iterator insert_with( const K& key, Func func )
 423         {
 424             return node_to_iterator( insert_with_at( head(), key, func ));
 425         }
 426
 427         /// Updates the item
 428         /**
 429             If \p key is not in the list and \p bAllowInsert is \p true,
 430
 431             the function inserts a new item.
 432             Otherwise, the function returns an iterator pointing to the item found.
 433
 434             Returns <tt> std::pair<iterator, bool> </tt> where \p first is an iterator pointing to
 435             item found or inserted, \p second is true if new item has been added or \p false if the item
 436             already is in the list.
 437         */
 438         template <typename K>
 439         std::pair<iterator, bool> update( K const& key, bool bAllowInsert = true )
 440         {
 441             std::pair< node_type *, bool > ret = update_at( head(), key, bAllowInsert );
 442             return std::make_pair( node_to_iterator( ret.first ), ret.second );
 443         }
 444         //@cond
 445         template <typename K>
 446         CDS_DEPRECATED("ensure() is deprecated, use update()")
 447         std::pair<iterator, bool> ensure( K const& key )
 448         {
 449             return update( key );
 450         }
 451         //@endcond
 452
 453         /// Inserts data of type \ref mapped_type constructed with <tt>std::forward<Args>(args)...</tt>
 454         /**
 455             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 456         */
 457         template <typename K, typename... Args>
 458         iterator emplace( K&& key, Args&&... args )
 459         {
 460             return node_to_iterator( emplace_at( head(), std::forward<K>(key), std::forward<Args>(args)... ));
 461         }
 462
 463         /// Checks whether the list contains \p key
 464         /**
 465             The function searches the item with key equal to \p key
 466             and returns an iterator pointed to item found and \ref end() otherwise
 467         */
 468         template <typename Q>
 469         iterator contains( Q const& key )
 470         {
 471             return node_to_iterator( find_at( head(), key, intrusive_key_comparator() ) );
 472         }
 473         //@cond
 474         template <typename Q>
 475         CDS_DEPRECATED("deprecated, use contains()")
 476         iterator find( Q const& key )
 477         {
 478             return contains( key );
 479         }
 480         //@endcond
 481
 482         /// Checks whether the list contains \p key using \p pred predicate for searching
 483         /**
 484             The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
 485             \p Less functor has the interface like \p std::less.
 486             \p pred must imply the same element order as the comparator used for building the list.
 487         */
 488         template <typename Q, typename Less>
 489         iterator contains( Q const& key, Less pred )
 490         {
 491             CDS_UNUSED( pred );
 492             return node_to_iterator( find_at( head(), key, typename maker::template less_wrapper<Less>::type() ) );
 493         }
 494         //@cond
 495         template <typename Q, typename Less>
 496         CDS_DEPRECATED("deprecated, use contains()")
 497         iterator find_with( Q const& key, Less pred )
 498         {
 499             return contains( key, pred );
 500         }
 501         //@endcond
 502
 503         /// Check if the list is empty
 504         bool empty() const
 505         {
 506             return base_class::empty();
 507         }
 508
 509         /// Returns list's item count
 510         /**
 511             The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
 512             this function always returns 0.
 513
 514             @note Even if you use real item counter and it returns 0, this fact does not mean that the list
 515             is empty. To check list emptyness use \p empty() method.
 516         */
 517         size_t size() const
 518         {
 519             return base_class::size();
 520         }
 521
 522         /// Clears the list
 523         void clear()
 524         {
 525             base_class::clear();
 526         }
 527
 528     protected:
 529         //@cond
 530         node_type * insert_node_at( head_type& refHead, node_type * pNode )
 531         {
 532             assert( pNode != nullptr );
 533             scoped_node_ptr p( pNode );
 534             if ( base_class::insert_at( refHead, *pNode ))
 535                 return p.release();
 536             return nullptr;
 537         }
 538
 539         template <typename K>
 540         node_type * insert_at( head_type& refHead, const K& key )
 541         {
 542             return insert_node_at( refHead, alloc_node( key ));
 543         }
 544
 545         template <typename K, typename V>
 546         node_type * insert_at( head_type& refHead, const K& key, const V& val )
 547         {
 548             return insert_node_at( refHead, alloc_node( key, val ));
 549         }
 550
 551         template <typename K, typename Func>
 552         node_type * insert_with_at( head_type& refHead, const K& key, Func f )
 553         {
 554             scoped_node_ptr pNode( alloc_node( key ));
 555
 556             if ( base_class::insert_at( refHead, *pNode )) {
 557                 f( pNode->m_Data );
 558                 return pNode.release();
 559             }
 560             return nullptr;
 561         }
 562
 563         template <typename K>
 564         std::pair< node_type *, bool > update_at( head_type& refHead, const K& key, bool bAllowInsert )
 565         {
 566             scoped_node_ptr pNode( alloc_node( key ));
 567             node_type * pItemFound = nullptr;
 568
 569             std::pair<bool, bool> ret = base_class::update_at( refHead, *pNode,
 570
 571                 [&pItemFound](bool, node_type& item, node_type&){ pItemFound = &item; },
 572                 bAllowInsert );
 573
 574             if ( ret.second )
 575                 pNode.release();
 576             return std::make_pair( pItemFound, ret.second );
 577         }
 578
 579         template <typename K, typename... Args>
 580         node_type * emplace_at( head_type& refHead, K&& key, Args&&... args )
 581         {
 582             return insert_node_at( refHead, alloc_node( std::forward<K>(key), std::forward<Args>(args)... ));
 583         }
 584
 585         template <typename K, typename Compare>
 586         node_type * find_at( head_type& refHead, K const& key, Compare cmp )
 587         {
 588             return base_class::find_at( refHead, key, cmp );
 589         }
 590         //@endcond
 591     };
 592
 593 }} // namespace cds::container
 594
 595 #endif // #ifndef CDSLIB_CONTAINER_MICHAEL_KVLIST_NOGC_H