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