cds/intrusive/details/michael_list_base.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_INTRUSIVE_DETAILS_MICHAEL_LIST_BASE_H
  32 #define CDSLIB_INTRUSIVE_DETAILS_MICHAEL_LIST_BASE_H
  33
  34 #include <type_traits>
  35 #include <cds/intrusive/details/base.h>
  36 #include <cds/opt/compare.h>
  37 #include <cds/algo/atomic.h>
  38 #include <cds/details/marked_ptr.h>
  39 #include <cds/urcu/options.h>
  40
  41 namespace cds { namespace intrusive {
  42
  43     /// MichaelList ordered list related definitions
  44     /** @ingroup cds_intrusive_helper
  45     */
  46     namespace michael_list {
  47         /// Michael's list node
  48         /**
  49             Template parameters:
  50             - \p GC - garbage collector
  51             - \p Tag - a \ref cds_intrusive_hook_tag "tag"
  52         */
  53         template <class GC, typename Tag = opt::none>
  54         struct node
  55         {
  56             typedef GC              gc  ;   ///< Garbage collector
  57             typedef Tag             tag ;   ///< tag
  58
  59             typedef cds::details::marked_ptr<node, 1>   marked_ptr;   ///< marked pointer
  60             typedef typename gc::template atomic_marked_ptr<marked_ptr> atomic_marked_ptr;   ///< atomic marked pointer specific for GC
  61
  62             atomic_marked_ptr m_pNext ; ///< pointer to the next node in the container
  63
  64             CDS_CONSTEXPR node() CDS_NOEXCEPT
  65                 : m_pNext( nullptr )
  66             {}
  67         };
  68
  69         //@cond
  70         template <typename GC, typename Node, typename MemoryModel>
  71         struct node_cleaner {
  72             void operator()( Node * p )
  73             {
  74                 typedef typename Node::marked_ptr marked_ptr;
  75                 p->m_pNext.store( marked_ptr(), MemoryModel::memory_order_release );
  76             }
  77         };
  78         //@endcond
  79
  80         //@cond
  81         struct undefined_gc;
  82         struct default_hook {
  83             typedef undefined_gc    gc;
  84             typedef opt::none       tag;
  85         };
  86         //@endcond
  87
  88         //@cond
  89         template < typename HookType, typename... Options>
  90         struct hook
  91         {
  92             typedef typename opt::make_options< default_hook, Options...>::type  options;
  93             typedef typename options::gc    gc;
  94             typedef typename options::tag   tag;
  95             typedef node<gc, tag>   node_type;
  96             typedef HookType        hook_type;
  97         };
  98         //@endcond
  99
 100         /// Base hook
 101         /**
 102             \p Options are:
 103             - opt::gc - garbage collector used.
 104             - opt::tag - a \ref cds_intrusive_hook_tag "tag"
 105         */
 106         template < typename... Options >
 107         struct base_hook: public hook< opt::base_hook_tag, Options... >
 108         {};
 109
 110         /// Member hook
 111         /**
 112             \p MemberOffset defines offset in bytes of \ref node member into your structure.
 113             Use \p offsetof macro to define \p MemberOffset
 114
 115             \p Options are:
 116             - opt::gc - garbage collector used.
 117             - opt::tag - a \ref cds_intrusive_hook_tag "tag"
 118         */
 119         template < size_t MemberOffset, typename... Options >
 120         struct member_hook: public hook< opt::member_hook_tag, Options... >
 121         {
 122             //@cond
 123             static const size_t c_nMemberOffset = MemberOffset;
 124             //@endcond
 125         };
 126
 127         /// Traits hook
 128         /**
 129             \p NodeTraits defines type traits for node.
 130             See \ref node_traits for \p NodeTraits interface description
 131
 132             \p Options are:
 133             - opt::gc - garbage collector used.
 134             - opt::tag - a \ref cds_intrusive_hook_tag "tag"
 135         */
 136         template <typename NodeTraits, typename... Options >
 137         struct traits_hook: public hook< opt::traits_hook_tag, Options... >
 138         {
 139             //@cond
 140             typedef NodeTraits node_traits;
 141             //@endcond
 142         };
 143
 144         /// Checks link
 145         template <typename Node>
 146         struct link_checker
 147         {
 148             //@cond
 149             typedef Node node_type;
 150             //@endcond
 151
 152             /// Checks if the link field of node \p pNode is \p nullptr
 153             /**
 154                 An asserting is generated if \p pNode link field is not \p nullptr
 155             */
 156             static void is_empty( const node_type * pNode )
 157             {
 158                 assert( pNode->m_pNext.load( atomics::memory_order_relaxed ) == nullptr );
 159                 CDS_UNUSED( pNode );
 160             }
 161         };
 162
 163         //@cond
 164         template <class GC, typename Node, opt::link_check_type LinkType >
 165         struct link_checker_selector;
 166
 167         template <typename GC, typename Node>
 168         struct link_checker_selector< GC, Node, opt::never_check_link >
 169         {
 170             typedef intrusive::opt::v::empty_link_checker<Node>  type;
 171         };
 172
 173         template <typename GC, typename Node>
 174         struct link_checker_selector< GC, Node, opt::debug_check_link >
 175         {
 176 #       ifdef _DEBUG
 177             typedef link_checker<Node>  type;
 178 #       else
 179             typedef intrusive::opt::v::empty_link_checker<Node>  type;
 180 #       endif
 181         };
 182
 183         template <typename GC, typename Node>
 184         struct link_checker_selector< GC, Node, opt::always_check_link >
 185         {
 186             typedef link_checker<Node>  type;
 187         };
 188         //@endcond
 189
 190         /// Metafunction for selecting appropriate link checking policy
 191         template < typename Node, opt::link_check_type LinkType >
 192         struct get_link_checker
 193         {
 194             //@cond
 195             typedef typename link_checker_selector< typename Node::gc, Node, LinkType>::type type;
 196             //@endcond
 197         };
 198
 199         /// MichaelList traits
 200         struct traits
 201         {
 202             /// Hook used
 203             /**
 204                 Possible values are: \p michael_list::base_hook, \p michael_list::member_hook, \p michael_list::traits_hook.
 205             */
 206             typedef base_hook<>       hook;
 207
 208             /// Key comparison functor
 209             /**
 210                 No default functor is provided. If the option is not specified, the \p less is used.
 211             */
 212             typedef opt::none                       compare;
 213
 214             /// Specifies binary predicate used for key compare.
 215             /**
 216                 Default is \p std::less<T>.
 217             */
 218             typedef opt::none                       less;
 219
 220             /// Back-off strategy
 221             typedef cds::backoff::Default           back_off;
 222
 223             /// Disposer for removing items
 224             typedef opt::v::empty_disposer          disposer;
 225
 226             /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
 227             typedef atomicity::empty_item_counter     item_counter;
 228
 229             /// Link fields checking feature
 230             /**
 231                 Default is \p opt::debug_check_link
 232             */
 233             static const opt::link_check_type link_checker = opt::debug_check_link;
 234
 235             /// C++ memory ordering model
 236             /**
 237                 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 238                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 239             */
 240             typedef opt::v::relaxed_ordering        memory_model;
 241
 242             /// RCU deadlock checking policy (only for \ref cds_intrusive_MichaelList_rcu "RCU-based MichaelList")
 243             /**
 244                 List of available policy see \p opt::rcu_check_deadlock
 245             */
 246             typedef opt::v::rcu_throw_deadlock      rcu_check_deadlock;
 247         };
 248
 249         /// Metafunction converting option list to \p michael_list::traits
 250         /**
 251             Supported \p Options are:
 252             - \p opt::hook - hook used. Possible values are: \p michael_list::base_hook, \p michael_list::member_hook, \p michael_list::traits_hook.
 253                 If the option is not specified, \p %michael_list::base_hook<> and \p gc::HP is used.
 254             - \p opt::compare - key comparison functor. No default functor is provided.
 255                 If the option is not specified, the \p opt::less is used.
 256             - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
 257             - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
 258             - \p opt::disposer - the functor used for disposing removed items. Default is \p opt::v::empty_disposer. Due the nature
 259                 of GC schema the disposer may be called asynchronously.
 260             - \p opt::link_checker - the type of node's link fields checking. Default is \p opt::debug_check_link
 261             - \p opt::item_counter - the type of item counting feature. Default is disabled (\p atomicity::empty_item_counter).
 262                  To enable item counting use \p atomicity::item_counter.
 263             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 264                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 265             - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_MichaelList_rcu "RCU-based MichaelList"
 266                 Default is \p opt::v::rcu_throw_deadlock
 267         */
 268         template <typename... Options>
 269         struct make_traits {
 270 #   ifdef CDS_DOXYGEN_INVOKED
 271             typedef implementation_defined type ;   ///< Metafunction result
 272 #   else
 273             typedef typename cds::opt::make_options<
 274                 typename cds::opt::find_type_traits< traits, Options... >::type
 275                 ,Options...
 276             >::type   type;
 277 #   endif
 278         };
 279
 280     } // namespace michael_list
 281
 282     //@cond
 283     // Forward declaration
 284     template < class GC, typename T, class Traits = michael_list::traits >
 285     class MichaelList;
 286     //@endcond
 287
 288
 289     /// Tag for selecting Michael list
 290     //class michael_list_tag;
 291
 292 }}   // namespace cds::intrusive
 293
 294 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_MICHAEL_LIST_BASE_H