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
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 using exempt_ptr = cds::urcu::exempt_ptr< gc, node_type, value_type, typename maker::intrusive_type_traits::disposer >;
145 struct raw_ptr_converter
147 value_type * operator()( node_type * p ) const
149 return p ? &p->m_Value : nullptr;
152 value_type& operator()( node_type& n ) const
157 value_type const& operator()( node_type const& n ) const
165 /// Result of \p get(), \p get_with() functions - pointer to the node found
166 typedef cds::urcu::raw_ptr_adaptor< value_type, typename base_class::raw_ptr, raw_ptr_converter > raw_ptr;
170 unsigned int random_level()
172 return base_class::random_level();
182 /// Destructor destroys the set object
188 typedef skip_list::details::iterator< typename base_class::iterator > iterator;
190 /// Const iterator type
191 typedef skip_list::details::iterator< typename base_class::const_iterator > const_iterator;
193 /// Returns a forward iterator addressing the first element in a map
196 return iterator( base_class::begin() );
199 /// Returns a forward const iterator addressing the first element in a map
200 const_iterator begin() const
204 /// Returns a forward const iterator addressing the first element in a map
205 const_iterator cbegin() const
207 return const_iterator( base_class::cbegin() );
210 /// Returns a forward iterator that addresses the location succeeding the last element in a map.
213 return iterator( base_class::end() );
216 /// Returns a forward const iterator that addresses the location succeeding the last element in a map.
217 const_iterator end() const
221 /// Returns a forward const iterator that addresses the location succeeding the last element in a map.
222 const_iterator cend() const
224 return const_iterator( base_class::cend() );
228 /// Inserts new node with key and default value
230 The function creates a node with \p key and default value, and then inserts the node created into the map.
233 - The \p key_type should be constructible from a value of type \p K.
234 In trivial case, \p K is equal to \p key_type.
235 - The \p mapped_type should be default-constructible.
237 RCU \p synchronize method can be called. RCU should not be locked.
239 Returns \p true if inserting successful, \p false otherwise.
241 template <typename K>
242 bool insert( K const& key )
244 return insert_with( key, [](value_type&){} );
249 The function creates a node with copy of \p val value
250 and then inserts the node created into the map.
253 - The \p key_type should be constructible from \p key of type \p K.
254 - The \p value_type should be constructible from \p val of type \p V.
256 RCU \p synchronize method can be called. RCU should not be locked.
258 Returns \p true if \p val is inserted into the set, \p false otherwise.
260 template <typename K, typename V>
261 bool insert( K const& key, V const& val )
263 scoped_node_ptr pNode( node_allocator().New( random_level(), key, val ));
264 if ( base_class::insert( *pNode ))
272 /// Inserts new node and initialize it by a functor
274 This function inserts new node with key \p key and if inserting is successful then it calls
275 \p func functor with signature
278 void operator()( value_type& item );
282 The argument \p item of user-defined functor \p func is the reference
283 to the map's item inserted:
284 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
285 - <tt>item.second</tt> is a reference to item's value that may be changed.
287 The function allows to split creating of new item into three part:
288 - create item from \p key;
289 - insert new item into the map;
290 - if inserting is successful, initialize the value of item by calling \p func functor
292 This can be useful if complete initialization of object of \p value_type is heavyweight and
293 it is preferable that the initialization should be completed only if inserting is successful.
295 RCU \p synchronize method can be called. RCU should not be locked.
297 template <typename K, typename Func>
298 bool insert_with( const K& key, Func func )
300 scoped_node_ptr pNode( node_allocator().New( random_level(), key ));
301 if ( base_class::insert( *pNode, [&func]( node_type& item ) { func( item.m_Value ); } )) {
308 /// For key \p key inserts data of type \p value_type created in-place from \p args
310 Returns \p true if inserting successful, \p false otherwise.
312 RCU \p synchronize() method can be called. RCU should not be locked.
314 template <typename K, typename... Args>
315 bool emplace( K&& key, Args&&... args )
317 scoped_node_ptr pNode( node_allocator().New( random_level(), std::forward<K>(key), std::forward<Args>(args)... ));
318 if ( base_class::insert( *pNode )) {
325 /// Updates data by \p key
327 The operation performs inserting or changing data with lock-free manner.
329 If the \p key not found in the map, then the new item created from \p key
330 is inserted into the map iff \p bInsert is \p true.
331 Otherwise, if \p key found, the functor \p func is called with item found.
332 The functor \p Func interface is:
335 void operator()( bool bNew, value_type& item );
339 - \p bNew - \p true if the item has been inserted, \p false otherwise
340 - \p item - item of the map
342 The functor may change any fields of \p item.second.
344 RCU \p synchronize() method can be called. RCU should not be locked.
346 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
347 \p second is \p true if new item has been added or \p false if the item with \p key
350 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
352 template <typename K, typename Func>
353 std::pair<bool, bool> update( K const& key, Func func, bool bInsert = true )
355 scoped_node_ptr pNode( node_allocator().New( random_level(), key ));
356 std::pair<bool, bool> res = base_class::update( *pNode,
357 [&func](bool bNew, node_type& item, node_type const& ){ func( bNew, item.m_Value );},
360 if ( res.first && res.second )
365 // Deprecated, use update()
366 template <typename K, typename Func>
367 std::pair<bool, bool> ensure( K const& key, Func func )
369 return update( key, func, true );
373 /// Delete \p key from the map
374 /**\anchor cds_nonintrusive_SkipListMap_rcu_erase_val
376 RCU \p synchronize method can be called. RCU should not be locked.
378 Return \p true if \p key is found and deleted, \p false otherwise
380 template <typename K>
381 bool erase( K const& key )
383 return base_class::erase(key);
386 /// Deletes the item from the map using \p pred predicate for searching
388 The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_erase_val "erase(K const&)"
389 but \p pred is used for key comparing.
390 \p Less functor has the interface like \p std::less.
391 \p Less must imply the same element order as the comparator used for building the map.
393 template <typename K, typename Less>
394 bool erase_with( K const& key, Less pred )
397 return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >());
400 /// Delete \p key from the map
401 /** \anchor cds_nonintrusive_SkipListMap_rcu_erase_func
403 The function searches an item with key \p key, calls \p f functor
404 and deletes the item. If \p key is not found, the functor is not called.
406 The functor \p Func interface:
409 void operator()(value_type& item) { ... }
413 RCU \p synchronize method can be called. RCU should not be locked.
415 Return \p true if key is found and deleted, \p false otherwise
417 template <typename K, typename Func>
418 bool erase( K const& key, Func f )
420 return base_class::erase( key, [&f]( node_type& node) { f( node.m_Value ); } );
423 /// Deletes the item from the map using \p pred predicate for searching
425 The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_erase_func "erase(K const&, Func)"
426 but \p pred is used for key comparing.
427 \p Less functor has the interface like \p std::less.
428 \p Less must imply the same element order as the comparator used for building the map.
430 template <typename K, typename Less, typename Func>
431 bool erase_with( K const& key, Less pred, Func f )
434 return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >(),
435 [&f]( node_type& node) { f( node.m_Value ); } );
438 /// Extracts the item from the map with specified \p key
439 /** \anchor cds_nonintrusive_SkipListMap_rcu_extract
440 The function searches an item with key equal to \p key in the map,
441 unlinks it from the set, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
442 If the item is not found the function returns an empty \p exempt_ptr
444 Note the compare functor from \p Traits class' template argument
445 should accept a parameter of type \p K that can be not the same as \p key_type.
447 RCU \p synchronize() method can be called. RCU should NOT be locked.
449 The function does not free the item found.
450 The item will be implicitly freed when the returned object is destroyed or when
451 its \p release() member function is called.
453 template <typename K>
454 exempt_ptr extract( K const& key )
456 return exempt_ptr( base_class::do_extract( key ));
459 /// Extracts the item from the map with comparing functor \p pred
461 The function is an analog of \p extract(K const&) but \p pred predicate is used for key comparing.
462 \p Less has the semantics like \p std::less.
463 \p pred must imply the same element order as the comparator used for building the map.
465 template <typename K, typename Less>
466 exempt_ptr extract_with( K const& key, Less pred )
469 return exempt_ptr( base_class::do_extract_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >()));
472 /// Extracts an item with minimal key from the map
474 The function searches an item with minimal key, unlinks it,
475 and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item.
476 If the skip-list is empty the function returns an empty \p exempt_ptr.
478 RCU \p synchronize method can be called. RCU should NOT be locked.
480 The function does not free the item found.
481 The item will be implicitly freed when the returned object is destroyed or when
482 its \p release() member function is called.
484 exempt_ptr extract_min()
486 return exempt_ptr( base_class::do_extract_min());
489 /// Extracts an item with maximal key from the map
491 The function searches an item with maximal key, unlinks it from the set,
492 and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item.
493 If the skip-list is empty the function returns an empty \p exempt_ptr.
495 RCU \p synchronize method can be called. RCU should NOT be locked.
497 The function does not free the item found.
498 The item will be implicitly freed when the returned object is destroyed or when
499 its \p release() member function is called.
501 exempt_ptr extract_max()
503 return exempt_ptr( base_class::do_extract_max());
506 /// Find the key \p key
507 /** \anchor cds_nonintrusive_SkipListMap_rcu_find_cfunc
509 The function searches the item with key equal to \p key and calls the functor \p f for item found.
510 The interface of \p Func functor is:
513 void operator()( value_type& item );
516 where \p item is the item found.
518 The functor may change \p item.second.
520 The function applies RCU lock internally.
522 The function returns \p true if \p key is found, \p false otherwise.
524 template <typename K, typename Func>
525 bool find( K const& key, Func f )
527 return base_class::find( key, [&f](node_type& item, K const& ) { f( item.m_Value );});
530 /// Finds the key \p val using \p pred predicate for searching
532 The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_find_cfunc "find(K const&, Func)"
533 but \p pred is used for key comparing.
534 \p Less functor has the interface like \p std::less.
535 \p Less must imply the same element order as the comparator used for building the map.
537 template <typename K, typename Less, typename Func>
538 bool find_with( K const& key, Less pred, Func f )
541 return base_class::find_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >(),
542 [&f](node_type& item, K const& ) { f( item.m_Value );});
545 /// Checks whether the map contains \p key
547 The function searches the item with key equal to \p key
548 and returns \p true if it is found, and \p false otherwise.
550 The function applies RCU lock internally.
552 template <typename K>
553 bool contains( K const& key )
555 return base_class::contains( key );
558 // Deprecated, use contains()
559 template <typename K>
560 bool find( K const& key )
562 return contains( key );
566 /// Checks whether the map contains \p key using \p pred predicate for searching
568 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
569 \p Less functor has the interface like \p std::less.
570 \p Less must imply the same element order as the comparator used for building the set.
572 template <typename K, typename Less>
573 bool contains( K const& key, Less pred )
576 return base_class::contains( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >() );
579 // Deprecated, use contains()
580 template <typename K, typename Less>
581 bool find_with( K const& key, Less pred )
583 return contains( key, pred );
587 /// Finds the key \p key and return the item found
588 /** \anchor cds_nonintrusive_SkipListMap_rcu_get
589 The function searches the item with key equal to \p key and returns a \p raw_ptr object pointing to an item found.
590 If \p key is not found it returns empty \p raw_ptr.
592 Note the compare functor in \p Traits class' template argument
593 should accept a parameter of type \p K that can be not the same as \p key_type.
595 RCU should be locked before call of this function.
596 Returned item is valid only while RCU is locked:
598 typedef cds::container::SkipListMap< cds::urcu::gc< cds::urcu::general_buffered<> >, int, foo, my_traits > skip_list;
601 typename skip_list::raw_ptr pVal;
604 skip_list::rcu_lock lock;
606 pVal = theList.get( 5 );
612 // You can manually release pVal after RCU-locked section
616 template <typename K>
617 raw_ptr get( K const& key )
619 return raw_ptr( base_class::get( key ));
622 /// Finds the key \p key and return the item found
624 The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_get "get(K const&)"
625 but \p pred is used for comparing the keys.
627 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
629 \p pred must imply the same element order as the comparator used for building the map.
631 template <typename K, typename Less>
632 raw_ptr get_with( K const& key, Less pred )
635 return raw_ptr( base_class::get_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >() ));
638 /// Clears the map (not atomic)
644 /// Checks if the map is empty
646 Emptiness is checked by item counting: if item count is zero then the map is empty.
650 return base_class::empty();
653 /// Returns item count in the map
656 return base_class::size();
659 /// Returns const reference to internal statistics
660 stat const& statistics() const
662 return base_class::statistics();
665 }} // namespace cds::container
667 #endif // #ifndef CDSLIB_CONTAINER_SKIP_LIST_MAP_RCU_H