3 #ifndef __CDS_CONTAINER_SKIP_LIST_MAP_RCU_H
4 #define __CDS_CONTAINER_SKIP_LIST_MAP_RCU_H
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>
10 namespace cds { namespace container {
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
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
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
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"
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.
44 Like STL map class, \p %SkipListMap stores its key-value pair as <tt>std:pair< K const, T></tt>.
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.
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.
57 The requirement of RCU lock during iterating means that deletion of the elements (i.e. \ref erase)
60 @warning The iterator object cannot be passed between threads
62 The iterator class supports the following minimalistic interface:
69 iterator( iterator const& s);
71 value_type * operator ->() const;
72 value_type& operator *() const;
75 iterator& operator ++();
78 iterator& operator = (const iterator& src);
80 bool operator ==(iterator const& i ) const;
81 bool operator !=(iterator const& i ) const;
84 Note, the iterator object returned by \ref end, \p cend member functions points to \p nullptr and should not be dereferenced.
91 #ifdef CDS_DOXYGEN_INVOKED
92 typename Traits = skip_list::traits
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 >
101 protected details::make_skip_list_map< cds::urcu::gc< RCU >, Key, T, Traits >::type
105 typedef details::make_skip_list_map< cds::urcu::gc< RCU >, Key, T, Traits > maker;
106 typedef typename maker::type base_class;
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
115 typedef typename maker::value_type value_type;
117 typedef Traits traits; ///< Map traits
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
129 typedef typename maker::node_type node_type;
130 typedef typename maker::node_allocator node_allocator;
132 typedef std::unique_ptr< node_type, typename maker::node_deallocator > scoped_node_ptr;
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;
140 /// pointer to extracted node
141 typedef cds::urcu::exempt_ptr< gc, node_type, value_type, typename maker::intrusive_type_traits::disposer > exempt_ptr;
145 unsigned int random_level()
147 return base_class::random_level();
150 value_type * to_value_ptr( node_type * pNode ) const CDS_NOEXCEPT
152 return pNode ? &pNode->m_Value : nullptr;
162 /// Destructor destroys the set object
168 typedef skip_list::details::iterator< typename base_class::iterator > iterator;
170 /// Const iterator type
171 typedef skip_list::details::iterator< typename base_class::const_iterator > const_iterator;
173 /// Returns a forward iterator addressing the first element in a map
176 return iterator( base_class::begin() );
179 /// Returns a forward const iterator addressing the first element in a map
180 const_iterator begin() const
184 /// Returns a forward const iterator addressing the first element in a map
185 const_iterator cbegin() const
187 return const_iterator( base_class::cbegin() );
190 /// Returns a forward iterator that addresses the location succeeding the last element in a map.
193 return iterator( base_class::end() );
196 /// Returns a forward const iterator that addresses the location succeeding the last element in a map.
197 const_iterator end() const
201 /// Returns a forward const iterator that addresses the location succeeding the last element in a map.
202 const_iterator cend() const
204 return const_iterator( base_class::cend() );
208 /// Inserts new node with key and default value
210 The function creates a node with \p key and default value, and then inserts the node created into the map.
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.
217 RCU \p synchronize method can be called. RCU should not be locked.
219 Returns \p true if inserting successful, \p false otherwise.
221 template <typename K>
222 bool insert( K const& key )
224 return insert_key( key, [](value_type&){} );
229 The function creates a node with copy of \p val value
230 and then inserts the node created into the map.
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.
236 RCU \p synchronize method can be called. RCU should not be locked.
238 Returns \p true if \p val is inserted into the set, \p false otherwise.
240 template <typename K, typename V>
241 bool insert( K const& key, V const& val )
243 scoped_node_ptr pNode( node_allocator().New( random_level(), key, val ));
244 if ( base_class::insert( *pNode ))
252 /// Inserts new node and initialize it by a functor
254 This function inserts new node with key \p key and if inserting is successful then it calls
255 \p func functor with signature
258 void operator()( value_type& item );
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.
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
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.
275 RCU \p synchronize method can be called. RCU should not be locked.
277 template <typename K, typename Func>
278 bool insert_key( const K& key, Func func )
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 ); } )) {
288 /// For key \p key inserts data of type \p value_type created in-place from \p args
290 Returns \p true if inserting successful, \p false otherwise.
292 RCU \p synchronize() method can be called. RCU should not be locked.
294 template <typename K, typename... Args>
295 bool emplace( K&& key, Args&&... args )
297 scoped_node_ptr pNode( node_allocator().New( random_level(), std::forward<K>(key), std::forward<Args>(args)... ));
298 if ( base_class::insert( *pNode )) {
305 /// Ensures that the \p key exists in the map
307 The operation performs inserting or changing data with lock-free manner.
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:
316 void operator()( bool bNew, value_type& item );
320 - \p bNew - \p true if the item has been inserted, \p false otherwise
321 - \p item - item of the list
323 The functor may change any fields of \p item.second.
325 RCU \p synchronize() method can be called. RCU should not be locked.
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.
331 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
333 template <typename K, typename Func>
334 std::pair<bool, bool> ensure( K const& key, Func func )
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 ); }
340 if ( res.first && res.second )
345 /// Delete \p key from the map
346 /**\anchor cds_nonintrusive_SkipListMap_rcu_erase_val
348 RCU \p synchronize method can be called. RCU should not be locked.
350 Return \p true if \p key is found and deleted, \p false otherwise
352 template <typename K>
353 bool erase( K const& key )
355 return base_class::erase(key);
358 /// Deletes the item from the map using \p pred predicate for searching
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.
365 template <typename K, typename Less>
366 bool erase_with( K const& key, Less pred )
368 return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >());
371 /// Delete \p key from the map
372 /** \anchor cds_nonintrusive_SkipListMap_rcu_erase_func
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.
377 The functor \p Func interface:
380 void operator()(value_type& item) { ... }
384 RCU \p synchronize method can be called. RCU should not be locked.
386 Return \p true if key is found and deleted, \p false otherwise
388 template <typename K, typename Func>
389 bool erase( K const& key, Func f )
391 return base_class::erase( key, [&f]( node_type& node) { f( node.m_Value ); } );
394 /// Deletes the item from the map using \p pred predicate for searching
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.
401 template <typename K, typename Less, typename Func>
402 bool erase_with( K const& key, Less pred, Func f )
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 ); } );
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 it in \p result parameter.
412 If the item with key equal to \p key is not found the function returns \p false.
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.
417 RCU \p synchronize() method can be called. RCU should NOT be locked.
419 The function does not free the item found.
420 The item will be implicitly freed when \p result object is destroyed or when
421 <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
422 @note Before reusing \p result object you should call its \p release() method.
424 template <typename K>
425 bool extract( exempt_ptr& result, K const& key )
427 return base_class::do_extract( result, key );
430 /// Extracts the item from the map with comparing functor \p pred
432 The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_extract "extract(exempt_ptr&, K const&)"
433 but \p pred predicate is used for key comparing.
434 \p Less has the semantics like \p std::less.
435 \p pred must imply the same element order as the comparator used for building the map.
437 template <typename K, typename Less>
438 bool extract_with( exempt_ptr& result, K const& key, Less pred )
440 return base_class::do_extract_with( result, key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >());
443 /// Extracts an item with minimal key from the map
445 The function searches an item with minimal key, unlinks it, and returns the item found in \p result parameter.
446 If the skip-list is empty the function returns \p false.
448 RCU \p synchronize method can be called. RCU should NOT be locked.
450 The function does not free the item found.
451 The item will be implicitly freed when \p result object is destroyed or when
452 <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
453 @note Before reusing \p result object you should call its \p release() method.
455 bool extract_min( exempt_ptr& result )
457 return base_class::do_extract_min(result);
460 /// Extracts an item with maximal key from the map
462 The function searches an item with maximal key, unlinks it from the set, and returns the item found
463 in \p result parameter. If the skip-list is empty the function returns \p false.
465 RCU \p synchronize method can be called. RCU should NOT be locked.
467 The function does not free the item found.
468 The item will be implicitly freed when \p result object is destroyed or when
469 <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
470 @note Before reusing \p result object you should call its \p release() method.
472 bool extract_max( exempt_ptr& result )
474 return base_class::do_extract_max(result);
477 /// Find the key \p key
478 /** \anchor cds_nonintrusive_SkipListMap_rcu_find_cfunc
480 The function searches the item with key equal to \p key and calls the functor \p f for item found.
481 The interface of \p Func functor is:
484 void operator()( value_type& item );
487 where \p item is the item found.
489 The functor may change \p item.second.
491 The function applies RCU lock internally.
493 The function returns \p true if \p key is found, \p false otherwise.
495 template <typename K, typename Func>
496 bool find( K const& key, Func f )
498 return base_class::find( key, [&f](node_type& item, K const& ) { f( item.m_Value );});
501 /// Finds the key \p val using \p pred predicate for searching
503 The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_find_cfunc "find(K const&, Func)"
504 but \p pred is used for key comparing.
505 \p Less functor has the interface like \p std::less.
506 \p Less must imply the same element order as the comparator used for building the map.
508 template <typename K, typename Less, typename Func>
509 bool find_with( K const& key, Less pred, Func f )
511 return base_class::find_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >(),
512 [&f](node_type& item, K const& ) { f( item.m_Value );});
515 /// Find the key \p key
516 /** \anchor cds_nonintrusive_SkipListMap_rcu_find_val
518 The function searches the item with key equal to \p key
519 and returns \p true if it is found, and \p false otherwise.
521 The function applies RCU lock internally.
523 template <typename K>
524 bool find( K const& key )
526 return base_class::find( key );
529 /// Finds the key \p val using \p pred predicate for searching
531 The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_find_val "find(K const&)"
532 but \p pred is used for key comparing.
533 \p Less functor has the interface like \p std::less.
534 \p Less must imply the same element order as the comparator used for building the map.
536 template <typename K, typename Less>
537 bool find_with( K const& key, Less pred )
539 return base_class::find_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >() );
542 /// Finds the key \p key and return the item found
543 /** \anchor cds_nonintrusive_SkipListMap_rcu_get
544 The function searches the item with key equal to \p key and returns the pointer to item found.
545 If \p key is not found it returns \p nullptr.
547 Note the compare functor in \p Traits class' template argument
548 should accept a parameter of type \p K that can be not the same as \p key_type.
550 RCU should be locked before call of this function.
551 Returned item is valid only while RCU is locked:
553 typedef cds::container::SkipListMap< cds::urcu::gc< cds::urcu::general_buffered<> >, int, foo, my_traits > skip_list;
558 skip_list::rcu_lock lock;
560 skip_list::value_type * pVal = theList.get( 5 );
564 // Unlock RCU by rcu_lock destructor
565 // pVal can be freed at any time after RCU unlocking
569 After RCU unlocking the \p %force_dispose member function can be called manually,
570 see \ref force_dispose for explanation.
572 template <typename K>
573 value_type * get( K const& key )
575 return to_value_ptr( base_class::get( key ));
578 /// Finds the key \p key and return the item found
580 The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_get "get(K const&)"
581 but \p pred is used for comparing the keys.
583 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
585 \p pred must imply the same element order as the comparator used for building the map.
587 template <typename K, typename Less>
588 value_type * get_with( K const& key, Less pred )
590 return to_value_ptr( base_class::get_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >() ));
593 /// Clears the map (not atomic)
599 /// Checks if the map is empty
601 Emptiness is checked by item counting: if item count is zero then the map is empty.
605 return base_class::empty();
608 /// Returns item count in the map
611 return base_class::size();
614 /// Returns const reference to internal statistics
615 stat const& statistics() const
617 return base_class::statistics();
620 /// Clears internal list of ready-to-delete items passing them to RCU reclamation cycle
621 /** @copydetails cds_intrusive_SkipListSet_rcu_force_dispose
625 return base_class::force_dispose();
628 }} // namespace cds::container
630 #endif // #ifndef __CDS_CONTAINER_SKIP_LIST_MAP_RCU_H