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 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 Restriction for Gidenstam's garbage collector cds::gc::HRC:
25 the Gidenstam's garbage collector makes additional requirements to type of item in intrusive container.
26 Therefore, for this GC only \p base_hook is allowed as the value of opt::hook option.
28 \anchor cds_intrusive_item_destroying
31 It should be very careful when destroying an item removed from intrusive container.
32 In other threads the references to popped item may exists some time after removing.
33 To destroy the removed item in thread-safe manner you should call static function \p retire
34 of garbage collector you use, for example:
37 void operator ()( my_type * p )
43 typedef cds::intrusive::TreiberStack< cds::gc::HP, my_type, cds::opt::disposer< destroyer > > stack;
48 my_type * p = s.pop();
55 cds::gc:HP::retire< destroyer >( p );
58 The situation becomes even more complicated when you want store items in different intrusive containers.
59 In this case the best way is using reference counting:
63 std::atomic<unsigned int> nRefCount;
71 void operator ()( my_type * p )
73 if ( --p->nRefCount == 0 )
74 delete p ; // delete only after no reference pointing to p
78 typedef cds::intrusive::TreiberStack< cds::gc::HP, my_type, cds::opt::disposer< destroyer > > stack;
79 typedef cds::intrusive::MSQueue< cds::gc::HP, my_type, cds::opt::disposer< destroyer > > queue;
83 my_type * v = new my_type();
85 v.nRefCount++ ; // increment counter before pushing the item to the stack
88 v.nRefCount++ ; // increment counter before pushing the item to the queue
93 my_type * ps = s.pop();
99 cds::gc:HP::retire< destroyer >( ps );
102 my_type * pq = q.pop();
108 cds::gc:HP::retire< destroyer >( pq );
111 Violation of these rules may lead to a crash.
113 \par Intrusive containers and Hazard Pointer-like garbage collectors
115 If you develop your intrusive container based on <b>libcds</b> library framework, you should
116 take in the account the following.
117 The main idea of garbage collectors (GC) based on Hazard Pointer schema is protecting a shared pointer
118 by publishing it as a "hazard" one i.e. as a pointer that is changing at the current time and cannot be
119 deleted at this moment. In intrusive container paradigm, the pointer to the node of the container
120 and the pointer to the item stored in the container are not equal in the general case.
121 However, any pointer to the node should be castable to the appropriate pointer to the container's item.
122 In general, any item can be placed to some different intrusive containers simultaneously,
123 and each of those container holds a unique pointer to its node that refers to the same item.
124 When we protect a pointer, we want to protect an <b>item</b> pointer that is the invariant
125 for any container stored that item. In your intrusive container, instead of protecting by GC's guard a pointer to an node
126 you should convert it to the pointer to the item and then protect resulting item pointer.
127 Otherwise an unpredictable result may occur.
130 namespace intrusive {
132 /// @defgroup cds_intrusive_containers Intrusive containers
133 /** @defgroup cds_intrusive_helper Helper structs for intrusive containers
134 @ingroup cds_intrusive_containers
136 /** @defgroup cds_intrusive_stack Stack
137 @ingroup cds_intrusive_containers
139 /** @defgroup cds_intrusive_queue Queue
140 @ingroup cds_intrusive_containers
142 /** @defgroup cds_intrusive_priority_queue Priority queue
143 @ingroup cds_intrusive_containers
145 /** @defgroup cds_intrusive_deque Deque
146 @ingroup cds_intrusive_containers
148 /** @defgroup cds_intrusive_map Set
149 @ingroup cds_intrusive_containers
151 /** @defgroup cds_intrusive_tree Tree
152 @ingroup cds_intrusive_containers
154 /** @defgroup cds_intrusive_list List
155 @ingroup cds_intrusive_containers
158 }} // namespace cds::intrusuve
160 #endif // #ifndef __CDS_INTRUSIVE_DETAILS_BASE_H