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 |
---|