cds/intrusive/base.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_INTRUSIVE_BASE_H
   4 #define __CDS_INTRUSIVE_BASE_H
   5
   6 #include <cds/intrusive/node_traits.h>
   7 #include <cds/details/allocator.h>
   8 #include <cds/algo/backoff_strategy.h>
   9
  10 namespace cds {
  11
  12 /// Intrusive containers
  13 /**
  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
  18
  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.
  23
  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.
  27
  28     \anchor cds_intrusive_item_destroying
  29     \par Destroying items
  30
  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:
  35     \code
  36     struct destroyer  {
  37         void operator ()( my_type * p )
  38         {
  39             delete p;
  40         }
  41     };
  42
  43     typedef cds::intrusive::TreiberStack< cds::gc::HP, my_type, cds::opt::disposer< destroyer > > stack;
  44     stack s;
  45
  46     // ....
  47
  48     my_type * p = s.pop();
  49
  50     if ( p ) {
  51         // It is wrong
  52         // delete p;
  53
  54         // It is correct
  55         cds::gc:HP::retire< destroyer >( p );
  56     }
  57     \endcode
  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:
  60     \code
  61     struct my_type {
  62         ...
  63         std::atomic<unsigned int> nRefCount;
  64
  65         my_type()
  66             : nRefCount(0)
  67         {}
  68     };
  69
  70     struct destroyer  {
  71         void operator ()( my_type * p )
  72         {
  73             if ( --p->nRefCount == 0 )
  74                 delete p    ;   // delete only after no reference pointing to p
  75         }
  76     };
  77
  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;
  80     stack s;
  81     queue q;
  82
  83     my_type * v = new my_type();
  84
  85     v.nRefCount++   ; // increment counter before pushing the item to the stack
  86     s.push(v);
  87
  88     v.nRefCount++   ; // increment counter before pushing the item to the queue
  89     q.push(v);
  90
  91     // ....
  92
  93     my_type * ps = s.pop();
  94     if ( ps ) {
  95         // It is wrong
  96         // delete ps;
  97
  98         // It is correct
  99         cds::gc:HP::retire< destroyer >( ps );
 100     }
 101
 102     my_type * pq = q.pop();
 103     if ( pq ) {
 104         // It is wrong
 105         // delete pq;
 106
 107         // It is correct
 108         cds::gc:HP::retire< destroyer >( pq );
 109     }
 110     \endcode
 111     Violation of these rules may lead to a crash.
 112
 113     \par Intrusive containers and Hazard Pointer-like garbage collectors
 114
 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.
 128
 129 */
 130 namespace intrusive {
 131
 132     /// @defgroup cds_intrusive_containers Intrusive containers
 133     /** @defgroup cds_intrusive_helper Helper structs for intrusive containers
 134         @ingroup cds_intrusive_containers
 135     */
 136     /** @defgroup cds_intrusive_stack Stack
 137         @ingroup cds_intrusive_containers
 138     */
 139     /** @defgroup cds_intrusive_queue Queue
 140         @ingroup cds_intrusive_containers
 141     */
 142     /** @defgroup cds_intrusive_priority_queue Priority queue
 143         @ingroup cds_intrusive_containers
 144     */
 145     /** @defgroup cds_intrusive_deque Deque
 146         @ingroup cds_intrusive_containers
 147     */
 148     /** @defgroup cds_intrusive_map Set
 149         @ingroup cds_intrusive_containers
 150     */
 151     /** @defgroup cds_intrusive_tree Tree
 152         @ingroup cds_intrusive_containers
 153     */
 154     /** @defgroup cds_intrusive_list List
 155         @ingroup cds_intrusive_containers
 156     */
 157
 158 }} // namespace cds::intrusuve
 159
 160 #endif  // #ifndef __CDS_INTRUSIVE_BASE_H