cds/intrusive/details/lazy_list_base.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_INTRUSIVE_DETAILS_LAZY_LIST_BASE_H
   4 #define CDSLIB_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                 CDS_UNUSED( pNode );
 151             }
 152         };
 153
 154         //@cond
 155         template <class GC, typename Node, opt::link_check_type LinkType >
 156         struct link_checker_selector;
 157
 158         template <typename GC, typename Node>
 159         struct link_checker_selector< GC, Node, opt::never_check_link >
 160         {
 161             typedef intrusive::opt::v::empty_link_checker<Node>  type;
 162         };
 163
 164         template <typename GC, typename Node>
 165         struct link_checker_selector< GC, Node, opt::debug_check_link >
 166         {
 167 #       ifdef _DEBUG
 168             typedef link_checker<Node>  type;
 169 #       else
 170             typedef intrusive::opt::v::empty_link_checker<Node>  type;
 171 #       endif
 172         };
 173
 174         template <typename GC, typename Node>
 175         struct link_checker_selector< GC, Node, opt::always_check_link >
 176         {
 177             typedef link_checker<Node>  type;
 178         };
 179         //@endcond
 180
 181         /// Metafunction for selecting appropriate link checking policy
 182         template < typename Node, opt::link_check_type LinkType >
 183         struct get_link_checker
 184         {
 185             //@cond
 186             typedef typename link_checker_selector< typename Node::gc, Node, LinkType>::type type;
 187             //@endcond
 188         };
 189
 190         /// LazyList traits
 191         struct traits
 192         {
 193             /// Hook used
 194             /**
 195                 Possible values are: \p lazy_list::base_hook, \p lazy_list::member_hook, \p lazy_list::traits_hook.
 196             */
 197             typedef base_hook<>       hook;
 198
 199             /// Key comparing functor
 200             /**
 201                 No default functor is provided. If the functor is not specified, the \p less is used.
 202             */
 203             typedef opt::none                       compare;
 204
 205             /// Specifies binary predicate used for comparing keys
 206             /**
 207                 Default is \p std::less<T>.
 208             */
 209             typedef opt::none                       less;
 210
 211             /// Back-off strategy
 212             typedef cds::backoff::Default           back_off;
 213
 214             /// Disposer for removing items
 215             typedef opt::v::empty_disposer          disposer;
 216
 217             /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
 218             typedef atomicity::empty_item_counter     item_counter;
 219
 220             /// Link fields checking feature
 221             /**
 222                 Default is \p opt::debug_check_link
 223             */
 224             static const opt::link_check_type link_checker = opt::debug_check_link;
 225
 226             /// C++ memory ordering model
 227             /**
 228                 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 229                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 230             */
 231             typedef opt::v::relaxed_ordering        memory_model;
 232
 233             /// RCU deadlock checking policy (only for \ref cds_intrusive_LazyList_rcu "RCU-based LazyList")
 234             /**
 235                 List of available options see \p opt::rcu_check_deadlock
 236             */
 237             typedef opt::v::rcu_throw_deadlock      rcu_check_deadlock;
 238         };
 239
 240         /// Metafunction converting option list to \p lazy_list::traits
 241         /**
 242             Supported \p Options are:
 243             - \p opt::hook - hook used. Possible values are: \p lazy_list::base_hook, \p lazy_list::member_hook, \p lazy_list::traits_hook.
 244                 If the option is not specified, \p %lazy_list::base_hook and \p gc::HP is used.
 245             - \p opt::compare - key comparison functor. No default functor is provided.
 246                 If the option is not specified, the \p opt::less is used.
 247             - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
 248             - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
 249             - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. Due the nature
 250                 of GC schema the disposer may be called asynchronously.
 251             - \p opt::link_checker - the type of node's link fields checking. Default is \p opt::debug_check_link
 252             - \p opt::item_counter - the type of item counting feature. Default is disabled (\p atomicity::empty_item_counter).
 253                  To enable item counting use \p atomicity::item_counter.
 254             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 255                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 256             - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_MichaelList_rcu "RCU-based MichaelList"
 257                 Default is \p opt::v::rcu_throw_deadlock
 258         */
 259         template <typename... Options>
 260         struct make_traits {
 261 #   ifdef CDS_DOXYGEN_INVOKED
 262             typedef implementation_defined type ;   ///< Metafunction result
 263 #   else
 264             typedef typename cds::opt::make_options<
 265                 typename cds::opt::find_type_traits< traits, Options... >::type
 266                 ,Options...
 267             >::type   type;
 268 #   endif
 269         };
 270
 271     } // namespace lazy_list
 272
 273     //@cond
 274     // Forward declaration
 275     template < class GC, typename T, class Traits = lazy_list::traits >
 276     class LazyList;
 277     //@endcond
 278
 279 }}   // namespace cds::intrusive
 280
 281 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_LAZY_LIST_BASE_H