2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
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_SKIP_LIST_MAP_RCU_H
32 #define CDSLIB_CONTAINER_SKIP_LIST_MAP_RCU_H
34 #include <cds/container/details/skip_list_base.h>
35 #include <cds/intrusive/skip_list_rcu.h>
36 #include <cds/container/details/make_skip_list_map.h>
38 namespace cds { namespace container {
40 /// Lock-free skip-list map (template specialization for \ref cds_urcu_desc "RCU")
41 /** @ingroup cds_nonintrusive_map
42 \anchor cds_nonintrusive_SkipListMap_rcu
44 The implementation of well-known probabilistic data structure called skip-list
45 invented by W.Pugh in his papers:
46 - [1989] W.Pugh Skip Lists: A Probabilistic Alternative to Balanced Trees
47 - [1990] W.Pugh A Skip List Cookbook
49 A skip-list is a probabilistic data structure that provides expected logarithmic
50 time search without the need of rebalance. The skip-list is a collection of sorted
51 linked list. Nodes are ordered by key. Each node is linked into a subset of the lists.
52 Each list has a level, ranging from 0 to 32. The bottom-level list contains
53 all the nodes, and each higher-level list is a sublist of the lower-level lists.
54 Each node is created with a random top level (with a random height), and belongs
55 to all lists up to that level. The probability that a node has the height 1 is 1/2.
56 The probability that a node has the height N is 1/2 ** N (more precisely,
57 the distribution depends on an random generator provided, but our generators
60 The lock-free variant of skip-list is implemented according to book
61 - [2008] M.Herlihy, N.Shavit "The Art of Multiprocessor Programming",
62 chapter 14.4 "A Lock-Free Concurrent Skiplist"
65 - \p RCU - one of \ref cds_urcu_gc "RCU type".
66 - \p K - type of a key to be stored in the list.
67 - \p T - type of a value to be stored in the list.
68 - \p Traits - map traits, default is \p skip_list::traits.
69 It is possible to declare option-based list with \p cds::container::skip_list::make_traits metafunction
70 instead of \p Traits template argument.
72 Like STL map class, \p %SkipListMap stores its key-value pair as <tt>std:pair< K const, T></tt>.
74 @note Before including <tt><cds/container/skip_list_map_rcu.h></tt> you should include appropriate RCU header file,
75 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
79 The class supports a forward iterator (\ref iterator and \ref const_iterator).
80 The iteration is ordered.
81 You may iterate over skip-list set items only under RCU lock.
82 Only in this case the iterator is thread-safe since
83 while RCU is locked any set's item cannot be reclaimed.
85 The requirement of RCU lock during iterating means that deletion of the elements (i.e. \ref erase)
88 @warning The iterator object cannot be passed between threads
90 The iterator class supports the following minimalistic interface:
97 iterator( iterator const& s);
99 value_type * operator ->() const;
100 value_type& operator *() const;
103 iterator& operator ++();
106 iterator& operator = (const iterator& src);
108 bool operator ==(iterator const& i ) const;
109 bool operator !=(iterator const& i ) const;
112 Note, the iterator object returned by \ref end, \p cend member functions points to \p nullptr and should not be dereferenced.
119 #ifdef CDS_DOXYGEN_INVOKED
120 typename Traits = skip_list::traits
125 class SkipListMap< cds::urcu::gc< RCU >, Key, T, Traits >:
126 #ifdef CDS_DOXYGEN_INVOKED
127 protected intrusive::SkipListSet< cds::urcu::gc< RCU >, std::pair<Key const, T>, Traits >
129 protected details::make_skip_list_map< cds::urcu::gc< RCU >, Key, T, Traits >::type
133 typedef details::make_skip_list_map< cds::urcu::gc< RCU >, Key, T, Traits > maker;
134 typedef typename maker::type base_class;
137 typedef cds::urcu::gc< RCU > gc; ///< Garbage collector used
138 typedef Key key_type; ///< Key type
139 typedef T mapped_type; ///< Mapped type
140 # ifdef CDS_DOXYGEN_INVOKED
141 typedef std::pair< K const, T> value_type; ///< Value type stored in the map
143 typedef typename maker::value_type value_type;
145 typedef Traits traits; ///< Map traits
147 typedef typename base_class::back_off back_off; ///< Back-off strategy used
148 typedef typename traits::allocator allocator_type; ///< Allocator type used for allocate/deallocate the skip-list nodes
149 typedef typename base_class::item_counter item_counter; ///< Item counting policy used
150 typedef typename maker::key_comparator key_comparator; ///< key comparison functor
151 typedef typename base_class::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
152 typedef typename traits::random_level_generator random_level_generator; ///< random level generator
153 typedef typename traits::stat stat; ///< internal statistics type
157 typedef typename maker::node_type node_type;
158 typedef typename maker::node_allocator node_allocator;
160 typedef std::unique_ptr< node_type, typename maker::node_deallocator > scoped_node_ptr;
164 typedef typename base_class::rcu_lock rcu_lock; ///< RCU scoped lock
165 /// Group of \p extract_xxx functions do not require external locking
166 static CDS_CONSTEXPR const bool c_bExtractLockExternal = base_class::c_bExtractLockExternal;
168 /// pointer to extracted node
169 using exempt_ptr = cds::urcu::exempt_ptr< gc, node_type, value_type, typename maker::intrusive_type_traits::disposer >;
173 struct raw_ptr_converter
175 value_type * operator()( node_type * p ) const
177 return p ? &p->m_Value : nullptr;
180 value_type& operator()( node_type& n ) const
185 value_type const& operator()( node_type const& n ) const
193 /// Result of \p get(), \p get_with() functions - pointer to the node found
194 typedef cds::urcu::raw_ptr_adaptor< value_type, typename base_class::raw_ptr, raw_ptr_converter > raw_ptr;
198 unsigned int random_level()
200 return base_class::random_level();
210 /// Destructor destroys the set object
215 ///@name Forward ordered iterators (thread-safe under RCU lock)
219 The forward iterator has some features:
220 - it has no post-increment operator
221 - it depends on iterator of underlying \p OrderedList
223 You may safely use iterators in multi-threaded environment only under RCU lock.
224 Otherwise, a crash is possible if another thread deletes the element the iterator points to.
226 typedef skip_list::details::iterator< typename base_class::iterator > iterator;
228 /// Const iterator type
229 typedef skip_list::details::iterator< typename base_class::const_iterator > const_iterator;
231 /// Returns a forward iterator addressing the first element in a map
234 return iterator( base_class::begin());
237 /// Returns a forward const iterator addressing the first element in a map
238 const_iterator begin() const
242 /// Returns a forward const iterator addressing the first element in a map
243 const_iterator cbegin() const
245 return const_iterator( base_class::cbegin());
248 /// Returns a forward iterator that addresses the location succeeding the last element in a map.
251 return iterator( base_class::end());
254 /// Returns a forward const iterator that addresses the location succeeding the last element in a map.
255 const_iterator end() const
259 /// Returns a forward const iterator that addresses the location succeeding the last element in a map.
260 const_iterator cend() const
262 return const_iterator( base_class::cend());
267 /// Inserts new node with key and default value
269 The function creates a node with \p key and default value, and then inserts the node created into the map.
272 - The \p key_type should be constructible from a value of type \p K.
273 In trivial case, \p K is equal to \p key_type.
274 - The \p mapped_type should be default-constructible.
276 RCU \p synchronize method can be called. RCU should not be locked.
278 Returns \p true if inserting successful, \p false otherwise.
280 template <typename K>
281 bool insert( K const& key )
283 return insert_with( key, [](value_type&){} );
288 The function creates a node with copy of \p val value
289 and then inserts the node created into the map.
292 - The \p key_type should be constructible from \p key of type \p K.
293 - The \p value_type should be constructible from \p val of type \p V.
295 RCU \p synchronize method can be called. RCU should not be locked.
297 Returns \p true if \p val is inserted into the set, \p false otherwise.
299 template <typename K, typename V>
300 bool insert( K const& key, V const& val )
302 scoped_node_ptr pNode( node_allocator().New( random_level(), key, val ));
303 if ( base_class::insert( *pNode ))
311 /// Inserts new node and initialize it by a functor
313 This function inserts new node with key \p key and if inserting is successful then it calls
314 \p func functor with signature
317 void operator()( value_type& item );
321 The argument \p item of user-defined functor \p func is the reference
322 to the map's item inserted:
323 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
324 - <tt>item.second</tt> is a reference to item's value that may be changed.
326 The function allows to split creating of new item into three part:
327 - create item from \p key;
328 - insert new item into the map;
329 - if inserting is successful, initialize the value of item by calling \p func functor
331 This can be useful if complete initialization of object of \p value_type is heavyweight and
332 it is preferable that the initialization should be completed only if inserting is successful.
334 RCU \p synchronize method can be called. RCU should not be locked.
336 template <typename K, typename Func>
337 bool insert_with( const K& key, Func func )
339 scoped_node_ptr pNode( node_allocator().New( random_level(), key ));
340 if ( base_class::insert( *pNode, [&func]( node_type& item ) { func( item.m_Value ); } )) {
347 /// For key \p key inserts data of type \p value_type created in-place from \p args
349 Returns \p true if inserting successful, \p false otherwise.
351 RCU \p synchronize() method can be called. RCU should not be locked.
353 template <typename K, typename... Args>
354 bool emplace( K&& key, Args&&... args )
356 scoped_node_ptr pNode( node_allocator().New( random_level(), std::forward<K>(key), std::forward<Args>(args)... ));
357 if ( base_class::insert( *pNode )) {
364 /// Updates data by \p key
366 The operation performs inserting or changing data with lock-free manner.
368 If the \p key not found in the map, then the new item created from \p key
369 is inserted into the map iff \p bInsert is \p true.
370 Otherwise, if \p key found, the functor \p func is called with item found.
371 The functor \p Func interface is:
374 void operator()( bool bNew, value_type& item );
378 - \p bNew - \p true if the item has been inserted, \p false otherwise
379 - \p item - item of the map
381 The functor may change any fields of \p item.second.
383 RCU \p synchronize() method can be called. RCU should not be locked.
385 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
386 \p second is \p true if new item has been added or \p false if the item with \p key
389 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
391 template <typename K, typename Func>
392 std::pair<bool, bool> update( K const& key, Func func, bool bInsert = true )
394 scoped_node_ptr pNode( node_allocator().New( random_level(), key ));
395 std::pair<bool, bool> res = base_class::update( *pNode,
396 [&func](bool bNew, node_type& item, node_type const& ){ func( bNew, item.m_Value );},
399 if ( res.first && res.second )
404 template <typename K, typename Func>
405 CDS_DEPRECATED("ensure() is deprecated, use update()")
406 std::pair<bool, bool> ensure( K const& key, Func func )
408 return update( key, func, true );
412 /// Delete \p key from the map
413 /**\anchor cds_nonintrusive_SkipListMap_rcu_erase_val
415 RCU \p synchronize method can be called. RCU should not be locked.
417 Return \p true if \p key is found and deleted, \p false otherwise
419 template <typename K>
420 bool erase( K const& key )
422 return base_class::erase(key);
425 /// Deletes the item from the map using \p pred predicate for searching
427 The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_erase_val "erase(K const&)"
428 but \p pred is used for key comparing.
429 \p Less functor has the interface like \p std::less.
430 \p Less must imply the same element order as the comparator used for building the map.
432 template <typename K, typename Less>
433 bool erase_with( K const& key, Less pred )
436 return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >());
439 /// Delete \p key from the map
440 /** \anchor cds_nonintrusive_SkipListMap_rcu_erase_func
442 The function searches an item with key \p key, calls \p f functor
443 and deletes the item. If \p key is not found, the functor is not called.
445 The functor \p Func interface:
448 void operator()(value_type& item) { ... }
452 RCU \p synchronize method can be called. RCU should not be locked.
454 Return \p true if key is found and deleted, \p false otherwise
456 template <typename K, typename Func>
457 bool erase( K const& key, Func f )
459 return base_class::erase( key, [&f]( node_type& node) { f( node.m_Value ); } );
462 /// Deletes the item from the map using \p pred predicate for searching
464 The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_erase_func "erase(K const&, Func)"
465 but \p pred is used for key comparing.
466 \p Less functor has the interface like \p std::less.
467 \p Less must imply the same element order as the comparator used for building the map.
469 template <typename K, typename Less, typename Func>
470 bool erase_with( K const& key, Less pred, Func f )
473 return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >(),
474 [&f]( node_type& node) { f( node.m_Value ); } );
477 /// Extracts the item from the map with specified \p key
478 /** \anchor cds_nonintrusive_SkipListMap_rcu_extract
479 The function searches an item with key equal to \p key in the map,
480 unlinks it from the set, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
481 If the item is not found the function returns an empty \p exempt_ptr
483 Note the compare functor from \p Traits class' template argument
484 should accept a parameter of type \p K that can be not the same as \p key_type.
486 RCU \p synchronize() method can be called. RCU should NOT be locked.
488 The function does not free the item found.
489 The item will be implicitly freed when the returned object is destroyed or when
490 its \p release() member function is called.
492 template <typename K>
493 exempt_ptr extract( K const& key )
495 return exempt_ptr( base_class::do_extract( key ));
498 /// Extracts the item from the map with comparing functor \p pred
500 The function is an analog of \p extract(K const&) but \p pred predicate is used for key comparing.
501 \p Less has the semantics like \p std::less.
502 \p pred must imply the same element order as the comparator used for building the map.
504 template <typename K, typename Less>
505 exempt_ptr extract_with( K const& key, Less pred )
508 return exempt_ptr( base_class::do_extract_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >()));
511 /// Extracts an item with minimal key from the map
513 The function searches an item with minimal key, unlinks it,
514 and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item.
515 If the skip-list is empty the function returns an empty \p exempt_ptr.
517 RCU \p synchronize method can be called. RCU should NOT be locked.
519 The function does not free the item found.
520 The item will be implicitly freed when the returned object is destroyed or when
521 its \p release() member function is called.
523 exempt_ptr extract_min()
525 return exempt_ptr( base_class::do_extract_min());
528 /// Extracts an item with maximal key from the map
530 The function searches an item with maximal key, unlinks it from the set,
531 and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item.
532 If the skip-list is empty the function returns an empty \p exempt_ptr.
534 RCU \p synchronize method can be called. RCU should NOT be locked.
536 The function does not free the item found.
537 The item will be implicitly freed when the returned object is destroyed or when
538 its \p release() member function is called.
540 exempt_ptr extract_max()
542 return exempt_ptr( base_class::do_extract_max());
545 /// Find the key \p key
546 /** \anchor cds_nonintrusive_SkipListMap_rcu_find_cfunc
548 The function searches the item with key equal to \p key and calls the functor \p f for item found.
549 The interface of \p Func functor is:
552 void operator()( value_type& item );
555 where \p item is the item found.
557 The functor may change \p item.second.
559 The function applies RCU lock internally.
561 The function returns \p true if \p key is found, \p false otherwise.
563 template <typename K, typename Func>
564 bool find( K const& key, Func f )
566 return base_class::find( key, [&f](node_type& item, K const& ) { f( item.m_Value );});
569 /// Finds the key \p val using \p pred predicate for searching
571 The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_find_cfunc "find(K const&, Func)"
572 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 map.
576 template <typename K, typename Less, typename Func>
577 bool find_with( K const& key, Less pred, Func f )
580 return base_class::find_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >(),
581 [&f](node_type& item, K const& ) { f( item.m_Value );});
584 /// Checks whether the map contains \p key
586 The function searches the item with key equal to \p key
587 and returns \p true if it is found, and \p false otherwise.
589 The function applies RCU lock internally.
591 template <typename K>
592 bool contains( K const& key )
594 return base_class::contains( key );
597 template <typename K>
598 CDS_DEPRECATED("deprecated, use contains()")
599 bool find( K const& key )
601 return contains( key );
605 /// Checks whether the map contains \p key using \p pred predicate for searching
607 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
608 \p Less functor has the interface like \p std::less.
609 \p Less must imply the same element order as the comparator used for building the set.
611 template <typename K, typename Less>
612 bool contains( K const& key, Less pred )
615 return base_class::contains( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >());
618 template <typename K, typename Less>
619 CDS_DEPRECATED("deprecated, use contains()")
620 bool find_with( K const& key, Less pred )
622 return contains( key, pred );
626 /// Finds the key \p key and return the item found
627 /** \anchor cds_nonintrusive_SkipListMap_rcu_get
628 The function searches the item with key equal to \p key and returns a \p raw_ptr object pointing to an item found.
629 If \p key is not found it returns empty \p raw_ptr.
631 Note the compare functor in \p Traits class' template argument
632 should accept a parameter of type \p K that can be not the same as \p key_type.
634 RCU should be locked before call of this function.
635 Returned item is valid only while RCU is locked:
637 typedef cds::container::SkipListMap< cds::urcu::gc< cds::urcu::general_buffered<> >, int, foo, my_traits > skip_list;
640 typename skip_list::raw_ptr pVal;
643 skip_list::rcu_lock lock;
645 pVal = theList.get( 5 );
651 // You can manually release pVal after RCU-locked section
655 template <typename K>
656 raw_ptr get( K const& key )
658 return raw_ptr( base_class::get( key ));
661 /// Finds the key \p key and return the item found
663 The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_get "get(K const&)"
664 but \p pred is used for comparing the keys.
666 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
668 \p pred must imply the same element order as the comparator used for building the map.
670 template <typename K, typename Less>
671 raw_ptr get_with( K const& key, Less pred )
674 return raw_ptr( base_class::get_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >()));
677 /// Clears the map (not atomic)
683 /// Checks if the map is empty
685 Emptiness is checked by item counting: if item count is zero then the map is empty.
689 return base_class::empty();
692 /// Returns item count in the map
695 return base_class::size();
698 /// Returns const reference to internal statistics
699 stat const& statistics() const
701 return base_class::statistics();
704 }} // namespace cds::container
706 #endif // #ifndef CDSLIB_CONTAINER_SKIP_LIST_MAP_RCU_H