cds/intrusive/details/lazy_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_LAZY_LIST_BASE_H
  32 #define CDSLIB_INTRUSIVE_DETAILS_LAZY_LIST_BASE_H
  33
  34 #include <cds/intrusive/details/base.h>
  35 #include <cds/opt/compare.h>
  36 #include <cds/details/marked_ptr.h>
  37 #include <cds/details/make_const_type.h>
  38 #include <cds/sync/spinlock.h>
  39 #include <cds/urcu/options.h>
  40
  41 namespace cds { namespace intrusive {
  42
  43     /// LazyList ordered list related definitions
  44     /** @ingroup cds_intrusive_helper
  45     */
  46     namespace lazy_list {
  47         /// Lazy list node
  48         /**
  49             Template parameters:
  50             - GC - garbage collector
  51             - Lock - lock type. Default is \p cds::sync::spin
  52             - Tag - a \ref cds_intrusive_hook_tag "tag"
  53         */
  54         template <
  55             class GC
  56             ,typename Lock =  cds::sync::spin
  57             ,typename Tag = opt::none
  58         >
  59         struct node
  60         {
  61             typedef GC      gc          ;   ///< Garbage collector
  62             typedef Lock    lock_type   ;   ///< Lock type
  63             typedef Tag     tag         ;   ///< tag
  64
  65             typedef cds::details::marked_ptr<node, 1>   marked_ptr         ;   ///< marked pointer
  66             typedef typename gc::template atomic_marked_ptr< marked_ptr>     atomic_marked_ptr   ;   ///< atomic marked pointer specific for GC
  67
  68             atomic_marked_ptr   m_pNext; ///< pointer to the next node in the list + logical deletion mark
  69             mutable lock_type   m_Lock;  ///< Node lock
  70
  71             /// Checks if node is marked
  72             bool is_marked() const
  73             {
  74                 return m_pNext.load(atomics::memory_order_relaxed).bits() != 0;
  75             }
  76
  77             /// Default ctor
  78             node()
  79                 : m_pNext( nullptr )
  80             {}
  81         };
  82
  83         //@cond
  84         template <typename GC, typename Node, typename MemoryModel>
  85         struct node_cleaner {
  86             void operator()( Node * p )
  87             {
  88                 typedef typename Node::marked_ptr marked_ptr;
  89                 p->m_pNext.store( marked_ptr(), MemoryModel::memory_order_release );
  90             }
  91         };
  92         //@endcond
  93
  94         //@cond
  95         struct undefined_gc;
  96         struct default_hook {
  97             typedef undefined_gc    gc;
  98             typedef opt::none       tag;
  99             typedef sync::spin      lock_type;
 100         };
 101         //@endcond
 102
 103         //@cond
 104         template < typename HookType, typename... Options>
 105         struct hook
 106         {
 107             typedef typename opt::make_options< default_hook, Options...>::type  options;
 108             typedef typename options::gc        gc;
 109             typedef typename options::tag       tag;
 110             typedef typename options::lock_type lock_type;
 111             typedef node<gc, lock_type, tag>    node_type;
 112             typedef HookType        hook_type;
 113         };
 114         //@endcond
 115
 116         /// Base hook
 117         /**
 118             \p Options are:
 119             - opt::gc - garbage collector
 120             - opt::lock_type - lock type used for node locking. Default is sync::spin
 121             - opt::tag - a \ref cds_intrusive_hook_tag "tag"
 122         */
 123         template < typename... Options >
 124         struct base_hook: public hook< opt::base_hook_tag, Options... >
 125         {};
 126
 127         /// Member hook
 128         /**
 129             \p MemberOffset defines offset in bytes of \ref node member into your structure.
 130             Use \p offsetof macro to define \p MemberOffset
 131
 132             \p Options are:
 133             - opt::gc - garbage collector
 134             - opt::lock_type - lock type used for node locking. Default is sync::spin
 135             - opt::tag - a \ref cds_intrusive_hook_tag "tag"
 136         */
 137         template < size_t MemberOffset, typename... Options >
 138         struct member_hook: public hook< opt::member_hook_tag, Options... >
 139         {
 140             //@cond
 141             static const size_t c_nMemberOffset = MemberOffset;
 142             //@endcond
 143         };
 144
 145         /// Traits hook
 146         /**
 147             \p NodeTraits defines type traits for node.
 148             See \ref node_traits for \p NodeTraits interface description
 149
 150             \p Options are:
 151             - opt::gc - garbage collector used.
 152             - opt::lock_type - lock type used for node locking. Default is sync::spin
 153             - opt::tag - a \ref cds_intrusive_hook_tag "tag"
 154         */
 155         template <typename NodeTraits, typename... Options >
 156         struct traits_hook: public hook< opt::traits_hook_tag, Options... >
 157         {
 158             //@cond
 159             typedef NodeTraits node_traits;
 160             //@endcond
 161         };
 162
 163         /// Check link
 164         template <typename Node>
 165         struct link_checker
 166         {
 167             //@cond
 168             typedef Node node_type;
 169             //@endcond
 170
 171             /// Checks if the link field of node \p pNode is \p nullptr
 172             /**
 173                 An asserting is generated if \p pNode link field is not \p nullptr
 174             */
 175             static void is_empty( node_type const * pNode )
 176             {
 177                 assert( pNode->m_pNext.load( atomics::memory_order_relaxed ) == nullptr );
 178                 CDS_UNUSED( pNode );
 179             }
 180         };
 181
 182         //@cond
 183         template <class GC, typename Node, opt::link_check_type LinkType >
 184         struct link_checker_selector;
 185
 186         template <typename GC, typename Node>
 187         struct link_checker_selector< GC, Node, opt::never_check_link >
 188         {
 189             typedef intrusive::opt::v::empty_link_checker<Node>  type;
 190         };
 191
 192         template <typename GC, typename Node>
 193         struct link_checker_selector< GC, Node, opt::debug_check_link >
 194         {
 195 #       ifdef _DEBUG
 196             typedef link_checker<Node>  type;
 197 #       else
 198             typedef intrusive::opt::v::empty_link_checker<Node>  type;
 199 #       endif
 200         };
 201
 202         template <typename GC, typename Node>
 203         struct link_checker_selector< GC, Node, opt::always_check_link >
 204         {
 205             typedef link_checker<Node>  type;
 206         };
 207         //@endcond
 208
 209         /// Metafunction for selecting appropriate link checking policy
 210         template < typename Node, opt::link_check_type LinkType >
 211         struct get_link_checker
 212         {
 213             //@cond
 214             typedef typename link_checker_selector< typename Node::gc, Node, LinkType>::type type;
 215             //@endcond
 216         };
 217
 218         /// LazyList traits
 219         struct traits
 220         {
 221             /// Hook used
 222             /**
 223                 Possible values are: \p lazy_list::base_hook, \p lazy_list::member_hook, \p lazy_list::traits_hook.
 224             */
 225             typedef base_hook<>       hook;
 226
 227             /// Key comparing functor
 228             /**
 229                 No default functor is provided. If the functor is not specified, the \p less is used.
 230             */
 231             typedef opt::none                       compare;
 232
 233             /// Specifies binary predicate used for comparing keys
 234             /**
 235                 Default is \p std::less<T>.
 236             */
 237             typedef opt::none                       less;
 238
 239             /// Specifies binary functor used for comparing keys for equality (for unordered list only)
 240             /**
 241                 If \p equal_to option is not specified, \p compare is used, if \p compare is not specified, \p less is used,
 242                 if \p less is not specified, then \p std::equal_to<T> is used.
 243             */
 244             typedef opt::none                       equal_to;
 245
 246             /// Specifies list ordering policy
 247             /**
 248                 If \p sort is \p true, than list maintains items in sorted order, otherwise the list is unordered.
 249                 Default is \p true.
 250                 Note that if \p sort is \p false, than lookup operations scan entire list.
 251             */
 252             static const bool sort = true;
 253
 254             /// Back-off strategy
 255             typedef cds::backoff::Default           back_off;
 256
 257             /// Disposer for removing items
 258             typedef opt::v::empty_disposer          disposer;
 259
 260             /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
 261             typedef atomicity::empty_item_counter     item_counter;
 262
 263             /// Link fields checking feature
 264             /**
 265                 Default is \p opt::debug_check_link
 266             */
 267             static const opt::link_check_type link_checker = opt::debug_check_link;
 268
 269             /// C++ memory ordering model
 270             /**
 271                 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 272                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 273             */
 274             typedef opt::v::relaxed_ordering        memory_model;
 275
 276             /// RCU deadlock checking policy (only for \ref cds_intrusive_LazyList_rcu "RCU-based LazyList")
 277             /**
 278                 List of available options see \p opt::rcu_check_deadlock
 279             */
 280             typedef opt::v::rcu_throw_deadlock      rcu_check_deadlock;
 281         };
 282
 283         /// Metafunction converting option list to \p lazy_list::traits
 284         /**
 285             Supported \p Options are:
 286             - \p opt::hook - hook used. Possible values are: \p lazy_list::base_hook, \p lazy_list::member_hook, \p lazy_list::traits_hook.
 287                 If the option is not specified, \p %lazy_list::base_hook and \p gc::HP is used.
 288             - \p opt::compare - key comparison functor. No default functor is provided.
 289                 If the option is not specified, the \p opt::less is used.
 290             - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
 291             - \p opt::equal_to - specifies binary functor for comparing keys for equality. This option is applicable only for unordered list.
 292                 If \p equal_to is not specified, \p compare is used, \p compare is not specified, \p less is used.
 293             - \p opt::sort - specifies ordering policy. Default value is \p true, i.e. the list is ordered.
 294                 Note: unordering feature is not fully supported yet.
 295             - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
 296             - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. Due the nature
 297                 of GC schema the disposer may be called asynchronously.
 298             - \p opt::link_checker - the type of node's link fields checking. Default is \p opt::debug_check_link
 299             - \p opt::item_counter - the type of item counting feature. Default is disabled (\p atomicity::empty_item_counter).
 300                  To enable item counting use \p atomicity::item_counter.
 301             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 302                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 303             - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_MichaelList_rcu "RCU-based MichaelList"
 304                 Default is \p opt::v::rcu_throw_deadlock
 305         */
 306         template <typename... Options>
 307         struct make_traits {
 308 #   ifdef CDS_DOXYGEN_INVOKED
 309             typedef implementation_defined type ;   ///< Metafunction result
 310 #   else
 311             typedef typename cds::opt::make_options<
 312                 typename cds::opt::find_type_traits< traits, Options... >::type
 313                 ,Options...
 314             >::type   type;
 315 #   endif
 316         };
 317
 318     } // namespace lazy_list
 319
 320     //@cond
 321     // Forward declaration
 322     template < class GC, typename T, class Traits = lazy_list::traits >
 323     class LazyList;
 324     //@endcond
 325
 326 }}   // namespace cds::intrusive
 327
 328 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_LAZY_LIST_BASE_H