2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_CONTAINER_IMPL_SKIP_LIST_MAP_H
32 #define CDSLIB_CONTAINER_IMPL_SKIP_LIST_MAP_H
34 #include <cds/container/details/guarded_ptr_cast.h>
36 namespace cds { namespace container {
38 /// Lock-free skip-list map
39 /** @ingroup cds_nonintrusive_map
40 \anchor cds_nonintrusive_SkipListMap_hp
42 The implementation of well-known probabilistic data structure called skip-list
43 invented by W.Pugh in his papers:
44 - [1989] W.Pugh Skip Lists: A Probabilistic Alternative to Balanced Trees
45 - [1990] W.Pugh A Skip List Cookbook
47 A skip-list is a probabilistic data structure that provides expected logarithmic
48 time search without the need of rebalance. The skip-list is a collection of sorted
49 linked list. Nodes are ordered by key. Each node is linked into a subset of the lists.
50 Each list has a level, ranging from 0 to 32. The bottom-level list contains
51 all the nodes, and each higher-level list is a sublist of the lower-level lists.
52 Each node is created with a random top level (with a random height), and belongs
53 to all lists up to that level. The probability that a node has the height 1 is 1/2.
54 The probability that a node has the height N is 1/2 ** N (more precisely,
55 the distribution depends on an random generator provided, but our generators
58 The lock-free variant of skip-list is implemented according to book
59 - [2008] M.Herlihy, N.Shavit "The Art of Multiprocessor Programming",
60 chapter 14.4 "A Lock-Free Concurrent Skiplist"
63 - \p GC - Garbage collector used.
64 - \p K - type of a key to be stored in the list.
65 - \p T - type of a value to be stored in the list.
66 - \p Traits - map traits, default is \p skip_list::traits
67 It is possible to declare option-based list with \p cds::container::skip_list::make_traits metafunction
68 istead of \p Traits template argument.
70 Like STL map class, \p %SkipListMap stores the key-value pair as <tt>std:pair< K const, T></tt>.
72 @warning The skip-list requires up to 67 hazard pointers that may be critical for some GCs for which
73 the guard count is limited (like \p gc::HP). Those GCs should be explicitly initialized with
74 hazard pointer enough: \code cds::gc::HP myhp( 67 ) \endcode. Otherwise an run-time exception may be raised
75 when you try to create skip-list object.
77 @note There are several specializations of \p %SkipListMap for each \p GC. You should include:
78 - <tt><cds/container/skip_list_map_hp.h></tt> for \p gc::HP garbage collector
79 - <tt><cds/container/skip_list_map_dhp.h></tt> for \p gc::DHP garbage collector
80 - <tt><cds/container/skip_list_map_rcu.h></tt> for \ref cds_nonintrusive_SkipListMap_rcu "RCU type"
81 - <tt><cds/container/skip_list_map_nogc.h></tt> for \ref cds_nonintrusive_SkipListMap_nogc "non-deletable SkipListMap"
87 #ifdef CDS_DOXYGEN_INVOKED
88 typename Traits = skip_list::traits
94 #ifdef CDS_DOXYGEN_INVOKED
95 protected intrusive::SkipListSet< GC, std::pair<Key const, T>, Traits >
97 protected details::make_skip_list_map< GC, Key, T, Traits >::type
101 typedef details::make_skip_list_map< GC, Key, T, Traits > maker;
102 typedef typename maker::type base_class;
105 typedef GC gc; ///< Garbage collector
106 typedef Key key_type; ///< Key type
107 typedef T mapped_type; ///< Mapped type
108 typedef Traits traits; ///< Map traits
109 # ifdef CDS_DOXYGEN_INVOKED
110 typedef std::pair< Key const, T> value_type; ///< Key-value pair to be stored in the map
112 typedef typename maker::value_type value_type;
115 typedef typename base_class::back_off back_off; ///< Back-off strategy
116 typedef typename traits::allocator allocator_type; ///< Allocator type used for allocate/deallocate the skip-list nodes
117 typedef typename base_class::item_counter item_counter; ///< Item counting policy used
118 typedef typename maker::key_comparator key_comparator; ///< key comparison functor
119 typedef typename base_class::memory_model memory_model; ///< Memory ordering, see \p cds::opt::memory_model
120 typedef typename traits::random_level_generator random_level_generator ; ///< random level generator
121 typedef typename traits::stat stat; ///< internal statistics type
123 static size_t const c_nHazardPtrCount = base_class::c_nHazardPtrCount; ///< Count of hazard pointer required for the skip-list
127 typedef typename maker::node_type node_type;
128 typedef typename maker::node_allocator node_allocator;
130 typedef std::unique_ptr< node_type, typename maker::node_deallocator > scoped_node_ptr;
135 typedef typename gc::template guarded_ptr< node_type, value_type, details::guarded_ptr_cast_set<node_type, value_type> > guarded_ptr;
139 unsigned int random_level()
141 return base_class::random_level();
151 /// Destructor destroys the set object
156 ///@name Forward iterators (only for debugging purpose)
160 The forward iterator has some features:
162 - it has no post-increment operator
163 - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
164 For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard"
165 may be thrown if the limit of guard count per thread is exceeded.
166 - The iterator cannot be moved across thread boundary because it contains thread-private GC's guard.
167 - Iterator ensures thread-safety even if you delete the item the iterator points to. However, in case of concurrent
168 deleting operations there is no guarantee that you iterate all item in the list.
169 Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
171 @warning Use this iterator on the concurrent container for debugging purpose only.
173 @note \p end() and \p cend() are not dereferenceable.
175 The iterator interface:
179 // Default constructor
183 iterator( iterator const& src );
185 // Dereference operator
186 value_type * operator ->() const;
188 // Dereference operator
189 value_type& operator *() const;
191 // Preincrement operator
192 iterator& operator ++();
194 // Assignment operator
195 iterator& operator = (iterator const& src);
197 // Equality operators
198 bool operator ==(iterator const& i ) const;
199 bool operator !=(iterator const& i ) const;
203 typedef skip_list::details::iterator< typename base_class::iterator > iterator;
205 /// Const forward iterator type
206 typedef skip_list::details::iterator< typename base_class::const_iterator > const_iterator;
208 /// Returns a forward iterator addressing the first element in a map
211 return iterator( base_class::begin() );
214 /// Returns a forward const iterator addressing the first element in a map
215 const_iterator begin() const
220 /// Returns a forward const iterator addressing the first element in a map
221 const_iterator cbegin() const
223 return const_iterator( base_class::cbegin() );
226 /// Returns a forward iterator that addresses the location succeeding the last element in a map.
229 return iterator( base_class::end() );
232 /// Returns a forward const iterator that addresses the location succeeding the last element in a map.
233 const_iterator end() const
238 /// Returns a forward const iterator that addresses the location succeeding the last element in a map.
239 const_iterator cend() const
241 return const_iterator( base_class::cend() );
246 /// Inserts new node with key and default value
248 The function creates a node with \p key and default value, and then inserts the node created into the map.
251 - The \p key_type should be constructible from a value of type \p K.
252 In trivial case, \p K is equal to \p key_type.
253 - The \p mapped_type should be default-constructible.
255 Returns \p true if inserting successful, \p false otherwise.
257 template <typename K>
258 bool insert( K const& key )
260 return insert_with( key, [](value_type&){} );
265 The function creates a node with copy of \p val value
266 and then inserts the node created into the map.
269 - The \p key_type should be constructible from \p key of type \p K.
270 - The \p value_type should be constructible from \p val of type \p V.
272 Returns \p true if \p val is inserted into the set, \p false otherwise.
274 template <typename K, typename V>
275 bool insert( K const& key, V const& val )
277 return insert_with( key, [&val]( value_type& item ) { item.second = val; } );
280 /// Inserts new node and initialize it by a functor
282 This function inserts new node with key \p key and if inserting is successful then it calls
283 \p func functor with signature
286 void operator()( value_type& item );
290 The argument \p item of user-defined functor \p func is the reference
291 to the map's item inserted:
292 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
293 - <tt>item.second</tt> is a reference to item's value that may be changed.
295 \p key_type should be constructible from value of type \p K.
297 The function allows to split creating of new item into two part:
298 - create item from \p key;
299 - insert new item into the map;
300 - if inserting is successful, initialize the value of item by calling \p func functor
302 This can be useful if complete initialization of object of \p value_type is heavyweight and
303 it is preferable that the initialization should be completed only if inserting is successful.
305 template <typename K, typename Func>
306 bool insert_with( K const& key, Func func )
308 scoped_node_ptr pNode( node_allocator().New( random_level(), key ));
309 if ( base_class::insert( *pNode, [&func]( node_type& item ) { func( item.m_Value ); } )) {
316 /// For key \p key inserts data of type \p value_type created in-place from <tt>std::forward<Args>(args)...</tt>
318 Returns \p true if inserting successful, \p false otherwise.
320 template <typename K, typename... Args>
321 bool emplace( K&& key, Args&&... args )
323 scoped_node_ptr pNode( node_allocator().New( random_level(), std::forward<K>(key), std::forward<Args>(args)... ));
324 if ( base_class::insert( *pNode )) {
331 /// Updates data by \p key
333 The operation performs inserting or changing data with lock-free manner.
335 If the \p key not found in the map, then the new item created from \p key
336 will be inserted into the map iff \p bInsert is \p true
337 (note that in this case the \ref key_type should be constructible from type \p K).
338 Otherwise, if \p key is found, the functor \p func is called with item found.
339 The functor \p Func signature:
342 void operator()( bool bNew, value_type& item );
346 - \p bNew - \p true if the item has been inserted, \p false otherwise
347 - \p item - item of the map
349 The functor may change any fields of the \p item.second that is \ref value_type.
351 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
352 \p second is \p true if new item has been added or \p false if \p key already exists.
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 template <typename K, typename Func>
370 CDS_DEPRECATED("ensure() is deprecated, use update()")
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_erase_val
380 Return \p true if \p key is found and deleted, \p false otherwise
382 template <typename K>
383 bool erase( K const& key )
385 return base_class::erase(key);
388 /// Deletes the item from the map using \p pred predicate for searching
390 The function is an analog of \ref cds_nonintrusive_SkipListMap_erase_val "erase(K const&)"
391 but \p pred is used for key comparing.
392 \p Less functor has the interface like \p std::less.
393 \p Less must imply the same element order as the comparator used for building the map.
395 template <typename K, typename Less>
396 bool erase_with( K const& key, Less pred )
399 return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >());
402 /// Delete \p key from the map
403 /** \anchor cds_nonintrusive_SkipListMap_erase_func
405 The function searches an item with key \p key, calls \p f functor
406 and deletes the item. If \p key is not found, the functor is not called.
408 The functor \p Func interface:
411 void operator()(value_type& item) { ... }
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_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,
435 cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >(),
436 [&f]( node_type& node) { f( node.m_Value ); } );
439 /// Extracts the item from the map with specified \p key
440 /** \anchor cds_nonintrusive_SkipListMap_hp_extract
441 The function searches an item with key equal to \p key in the map,
442 unlinks it from the map, and returns a guarded pointer to the item found.
443 If \p key is not found the function returns an empty guarded pointer.
445 Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type.
447 The item extracted is freed automatically by garbage collector \p GC
448 when returned \p guarded_ptr object will be destroyed or released.
449 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
453 typedef cds::container::SkipListMap< cds::gc::HP, int, foo, my_traits > skip_list;
457 skip_list::guarded_ptr gp( theList.extract( 5 ));
462 // Destructor of gp releases internal HP guard and frees the pointer
466 template <typename K>
467 guarded_ptr extract( K const& key )
470 base_class::extract_( gp.guard(), key, typename base_class::key_comparator() );
474 /// Extracts the item from the map with comparing functor \p pred
476 The function is an analog of \ref cds_nonintrusive_SkipListMap_hp_extract "extract(K const&)"
477 but \p pred predicate is used for key comparing.
479 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
481 \p pred must imply the same element order as the comparator used for building the map.
483 template <typename K, typename Less>
484 guarded_ptr extract_with( K const& key, Less pred )
487 typedef cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor > wrapped_less;
489 base_class::extract_( gp.guard(), key, cds::opt::details::make_comparator_from_less<wrapped_less>() );
493 /// Extracts an item with minimal key from the map
495 The function searches an item with minimal key, unlinks it, and returns an guarded pointer to the item found.
496 If the skip-list is empty the function returns an empty guarded pointer.
498 The item extracted is freed automatically by garbage collector \p GC
499 when returned \p guarded_ptr object will be destroyed or released.
500 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
504 typedef cds::continer::SkipListMap< cds::gc::HP, int, foo, my_traits > skip_list;
508 skip_list::guarded_ptr gp( theList.extract_min());
513 // Destructor of gp releases internal HP guard and then frees the pointer
517 guarded_ptr extract_min()
520 base_class::extract_min_( gp.guard() );
524 /// Extracts an item with maximal key from the map
526 The function searches an item with maximal key, unlinks it, and returns a guarded pointer to item found.
527 If the skip-list is empty the function returns an empty \p guarded_ptr.
529 The item found is freed by garbage collector \p GC automatically
530 when returned \p guarded_ptr object will be destroyed or released.
531 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
535 typedef cds::container::SkipListMap< cds::gc::HP, int, foo, my_traits > skip_list;
539 skip_list::guarded_ptr gp( theList.extract_max());
544 // Destructor of gp releases internal HP guard and then frees the pointer
548 guarded_ptr extract_max()
551 base_class::extract_max_( gp.guard() );
555 /// Find the key \p key
556 /** \anchor cds_nonintrusive_SkipListMap_find_cfunc
558 The function searches the item with key equal to \p key and calls the functor \p f for item found.
559 The interface of \p Func functor is:
562 void operator()( value_type& item );
565 where \p item is the item found.
567 The functor may change \p item.second.
569 The function returns \p true if \p key is found, \p false otherwise.
571 template <typename K, typename Func>
572 bool find( K const& key, Func f )
574 return base_class::find( key, [&f](node_type& item, K const& ) { f( item.m_Value );});
577 /// Finds the key \p val using \p pred predicate for searching
579 The function is an analog of \ref cds_nonintrusive_SkipListMap_find_cfunc "find(K const&, Func)"
580 but \p pred is used for key comparing.
581 \p Less functor has the interface like \p std::less.
582 \p Less must imply the same element order as the comparator used for building the map.
584 template <typename K, typename Less, typename Func>
585 bool find_with( K const& key, Less pred, Func f )
588 return base_class::find_with( key,
589 cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >(),
590 [&f](node_type& item, K const& ) { f( item.m_Value );});
593 /// Checks whether the map contains \p key
595 The function searches the item with key equal to \p key
596 and returns \p true if it is found, and \p false otherwise.
598 template <typename K>
599 bool contains( K const& key )
601 return base_class::contains( key );
604 template <typename K>
605 CDS_DEPRECATED("deprecated, use contains()")
606 bool find( K const& key )
608 return contains( key );
612 /// Checks whether the set contains \p key using \p pred predicate for searching
614 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
615 \p Less functor has the interface like \p std::less.
616 \p Less must imply the same element order as the comparator used for building the set.
618 template <typename K, typename Less>
619 bool contains( K const& key, Less pred )
622 return base_class::contains( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >() );
625 template <typename K, typename Less>
626 CDS_DEPRECATED("deprecated, use contains()")
627 bool find_with( K const& key, Less pred )
629 return contains( key, pred );
633 /// Finds the key \p key and return the item found
634 /** \anchor cds_nonintrusive_SkipListMap_hp_get
635 The function searches the item with key equal to \p key
636 and returns a guarded pointer to the item found.
637 If \p key is not found the function returns an empty guarded pointer.
639 It is safe when a concurrent thread erases the item returned as \p guarded_ptr.
640 In this case the item will be freed later by garbage collector \p GC automatically
641 when \p guarded_ptr object will be destroyed or released.
642 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
646 typedef cds::container::SkipListMap< cds::gc::HP, int, foo, my_traits > skip_list;
650 skip_list::guarded_ptr gp( theList.get( 5 ));
655 // Destructor of guarded_ptr releases internal HP guard
659 Note the compare functor specified for class \p Traits template parameter
660 should accept a parameter of type \p K that can be not the same as \p value_type.
662 template <typename K>
663 guarded_ptr get( K const& key )
666 base_class::get_with_( gp.guard(), key, typename base_class::key_comparator() );
670 /// Finds the key \p key and return the item found
672 The function is an analog of \ref cds_nonintrusive_SkipListMap_hp_get "get( K const&)"
673 but \p pred is used for comparing the keys.
675 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
677 \p pred must imply the same element order as the comparator used for building the map.
679 template <typename K, typename Less>
680 guarded_ptr get_with( K const& key, Less pred )
683 typedef cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor > wrapped_less;
685 base_class::get_with_( gp.guard(), key, cds::opt::details::make_comparator_from_less< wrapped_less >());
695 /// Checks if the map is empty
698 return base_class::empty();
701 /// Returns item count in the map
704 return base_class::size();
707 /// Returns const reference to internal statistics
708 stat const& statistics() const
710 return base_class::statistics();
713 }} // namespace cds::container
715 #endif // #ifndef CDSLIB_CONTAINER_IMPL_SKIP_LIST_MAP_H