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_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 const& val )
394 return insert_node( alloc_node( 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 const& val, Func f )
419 scoped_node_ptr pNode( alloc_node( 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( 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 const& val, Func func, bool bAllowInsert = true )
519 scoped_node_ptr pNode( alloc_node( 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 const& val, Func func, bool bAllowInsert = true )
538 scoped_node_ptr pNode( alloc_node( 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 /// Extracts the item with specified \p key
630 /** \anchor cds_nonintrusive_SplitListSet_hp_extract
631 The function searches an item with key equal to \p key,
632 unlinks it from the set, and returns it as \p guarded_ptr.
633 If \p key is not found the function returns an empty guarded pointer.
635 Note the compare functor should accept a parameter of type \p Q that may be not the same as \p value_type.
637 The extracted item is freed automatically when returned \p guarded_ptr object will be destroyed or released.
638 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
642 typedef cds::container::SplitListSet< your_template_args > splitlist_set;
643 splitlist_set theSet;
646 splitlist_set::guarded_ptr gp(theSet.extract( 5 ));
651 // Destructor of gp releases internal HP guard
655 template <typename Q>
656 guarded_ptr extract( Q const& key )
658 return extract_( key );
661 /// Extracts the item using compare functor \p pred
663 The function is an analog of \ref cds_nonintrusive_SplitListSet_hp_extract "extract(Q const&)"
664 but \p pred predicate is used for key comparing.
666 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
668 \p pred must imply the same element order as the comparator used for building the set.
670 template <typename Q, typename Less>
671 guarded_ptr extract_with( Q const& key, Less pred )
673 return extract_with_( key, pred );
676 /// Finds the key \p key
677 /** \anchor cds_nonintrusive_SplitListSet_find_func
679 The function searches the item with key equal to \p key and calls the functor \p f for item found.
680 The interface of \p Func functor is:
683 void operator()( value_type& item, Q& key );
686 where \p item is the item found, \p key is the <tt>find</tt> function argument.
688 The functor may change non-key fields of \p item. Note that the functor is only guarantee
689 that \p item cannot be disposed during functor is executing.
690 The functor does not serialize simultaneous access to the set's \p item. If such access is
691 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
693 The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
694 may modify both arguments.
696 Note the hash functor specified for class \p Traits template parameter
697 should accept a parameter of type \p Q that can be not the same as \p value_type.
699 The function returns \p true if \p key is found, \p false otherwise.
701 template <typename Q, typename Func>
702 bool find( Q& key, Func f )
704 return find_( key, f );
707 template <typename Q, typename Func>
708 bool find( Q const& key, Func f )
710 return find_( key, f );
714 /// Finds \p key and returns iterator pointed to the item found (only for \p IterableList -based set)
716 If \p key is not found the function returns \p end().
718 @note This function is supported only for the set based on \p IterableList
720 template <typename Q>
721 #ifdef CDS_DOXYGEN_INVOKED
724 typename std::enable_if< std::is_same<Q,Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
728 return find_iterator_( key );
731 template <typename Q>
732 typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
735 return find_iterator_( key );
740 /// Finds the key \p key using \p pred predicate for searching
742 The function is an analog of \ref cds_nonintrusive_SplitListSet_find_func "find(Q&, Func)"
743 but \p pred is used for key comparing.
744 \p Less functor has the interface like \p std::less.
745 \p Less must imply the same element order as the comparator used for building the set.
747 template <typename Q, typename Less, typename Func>
748 bool find_with( Q& key, Less pred, Func f )
750 return find_with_( key, pred, f );
753 template <typename Q, typename Less, typename Func>
754 bool find_with( Q const& key, Less pred, Func f )
756 return find_with_( key, pred, f );
760 /// Finds \p key using \p pred predicate and returns iterator pointed to the item found (only for \p IterableList -based set)
762 The function is an analog of \p find(Q&) but \p pred is used for key comparing.
763 \p Less functor has the interface like \p std::less.
764 \p pred must imply the same element order as the comparator used for building the set.
766 If \p key is not found the function returns \p end().
768 @note This function is supported only for the set based on \p IterableList
770 template <typename Q, typename Less>
771 #ifdef CDS_DOXYGEN_INVOKED
774 typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
776 find_with( Q& key, Less pred )
778 return find_iterator_with_( key, pred );
781 template <typename Q, typename Less>
782 typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
783 find_with( Q const& key, Less pred )
785 return find_iterator_with_( key, pred );
789 /// Checks whether the set contains \p key
791 The function searches the item with key equal to \p key
792 and returns \p true if it is found, and \p false otherwise.
794 Note the hash functor specified for class \p Traits template parameter
795 should accept a parameter of type \p Q that can be not the same as \p value_type.
796 Otherwise, you may use \p contains( Q const&, Less pred ) functions with explicit predicate for key comparing.
798 template <typename Q>
799 bool contains( Q const& key )
801 return base_class::contains( key );
804 /// Checks whether the map contains \p key using \p pred predicate for searching
806 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
807 \p Less functor has the interface like \p std::less.
808 \p Less must imply the same element order as the comparator used for building the map.
810 template <typename Q, typename Less>
811 bool contains( Q const& key, Less pred )
814 return base_class::contains( key, typename maker::template predicate_wrapper<Less>::type());
817 /// Finds the key \p key and return the item found
818 /** \anchor cds_nonintrusive_SplitListSet_hp_get
819 The function searches the item with key equal to \p key
820 and returns the item found as \p guarded_ptr.
821 If \p key is not found the function returns an empty guarded pointer.
823 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
827 typedef cds::container::SplitListSet< your_template_params > splitlist_set;
828 splitlist_set theSet;
831 splitlist_set::guarded_ptr gp(theSet.get( 5 ));
836 // Destructor of guarded_ptr releases internal HP guard
840 Note the compare functor specified for split-list set
841 should accept a parameter of type \p Q that can be not the same as \p value_type.
843 template <typename Q>
844 guarded_ptr get( Q const& key )
849 /// Finds \p key and return the item found
851 The function is an analog of \ref cds_nonintrusive_SplitListSet_hp_get "get( Q const&)"
852 but \p pred is used for comparing the keys.
854 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
856 \p pred must imply the same element order as the comparator used for building the set.
858 template <typename Q, typename Less>
859 guarded_ptr get_with( Q const& key, Less pred )
861 return get_with_( key, pred );
864 /// Clears the set (not atomic)
870 /// Checks if the set is empty
872 Emptiness is checked by item counting: if item count is zero then assume that the set is empty.
873 Thus, the correct item counting feature is an important part of split-list set implementation.
877 return base_class::empty();
880 /// Returns item count in the set
883 return base_class::size();
886 /// Returns internal statistics
887 stat const& statistics() const
889 return base_class::statistics();
892 /// Returns internal statistics for \p ordered_list
893 typename ordered_list::stat const& list_statistics() const
895 return base_class::statistics();
900 using base_class::extract_;
901 using base_class::get_;
903 template <typename Q>
904 static node_type * alloc_node( Q const& v )
906 return cxx_node_allocator().New( v );
909 template <typename... Args>
910 static node_type * alloc_node( Args&&... args )
912 return cxx_node_allocator().MoveNew( std::forward<Args>( args )... );
915 static void free_node( node_type * pNode )
917 cxx_node_allocator().Delete( pNode );
920 template <typename Q, typename Func>
921 bool find_( Q& val, Func f )
923 return base_class::find( val, [&f]( node_type& item, Q& val ) { f( item.m_Value, val ); } );
926 template <typename Q>
927 typename std::enable_if< std::is_same<Q,Q>::value && is_iterable_list< ordered_list >::value, iterator>::type
928 find_iterator_( Q& val )
930 return iterator( base_class::find( val ) );
933 template <typename Q, typename Less, typename Func>
934 bool find_with_( Q& val, Less pred, Func f )
937 return base_class::find_with( val, typename maker::template predicate_wrapper<Less>::type(),
938 [&f]( node_type& item, Q& val ) { f( item.m_Value, val ); } );
941 template <typename Q, typename Less>
942 typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator>::type
943 find_iterator_with_( Q& val, Less pred )
946 return iterator( base_class::find_with( val, typename maker::template predicate_wrapper<Less>::type() ));
949 struct node_disposer {
950 void operator()( node_type * pNode )
955 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
957 bool insert_node( node_type * pNode )
959 assert( pNode != nullptr );
960 scoped_node_ptr p( pNode );
962 if ( base_class::insert( *pNode ) ) {
969 template <typename Q, typename Less>
970 guarded_ptr extract_with_( Q const& key, Less pred )
973 return base_class::extract_with_( key, typename maker::template predicate_wrapper<Less>::type());
976 template <typename Q, typename Less>
977 guarded_ptr get_with_( Q const& key, Less pred )
980 return base_class::get_with_( key, typename maker::template predicate_wrapper<Less>::type());
986 }} // namespace cds::container
988 #endif // #ifndef CDSLIB_CONTAINER_SPLIT_LIST_SET_H