cds/intrusive/details/base.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_INTRUSIVE_DETAILS_BASE_H
   4 #define __CDS_INTRUSIVE_DETAILS_BASE_H
   5
   6 #include <cds/intrusive/details/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 \p 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     \anchor cds_intrusive_hook_tag
  25     \par Tags
  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.
  29     Example:
  30     \code
  31     struct tag1;
  32     cds::intrusive::treiber_stack::node< cds::gc::HP, tag<tag1> >
  33     \endcode
  34     If no tag is specified åðó default \p cds::opt::none will be used.
  35
  36     \anchor cds_intrusive_item_destroying
  37     \par Destroying items
  38
  39     It should be very careful when destroying an item removed from intrusive container.
  40     In other threads the references to popped item may exists some time after removing.
  41     To destroy the removed item in thread-safe manner you should call static function \p retire
  42     of garbage collector you use, for example:
  43     \code
  44     struct destroyer  {
  45         void operator ()( my_type * p )
  46         {
  47             delete p;
  48         }
  49     };
  50
  51     typedef cds::intrusive::TreiberStack< cds::gc::HP, my_type, cds::opt::disposer< destroyer > > stack;
  52     stack s;
  53
  54     // ....
  55
  56     my_type * p = s.pop();
  57
  58     if ( p ) {
  59         // It is wrong
  60         // delete p;
  61
  62         // It is correct
  63         cds::gc:HP::retire< destroyer >( p );
  64     }
  65     \endcode
  66     The situation becomes even more complicated when you want store items in different intrusive containers.
  67     In this case the best way is using reference counting:
  68     \code
  69     struct my_type {
  70         ...
  71         std::atomic<unsigned int> nRefCount;
  72
  73         my_type()
  74             : nRefCount(0)
  75         {}
  76     };
  77
  78     struct destroyer  {
  79         void operator ()( my_type * p )
  80         {
  81             if ( --p->nRefCount == 0 )
  82                 delete p    ;   // delete only after no reference pointing to p
  83         }
  84     };
  85
  86     typedef cds::intrusive::TreiberStack< cds::gc::HP, my_type, cds::opt::disposer< destroyer > > stack;
  87     typedef cds::intrusive::MSQueue< cds::gc::HP, my_type, cds::opt::disposer< destroyer > > queue;
  88     stack s;
  89     queue q;
  90
  91     my_type * v = new my_type();
  92
  93     v.nRefCount++   ; // increment counter before pushing the item to the stack
  94     s.push(v);
  95
  96     v.nRefCount++   ; // increment counter before pushing the item to the queue
  97     q.push(v);
  98
  99     // ....
 100
 101     my_type * ps = s.pop();
 102     if ( ps ) {
 103         // It is wrong
 104         // delete ps;
 105
 106         // It is correct
 107         cds::gc:HP::retire< destroyer >( ps );
 108     }
 109
 110     my_type * pq = q.pop();
 111     if ( pq ) {
 112         // It is wrong
 113         // delete pq;
 114
 115         // It is correct
 116         cds::gc:HP::retire< destroyer >( pq );
 117     }
 118     \endcode
 119     Violation of these rules may lead to a crash.
 120
 121     \par Intrusive containers and Hazard Pointer-like garbage collectors
 122
 123     If you develop your intrusive container based on <b>libcds</b> library framework, you should
 124     take in the account the following.
 125     The main idea of garbage collectors (GC) based on Hazard Pointer schema is protecting a shared pointer
 126     by publishing it as a "hazard" one i.e. as a pointer that is changing at the current time and cannot be
 127     deleted at this moment. In intrusive container paradigm, the pointer to the node of the container
 128     and the pointer to the item stored in the container are not equal in the general case.
 129     However, any pointer to the node should be castable to the appropriate pointer to the container's item.
 130     In general, any item can be placed to some different intrusive containers simultaneously,
 131     and each of those container holds a unique pointer to its node that refers to the same item.
 132     When we protect a pointer, we want to protect an <b>item</b> pointer that is the invariant
 133     for any container stored that item. In your intrusive container, instead of protecting by GC's guard a pointer to an node
 134     you should convert it to the pointer to the item and then protect resulting item pointer.
 135     Otherwise an unpredictable result may occur.
 136 */
 137 namespace intrusive {
 138
 139     /// @defgroup cds_intrusive_containers Intrusive containers
 140     /** @defgroup cds_intrusive_helper Helper structs for intrusive containers
 141         @ingroup cds_intrusive_containers
 142     */
 143     /** @defgroup cds_intrusive_stack Stack
 144         @ingroup cds_intrusive_containers
 145     */
 146     /** @defgroup cds_intrusive_queue Queue
 147         @ingroup cds_intrusive_containers
 148     */
 149     /** @defgroup cds_intrusive_priority_queue Priority queue
 150         @ingroup cds_intrusive_containers
 151     */
 152     /** @defgroup cds_intrusive_deque Deque
 153         @ingroup cds_intrusive_containers
 154     */
 155     /** @defgroup cds_intrusive_map Set
 156         @ingroup cds_intrusive_containers
 157     */
 158     /** @defgroup cds_intrusive_tree Tree
 159         @ingroup cds_intrusive_containers
 160     */
 161     /** @defgroup cds_intrusive_list List
 162         @ingroup cds_intrusive_containers
 163     */
 164
 165 }} // namespace cds::intrusuve
 166
 167 #endif  // #ifndef __CDS_INTRUSIVE_DETAILS_BASE_H