cds/intrusive/details/single_link_struct.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-2017
   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_SINGLE_LINK_STRUCT_H
  32 #define CDSLIB_INTRUSIVE_DETAILS_SINGLE_LINK_STRUCT_H
  33
  34 #include <cds/intrusive/details/base.h>
  35 #include <cds/gc/default_gc.h>
  36 #include <cds/algo/atomic.h>
  37
  38 namespace cds { namespace intrusive {
  39
  40     /// Definitions common for single-linked data structures
  41     /** @ingroup cds_intrusive_helper
  42     */
  43     namespace single_link {
  44
  45         /// Container's node
  46         /**
  47             Template parameters:
  48             - GC - garbage collector used
  49             - Tag - a tag used to distinguish between different implementation
  50         */
  51         template <class GC, typename Tag = opt::none>
  52         struct node
  53         {
  54             typedef GC              gc  ;   ///< Garbage collector
  55             typedef Tag             tag ;   ///< tag
  56
  57             typedef typename gc::template atomic_ref<node>    atomic_node_ptr; ///< atomic pointer
  58
  59             /// Rebind node for other template parameters
  60             template <class GC2, typename Tag2 = tag>
  61             struct rebind {
  62                 typedef node<GC2, Tag2>  other ;    ///< Rebinding result
  63             };
  64
  65             atomic_node_ptr m_pNext ; ///< pointer to the next node in the container
  66
  67             node() CDS_NOEXCEPT
  68             {
  69                 m_pNext.store( nullptr, atomics::memory_order_release );
  70             }
  71         };
  72
  73         //@cond
  74         struct default_hook {
  75             typedef cds::gc::default_gc gc;
  76             typedef opt::none           tag;
  77         };
  78         //@endcond
  79
  80         //@cond
  81         template < typename HookType, typename... Options>
  82         struct hook
  83         {
  84             typedef typename opt::make_options< default_hook, Options...>::type  options;
  85             typedef typename options::gc    gc;
  86             typedef typename options::tag   tag;
  87             typedef node<gc, tag> node_type;
  88             typedef HookType      hook_type;
  89         };
  90         //@endcond
  91
  92         /// Base hook
  93         /**
  94             \p Options are:
  95             - opt::gc - garbage collector used.
  96             - opt::tag - tag
  97         */
  98         template < typename... Options >
  99         struct base_hook: public hook< opt::base_hook_tag, Options... >
 100         {};
 101
 102         /// Member hook
 103         /**
 104             \p MemberOffset defines offset in bytes of \ref node member into your structure.
 105             Use \p offsetof macro to define \p MemberOffset
 106
 107             \p Options are:
 108             - opt::gc - garbage collector used.
 109             - opt::tag - tag
 110         */
 111         template < size_t MemberOffset, typename... Options >
 112         struct member_hook: public hook< opt::member_hook_tag, Options... >
 113         {
 114             //@cond
 115             static const size_t c_nMemberOffset = MemberOffset;
 116             //@endcond
 117         };
 118
 119         /// Traits hook
 120         /**
 121             \p NodeTraits defines type traits for node.
 122             See \ref node_traits for \p NodeTraits interface description
 123
 124             \p Options are:
 125             - opt::gc - garbage collector used.
 126             - opt::tag - tag
 127         */
 128         template <typename NodeTraits, typename... Options >
 129         struct traits_hook: public hook< opt::traits_hook_tag, Options... >
 130         {
 131             //@cond
 132             typedef NodeTraits node_traits;
 133             //@endcond
 134         };
 135
 136         /// Check link
 137         template <typename Node>
 138         struct link_checker {
 139             //@cond
 140             typedef Node node_type;
 141             //@endcond
 142
 143             /// Checks if the link field of node \p pNode is \p nullptr
 144             /**
 145                 An asserting is generated if \p pNode link field is not \p nullptr
 146             */
 147             static void is_empty( const node_type * pNode )
 148             {
 149                 assert( pNode->m_pNext.load( atomics::memory_order_relaxed ) == nullptr );
 150                 CDS_UNUSED( pNode );
 151             }
 152         };
 153
 154         //@cond
 155         template <class GC, typename Node, opt::link_check_type LinkType >
 156         struct link_checker_selector;
 157
 158         template <typename GC, typename Node>
 159         struct link_checker_selector< GC, Node, opt::never_check_link >
 160         {
 161             typedef intrusive::opt::v::empty_link_checker<Node>  type;
 162         };
 163
 164         template <typename GC, typename Node>
 165         struct link_checker_selector< GC, Node, opt::debug_check_link >
 166         {
 167 #       ifdef _DEBUG
 168             typedef link_checker<Node>  type;
 169 #       else
 170             typedef intrusive::opt::v::empty_link_checker<Node>  type;
 171 #       endif
 172         };
 173
 174         template <typename GC, typename Node>
 175         struct link_checker_selector< GC, Node, opt::always_check_link >
 176         {
 177             typedef link_checker<Node>  type;
 178         };
 179         //@endcond
 180
 181         /// Metafunction for selecting appropriate link checking policy
 182         template < typename Node, opt::link_check_type LinkType >
 183         struct get_link_checker
 184         {
 185             //@cond
 186             typedef typename link_checker_selector< typename Node::gc, Node, LinkType>::type type;
 187             //@endcond
 188         };
 189
 190     }   // namespace single_link
 191
 192 }}  // namespace cds::intrusive
 193
 194
 195
 196 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_SINGLE_LINK_STRUCT_H