cds/container/skip_list_map_rcu.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_CONTAINER_SKIP_LIST_MAP_RCU_H
   4 #define __CDS_CONTAINER_SKIP_LIST_MAP_RCU_H
   5
   6 #include <cds/container/details/skip_list_base.h>
   7 #include <cds/intrusive/skip_list_rcu.h>
   8 #include <cds/container/details/make_skip_list_map.h>
   9
  10 namespace cds { namespace container {
  11
  12     /// Lock-free skip-list map (template specialization for \ref cds_urcu_desc "RCU")
  13     /** @ingroup cds_nonintrusive_map
  14         \anchor cds_nonintrusive_SkipListMap_rcu
  15
  16         The implementation of well-known probabilistic data structure called skip-list
  17         invented by W.Pugh in his papers:
  18             - [1989] W.Pugh Skip Lists: A Probabilistic Alternative to Balanced Trees
  19             - [1990] W.Pugh A Skip List Cookbook
  20
  21         A skip-list is a probabilistic data structure that provides expected logarithmic
  22         time search without the need of rebalance. The skip-list is a collection of sorted
  23         linked list. Nodes are ordered by key. Each node is linked into a subset of the lists.
  24         Each list has a level, ranging from 0 to 32. The bottom-level list contains
  25         all the nodes, and each higher-level list is a sublist of the lower-level lists.
  26         Each node is created with a random top level (with a random height), and belongs
  27         to all lists up to that level. The probability that a node has the height 1 is 1/2.
  28         The probability that a node has the height N is 1/2 ** N (more precisely,
  29         the distribution depends on an random generator provided, but our generators
  30         have this property).
  31
  32         The lock-free variant of skip-list is implemented according to book
  33             - [2008] M.Herlihy, N.Shavit "The Art of Multiprocessor Programming",
  34                 chapter 14.4 "A Lock-Free Concurrent Skiplist"
  35
  36         Template arguments:
  37         - \p RCU - one of \ref cds_urcu_gc "RCU type".
  38         - \p K - type of a key to be stored in the list.
  39         - \p T - type of a value to be stored in the list.
  40         - \p Traits - map traits, default is \p skip_list::traits.
  41             It is possible to declare option-based list with \p cds::container::skip_list::make_traits metafunction
  42             instead of \p Traits template argument.
  43
  44         Like STL map class, \p %SkipListMap stores its key-value pair as <tt>std:pair< K const, T></tt>.
  45
  46         @note Before including <tt><cds/container/skip_list_map_rcu.h></tt> you should include appropriate RCU header file,
  47         see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
  48
  49         <b>Iterators</b>
  50
  51         The class supports a forward iterator (\ref iterator and \ref const_iterator).
  52         The iteration is ordered.
  53         You may iterate over skip-list set items only under RCU lock.
  54         Only in this case the iterator is thread-safe since
  55         while RCU is locked any set's item cannot be reclaimed.
  56
  57         The requirement of RCU lock during iterating means that deletion of the elements (i.e. \ref erase)
  58         is not possible.
  59
  60         @warning The iterator object cannot be passed between threads
  61
  62         The iterator class supports the following minimalistic interface:
  63         \code
  64         struct iterator {
  65             // Default ctor
  66             iterator();
  67
  68             // Copy ctor
  69             iterator( iterator const& s);
  70
  71             value_type * operator ->() const;
  72             value_type& operator *() const;
  73
  74             // Pre-increment
  75             iterator& operator ++();
  76
  77             // Copy assignment
  78             iterator& operator = (const iterator& src);
  79
  80             bool operator ==(iterator const& i ) const;
  81             bool operator !=(iterator const& i ) const;
  82         };
  83         \endcode
  84         Note, the iterator object returned by \ref end, \p cend member functions points to \p nullptr and should not be dereferenced.
  85
  86     */
  87     template <
  88         typename RCU,
  89         typename Key,
  90         typename T,
  91 #ifdef CDS_DOXYGEN_INVOKED
  92         typename Traits = skip_list::traits
  93 #else
  94         typename Traits
  95 #endif
  96     >
  97     class SkipListMap< cds::urcu::gc< RCU >, Key, T, Traits >:
  98 #ifdef CDS_DOXYGEN_INVOKED
  99         protected intrusive::SkipListSet< cds::urcu::gc< RCU >, std::pair<Key const, T>, Traits >
 100 #else
 101         protected details::make_skip_list_map< cds::urcu::gc< RCU >, Key, T, Traits >::type
 102 #endif
 103     {
 104         //@cond
 105         typedef details::make_skip_list_map< cds::urcu::gc< RCU >, Key, T, Traits >    maker;
 106         typedef typename maker::type base_class;
 107         //@endcond
 108     public:
 109         typedef cds::urcu::gc< RCU > gc; ///< Garbage collector used
 110         typedef Key     key_type;       ///< Key type
 111         typedef T       mapped_type;    ///< Mapped type
 112 #   ifdef CDS_DOXYGEN_INVOKED
 113         typedef std::pair< K const, T> value_type;   ///< Value type stored in the map
 114 #   else
 115         typedef typename maker::value_type  value_type;
 116 #   endif
 117         typedef Traits  traits;   ///< Map traits
 118
 119         typedef typename base_class::back_off       back_off;       ///< Back-off strategy used
 120         typedef typename traits::allocator          allocator_type; ///< Allocator type used for allocate/deallocate the skip-list nodes
 121         typedef typename base_class::item_counter   item_counter;   ///< Item counting policy used
 122         typedef typename maker::key_comparator      key_comparator; ///< key comparison functor
 123         typedef typename base_class::memory_model   memory_model;   ///< Memory ordering. See cds::opt::memory_model option
 124         typedef typename traits::random_level_generator random_level_generator; ///< random level generator
 125         typedef typename traits::stat               stat;   ///< internal statistics type
 126
 127     protected:
 128         //@cond
 129         typedef typename maker::node_type           node_type;
 130         typedef typename maker::node_allocator      node_allocator;
 131
 132         typedef std::unique_ptr< node_type, typename maker::node_deallocator >    scoped_node_ptr;
 133         //@endcond
 134
 135     public:
 136         typedef typename base_class::rcu_lock  rcu_lock;   ///< RCU scoped lock
 137         /// Group of \p extract_xxx functions do not require external locking
 138         static CDS_CONSTEXPR const bool c_bExtractLockExternal = base_class::c_bExtractLockExternal;
 139
 140         /// pointer to extracted node
 141         using exempt_ptr = cds::urcu::exempt_ptr< gc, node_type, value_type, typename maker::intrusive_type_traits::disposer >;
 142
 143     protected:
 144         //@cond
 145         unsigned int random_level()
 146         {
 147             return base_class::random_level();
 148         }
 149
 150         value_type * to_value_ptr( node_type * pNode ) const CDS_NOEXCEPT
 151         {
 152             return pNode ? &pNode->m_Value : nullptr;
 153         }
 154         //@endcond
 155
 156     public:
 157         /// Default ctor
 158         SkipListMap()
 159             : base_class()
 160         {}
 161
 162         /// Destructor destroys the set object
 163         ~SkipListMap()
 164         {}
 165
 166     public:
 167         /// Iterator type
 168         typedef skip_list::details::iterator< typename base_class::iterator >  iterator;
 169
 170         /// Const iterator type
 171         typedef skip_list::details::iterator< typename base_class::const_iterator >   const_iterator;
 172
 173         /// Returns a forward iterator addressing the first element in a map
 174         iterator begin()
 175         {
 176             return iterator( base_class::begin() );
 177         }
 178
 179         /// Returns a forward const iterator addressing the first element in a map
 180         const_iterator begin() const
 181         {
 182             return cbegin();
 183         }
 184         /// Returns a forward const iterator addressing the first element in a map
 185         const_iterator cbegin() const
 186         {
 187             return const_iterator( base_class::cbegin() );
 188         }
 189
 190         /// Returns a forward iterator that addresses the location succeeding the last element in a map.
 191         iterator end()
 192         {
 193             return iterator( base_class::end() );
 194         }
 195
 196         /// Returns a forward const iterator that addresses the location succeeding the last element in a map.
 197         const_iterator end() const
 198         {
 199             return cend();
 200         }
 201         /// Returns a forward const iterator that addresses the location succeeding the last element in a map.
 202         const_iterator cend() const
 203         {
 204             return const_iterator( base_class::cend() );
 205         }
 206
 207     public:
 208         /// Inserts new node with key and default value
 209         /**
 210             The function creates a node with \p key and default value, and then inserts the node created into the map.
 211
 212             Preconditions:
 213             - The \p key_type should be constructible from a value of type \p K.
 214                 In trivial case, \p K is equal to \p key_type.
 215             - The \p mapped_type should be default-constructible.
 216
 217             RCU \p synchronize method can be called. RCU should not be locked.
 218
 219             Returns \p true if inserting successful, \p false otherwise.
 220         */
 221         template <typename K>
 222         bool insert( K const& key )
 223         {
 224             return insert_key( key, [](value_type&){} );
 225         }
 226
 227         /// Inserts new node
 228         /**
 229             The function creates a node with copy of \p val value
 230             and then inserts the node created into the map.
 231
 232             Preconditions:
 233             - The \p key_type should be constructible from \p key of type \p K.
 234             - The \p value_type should be constructible from \p val of type \p V.
 235
 236             RCU \p synchronize method can be called. RCU should not be locked.
 237
 238             Returns \p true if \p val is inserted into the set, \p false otherwise.
 239         */
 240         template <typename K, typename V>
 241         bool insert( K const& key, V const& val )
 242         {
 243             scoped_node_ptr pNode( node_allocator().New( random_level(), key, val ));
 244             if ( base_class::insert( *pNode ))
 245             {
 246                 pNode.release();
 247                 return true;
 248             }
 249             return false;
 250         }
 251
 252         /// Inserts new node and initialize it by a functor
 253         /**
 254             This function inserts new node with key \p key and if inserting is successful then it calls
 255             \p func functor with signature
 256             \code
 257                 struct functor {
 258                     void operator()( value_type& item );
 259                 };
 260             \endcode
 261
 262             The argument \p item of user-defined functor \p func is the reference
 263             to the map's item inserted:
 264                 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
 265                 - <tt>item.second</tt> is a reference to item's value that may be changed.
 266
 267             The function allows to split creating of new item into three part:
 268             - create item from \p key;
 269             - insert new item into the map;
 270             - if inserting is successful, initialize the value of item by calling \p func functor
 271
 272             This can be useful if complete initialization of object of \p value_type is heavyweight and
 273             it is preferable that the initialization should be completed only if inserting is successful.
 274
 275             RCU \p synchronize method can be called. RCU should not be locked.
 276         */
 277         template <typename K, typename Func>
 278         bool insert_key( const K& key, Func func )
 279         {
 280             scoped_node_ptr pNode( node_allocator().New( random_level(), key ));
 281             if ( base_class::insert( *pNode, [&func]( node_type& item ) { func( item.m_Value ); } )) {
 282                 pNode.release();
 283                 return true;
 284             }
 285             return false;
 286         }
 287
 288         /// For key \p key inserts data of type \p value_type created in-place from \p args
 289         /**
 290             Returns \p true if inserting successful, \p false otherwise.
 291
 292             RCU \p synchronize() method can be called. RCU should not be locked.
 293         */
 294         template <typename K, typename... Args>
 295         bool emplace( K&& key, Args&&... args )
 296         {
 297             scoped_node_ptr pNode( node_allocator().New( random_level(), std::forward<K>(key), std::forward<Args>(args)... ));
 298             if ( base_class::insert( *pNode )) {
 299                 pNode.release();
 300                 return true;
 301             }
 302             return false;
 303         }
 304
 305         /// Ensures that the \p key exists in the map
 306         /**
 307             The operation performs inserting or changing data with lock-free manner.
 308
 309             If the \p key not found in the map, then the new item created from \p key
 310             is inserted into the map (note that in this case the \ref key_type should be
 311             constructible from type \p K).
 312             Otherwise, the functor \p func is called with item found.
 313             The functor \p Func interface is:
 314             \code
 315                 struct my_functor {
 316                     void operator()( bool bNew, value_type& item );
 317                 };
 318             \endcode
 319             with arguments:
 320             - \p bNew - \p true if the item has been inserted, \p false otherwise
 321             - \p item - item of the list
 322
 323             The functor may change any fields of \p item.second.
 324
 325             RCU \p synchronize() method can be called. RCU should not be locked.
 326
 327             Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
 328             \p second is true if new item has been added or \p false if the item with \p key
 329             already is in the list.
 330
 331             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
 332         */
 333         template <typename K, typename Func>
 334         std::pair<bool, bool> ensure( K const& key, Func func )
 335         {
 336             scoped_node_ptr pNode( node_allocator().New( random_level(), key ));
 337             std::pair<bool, bool> res = base_class::ensure( *pNode,
 338                 [&func](bool bNew, node_type& item, node_type const& ){ func( bNew, item.m_Value ); }
 339             );
 340             if ( res.first && res.second )
 341                 pNode.release();
 342             return res;
 343         }
 344
 345         /// Delete \p key from the map
 346         /**\anchor cds_nonintrusive_SkipListMap_rcu_erase_val
 347
 348             RCU \p synchronize method can be called. RCU should not be locked.
 349
 350             Return \p true if \p key is found and deleted, \p false otherwise
 351         */
 352         template <typename K>
 353         bool erase( K const& key )
 354         {
 355             return base_class::erase(key);
 356         }
 357
 358         /// Deletes the item from the map using \p pred predicate for searching
 359         /**
 360             The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_erase_val "erase(K const&)"
 361             but \p pred is used for key comparing.
 362             \p Less functor has the interface like \p std::less.
 363             \p Less must imply the same element order as the comparator used for building the map.
 364         */
 365         template <typename K, typename Less>
 366         bool erase_with( K const& key, Less pred )
 367         {
 368             return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >());
 369         }
 370
 371         /// Delete \p key from the map
 372         /** \anchor cds_nonintrusive_SkipListMap_rcu_erase_func
 373
 374             The function searches an item with key \p key, calls \p f functor
 375             and deletes the item. If \p key is not found, the functor is not called.
 376
 377             The functor \p Func interface:
 378             \code
 379             struct extractor {
 380                 void operator()(value_type& item) { ... }
 381             };
 382             \endcode
 383
 384             RCU \p synchronize method can be called. RCU should not be locked.
 385
 386             Return \p true if key is found and deleted, \p false otherwise
 387         */
 388         template <typename K, typename Func>
 389         bool erase( K const& key, Func f )
 390         {
 391             return base_class::erase( key, [&f]( node_type& node) { f( node.m_Value ); } );
 392         }
 393
 394         /// Deletes the item from the map using \p pred predicate for searching
 395         /**
 396             The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_erase_func "erase(K const&, Func)"
 397             but \p pred is used for key comparing.
 398             \p Less functor has the interface like \p std::less.
 399             \p Less must imply the same element order as the comparator used for building the map.
 400         */
 401         template <typename K, typename Less, typename Func>
 402         bool erase_with( K const& key, Less pred, Func f )
 403         {
 404             return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >(),
 405                 [&f]( node_type& node) { f( node.m_Value ); } );
 406         }
 407
 408         /// Extracts the item from the map with specified \p key
 409         /** \anchor cds_nonintrusive_SkipListMap_rcu_extract
 410             The function searches an item with key equal to \p key in the map,
 411             unlinks it from the set, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
 412             If the item is not found the function returns an empty \p exempt_ptr
 413
 414             Note the compare functor from \p Traits class' template argument
 415             should accept a parameter of type \p K that can be not the same as \p key_type.
 416
 417             RCU \p synchronize() method can be called. RCU should NOT be locked.
 418
 419             The function does not free the item found.
 420             The item will be implicitly freed when the returned object is destroyed or when
 421             its \p release() member function is called.
 422         */
 423         template <typename K>
 424         exempt_ptr extract( K const& key )
 425         {
 426             return exempt_ptr( base_class::do_extract( key ));
 427         }
 428
 429         /// Extracts the item from the map with comparing functor \p pred
 430         /**
 431             The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_extract "extract(exempt_ptr&, K const&)"
 432             but \p pred predicate is used for key comparing.
 433             \p Less has the semantics like \p std::less.
 434             \p pred must imply the same element order as the comparator used for building the map.
 435         */
 436         template <typename K, typename Less>
 437         exempt_ptr extract_with( K const& key, Less pred )
 438         {
 439             return exempt_ptr( base_class::do_extract_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >()));
 440         }
 441
 442         /// Extracts an item with minimal key from the map
 443         /**
 444             The function searches an item with minimal key, unlinks it,
 445             and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item.
 446             If the skip-list is empty the function returns an empty \p exempt_ptr.
 447
 448             RCU \p synchronize method can be called. RCU should NOT be locked.
 449
 450             The function does not free the item found.
 451             The item will be implicitly freed when the returned object is destroyed or when
 452             its \p release() member function is called.
 453         */
 454         exempt_ptr extract_min()
 455         {
 456             return exempt_ptr( base_class::do_extract_min());
 457         }
 458
 459         /// Extracts an item with maximal key from the map
 460         /**
 461             The function searches an item with maximal key, unlinks it from the set,
 462             and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item.
 463             If the skip-list is empty the function returns an empty \p exempt_ptr.
 464
 465             RCU \p synchronize method can be called. RCU should NOT be locked.
 466
 467             The function does not free the item found.
 468             The item will be implicitly freed when the returned object is destroyed or when
 469             its \p release() member function is called.
 470             */
 471         exempt_ptr extract_max()
 472         {
 473             return exempt_ptr( base_class::do_extract_max());
 474         }
 475
 476         /// Find the key \p key
 477         /** \anchor cds_nonintrusive_SkipListMap_rcu_find_cfunc
 478
 479             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 480             The interface of \p Func functor is:
 481             \code
 482             struct functor {
 483                 void operator()( value_type& item );
 484             };
 485             \endcode
 486             where \p item is the item found.
 487
 488             The functor may change \p item.second.
 489
 490             The function applies RCU lock internally.
 491
 492             The function returns \p true if \p key is found, \p false otherwise.
 493         */
 494         template <typename K, typename Func>
 495         bool find( K const& key, Func f )
 496         {
 497             return base_class::find( key, [&f](node_type& item, K const& ) { f( item.m_Value );});
 498         }
 499
 500         /// Finds the key \p val using \p pred predicate for searching
 501         /**
 502             The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_find_cfunc "find(K const&, Func)"
 503             but \p pred is used for key comparing.
 504             \p Less functor has the interface like \p std::less.
 505             \p Less must imply the same element order as the comparator used for building the map.
 506         */
 507         template <typename K, typename Less, typename Func>
 508         bool find_with( K const& key, Less pred, Func f )
 509         {
 510             return base_class::find_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >(),
 511                 [&f](node_type& item, K const& ) { f( item.m_Value );});
 512         }
 513
 514         /// Find the key \p key
 515         /** \anchor cds_nonintrusive_SkipListMap_rcu_find_val
 516
 517             The function searches the item with key equal to \p key
 518             and returns \p true if it is found, and \p false otherwise.
 519
 520             The function applies RCU lock internally.
 521         */
 522         template <typename K>
 523         bool find( K const& key )
 524         {
 525             return base_class::find( key );
 526         }
 527
 528         /// Finds the key \p val using \p pred predicate for searching
 529         /**
 530             The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_find_val "find(K const&)"
 531             but \p pred is used for key comparing.
 532             \p Less functor has the interface like \p std::less.
 533             \p Less must imply the same element order as the comparator used for building the map.
 534         */
 535         template <typename K, typename Less>
 536         bool find_with( K const& key, Less pred )
 537         {
 538             return base_class::find_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >() );
 539         }
 540
 541         /// Finds the key \p key and return the item found
 542         /** \anchor cds_nonintrusive_SkipListMap_rcu_get
 543             The function searches the item with key equal to \p key and returns the pointer to item found.
 544             If \p key is not found it returns \p nullptr.
 545
 546             Note the compare functor in \p Traits class' template argument
 547             should accept a parameter of type \p K that can be not the same as \p key_type.
 548
 549             RCU should be locked before call of this function.
 550             Returned item is valid only while RCU is locked:
 551             \code
 552             typedef cds::container::SkipListMap< cds::urcu::gc< cds::urcu::general_buffered<> >, int, foo, my_traits > skip_list;
 553             skip_list theList;
 554             // ...
 555             {
 556                 // Lock RCU
 557                 skip_list::rcu_lock lock;
 558
 559                 skip_list::value_type * pVal = theList.get( 5 );
 560                 // Deal with pVal
 561                 //...
 562
 563                 // Unlock RCU by rcu_lock destructor
 564                 // pVal can be freed at any time after RCU unlocking
 565             }
 566             \endcode
 567
 568             After RCU unlocking the \p %force_dispose member function can be called manually,
 569             see \ref force_dispose for explanation.
 570         */
 571         template <typename K>
 572         value_type * get( K const& key )
 573         {
 574             return to_value_ptr( base_class::get( key ));
 575         }
 576
 577         /// Finds the key \p key and return the item found
 578         /**
 579             The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_get "get(K const&)"
 580             but \p pred is used for comparing the keys.
 581
 582             \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
 583             in any order.
 584             \p pred must imply the same element order as the comparator used for building the map.
 585         */
 586         template <typename K, typename Less>
 587         value_type * get_with( K const& key, Less pred )
 588         {
 589             return to_value_ptr( base_class::get_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >() ));
 590         }
 591
 592         /// Clears the map (not atomic)
 593         void clear()
 594         {
 595             base_class::clear();
 596         }
 597
 598         /// Checks if the map is empty
 599         /**
 600             Emptiness is checked by item counting: if item count is zero then the map is empty.
 601         */
 602         bool empty() const
 603         {
 604             return base_class::empty();
 605         }
 606
 607         /// Returns item count in the map
 608         size_t size() const
 609         {
 610             return base_class::size();
 611         }
 612
 613         /// Returns const reference to internal statistics
 614         stat const& statistics() const
 615         {
 616             return base_class::statistics();
 617         }
 618
 619         /// Clears internal list of ready-to-delete items passing them to RCU reclamation cycle
 620         /** @copydetails cds_intrusive_SkipListSet_rcu_force_dispose
 621         */
 622         void force_dispose()
 623         {
 624             return base_class::force_dispose();
 625         }
 626     };
 627 }} // namespace cds::container
 628
 629 #endif // #ifndef __CDS_CONTAINER_SKIP_LIST_MAP_RCU_H