Removed trailing spaces
[libcds.git] / cds / intrusive / details / base.h
1 /*
2     This file is a part of libcds - Concurrent Data Structures library
3
4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
5
6     Source code repo: http://github.com/khizmax/libcds/
7     Download: http://sourceforge.net/projects/libcds/files/
8
9     Redistribution and use in source and binary forms, with or without
10     modification, are permitted provided that the following conditions are met:
11
12     * Redistributions of source code must retain the above copyright notice, this
13       list of conditions and the following disclaimer.
14
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.
18
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.
29 */
30
31 #ifndef CDSLIB_INTRUSIVE_DETAILS_BASE_H
32 #define CDSLIB_INTRUSIVE_DETAILS_BASE_H
33
34 #include <cds/intrusive/details/node_traits.h>
35 #include <cds/details/allocator.h>
36 #include <cds/algo/backoff_strategy.h>
37
38 namespace cds {
39
40 /// Intrusive containers
41 /**
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
46
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.
51
52     \anchor cds_intrusive_hook_tag
53     \par Tags
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.
57     Example:
58     \code
59     struct tag1;
60     cds::intrusive::treiber_stack::node< cds::gc::HP, tag<tag1> >
61     \endcode
62     If no tag is specified the default \p cds::opt::none will be used.
63
64     \anchor cds_intrusive_item_creating
65     \par Inserting items
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,
68     for example:
69     \code
70     template <typename Q, typename Func>
71     bool insert( Q& key, Func f );
72
73     template <typename Q, typename Func>
74     std::pair<bool, bool> update( Q& key, Func f, bool bAllowInsert = true );
75     \endcode
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
77     \p key.
78
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:
81     \code
82     void f( bool bNew, item_type& item, Q& key );
83     \endcode
84     where \p bNew is a flag to indicate whether \p item is a new created node or not.
85
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:
90     \code
91         // Suppose, Foo is a complex structure with int key field
92         SomeContainer<Foo> q;
93
94         Thread 1                                  Thread 2
95
96         q.insert( Foo(5),                         q.find( 5, []( Foo& item ) {
97             []( Foo& item ){                         // access to item fields
98                // complex initialization             ...
99                item.f1 = ...;                     });
100                ...
101             });
102     \endcode
103     Execute sequence:
104     \code
105         Find 5 in the container.
106         Key 5 is not found
107         Create a new item                         Find key 5
108             with calling Foo(5) ctor
109         Insert the new item
110                                                   The key 5 is found -
111                                                      call the functor     (!)
112         Perform complex
113            initialization -
114            call the functor
115     \endcode
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.
120
121     \p update() member function race. Suppose, thread 1 and thread 2 perform
122     the
123     following code:
124     \code
125         q.update( 5, []( bool bNew, Foo& item, int  arg )
126            {
127               // bNew: true if the new element has been created
128               //       false otherwise
129               if ( bNew ) {
130                  // initialize item
131                  item.f1=...;
132                  //...
133               }
134               else {
135                  // do some work
136                  if ( !item.f1 )
137                     item.f1 = ...;
138                  else {
139                    //...
140                  }
141                  //...
142               }
143            }
144         );
145     \endcode
146     Execute sequence:
147     \code
148         Thread 1                                  Thread 2
149         key 5 not found
150         insert new item Foo(5)                    Find 5
151                                                   Key 5 found
152                                                   call the functor with
153                                                      bNew = false        (!)
154         call the functor with
155            bNew = true
156     \endcode
157     (!): Thread 2 executes its functor on incomplete initialized item.
158
159     To protect your code from such races you can use some item-level synchronization,
160     for example:
161     \code
162     struct Foo {
163        spinlock lock;       // item-level lock
164        bool initialized = false;    // initialization flag
165        // other fields
166        // ....
167     };
168
169     q.update( 5, []( bool bNew, Foo& item, int  arg )
170         {
171             // Lock access to the item
172             std::unique_lock( item.lock );
173
174             if ( !item.initialized ) {
175                 // initialize item
176                 item.f1=...;
177                 //...
178                 item.initialized = true; // mark the item as initialized
179             }
180             else {
181                 // do some work
182                 if ( !item.f1 )
183                     item.f1 = ...;
184                 else {
185                     //...
186                 }
187                 //...
188             }
189         }
190     );
191     \endcode
192     If the item-level synchronization is not suitable, you should not use any inserting member function
193     with post-insert functor argument.
194
195     \anchor cds_intrusive_item_destroying
196     \par Destroying items
197
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:
202     \code
203     struct destroyer  {
204         void operator ()( my_type * p )
205         {
206             delete p;
207         }
208     };
209
210     typedef cds::intrusive::TreiberStack< cds::gc::HP, my_type, cds::opt::disposer< destroyer > > stack;
211     stack s;
212
213     // ....
214
215     my_type * p = s.pop();
216
217     if ( p ) {
218         // It is wrong
219         // delete p;
220
221         // It is correct
222         cds::gc:HP::retire< destroyer >( p );
223     }
224     \endcode
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:
227     \code
228     struct my_type {
229         ...
230         std::atomic<unsigned int> nRefCount;
231
232         my_type()
233             : nRefCount(0)
234         {}
235     };
236
237     struct destroyer  {
238         void operator ()( my_type * p )
239         {
240             if ( --p->nRefCount == 0 )
241                 delete p    ;   // delete only after no reference pointing to p
242         }
243     };
244
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;
247     stack s;
248     queue q;
249
250     my_type * v = new my_type();
251
252     v.nRefCount++   ; // increment counter before pushing the item to the stack
253     s.push(v);
254
255     v.nRefCount++   ; // increment counter before pushing the item to the queue
256     q.push(v);
257
258     // ....
259
260     my_type * ps = s.pop();
261     if ( ps ) {
262         // It is wrong
263         // delete ps;
264
265         // It is correct
266         cds::gc:HP::retire< destroyer >( ps );
267     }
268
269     my_type * pq = q.pop();
270     if ( pq ) {
271         // It is wrong
272         // delete pq;
273
274         // It is correct
275         cds::gc:HP::retire< destroyer >( pq );
276     }
277     \endcode
278     Violation of these rules may lead to a crash.
279
280     \par Intrusive containers and Hazard Pointer-like garbage collectors
281
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.
295 */
296 namespace intrusive {
297
298     /// @defgroup cds_intrusive_containers Intrusive containers
299     /** @defgroup cds_intrusive_helper Helper structs for intrusive containers
300         @ingroup cds_intrusive_containers
301     */
302     /** @defgroup cds_intrusive_stack Stack
303         @ingroup cds_intrusive_containers
304     */
305     /** @defgroup cds_intrusive_queue Queue
306         @ingroup cds_intrusive_containers
307     */
308     /** @defgroup cds_intrusive_priority_queue Priority queue
309         @ingroup cds_intrusive_containers
310     */
311     /** @defgroup cds_intrusive_deque Deque
312         @ingroup cds_intrusive_containers
313     */
314     /** @defgroup cds_intrusive_map Set
315         @ingroup cds_intrusive_containers
316     */
317     /** @defgroup cds_intrusive_tree Tree
318         @ingroup cds_intrusive_containers
319     */
320     /** @defgroup cds_intrusive_list List
321         @ingroup cds_intrusive_containers
322     */
323     /** @defgroup cds_intrusive_freelist Free-list
324         @ingroup cds_intrusive_containers
325     */
326
327     //@cond
328     class iterable_list_tag
329     {};
330
331     template <typename List>
332     struct is_iterable_list: public std::is_base_of< iterable_list_tag, List>
333     {};
334     //@endcond
335
336 }} // namespace cds::intrusuve
337
338 #endif  // #ifndef CDSLIB_INTRUSIVE_DETAILS_BASE_H