3 #ifndef CDSLIB_CONTAINER_SPLIT_LIST_SET_RCU_H
4 #define CDSLIB_CONTAINER_SPLIT_LIST_SET_RCU_H
6 #include <cds/intrusive/split_list_rcu.h>
7 #include <cds/container/details/make_split_list_set.h>
8 #include <cds/urcu/exempt_ptr.h>
10 namespace cds { namespace container {
12 /// Split-ordered list set (template specialization for \ref cds_urcu_desc "RCU")
13 /** @ingroup cds_nonintrusive_set
14 \anchor cds_nonintrusive_SplitListSet_rcu
16 Hash table implementation based on split-ordered list algorithm discovered by Ori Shalev and Nir Shavit, see
17 - [2003] Ori Shalev, Nir Shavit "Split-Ordered Lists - Lock-free Resizable Hash Tables"
18 - [2008] Nir Shavit "The Art of Multiprocessor Programming"
20 See \p intrusive::SplitListSet for a brief description of the split-list algorithm.
23 - \p RCU - one of \ref cds_urcu_gc "RCU type"
24 - \p T - type of the value to be stored in the split-list.
25 - \p Traits - type traits, default is \p split_list::traits. Instead of declaring \p split_list::traits -based
26 struct you can apply option-based notation with \p split_list::make_traits metafunction.
30 The class supports a forward iterator (\ref iterator and \ref const_iterator).
31 The iteration is unordered.
33 You may iterate over split-list set items only under RCU lock.
34 Only in this case the iterator is thread-safe since
35 while RCU is locked any set's item cannot be reclaimed.
37 @warning The iterator object cannot be passed between threads
39 \warning Due to concurrent nature of skip-list set it is not guarantee that you can iterate
40 all elements in the set: any concurrent deletion can exclude the element
41 pointed by the iterator from the set, and your iteration can be terminated
42 before end of the set. Therefore, such iteration is more suitable for debugging purposes
44 The iterator class supports the following minimalistic interface:
51 iterator( iterator const& s);
53 value_type * operator ->() const;
54 value_type& operator *() const;
57 iterator& operator ++();
60 iterator& operator = (const iterator& src);
62 bool operator ==(iterator const& i ) const;
63 bool operator !=(iterator const& i ) const;
66 Note, the iterator object returned by \p end(), \p cend() member functions points to \p nullptr and should not be dereferenced.
70 You should decide what garbage collector you want, and what ordered list you want to use. Split-ordered list
71 is an original data structure based on an ordered list. Suppose, you want construct split-list set based on \p cds::urcu::general_buffered<> GC
72 and \p LazyList as ordered list implementation. So, you beginning your program with following include:
74 #include <cds/urcu/general_buffered.h>
75 #include <cds/container/lazy_list_rcu.h>
76 #include <cds/container/split_list_set_rcu.h>
78 namespace cc = cds::container;
80 // The data belonged to split-ordered list
82 int nKey; // key field
83 std::string strValue ; // value field
86 The inclusion order is important:
87 - first, include one of \ref cds_urcu_gc "RCU implementation" (<tt>cds/urcu/general_buffered.h</tt> in our case)
88 - second, include file for ordered-list implementation (for this example, <tt>cds/container/lazy_list_rcu.h</tt>),
89 - then, the header for RCU-based split-list set <tt>cds/container/split_list_set_rcu.h</tt>.
91 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.
92 Note that we define several function in \p foo_hash and \p foo_less functors for different argument types since we want call our \p %SplitListSet
93 object by the key of type \p int and by the value of type \p foo.
95 The second attention: instead of using \p %LazyList in \p %SplitListSet traits we use \p cds::contaner::lazy_list_tag tag for the lazy list.
96 The split-list requires significant support from underlying ordered list class and it is not good idea to dive you
97 into deep implementation details of split-list and ordered list interrelations. The tag paradigm simplifies split-list interface.
102 size_t operator()( int key ) const { return std::hash( key ) ; }
103 size_t operator()( foo const& item ) const { return std::hash( item.nKey ) ; }
108 bool operator()(int i, foo const& f ) const { return i < f.nKey ; }
109 bool operator()(foo const& f, int i ) const { return f.nKey < i ; }
110 bool operator()(foo const& f1, foo const& f2) const { return f1.nKey < f2.nKey; }
113 // SplitListSet traits
114 struct foo_set_traits: public cc::split_list::traits
116 typedef cc::lazy_list_tag ordered_list ; // what type of ordered list we want to use
117 typedef foo_hash hash ; // hash functor for our data stored in split-list set
119 // Type traits for our LazyList class
120 struct ordered_list_traits: public cc::lazy_list::traits
122 typedef foo_less less ; // use our foo_less as comparator to order list nodes
127 Now you are ready to declare our set class based on \p %SplitListSet:
129 typedef cc::SplitListSet< cds::urcu::gc<cds::urcu::general_buffered<> >, foo, foo_set_traits > foo_set;
132 You may use the modern option-based declaration instead of classic type-traits-based one:
134 typedef cc:SplitListSet<
135 cds::urcu::gc<cds::urcu::general_buffered<> > // RCU type used
136 ,foo // type of data stored
137 ,cc::split_list::make_traits< // metafunction to build split-list traits
138 cc::split_list::ordered_list<cc::lazy_list_tag> // tag for underlying ordered list implementation
139 ,cc::opt::hash< foo_hash > // hash functor
140 ,cc::split_list::ordered_list_traits< // ordered list traits
141 cc::lazy_list::make_traits< // metafunction to build lazy list traits
142 cc::opt::less< foo_less > // less-based compare functor
148 In case of option-based declaration using \p split_list::make_traits metafunction
149 the struct \p foo_set_traits is not required.
151 Now, the set of type \p foo_set is ready to use in your program.
153 Note that in this example we show only mandatory \p traits parts, optional ones is the default and they are inherited
154 from \p container::split_list::traits.
155 There are many other options for deep tuning of the split-list and ordered-list containers.
160 #ifdef CDS_DOXYGEN_INVOKED
161 class Traits = split_list::traits
166 class SplitListSet< cds::urcu::gc< RCU >, T, Traits >:
167 #ifdef CDS_DOXYGEN_INVOKED
168 protected intrusive::SplitListSet< cds::urcu::gc< RCU >, T, typename Traits::ordered_list, Traits >
170 protected details::make_split_list_set< cds::urcu::gc< RCU >, T, typename Traits::ordered_list, split_list::details::wrap_set_traits<T, Traits> >::type
175 typedef details::make_split_list_set< cds::urcu::gc< RCU >, T, typename Traits::ordered_list, split_list::details::wrap_set_traits<T, Traits> > maker;
176 typedef typename maker::type base_class;
180 typedef cds::urcu::gc< RCU > gc; ///< RCU-based garbage collector
181 typedef T value_type; ///< Type of value to be storedin the set
182 typedef Traits traits; ///< \p Traits template argument
184 typedef typename maker::ordered_list ordered_list; ///< Underlying ordered list class
185 typedef typename base_class::key_comparator key_comparator; ///< key compare functor
187 /// Hash functor for \ref value_type and all its derivatives that you use
188 typedef typename base_class::hash hash;
189 typedef typename base_class::item_counter item_counter; ///< Item counter type
190 typedef typename base_class::stat stat; ///< Internal statistics
192 typedef typename base_class::rcu_lock rcu_lock ; ///< RCU scoped lock
193 /// Group of \p extract_xxx functions require external locking if underlying ordered list requires that
194 static CDS_CONSTEXPR const bool c_bExtractLockExternal = base_class::c_bExtractLockExternal;
197 typedef cds::container::split_list::implementation_tag implementation_tag;
202 typedef typename maker::cxx_node_allocator cxx_node_allocator;
203 typedef typename maker::node_type node_type;
207 /// pointer to extracted node
208 using exempt_ptr = cds::urcu::exempt_ptr< gc, node_type, value_type, typename maker::ordered_list_traits::disposer >;
212 template <typename Q, typename Func>
213 bool find_( Q& val, Func f )
215 return base_class::find( val, [&f]( node_type& item, Q& val ) { f(item.m_Value, val) ; } );
218 template <typename Q, typename Less, typename Func>
219 bool find_with_( Q& val, Less pred, Func f )
222 return base_class::find_with( val, typename maker::template predicate_wrapper<Less>::type(),
223 [&f]( node_type& item, Q& val ) { f(item.m_Value, val) ; } );
226 template <typename Q>
227 static node_type * alloc_node( Q const& v )
229 return cxx_node_allocator().New( v );
232 template <typename... Args>
233 static node_type * alloc_node( Args&&... args )
235 return cxx_node_allocator().MoveNew( std::forward<Args>(args)...);
238 static void free_node( node_type * pNode )
240 cxx_node_allocator().Delete( pNode );
243 struct node_disposer {
244 void operator()( node_type * pNode )
249 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
251 bool insert_node( node_type * pNode )
253 assert( pNode != nullptr );
254 scoped_node_ptr p(pNode);
256 if ( base_class::insert( *pNode ) ) {
268 \p IsConst - constness boolean flag
270 The forward iterator for a split-list has the following features:
271 - it has no post-increment operator
272 - it depends on underlying ordered list iterator
273 - it is safe to iterate only inside RCU critical section
274 - deleting an item pointed by the iterator can cause to deadlock
276 Therefore, the use of iterators in concurrent environment is not good idea.
277 Use it for debug purpose only.
279 template <bool IsConst>
280 class iterator_type: protected base_class::template iterator_type<IsConst>
283 typedef typename base_class::template iterator_type<IsConst> iterator_base_class;
284 friend class SplitListSet;
287 /// Value pointer type (const for const iterator)
288 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
289 /// Value reference type (const for const iterator)
290 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
298 iterator_type( iterator_type const& src )
299 : iterator_base_class( src )
304 explicit iterator_type( iterator_base_class const& src )
305 : iterator_base_class( src )
310 /// Dereference operator
311 value_ptr operator ->() const
313 return &(iterator_base_class::operator->()->m_Value);
316 /// Dereference operator
317 value_ref operator *() const
319 return iterator_base_class::operator*().m_Value;
323 iterator_type& operator ++()
325 iterator_base_class::operator++();
329 /// Assignment operator
330 iterator_type& operator = (iterator_type const& src)
332 iterator_base_class::operator=(src);
336 /// Equality operator
338 bool operator ==(iterator_type<C> const& i ) const
340 return iterator_base_class::operator==(i);
343 /// Equality operator
345 bool operator !=(iterator_type<C> const& i ) const
347 return iterator_base_class::operator!=(i);
352 /// Initializes split-ordered list of default capacity
354 The default capacity is defined in bucket table constructor.
355 See \p intrusive::split_list::expandable_bucket_table, \p intrusive::split_list::static_bucket_table
356 which selects by \p container::split_list::dynamic_bucket_table option.
362 /// Initializes split-ordered list
364 size_t nItemCount ///< estimated average of item count
365 , size_t nLoadFactor = 1 ///< load factor - average item count per bucket. Small integer up to 8, default is 1.
367 : base_class( nItemCount, nLoadFactor )
371 typedef iterator_type<false> iterator ; ///< Forward iterator
372 typedef iterator_type<true> const_iterator ; ///< Forward const iterator
374 /// Returns a forward iterator addressing the first element in a set
376 For empty set \code begin() == end() \endcode
380 return iterator( base_class::begin() );
383 /// Returns an iterator that addresses the location succeeding the last element in a set
385 Do not use the value returned by <tt>end</tt> function to access any item.
386 The returned value can be used only to control reaching the end of the set.
387 For empty set \code begin() == end() \endcode
391 return iterator( base_class::end() );
394 /// Returns a forward const iterator addressing the first element in a set
395 const_iterator begin() const
399 /// Returns a forward const iterator addressing the first element in a set
400 const_iterator cbegin() const
402 return const_iterator( base_class::cbegin() );
405 /// Returns an const iterator that addresses the location succeeding the last element in a set
406 const_iterator end() const
410 /// Returns an const iterator that addresses the location succeeding the last element in a set
411 const_iterator cend() const
413 return const_iterator( base_class::cend() );
419 The function creates a node with copy of \p val value
420 and then inserts the node created into the set.
422 The type \p Q should contain as minimum the complete key for the node.
423 The object of \p value_type should be constructible from a value of type \p Q.
424 In trivial case, \p Q is equal to \p value_type.
426 The function applies RCU lock internally.
428 Returns \p true if \p val is inserted into the set, \p false otherwise.
430 template <typename Q>
431 bool insert( Q const& val )
433 return insert_node( alloc_node( val ) );
438 The function allows to split creating of new item into two part:
439 - create item with key only
440 - insert new item into the set
441 - if inserting is success, calls \p f functor to initialize value-field of \p val.
443 The functor signature is:
445 void func( value_type& val );
447 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
448 \p val no any other changes could be made on this set's item by concurrent threads.
449 The user-defined functor is called only if the inserting is success.
451 The function applies RCU lock internally.
453 template <typename Q, typename Func>
454 bool insert( Q const& key, Func f )
456 scoped_node_ptr pNode( alloc_node( key ));
458 if ( base_class::insert( *pNode, [&f](node_type& node) { f( node.m_Value ) ; } )) {
465 /// Inserts data of type \p value_type created from \p args
467 Returns \p true if inserting successful, \p false otherwise.
469 The function applies RCU lock internally.
471 template <typename... Args>
472 bool emplace( Args&&... args )
474 return insert_node( alloc_node( std::forward<Args>(args)...));
477 /// Ensures that the \p val exists in the set
479 The operation performs inserting or changing data with lock-free manner.
481 If the \p val key not found in the set, then the new item created from \p val
482 is inserted into the set. Otherwise, the functor \p func is called with the item found.
483 The functor \p Func signature is:
486 void operator()( bool bNew, value_type& item, const Q& val );
491 - \p bNew - \p true if the item has been inserted, \p false otherwise
492 - \p item - item of the set
493 - \p val - argument \p val passed into the \p %ensure() function
495 The functor may change non-key fields of the \p item; however, \p func must guarantee
496 that during changing no any other modifications could be made on this item by concurrent threads.
498 The function applies RCU lock internally.
500 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
501 \p second is true if new item has been added or \p false if the item with \p key
502 already is in the set.
504 template <typename Q, typename Func>
505 std::pair<bool, bool> ensure( Q const& val, Func func )
507 scoped_node_ptr pNode( alloc_node( val ));
509 std::pair<bool, bool> bRet = base_class::ensure( *pNode,
510 [&func, &val]( bool bNew, node_type& item, node_type const& /*val*/ ) {
511 func( bNew, item.m_Value, val );
513 if ( bRet.first && bRet.second )
518 /// Deletes \p key from the set
519 /** \anchor cds_nonintrusive_SplitListSet_rcu_erase_val
521 Template parameter of type \p Q defines the key type searching in the list.
522 The set item comparator should be able to compare the values of type \p value_type
525 RCU \p synchronize method can be called. RCU should not be locked.
527 Return \p true if key is found and deleted, \p false otherwise
529 template <typename Q>
530 bool erase( Q const& key )
532 return base_class::erase( key );
535 /// Deletes the item from the set using \p pred predicate for searching
537 The function is an analog of \ref cds_nonintrusive_SplitListSet_rcu_erase_val "erase(Q const&)"
538 but \p pred is used for key comparing.
539 \p Less functor has the interface like \p std::less.
540 \p Less must imply the same element order as the comparator used for building the set.
542 template <typename Q, typename Less>
543 bool erase_with( Q const& key, Less pred )
546 return base_class::erase_with( key, typename maker::template predicate_wrapper<Less>::type() );
549 /// Deletes \p key from the set
550 /** \anchor cds_nonintrusive_SplitListSet_rcu_erase_func
552 The function searches an item with key \p key, calls \p f functor
553 and deletes the item. If \p key is not found, the functor is not called.
555 The functor \p Func interface:
558 void operator()(value_type const& val);
562 Template parameter of type \p Q defines the key type searching in the list.
563 The list item comparator should be able to compare the values of the type \p value_type
566 RCU \p synchronize method can be called. RCU should not be locked.
568 Return \p true if key is found and deleted, \p false otherwise
570 template <typename Q, typename Func>
571 bool erase( Q const& key, Func f )
573 return base_class::erase( key, [&f](node_type& node) { f( node.m_Value ); } );
576 /// Deletes the item from the set using \p pred predicate for searching
578 The function is an analog of \ref cds_nonintrusive_SplitListSet_rcu_erase_func "erase(Q const&, Func)"
579 but \p pred is used for key comparing.
580 \p Less functor has the interface like \p std::less.
581 \p Less must imply the same element order as the comparator used for building the set.
583 template <typename Q, typename Less, typename Func>
584 bool erase_with( Q const& key, Less pred, Func f )
587 return base_class::erase_with( key, typename maker::template predicate_wrapper<Less>::type(),
588 [&f](node_type& node) { f( node.m_Value ); } );
591 /// Extracts an item from the set
592 /** \anchor cds_nonintrusive_SplitListSet_rcu_extract
593 The function searches an item with key equal to \p key in the set,
594 unlinks it from the set, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
595 If the item with the key equal to \p key is not found the function returns an empty \p exempt_ptr.
597 @note The function does NOT call RCU read-side lock or synchronization,
598 and does NOT dispose the item found. It just excludes the item from the set
599 and returns a pointer to item found.
600 You should lock RCU before calling of the function, and you should synchronize RCU
601 outside the RCU lock to free extracted item
604 typedef cds::urcu::gc< general_buffered<> > rcu;
605 typedef cds::container::SplitListSet< rcu, Foo > splitlist_set;
607 splitlist_set theSet;
610 splitlist_set::exempt_ptr p;
612 // first, we should lock RCU
613 splitlist_set::rcu_lock lock;
615 // Now, you can apply extract function
616 // Note that you must not delete the item found inside the RCU lock
617 p = theSet.extract( 10 );
619 // do something with p
624 // We may safely release p here
625 // release() passes the pointer to RCU reclamation cycle
629 template <typename Q>
630 exempt_ptr extract( Q const& key )
632 return exempt_ptr( base_class::extract_( key, key_comparator() ));
635 /// Extracts an item from the set using \p pred predicate for searching
637 The function is an analog of \p extract(Q const&) but \p pred is used for key comparing.
638 \p Less functor has the interface like \p std::less.
639 \p pred must imply the same element order as the comparator used for building the set.
641 template <typename Q, typename Less>
642 exempt_ptr extract_with( Q const& key, Less pred )
645 return exempt_ptr( base_class::extract_with_( key, typename maker::template predicate_wrapper<Less>::type()));
648 /// Finds the key \p key
649 /** \anchor cds_nonintrusive_SplitListSet_rcu_find_func
651 The function searches the item with key equal to \p key and calls the functor \p f for item found.
652 The interface of \p Func functor is:
655 void operator()( value_type& item, Q& key );
658 where \p item is the item found, \p key is the <tt>find</tt> function argument.
660 The functor may change non-key fields of \p item. Note that the functor is only guarantee
661 that \p item cannot be disposed during functor is executing.
662 The functor does not serialize simultaneous access to the set's \p item. If such access is
663 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
665 Note the hash functor specified for class \p Traits template parameter
666 should accept a parameter of type \p Q that can be not the same as \p value_type.
668 The function makes RCU lock internally.
670 The function returns \p true if \p key is found, \p false otherwise.
672 template <typename Q, typename Func>
673 bool find( Q& key, Func f )
675 return find_( key, f );
678 template <typename Q, typename Func>
679 bool find( Q const& key, Func f )
681 return find_( key, f );
685 /// Finds the key \p key using \p pred predicate for searching
687 The function is an analog of \ref cds_nonintrusive_SplitListSet_rcu_find_func "find(Q&, Func)"
688 but \p pred is used for key comparing.
689 \p Less functor has the interface like \p std::less.
690 \p Less must imply the same element order as the comparator used for building the set.
692 template <typename Q, typename Less, typename Func>
693 bool find_with( Q& key, Less pred, Func f )
695 return find_with_( key, pred, f );
698 template <typename Q, typename Less, typename Func>
699 bool find_with( Q const& key, Less pred, Func f )
701 return find_with_( key, pred, f );
705 /// Finds the key \p key
706 /** \anchor cds_nonintrusive_SplitListSet_rcu_find_val
708 The function searches the item with key equal to \p key
709 and returns \p true if it is found, and \p false otherwise.
711 Note the hash functor specified for class \p Traits template parameter
712 should accept a parameter of type \p Q that can be not the same as \p value_type.
714 The function makes RCU lock internally.
716 template <typename Q>
717 bool find( Q const& key )
719 return base_class::find( key );
722 /// Finds the key \p key using \p pred predicate for searching
724 The function is an analog of \ref cds_nonintrusive_SplitListSet_rcu_find_val "find(Q const&)"
725 but \p pred is used for key comparing.
726 \p Less functor has the interface like \p std::less.
727 \p Less must imply the same element order as the comparator used for building the set.
729 template <typename Q, typename Less>
730 bool find_with( Q const& key, Less pred )
733 return base_class::find_with( key, typename maker::template predicate_wrapper<Less>::type() );
736 /// Finds the key \p key and return the item found
737 /** \anchor cds_nonintrusive_SplitListSet_rcu_get
738 The function searches the item with key equal to \p key and returns the pointer to item found.
739 If \p key is not found it returns \p nullptr.
741 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
743 RCU should be locked before call of this function.
744 Returned item is valid only while RCU is locked:
746 typedef cds::urcu::gc< general_buffered<> > rcu;
747 typedef cds::container::SplitListSet< rcu, Foo > splitlist_set;
748 splitlist_set theSet;
752 splitlist_set::rcu_lock lock;
754 foo * pVal = theSet.get( 5 );
759 // Unlock RCU by rcu_lock destructor
760 // pVal can be retired by disposer at any time after RCU has been unlocked
764 template <typename Q>
765 value_type * get( Q const& key )
767 node_type * pNode = base_class::get( key );
768 return pNode ? &pNode->m_Value : nullptr;
771 /// Finds the key \p key and return the item found
773 The function is an analog of \ref cds_nonintrusive_SplitListSet_rcu_get "get(Q const&)"
774 but \p pred is used for comparing the keys.
776 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
778 \p pred must imply the same element order as the comparator used for building the set.
780 template <typename Q, typename Less>
781 value_type * get_with( Q const& key, Less pred )
784 node_type * pNode = base_class::get_with( key, typename maker::template predicate_wrapper<Less>::type());
785 return pNode ? &pNode->m_Value : nullptr;
788 /// Clears the set (not atomic)
794 /// Checks if the set is empty
796 Emptiness is checked by item counting: if item count is zero then assume that the set is empty.
797 Thus, the correct item counting feature is an important part of split-list set implementation.
801 return base_class::empty();
804 /// Returns item count in the set
807 return base_class::size();
810 /// Returns internal statistics
811 stat const& statistics() const
813 return base_class::statistics();
816 }} // namespace cds::container
818 #endif // #ifndef CDSLIB_CONTAINER_SPLIT_LIST_SET_RCU_H