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_SPLIT_LIST_SET_H
32 #define CDSLIB_CONTAINER_SPLIT_LIST_SET_H
34 #include <cds/intrusive/split_list.h>
35 #include <cds/container/details/make_split_list_set.h>
36 #include <cds/container/details/guarded_ptr_cast.h>
38 namespace cds { namespace container {
40 /// Split-ordered list set
41 /** @ingroup cds_nonintrusive_set
42 \anchor cds_nonintrusive_SplitListSet_hp
44 Hash table implementation based on split-ordered list algorithm discovered by Ori Shalev and Nir Shavit, see
45 - [2003] Ori Shalev, Nir Shavit "Split-Ordered Lists - Lock-free Resizable Hash Tables"
46 - [2008] Nir Shavit "The Art of Multiprocessor Programming"
48 See \p intrusive::SplitListSet for a brief description of the split-list algorithm.
51 - \p GC - Garbage collector used
52 - \p T - type to be stored in the split-list.
53 - \p Traits - type traits, default is \p split_list::traits. Instead of declaring \p split_list::traits -based
54 struct you may apply option-based notation with \p split_list::make_traits metafunction.
56 There are the specializations:
57 - for \ref cds_urcu_desc "RCU" - declared in <tt>cd/container/split_list_set_rcu.h</tt>,
58 see \ref cds_nonintrusive_SplitListSet_rcu "SplitListSet<RCU>".
59 - for \ref cds::gc::nogc declared in <tt>cds/container/split_list_set_nogc.h</tt>,
60 see \ref cds_nonintrusive_SplitListSet_nogc "SplitListSet<gc::nogc>".
64 You should decide what garbage collector you want, and what ordered list you want to use as a base. Split-ordered list
65 is original data structure based on an ordered list.
67 Suppose, you want construct split-list set based on \p gc::DHP GC
68 and \p LazyList as ordered list implementation. So, you beginning your program with following include:
70 #include <cds/container/lazy_list_dhp.h>
71 #include <cds/container/split_list_set.h>
73 namespace cc = cds::container;
75 // The data belonged to split-ordered list
77 int nKey; // key field
78 std::string strValue ; // value field
81 The inclusion order is important: first, include header for ordered-list implementation (for this example, <tt>cds/container/lazy_list_dhp.h</tt>),
82 then the header for split-list set <tt>cds/container/split_list_set.h</tt>.
84 Now, you should declare traits for split-list set. The main parts of traits are a hash functor for the set and a comparing functor for ordered list.
85 Note that we define several function in <tt>foo_hash</tt> and <tt>foo_less</tt> functors for different argument types since we want call our \p %SplitListSet
86 object by the key of type <tt>int</tt> and by the value of type <tt>foo</tt>.
88 The second attention: instead of using \p %LazyList in \p %SplitListSet traits we use a tag \p cds::contaner::lazy_list_tag for the lazy list.
89 The split-list requires significant support from underlying ordered list class and it is not good idea to dive you
90 into deep implementation details of split-list and ordered list interrelations. The tag paradigm simplifies split-list interface.
95 size_t operator()( int key ) const { return std::hash( key ) ; }
96 size_t operator()( foo const& item ) const { return std::hash( item.nKey ) ; }
101 bool operator()(int i, foo const& f ) const { return i < f.nKey ; }
102 bool operator()(foo const& f, int i ) const { return f.nKey < i ; }
103 bool operator()(foo const& f1, foo const& f2) const { return f1.nKey < f2.nKey; }
106 // SplitListSet traits
107 struct foo_set_traits: public cc::split_list::traits
109 typedef cc::lazy_list_tag ordered_list; // what type of ordered list we want to use
110 typedef foo_hash hash; // hash functor for our data stored in split-list set
112 // Type traits for our LazyList class
113 struct ordered_list_traits: public cc::lazy_list::traits
115 typedef foo_less less ; // use our foo_less as comparator to order list nodes
120 Now you are ready to declare our set class based on \p %SplitListSet:
122 typedef cc::SplitListSet< cds::gc::DHP, foo, foo_set_traits > foo_set;
125 You may use the modern option-based declaration instead of classic traits-based one:
127 typedef cc::SplitListSet<
128 cs::gc::DHP // GC used
129 ,foo // type of data stored
130 ,cc::split_list::make_traits< // metafunction to build split-list traits
131 cc::split_list::ordered_list<cc::lazy_list_tag> // tag for underlying ordered list implementation
132 ,cc::opt::hash< foo_hash > // hash functor
133 ,cc::split_list::ordered_list_traits< // ordered list traits desired
134 cc::lazy_list::make_traits< // metafunction to build lazy list traits
135 cc::opt::less< foo_less > // less-based compare functor
141 In case of option-based declaration using split_list::make_traits metafunction
142 the struct \p foo_set_traits is not required.
144 Now, the set of type \p foo_set is ready to use in your program.
146 Note that in this example we show only mandatory \p traits parts, optional ones is the default and they are inherited
147 from \p cds::container::split_list::traits.
148 There are many other options for deep tuning the split-list and ordered-list containers.
153 #ifdef CDS_DOXYGEN_INVOKED
154 class Traits = split_list::traits
160 #ifdef CDS_DOXYGEN_INVOKED
161 protected intrusive::SplitListSet<GC, typename Traits::ordered_list, Traits>
163 protected details::make_split_list_set< GC, T, typename Traits::ordered_list, split_list::details::wrap_set_traits<T, Traits> >::type
168 typedef details::make_split_list_set< GC, T, typename Traits::ordered_list, split_list::details::wrap_set_traits<T, Traits> > maker;
169 typedef typename maker::type base_class;
173 typedef GC gc; ///< Garbage collector
174 typedef T value_type; ///< Type of vlue to be stored in split-list
175 typedef Traits traits; ///< \p Traits template argument
176 typedef typename maker::ordered_list ordered_list; ///< Underlying ordered list class
177 typedef typename base_class::key_comparator key_comparator; ///< key compare functor
179 /// Hash functor for \p %value_type and all its derivatives that you use
180 typedef typename base_class::hash hash;
181 typedef typename base_class::item_counter item_counter; ///< Item counter type
182 typedef typename base_class::stat stat; ///< Internal statistics
184 /// Count of hazard pointer required
185 static CDS_CONSTEXPR const size_t c_nHazardPtrCount = base_class::c_nHazardPtrCount;
189 typedef typename maker::cxx_node_allocator cxx_node_allocator;
190 typedef typename maker::node_type node_type;
195 typedef typename gc::template guarded_ptr< node_type, value_type, details::guarded_ptr_cast_set<node_type, value_type> > guarded_ptr;
199 template <bool IsConst>
200 class iterator_type: protected base_class::template iterator_type<IsConst>
202 typedef typename base_class::template iterator_type<IsConst> iterator_base_class;
203 friend class SplitListSet;
206 /// Value pointer type (const for const iterator)
207 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
208 /// Value reference type (const for const iterator)
209 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
217 iterator_type( iterator_type const& src )
218 : iterator_base_class( src )
222 explicit iterator_type( iterator_base_class const& src )
223 : iterator_base_class( src )
227 /// Dereference operator
228 value_ptr operator ->() const
230 return &(iterator_base_class::operator->()->m_Value);
233 /// Dereference operator
234 value_ref operator *() const
236 return iterator_base_class::operator*().m_Value;
240 iterator_type& operator ++()
242 iterator_base_class::operator++();
246 /// Assignment operator
247 iterator_type& operator = (iterator_type const& src)
249 iterator_base_class::operator=(src);
253 /// Equality operator
255 bool operator ==(iterator_type<C> const& i ) const
257 return iterator_base_class::operator==(i);
260 /// Equality operator
262 bool operator !=(iterator_type<C> const& i ) const
264 return iterator_base_class::operator!=(i);
270 /// Initializes split-ordered list of default capacity
272 The default capacity is defined in bucket table constructor.
273 See \p intrusive::split_list::expandable_bucket_table, \p intrusive::split_list::static_bucket_table
274 which selects by \p split_list::dynamic_bucket_table option.
280 /// Initializes split-ordered list
282 size_t nItemCount ///< estimated average of item count
283 , size_t nLoadFactor = 1 ///< the load factor - average item count per bucket. Small integer up to 8, default is 1.
285 : base_class( nItemCount, nLoadFactor )
289 ///@name Forward iterators (only for debugging purpose)
293 The forward iterator for a split-list has the following features:
294 - it has no post-increment operator
295 - it depends on underlying ordered list iterator
296 - The iterator object cannot be moved across thread boundary because it contains GC's guard that is thread-private GC data.
297 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
298 deleting operations it is no guarantee that you iterate all item in the split-list.
299 Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
301 @warning Use this iterator on the concurrent container for debugging purpose only.
303 The iterator interface:
307 // Default constructor
311 iterator( iterator const& src );
313 // Dereference operator
314 value_type * operator ->() const;
316 // Dereference operator
317 value_type& operator *() const;
319 // Preincrement operator
320 iterator& operator ++();
322 // Assignment operator
323 iterator& operator = (iterator const& src);
325 // Equality operators
326 bool operator ==(iterator const& i ) const;
327 bool operator !=(iterator const& i ) const;
331 typedef iterator_type<false> iterator;
333 /// Const forward iterator
334 typedef iterator_type<true> const_iterator;
336 /// Returns a forward iterator addressing the first element in a set
338 For empty set \code begin() == end() \endcode
342 return iterator( base_class::begin());
345 /// Returns an iterator that addresses the location succeeding the last element in a set
347 Do not use the value returned by <tt>end</tt> function to access any item.
348 The returned value can be used only to control reaching the end of the set.
349 For empty set \code begin() == end() \endcode
353 return iterator( base_class::end());
356 /// Returns a forward const iterator addressing the first element in a set
357 const_iterator begin() const
361 /// Returns a forward const iterator addressing the first element in a set
362 const_iterator cbegin() const
364 return const_iterator( base_class::cbegin());
367 /// Returns an const iterator that addresses the location succeeding the last element in a set
368 const_iterator end() const
372 /// Returns an const iterator that addresses the location succeeding the last element in a set
373 const_iterator cend() const
375 return const_iterator( base_class::cend());
382 The function creates a node with copy of \p val value
383 and then inserts the node created into the set.
385 The type \p Q should contain as minimum the complete key for the node.
386 The object of \ref value_type should be constructible from a value of type \p Q.
387 In trivial case, \p Q is equal to \ref value_type.
389 Returns \p true if \p val is inserted into the set, \p false otherwise.
391 template <typename Q>
392 bool insert( Q&& val )
394 return insert_node( alloc_node( std::forward<Q>( val )));
399 The function allows to split creating of new item into two part:
400 - create item with key only
401 - insert new item into the set
402 - if inserting is success, calls \p f functor to initialize value-field of \p val.
404 The functor signature is:
406 void func( value_type& val );
408 where \p val is the item inserted.
410 The user-defined functor is called only if the inserting is success.
412 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
413 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
416 template <typename Q, typename Func>
417 bool insert( Q&& val, Func f )
419 scoped_node_ptr pNode( alloc_node( std::forward<Q>( val )));
421 if ( base_class::insert( *pNode, [&f](node_type& node) { f( node.m_Value ) ; } )) {
428 /// Inserts data of type \p value_type created from \p args
430 Returns \p true if inserting successful, \p false otherwise.
432 template <typename... Args>
433 bool emplace( Args&&... args )
435 return insert_node( alloc_node( std::forward<Args>(args)...));
438 /// Inserts or updates the node (only for \p IterableList -based set)
440 The operation performs inserting or changing data with lock-free manner.
442 If the item \p val is not found in the set, then \p val is inserted iff \p bAllowInsert is \p true.
443 Otherwise, the current element is changed to \p val, the old element will be retired later.
445 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
446 \p second is \p true if \p val has been added or \p false if the item with that key
449 template <typename Q>
450 #ifdef CDS_DOXYGEN_INVOKED
451 std::pair<bool, bool>
453 typename std::enable_if<
454 std::is_same< Q, Q>::value && is_iterable_list< ordered_list >::value,
455 std::pair<bool, bool>
458 upsert( Q&& val, bool bAllowInsert = true )
460 scoped_node_ptr pNode( alloc_node( std::forward<Q>( val )));
462 auto bRet = base_class::upsert( *pNode, bAllowInsert );
471 The operation performs inserting or changing data with lock-free manner.
473 If \p key is not found in the set, then \p key is inserted iff \p bAllowInsert is \p true.
474 Otherwise, the functor \p func is called with item found.
476 The functor \p func signature depends of ordered list:
478 <b>for \p MichaelList, \p LazyList</b>
481 void operator()( bool bNew, value_type& item, Q const& val );
485 - \p bNew - \p true if the item has been inserted, \p false otherwise
486 - \p item - item of the set
487 - \p val - argument \p val passed into the \p %update() function
489 The functor may change non-key fields of the \p item.
491 <b>for \p IterableList</b>
493 void func( value_type& val, value_type * old );
496 - \p val - a new data constructed from \p key
497 - \p old - old value that will be retired. If new item has been inserted then \p old is \p nullptr.
499 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successful,
500 \p second is true if new item has been added or \p false if the item with \p key
501 already is in the set.
503 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" and \ref cds_nonintrusive_IterableList_gc "IterableList"
504 as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
505 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
508 template <typename Q, typename Func>
509 #ifdef CDS_DOXYGEN_INVOKED
510 std::pair<bool, bool>
512 typename std::enable_if<
513 std::is_same<Q, Q>::value && !is_iterable_list<ordered_list>::value,
514 std::pair<bool, bool>
517 update( Q&& val, Func func, bool bAllowInsert = true )
519 scoped_node_ptr pNode( alloc_node( std::forward<Q>( val )));
521 auto bRet = base_class::update( *pNode,
522 [&func, &val]( bool bNew, node_type& item, node_type const& /*val*/ ) {
523 func( bNew, item.m_Value, val );
526 if ( bRet.first && bRet.second )
531 template <typename Q, typename Func>
532 typename std::enable_if<
533 std::is_same<Q, Q>::value && is_iterable_list<ordered_list>::value,
534 std::pair<bool, bool>
536 update( Q&& val, Func func, bool bAllowInsert = true )
538 scoped_node_ptr pNode( alloc_node( std::forward<Q>( val )));
540 auto bRet = base_class::update( *pNode,
541 [&func]( node_type& item, node_type* old ) {
542 func( item.m_Value, old ? &old->m_Value : nullptr );
552 template <typename Q, typename Func>
553 CDS_DEPRECATED("ensure() is deprecated, use update()")
554 std::pair<bool, bool> ensure( Q const& val, Func func )
556 return update( val, func, true );
560 /// Deletes \p key from the set
561 /** \anchor cds_nonintrusive_SplitListSet_erase_val
563 The item comparator should be able to compare the values of type \p value_type
566 Return \p true if key is found and deleted, \p false otherwise
568 template <typename Q>
569 bool erase( Q const& key )
571 return base_class::erase( key );
574 /// Deletes the item from the set using \p pred predicate for searching
576 The function is an analog of \ref cds_nonintrusive_SplitListSet_erase_val "erase(Q const&)"
577 but \p pred is used for key comparing.
578 \p Less functor has the interface like \p std::less.
579 \p Less must imply the same element order as the comparator used for building the set.
581 template <typename Q, typename Less>
582 bool erase_with( Q const& key, Less pred )
585 return base_class::erase_with( key, typename maker::template predicate_wrapper<Less>::type());
588 /// Deletes \p key from the set
589 /** \anchor cds_nonintrusive_SplitListSet_erase_func
591 The function searches an item with key \p key, calls \p f functor
592 and deletes the item. If \p key is not found, the functor is not called.
594 The functor \p Func interface:
597 void operator()(value_type const& val);
601 Since the key of split-list \p value_type is not explicitly specified,
602 template parameter \p Q defines the key type searching in the list.
603 The list item comparator should be able to compare the values of the type \p value_type
606 Return \p true if key is found and deleted, \p false otherwise
608 template <typename Q, typename Func>
609 bool erase( Q const& key, Func f )
611 return base_class::erase( key, [&f](node_type& node) { f( node.m_Value ); } );
614 /// Deletes the item from the set using \p pred predicate for searching
616 The function is an analog of \ref cds_nonintrusive_SplitListSet_erase_func "erase(Q const&, Func)"
617 but \p pred is used for key comparing.
618 \p Less functor has the interface like \p std::less.
619 \p Less must imply the same element order as the comparator used for building the set.
621 template <typename Q, typename Less, typename Func>
622 bool erase_with( Q const& key, Less pred, Func f )
625 return base_class::erase_with( key, typename maker::template predicate_wrapper<Less>::type(),
626 [&f](node_type& node) { f( node.m_Value ); } );
629 /// Deletes the item pointed by iterator \p iter (only for \p IterableList based set)
631 Returns \p true if the operation is successful, \p false otherwise.
632 The function can return \p false if the node the iterator points to has already been deleted
635 The function does not invalidate the iterator, it remains valid and can be used for further traversing.
637 @note \p %erase_at() is supported only for \p %SplitListSet based on \p IterableList.
639 #ifdef CDS_DOXYGEN_INVOKED
640 bool erase_at( iterator const& iter )
642 template <typename Iterator>
643 typename std::enable_if< std::is_same<Iterator, iterator>::value && is_iterable_list< ordered_list >::value, bool >::type
644 erase_at( Iterator const& iter )
647 return base_class::erase_at( static_cast<iterator::iterator_base_class const&>( iter ));
651 /// Extracts the item with specified \p key
652 /** \anchor cds_nonintrusive_SplitListSet_hp_extract
653 The function searches an item with key equal to \p key,
654 unlinks it from the set, and returns it as \p guarded_ptr.
655 If \p key is not found the function returns an empty guarded pointer.
657 Note the compare functor should accept a parameter of type \p Q that may be not the same as \p value_type.
659 The extracted item is freed automatically when returned \p guarded_ptr object will be destroyed or released.
660 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
664 typedef cds::container::SplitListSet< your_template_args > splitlist_set;
665 splitlist_set theSet;
668 splitlist_set::guarded_ptr gp(theSet.extract( 5 ));
673 // Destructor of gp releases internal HP guard
677 template <typename Q>
678 guarded_ptr extract( Q const& key )
680 return extract_( key );
683 /// Extracts the item using compare functor \p pred
685 The function is an analog of \ref cds_nonintrusive_SplitListSet_hp_extract "extract(Q const&)"
686 but \p pred predicate is used for key comparing.
688 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
690 \p pred must imply the same element order as the comparator used for building the set.
692 template <typename Q, typename Less>
693 guarded_ptr extract_with( Q const& key, Less pred )
695 return extract_with_( key, pred );
698 /// Finds the key \p key
699 /** \anchor cds_nonintrusive_SplitListSet_find_func
701 The function searches the item with key equal to \p key and calls the functor \p f for item found.
702 The interface of \p Func functor is:
705 void operator()( value_type& item, Q& key );
708 where \p item is the item found, \p key is the <tt>find</tt> function argument.
710 The functor may change non-key fields of \p item. Note that the functor is only guarantee
711 that \p item cannot be disposed during functor is executing.
712 The functor does not serialize simultaneous access to the set's \p item. If such access is
713 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
715 The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
716 may modify both arguments.
718 Note the hash functor specified for class \p Traits template parameter
719 should accept a parameter of type \p Q that can be not the same as \p value_type.
721 The function returns \p true if \p key is found, \p false otherwise.
723 template <typename Q, typename Func>
724 bool find( Q& key, Func f )
726 return find_( key, f );
729 template <typename Q, typename Func>
730 bool find( Q const& key, Func f )
732 return find_( key, f );
736 /// Finds \p key and returns iterator pointed to the item found (only for \p IterableList -based set)
738 If \p key is not found the function returns \p end().
740 @note This function is supported only for the set based on \p IterableList
742 template <typename Q>
743 #ifdef CDS_DOXYGEN_INVOKED
746 typename std::enable_if< std::is_same<Q,Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
750 return find_iterator_( key );
753 template <typename Q>
754 typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
757 return find_iterator_( key );
762 /// Finds the key \p key using \p pred predicate for searching
764 The function is an analog of \ref cds_nonintrusive_SplitListSet_find_func "find(Q&, Func)"
765 but \p pred is used for key comparing.
766 \p Less functor has the interface like \p std::less.
767 \p Less must imply the same element order as the comparator used for building the set.
769 template <typename Q, typename Less, typename Func>
770 bool find_with( Q& key, Less pred, Func f )
772 return find_with_( key, pred, f );
775 template <typename Q, typename Less, typename Func>
776 bool find_with( Q const& key, Less pred, Func f )
778 return find_with_( key, pred, f );
782 /// Finds \p key using \p pred predicate and returns iterator pointed to the item found (only for \p IterableList -based set)
784 The function is an analog of \p find(Q&) but \p pred is used for key comparing.
785 \p Less functor has the interface like \p std::less.
786 \p pred must imply the same element order as the comparator used for building the set.
788 If \p key is not found the function returns \p end().
790 @note This function is supported only for the set based on \p IterableList
792 template <typename Q, typename Less>
793 #ifdef CDS_DOXYGEN_INVOKED
796 typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
798 find_with( Q& key, Less pred )
800 return find_iterator_with_( key, pred );
803 template <typename Q, typename Less>
804 typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
805 find_with( Q const& key, Less pred )
807 return find_iterator_with_( key, pred );
811 /// Checks whether the set contains \p key
813 The function searches the item with key equal to \p key
814 and returns \p true if it is found, and \p false otherwise.
816 Note the hash functor specified for class \p Traits template parameter
817 should accept a parameter of type \p Q that can be not the same as \p value_type.
818 Otherwise, you may use \p contains( Q const&, Less pred ) functions with explicit predicate for key comparing.
820 template <typename Q>
821 bool contains( Q const& key )
823 return base_class::contains( key );
826 /// Checks whether the map contains \p key using \p pred predicate for searching
828 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
829 \p Less functor has the interface like \p std::less.
830 \p Less must imply the same element order as the comparator used for building the map.
832 template <typename Q, typename Less>
833 bool contains( Q const& key, Less pred )
836 return base_class::contains( key, typename maker::template predicate_wrapper<Less>::type());
839 /// Finds the key \p key and return the item found
840 /** \anchor cds_nonintrusive_SplitListSet_hp_get
841 The function searches the item with key equal to \p key
842 and returns the item found as \p guarded_ptr.
843 If \p key is not found the function returns an empty guarded pointer.
845 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
849 typedef cds::container::SplitListSet< your_template_params > splitlist_set;
850 splitlist_set theSet;
853 splitlist_set::guarded_ptr gp(theSet.get( 5 ));
858 // Destructor of guarded_ptr releases internal HP guard
862 Note the compare functor specified for split-list set
863 should accept a parameter of type \p Q that can be not the same as \p value_type.
865 template <typename Q>
866 guarded_ptr get( Q const& key )
871 /// Finds \p key and return the item found
873 The function is an analog of \ref cds_nonintrusive_SplitListSet_hp_get "get( Q const&)"
874 but \p pred is used for comparing the keys.
876 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
878 \p pred must imply the same element order as the comparator used for building the set.
880 template <typename Q, typename Less>
881 guarded_ptr get_with( Q const& key, Less pred )
883 return get_with_( key, pred );
886 /// Clears the set (not atomic)
892 /// Checks if the set is empty
894 Emptiness is checked by item counting: if item count is zero then assume that the set is empty.
895 Thus, the correct item counting feature is an important part of split-list set implementation.
899 return base_class::empty();
902 /// Returns item count in the set
905 return base_class::size();
908 /// Returns internal statistics
909 stat const& statistics() const
911 return base_class::statistics();
914 /// Returns internal statistics for \p ordered_list
915 typename ordered_list::stat const& list_statistics() const
917 return base_class::list_statistics();
922 using base_class::extract_;
923 using base_class::get_;
925 template <typename... Args>
926 static node_type * alloc_node( Args&&... args )
928 return cxx_node_allocator().MoveNew( std::forward<Args>( args )... );
931 static void free_node( node_type * pNode )
933 cxx_node_allocator().Delete( pNode );
936 template <typename Q, typename Func>
937 bool find_( Q& val, Func f )
939 return base_class::find( val, [&f]( node_type& item, Q& val ) { f( item.m_Value, val ); } );
942 template <typename Q>
943 typename std::enable_if< std::is_same<Q,Q>::value && is_iterable_list< ordered_list >::value, iterator>::type
944 find_iterator_( Q& val )
946 return iterator( base_class::find( val ));
949 template <typename Q, typename Less, typename Func>
950 bool find_with_( Q& val, Less pred, Func f )
953 return base_class::find_with( val, typename maker::template predicate_wrapper<Less>::type(),
954 [&f]( node_type& item, Q& val ) { f( item.m_Value, val ); } );
957 template <typename Q, typename Less>
958 typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator>::type
959 find_iterator_with_( Q& val, Less pred )
962 return iterator( base_class::find_with( val, typename maker::template predicate_wrapper<Less>::type()));
965 struct node_disposer {
966 void operator()( node_type * pNode )
971 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
973 bool insert_node( node_type * pNode )
975 assert( pNode != nullptr );
976 scoped_node_ptr p( pNode );
978 if ( base_class::insert( *pNode )) {
985 template <typename Q, typename Less>
986 guarded_ptr extract_with_( Q const& key, Less pred )
989 return base_class::extract_with_( key, typename maker::template predicate_wrapper<Less>::type());
992 template <typename Q, typename Less>
993 guarded_ptr get_with_( Q const& key, Less pred )
996 return base_class::get_with_( key, typename maker::template predicate_wrapper<Less>::type());
1002 }} // namespace cds::container
1004 #endif // #ifndef CDSLIB_CONTAINER_SPLIT_LIST_SET_H