3 #ifndef __CDS_CONTAINER_SPLIT_LIST_SET_H
4 #define __CDS_CONTAINER_SPLIT_LIST_SET_H
6 #include <cds/intrusive/split_list.h>
7 #include <cds/container/details/make_split_list_set.h>
9 namespace cds { namespace container {
11 /// Split-ordered list set
12 /** @ingroup cds_nonintrusive_set
13 \anchor cds_nonintrusive_SplitListSet_hp
15 Hash table implementation based on split-ordered list algorithm discovered by Ori Shalev and Nir Shavit, see
16 - [2003] Ori Shalev, Nir Shavit "Split-Ordered Lists - Lock-free Resizable Hash Tables"
17 - [2008] Nir Shavit "The Art of Multiprocessor Programming"
19 See intrusive::SplitListSet for a brief description of the split-list algorithm.
22 - \p GC - Garbage collector used
23 - \p T - type stored in the split-list. The type must be default- and copy-constructible.
24 - \p Traits - type traits, default is split_list::type_traits. Instead of declaring split_list::type_traits -based
25 struct you may apply option-based notation with split_list::make_traits metafunction.
27 There are the specializations:
28 - for \ref cds_urcu_desc "RCU" - declared in <tt>cd/container/split_list_set_rcu.h</tt>,
29 see \ref cds_nonintrusive_SplitListSet_rcu "SplitListSet<RCU>".
30 - for \ref cds::gc::nogc declared in <tt>cds/container/split_list_set_nogc.h</tt>,
31 see \ref cds_nonintrusive_SplitListSet_nogc "SplitListSet<gc::nogc>".
35 You should decide what garbage collector you want, and what ordered list you want to use. Split-ordered list
36 is original data structure based on an ordered list. Suppose, you want construct split-list set based on gc::DHP GC
37 and LazyList as ordered list implementation. So, you beginning your program with following include:
39 #include <cds/container/lazy_list_dhp.h>
40 #include <cds/container/split_list_set.h>
42 namespace cc = cds::container;
44 // The data belonged to split-ordered list
46 int nKey; // key field
47 std::string strValue ; // value field
50 The inclusion order is important: first, include header for ordered-list implementation (for this example, <tt>cds/container/lazy_list_dhp.h</tt>),
51 then the header for split-list set <tt>cds/container/split_list_set.h</tt>.
53 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.
54 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
55 object by the key of type <tt>int</tt> and by the value of type <tt>foo</tt>.
57 The second attention: instead of using \p %LazyList in \p %SplitListSet traits we use a tag <tt>cds::contaner::lazy_list_tag</tt> for the lazy list.
58 The split-list requires significant support from underlying ordered list class and it is not good idea to dive you
59 into deep implementation details of split-list and ordered list interrelations. The tag paradigm simplifies split-list interface.
64 size_t operator()( int key ) const { return std::hash( key ) ; }
65 size_t operator()( foo const& item ) const { return std::hash( item.nKey ) ; }
70 bool operator()(int i, foo const& f ) const { return i < f.nKey ; }
71 bool operator()(foo const& f, int i ) const { return f.nKey < i ; }
72 bool operator()(foo const& f1, foo const& f2) const { return f1.nKey < f2.nKey; }
75 // SplitListSet traits
76 struct foo_set_traits: public cc::split_list::type_traits
78 typedef cc::lazy_list_tag ordered_list ; // what type of ordered list we want to use
79 typedef foo_hash hash ; // hash functor for our data stored in split-list set
81 // Type traits for our LazyList class
82 struct ordered_list_traits: public cc::lazy_list::type_traits
84 typedef foo_less less ; // use our foo_less as comparator to order list nodes
89 Now you are ready to declare our set class based on \p %SplitListSet:
91 typedef cc::SplitListSet< cds::gc::PTB, foo, foo_set_traits > foo_set;
94 You may use the modern option-based declaration instead of classic type-traits-based one:
96 typedef cc:SplitListSet<
97 cs::gc::PTB // GC used
98 ,foo // type of data stored
99 ,cc::split_list::make_traits< // metafunction to build split-list traits
100 cc::split_list::ordered_list<cc::lazy_list_tag> // tag for underlying ordered list implementation
101 ,cc::opt::hash< foo_hash > // hash functor
102 ,cc::split_list::ordered_list_traits< // ordered list traits desired
103 cc::lazy_list::make_traits< // metafunction to build lazy list traits
104 cc::opt::less< foo_less > // less-based compare functor
110 In case of option-based declaration using split_list::make_traits metafunction
111 the struct \p foo_set_traits is not required.
113 Now, the set of type \p foo_set is ready to use in your program.
115 Note that in this example we show only mandatory type_traits parts, optional ones is the default and they are inherited
116 from cds::container::split_list::type_traits.
117 The <b>cds</b> library contains many other options for deep tuning of behavior of the split-list and
118 ordered-list containers.
123 #ifdef CDS_DOXYGEN_INVOKED
124 class Traits = split_list::type_traits
130 #ifdef CDS_DOXYGEN_INVOKED
131 protected intrusive::SplitListSet<GC, typename Traits::ordered_list, Traits>
133 protected details::make_split_list_set< GC, T, typename Traits::ordered_list, split_list::details::wrap_set_traits<T, Traits> >::type
138 typedef details::make_split_list_set< GC, T, typename Traits::ordered_list, split_list::details::wrap_set_traits<T, Traits> > maker;
139 typedef typename maker::type base_class;
143 typedef Traits options ; ///< \p Traits template argument
144 typedef typename maker::gc gc ; ///< Garbage collector
145 typedef typename maker::value_type value_type ; ///< type of value stored in the list
146 typedef typename maker::ordered_list ordered_list ; ///< Underlying ordered list class
147 typedef typename base_class::key_comparator key_comparator; ///< key compare functor
149 /// Hash functor for \p %value_type and all its derivatives that you use
150 typedef typename base_class::hash hash;
151 typedef typename base_class::item_counter item_counter ; ///< Item counter type
155 typedef typename maker::cxx_node_allocator cxx_node_allocator;
156 typedef typename maker::node_type node_type;
161 typedef cds::gc::guarded_ptr< gc, node_type, value_type, details::guarded_ptr_cast_set<node_type, value_type> > guarded_ptr;
165 template <typename Q>
166 static node_type * alloc_node(Q const& v )
168 return cxx_node_allocator().New( v );
171 template <typename Q, typename Func>
172 bool find_( Q& val, Func f )
174 return base_class::find( val, [&f]( node_type& item, Q& val ) { f(item.m_Value, val) ; } );
177 template <typename Q, typename Less, typename Func>
178 bool find_with_( Q& val, Less pred, Func f )
180 return base_class::find_with( val, typename maker::template predicate_wrapper<Less>::type(),
181 [&f]( node_type& item, Q& val ) { f(item.m_Value, val) ; } );
184 template <typename... Args>
185 static node_type * alloc_node( Args&&... args )
187 return cxx_node_allocator().MoveNew( std::forward<Args>(args)...);
190 static void free_node( node_type * pNode )
192 cxx_node_allocator().Delete( pNode );
195 struct node_disposer {
196 void operator()( node_type * pNode )
201 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
203 bool insert_node( node_type * pNode )
205 assert( pNode != nullptr );
206 scoped_node_ptr p(pNode);
208 if ( base_class::insert( *pNode ) ) {
221 \p IsConst - constness boolean flag
223 The forward iterator for a split-list has the following features:
224 - it has no post-increment operator
225 - it depends on underlying ordered list iterator
226 - The iterator object cannot be moved across thread boundary since it contains GC's guard that is thread-private GC data.
227 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
228 deleting operations it is no guarantee that you iterate all item in the split-list.
230 Therefore, the use of iterators in concurrent environment is not good idea. Use it for debug purpose only.
232 template <bool IsConst>
233 class iterator_type: protected base_class::template iterator_type<IsConst>
236 typedef typename base_class::template iterator_type<IsConst> iterator_base_class;
237 friend class SplitListSet;
240 /// Value pointer type (const for const iterator)
241 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
242 /// Value reference type (const for const iterator)
243 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
251 iterator_type( iterator_type const& src )
252 : iterator_base_class( src )
257 explicit iterator_type( iterator_base_class const& src )
258 : iterator_base_class( src )
263 /// Dereference operator
264 value_ptr operator ->() const
266 return &(iterator_base_class::operator->()->m_Value);
269 /// Dereference operator
270 value_ref operator *() const
272 return iterator_base_class::operator*().m_Value;
276 iterator_type& operator ++()
278 iterator_base_class::operator++();
282 /// Assignment operator
283 iterator_type& operator = (iterator_type const& src)
285 iterator_base_class::operator=(src);
289 /// Equality operator
291 bool operator ==(iterator_type<C> const& i ) const
293 return iterator_base_class::operator==(i);
296 /// Equality operator
298 bool operator !=(iterator_type<C> const& i ) const
300 return iterator_base_class::operator!=(i);
305 /// Initializes split-ordered list of default capacity
307 The default capacity is defined in bucket table constructor.
308 See intrusive::split_list::expandable_bucket_table, intrusive::split_list::static_bucket_table
309 which selects by intrusive::split_list::dynamic_bucket_table option.
315 /// Initializes split-ordered list
317 size_t nItemCount ///< estimate average of item count
318 , size_t nLoadFactor = 1 ///< load factor - average item count per bucket. Small integer up to 8, default is 1.
320 : base_class( nItemCount, nLoadFactor )
325 typedef iterator_type<false> iterator;
327 /// Const forward iterator
328 typedef iterator_type<true> const_iterator;
330 /// Returns a forward iterator addressing the first element in a set
332 For empty set \code begin() == end() \endcode
336 return iterator( base_class::begin() );
339 /// Returns an iterator that addresses the location succeeding the last element in a set
341 Do not use the value returned by <tt>end</tt> function to access any item.
342 The returned value can be used only to control reaching the end of the set.
343 For empty set \code begin() == end() \endcode
347 return iterator( base_class::end() );
350 /// Returns a forward const iterator addressing the first element in a set
351 const_iterator begin() const
353 return const_iterator( base_class::begin() );
356 /// Returns an const iterator that addresses the location succeeding the last element in a set
357 const_iterator end() const
359 return const_iterator( base_class::end() );
365 The function creates a node with copy of \p val value
366 and then inserts the node created into the set.
368 The type \p Q should contain as minimum the complete key for the node.
369 The object of \ref value_type should be constructible from a value of type \p Q.
370 In trivial case, \p Q is equal to \ref value_type.
372 Returns \p true if \p val is inserted into the set, \p false otherwise.
374 template <typename Q>
375 bool insert( Q const& val )
377 return insert_node( alloc_node( val ) );
382 The function allows to split creating of new item into two part:
383 - create item with key only
384 - insert new item into the set
385 - if inserting is success, calls \p f functor to initialize value-field of \p val.
387 The functor signature is:
389 void func( value_type& val );
391 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
392 \p val no any other changes could be made on this set's item by concurrent threads.
393 The user-defined functor is called only if the inserting is success. It may be passed by reference
396 template <typename Q, typename Func>
397 bool insert( Q const& val, Func f )
399 scoped_node_ptr pNode( alloc_node( val ));
401 if ( base_class::insert( *pNode, [&f](node_type& node) { f( node.m_Value ) ; } )) {
408 /// Inserts data of type \p %value_type constructed with <tt>std::forward<Args>(args)...</tt>
410 Returns \p true if inserting successful, \p false otherwise.
412 template <typename... Args>
413 bool emplace( Args&&... args )
415 return insert_node( alloc_node( std::forward<Args>(args)...));
418 /// Ensures that the \p item exists in the set
420 The operation performs inserting or changing data with lock-free manner.
422 If the \p val key not found in the set, then the new item created from \p val
423 is inserted into the set. Otherwise, the functor \p func is called with the item found.
424 The functor \p Func should be a function with signature:
426 void func( bool bNew, value_type& item, const Q& val );
431 void operator()( bool bNew, value_type& item, const Q& val );
436 - \p bNew - \p true if the item has been inserted, \p false otherwise
437 - \p item - item of the set
438 - \p val - argument \p val passed into the \p ensure function
440 The functor may change non-key fields of the \p item; however, \p func must guarantee
441 that during changing no any other modifications could be made on this item by concurrent threads.
443 You may pass \p func argument by reference using \p std::ref
445 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
446 \p second is true if new item has been added or \p false if the item with \p key
447 already is in the set.
449 template <typename Q, typename Func>
450 std::pair<bool, bool> ensure( Q const& val, Func func )
452 scoped_node_ptr pNode( alloc_node( val ));
454 std::pair<bool, bool> bRet = base_class::ensure( *pNode,
455 [&func, &val]( bool bNew, node_type& item, node_type const& /*val*/ ) {
456 func( bNew, item.m_Value, val );
459 if ( bRet.first && bRet.second )
464 /// Deletes \p key from the set
465 /** \anchor cds_nonintrusive_SplitListSet_erase_val
467 The item comparator should be able to compare the values of type \p value_type
470 Return \p true if key is found and deleted, \p false otherwise
472 template <typename Q>
473 bool erase( Q const& key )
475 return base_class::erase( key );
478 /// Deletes the item from the set using \p pred predicate for searching
480 The function is an analog of \ref cds_nonintrusive_SplitListSet_erase_val "erase(Q const&)"
481 but \p pred is used for key comparing.
482 \p Less functor has the interface like \p std::less.
483 \p Less must imply the same element order as the comparator used for building the set.
485 template <typename Q, typename Less>
486 bool erase_with( Q const& key, Less pred )
488 return base_class::erase_with( key, typename maker::template predicate_wrapper<Less>::type() );
491 /// Deletes \p key from the set
492 /** \anchor cds_nonintrusive_SplitListSet_erase_func
494 The function searches an item with key \p key, calls \p f functor
495 and deletes the item. If \p key is not found, the functor is not called.
497 The functor \p Func interface:
500 void operator()(value_type const& val);
503 The functor may be passed by reference using <tt>boost:ref</tt>
505 Since the key of SplitListSet's \p value_type is not explicitly specified,
506 template parameter \p Q defines the key type searching in the list.
507 The list item comparator should be able to compare the values of the type \p value_type
510 Return \p true if key is found and deleted, \p false otherwise
512 template <typename Q, typename Func>
513 bool erase( Q const& key, Func f )
515 return base_class::erase( key, [&f](node_type& node) { f( node.m_Value ); } );
518 /// Deletes the item from the set using \p pred predicate for searching
520 The function is an analog of \ref cds_nonintrusive_SplitListSet_erase_func "erase(Q const&, Func)"
521 but \p pred is used for key comparing.
522 \p Less functor has the interface like \p std::less.
523 \p Less must imply the same element order as the comparator used for building the set.
525 template <typename Q, typename Less, typename Func>
526 bool erase_with( Q const& key, Less pred, Func f )
528 return base_class::erase_with( key, typename maker::template predicate_wrapper<Less>::type(),
529 [&f](node_type& node) { f( node.m_Value ); } );
532 /// Extracts the item with specified \p key
533 /** \anchor cds_nonintrusive_SplitListSet_hp_extract
534 The function searches an item with key equal to \p key,
535 unlinks it from the set, and returns it in \p dest parameter.
536 If the item with key equal to \p key is not found the function returns \p false.
538 Note the compare functor should accept a parameter of type \p Q that may be not the same as \p value_type.
540 The extracted item is freed automatically when returned \ref guarded_ptr object will be destroyed or released.
541 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
545 typedef cds::container::SplitListSet< your_template_args > splitlist_set;
546 splitlist_set theSet;
549 splitlist_set::guarded_ptr gp;
550 theSet.extract( gp, 5 );
554 // Destructor of gp releases internal HP guard
558 template <typename Q>
559 bool extract( guarded_ptr& dest, Q const& key )
561 return extract_( dest.guard(), key );
564 /// Extracts the item using compare functor \p pred
566 The function is an analog of \ref cds_nonintrusive_SplitListSet_hp_extract "extract(guarded_ptr&, Q const&)"
567 but \p pred predicate is used for key comparing.
569 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
571 \p pred must imply the same element order as the comparator used for building the set.
573 template <typename Q, typename Less>
574 bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
576 return extract_with_( dest.guard(), key, pred );
579 /// Finds the key \p val
580 /** \anchor cds_nonintrusive_SplitListSet_find_func
582 The function searches the item with key equal to \p val and calls the functor \p f for item found.
583 The interface of \p Func functor is:
586 void operator()( value_type& item, Q& val );
589 where \p item is the item found, \p val is the <tt>find</tt> function argument.
591 You may pass \p f argument by reference using \p std::ref.
593 The functor may change non-key fields of \p item. Note that the functor is only guarantee
594 that \p item cannot be disposed during functor is executing.
595 The functor does not serialize simultaneous access to the set's \p item. If such access is
596 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
598 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
599 may modify both arguments.
601 Note the hash functor specified for class \p Traits template parameter
602 should accept a parameter of type \p Q that can be not the same as \p value_type.
604 The function returns \p true if \p val is found, \p false otherwise.
606 template <typename Q, typename Func>
607 bool find( Q& val, Func f )
609 return find_( val, f );
612 /// Finds the key \p val using \p pred predicate for searching
614 The function is an analog of \ref cds_nonintrusive_SplitListSet_find_func "find(Q&, Func)"
615 but \p pred is used for key comparing.
616 \p Less functor has the interface like \p std::less.
617 \p Less must imply the same element order as the comparator used for building the set.
619 template <typename Q, typename Less, typename Func>
620 bool find_with( Q& val, Less pred, Func f )
622 return find_with_( val, pred, f );
625 /// Finds the key \p val
626 /** \anchor cds_nonintrusive_SplitListSet_find_cfunc
628 The function searches the item with key equal to \p val and calls the functor \p f for item found.
629 The interface of \p Func functor is:
632 void operator()( value_type& item, Q const& val );
635 where \p item is the item found, \p val is the <tt>find</tt> function argument.
637 You may pass \p f argument by reference using \p std::ref.
639 The functor may change non-key fields of \p item. Note that the functor is only guarantee
640 that \p item cannot be disposed during functor is executing.
641 The functor does not serialize simultaneous access to the set's \p item. If such access is
642 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
644 Note the hash functor specified for class \p Traits template parameter
645 should accept a parameter of type \p Q that can be not the same as \p value_type.
647 The function returns \p true if \p val is found, \p false otherwise.
649 template <typename Q, typename Func>
650 bool find( Q const& val, Func f )
652 return find_( val, f );
655 /// Finds the key \p val using \p pred predicate for searching
657 The function is an analog of \ref cds_nonintrusive_SplitListSet_find_cfunc "find(Q const&, Func)"
658 but \p pred is used for key comparing.
659 \p Less functor has the interface like \p std::less.
660 \p Less must imply the same element order as the comparator used for building the set.
662 template <typename Q, typename Less, typename Func>
663 bool find_with( Q const& val, Less pred, Func f )
665 return find_with_( val, pred, f );
668 /// Finds the key \p val
669 /** \anchor cds_nonintrusive_SplitListSet_find_val
671 The function searches the item with key equal to \p val
672 and returns \p true if it is found, and \p false otherwise.
674 Note the hash functor specified for class \p Traits template parameter
675 should accept a parameter of type \p Q that can be not the same as \ref value_type.
677 template <typename Q>
678 bool find( Q const& val )
680 return base_class::find( val );
683 /// Finds the key \p val using \p pred predicate for searching
685 The function is an analog of \ref cds_nonintrusive_SplitListSet_find_val "find(Q const&)"
686 but \p pred is used for key comparing.
687 \p Less functor has the interface like \p std::less.
688 \p Less must imply the same element order as the comparator used for building the set.
690 template <typename Q, typename Less>
691 bool find_with( Q const& val, Less pred )
693 return base_class::find_with( val, typename maker::template predicate_wrapper<Less>::type() );
696 /// Finds the key \p key and return the item found
697 /** \anchor cds_nonintrusive_SplitListSet_hp_get
698 The function searches the item with key equal to \p key
699 and assigns the item found to guarded pointer \p ptr.
700 The function returns \p true if \p key is found, and \p false otherwise.
701 If \p key is not found the \p ptr parameter is not changed.
703 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
707 typedef cds::container::SplitListSet< your_template_params > splitlist_set;
708 splitlist_set theSet;
711 splitlist_set::guarded_ptr gp;
712 if ( theSet.get( gp, 5 )) {
716 // Destructor of guarded_ptr releases internal HP guard
720 Note the compare functor specified for split-list set
721 should accept a parameter of type \p Q that can be not the same as \p value_type.
723 template <typename Q>
724 bool get( guarded_ptr& ptr, Q const& key )
726 return get_( ptr.guard(), key );
729 /// Finds \p key and return the item found
731 The function is an analog of \ref cds_nonintrusive_SplitListSet_hp_get "get( guarded_ptr&, Q const&)"
732 but \p pred is used for comparing the keys.
734 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
736 \p pred must imply the same element order as the comparator used for building the set.
738 template <typename Q, typename Less>
739 bool get_with( guarded_ptr& ptr, Q const& key, Less pred )
741 return get_with_( ptr.guard(), key, pred );
744 /// Clears the set (non-atomic)
746 The function unlink all items from the set.
747 The function is not atomic and not lock-free and should be used for debugging only.
754 /// Checks if the set is empty
756 Emptiness is checked by item counting: if item count is zero then assume that the set is empty.
757 Thus, the correct item counting feature is an important part of split-list set implementation.
761 return base_class::empty();
764 /// Returns item count in the set
767 return base_class::size();
772 using base_class::extract_;
773 using base_class::get_;
775 template <typename Q, typename Less>
776 bool extract_with_( typename gc::Guard& guard, Q const& key, Less pred )
778 return base_class::extract_with_( guard, key, typename maker::template predicate_wrapper<Less>::type() );
781 template <typename Q, typename Less>
782 bool get_with_( typename gc::Guard& guard, Q const& key, Less pred )
784 return base_class::get_with_( guard, key, typename maker::template predicate_wrapper<Less>::type() );
792 }} // namespace cds::container
794 #endif // #ifndef __CDS_CONTAINER_SPLIT_LIST_SET_H