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_LAZY_KVLIST_RCU_H
32 #define CDSLIB_CONTAINER_LAZY_KVLIST_RCU_H
35 #include <cds/container/details/lazy_list_base.h>
36 #include <cds/intrusive/lazy_list_rcu.h>
37 #include <cds/container/details/make_lazy_kvlist.h>
39 namespace cds { namespace container {
41 /// Lazy ordered list (key-value pair), template specialization for \ref cds_urcu_desc "RCU"
42 /** @ingroup cds_nonintrusive_list
43 \anchor cds_nonintrusive_LazyKVList_rcu
45 This is key-value variation of non-intrusive \p %LazyList.
46 Like standard container, this implementation split a value stored into two part -
47 constant key and alterable value.
49 Usually, ordered single-linked list is used as a building block for the hash table implementation.
50 The complexity of searching is <tt>O(N)</tt>.
53 - \p RCU - one of \ref cds_urcu_gc "RCU type"
54 - \p Key - key type of an item to be stored in the list. It should be copy-constructible
55 - \p Value - value type to be stored in the list
56 - \p Traits - type traits, default is \p lazy_list::traits
57 It is possible to declare option-based list with \p lazy_list::make_traits metafunction istead of \p Traits template
58 argument. For example, the following traits-based declaration of \p gc::HP lazy list
60 #include <cds/urcu/general_threaded.h>
61 #include <cds/container/lazy_kvlist_rcu.h>
62 // Declare comparator for the item
64 int operator ()( int i1, int i2 )
71 struct my_traits: public cds::container::lazy_list::traits
73 typedef my_compare compare;
76 // Declare traits-based list
77 typedef cds::container::LazyKVList< cds::urcu::gc< cds::urcu::general_threaded<> >, int, int, my_traits > traits_based_list;
79 is equal to the following option-based list
81 #include <cds/urcu/general_threaded.h>
82 #include <cds/container/lazy_kvlist_rcu.h>
84 // my_compare is the same
86 // Declare option-based list
87 typedef cds::container::LazyKVList< cds::urcu::gc< cds::urcu::general_threaded<> >, int, int,
88 typename cds::container::lazy_list::make_traits<
89 cds::container::opt::compare< my_compare > // item comparator option
94 @note Before including <tt><cds/container/lazy_kvlist_rcu.h></tt> you should include appropriate RCU header file,
95 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
101 #ifdef CDS_DOXYGEN_INVOKED
102 typename Traits = lazy_list::traits
107 class LazyKVList< cds::urcu::gc<RCU>, Key, Value, Traits >:
108 #ifdef CDS_DOXYGEN_INVOKED
109 protected intrusive::LazyList< cds::urcu::gc<RCU>, implementation_defined, Traits >
111 protected details::make_lazy_kvlist< cds::urcu::gc<RCU>, Key, Value, Traits >::type
115 typedef details::make_lazy_kvlist< cds::urcu::gc<RCU>, Key, Value, Traits > maker;
116 typedef typename maker::type base_class;
120 typedef cds::urcu::gc<RCU> gc; ///< Garbage collector
121 #ifdef CDS_DOXYGEN_INVOKED
122 typedef Key key_type ; ///< Key type
123 typedef Value mapped_type ; ///< Type of value stored in the list
124 typedef std::pair<key_type const, mapped_type> value_type ; ///< key/value pair stored in the list
126 typedef typename maker::key_type key_type;
127 typedef typename maker::mapped_type mapped_type;
128 typedef typename maker::value_type value_type;
130 typedef typename base_class::back_off back_off; ///< Back-off strategy used
131 typedef typename maker::allocator_type allocator_type; ///< Allocator type used for allocate/deallocate the 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 cds::opt::memory_model option
135 typedef typename base_class::rcu_check_deadlock rcu_check_deadlock ; ///< RCU deadlock checking policy
137 typedef typename gc::scoped_lock rcu_lock ; ///< RCU scoped lock
138 static CDS_CONSTEXPR const bool c_bExtractLockExternal = base_class::c_bExtractLockExternal; ///< Group of \p extract_xxx functions require external locking
142 typedef typename base_class::value_type node_type;
143 typedef typename maker::cxx_allocator cxx_allocator;
144 typedef typename maker::node_deallocator node_deallocator;
145 typedef typename maker::intrusive_traits::compare intrusive_key_comparator;
147 typedef typename base_class::node_type head_type;
151 /// pointer to extracted node
152 using exempt_ptr = cds::urcu::exempt_ptr< gc, node_type, value_type, typename maker::intrusive_traits::disposer,
153 cds::urcu::details::conventional_exempt_pair_cast<node_type, value_type>
155 /// Type of \p get() member function return value
156 typedef value_type * raw_ptr;
160 template <typename K>
161 static node_type * alloc_node(const K& key)
163 return cxx_allocator().New( key );
166 template <typename K, typename V>
167 static node_type * alloc_node( const K& key, const V& val )
169 return cxx_allocator().New( key, val );
172 template <typename... Args>
173 static node_type * alloc_node( Args&&... args )
175 return cxx_allocator().MoveNew( std::forward<Args>(args)... );
178 static void free_node( node_type * pNode )
180 cxx_allocator().Delete( pNode );
183 struct node_disposer {
184 void operator()( node_type * pNode )
189 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
193 return base_class::m_Head;
196 head_type& head() const
198 return const_cast<head_type&>( base_class::m_Head );
203 return base_class::m_Tail;
206 head_type& tail() const
208 return const_cast<head_type&>( base_class::m_Tail );
215 template <bool IsConst>
216 class iterator_type: protected base_class::template iterator_type<IsConst>
218 typedef typename base_class::template iterator_type<IsConst> iterator_base;
220 iterator_type( head_type const& pNode )
221 : iterator_base( const_cast<head_type *>(&pNode) )
223 iterator_type( head_type const * pNode )
224 : iterator_base( const_cast<head_type *>(pNode) )
227 friend class LazyKVList;
230 typedef typename cds::details::make_const_type<mapped_type, IsConst>::reference value_ref;
231 typedef typename cds::details::make_const_type<mapped_type, IsConst>::pointer value_ptr;
233 typedef typename cds::details::make_const_type<value_type, IsConst>::reference pair_ref;
234 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer pair_ptr;
239 iterator_type( iterator_type const& src )
240 : iterator_base( src )
243 key_type const& key() const
245 typename iterator_base::value_ptr p = iterator_base::operator ->();
246 assert( p != nullptr );
247 return p->m_Data.first;
250 value_ref val() const
252 typename iterator_base::value_ptr p = iterator_base::operator ->();
253 assert( p != nullptr );
254 return p->m_Data.second;
257 pair_ptr operator ->() const
259 typename iterator_base::value_ptr p = iterator_base::operator ->();
260 return p ? &(p->m_Data) : nullptr;
263 pair_ref operator *() const
265 typename iterator_base::value_ref p = iterator_base::operator *();
270 iterator_type& operator ++()
272 iterator_base::operator ++();
277 bool operator ==(iterator_type<C> const& i ) const
279 return iterator_base::operator ==(i);
282 bool operator !=(iterator_type<C> const& i ) const
284 return iterator_base::operator !=(i);
291 typedef iterator_type<false> iterator;
293 /// Const forward iterator
294 typedef iterator_type<true> const_iterator;
296 /// Returns a forward iterator addressing the first element in a list
298 For empty list \code begin() == end() \endcode
302 iterator it( head() );
303 ++it ; // skip dummy head
307 /// Returns an iterator that addresses the location succeeding the last element in a list
309 Do not use the value returned by <tt>end</tt> function to access any item.
310 Internally, <tt>end</tt> returning value pointing to dummy tail node.
312 The returned value can be used only to control reaching the end of the list.
313 For empty list \code begin() == end() \endcode
317 return iterator( tail() );
320 /// Returns a forward const iterator addressing the first element in a list
322 const_iterator begin() const
324 const_iterator it( head() );
325 ++it; // skip dummy head
328 const_iterator cbegin() const
330 const_iterator it( head() );
331 ++it; // skip dummy head
336 /// Returns an const iterator that addresses the location succeeding the last element in a list
338 const_iterator end() const
340 return const_iterator( tail());
342 const_iterator cend() const
344 return const_iterator( tail());
349 /// Default constructor
353 /// Destructor clears the list
359 /// Inserts new node with key and default value
361 The function creates a node with \p key and default value, and then inserts the node created into the list.
364 - The \ref key_type should be constructible from value of type \p K.
365 In trivial case, \p K is equal to \p key_type.
366 - The \ref mapped_type should be default-constructible.
368 The function makes RCU lock internally.
370 Returns \p true if inserting successful, \p false otherwise.
372 template <typename K>
373 bool insert( const K& key )
375 return insert_at( head(), key );
378 /// Inserts new node with a key and a value
380 The function creates a node with \p key and value \p val, and then inserts the node created into the list.
383 - The \p key_type should be constructible from \p key of type \p K.
384 - The \p mapped_type should be constructible from \p val of type \p V.
386 The function makes RCU lock internally.
388 Returns \p true if inserting successful, \p false otherwise.
390 template <typename K, typename V>
391 bool insert( const K& key, const V& val )
393 return insert_at( head(), key, val );
396 /// Inserts new node and initializes it by a functor
398 This function inserts new node with key \p key and if inserting is successful then it calls
399 \p func functor with signature
402 void operator()( value_type& item );
406 The argument \p item of user-defined functor \p func is the reference
407 to the list's item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
408 The user-defined functor is called only if inserting is successful.
410 The key_type should be constructible from value of type \p K.
412 The function allows to split creating of new item into two part:
413 - create item from \p key;
414 - insert new item into the list;
415 - if inserting is successful, initialize the value of item by calling \p func functor
417 This can be useful if complete initialization of object of \p mapped_type is heavyweight and
418 it is preferable that the initialization should be completed only if inserting is successful.
420 The function makes RCU lock internally.
422 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
424 template <typename K, typename Func>
425 bool insert_with( const K& key, Func func )
427 return insert_with_at( head(), key, func );
430 /// Inserts data of type \p mapped_type constructed from \p args
432 Returns \p true if inserting successful, \p false otherwise.
434 The function makes RCU lock internally.
436 template <typename... Args>
437 bool emplace( Args&&... args )
439 return emplace_at( head(), std::forward<Args>(args)... );
442 /// Updates data by \p key
444 The operation performs inserting or replacing the element with lock-free manner.
446 If the \p key not found in the list, then the new item created from \p key
447 will be inserted iff \p bAllowInsert is \p true.
448 (note that in this case the \ref key_type should be constructible from type \p K).
449 Otherwise, if \p key is found, the functor \p func is called with item found.
451 The functor \p Func signature is:
454 void operator()( bool bNew, value_type& item );
458 - \p bNew - \p true if the item has been inserted, \p false otherwise
459 - \p item - the item found or inserted
461 The functor may change any fields of the \p item.second of \p mapped_type;
462 during \p func call \p item is locked so it is safe to modify the item in
463 multi-threaded environment.
465 The function applies RCU lock internally.
467 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
468 \p second is true if new item has been added or \p false if the item with \p key
471 template <typename K, typename Func>
472 std::pair<bool, bool> update( const K& key, Func func, bool bAllowInsert = true )
474 return update_at( head(), key, func, bAllowInsert );
477 template <typename K, typename Func>
478 CDS_DEPRECATED("ensure() is deprecated, use update()")
479 std::pair<bool, bool> ensure( const K& key, Func f )
481 return update( key, f, true );
485 /// Deletes \p key from the list
486 /** \anchor cds_nonintrusive_LazyKVList_rcu_erase
488 RCU \p synchronize method can be called. RCU should not be locked.
490 Returns \p true if \p key is found and has been deleted, \p false otherwise
492 template <typename K>
493 bool erase( K const& key )
495 return erase_at( head(), key, intrusive_key_comparator() );
498 /// Deletes the item from the list using \p pred predicate for searching
500 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_erase "erase(K const&)"
501 but \p pred is used for key comparing.
502 \p Less functor has the interface like \p std::less.
503 \p pred must imply the same element order as the comparator used for building the list.
505 template <typename K, typename Less>
506 bool erase_with( K const& key, Less pred )
509 return erase_at( head(), key, typename maker::template less_wrapper<Less>::type() );
512 /// Deletes \p key from the list
513 /** \anchor cds_nonintrusive_LazyKVList_rcu_erase_func
514 The function searches an item with key \p key, calls \p f functor
515 and deletes the item. If \p key is not found, the functor is not called.
517 The functor \p Func interface:
520 void operator()(value_type& val) { ... }
524 RCU \p synchronize method can be called. RCU should not be locked.
526 Returns \p true if key is found and deleted, \p false otherwise
528 template <typename K, typename Func>
529 bool erase( K const& key, Func f )
531 return erase_at( head(), key, intrusive_key_comparator(), f );
534 /// Deletes the item from the list using \p pred predicate for searching
536 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_erase_func "erase(K const&, Func)"
537 but \p pred is used for key comparing.
538 \p Less functor has the interface like \p std::less.
539 \p pred must imply the same element order as the comparator used for building the list.
541 template <typename K, typename Less, typename Func>
542 bool erase_with( K const& key, Less pred, Func f )
545 return erase_at( head(), key, typename maker::template less_wrapper<Less>::type(), f );
548 /// Extracts an item from the list
550 @anchor cds_nonintrusive_LazyKVList_rcu_extract
551 The function searches an item with key equal to \p key in the list,
552 unlinks it from the list, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
553 If \p key is not found the function returns an empty \p exempt_ptr.
555 @note The function does NOT call RCU read-side lock or synchronization,
556 and does NOT dispose the item found. It just excludes the item from the list
557 and returns a pointer to item found.
558 You should manually lock RCU before calling this function.
561 #include <cds/urcu/general_buffered.h>
562 #include <cds/container/lazy_kvlist_rcu.h>
564 typedef cds::urcu::gc< general_buffered<> > rcu;
565 typedef cds::container::LazyKVList< rcu, int, Foo > rcu_lazy_list;
567 rcu_lazy_list theList;
570 rcu_lazy_list::exempt_ptr p;
572 // first, we should lock RCU
573 rcu_lazy_list::rcu_lock sl;
575 // Now, you can apply extract function
576 // Note that you must not delete the item found inside the RCU lock
577 p = theList.extract( 10 );
579 // do something with p
583 // Outside RCU lock section we may safely release extracted pointer.
584 // release() passes the pointer to RCU reclamation cycle.
588 template <typename K>
589 exempt_ptr extract( K const& key )
591 return exempt_ptr( extract_at( head(), key, intrusive_key_comparator()));
594 /// Extracts an item from the list using \p pred predicate for searching
596 This function is the analog for \p extract(K const&).
597 The \p pred is a predicate used for key comparing.
598 \p Less has the interface like \p std::less.
599 \p pred must imply the same element order as \ref key_comparator.
601 template <typename K, typename Less>
602 exempt_ptr extract_with( K const& key, Less pred )
605 return exempt_ptr( extract_at( head(), key, typename maker::template less_wrapper<Less>::type() ));
608 /// Checks whether the list contains \p key
610 The function searches the item with key equal to \p key
611 and returns \p true if it is found, and \p false otherwise.
613 The function applies RCU lock internally.
615 template <typename Q>
616 bool contains( Q const& key ) const
618 return find_at( head(), key, intrusive_key_comparator() );
621 template <typename Q>
622 CDS_DEPRECATED("deprecated, use contains()")
623 bool find( Q const& key ) const
625 return contains( key );
629 /// Checks whether the map contains \p key using \p pred predicate for searching
631 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
632 \p Less functor has the interface like \p std::less.
633 \p Less must imply the same element order as the comparator used for building the list.
635 The function applies RCU lock internally.
637 template <typename Q, typename Less>
638 bool contains( Q const& key, Less pred ) const
641 return find_at( head(), key, typename maker::template less_wrapper<Less>::type() );
644 template <typename Q, typename Less>
645 CDS_DEPRECATED("deprecated, use contains()")
646 bool find_with( Q const& key, Less pred ) const
648 return contains( key, pred );
652 /// Finds the key \p key and performs an action with it
653 /** \anchor cds_nonintrusive_LazyKVList_rcu_find_func
654 The function searches an item with key equal to \p key and calls the functor \p f for the item found.
655 The interface of \p Func functor is:
658 void operator()( value_type& item );
661 where \p item is the item found.
663 The functor may change <tt>item.second</tt> that is reference to value of node.
664 Note that the function is only guarantee that \p item cannot be deleted during functor is executing.
665 The function does not serialize simultaneous access to the list \p item. If such access is
666 possible you must provide your own synchronization schema to exclude unsafe item modifications.
668 The function applies RCU lock internally.
670 The function returns \p true if \p key is found, \p false otherwise.
672 template <typename Q, typename Func>
673 bool find( Q const& key, Func f ) const
675 return find_at( head(), key, intrusive_key_comparator(), f );
678 /// Finds the key \p val using \p pred predicate for searching
680 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_find_func "find(Q const&, Func)"
681 but \p pred is used for key comparing.
682 \p Less functor has the interface like \p std::less.
683 \p pred must imply the same element order as the comparator used for building the list.
685 template <typename Q, typename Less, typename Func>
686 bool find_with( Q const& key, Less pred, Func f ) const
689 return find_at( head(), key, typename maker::template less_wrapper<Less>::type(), f );
692 /// Finds \p key and return the item found
693 /** \anchor cds_nonintrusive_LazyKVList_rcu_get
694 The function searches the item with \p key and returns the pointer to item found.
695 If \p key is not found it returns \p nullptr.
697 Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type.
699 RCU should be locked before call of this function.
700 Returned item is valid only while RCU is locked:
702 typedef cds::container::LazyKVList< cds::urcu::gc< cds::urcu::general_buffered<> >, int, foo, my_traits > ord_list;
707 ord_list::rcu_lock lock;
709 ord_list::value_type * pVal = theList.get( 5 );
714 // Unlock RCU by rcu_lock destructor
715 // pVal can be freed at any time after RCU has been unlocked
719 template <typename K>
720 value_type * get( K const& key ) const
722 return get_at( head(), key, intrusive_key_comparator());
725 /// Finds \p key and return the item found
727 The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_get "get(K const&)"
728 but \p pred is used for comparing the keys.
730 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
732 \p pred must imply the same element order as the comparator used for building the list.
734 template <typename K, typename Less>
735 value_type * get_with( K const& key, Less pred ) const
738 return get_at( head(), key, typename maker::template less_wrapper<Less>::type());
741 /// Checks if the list is empty
744 return base_class::empty();
747 /// Returns list's item count
749 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
750 this function always returns 0.
752 @note Even if you use real item counter and it returns 0, this fact is not mean that the list
753 is empty. To check list emptyness use \ref empty() method.
757 return base_class::size();
768 bool insert_node_at( head_type& refHead, node_type * pNode )
770 assert( pNode != nullptr );
771 scoped_node_ptr p( pNode );
773 if ( base_class::insert_at( &refHead, *p )) {
781 template <typename K>
782 bool insert_at( head_type& refHead, const K& key )
784 return insert_node_at( refHead, alloc_node( key ));
787 template <typename K, typename V>
788 bool insert_at( head_type& refHead, const K& key, const V& val )
790 return insert_node_at( refHead, alloc_node( key, val ));
793 template <typename K, typename Func>
794 bool insert_with_at( head_type& refHead, const K& key, Func f )
796 scoped_node_ptr pNode( alloc_node( key ));
798 if ( base_class::insert_at( &refHead, *pNode, [&f](node_type& node){ f( node.m_Data ); } )) {
805 template <typename... Args>
806 bool emplace_at( head_type& refHead, Args&&... args )
808 return insert_node_at( refHead, alloc_node( std::forward<Args>(args)... ));
811 template <typename K, typename Compare>
812 bool erase_at( head_type& refHead, K const& key, Compare cmp )
814 return base_class::erase_at( &refHead, key, cmp );
817 template <typename K, typename Compare, typename Func>
818 bool erase_at( head_type& refHead, K const & key, Compare cmp, Func f )
820 return base_class::erase_at( &refHead, key, cmp, [&f](node_type const & node){f( const_cast<value_type&>(node.m_Data)); });
823 template <typename K, typename Func>
824 std::pair<bool, bool> update_at( head_type& refHead, const K& key, Func f, bool bAllowInsert )
826 scoped_node_ptr pNode( alloc_node( key ));
828 std::pair<bool, bool> ret = base_class::update_at( &refHead, *pNode,
829 [&f]( bool bNew, node_type& node, node_type& ){ f( bNew, node.m_Data ); },
831 if ( ret.first && ret.second )
837 template <typename K, typename Compare>
838 node_type * extract_at( head_type& refHead, K const& key, Compare cmp )
840 return base_class::extract_at( &refHead, key, cmp );
843 template <typename K, typename Compare>
844 bool find_at( head_type& refHead, K const& key, Compare cmp ) const
846 return base_class::find_at( &refHead, key, cmp, [](node_type&, K const&) {} );
849 template <typename K, typename Compare, typename Func>
850 bool find_at( head_type& refHead, K& key, Compare cmp, Func f ) const
852 return base_class::find_at( &refHead, key, cmp, [&f]( node_type& node, K& ){ f( node.m_Data ); });
855 template <typename K, typename Compare>
856 value_type * get_at( head_type& refHead, K const& val, Compare cmp ) const
858 node_type * pNode = base_class::get_at( &refHead, val, cmp );
859 return pNode ? &pNode->m_Data : nullptr;
865 }} // namespace cds::container
867 #endif // #ifndef CDSLIB_CONTAINER_LAZY_KVLIST_RCU_H