2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
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_INTRUSIVE_DETAILS_BASE_H
32 #define CDSLIB_INTRUSIVE_DETAILS_BASE_H
34 #include <cds/intrusive/details/node_traits.h>
35 #include <cds/details/allocator.h>
36 #include <cds/algo/backoff_strategy.h>
40 /// Intrusive containers
42 @ingroup cds_intrusive_containers
43 The namespace \p cds::intrusive contains intrusive lock-free containers.
44 The idea comes from \p boost::intrusive library, see http://boost.org/doc/ as a good introduction to intrusive approach.
45 The intrusive containers of libcds library is developed as close to \p boost::intrusive
47 In terms of lock-free approach, the main advantage of intrusive containers is
48 that no memory allocation is performed to maintain container elements.
49 However, additional requirements are imposed for types and values that can be stored in intrusive container.
50 See the container documentation for details.
52 \anchor cds_intrusive_hook_tag
54 Many hooks and nodes for intrusive containers contain template argument \p Tag.
55 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
56 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.
60 cds::intrusive::treiber_stack::node< cds::gc::HP, tag<tag1> >
62 If no tag is specified the default \p cds::opt::none will be used.
64 \anchor cds_intrusive_item_creating
66 Many intrusive and non-intrusive (standard-like) containers in the library have the member functions
67 that take a functor argument to initialize the inserted item after it has been successfully inserted,
70 template <typename Q, typename Func>
71 bool insert( Q& key, Func f );
73 template <typename Q, typename Func>
74 std::pair<bool, bool> update( Q& key, Func f, bool bAllowInsert = true );
76 The first member function calls \p f functor iif a new item has been inserted. The functor takes two parameter: a reference to inserted item and
79 The second member function, \p update(), allows to insert a new item to the container if \p key is not found, or to find the item with \p key and
80 to perform some action with it. The \p f signature is:
82 void f( bool bNew, item_type& item, Q& key );
84 where \p bNew is a flag to indicate whether \p item is a new created node or not.
86 Such functions should be used with caution in multi-threaded environment
87 since they can cause races. The library does not synchronize access
88 to container's items, so many threads can access to one item simultaneously.
89 For example, for \p insert member function the following race is possible:
91 // Suppose, Foo is a complex structure with int key field
96 q.insert( Foo(5), q.find( 5, []( Foo& item ) {
97 []( Foo& item ){ // access to item fields
98 // complex initialization ...
105 Find 5 in the container.
107 Create a new item Find key 5
108 with calling Foo(5) ctor
116 (!): Thread 2 found the key and call its functor on incomplete initialized item.
117 Simultaneous access to the item also is possible. In this case Thread 1 is
118 initializing the item, thread 2 is reading (or writing) the item's fields.
119 In any case, Thread 2 can read uninitialized or incomplete initialized fields.
121 \p update() member function race. Suppose, thread 1 and thread 2 perform
125 q.update( 5, []( bool bNew, Foo& item, int arg )
127 // bNew: true if the new element has been created
150 insert new item Foo(5) Find 5
152 call the functor with
154 call the functor with
157 (!): Thread 2 executes its functor on incomplete initialized item.
159 To protect your code from such races you can use some item-level synchronization,
163 spinlock lock; // item-level lock
164 bool initialized = false; // initialization flag
169 q.update( 5, []( bool bNew, Foo& item, int arg )
171 // Lock access to the item
172 std::unique_lock( item.lock );
174 if ( !item.initialized ) {
178 item.initialized = true; // mark the item as initialized
192 If the item-level synchronization is not suitable, you should not use any inserting member function
193 with post-insert functor argument.
195 \anchor cds_intrusive_item_destroying
196 \par Destroying items
198 It should be very careful when destroying an item removed from intrusive container.
199 In other threads the references to popped item may exists some time after removing.
200 To destroy the removed item in thread-safe manner you should call static function \p retire
201 of garbage collector you use, for example:
204 void operator ()( my_type * p )
210 typedef cds::intrusive::TreiberStack< cds::gc::HP, my_type, cds::opt::disposer< destroyer > > stack;
215 my_type * p = s.pop();
222 cds::gc:HP::retire< destroyer >( p );
225 The situation becomes even more complicated when you want store items in different intrusive containers.
226 In this case the best way is using reference counting:
230 std::atomic<unsigned int> nRefCount;
238 void operator ()( my_type * p )
240 if ( --p->nRefCount == 0 )
241 delete p ; // delete only after no reference pointing to p
245 typedef cds::intrusive::TreiberStack< cds::gc::HP, my_type, cds::opt::disposer< destroyer > > stack;
246 typedef cds::intrusive::MSQueue< cds::gc::HP, my_type, cds::opt::disposer< destroyer > > queue;
250 my_type * v = new my_type();
252 v.nRefCount++ ; // increment counter before pushing the item to the stack
255 v.nRefCount++ ; // increment counter before pushing the item to the queue
260 my_type * ps = s.pop();
266 cds::gc:HP::retire< destroyer >( ps );
269 my_type * pq = q.pop();
275 cds::gc:HP::retire< destroyer >( pq );
278 Violation of these rules may lead to a crash.
280 \par Intrusive containers and Hazard Pointer-like garbage collectors
282 If you develop your intrusive container based on <b>libcds</b> library framework, you should
283 take in the account the following.
284 The main idea of garbage collectors (GC) based on Hazard Pointer schema is protecting a shared pointer
285 by publishing it as a "hazard" i.e. as a pointer that is changing at the current time and cannot be
286 deleted at this moment. In intrusive container paradigm, the pointer to a node of the container
287 and the pointer to a item stored in the container are not equal in the general case.
288 However, any pointer to node should be castable to appropriate pointer to container's item.
289 In general, any item can be placed to two or more intrusive containers simultaneously,
290 and each of those container holds an unique pointer to its node that refers to the same item.
291 When we protect a pointer, we want to protect an <b>item</b> pointer that is the invariant
292 for any container stored that item. In your intrusive container, instead of protecting by GC's guard a pointer to node
293 you should cast it to the pointer to item and then protect that item pointer.
294 Otherwise an unpredictable result may occur.
296 namespace intrusive {
298 /// @defgroup cds_intrusive_containers Intrusive containers
299 /** @defgroup cds_intrusive_helper Helper structs for intrusive containers
300 @ingroup cds_intrusive_containers
302 /** @defgroup cds_intrusive_stack Stack
303 @ingroup cds_intrusive_containers
305 /** @defgroup cds_intrusive_queue Queue
306 @ingroup cds_intrusive_containers
308 /** @defgroup cds_intrusive_priority_queue Priority queue
309 @ingroup cds_intrusive_containers
311 /** @defgroup cds_intrusive_deque Deque
312 @ingroup cds_intrusive_containers
314 /** @defgroup cds_intrusive_map Set
315 @ingroup cds_intrusive_containers
317 /** @defgroup cds_intrusive_tree Tree
318 @ingroup cds_intrusive_containers
320 /** @defgroup cds_intrusive_list List
321 @ingroup cds_intrusive_containers
323 /** @defgroup cds_intrusive_freelist Free-list
324 @ingroup cds_intrusive_containers
328 class iterable_list_tag
331 template <typename List>
332 struct is_iterable_list: public std::is_base_of< iterable_list_tag, List>
336 }} // namespace cds::intrusuve
338 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_BASE_H