cds/intrusive/details/lazy_list_base.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_INTRUSIVE_DETAILS_LAZY_LIST_BASE_H
   4 #define __CDS_INTRUSIVE_DETAILS_LAZY_LIST_BASE_H
   5
   6 #include <cds/intrusive/details/base.h>
   7 #include <cds/opt/compare.h>
   8 #include <cds/details/marked_ptr.h>
   9 #include <cds/details/make_const_type.h>
  10 #include <cds/lock/spinlock.h>
  11 #include <cds/urcu/options.h>
  12
  13 namespace cds { namespace intrusive {
  14
  15     /// LazyList ordered list related definitions
  16     /** @ingroup cds_intrusive_helper
  17     */
  18     namespace lazy_list {
  19         /// Lazy list node
  20         /**
  21             Template parameters:
  22             - GC - garbage collector
  23             - Lock - lock type. Default is \p cds::lock::Spin
  24             - Tag - a \ref cds_intrusive_hook_tag "tag"
  25         */
  26         template <
  27             class GC
  28             ,typename Lock =  cds::lock::Spin
  29             ,typename Tag = opt::none
  30         >
  31         struct node
  32         {
  33             typedef GC      gc          ;   ///< Garbage collector
  34             typedef Lock    lock_type   ;   ///< Lock type
  35             typedef Tag     tag         ;   ///< tag
  36
  37             typedef cds::details::marked_ptr<node, 1>   marked_ptr         ;   ///< marked pointer
  38             typedef typename gc::template atomic_marked_ptr< marked_ptr>     atomic_marked_ptr   ;   ///< atomic marked pointer specific for GC
  39
  40             atomic_marked_ptr   m_pNext; ///< pointer to the next node in the list + logical deletion mark
  41             mutable lock_type   m_Lock;  ///< Node lock
  42
  43             /// Checks if node is marked
  44             bool is_marked() const
  45             {
  46                 return m_pNext.load(atomics::memory_order_relaxed).bits() != 0;
  47             }
  48
  49             /// Default ctor
  50             node()
  51                 : m_pNext( nullptr )
  52             {}
  53         };
  54
  55         //@cond
  56         template <typename GC, typename Node, typename MemoryModel>
  57         struct node_cleaner {
  58             void operator()( Node * p )
  59             {
  60                 typedef typename Node::marked_ptr marked_ptr;
  61                 p->m_pNext.store( marked_ptr(), MemoryModel::memory_order_release );
  62             }
  63         };
  64         //@endcond
  65
  66         //@cond
  67         struct undefined_gc;
  68         struct default_hook {
  69             typedef undefined_gc    gc;
  70             typedef opt::none       tag;
  71             typedef lock::Spin      lock_type;
  72         };
  73         //@endcond
  74
  75         //@cond
  76         template < typename HookType, typename... Options>
  77         struct hook
  78         {
  79             typedef typename opt::make_options< default_hook, Options...>::type  options;
  80             typedef typename options::gc        gc;
  81             typedef typename options::tag       tag;
  82             typedef typename options::lock_type lock_type;
  83             typedef node<gc, lock_type, tag>    node_type;
  84             typedef HookType        hook_type;
  85         };
  86         //@endcond
  87
  88         /// Base hook
  89         /**
  90             \p Options are:
  91             - opt::gc - garbage collector
  92             - opt::lock_type - lock type used for node locking. Default is lock::Spin
  93             - opt::tag - a \ref cds_intrusive_hook_tag "tag"
  94         */
  95         template < typename... Options >
  96         struct base_hook: public hook< opt::base_hook_tag, Options... >
  97         {};
  98
  99         /// Member hook
 100         /**
 101             \p MemberOffset defines offset in bytes of \ref node member into your structure.
 102             Use \p offsetof macro to define \p MemberOffset
 103
 104             \p Options are:
 105             - opt::gc - garbage collector
 106             - opt::lock_type - lock type used for node locking. Default is lock::Spin
 107             - opt::tag - a \ref cds_intrusive_hook_tag "tag"
 108         */
 109         template < size_t MemberOffset, typename... Options >
 110         struct member_hook: public hook< opt::member_hook_tag, Options... >
 111         {
 112             //@cond
 113             static const size_t c_nMemberOffset = MemberOffset;
 114             //@endcond
 115         };
 116
 117         /// Traits hook
 118         /**
 119             \p NodeTraits defines type traits for node.
 120             See \ref node_traits for \p NodeTraits interface description
 121
 122             \p Options are:
 123             - opt::gc - garbage collector used.
 124             - opt::lock_type - lock type used for node locking. Default is lock::Spin
 125             - opt::tag - a \ref cds_intrusive_hook_tag "tag"
 126         */
 127         template <typename NodeTraits, typename... Options >
 128         struct traits_hook: public hook< opt::traits_hook_tag, Options... >
 129         {
 130             //@cond
 131             typedef NodeTraits node_traits;
 132             //@endcond
 133         };
 134
 135         /// Check link
 136         template <typename Node>
 137         struct link_checker
 138         {
 139             //@cond
 140             typedef Node node_type;
 141             //@endcond
 142
 143             /// Checks if the link field of node \p pNode is \p nullptr
 144             /**
 145                 An asserting is generated if \p pNode link field is not \p nullptr
 146             */
 147             static void is_empty( node_type const * pNode )
 148             {
 149                 assert( pNode->m_pNext.load( atomics::memory_order_relaxed ) == nullptr );
 150             }
 151         };
 152
 153         //@cond
 154         template <class GC, typename Node, opt::link_check_type LinkType >
 155         struct link_checker_selector;
 156
 157         template <typename GC, typename Node>
 158         struct link_checker_selector< GC, Node, opt::never_check_link >
 159         {
 160             typedef intrusive::opt::v::empty_link_checker<Node>  type;
 161         };
 162
 163         template <typename GC, typename Node>
 164         struct link_checker_selector< GC, Node, opt::debug_check_link >
 165         {
 166 #       ifdef _DEBUG
 167             typedef link_checker<Node>  type;
 168 #       else
 169             typedef intrusive::opt::v::empty_link_checker<Node>  type;
 170 #       endif
 171         };
 172
 173         template <typename GC, typename Node>
 174         struct link_checker_selector< GC, Node, opt::always_check_link >
 175         {
 176             typedef link_checker<Node>  type;
 177         };
 178         //@endcond
 179
 180         /// Metafunction for selecting appropriate link checking policy
 181         template < typename Node, opt::link_check_type LinkType >
 182         struct get_link_checker
 183         {
 184             //@cond
 185             typedef typename link_checker_selector< typename Node::gc, Node, LinkType>::type type;
 186             //@endcond
 187         };
 188
 189         /// LazyList traits
 190         struct traits
 191         {
 192             /// Hook used
 193             /**
 194                 Possible values are: \p lazy_list::base_hook, \p lazy_list::member_hook, \p lazy_list::traits_hook.
 195             */
 196             typedef base_hook<>       hook;
 197
 198             /// Key comparing functor
 199             /**
 200                 No default functor is provided. If the functor is not specified, the \p less is used.
 201             */
 202             typedef opt::none                       compare;
 203
 204             /// Specifies binary predicate used for comparing keys
 205             /**
 206                 Default is \p std::less<T>.
 207             */
 208             typedef opt::none                       less;
 209
 210             /// Back-off strategy
 211             typedef cds::backoff::Default           back_off;
 212
 213             /// Disposer for removing items
 214             typedef opt::v::empty_disposer          disposer;
 215
 216             /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
 217             typedef atomicity::empty_item_counter     item_counter;
 218
 219             /// Link fields checking feature
 220             /**
 221                 Default is \p opt::debug_check_link
 222             */
 223             static const opt::link_check_type link_checker = opt::debug_check_link;
 224
 225             /// C++ memory ordering model
 226             /**
 227                 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 228                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 229             */
 230             typedef opt::v::relaxed_ordering        memory_model;
 231
 232             /// RCU deadlock checking policy (only for \ref cds_intrusive_LazyList_rcu "RCU-based LazyList")
 233             /**
 234                 List of available options see \p opt::rcu_check_deadlock
 235             */
 236             typedef opt::v::rcu_throw_deadlock      rcu_check_deadlock;
 237         };
 238
 239         /// Metafunction converting option list to \p lazy_list::traits
 240         /**
 241             Supported \p Options are:
 242             - \p opt::hook - hook used. Possible values are: \p lazy_list::base_hook, \p lazy_list::member_hook, \p lazy_list::traits_hook.
 243                 If the option is not specified, \p %lazy_list::base_hook and \p gc::HP is used.
 244             - \p opt::compare - key comparison functor. No default functor is provided.
 245                 If the option is not specified, the \p opt::less is used.
 246             - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
 247             - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
 248             - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. Due the nature
 249                 of GC schema the disposer may be called asynchronously.
 250             - \p opt::link_checker - the type of node's link fields checking. Default is \p opt::debug_check_link
 251             - \p opt::item_counter - the type of item counting feature. Default is disabled (\p atomicity::empty_item_counter).
 252                  To enable item counting use \p atomicity::item_counter.
 253             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 254                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 255             - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_MichaelList_rcu "RCU-based MichaelList"
 256                 Default is \p opt::v::rcu_throw_deadlock
 257         */
 258         template <typename... Options>
 259         struct make_traits {
 260 #   ifdef CDS_DOXYGEN_INVOKED
 261             typedef implementation_defined type ;   ///< Metafunction result
 262 #   else
 263             typedef typename cds::opt::make_options<
 264                 typename cds::opt::find_type_traits< traits, Options... >::type
 265                 ,Options...
 266             >::type   type;
 267 #   endif
 268         };
 269
 270     } // namespace lazy_list
 271
 272     //@cond
 273     // Forward declaration
 274     template < class GC, typename T, class Traits = lazy_list::traits >
 275     class LazyList;
 276     //@endcond
 277
 278 }}   // namespace cds::intrusive
 279
 280 #endif // #ifndef __CDS_INTRUSIVE_DETAILS_LAZY_LIST_BASE_H