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