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/sync/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::sync::spin
  24             - Tag - a \ref cds_intrusive_hook_tag "tag"
  25         */
  26         template <
  27             class GC
  28             ,typename Lock =  cds::sync::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 sync::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 sync::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 sync::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 sync::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             /// Specifies binary functor used for comparing keys for equality
 212             /**
 213                 If \p equal_to option is not specified, \p compare is used, if \p compare is not specified, \p less is used,
 214                 if \p less is not specified, then \p std::equal_to<T> is used.
 215             */
 216             typedef opt::none                       equal_to;
 217
 218             /// Specifies list ordering policy
 219             /**
 220                 If \p sort is \p true, than list maintains items in sorted order, otherwise items are unordered. Default is \p true.
 221                 Note that if \p sort is \p false, than lookup operations scan entire list.
 222             */
 223             static const bool sort = true;
 224
 225             /// Back-off strategy
 226             typedef cds::backoff::Default           back_off;
 227
 228             /// Disposer for removing items
 229             typedef opt::v::empty_disposer          disposer;
 230
 231             /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
 232             typedef atomicity::empty_item_counter     item_counter;
 233
 234             /// Link fields checking feature
 235             /**
 236                 Default is \p opt::debug_check_link
 237             */
 238             static const opt::link_check_type link_checker = opt::debug_check_link;
 239
 240             /// C++ memory ordering model
 241             /**
 242                 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 243                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 244             */
 245             typedef opt::v::relaxed_ordering        memory_model;
 246
 247             /// RCU deadlock checking policy (only for \ref cds_intrusive_LazyList_rcu "RCU-based LazyList")
 248             /**
 249                 List of available options see \p opt::rcu_check_deadlock
 250             */
 251             typedef opt::v::rcu_throw_deadlock      rcu_check_deadlock;
 252         };
 253
 254         /// Metafunction converting option list to \p lazy_list::traits
 255         /**
 256             Supported \p Options are:
 257             - \p opt::hook - hook used. Possible values are: \p lazy_list::base_hook, \p lazy_list::member_hook, \p lazy_list::traits_hook.
 258                 If the option is not specified, \p %lazy_list::base_hook and \p gc::HP is used.
 259             - \p opt::compare - key comparison functor. No default functor is provided.
 260                 If the option is not specified, the \p opt::less is used.
 261             - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
 262             - \p opt::equal_to - specifies binary functor for comparing keys for equality. If \p equal_to is not specified, \p compare is
 263                 used, \p compare is not specified, \p less is used.
 264             - \p opt::sort - specifies ordering policy. Default value is \p true.
 265             - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
 266             - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. Due the nature
 267                 of GC schema the disposer may be called asynchronously.
 268             - \p opt::link_checker - the type of node's link fields checking. Default is \p opt::debug_check_link
 269             - \p opt::item_counter - the type of item counting feature. Default is disabled (\p atomicity::empty_item_counter).
 270                  To enable item counting use \p atomicity::item_counter.
 271             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 272                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 273             - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_MichaelList_rcu "RCU-based MichaelList"
 274                 Default is \p opt::v::rcu_throw_deadlock
 275         */
 276         template <typename... Options>
 277         struct make_traits {
 278 #   ifdef CDS_DOXYGEN_INVOKED
 279             typedef implementation_defined type ;   ///< Metafunction result
 280 #   else
 281             typedef typename cds::opt::make_options<
 282                 typename cds::opt::find_type_traits< traits, Options... >::type
 283                 ,Options...
 284             >::type   type;
 285 #   endif
 286         };
 287
 288     } // namespace lazy_list
 289
 290     //@cond
 291     // Forward declaration
 292     template < class GC, typename T, class Traits = lazy_list::traits >
 293     class LazyList;
 294     //@endcond
 295
 296 }}   // namespace cds::intrusive
 297
 298 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_LAZY_LIST_BASE_H