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 double_to_size_t(double f)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 next_prime(std::size_t num)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 prev_prime(std::size_t num)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> pair_cast(std::pair<Src1,Src2> const & x)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> distance(ForwardIterator i,ForwardIterator j)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> insert_size(I i,I j,boost::forward_traversal_tag)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> insert_size(I,I,boost::incrementable_traversal_tag)125 inline std::size_t insert_size(I, I, boost::incrementable_traversal_tag) 126 { 127 return 1; 128 } 129 130 template <class I> insert_size(I i,I j)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> initial_size(I i,I j,std::size_t num_buckets=boost::unordered_detail::default_bucket_count)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> construct_impl(T *,void * address,Args &&...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_ptr()); 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_ptr()); 326 value_constructed_ = false; 327 } 328 } 329 }} 330 331 #endif 332