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