3 #ifndef __CDS_CONTAINER_SKIP_LIST_MAP_IMPL_H
4 #define __CDS_CONTAINER_SKIP_LIST_MAP_IMPL_H
6 #include <cds/details/functor_wrapper.h>
7 #include <cds/gc/guarded_ptr.h>
8 #include <cds/container/details/guarded_ptr_cast.h>
10 namespace cds { namespace container {
12 /// Lock-free skip-list map
13 /** @ingroup cds_nonintrusive_map
14 \anchor cds_nonintrusive_SkipListMap_hp
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 GC - Garbage collector used.
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)
58 Like STL map class, %SkipListMap stores its key-value pair as <tt>std:pair< K const, T></tt>.
60 \warning The skip-list requires up to 67 hazard pointers that may be critical for some GCs for which
61 the guard count is limited (like as gc::HP, gc::HRC). Those GCs should be explicitly initialized with
62 hazard pointer enough: \code cds::gc::HP myhp( 67 ) \endcode. Otherwise an run-time exception may be raised
63 when you try to create skip-list object.
65 \note There are several specializations of \p %SkipListMap for each \p GC. You should include:
66 - <tt><cds/container/skip_list_map_hp.h></tt> for gc::HP garbage collector
67 - <tt><cds/container/skip_list_map_hrc.h></tt> for gc::HRC garbage collector
68 - <tt><cds/container/skip_list_map_ptb.h></tt> for gc::PTB garbage collector
69 - <tt><cds/container/skip_list_map_rcu.h></tt> for \ref cds_nonintrusive_SkipListMap_rcu "RCU type"
70 - <tt><cds/container/skip_list_map_nogc.h></tt> for \ref cds_nonintrusive_SkipListMap_nogc "non-deletable SkipListMap"
74 The class supports a forward iterator (\ref iterator and \ref const_iterator).
75 The iteration is ordered.
76 The iterator object is thread-safe: the element pointed by the iterator object is guarded,
77 so, the element cannot be reclaimed while the iterator object is alive.
78 However, passing an iterator object between threads is dangerous.
80 \warning Due to concurrent nature of skip-list map it is not guarantee that you can iterate
81 all elements in the map: any concurrent deletion can exclude the element
82 pointed by the iterator from the map, and your iteration can be terminated
83 before end of the map. Therefore, such iteration is more suitable for debugging purpose only
85 Remember, each iterator object requires 2 additional hazard pointers, that may be
86 a limited resource for \p GC like as gc::HP and gc::HRC (however, for gc::PTB the count of
89 The iterator class supports the following minimalistic interface:
96 iterator( iterator const& s);
98 value_type * operator ->() const;
99 value_type& operator *() const;
102 iterator& operator ++();
105 iterator& operator = (const iterator& src);
107 bool operator ==(iterator const& i ) const;
108 bool operator !=(iterator const& i ) const;
111 Note, the iterator object returned by \ref end, \ cend member functions points to \p nullptr and should not be dereferenced.
118 #ifdef CDS_DOXYGEN_INVOKED
119 typename Traits = skip_list::type_traits
125 #ifdef CDS_DOXYGEN_INVOKED
126 protected intrusive::SkipListSet< GC, std::pair<Key const, T>, Traits >
128 protected details::make_skip_list_map< GC, Key, T, Traits >::type
132 typedef details::make_skip_list_map< GC, Key, T, Traits > maker;
133 typedef typename maker::type base_class;
136 typedef typename base_class::gc gc ; ///< Garbage collector used
137 typedef Key key_type ; ///< Key type
138 typedef T mapped_type ; ///< Mapped type
139 # ifdef CDS_DOXYGEN_INVOKED
140 typedef std::pair< K const, T> value_type ; ///< Value type stored in the map
142 typedef typename maker::value_type value_type;
144 typedef Traits options ; ///< Options specified
146 typedef typename base_class::back_off back_off ; ///< Back-off strategy used
147 typedef typename options::allocator allocator_type ; ///< Allocator type used for allocate/deallocate the skip-list nodes
148 typedef typename base_class::item_counter item_counter ; ///< Item counting policy used
149 typedef typename maker::key_comparator key_comparator ; ///< key comparison functor
150 typedef typename base_class::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
151 typedef typename options::random_level_generator random_level_generator ; ///< random level generator
152 typedef typename options::stat stat ; ///< internal statistics type
156 typedef typename maker::node_type node_type;
157 typedef typename maker::node_allocator node_allocator;
159 typedef std::unique_ptr< node_type, typename maker::node_deallocator > scoped_node_ptr;
165 typedef cds::gc::guarded_ptr< gc, node_type, value_type, details::guarded_ptr_cast_set<node_type, value_type> > guarded_ptr;
169 unsigned int random_level()
171 return base_class::random_level();
177 # ifndef CDS_CXX11_LAMBDA_SUPPORT
178 struct empty_insert_functor
180 void operator()( value_type& ) const
184 template <typename Q>
185 class insert_value_functor
189 insert_value_functor( Q const & v)
193 void operator()( value_type& item )
199 template <typename Func>
200 class insert_key_wrapper: protected cds::details::functor_wrapper<Func>
202 typedef cds::details::functor_wrapper<Func> base_class;
204 insert_key_wrapper( Func f ): base_class(f) {}
206 void operator()( node_type& item )
208 base_class::get()( item.m_Value );
212 template <typename Func>
213 class ensure_wrapper: protected cds::details::functor_wrapper<Func>
215 typedef cds::details::functor_wrapper<Func> base_class;
217 ensure_wrapper( Func f) : base_class(f) {}
219 void operator()( bool bNew, node_type& item, node_type const& )
221 base_class::get()( bNew, item.m_Value );
225 template <typename Func>
230 erase_functor( Func f )
234 void operator()( node_type& node )
236 cds::unref(m_func)( node.m_Value );
240 template <typename Func>
241 class find_wrapper: protected cds::details::functor_wrapper<Func>
243 typedef cds::details::functor_wrapper<Func> base_class;
245 find_wrapper( Func f )
249 template <typename Q>
250 void operator()( node_type& item, Q& val )
252 base_class::get()( item.m_Value, val );
255 # endif // #ifndef CDS_CXX11_LAMBDA_SUPPORT
264 /// Destructor destroys the set object
270 typedef skip_list::details::iterator< typename base_class::iterator > iterator;
272 /// Const iterator type
273 typedef skip_list::details::iterator< typename base_class::const_iterator > const_iterator;
275 /// Returns a forward iterator addressing the first element in a map
278 return iterator( base_class::begin() );
281 /// Returns a forward const iterator addressing the first element in a map
283 const_iterator begin() const
287 const_iterator cbegin()
289 return const_iterator( base_class::cbegin() );
293 /// Returns a forward iterator that addresses the location succeeding the last element in a map.
296 return iterator( base_class::end() );
299 /// Returns a forward const iterator that addresses the location succeeding the last element in a map.
301 const_iterator end() const
305 const_iterator cend()
307 return const_iterator( base_class::cend() );
312 /// Inserts new node with key and default value
314 The function creates a node with \p key and default value, and then inserts the node created into the map.
317 - The \ref key_type should be constructible from a value of type \p K.
318 In trivial case, \p K is equal to \ref key_type.
319 - The \ref mapped_type should be default-constructible.
321 Returns \p true if inserting successful, \p false otherwise.
323 template <typename K>
324 bool insert( K const& key )
326 # ifdef CDS_CXX11_LAMBDA_SUPPORT
327 return insert_key( key, [](value_type&){} );
329 return insert_key( key, empty_insert_functor() );
335 The function creates a node with copy of \p val value
336 and then inserts the node created into the map.
339 - The \ref key_type should be constructible from \p key of type \p K.
340 - The \ref value_type should be constructible from \p val of type \p V.
342 Returns \p true if \p val is inserted into the set, \p false otherwise.
344 template <typename K, typename V>
345 bool insert( K const& key, V const& val )
347 # ifdef CDS_CXX11_LAMBDA_SUPPORT
348 return insert_key( key, [&val](value_type& item) { item.second = val ; } );
350 insert_value_functor<V> f(val);
351 return insert_key( key, cds::ref(f) );
355 /// Inserts new node and initialize it by a functor
357 This function inserts new node with key \p key and if inserting is successful then it calls
358 \p func functor with signature
361 void operator()( value_type& item );
365 The argument \p item of user-defined functor \p func is the reference
366 to the map's item inserted:
367 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
368 - <tt>item.second</tt> is a reference to item's value that may be changed.
370 The user-defined functor can be passed by reference using <tt>boost::ref</tt>
371 and it is called only if inserting is successful.
373 The key_type should be constructible from value of type \p K.
375 The function allows to split creating of new item into two part:
376 - create item from \p key;
377 - insert new item into the map;
378 - if inserting is successful, initialize the value of item by calling \p func functor
380 This can be useful if complete initialization of object of \p value_type is heavyweight and
381 it is preferable that the initialization should be completed only if inserting is successful.
383 template <typename K, typename Func>
384 bool insert_key( const K& key, Func func )
386 scoped_node_ptr pNode( node_allocator().New( random_level(), key ));
387 # ifdef CDS_CXX11_LAMBDA_SUPPORT
388 if ( base_class::insert( *pNode, [&func]( node_type& item ) { cds::unref(func)( item.m_Value ); } ))
390 insert_key_wrapper<Func> wrapper(func);
391 if ( base_class::insert( *pNode, cds::ref(wrapper) ))
400 # ifdef CDS_EMPLACE_SUPPORT
401 /// For key \p key inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
403 Returns \p true if inserting successful, \p false otherwise.
405 @note This function is available only for compiler that supports
406 variadic template and move semantics
408 template <typename K, typename... Args>
409 bool emplace( K&& key, Args&&... args )
411 scoped_node_ptr pNode( node_allocator().New( random_level(), std::forward<K>(key), std::forward<Args>(args)... ));
412 if ( base_class::insert( *pNode )) {
421 /// Ensures that the \p key exists in the map
423 The operation performs inserting or changing data with lock-free manner.
425 If the \p key not found in the map, then the new item created from \p key
426 is inserted into the map (note that in this case the \ref key_type should be
427 constructible from type \p K).
428 Otherwise, the functor \p func is called with item found.
429 The functor \p Func may be a function with signature:
431 void func( bool bNew, value_type& item );
436 void operator()( bool bNew, value_type& item );
441 - \p bNew - \p true if the item has been inserted, \p false otherwise
442 - \p item - item of the list
444 The functor may change any fields of the \p item.second that is \ref value_type.
446 You may pass \p func argument by reference using <tt>boost::ref</tt>.
448 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
449 \p second is true if new item has been added or \p false if the item with \p key
450 already is in the list.
452 template <typename K, typename Func>
453 std::pair<bool, bool> ensure( K const& key, Func func )
455 scoped_node_ptr pNode( node_allocator().New( random_level(), key ));
456 # ifdef CDS_CXX11_LAMBDA_SUPPORT
457 std::pair<bool, bool> res = base_class::ensure( *pNode,
458 [&func](bool bNew, node_type& item, node_type const& ){ cds::unref(func)( bNew, item.m_Value ); }
461 ensure_wrapper<Func> wrapper( func );
462 std::pair<bool, bool> res = base_class::ensure( *pNode, cds::ref(wrapper) );
464 if ( res.first && res.second )
469 /// Delete \p key from the map
470 /** \anchor cds_nonintrusive_SkipListMap_erase_val
472 Return \p true if \p key is found and deleted, \p false otherwise
474 template <typename K>
475 bool erase( K const& key )
477 return base_class::erase(key);
480 /// Deletes the item from the map using \p pred predicate for searching
482 The function is an analog of \ref cds_nonintrusive_SkipListMap_erase_val "erase(K const&)"
483 but \p pred is used for key comparing.
484 \p Less functor has the interface like \p std::less.
485 \p Less must imply the same element order as the comparator used for building the map.
487 template <typename K, typename Less>
488 bool erase_with( K const& key, Less pred )
490 return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >());
493 /// Delete \p key from the map
494 /** \anchor cds_nonintrusive_SkipListMap_erase_func
496 The function searches an item with key \p key, calls \p f functor
497 and deletes the item. If \p key is not found, the functor is not called.
499 The functor \p Func interface:
502 void operator()(value_type& item) { ... }
505 The functor may be passed by reference using <tt>boost:ref</tt>
507 Return \p true if key is found and deleted, \p false otherwise
509 template <typename K, typename Func>
510 bool erase( K const& key, Func f )
512 # ifdef CDS_CXX11_LAMBDA_SUPPORT
513 return base_class::erase( key, [&f]( node_type& node) { cds::unref(f)( node.m_Value ); } );
515 erase_functor<Func> wrapper(f);
516 return base_class::erase( key, cds::ref(wrapper));
520 /// Deletes the item from the map using \p pred predicate for searching
522 The function is an analog of \ref cds_nonintrusive_SkipListMap_erase_func "erase(K const&, Func)"
523 but \p pred is used for key comparing.
524 \p Less functor has the interface like \p std::less.
525 \p Less must imply the same element order as the comparator used for building the map.
527 template <typename K, typename Less, typename Func>
528 bool erase_with( K const& key, Less pred, Func f )
530 # ifdef CDS_CXX11_LAMBDA_SUPPORT
531 return base_class::erase_with( key,
532 cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >(),
533 [&f]( node_type& node) { cds::unref(f)( node.m_Value ); } );
535 erase_functor<Func> wrapper(f);
536 return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >(), cds::ref(wrapper));
540 /// Extracts the item from the map with specified \p key
541 /** \anchor cds_nonintrusive_SkipListMap_hp_extract
542 The function searches an item with key equal to \p key in the map,
543 unlinks it from the map, and returns it in \p ptr parameter.
544 If the item with key equal to \p key is not found the function returns \p false.
546 Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type.
548 The item extracted is freed automatically by garbage collector \p GC
549 when returned \ref guarded_ptr object will be destroyed or released.
550 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
554 typedef cds::container::SkipListMap< cds::gc::HP, int, foo, my_traits > skip_list;
558 skip_list::guarded_ptr gp;
559 if ( theList.extract( gp, 5 ) ) {
563 // Destructor of gp releases internal HP guard and frees the pointer
567 template <typename K>
568 bool extract( guarded_ptr& ptr, K const& key )
570 return base_class::extract_( ptr.guard(), key, typename base_class::key_comparator() );
573 /// Extracts the item from the map with comparing functor \p pred
575 The function is an analog of \ref cds_nonintrusive_SkipListMap_hp_extract "extract(K const&)"
576 but \p pred predicate is used for key comparing.
578 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
580 \p pred must imply the same element order as the comparator used for building the map.
582 template <typename K, typename Less>
583 bool extract_with( guarded_ptr& ptr, K const& key, Less pred )
585 typedef cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor > wrapped_less;
586 return base_class::extract_( ptr.guard(), key, cds::opt::details::make_comparator_from_less<wrapped_less>() );
589 /// Extracts an item with minimal key from the map
591 The function searches an item with minimal key, unlinks it, and returns the item found in \p ptr parameter.
592 If the skip-list is empty the function returns \p false.
594 The item extracted is freed automatically by garbage collector \p GC
595 when returned \ref guarded_ptr object will be destroyed or released.
596 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
600 typedef cds::continer::SkipListMap< cds::gc::HP, int, foo, my_traits > skip_list;
604 skip_list::guarded_ptr gp;
605 if ( theList.extract_min( gp )) {
609 // Destructor of gp releases internal HP guard and then frees the pointer
613 bool extract_min( guarded_ptr& ptr)
615 return base_class::extract_min_( ptr.guard() );
618 /// Extracts an item with maximal key from the map
620 The function searches an item with maximal key, unlinks it, and returns the pointer to item found in \p ptr parameter.
621 If the skip-list is empty the function returns empty \p guarded_ptr.
623 The item found is freed by garbage collector \p GC automatically
624 when returned \ref guarded_ptr object will be destroyed or released.
625 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
629 typedef cds::container::SkipListMap< cds::gc::HP, int, foo, my_traits > skip_list;
633 skip_list::guarded_ptr gp;
634 if ( theList.extract_max( gp )) {
638 // Destructor of gp releases internal HP guard and then frees the pointer
642 bool extract_max( guarded_ptr& dest )
644 return base_class::extract_max_( dest.guard() );
647 /// Find the key \p key
648 /** \anchor cds_nonintrusive_SkipListMap_find_cfunc
650 The function searches the item with key equal to \p key and calls the functor \p f for item found.
651 The interface of \p Func functor is:
654 void operator()( value_type& item );
657 where \p item is the item found.
659 You can pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
661 The functor may change \p item.second.
663 The function returns \p true if \p key is found, \p false otherwise.
665 template <typename K, typename Func>
666 bool find( K const& key, Func f )
668 # ifdef CDS_CXX11_LAMBDA_SUPPORT
669 return base_class::find( key, [&f](node_type& item, K const& ) { cds::unref(f)( item.m_Value );});
671 find_wrapper<Func> wrapper(f);
672 return base_class::find( key, cds::ref(wrapper) );
676 /// Finds the key \p val using \p pred predicate for searching
678 The function is an analog of \ref cds_nonintrusive_SkipListMap_find_cfunc "find(K const&, Func)"
679 but \p pred is used for key comparing.
680 \p Less functor has the interface like \p std::less.
681 \p Less must imply the same element order as the comparator used for building the map.
683 template <typename K, typename Less, typename Func>
684 bool find_with( K const& key, Less pred, Func f )
686 # ifdef CDS_CXX11_LAMBDA_SUPPORT
687 return base_class::find_with( key,
688 cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >(),
689 [&f](node_type& item, K const& ) { cds::unref(f)( item.m_Value );});
691 find_wrapper<Func> wrapper(f);
692 return base_class::find_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >(), cds::ref(wrapper) );
696 /// Find the key \p key
697 /** \anchor cds_nonintrusive_SkipListMap_find_val
699 The function searches the item with key equal to \p key
700 and returns \p true if it is found, and \p false otherwise.
702 template <typename K>
703 bool find( K const& key )
705 return base_class::find( key );
708 /// Finds the key \p val using \p pred predicate for searching
710 The function is an analog of \ref cds_nonintrusive_SkipListMap_find_val "find(K const&)"
711 but \p pred is used for key comparing.
712 \p Less functor has the interface like \p std::less.
713 \p Less must imply the same element order as the comparator used for building the map.
715 template <typename K, typename Less>
716 bool find_with( K const& key, Less pred )
718 return base_class::find_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >() );
721 /// Finds the key \p key and return the item found
722 /** \anchor cds_nonintrusive_SkipListMap_hp_get
723 The function searches the item with key equal to \p key
724 and assigns the item found to guarded pointer \p ptr.
725 The function returns \p true if \p key is found, and \p false otherwise.
726 If \p key is not found the \p ptr parameter is not changed.
728 It is safe when a concurrent thread erases the item returned in \p ptr guarded pointer.
729 In this case the item will be freed later by garbage collector \p GC automatically
730 when \p guarded_ptr object will be destroyed or released.
731 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
735 typedef cds::container::SkipListMap< cds::gc::HP, int, foo, my_traits > skip_list;
739 skip_list::guarded_ptr gp;
740 if ( theList.get( gp, 5 ) ) {
744 // Destructor of guarded_ptr releases internal HP guard
748 Note the compare functor specified for class \p Traits template parameter
749 should accept a parameter of type \p K that can be not the same as \p value_type.
751 template <typename K>
752 bool get( guarded_ptr& ptr, K const& key )
754 return base_class::get_with_( ptr.guard(), key, typename base_class::key_comparator() );
757 /// Finds the key \p key and return the item found
759 The function is an analog of \ref cds_nonintrusive_SkipListMap_hp_get "get( guarded_ptr& ptr, K const&)"
760 but \p pred is used for comparing the keys.
762 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
764 \p pred must imply the same element order as the comparator used for building the map.
766 template <typename K, typename Less>
767 bool get_with( guarded_ptr& ptr, K const& key, Less pred )
769 typedef cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor > wrapped_less;
770 return base_class::get_with_( ptr.guard(), key, cds::opt::details::make_comparator_from_less< wrapped_less >());
779 /// Checks if the map is empty
781 Emptiness is checked by item counting: if item count is zero then the map is empty.
785 return base_class::empty();
788 /// Returns item count in the map
791 return base_class::size();
794 /// Returns const reference to internal statistics
795 stat const& statistics() const
797 return base_class::statistics();
801 }} // namespace cds::container
803 #endif // #ifndef __CDS_CONTAINER_SKIP_LIST_MAP_IMPL_H