cds/intrusive/details/michael_list_base.h

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