3 #ifndef __CDS_INTRUSIVE_DETAILS_BASE_H
4 #define __CDS_INTRUSIVE_DETAILS_BASE_H
6 #include <cds/intrusive/details/node_traits.h>
7 #include <cds/details/allocator.h>
8 #include <cds/algo/backoff_strategy.h>
12 /// Intrusive containers
14 @ingroup cds_intrusive_containers
15 The namespace cds::intrusive contains intrusive lock-free containers.
16 The idea comes from \p boost::intrusive library, see http://boost.org/doc/ as a good introduction to intrusive approach.
17 The intrusive containers of libcds library is developed as close to \p boost::intrusive
19 In terms of lock-free approach, the main advantage of intrusive containers is
20 that no memory allocation is performed to maintain container items.
21 However, additional requirements is imposed for types and values that can be stored in intrusive container.
22 See the container documentation for details.
24 \anchor cds_intrusive_hook_tag
26 Many hooks and nodes for intrusive containers contain template argument \p Tag.
27 This argument serves as a tag, so you can derive from more than one container's node and hence put an object in multiple intrusive containers
28 at the same time. An incomplete type can serve as a tag. If you specify two hooks, you must specify a different tag for each one.
32 cds::intrusive::treiber_stack::node< cds::gc::HP, tag<tag1> >
34 If no tag is specified the default \p cds::opt::none will be used.
36 \anchor cds_intrusive_item_creating
38 Many intrusive and non-intrusive (standard-like) containers in the library have the member functions
39 that take an functor argument to initialize the inserted item after it has been successfully inserted,
42 template <typename Q, typename Func>
43 bool insert( Q& key, Func f );
45 template <typename Q, typename Func>
46 std::pair<bool, bool> ensure( Q& key, Func f );
48 The first member function calls \p f functor iif an new item has been inserted. The functor takes two parameter: a reference to inserted item and
51 The second member function, \p ensure, allows to insert a new item to the container if \p key is not found, or to find the item with \p key and
52 to perform some action with it. The \p f signature is:
54 void f( bool bNew, item_type& item, Q& key );
56 where \p bNew is a flag to indicate whether \p item is a new created node or not.
58 Such functions should be used with caution in multi-threaded environment
59 since they can cause races. The library does not synchronize access
60 to container's items, so many threads can access to one item simultaneously.
61 For example, for \p insert member function the following race is possible:
63 // Suppose, Foo is a complex structure with int key field
68 q.insert( Foo(5), q.find( 5, []( Foo& item ) {
69 []( Foo& item ){ // access to item fields
70 // complex initialization ...
77 Find 5 in the container.
79 Create a new item Find key 5
80 with calling Foo(5) ctor
88 (!): Thread 2 found the key and call its functor on incomplete initialized item.
89 Simultaneous access to the item also is possible. In this case Thread 1 is
90 initializing the item, thread 2 is reading (or writing) the item's fields.
91 In any case, Thread 2 can read uninitialized or incomplete initialized fields.
93 \p ensure member function race. Suppose, thread 1 and thread 2 perform
97 q.ensure( 5, []( bool bNew, Foo& item, int arg )
99 // bNew: true if the new element has been created
122 insert new item Foo(5) Find 5
124 call the functor with
126 call the functor with
129 (!): Thread 2 executes its functor on incomplete initialized item.
131 To protect your code from such races you can use some item-level synchronization,
135 spinlock lock; // item-level lock
136 bool initialized = false; // initialization flag
141 q.ensure( 5, []( bool bNew, Foo& item, int arg )
143 // Lock access to the item
144 std::unique_lock( item.lock );
146 if ( !item.initialized ) {
150 item.initialized = true; // mark the item as initialized
164 If the item-level synchronization is not suitable, you should not use any inserting member function
165 with post-insert functor argument.
167 \anchor cds_intrusive_item_destroying
168 \par Destroying items
170 It should be very careful when destroying an item removed from intrusive container.
171 In other threads the references to popped item may exists some time after removing.
172 To destroy the removed item in thread-safe manner you should call static function \p retire
173 of garbage collector you use, for example:
176 void operator ()( my_type * p )
182 typedef cds::intrusive::TreiberStack< cds::gc::HP, my_type, cds::opt::disposer< destroyer > > stack;
187 my_type * p = s.pop();
194 cds::gc:HP::retire< destroyer >( p );
197 The situation becomes even more complicated when you want store items in different intrusive containers.
198 In this case the best way is using reference counting:
202 std::atomic<unsigned int> nRefCount;
210 void operator ()( my_type * p )
212 if ( --p->nRefCount == 0 )
213 delete p ; // delete only after no reference pointing to p
217 typedef cds::intrusive::TreiberStack< cds::gc::HP, my_type, cds::opt::disposer< destroyer > > stack;
218 typedef cds::intrusive::MSQueue< cds::gc::HP, my_type, cds::opt::disposer< destroyer > > queue;
222 my_type * v = new my_type();
224 v.nRefCount++ ; // increment counter before pushing the item to the stack
227 v.nRefCount++ ; // increment counter before pushing the item to the queue
232 my_type * ps = s.pop();
238 cds::gc:HP::retire< destroyer >( ps );
241 my_type * pq = q.pop();
247 cds::gc:HP::retire< destroyer >( pq );
250 Violation of these rules may lead to a crash.
252 \par Intrusive containers and Hazard Pointer-like garbage collectors
254 If you develop your intrusive container based on <b>libcds</b> library framework, you should
255 take in the account the following.
256 The main idea of garbage collectors (GC) based on Hazard Pointer schema is protecting a shared pointer
257 by publishing it as a "hazard" one i.e. as a pointer that is changing at the current time and cannot be
258 deleted at this moment. In intrusive container paradigm, the pointer to the node of the container
259 and the pointer to the item stored in the container are not equal in the general case.
260 However, any pointer to the node should be castable to the appropriate pointer to the container's item.
261 In general, any item can be placed to some different intrusive containers simultaneously,
262 and each of those container holds a unique pointer to its node that refers to the same item.
263 When we protect a pointer, we want to protect an <b>item</b> pointer that is the invariant
264 for any container stored that item. In your intrusive container, instead of protecting by GC's guard a pointer to an node
265 you should convert it to the pointer to the item and then protect resulting item pointer.
266 Otherwise an unpredictable result may occur.
268 namespace intrusive {
270 /// @defgroup cds_intrusive_containers Intrusive containers
271 /** @defgroup cds_intrusive_helper Helper structs for intrusive containers
272 @ingroup cds_intrusive_containers
274 /** @defgroup cds_intrusive_stack Stack
275 @ingroup cds_intrusive_containers
277 /** @defgroup cds_intrusive_queue Queue
278 @ingroup cds_intrusive_containers
280 /** @defgroup cds_intrusive_priority_queue Priority queue
281 @ingroup cds_intrusive_containers
283 /** @defgroup cds_intrusive_deque Deque
284 @ingroup cds_intrusive_containers
286 /** @defgroup cds_intrusive_map Set
287 @ingroup cds_intrusive_containers
289 /** @defgroup cds_intrusive_tree Tree
290 @ingroup cds_intrusive_containers
292 /** @defgroup cds_intrusive_list List
293 @ingroup cds_intrusive_containers
296 }} // namespace cds::intrusuve
298 #endif // #ifndef __CDS_INTRUSIVE_DETAILS_BASE_H