3 #ifndef __CDS_CONTAINER_IMPL_SKIP_LIST_MAP_H
4 #define __CDS_CONTAINER_IMPL_SKIP_LIST_MAP_H
6 #include <cds/gc/guarded_ptr.h>
7 #include <cds/container/details/guarded_ptr_cast.h>
9 namespace cds { namespace container {
11 /// Lock-free skip-list map
12 /** @ingroup cds_nonintrusive_map
13 \anchor cds_nonintrusive_SkipListMap_hp
15 The implementation of well-known probabilistic data structure called skip-list
16 invented by W.Pugh in his papers:
17 - [1989] W.Pugh Skip Lists: A Probabilistic Alternative to Balanced Trees
18 - [1990] W.Pugh A Skip List Cookbook
20 A skip-list is a probabilistic data structure that provides expected logarithmic
21 time search without the need of rebalance. The skip-list is a collection of sorted
22 linked list. Nodes are ordered by key. Each node is linked into a subset of the lists.
23 Each list has a level, ranging from 0 to 32. The bottom-level list contains
24 all the nodes, and each higher-level list is a sublist of the lower-level lists.
25 Each node is created with a random top level (with a random height), and belongs
26 to all lists up to that level. The probability that a node has the height 1 is 1/2.
27 The probability that a node has the height N is 1/2 ** N (more precisely,
28 the distribution depends on an random generator provided, but our generators
31 The lock-free variant of skip-list is implemented according to book
32 - [2008] M.Herlihy, N.Shavit "The Art of Multiprocessor Programming",
33 chapter 14.4 "A Lock-Free Concurrent Skiplist"
36 - \p GC - Garbage collector used.
37 - \p K - type of a key to be stored in the list.
38 - \p T - type of a value to be stored in the list.
39 - \p Traits - map traits, default is \p skip_list::traits
40 It is possible to declare option-based list with \p cds::container::skip_list::make_traits metafunction
41 istead of \p Traits template argument.
43 Like STL map class, \p %SkipListMap stores the key-value pair as <tt>std:pair< K const, T></tt>.
45 @warning The skip-list requires up to 67 hazard pointers that may be critical for some GCs for which
46 the guard count is limited (like \p gc::HP). Those GCs should be explicitly initialized with
47 hazard pointer enough: \code cds::gc::HP myhp( 67 ) \endcode. Otherwise an run-time exception may be raised
48 when you try to create skip-list object.
50 @note There are several specializations of \p %SkipListMap for each \p GC. You should include:
51 - <tt><cds/container/skip_list_map_hp.h></tt> for \p gc::HP garbage collector
52 - <tt><cds/container/skip_list_map_dhp.h></tt> for \p gc::DHP garbage collector
53 - <tt><cds/container/skip_list_map_rcu.h></tt> for \ref cds_nonintrusive_SkipListMap_rcu "RCU type"
54 - <tt><cds/container/skip_list_map_nogc.h></tt> for \ref cds_nonintrusive_SkipListMap_nogc "non-deletable SkipListMap"
58 The class supports a forward iterator (\ref iterator and \ref const_iterator).
59 The iteration is ordered.
60 The iterator object is thread-safe: the element pointed by the iterator object is guarded,
61 so, the element cannot be reclaimed while the iterator object is alive.
62 However, passing an iterator object between threads is dangerous.
64 \warning Due to concurrent nature of skip-list map it is not guarantee that you can iterate
65 all elements in the map: any concurrent deletion can exclude the element
66 pointed by the iterator from the map, and your iteration can be terminated
67 before end of the map. Therefore, such iteration is more suitable for debugging purpose only
69 Remember, each iterator object requires 2 additional hazard pointers, that may be
70 a limited resource for \p GC like \p gc::HP (for gc::DHP the count of
73 The iterator class supports the following minimalistic interface:
80 iterator( iterator const& s);
82 value_type * operator ->() const;
83 value_type& operator *() const;
86 iterator& operator ++();
89 iterator& operator = (const iterator& src);
91 bool operator ==(iterator const& i ) const;
92 bool operator !=(iterator const& i ) const;
95 Note, the iterator object returned by \ref end, \ cend member functions points to \p nullptr and should not be dereferenced.
102 #ifdef CDS_DOXYGEN_INVOKED
103 typename Traits = skip_list::traits
109 #ifdef CDS_DOXYGEN_INVOKED
110 protected intrusive::SkipListSet< GC, std::pair<Key const, T>, Traits >
112 protected details::make_skip_list_map< GC, Key, T, Traits >::type
116 typedef details::make_skip_list_map< GC, Key, T, Traits > maker;
117 typedef typename maker::type base_class;
120 typedef GC gc; ///< Garbage collector
121 typedef Key key_type; ///< Key type
122 typedef T mapped_type; ///< Mapped type
123 typedef Traits traits; ///< Map traits
124 # ifdef CDS_DOXYGEN_INVOKED
125 typedef std::pair< K const, T> value_type; ///< Key-value pair to be stored in the map
127 typedef typename maker::value_type value_type;
130 typedef typename base_class::back_off back_off; ///< Back-off strategy
131 typedef typename traits::allocator allocator_type; ///< Allocator type used for allocate/deallocate the skip-list nodes
132 typedef typename base_class::item_counter item_counter; ///< Item counting policy used
133 typedef typename maker::key_comparator key_comparator; ///< key comparison functor
134 typedef typename base_class::memory_model memory_model; ///< Memory ordering, see \p cds::opt::memory_model
135 typedef typename traits::random_level_generator random_level_generator ; ///< random level generator
136 typedef typename traits::stat stat; ///< internal statistics type
140 typedef typename maker::node_type node_type;
141 typedef typename maker::node_allocator node_allocator;
143 typedef std::unique_ptr< node_type, typename maker::node_deallocator > scoped_node_ptr;
148 typedef cds::gc::guarded_ptr< gc, node_type, value_type, details::guarded_ptr_cast_set<node_type, value_type> > guarded_ptr;
152 unsigned int random_level()
154 return base_class::random_level();
164 /// Destructor destroys the set object
170 typedef skip_list::details::iterator< typename base_class::iterator > iterator;
172 /// Const iterator type
173 typedef skip_list::details::iterator< typename base_class::const_iterator > const_iterator;
175 /// Returns a forward iterator addressing the first element in a map
178 return iterator( base_class::begin() );
181 /// Returns a forward const iterator addressing the first element in a map
182 const_iterator begin() const
186 /// Returns a forward const iterator addressing the first element in a map
187 const_iterator cbegin() const
189 return const_iterator( base_class::cbegin() );
192 /// Returns a forward iterator that addresses the location succeeding the last element in a map.
195 return iterator( base_class::end() );
198 /// Returns a forward const iterator that addresses the location succeeding the last element in a map.
199 const_iterator end() const
203 /// Returns a forward const iterator that addresses the location succeeding the last element in a map.
204 const_iterator cend() const
206 return const_iterator( base_class::cend() );
210 /// Inserts new node with key and default value
212 The function creates a node with \p key and default value, and then inserts the node created into the map.
215 - The \p key_type should be constructible from a value of type \p K.
216 In trivial case, \p K is equal to \p key_type.
217 - The \p mapped_type should be default-constructible.
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 Returns \p true if \p val is inserted into the set, \p false otherwise.
238 template <typename K, typename V>
239 bool insert( K const& key, V const& val )
241 return insert_key( key, [&val](value_type& item) { item.second = val ; } );
244 /// Inserts new node and initialize it by a functor
246 This function inserts new node with key \p key and if inserting is successful then it calls
247 \p func functor with signature
250 void operator()( value_type& item );
254 The argument \p item of user-defined functor \p func is the reference
255 to the map's item inserted:
256 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
257 - <tt>item.second</tt> is a reference to item's value that may be changed.
259 \p key_type should be constructible from value of type \p K.
261 The function allows to split creating of new item into two part:
262 - create item from \p key;
263 - insert new item into the map;
264 - if inserting is successful, initialize the value of item by calling \p func functor
266 This can be useful if complete initialization of object of \p value_type is heavyweight and
267 it is preferable that the initialization should be completed only if inserting is successful.
269 template <typename K, typename Func>
270 bool insert_key( const K& key, Func func )
272 scoped_node_ptr pNode( node_allocator().New( random_level(), key ));
273 if ( base_class::insert( *pNode, [&func]( node_type& item ) { func( item.m_Value ); } )) {
280 /// For key \p key inserts data of type \p value_type created in-place from <tt>std::forward<Args>(args)...</tt>
282 Returns \p true if inserting successful, \p false otherwise.
284 template <typename K, typename... Args>
285 bool emplace( K&& key, Args&&... args )
287 scoped_node_ptr pNode( node_allocator().New( random_level(), std::forward<K>(key), std::forward<Args>(args)... ));
288 if ( base_class::insert( *pNode )) {
295 /// Ensures that the \p key exists in the map
297 The operation performs inserting or changing data with lock-free manner.
299 If the \p key not found in the map, then the new item created from \p key
300 is inserted into the map (note that in this case the \ref key_type should be
301 constructible from type \p K).
302 Otherwise, the functor \p func is called with item found.
303 The functor \p Func may be a function with signature:
305 void func( bool bNew, value_type& item );
310 void operator()( bool bNew, value_type& item );
315 - \p bNew - \p true if the item has been inserted, \p false otherwise
316 - \p item - item of the list
318 The functor may change any fields of the \p item.second that is \ref value_type.
320 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
321 \p second is true if new item has been added or \p false if the item with \p key
322 already is in the list.
324 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
326 template <typename K, typename Func>
327 std::pair<bool, bool> ensure( K const& key, Func func )
329 scoped_node_ptr pNode( node_allocator().New( random_level(), key ));
330 std::pair<bool, bool> res = base_class::ensure( *pNode,
331 [&func](bool bNew, node_type& item, node_type const& ){ func( bNew, item.m_Value ); }
333 if ( res.first && res.second )
338 /// Delete \p key from the map
339 /** \anchor cds_nonintrusive_SkipListMap_erase_val
341 Return \p true if \p key is found and deleted, \p false otherwise
343 template <typename K>
344 bool erase( K const& key )
346 return base_class::erase(key);
349 /// Deletes the item from the map using \p pred predicate for searching
351 The function is an analog of \ref cds_nonintrusive_SkipListMap_erase_val "erase(K const&)"
352 but \p pred is used for key comparing.
353 \p Less functor has the interface like \p std::less.
354 \p Less must imply the same element order as the comparator used for building the map.
356 template <typename K, typename Less>
357 bool erase_with( K const& key, Less pred )
360 return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >());
363 /// Delete \p key from the map
364 /** \anchor cds_nonintrusive_SkipListMap_erase_func
366 The function searches an item with key \p key, calls \p f functor
367 and deletes the item. If \p key is not found, the functor is not called.
369 The functor \p Func interface:
372 void operator()(value_type& item) { ... }
376 Return \p true if key is found and deleted, \p false otherwise
378 template <typename K, typename Func>
379 bool erase( K const& key, Func f )
381 return base_class::erase( key, [&f]( node_type& node) { f( node.m_Value ); } );
384 /// Deletes the item from the map using \p pred predicate for searching
386 The function is an analog of \ref cds_nonintrusive_SkipListMap_erase_func "erase(K const&, Func)"
387 but \p pred is used for key comparing.
388 \p Less functor has the interface like \p std::less.
389 \p Less must imply the same element order as the comparator used for building the map.
391 template <typename K, typename Less, typename Func>
392 bool erase_with( K const& key, Less pred, Func f )
395 return base_class::erase_with( key,
396 cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >(),
397 [&f]( node_type& node) { f( node.m_Value ); } );
400 /// Extracts the item from the map with specified \p key
401 /** \anchor cds_nonintrusive_SkipListMap_hp_extract
402 The function searches an item with key equal to \p key in the map,
403 unlinks it from the map, and returns it in \p ptr parameter.
404 If the item with key equal to \p key is not found the function returns \p false.
406 Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type.
408 The item extracted is freed automatically by garbage collector \p GC
409 when returned \ref guarded_ptr object will be destroyed or released.
410 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
414 typedef cds::container::SkipListMap< cds::gc::HP, int, foo, my_traits > skip_list;
418 skip_list::guarded_ptr gp;
419 if ( theList.extract( gp, 5 ) ) {
423 // Destructor of gp releases internal HP guard and frees the pointer
427 template <typename K>
428 bool extract( guarded_ptr& ptr, K const& key )
430 return base_class::extract_( ptr.guard(), key, typename base_class::key_comparator() );
433 /// Extracts the item from the map with comparing functor \p pred
435 The function is an analog of \ref cds_nonintrusive_SkipListMap_hp_extract "extract(K const&)"
436 but \p pred predicate is used for key comparing.
438 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
440 \p pred must imply the same element order as the comparator used for building the map.
442 template <typename K, typename Less>
443 bool extract_with( guarded_ptr& ptr, K const& key, Less pred )
446 typedef cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor > wrapped_less;
447 return base_class::extract_( ptr.guard(), key, cds::opt::details::make_comparator_from_less<wrapped_less>() );
450 /// Extracts an item with minimal key from the map
452 The function searches an item with minimal key, unlinks it, and returns the item found in \p ptr parameter.
453 If the skip-list is empty the function returns \p false.
455 The item extracted is freed automatically by garbage collector \p GC
456 when returned \ref guarded_ptr object will be destroyed or released.
457 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
461 typedef cds::continer::SkipListMap< cds::gc::HP, int, foo, my_traits > skip_list;
465 skip_list::guarded_ptr gp;
466 if ( theList.extract_min( gp )) {
470 // Destructor of gp releases internal HP guard and then frees the pointer
474 bool extract_min( guarded_ptr& ptr)
476 return base_class::extract_min_( ptr.guard() );
479 /// Extracts an item with maximal key from the map
481 The function searches an item with maximal key, unlinks it, and returns the pointer to item found in \p ptr parameter.
482 If the skip-list is empty the function returns empty \p guarded_ptr.
484 The item found is freed by garbage collector \p GC automatically
485 when returned \ref guarded_ptr object will be destroyed or released.
486 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
490 typedef cds::container::SkipListMap< cds::gc::HP, int, foo, my_traits > skip_list;
494 skip_list::guarded_ptr gp;
495 if ( theList.extract_max( gp )) {
499 // Destructor of gp releases internal HP guard and then frees the pointer
503 bool extract_max( guarded_ptr& dest )
505 return base_class::extract_max_( dest.guard() );
508 /// Find the key \p key
509 /** \anchor cds_nonintrusive_SkipListMap_find_cfunc
511 The function searches the item with key equal to \p key and calls the functor \p f for item found.
512 The interface of \p Func functor is:
515 void operator()( value_type& item );
518 where \p item is the item found.
520 The functor may change \p item.second.
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_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,
542 cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >(),
543 [&f](node_type& item, K const& ) { f( item.m_Value );});
546 /// Find the key \p key
547 /** \anchor cds_nonintrusive_SkipListMap_find_val
549 The function searches the item with key equal to \p key
550 and returns \p true if it is found, and \p false otherwise.
552 template <typename K>
553 bool find( K const& key )
555 return base_class::find( key );
558 /// Finds the key \p val using \p pred predicate for searching
560 The function is an analog of \ref cds_nonintrusive_SkipListMap_find_val "find(K const&)"
561 but \p pred is used for key comparing.
562 \p Less functor has the interface like \p std::less.
563 \p Less must imply the same element order as the comparator used for building the map.
565 template <typename K, typename Less>
566 bool find_with( K const& key, Less pred )
569 return base_class::find_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >() );
572 /// Finds the key \p key and return the item found
573 /** \anchor cds_nonintrusive_SkipListMap_hp_get
574 The function searches the item with key equal to \p key
575 and assigns the item found to guarded pointer \p ptr.
576 The function returns \p true if \p key is found, and \p false otherwise.
577 If \p key is not found the \p ptr parameter is not changed.
579 It is safe when a concurrent thread erases the item returned in \p ptr guarded pointer.
580 In this case the item will be freed later by garbage collector \p GC automatically
581 when \p guarded_ptr object will be destroyed or released.
582 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
586 typedef cds::container::SkipListMap< cds::gc::HP, int, foo, my_traits > skip_list;
590 skip_list::guarded_ptr gp;
591 if ( theList.get( gp, 5 ) ) {
595 // Destructor of guarded_ptr releases internal HP guard
599 Note the compare functor specified for class \p Traits template parameter
600 should accept a parameter of type \p K that can be not the same as \p value_type.
602 template <typename K>
603 bool get( guarded_ptr& ptr, K const& key )
605 return base_class::get_with_( ptr.guard(), key, typename base_class::key_comparator() );
608 /// Finds the key \p key and return the item found
610 The function is an analog of \ref cds_nonintrusive_SkipListMap_hp_get "get( guarded_ptr& ptr, K const&)"
611 but \p pred is used for comparing the keys.
613 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
615 \p pred must imply the same element order as the comparator used for building the map.
617 template <typename K, typename Less>
618 bool get_with( guarded_ptr& ptr, K const& key, Less pred )
621 typedef cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor > wrapped_less;
622 return base_class::get_with_( ptr.guard(), key, cds::opt::details::make_comparator_from_less< wrapped_less >());
631 /// Checks if the map is empty
634 return base_class::empty();
637 /// Returns item count in the map
640 return base_class::size();
643 /// Returns const reference to internal statistics
644 stat const& statistics() const
646 return base_class::statistics();
649 }} // namespace cds::container
651 #endif // #ifndef __CDS_CONTAINER_IMPL_SKIP_LIST_MAP_H