3 #ifndef CDSLIB_CONTAINER_SKIP_LIST_MAP_RCU_H
4 #define CDSLIB_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
128 typedef cds::container::skip_list::implementation_tag implementation_tag;
133 typedef typename maker::node_type node_type;
134 typedef typename maker::node_allocator node_allocator;
136 typedef std::unique_ptr< node_type, typename maker::node_deallocator > scoped_node_ptr;
140 typedef typename base_class::rcu_lock rcu_lock; ///< RCU scoped lock
141 /// Group of \p extract_xxx functions do not require external locking
142 static CDS_CONSTEXPR const bool c_bExtractLockExternal = base_class::c_bExtractLockExternal;
144 /// pointer to extracted node
145 using exempt_ptr = cds::urcu::exempt_ptr< gc, node_type, value_type, typename maker::intrusive_type_traits::disposer >;
149 struct raw_ptr_converter
151 value_type * operator()( node_type * p ) const
153 return p ? &p->m_Value : nullptr;
156 value_type& operator()( node_type& n ) const
161 value_type const& operator()( node_type const& n ) const
169 /// Result of \p get(), \p get_with() functions - pointer to the node found
170 typedef cds::urcu::raw_ptr_adaptor< value_type, typename base_class::raw_ptr, raw_ptr_converter > raw_ptr;
174 unsigned int random_level()
176 return base_class::random_level();
186 /// Destructor destroys the set object
192 typedef skip_list::details::iterator< typename base_class::iterator > iterator;
194 /// Const iterator type
195 typedef skip_list::details::iterator< typename base_class::const_iterator > const_iterator;
197 /// Returns a forward iterator addressing the first element in a map
200 return iterator( base_class::begin() );
203 /// Returns a forward const iterator addressing the first element in a map
204 const_iterator begin() const
208 /// Returns a forward const iterator addressing the first element in a map
209 const_iterator cbegin() const
211 return const_iterator( base_class::cbegin() );
214 /// Returns a forward iterator that addresses the location succeeding the last element in a map.
217 return iterator( base_class::end() );
220 /// Returns a forward const iterator that addresses the location succeeding the last element in a map.
221 const_iterator end() const
225 /// Returns a forward const iterator that addresses the location succeeding the last element in a map.
226 const_iterator cend() const
228 return const_iterator( base_class::cend() );
232 /// Inserts new node with key and default value
234 The function creates a node with \p key and default value, and then inserts the node created into the map.
237 - The \p key_type should be constructible from a value of type \p K.
238 In trivial case, \p K is equal to \p key_type.
239 - The \p mapped_type should be default-constructible.
241 RCU \p synchronize method can be called. RCU should not be locked.
243 Returns \p true if inserting successful, \p false otherwise.
245 template <typename K>
246 bool insert( K const& key )
248 return insert_with( key, [](value_type&){} );
253 The function creates a node with copy of \p val value
254 and then inserts the node created into the map.
257 - The \p key_type should be constructible from \p key of type \p K.
258 - The \p value_type should be constructible from \p val of type \p V.
260 RCU \p synchronize method can be called. RCU should not be locked.
262 Returns \p true if \p val is inserted into the set, \p false otherwise.
264 template <typename K, typename V>
265 bool insert( K const& key, V const& val )
267 scoped_node_ptr pNode( node_allocator().New( random_level(), key, val ));
268 if ( base_class::insert( *pNode ))
276 /// Inserts new node and initialize it by a functor
278 This function inserts new node with key \p key and if inserting is successful then it calls
279 \p func functor with signature
282 void operator()( value_type& item );
286 The argument \p item of user-defined functor \p func is the reference
287 to the map's item inserted:
288 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
289 - <tt>item.second</tt> is a reference to item's value that may be changed.
291 The function allows to split creating of new item into three part:
292 - create item from \p key;
293 - insert new item into the map;
294 - if inserting is successful, initialize the value of item by calling \p func functor
296 This can be useful if complete initialization of object of \p value_type is heavyweight and
297 it is preferable that the initialization should be completed only if inserting is successful.
299 RCU \p synchronize method can be called. RCU should not be locked.
301 template <typename K, typename Func>
302 bool insert_with( const K& key, Func func )
304 scoped_node_ptr pNode( node_allocator().New( random_level(), key ));
305 if ( base_class::insert( *pNode, [&func]( node_type& item ) { func( item.m_Value ); } )) {
312 /// For key \p key inserts data of type \p value_type created in-place from \p args
314 Returns \p true if inserting successful, \p false otherwise.
316 RCU \p synchronize() method can be called. RCU should not be locked.
318 template <typename K, typename... Args>
319 bool emplace( K&& key, Args&&... args )
321 scoped_node_ptr pNode( node_allocator().New( random_level(), std::forward<K>(key), std::forward<Args>(args)... ));
322 if ( base_class::insert( *pNode )) {
329 /// Updates data by \p key
331 The operation performs inserting or changing data with lock-free manner.
333 If the \p key not found in the map, then the new item created from \p key
334 is inserted into the map iff \p bInsert is \p true.
335 Otherwise, if \p key found, the functor \p func is called with item found.
336 The functor \p Func interface is:
339 void operator()( bool bNew, value_type& item );
343 - \p bNew - \p true if the item has been inserted, \p false otherwise
344 - \p item - item of the map
346 The functor may change any fields of \p item.second.
348 RCU \p synchronize() method can be called. RCU should not be locked.
350 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
351 \p second is \p true if new item has been added or \p false if the item with \p key
354 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
356 template <typename K, typename Func>
357 std::pair<bool, bool> update( K const& key, Func func, bool bInsert = true )
359 scoped_node_ptr pNode( node_allocator().New( random_level(), key ));
360 std::pair<bool, bool> res = base_class::update( *pNode,
361 [&func](bool bNew, node_type& item, node_type const& ){ func( bNew, item.m_Value );},
364 if ( res.first && res.second )
369 // Deprecated, use update()
370 template <typename K, typename Func>
371 std::pair<bool, bool> ensure( K const& key, Func func )
373 return update( key, func, true );
377 /// Delete \p key from the map
378 /**\anchor cds_nonintrusive_SkipListMap_rcu_erase_val
380 RCU \p synchronize method can be called. RCU should not be locked.
382 Return \p true if \p key is found and deleted, \p false otherwise
384 template <typename K>
385 bool erase( K const& key )
387 return base_class::erase(key);
390 /// Deletes the item from the map using \p pred predicate for searching
392 The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_erase_val "erase(K const&)"
393 but \p pred is used for key comparing.
394 \p Less functor has the interface like \p std::less.
395 \p Less must imply the same element order as the comparator used for building the map.
397 template <typename K, typename Less>
398 bool erase_with( K const& key, Less pred )
401 return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >());
404 /// Delete \p key from the map
405 /** \anchor cds_nonintrusive_SkipListMap_rcu_erase_func
407 The function searches an item with key \p key, calls \p f functor
408 and deletes the item. If \p key is not found, the functor is not called.
410 The functor \p Func interface:
413 void operator()(value_type& item) { ... }
417 RCU \p synchronize method can be called. RCU should not be locked.
419 Return \p true if key is found and deleted, \p false otherwise
421 template <typename K, typename Func>
422 bool erase( K const& key, Func f )
424 return base_class::erase( key, [&f]( node_type& node) { f( node.m_Value ); } );
427 /// Deletes the item from the map using \p pred predicate for searching
429 The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_erase_func "erase(K const&, Func)"
430 but \p pred is used for key comparing.
431 \p Less functor has the interface like \p std::less.
432 \p Less must imply the same element order as the comparator used for building the map.
434 template <typename K, typename Less, typename Func>
435 bool erase_with( K const& key, Less pred, Func f )
438 return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >(),
439 [&f]( node_type& node) { f( node.m_Value ); } );
442 /// Extracts the item from the map with specified \p key
443 /** \anchor cds_nonintrusive_SkipListMap_rcu_extract
444 The function searches an item with key equal to \p key in the map,
445 unlinks it from the set, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
446 If the item is not found the function returns an empty \p exempt_ptr
448 Note the compare functor from \p Traits class' template argument
449 should accept a parameter of type \p K that can be not the same as \p key_type.
451 RCU \p synchronize() method can be called. RCU should NOT be locked.
453 The function does not free the item found.
454 The item will be implicitly freed when the returned object is destroyed or when
455 its \p release() member function is called.
457 template <typename K>
458 exempt_ptr extract( K const& key )
460 return exempt_ptr( base_class::do_extract( key ));
463 /// Extracts the item from the map with comparing functor \p pred
465 The function is an analog of \p extract(K const&) but \p pred predicate is used for key comparing.
466 \p Less has the semantics like \p std::less.
467 \p pred must imply the same element order as the comparator used for building the map.
469 template <typename K, typename Less>
470 exempt_ptr extract_with( K const& key, Less pred )
473 return exempt_ptr( base_class::do_extract_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >()));
476 /// Extracts an item with minimal key from the map
478 The function searches an item with minimal key, unlinks it,
479 and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item.
480 If the skip-list is empty the function returns an empty \p exempt_ptr.
482 RCU \p synchronize method can be called. RCU should NOT be locked.
484 The function does not free the item found.
485 The item will be implicitly freed when the returned object is destroyed or when
486 its \p release() member function is called.
488 exempt_ptr extract_min()
490 return exempt_ptr( base_class::do_extract_min());
493 /// Extracts an item with maximal key from the map
495 The function searches an item with maximal key, unlinks it from the set,
496 and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item.
497 If the skip-list is empty the function returns an empty \p exempt_ptr.
499 RCU \p synchronize method can be called. RCU should NOT be locked.
501 The function does not free the item found.
502 The item will be implicitly freed when the returned object is destroyed or when
503 its \p release() member function is called.
505 exempt_ptr extract_max()
507 return exempt_ptr( base_class::do_extract_max());
510 /// Find the key \p key
511 /** \anchor cds_nonintrusive_SkipListMap_rcu_find_cfunc
513 The function searches the item with key equal to \p key and calls the functor \p f for item found.
514 The interface of \p Func functor is:
517 void operator()( value_type& item );
520 where \p item is the item found.
522 The functor may change \p item.second.
524 The function applies RCU lock internally.
526 The function returns \p true if \p key is found, \p false otherwise.
528 template <typename K, typename Func>
529 bool find( K const& key, Func f )
531 return base_class::find( key, [&f](node_type& item, K const& ) { f( item.m_Value );});
534 /// Finds the key \p val using \p pred predicate for searching
536 The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_find_cfunc "find(K const&, Func)"
537 but \p pred is used for key comparing.
538 \p Less functor has the interface like \p std::less.
539 \p Less must imply the same element order as the comparator used for building the map.
541 template <typename K, typename Less, typename Func>
542 bool find_with( K const& key, Less pred, Func f )
545 return base_class::find_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >(),
546 [&f](node_type& item, K const& ) { f( item.m_Value );});
549 /// Checks whether the map contains \p key
551 The function searches the item with key equal to \p key
552 and returns \p true if it is found, and \p false otherwise.
554 The function applies RCU lock internally.
556 template <typename K>
557 bool contains( K const& key )
559 return base_class::contains( key );
562 // Deprecated, use contains()
563 template <typename K>
564 bool find( K const& key )
566 return contains( key );
570 /// Checks whether the map contains \p key using \p pred predicate for searching
572 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
573 \p Less functor has the interface like \p std::less.
574 \p Less must imply the same element order as the comparator used for building the set.
576 template <typename K, typename Less>
577 bool contains( K const& key, Less pred )
580 return base_class::contains( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >() );
583 // Deprecated, use contains()
584 template <typename K, typename Less>
585 bool find_with( K const& key, Less pred )
587 return contains( key, pred );
591 /// Finds the key \p key and return the item found
592 /** \anchor cds_nonintrusive_SkipListMap_rcu_get
593 The function searches the item with key equal to \p key and returns a \p raw_ptr object pointing to an item found.
594 If \p key is not found it returns empty \p raw_ptr.
596 Note the compare functor in \p Traits class' template argument
597 should accept a parameter of type \p K that can be not the same as \p key_type.
599 RCU should be locked before call of this function.
600 Returned item is valid only while RCU is locked:
602 typedef cds::container::SkipListMap< cds::urcu::gc< cds::urcu::general_buffered<> >, int, foo, my_traits > skip_list;
605 typename skip_list::raw_ptr pVal;
608 skip_list::rcu_lock lock;
610 pVal = theList.get( 5 );
616 // You can manually release pVal after RCU-locked section
620 template <typename K>
621 raw_ptr get( K const& key )
623 return raw_ptr( base_class::get( key ));
626 /// Finds the key \p key and return the item found
628 The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_get "get(K const&)"
629 but \p pred is used for comparing the keys.
631 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
633 \p pred must imply the same element order as the comparator used for building the map.
635 template <typename K, typename Less>
636 raw_ptr get_with( K const& key, Less pred )
639 return raw_ptr( base_class::get_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >() ));
642 /// Clears the map (not atomic)
648 /// Checks if the map is empty
650 Emptiness is checked by item counting: if item count is zero then the map is empty.
654 return base_class::empty();
657 /// Returns item count in the map
660 return base_class::size();
663 /// Returns const reference to internal statistics
664 stat const& statistics() const
666 return base_class::statistics();
669 }} // namespace cds::container
671 #endif // #ifndef CDSLIB_CONTAINER_SKIP_LIST_MAP_RCU_H