boost/intrusive/options.hpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga  2007-2014
   4 //
   5 // Distributed under the Boost Software License, Version 1.0.
   6 //    (See accompanying file LICENSE_1_0.txt or copy at
   7 //          http://www.boost.org/LICENSE_1_0.txt)
   8 //
   9 // See http://www.boost.org/libs/intrusive for documentation.
  10 //
  11 /////////////////////////////////////////////////////////////////////////////
  12
  13 #ifndef BOOST_INTRUSIVE_OPTIONS_HPP
  14 #define BOOST_INTRUSIVE_OPTIONS_HPP
  15
  16 #if defined(_MSC_VER)
  17 #  pragma once
  18 #endif
  19
  20 #include <boost/intrusive/detail/config_begin.hpp>
  21 #include <boost/intrusive/intrusive_fwd.hpp>
  22 #include <boost/intrusive/link_mode.hpp>
  23 #include <boost/intrusive/pack_options.hpp>
  24 #include <boost/intrusive/detail/mpl.hpp>
  25
  26 namespace boost {
  27 namespace intrusive {
  28
  29 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
  30
  31 struct empty
  32 {};
  33
  34 template<class Functor>
  35 struct fhtraits;
  36
  37 template<class T, class Hook, Hook T::* P>
  38 struct mhtraits;
  39
  40 //typedef void default_tag;
  41 struct default_tag;
  42 struct member_tag;
  43
  44 template<class SupposedValueTraits>
  45 struct is_default_hook_tag;
  46
  47 #endif   //#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
  48
  49 //!This option setter specifies if the intrusive
  50 //!container stores its size as a member to
  51 //!obtain constant-time size() member.
  52 BOOST_INTRUSIVE_OPTION_CONSTANT(constant_time_size, bool, Enabled, constant_time_size)
  53
  54 //!This option setter specifies a container header holder type
  55 BOOST_INTRUSIVE_OPTION_TYPE(header_holder_type, HeaderHolder, HeaderHolder, header_holder_type)
  56
  57 //!This option setter specifies the type that
  58 //!the container will use to store its size.
  59 BOOST_INTRUSIVE_OPTION_TYPE(size_type, SizeType, SizeType, size_type)
  60
  61 //!This option setter specifies the strict weak ordering
  62 //!comparison functor for the value type
  63 BOOST_INTRUSIVE_OPTION_TYPE(compare, Compare, Compare, compare)
  64
  65 //!This option setter for scapegoat containers specifies if
  66 //!the intrusive scapegoat container should use a non-variable
  67 //!alpha value that does not need floating-point operations.
  68 //!
  69 //!If activated, the fixed alpha value is 1/sqrt(2). This
  70 //!option also saves some space in the container since
  71 //!the alpha value and some additional data does not need
  72 //!to be stored in the container.
  73 //!
  74 //!If the user only needs an alpha value near 1/sqrt(2), this
  75 //!option also improves performance since avoids logarithm
  76 //!and division operations when rebalancing the tree.
  77 BOOST_INTRUSIVE_OPTION_CONSTANT(floating_point, bool, Enabled, floating_point)
  78
  79 //!This option setter specifies the equality
  80 //!functor for the value type
  81 BOOST_INTRUSIVE_OPTION_TYPE(equal, Equal, Equal, equal)
  82
  83 //!This option setter specifies the equality
  84 //!functor for the value type
  85 BOOST_INTRUSIVE_OPTION_TYPE(priority, Priority, Priority, priority)
  86
  87 //!This option setter specifies the hash
  88 //!functor for the value type
  89 BOOST_INTRUSIVE_OPTION_TYPE(hash, Hash, Hash, hash)
  90
  91 //!This option setter specifies the relationship between the type
  92 //!to be managed by the container (the value type) and the node to be
  93 //!used in the node algorithms. It also specifies the linking policy.
  94 BOOST_INTRUSIVE_OPTION_TYPE(value_traits, ValueTraits, ValueTraits, proto_value_traits)
  95
  96 //#define BOOST_INTRUSIVE_COMMA ,
  97 //#define BOOST_INTRUSIVE_LESS <
  98 //#define BOOST_INTRUSIVE_MORE >
  99 //BOOST_INTRUSIVE_OPTION_TYPE (member_hook, Parent BOOST_INTRUSIVE_COMMA class MemberHook BOOST_INTRUSIVE_COMMA MemberHook Parent::* PtrToMember , mhtraits BOOST_INTRUSIVE_LESS Parent BOOST_INTRUSIVE_COMMA MemberHook BOOST_INTRUSIVE_COMMA PtrToMember BOOST_INTRUSIVE_MORE , proto_value_traits)
 100 //template< class Parent , class MemberHook , MemberHook Parent::* PtrToMember>
 101 //struct member_hook {
 102 //   template<class Base> struct pack : Base {
 103 //      typedef mhtraits < Parent , MemberHook , PtrToMember > proto_value_traits;
 104 //   };
 105 //};
 106 //
 107 //#undef BOOST_INTRUSIVE_COMMA
 108 //#undef BOOST_INTRUSIVE_LESS
 109 //#undef BOOST_INTRUSIVE_MORE
 110
 111 //!This option setter specifies the member hook the
 112 //!container must use.
 113 template< typename Parent
 114         , typename MemberHook
 115         , MemberHook Parent::* PtrToMember>
 116 struct member_hook
 117 {
 118 // @cond
 119 //   typedef typename MemberHook::hooktags::node_traits node_traits;
 120 //   typedef typename node_traits::node node_type;
 121 //   typedef node_type Parent::* Ptr2MemNode;
 122 //   typedef mhtraits
 123 //      < Parent
 124 //      , node_traits
 125 //      //This cast is really ugly but necessary to reduce template bloat.
 126 //      //Since we control the layout between the hook and the node, and there is
 127 //      //always single inheritance, the offset of the node is exactly the offset of
 128 //      //the hook. Since the node type is shared between all member hooks, this saves
 129 //      //quite a lot of symbol stuff.
 130 //      , (Ptr2MemNode)PtrToMember
 131 //      , MemberHook::hooktags::link_mode> member_value_traits;
 132    typedef mhtraits <Parent, MemberHook, PtrToMember> member_value_traits;
 133    template<class Base>
 134    struct pack : Base
 135    {
 136       typedef member_value_traits proto_value_traits;
 137    };
 138 /// @endcond
 139 };
 140
 141 //!This option setter specifies the function object that will
 142 //!be used to convert between values to be inserted in a container
 143 //!and the hook to be used for that purpose.
 144 BOOST_INTRUSIVE_OPTION_TYPE(function_hook, Functor, fhtraits<Functor>, proto_value_traits)
 145
 146 //!This option setter specifies that the container
 147 //!must use the specified base hook
 148 BOOST_INTRUSIVE_OPTION_TYPE(base_hook, BaseHook, BaseHook, proto_value_traits)
 149
 150 //!This option setter specifies the type of
 151 //!a void pointer. This will instruct the hook
 152 //!to use this type of pointer instead of the
 153 //!default one
 154 BOOST_INTRUSIVE_OPTION_TYPE(void_pointer, VoidPointer, VoidPointer, void_pointer)
 155
 156 //!This option setter specifies the type of
 157 //!the tag of a base hook. A type cannot have two
 158 //!base hooks of the same type, so a tag can be used
 159 //!to differentiate two base hooks with otherwise same type
 160 BOOST_INTRUSIVE_OPTION_TYPE(tag, Tag, Tag, tag)
 161
 162 //!This option setter specifies the link mode
 163 //!(normal_link, safe_link or auto_unlink)
 164 BOOST_INTRUSIVE_OPTION_CONSTANT(link_mode, link_mode_type, LinkType, link_mode)
 165
 166 //!This option setter specifies if the hook
 167 //!should be optimized for size instead of for speed.
 168 BOOST_INTRUSIVE_OPTION_CONSTANT(optimize_size, bool, Enabled, optimize_size)
 169
 170 //!This option setter specifies if the slist container should
 171 //!use a linear implementation instead of a circular one.
 172 BOOST_INTRUSIVE_OPTION_CONSTANT(linear, bool, Enabled, linear)
 173
 174 //!If true, slist also stores a pointer to the last element of the singly linked list.
 175 //!This allows O(1) swap and splice_after(iterator, slist &) for circular slists and makes
 176 //!possible new functions like push_back(reference) and back().
 177 BOOST_INTRUSIVE_OPTION_CONSTANT(cache_last, bool, Enabled, cache_last)
 178
 179 //!This option setter specifies the bucket traits
 180 //!class for unordered associative containers. When this option is specified,
 181 //!instead of using the default bucket traits, a user defined holder will be defined
 182 BOOST_INTRUSIVE_OPTION_TYPE(bucket_traits, BucketTraits, BucketTraits, bucket_traits)
 183
 184 //!This option setter specifies if the unordered hook
 185 //!should offer room to store the hash value.
 186 //!Storing the hash in the hook will speed up rehashing
 187 //!processes in applications where rehashing is frequent,
 188 //!rehashing might throw or the value is heavy to hash.
 189 BOOST_INTRUSIVE_OPTION_CONSTANT(store_hash, bool, Enabled, store_hash)
 190
 191 //!This option setter specifies if the unordered hook
 192 //!should offer room to store another link to another node
 193 //!with the same key.
 194 //!Storing this link will speed up lookups and insertions on
 195 //!unordered_multiset containers with a great number of elements
 196 //!with the same key.
 197 BOOST_INTRUSIVE_OPTION_CONSTANT(optimize_multikey, bool, Enabled, optimize_multikey)
 198
 199 //!This option setter specifies if the bucket array will be always power of two.
 200 //!This allows using masks instead of the default modulo operation to determine
 201 //!the bucket number from the hash value, leading to better performance.
 202 //!In debug mode, if power of two buckets mode is activated, the bucket length
 203 //!will be checked to through assertions to assure the bucket length is power of two.
 204 BOOST_INTRUSIVE_OPTION_CONSTANT(power_2_buckets, bool, Enabled, power_2_buckets)
 205
 206 //!This option setter specifies if the container will cache a pointer to the first
 207 //!non-empty bucket so that begin() is always constant-time.
 208 //!This is specially helpful when we can have containers with a few elements
 209 //!but with big bucket arrays (that is, hashtables with low load factors).
 210 BOOST_INTRUSIVE_OPTION_CONSTANT(cache_begin, bool, Enabled, cache_begin)
 211
 212 //!This option setter specifies if the container will compare the hash value
 213 //!before comparing objects. This option can't be specified if store_hash<>
 214 //!is not true.
 215 //!This is specially helpful when we have containers with a high load factor.
 216 //!and the comparison function is much more expensive that comparing already
 217 //!stored hash values.
 218 BOOST_INTRUSIVE_OPTION_CONSTANT(compare_hash, bool, Enabled, compare_hash)
 219
 220 //!This option setter specifies if the hash container will use incremental
 221 //!hashing. With incremental hashing the cost of hash table expansion is spread
 222 //!out across each hash table insertion operation, as opposed to be incurred all at once.
 223 //!Therefore linear hashing is well suited for interactive applications or real-time
 224 //!appplications where the worst-case insertion time of non-incremental hash containers
 225 //!(rehashing the whole bucket array) is not admisible.
 226 BOOST_INTRUSIVE_OPTION_CONSTANT(incremental, bool, Enabled, incremental)
 227
 228 /// @cond
 229
 230 struct hook_defaults
 231 {
 232    typedef void* void_pointer;
 233    static const link_mode_type link_mode = safe_link;
 234    typedef default_tag tag;
 235    static const bool optimize_size = false;
 236    static const bool store_hash = false;
 237    static const bool linear = false;
 238    static const bool optimize_multikey = false;
 239 };
 240
 241 /// @endcond
 242
 243 }  //namespace intrusive {
 244 }  //namespace boost {
 245
 246 #include <boost/intrusive/detail/config_end.hpp>
 247
 248 #endif   //#ifndef BOOST_INTRUSIVE_OPTIONS_HPP