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_ITERABLE_LIST_H
32 #define CDSLIB_CONTAINER_IMPL_ITERABLE_LIST_H
34 #include <cds/container/details/make_iterable_list.h>
37 namespace cds { namespace container {
39 /// Iterable ordered list
40 /** @ingroup cds_nonintrusive_list
41 \anchor cds_nonintrusive_IterableList_gc
43 This lock-free list implementation supports thread-safe iterators.
45 Usually, ordered single-linked list is used as a building block for the hash table implementation.
46 Iterable list is suitable for almost append-only hash table because the list doesn't delete
47 its internal node when erasing a key but it is marked them as empty to be reused in the future.
48 However, plenty of empty nodes degrades performance.
50 The complexity of searching is <tt>O(N)</tt>.
53 - \p GC - Garbage collector used.
54 - \p T - type to be stored in the list.
55 - \p Traits - type traits, default is \p iterable_list::traits.
57 Unlike standard container, this implementation does not divide type \p T into key and value part and
58 may be used as a main building block for hash set algorithms.
59 The key is a function (or a part) of type \p T, and this function is specified by <tt>Traits::compare</tt> functor
60 or <tt>Traits::less</tt> predicate.
62 \p IterableKVList is a key-value version of iterable non-intrusive list that is closer to the C++ std library approach.
64 It is possible to declare option-based list with cds::container::iterable_list::make_traits metafunction istead of \p Traits template
65 argument. For example, the following traits-based declaration of gc::HP iterable list
67 #include <cds/container/iterable_list_hp.h>
68 // Declare comparator for the item
70 int operator ()( int i1, int i2 )
77 struct my_traits: public cds::container::iterable_list::traits
79 typedef my_compare compare;
82 // Declare traits-based list
83 typedef cds::container::IterableList< cds::gc::HP, int, my_traits > traits_based_list;
86 is equivalent for the following option-based list
88 #include <cds/container/iterable_list_hp.h>
90 // my_compare is the same
92 // Declare option-based list
93 typedef cds::container::IterableList< cds::gc::HP, int,
94 typename cds::container::iterable_list::make_traits<
95 cds::container::opt::compare< my_compare > // item comparator option
101 There are different specializations of this template for each garbage collecting schema used.
102 You should include appropriate .h-file depending on GC you are using:
103 - for gc::HP: \code #include <cds/container/iterable_list_hp.h> \endcode
104 - for gc::DHP: \code #include <cds/container/iterable_list_dhp.h> \endcode
105 - for \ref cds_urcu_desc "RCU": \code #include <cds/container/iterable_list_rcu.h> \endcode
110 #ifdef CDS_DOXYGEN_INVOKED
111 typename Traits = iterable_list::traits
117 #ifdef CDS_DOXYGEN_INVOKED
118 protected intrusive::IterableList< GC, T, Traits >
120 protected details::make_iterable_list< GC, T, Traits >::type
124 typedef details::make_iterable_list< GC, T, Traits > maker;
125 typedef typename maker::type base_class;
129 typedef T value_type; ///< Type of value stored in the list
130 typedef Traits traits; ///< List traits
132 typedef typename base_class::gc gc; ///< Garbage collector used
133 typedef typename base_class::back_off back_off; ///< Back-off strategy used
134 typedef typename maker::data_allocator_type allocator_type; ///< Allocator type used for allocate/deallocate data
135 typedef typename base_class::item_counter item_counter; ///< Item counting policy used
136 typedef typename maker::key_comparator key_comparator; ///< key comparison functor
137 typedef typename base_class::memory_model memory_model; ///< Memory ordering. See \p cds::opt::memory_model option
138 typedef typename base_class::stat stat; ///< Internal statistics
140 static CDS_CONSTEXPR const size_t c_nHazardPtrCount = base_class::c_nHazardPtrCount; ///< Count of hazard pointer required for the algorithm
144 typedef typename base_class::value_type node_type;
145 typedef typename maker::cxx_data_allocator cxx_data_allocator;
146 typedef typename maker::data_disposer data_disposer;
147 typedef typename base_class::atomic_node_ptr head_type;
152 typedef typename base_class::guarded_ptr guarded_ptr;
156 template <bool IsConst>
157 class iterator_type: protected base_class::template iterator_type<IsConst>
159 typedef typename base_class::template iterator_type<IsConst> iterator_base;
160 friend class IterableList;
162 iterator_type( head_type const& pNode )
163 : iterator_base( pNode )
166 iterator_type( iterator_base it )
167 : iterator_base( it )
171 typedef typename iterator_base::value_ptr value_ptr;
172 typedef typename iterator_base::value_ref value_ref;
177 iterator_type( iterator_type const& src )
178 : iterator_base( src )
181 value_ptr operator ->() const
183 return iterator_base::operator ->();
186 value_ref operator *() const
188 return iterator_base::operator *();
192 iterator_type& operator ++()
194 iterator_base::operator ++();
199 bool operator ==(iterator_type<C> const& i ) const
201 return iterator_base::operator ==(i);
204 bool operator !=(iterator_type<C> const& i ) const
206 return iterator_base::operator !=(i);
212 ///@name Thread-safe forward iterators
216 The forward iterator for iterable list has some features:
217 - it has no post-increment operator
218 - to protect the value, the iterator contains a GC-specific guard.
219 For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard"
220 may be thrown if the limit of guard count per thread is exceeded.
221 - The iterator cannot be moved across thread boundary since it contains thread-private GC's guard.
222 - Iterator is thread-safe: even if an element the iterator points to is removed, the iterator stays valid because
223 it contains the guard keeping the value from to be recycled.
225 The iterator interface:
229 // Default constructor
233 iterator( iterator const& src );
235 // Dereference operator
236 value_type * operator ->() const;
238 // Dereference operator
239 value_type& operator *() const;
241 // Preincrement operator
242 iterator& operator ++();
244 // Assignment operator
245 iterator& operator = (iterator const& src);
247 // Equality operators
248 bool operator ==(iterator const& i ) const;
249 bool operator !=(iterator const& i ) const;
253 @note For two iterators pointed to the same element the value can be different;
257 assert( &(*it1) == &(*it2) );
259 can throw assertion. The point is that the iterator stores the value of element which can be modified later by other thread.
260 The guard inside the iterator prevents recycling that value so the iterator's value remains valid even after such changing.
261 Other iterator can observe modified value of the element.
263 typedef iterator_type<false> iterator;
265 /// Const forward iterator
267 For iterator's features and requirements see \ref iterator
269 typedef iterator_type<true> const_iterator;
271 /// Returns a forward iterator addressing the first element in a list
273 For empty list \code begin() == end() \endcode
277 return iterator( head() );
280 /// Returns an iterator that addresses the location succeeding the last element in a list
282 Do not use the value returned by <tt>end</tt> function to access any item.
283 Internally, <tt>end</tt> returning value equals to \p nullptr.
285 The returned value can be used only to control reaching the end of the list.
286 For empty list \code begin() == end() \endcode
293 /// Returns a forward const iterator addressing the first element in a list
294 const_iterator begin() const
296 return const_iterator( head() );
299 /// Returns a forward const iterator addressing the first element in a list
300 const_iterator cbegin() const
302 return const_iterator( head() );
305 /// Returns an const iterator that addresses the location succeeding the last element in a list
306 const_iterator end() const
308 return const_iterator();
311 /// Returns an const iterator that addresses the location succeeding the last element in a list
312 const_iterator cend() const
314 return const_iterator();
319 /// Default constructor
321 Initialize empty list
327 template <typename Stat, typename = std::enable_if<std::is_same<stat, iterable_list::wrapped_stat<Stat>>::value >>
328 explicit IterableList( Stat& st )
342 The function creates a node with copy of \p val value
343 and then inserts the node created into the list.
345 The type \p Q should contain least the complete key of the node.
346 The object of \ref value_type should be constructible from \p val of type \p Q.
347 In trivial case, \p Q is equal to \ref value_type.
349 Returns \p true if inserting successful, \p false otherwise.
351 template <typename Q>
352 bool insert( Q const& val )
354 return insert_at( head(), val );
359 This function inserts new node with default-constructed value and then it calls
360 \p func functor with signature
362 void func( value_type& data );
365 The argument \p data of user-defined functor \p func is the reference
366 to the list's item inserted. User-defined functor \p func should guarantee that during changing
367 item's value no any other changes could be made on this list's item by concurrent threads.
368 The user-defined functor is called only if inserting is success.
370 The type \p Q should contain the complete key of the node.
371 The object of \p value_type should be constructible from \p key of type \p Q.
373 The function allows to split creating of new item into two part:
374 - create item from \p key with initializing key-fields only;
375 - insert new item into the list;
376 - if inserting is successful, initialize non-key fields of item by calling \p func functor
378 The method can be useful if complete initialization of object of \p value_type is heavyweight and
379 it is preferable that the initialization should be completed only if inserting is successful.
381 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
383 template <typename Q, typename Func>
384 bool insert( Q const& key, Func func )
386 return insert_at( head(), key, func );
389 /// Updates data by \p key
391 The operation performs inserting or replacing the element with lock-free manner.
393 If the \p key not found in the list, then the new item created from \p key
394 will be inserted iff \p bAllowInsert is \p true.
395 Otherwise, if \p key is found, the functor \p func is called with item found.
397 The functor \p func is called after inserting or replacing, it signature is:
399 void func( value_type& val, value_type * old );
402 - \p val - a new data constructed from \p key
403 - \p old - old value that will be retired. If new item has been inserted then \p old is \p nullptr.
405 The functor may change non-key fields of \p val; however, \p func must guarantee
406 that during changing no any other modifications could be made on this item by concurrent threads.
408 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successful,
409 \p second is true if new item has been added or \p false if the item with such \p key
412 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
414 template <typename Q, typename Func>
415 std::pair<bool, bool> update( Q const& key, Func func, bool bAllowInsert = true )
417 return update_at( head(), key, func, bAllowInsert );
422 The operation performs inserting or updating data with lock-free manner.
424 If the item \p val is not found in the list, then \p val is inserted
425 iff \p bInsert is \p true.
426 Otherwise, the current element is changed to \p val, the old element will be retired later.
428 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
429 \p second is \p true if \p val has been added or \p false if the item with that key
432 template <typename Q>
433 std::pair<bool, bool> upsert( Q const& key, bool bInsert = true )
435 return update_at( head(), key, []( value_type&, value_type* ) {}, bInsert );
438 /// Inserts data of type \p value_type constructed with <tt>std::forward<Args>(args)...</tt>
440 Returns \p true if inserting successful, \p false otherwise.
442 template <typename... Args>
443 bool emplace( Args&&... args )
445 return emplace_at( head(), std::forward<Args>(args)... );
448 /// Delete \p key from the list
450 Since the key of IterableList's item type \p value_type is not explicitly specified,
451 template parameter \p Q sould contain the complete key to search in the list.
452 The list item comparator should be able to compare the type \p value_type
455 Return \p true if key is found and deleted, \p false otherwise
457 template <typename Q>
458 bool erase( Q const& key )
460 return erase_at( head(), key, key_comparator(), [](value_type const&){} );
463 /// Deletes the item from the list using \p pred predicate for searching
465 The function is an analog of \p erase(Q const&) but \p pred is used for key comparing.
466 \p Less functor has the interface like \p std::less.
467 \p pred must imply the same element order as the comparator used for building the list.
469 template <typename Q, typename Less>
470 bool erase_with( Q const& key, Less pred )
473 return erase_at( head(), key, typename maker::template less_wrapper<Less>::type(), [](value_type const&){} );
476 /// Deletes \p key from the list
478 The function searches an item with key \p key, calls \p f functor with item found
479 and deletes it. If \p key is not found, the functor is not called.
481 The functor \p Func interface:
484 void operator()(const value_type& val) { ... }
488 Since the key of IterableList's item type \p value_type is not explicitly specified,
489 template parameter \p Q should contain the complete key to search in the list.
490 The list item comparator should be able to compare the type \p value_type of list item
493 Return \p true if key is found and deleted, \p false otherwise
495 template <typename Q, typename Func>
496 bool erase( Q const& key, Func f )
498 return erase_at( head(), key, key_comparator(), f );
501 /// Deletes the item from the list using \p pred predicate for searching
503 The function is an analog of \p erase(Q const&, Func) but \p pred is used for key comparing.
504 \p Less functor has the interface like \p std::less.
505 \p pred must imply the same element order as the comparator used for building the list.
507 template <typename Q, typename Less, typename Func>
508 bool erase_with( Q const& key, Less pred, Func f )
511 return erase_at( head(), key, typename maker::template less_wrapper<Less>::type(), f );
514 /// Extracts the item from the list with specified \p key
516 The function searches an item with key equal to \p key,
517 unlinks it from the list, and returns it as \p guarded_ptr.
518 If \p key is not found the function returns an empty guarded pointer.
520 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
522 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
526 typedef cds::container::IterableList< cds::gc::HP, foo, my_traits > ord_list;
530 ord_list::guarded_ptr gp(theList.extract( 5 ));
535 // Destructor of gp releases internal HP guard and frees the item
539 template <typename Q>
540 guarded_ptr extract( Q const& key )
543 extract_at( head(), gp.guard(), key, key_comparator() );
547 /// Extracts the item from the list with comparing functor \p pred
549 The function is an analog of \p extract(Q const&) but \p pred predicate is used for key comparing.
551 \p Less functor has the semantics like \p std::less but it should accept arguments
552 of type \p value_type and \p Q in any order.
553 \p pred must imply the same element order as the comparator used for building the list.
555 template <typename Q, typename Less>
556 guarded_ptr extract_with( Q const& key, Less pred )
560 extract_at( head(), gp.guard(), key, typename maker::template less_wrapper<Less>::type() );
564 /// Checks whether the list contains \p key
566 The function searches the item with key equal to \p key
567 and returns \p true if it is found, and \p false otherwise.
569 template <typename Q>
570 bool contains( Q const& key ) const
572 return find_at( head(), key, key_comparator() );
575 /// Checks whether the list contains \p key using \p pred predicate for searching
577 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
578 \p Less functor has the interface like \p std::less.
579 \p pred must imply the same element order as the comparator used for building the list.
581 template <typename Q, typename Less>
582 bool contains( Q const& key, Less pred ) const
585 return find_at( head(), key, typename maker::template less_wrapper<Less>::type() );
588 /// Finds \p key and perform an action with it
590 The function searches an item with key equal to \p key and calls the functor \p f for the item found.
591 The interface of \p Func functor is:
594 void operator()( value_type& item, Q& key );
597 where \p item is the item found, \p key is the <tt>find</tt> function argument.
599 The functor may change non-key fields of \p item. Note that the function is only guarantee
600 that \p item cannot be deleted during functor is executing.
601 The function does not serialize simultaneous access to the list \p item. If such access is
602 possible you must provide your own synchronization schema to exclude unsafe item modifications.
604 The function returns \p true if \p key is found, \p false otherwise.
606 template <typename Q, typename Func>
607 bool find( Q& key, Func f ) const
609 return find_at( head(), key, key_comparator(), f );
612 template <typename Q, typename Func>
613 bool find( Q const& key, Func f ) const
615 return find_at( head(), key, key_comparator(), f );
619 /// Finds \p key in the list and returns iterator pointed to the item found
621 If \p key is not found the function returns \p end().
623 template <typename Q>
624 iterator find( Q& key ) const
626 return find_iterator_at( head(), key, key_comparator());
629 template <typename Q>
630 iterator find( Q const& key ) const
632 return find_iterator_at( head(), key, key_comparator() );
636 /// Finds \p key using \p pred predicate for searching
638 The function is an analog of \p find(Q&, Func) but \p pred is used for key comparing.
639 \p Less functor has the interface like \p std::less.
640 \p pred must imply the same element order as the comparator used for building the list.
642 template <typename Q, typename Less, typename Func>
643 bool find_with( Q& key, Less pred, Func f ) const
646 return find_at( head(), key, typename maker::template less_wrapper<Less>::type(), f );
649 template <typename Q, typename Less, typename Func>
650 bool find_with( Q const& key, Less pred, Func f ) const
653 return find_at( head(), key, typename maker::template less_wrapper<Less>::type(), f );
657 /// Finds \p key in the list using \p pred predicate for searching and returns iterator pointed to the item found
659 The function is an analog of \p find(Q&) but \p pred is used for key comparing.
660 \p Less functor has the interface like \p std::less.
661 \p pred must imply the same element order as the comparator used for building the list.
663 If \p key is not found the function returns \p end().
665 template <typename Q, typename Less>
666 iterator find_with( Q& key, Less pred ) const
669 return find_iterator_at( head(), key, cds::opt::details::make_comparator_from_less<Less>());
672 template <typename Q, typename Less>
673 iterator find_with( Q const& key, Less pred ) const
676 return find_iterator_at( head(), key, cds::opt::details::make_comparator_from_less<Less>());
680 /// Finds \p key and return the item found
681 /** \anchor cds_nonintrusive_MichaelList_hp_get
682 The function searches the item with key equal to \p key
683 and returns it as \p guarded_ptr.
684 If \p key is not found the function returns an empty guarded pointer.
686 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
690 typedef cds::container::MichaelList< cds::gc::HP, foo, my_traits > ord_list;
694 ord_list::guarded_ptr gp(theList.get( 5 ));
699 // Destructor of guarded_ptr releases internal HP guard and frees the item
703 Note the compare functor specified for class \p Traits template parameter
704 should accept a parameter of type \p Q that can be not the same as \p value_type.
706 template <typename Q>
707 guarded_ptr get( Q const& key ) const
710 get_at( head(), gp.guard(), key, key_comparator() );
714 /// Finds \p key and return the item found
716 The function is an analog of \ref cds_nonintrusive_MichaelList_hp_get "get( Q const&)"
717 but \p pred is used for comparing the keys.
719 \p Less functor has the semantics like \p std::less but should accept arguments of type \p value_type and \p Q
721 \p pred must imply the same element order as the comparator used for building the list.
723 template <typename Q, typename Less>
724 guarded_ptr get_with( Q const& key, Less pred ) const
728 get_at( head(), gp.guard(), key, typename maker::template less_wrapper<Less>::type() );
732 /// Checks if the list is empty
734 Emptiness is checked by item counting: if item count is zero then the set is empty.
735 Thus, if you need to use \p %empty() you should provide appropriate (non-empty) \p iterable_list::traits::item_counter
740 return base_class::empty();
743 /// Returns list's item count
745 The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
746 this function always returns 0.
750 return base_class::size();
753 /// Clears the list (thread safe, not atomic)
759 /// Returns const reference to internal statistics
760 stat const& statistics() const
762 return base_class::statistics();
767 template <typename Q>
768 static value_type* alloc_data( Q const& v )
770 return cxx_data_allocator().New( v );
773 template <typename... Args>
774 static value_type* alloc_data( Args&&... args )
776 return cxx_data_allocator().MoveNew( std::forward<Args>(args)... );
779 static void free_data( value_type* pData )
781 cxx_data_allocator().Delete( pData );
784 typedef std::unique_ptr< value_type, data_disposer > scoped_data_ptr;
788 return base_class::m_pHead;
791 head_type const& head() const
793 return base_class::m_pHead;
799 bool insert_node( value_type * pData )
801 return insert_node_at( head(), pData );
804 bool insert_node_at( head_type& refHead, value_type* pData )
807 scoped_data_ptr p( pData );
808 if ( base_class::insert_at( refHead, *pData )) {
816 template <typename Q>
817 bool insert_at( head_type& refHead, Q const& val )
819 return insert_node_at( refHead, alloc_data( val ));
822 template <typename Q, typename Func>
823 bool insert_at( head_type& refHead, Q const& key, Func f )
825 scoped_data_ptr pNode( alloc_data( key ));
827 if ( base_class::insert_at( refHead, *pNode, f )) {
834 template <typename... Args>
835 bool emplace_at( head_type& refHead, Args&&... args )
837 return insert_node_at( refHead, alloc_data( std::forward<Args>(args) ... ));
840 template <typename Q, typename Func>
841 std::pair<bool, bool> update_at( head_type& refHead, Q const& key, Func f, bool bAllowInsert )
843 scoped_data_ptr pData( alloc_data( key ) );
845 std::pair<bool, bool> ret = base_class::update_at( refHead, *pData, f, bAllowInsert );
852 template <typename Q, typename Compare, typename Func>
853 bool erase_at( head_type& refHead, Q const& key, Compare cmp, Func f )
855 return base_class::erase_at( refHead, key, cmp, f );
858 template <typename Q, typename Compare>
859 bool extract_at( head_type& refHead, typename guarded_ptr::native_guard& guard, Q const& key, Compare cmp )
861 return base_class::extract_at( refHead, guard, key, cmp );
864 template <typename Q, typename Compare>
865 bool find_at( head_type const& refHead, Q const& key, Compare cmp ) const
867 return base_class::find_at( refHead, key, cmp );
870 template <typename Q, typename Compare, typename Func>
871 bool find_at( head_type const& refHead, Q& val, Compare cmp, Func f ) const
873 return base_class::find_at( refHead, val, cmp, f );
876 template <typename Q, typename Compare>
877 iterator find_iterator_at( head_type const& refHead, Q const& key, Compare cmp ) const
879 return iterator( base_class::find_iterator_at( refHead, key, cmp ));
882 template <typename Q, typename Compare>
883 bool get_at( head_type const& refHead, typename guarded_ptr::native_guard& guard, Q const& key, Compare cmp ) const
885 return base_class::get_at( refHead, guard, key, cmp );
891 }} // namespace cds::container
893 #endif // #ifndef CDSLIB_CONTAINER_IMPL_ITERABLE_LIST_H