[3408] | 1 | |
---|
| 2 | // Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard. |
---|
| 3 | // Copyright (C) 2005-2009 Daniel James |
---|
| 4 | // Distributed under the Boost Software License, Version 1.0. (See accompanying |
---|
| 5 | // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) |
---|
| 6 | |
---|
| 7 | #ifndef BOOST_UNORDERED_DETAIL_UTIL_HPP_INCLUDED |
---|
| 8 | #define BOOST_UNORDERED_DETAIL_UTIL_HPP_INCLUDED |
---|
| 9 | |
---|
| 10 | #include <cstddef> |
---|
| 11 | #include <utility> |
---|
| 12 | #include <algorithm> |
---|
| 13 | #include <boost/limits.hpp> |
---|
| 14 | #include <boost/iterator/iterator_categories.hpp> |
---|
| 15 | #include <boost/preprocessor/seq/size.hpp> |
---|
| 16 | #include <boost/preprocessor/seq/enum.hpp> |
---|
| 17 | #include <boost/unordered/detail/fwd.hpp> |
---|
| 18 | |
---|
| 19 | namespace boost { namespace unordered_detail { |
---|
| 20 | |
---|
| 21 | //////////////////////////////////////////////////////////////////////////// |
---|
| 22 | // convert double to std::size_t |
---|
| 23 | |
---|
| 24 | inline std::size_t double_to_size_t(double f) |
---|
| 25 | { |
---|
| 26 | return f >= static_cast<double>( |
---|
| 27 | (std::numeric_limits<std::size_t>::max)()) ? |
---|
| 28 | (std::numeric_limits<std::size_t>::max)() : |
---|
| 29 | static_cast<std::size_t>(f); |
---|
| 30 | } |
---|
| 31 | |
---|
| 32 | //////////////////////////////////////////////////////////////////////////// |
---|
| 33 | // primes |
---|
| 34 | |
---|
| 35 | #define BOOST_UNORDERED_PRIMES \ |
---|
| 36 | (5ul)(11ul)(17ul)(29ul)(37ul)(53ul)(67ul)(79ul) \ |
---|
| 37 | (97ul)(131ul)(193ul)(257ul)(389ul)(521ul)(769ul) \ |
---|
| 38 | (1031ul)(1543ul)(2053ul)(3079ul)(6151ul)(12289ul)(24593ul) \ |
---|
| 39 | (49157ul)(98317ul)(196613ul)(393241ul)(786433ul) \ |
---|
| 40 | (1572869ul)(3145739ul)(6291469ul)(12582917ul)(25165843ul) \ |
---|
| 41 | (50331653ul)(100663319ul)(201326611ul)(402653189ul)(805306457ul) \ |
---|
| 42 | (1610612741ul)(3221225473ul)(4294967291ul) |
---|
| 43 | |
---|
| 44 | template<class T> struct prime_list_template |
---|
| 45 | { |
---|
| 46 | static std::size_t const value[]; |
---|
| 47 | |
---|
| 48 | #if !defined(SUNPRO_CC) |
---|
| 49 | static std::ptrdiff_t const length; |
---|
| 50 | #else |
---|
| 51 | static std::ptrdiff_t const length |
---|
| 52 | = BOOST_PP_SEQ_SIZE(BOOST_UNORDERED_PRIMES); |
---|
| 53 | #endif |
---|
| 54 | }; |
---|
| 55 | |
---|
| 56 | template<class T> |
---|
| 57 | std::size_t const prime_list_template<T>::value[] = { |
---|
| 58 | BOOST_PP_SEQ_ENUM(BOOST_UNORDERED_PRIMES) |
---|
| 59 | }; |
---|
| 60 | |
---|
| 61 | #if !defined(SUNPRO_CC) |
---|
| 62 | template<class T> |
---|
| 63 | std::ptrdiff_t const prime_list_template<T>::length |
---|
| 64 | = BOOST_PP_SEQ_SIZE(BOOST_UNORDERED_PRIMES); |
---|
| 65 | #endif |
---|
| 66 | |
---|
| 67 | #undef BOOST_UNORDERED_PRIMES |
---|
| 68 | |
---|
| 69 | typedef prime_list_template<std::size_t> prime_list; |
---|
| 70 | |
---|
| 71 | // no throw |
---|
| 72 | inline std::size_t next_prime(std::size_t num) { |
---|
| 73 | std::size_t const* const prime_list_begin = prime_list::value; |
---|
| 74 | std::size_t const* const prime_list_end = prime_list_begin + |
---|
| 75 | prime_list::length; |
---|
| 76 | std::size_t const* bound = |
---|
| 77 | std::lower_bound(prime_list_begin, prime_list_end, num); |
---|
| 78 | if(bound == prime_list_end) |
---|
| 79 | bound--; |
---|
| 80 | return *bound; |
---|
| 81 | } |
---|
| 82 | |
---|
| 83 | // no throw |
---|
| 84 | inline std::size_t prev_prime(std::size_t num) { |
---|
| 85 | std::size_t const* const prime_list_begin = prime_list::value; |
---|
| 86 | std::size_t const* const prime_list_end = prime_list_begin + |
---|
| 87 | prime_list::length; |
---|
| 88 | std::size_t const* bound = |
---|
| 89 | std::upper_bound(prime_list_begin,prime_list_end, num); |
---|
| 90 | if(bound != prime_list_begin) |
---|
| 91 | bound--; |
---|
| 92 | return *bound; |
---|
| 93 | } |
---|
| 94 | |
---|
| 95 | //////////////////////////////////////////////////////////////////////////// |
---|
| 96 | // pair_cast - because some libraries don't have the full pair constructors. |
---|
| 97 | |
---|
| 98 | template <class Dst1, class Dst2, class Src1, class Src2> |
---|
| 99 | inline std::pair<Dst1, Dst2> pair_cast(std::pair<Src1, Src2> const& x) |
---|
| 100 | { |
---|
| 101 | return std::pair<Dst1, Dst2>(Dst1(x.first), Dst2(x.second)); |
---|
| 102 | } |
---|
| 103 | |
---|
| 104 | //////////////////////////////////////////////////////////////////////////// |
---|
| 105 | // insert_size/initial_size |
---|
| 106 | |
---|
| 107 | #if !defined(BOOST_NO_STD_DISTANCE) |
---|
| 108 | using ::std::distance; |
---|
| 109 | #else |
---|
| 110 | template <class ForwardIterator> |
---|
| 111 | inline std::size_t distance(ForwardIterator i, ForwardIterator j) { |
---|
| 112 | std::size_t x; |
---|
| 113 | std::distance(i, j, x); |
---|
| 114 | return x; |
---|
| 115 | } |
---|
| 116 | #endif |
---|
| 117 | |
---|
| 118 | template <class I> |
---|
| 119 | inline std::size_t insert_size(I i, I j, boost::forward_traversal_tag) |
---|
| 120 | { |
---|
| 121 | return std::distance(i, j); |
---|
| 122 | } |
---|
| 123 | |
---|
| 124 | template <class I> |
---|
| 125 | inline std::size_t insert_size(I, I, boost::incrementable_traversal_tag) |
---|
| 126 | { |
---|
| 127 | return 1; |
---|
| 128 | } |
---|
| 129 | |
---|
| 130 | template <class I> |
---|
| 131 | inline std::size_t insert_size(I i, I j) |
---|
| 132 | { |
---|
| 133 | BOOST_DEDUCED_TYPENAME boost::iterator_traversal<I>::type |
---|
| 134 | iterator_traversal_tag; |
---|
| 135 | return insert_size(i, j, iterator_traversal_tag); |
---|
| 136 | } |
---|
| 137 | |
---|
| 138 | template <class I> |
---|
| 139 | inline std::size_t initial_size(I i, I j, |
---|
| 140 | std::size_t num_buckets = boost::unordered_detail::default_bucket_count) |
---|
| 141 | { |
---|
| 142 | return (std::max)(static_cast<std::size_t>(insert_size(i, j)) + 1, |
---|
| 143 | num_buckets); |
---|
| 144 | } |
---|
| 145 | |
---|
| 146 | //////////////////////////////////////////////////////////////////////////// |
---|
| 147 | // Node Constructors |
---|
| 148 | |
---|
| 149 | #if defined(BOOST_UNORDERED_STD_FORWARD) |
---|
| 150 | |
---|
| 151 | template <class T, class... Args> |
---|
| 152 | inline void construct_impl(T*, void* address, Args&&... args) |
---|
| 153 | { |
---|
| 154 | new(address) T(std::forward<Args>(args)...); |
---|
| 155 | } |
---|
| 156 | |
---|
| 157 | #if defined(BOOST_UNORDERED_CPP0X_PAIR) |
---|
| 158 | template <class First, class Second, class Key, class Arg0, class... Args> |
---|
| 159 | inline void construct_impl(std::pair<First, Second>*, void* address, |
---|
| 160 | Key&& k, Arg0&& arg0, Args&&... args) |
---|
| 161 | ) |
---|
| 162 | { |
---|
| 163 | new(address) std::pair<First, Second>(k, |
---|
| 164 | Second(arg0, std::forward<Args>(args)...); |
---|
| 165 | } |
---|
| 166 | #endif |
---|
| 167 | |
---|
| 168 | #else |
---|
| 169 | |
---|
| 170 | #define BOOST_UNORDERED_CONSTRUCT_IMPL(z, num_params, _) \ |
---|
| 171 | template < \ |
---|
| 172 | class T, \ |
---|
| 173 | BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params) \ |
---|
| 174 | > \ |
---|
| 175 | inline void construct_impl( \ |
---|
| 176 | T*, void* address, \ |
---|
| 177 | BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params) \ |
---|
| 178 | ) \ |
---|
| 179 | { \ |
---|
| 180 | new(address) T( \ |
---|
| 181 | BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \ |
---|
| 182 | } \ |
---|
| 183 | \ |
---|
| 184 | template <class First, class Second, class Key, \ |
---|
| 185 | BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params) \ |
---|
| 186 | > \ |
---|
| 187 | inline void construct_impl( \ |
---|
| 188 | std::pair<First, Second>*, void* address, \ |
---|
| 189 | Key const& k, BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \ |
---|
| 190 | { \ |
---|
| 191 | new(address) std::pair<First, Second>(k, \ |
---|
| 192 | Second(BOOST_UNORDERED_CALL_PARAMS(z, num_params))); \ |
---|
| 193 | } |
---|
| 194 | |
---|
| 195 | BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT, |
---|
| 196 | BOOST_UNORDERED_CONSTRUCT_IMPL, _) |
---|
| 197 | |
---|
| 198 | #undef BOOST_UNORDERED_CONSTRUCT_IMPL |
---|
| 199 | #endif |
---|
| 200 | |
---|
| 201 | // hash_node_constructor |
---|
| 202 | // |
---|
| 203 | // Used to construct nodes in an exception safe manner. |
---|
| 204 | |
---|
| 205 | template <class Alloc, class Grouped> |
---|
| 206 | class hash_node_constructor |
---|
| 207 | { |
---|
| 208 | typedef hash_buckets<Alloc, Grouped> buckets; |
---|
| 209 | typedef BOOST_DEDUCED_TYPENAME buckets::node node; |
---|
| 210 | typedef BOOST_DEDUCED_TYPENAME buckets::real_node_ptr real_node_ptr; |
---|
| 211 | typedef BOOST_DEDUCED_TYPENAME buckets::value_type value_type; |
---|
| 212 | |
---|
| 213 | buckets& buckets_; |
---|
| 214 | real_node_ptr node_; |
---|
| 215 | bool node_constructed_; |
---|
| 216 | bool value_constructed_; |
---|
| 217 | |
---|
| 218 | public: |
---|
| 219 | |
---|
| 220 | hash_node_constructor(buckets& m) : |
---|
| 221 | buckets_(m), |
---|
| 222 | node_(), |
---|
| 223 | node_constructed_(false), |
---|
| 224 | value_constructed_(false) |
---|
| 225 | { |
---|
| 226 | } |
---|
| 227 | |
---|
| 228 | ~hash_node_constructor(); |
---|
| 229 | void construct_preamble(); |
---|
| 230 | |
---|
| 231 | #if defined(BOOST_UNORDERED_STD_FORWARD) |
---|
| 232 | template <class... Args> |
---|
| 233 | void construct(Args&&... args) |
---|
| 234 | { |
---|
| 235 | construct_preamble(); |
---|
| 236 | construct_impl((value_type*) 0, node_->address(), |
---|
| 237 | std::forward<Args>(args)...); |
---|
| 238 | value_constructed_ = true; |
---|
| 239 | } |
---|
| 240 | #else |
---|
| 241 | |
---|
| 242 | #define BOOST_UNORDERED_CONSTRUCT(z, num_params, _) \ |
---|
| 243 | template < \ |
---|
| 244 | BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params) \ |
---|
| 245 | > \ |
---|
| 246 | void construct( \ |
---|
| 247 | BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params) \ |
---|
| 248 | ) \ |
---|
| 249 | { \ |
---|
| 250 | construct_preamble(); \ |
---|
| 251 | construct_impl( \ |
---|
| 252 | (value_type*) 0, node_->address(), \ |
---|
| 253 | BOOST_UNORDERED_CALL_PARAMS(z, num_params) \ |
---|
| 254 | ); \ |
---|
| 255 | value_constructed_ = true; \ |
---|
| 256 | } |
---|
| 257 | |
---|
| 258 | BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT, |
---|
| 259 | BOOST_UNORDERED_CONSTRUCT, _) |
---|
| 260 | |
---|
| 261 | #undef BOOST_UNORDERED_CONSTRUCT |
---|
| 262 | |
---|
| 263 | #endif |
---|
| 264 | template <class K, class M> |
---|
| 265 | void construct_pair(K const& k, M*) |
---|
| 266 | { |
---|
| 267 | construct_preamble(); |
---|
| 268 | new(node_->address()) value_type(k, M()); |
---|
| 269 | value_constructed_ = true; |
---|
| 270 | } |
---|
| 271 | |
---|
| 272 | value_type& value() const |
---|
| 273 | { |
---|
| 274 | BOOST_ASSERT(node_); |
---|
| 275 | return node_->value(); |
---|
| 276 | } |
---|
| 277 | |
---|
| 278 | // no throw |
---|
| 279 | BOOST_DEDUCED_TYPENAME buckets::node_ptr release() |
---|
| 280 | { |
---|
| 281 | real_node_ptr p = node_; |
---|
| 282 | node_ = real_node_ptr(); |
---|
| 283 | // node_ptr cast |
---|
| 284 | return buckets_.bucket_alloc().address(*p); |
---|
| 285 | } |
---|
| 286 | |
---|
| 287 | private: |
---|
| 288 | hash_node_constructor(hash_node_constructor const&); |
---|
| 289 | hash_node_constructor& operator=(hash_node_constructor const&); |
---|
| 290 | }; |
---|
| 291 | |
---|
| 292 | // hash_node_constructor |
---|
| 293 | |
---|
| 294 | template <class Alloc, class Grouped> |
---|
| 295 | inline hash_node_constructor<Alloc, Grouped>::~hash_node_constructor() |
---|
| 296 | { |
---|
| 297 | if (node_) { |
---|
| 298 | if (value_constructed_) { |
---|
| 299 | #if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613)) |
---|
| 300 | struct dummy { hash_node<Alloc, Grouped> x; }; |
---|
| 301 | #endif |
---|
| 302 | boost::unordered_detail::destroy(&node_->value()); |
---|
| 303 | } |
---|
| 304 | |
---|
| 305 | if (node_constructed_) |
---|
| 306 | buckets_.node_alloc().destroy(node_); |
---|
| 307 | |
---|
| 308 | buckets_.node_alloc().deallocate(node_, 1); |
---|
| 309 | } |
---|
| 310 | } |
---|
| 311 | |
---|
| 312 | template <class Alloc, class Grouped> |
---|
| 313 | inline void hash_node_constructor<Alloc, Grouped>::construct_preamble() |
---|
| 314 | { |
---|
| 315 | if(!node_) { |
---|
| 316 | node_constructed_ = false; |
---|
| 317 | value_constructed_ = false; |
---|
| 318 | |
---|
| 319 | node_ = buckets_.node_alloc().allocate(1); |
---|
| 320 | buckets_.node_alloc().construct(node_, node()); |
---|
| 321 | node_constructed_ = true; |
---|
| 322 | } |
---|
| 323 | else { |
---|
| 324 | BOOST_ASSERT(node_constructed_ && value_constructed_); |
---|
| 325 | boost::unordered_detail::destroy(&node_->value()); |
---|
| 326 | value_constructed_ = false; |
---|
| 327 | } |
---|
| 328 | } |
---|
| 329 | }} |
---|
| 330 | |
---|
| 331 | #endif |
---|