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 - type traits. See skip_list::type_traits for explanation.
42 It is possible to declare option-based list with cds::container::skip_list::make_traits metafunction istead of \p Traits template
44 Template argument list \p Options of cds::container::skip_list::make_traits metafunction are:
45 - opt::compare - key compare functor. No default functor is provided.
46 If the option is not specified, the opt::less is used.
47 - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<K>.
48 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
49 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
50 or opt::v::sequential_consistent (sequentially consisnent memory model).
51 - skip_list::random_level_generator - random level generator. Can be skip_list::xorshift, skip_list::turbo_pascal or
52 user-provided one. See skip_list::random_level_generator option description for explanation.
53 Default is \p %skip_list::turbo_pascal.
54 - opt::allocator - allocator for skip-list node. Default is \ref CDS_DEFAULT_ALLOCATOR.
55 - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::Default is used.
56 - opt::stat - internal statistics. Available types: skip_list::stat, skip_list::empty_stat (the default)
57 - opt::rcu_check_deadlock - a deadlock checking policy. Default is opt::v::rcu_throw_deadlock
59 Like STL map class, \p %SkipListMap stores its key-value pair as <tt>std:pair< K const, T></tt>.
61 @note Before including <tt><cds/container/skip_list_map_rcu.h></tt> you should include appropriate RCU header file,
62 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
66 The class supports a forward iterator (\ref iterator and \ref const_iterator).
67 The iteration is ordered.
68 You may iterate over skip-list set items only under RCU lock.
69 Only in this case the iterator is thread-safe since
70 while RCU is locked any set's item cannot be reclaimed.
72 The requirement of RCU lock during iterating means that deletion of the elements (i.e. \ref erase)
75 @warning The iterator object cannot be passed between threads
77 The iterator class supports the following minimalistic interface:
84 iterator( iterator const& s);
86 value_type * operator ->() const;
87 value_type& operator *() const;
90 iterator& operator ++();
93 iterator& operator = (const iterator& src);
95 bool operator ==(iterator const& i ) const;
96 bool operator !=(iterator const& i ) const;
99 Note, the iterator object returned by \ref end, \p cend member functions points to \p nullptr and should not be dereferenced.
106 #ifdef CDS_DOXYGEN_INVOKED
107 typename Traits = skip_list::type_traits
112 class SkipListMap< cds::urcu::gc< RCU >, Key, T, Traits >:
113 #ifdef CDS_DOXYGEN_INVOKED
114 protected intrusive::SkipListSet< cds::urcu::gc< RCU >, std::pair<Key const, T>, Traits >
116 protected details::make_skip_list_map< cds::urcu::gc< RCU >, Key, T, Traits >::type
120 typedef details::make_skip_list_map< cds::urcu::gc< RCU >, Key, T, Traits > maker;
121 typedef typename maker::type base_class;
124 typedef typename base_class::gc gc ; ///< Garbage collector used
125 typedef Key key_type ; ///< Key type
126 typedef T mapped_type ; ///< Mapped type
127 # ifdef CDS_DOXYGEN_INVOKED
128 typedef std::pair< K const, T> value_type ; ///< Value type stored in the map
130 typedef typename maker::value_type value_type;
132 typedef Traits options ; ///< Options specified
134 typedef typename base_class::back_off back_off ; ///< Back-off strategy used
135 typedef typename options::allocator allocator_type ; ///< Allocator type used for allocate/deallocate the skip-list nodes
136 typedef typename base_class::item_counter item_counter ; ///< Item counting policy used
137 typedef typename maker::key_comparator key_comparator ; ///< key comparison functor
138 typedef typename base_class::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
139 typedef typename options::random_level_generator random_level_generator ; ///< random level generator
140 typedef typename options::stat stat ; ///< internal statistics type
144 typedef typename maker::node_type node_type;
145 typedef typename maker::node_allocator node_allocator;
147 typedef std::unique_ptr< node_type, typename maker::node_deallocator > scoped_node_ptr;
151 typedef typename base_class::rcu_lock rcu_lock; ///< RCU scoped lock
152 /// Group of \p extract_xxx functions do not require external locking
153 static CDS_CONSTEXPR_CONST bool c_bExtractLockExternal = base_class::c_bExtractLockExternal;
155 /// pointer to extracted node
156 typedef cds::urcu::exempt_ptr< gc, node_type, value_type, typename maker::intrusive_type_traits::disposer > exempt_ptr;
160 unsigned int random_level()
162 return base_class::random_level();
165 value_type * to_value_ptr( node_type * pNode ) const CDS_NOEXCEPT
167 return pNode ? &pNode->m_Value : nullptr;
177 /// Destructor destroys the set object
183 typedef skip_list::details::iterator< typename base_class::iterator > iterator;
185 /// Const iterator type
186 typedef skip_list::details::iterator< typename base_class::const_iterator > const_iterator;
188 /// Returns a forward iterator addressing the first element in a map
191 return iterator( base_class::begin() );
194 /// Returns a forward const iterator addressing the first element in a map
196 const_iterator begin() const
200 const_iterator cbegin()
202 return const_iterator( base_class::cbegin() );
206 /// Returns a forward iterator that addresses the location succeeding the last element in a map.
209 return iterator( base_class::end() );
212 /// Returns a forward const iterator that addresses the location succeeding the last element in a map.
214 const_iterator end() const
218 const_iterator cend()
220 return const_iterator( base_class::cend() );
225 /// Inserts new node with key and default value
227 The function creates a node with \p key and default value, and then inserts the node created into the map.
230 - The \ref key_type should be constructible from a value of type \p K.
231 In trivial case, \p K is equal to \ref key_type.
232 - The \ref mapped_type should be default-constructible.
234 RCU \p synchronize method can be called. RCU should not be locked.
236 Returns \p true if inserting successful, \p false otherwise.
238 template <typename K>
239 bool insert( K const& key )
241 return insert_key( key, [](value_type&){} );
246 The function creates a node with copy of \p val value
247 and then inserts the node created into the map.
250 - The \ref key_type should be constructible from \p key of type \p K.
251 - The \ref value_type should be constructible from \p val of type \p V.
253 RCU \p synchronize method can be called. RCU should not be locked.
255 Returns \p true if \p val is inserted into the set, \p false otherwise.
257 template <typename K, typename V>
258 bool insert( K const& key, V const& val )
260 scoped_node_ptr pNode( node_allocator().New( random_level(), key, val ));
261 if ( base_class::insert( *pNode ))
269 /// Inserts new node and initialize it by a functor
271 This function inserts new node with key \p key and if inserting is successful then it calls
272 \p func functor with signature
275 void operator()( value_type& item );
279 The argument \p item of user-defined functor \p func is the reference
280 to the map's item inserted:
281 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
282 - <tt>item.second</tt> is a reference to item's value that may be changed.
284 The user-defined functor can be passed by reference using \p std::ref
285 and it is called only if inserting is successful.
287 The key_type should be constructible from value of type \p K.
289 The function allows to split creating of new item into two part:
290 - create item from \p key;
291 - insert new item into the map;
292 - if inserting is successful, initialize the value of item by calling \p func functor
294 This can be useful if complete initialization of object of \p value_type is heavyweight and
295 it is preferable that the initialization should be completed only if inserting is successful.
297 RCU \p synchronize method can be called. RCU should not be locked.
299 template <typename K, typename Func>
300 bool insert_key( const K& key, Func func )
302 scoped_node_ptr pNode( node_allocator().New( random_level(), key ));
303 if ( base_class::insert( *pNode, [&func]( node_type& item ) { func( item.m_Value ); } )) {
310 /// For key \p key inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
312 Returns \p true if inserting successful, \p false otherwise.
314 RCU \p synchronize method can be called. RCU should not be locked.
316 template <typename K, typename... Args>
317 bool emplace( K&& key, Args&&... args )
319 scoped_node_ptr pNode( node_allocator().New( random_level(), std::forward<K>(key), std::forward<Args>(args)... ));
320 if ( base_class::insert( *pNode )) {
327 /// Ensures that the \p key exists in the map
329 The operation performs inserting or changing data with lock-free manner.
331 If the \p key not found in the map, then the new item created from \p key
332 is inserted into the map (note that in this case the \ref key_type should be
333 constructible from type \p K).
334 Otherwise, the functor \p func is called with item found.
335 The functor \p Func may be a function with signature:
337 void func( bool bNew, value_type& item );
342 void operator()( bool bNew, value_type& item );
347 - \p bNew - \p true if the item has been inserted, \p false otherwise
348 - \p item - item of the list
350 The functor may change any fields of the \p item.second that is \ref value_type.
352 You may pass \p func argument by reference using \p std::ref
354 RCU \p synchronize method can be called. RCU should not be locked.
356 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
357 \p second is true if new item has been added or \p false if the item with \p key
358 already is in the list.
360 template <typename K, typename Func>
361 std::pair<bool, bool> ensure( K const& key, Func func )
363 scoped_node_ptr pNode( node_allocator().New( random_level(), key ));
364 std::pair<bool, bool> res = base_class::ensure( *pNode,
365 [&func](bool bNew, node_type& item, node_type const& ){ func( bNew, item.m_Value ); }
367 if ( res.first && res.second )
372 /// Delete \p key from the map
373 /**\anchor cds_nonintrusive_SkipListMap_rcu_erase_val
375 RCU \p synchronize method can be called. RCU should not be locked.
377 Return \p true if \p key is found and deleted, \p false otherwise
379 template <typename K>
380 bool erase( K const& key )
382 return base_class::erase(key);
385 /// Deletes the item from the map using \p pred predicate for searching
387 The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_erase_val "erase(K const&)"
388 but \p pred is used for key comparing.
389 \p Less functor has the interface like \p std::less.
390 \p Less must imply the same element order as the comparator used for building the map.
392 template <typename K, typename Less>
393 bool erase_with( K const& key, Less pred )
395 return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >());
398 /// Delete \p key from the map
399 /** \anchor cds_nonintrusive_SkipListMap_rcu_erase_func
401 The function searches an item with key \p key, calls \p f functor
402 and deletes the item. If \p key is not found, the functor is not called.
404 The functor \p Func interface:
407 void operator()(value_type& item) { ... }
410 The functor may be passed by reference using <tt>boost:ref</tt>
412 RCU \p synchronize method can be called. RCU should not be locked.
414 Return \p true if key is found and deleted, \p false otherwise
416 template <typename K, typename Func>
417 bool erase( K const& key, Func f )
419 return base_class::erase( key, [&f]( node_type& node) { f( node.m_Value ); } );
422 /// Deletes the item from the map using \p pred predicate for searching
424 The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_erase_func "erase(K const&, Func)"
425 but \p pred is used for key comparing.
426 \p Less functor has the interface like \p std::less.
427 \p Less must imply the same element order as the comparator used for building the map.
429 template <typename K, typename Less, typename Func>
430 bool erase_with( K const& key, Less pred, Func f )
432 return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >(),
433 [&f]( node_type& node) { f( node.m_Value ); } );
436 /// Extracts the item from the map with specified \p key
437 /** \anchor cds_nonintrusive_SkipListMap_rcu_extract
438 The function searches an item with key equal to \p key in the map,
439 unlinks it from the set, and returns it in \p result parameter.
440 If the item with key equal to \p key is not found the function returns \p false.
442 Note the compare functor from \p Traits class' template argument
443 should accept a parameter of type \p K that can be not the same as \p key_type.
445 RCU \p synchronize method can be called. RCU should NOT be locked.
446 The function does not free the item found.
447 The item will be implicitly freed when \p result object is destroyed or when
448 <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
449 @note Before reusing \p result object you should call its \p release() method.
451 template <typename K>
452 bool extract( exempt_ptr& result, K const& key )
454 return base_class::do_extract( result, key );
457 /// Extracts the item from the map with comparing functor \p pred
459 The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_extract "extract(exempt_ptr&, K const&)"
460 but \p pred predicate is used for key comparing.
461 \p Less has the semantics like \p std::less.
462 \p pred must imply the same element order as the comparator used for building the map.
464 template <typename K, typename Less>
465 bool extract_with( exempt_ptr& result, K const& key, Less pred )
467 return base_class::do_extract_with( result, key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >());
470 /// Extracts an item with minimal key from the map
472 The function searches an item with minimal key, unlinks it, and returns the item found in \p result parameter.
473 If the skip-list is empty the function returns \p false.
475 RCU \p synchronize method can be called. RCU should NOT be locked.
476 The function does not free the item found.
477 The item will be implicitly freed when \p result object is destroyed or when
478 <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
479 @note Before reusing \p result object you should call its \p release() method.
481 bool extract_min( exempt_ptr& result )
483 return base_class::do_extract_min(result);
486 /// Extracts an item with maximal key from the map
488 The function searches an item with maximal key, unlinks it from the set, and returns the item found
489 in \p result parameter. If the skip-list is empty the function returns \p false.
491 RCU \p synchronize method can be called. RCU should NOT be locked.
492 The function does not free the item found.
493 The item will be implicitly freed when \p result object is destroyed or when
494 <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
495 @note Before reusing \p result object you should call its \p release() method.
497 bool extract_max( exempt_ptr& result )
499 return base_class::do_extract_max(result);
502 /// Find the key \p key
503 /** \anchor cds_nonintrusive_SkipListMap_rcu_find_cfunc
505 The function searches the item with key equal to \p key and calls the functor \p f for item found.
506 The interface of \p Func functor is:
509 void operator()( value_type& item );
512 where \p item is the item found.
514 You can pass \p f argument by reference using \p std::ref.
516 The functor may change \p item.second.
518 The function applies RCU lock internally.
520 The function returns \p true if \p key is found, \p false otherwise.
522 template <typename K, typename Func>
523 bool find( K const& key, Func f )
525 return base_class::find( key, [&f](node_type& item, K const& ) { f( item.m_Value );});
528 /// Finds the key \p val using \p pred predicate for searching
530 The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_find_cfunc "find(K const&, Func)"
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.
535 template <typename K, typename Less, typename Func>
536 bool find_with( K const& key, Less pred, Func f )
538 return base_class::find_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >(),
539 [&f](node_type& item, K const& ) { f( item.m_Value );});
542 /// Find the key \p key
543 /** \anchor cds_nonintrusive_SkipListMap_rcu_find_val
545 The function searches the item with key equal to \p key
546 and returns \p true if it is found, and \p false otherwise.
548 The function applies RCU lock internally.
550 template <typename K>
551 bool find( K const& key )
553 return base_class::find( key );
556 /// Finds the key \p val using \p pred predicate for searching
558 The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_find_val "find(K const&)"
559 but \p pred is used for key comparing.
560 \p Less functor has the interface like \p std::less.
561 \p Less must imply the same element order as the comparator used for building the map.
563 template <typename K, typename Less>
564 bool find_with( K const& key, Less pred )
566 return base_class::find_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >() );
569 /// Finds the key \p key and return the item found
570 /** \anchor cds_nonintrusive_SkipListMap_rcu_get
571 The function searches the item with key equal to \p key and returns the pointer to item found.
572 If \p key is not found it returns \p nullptr.
574 Note the compare functor in \p Traits class' template argument
575 should accept a parameter of type \p K that can be not the same as \p key_type.
577 RCU should be locked before call of this function.
578 Returned item is valid only while RCU is locked:
580 typedef cds::container::SkipListMap< cds::urcu::gc< cds::urcu::general_buffered<> >, int, foo, my_traits > skip_list;
585 skip_list::rcu_lock lock;
587 skip_list::value_type * pVal = theList.get( 5 );
591 // Unlock RCU by rcu_lock destructor
592 // pVal can be freed at any time after RCU unlocking
596 After RCU unlocking the \p %force_dispose member function can be called manually,
597 see \ref force_dispose for explanation.
599 template <typename K>
600 value_type * get( K const& key )
602 return to_value_ptr( base_class::get( key ));
605 /// Finds the key \p key and return the item found
607 The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_get "get(K const&)"
608 but \p pred is used for comparing the keys.
610 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
612 \p pred must imply the same element order as the comparator used for building the map.
614 template <typename K, typename Less>
615 value_type * get_with( K const& key, Less pred )
617 return to_value_ptr( base_class::get_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >() ));
626 /// Checks if the map is empty
628 Emptiness is checked by item counting: if item count is zero then the map is empty.
632 return base_class::empty();
635 /// Returns item count in the map
638 return base_class::size();
641 /// Returns const reference to internal statistics
642 stat const& statistics() const
644 return base_class::statistics();
647 /// Clears internal list of ready-to-delete items passing them to RCU reclamation cycle
649 See \ref cds_intrusive_SkipListSet_rcu_force_dispose "intrusive SkipListSet" for explanation
653 return base_class::force_dispose();
656 }} // namespace cds::container
658 #endif // #ifndef __CDS_CONTAINER_SKIP_LIST_MAP_RCU_H