cds/intrusive/lazy_list_base.h

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