cds/container/michael_kvlist_nogc.h

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