1 | |
2 | // Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard. |
3 | // Copyright (C) 2005-2011 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 <boost/config.hpp> |
11 | #if defined(BOOST_HAS_PRAGMA_ONCE) |
12 | #pragma once |
13 | #endif |
14 | |
15 | #include <boost/type_traits/is_convertible.hpp> |
16 | #include <boost/type_traits/is_empty.hpp> |
17 | #include <boost/iterator/iterator_categories.hpp> |
18 | #include <boost/utility/enable_if.hpp> |
19 | #include <boost/detail/select_type.hpp> |
20 | #include <boost/move/move.hpp> |
21 | #include <boost/preprocessor/seq/size.hpp> |
22 | #include <boost/preprocessor/seq/enum.hpp> |
23 | #include <boost/swap.hpp> |
24 | |
25 | namespace boost { namespace unordered { namespace detail { |
26 | |
27 | static const float minimum_max_load_factor = 1e-3f; |
28 | static const std::size_t default_bucket_count = 11; |
29 | struct move_tag {}; |
30 | struct empty_emplace {}; |
31 | |
32 | namespace func { |
33 | template <class T> |
34 | inline void ignore_unused_variable_warning(T const&) {} |
35 | } |
36 | |
37 | //////////////////////////////////////////////////////////////////////////// |
38 | // iterator SFINAE |
39 | |
40 | template <typename I> |
41 | struct is_forward : |
42 | boost::is_convertible< |
43 | typename boost::iterator_traversal<I>::type, |
44 | boost::forward_traversal_tag> |
45 | {}; |
46 | |
47 | template <typename I, typename ReturnType> |
48 | struct enable_if_forward : |
49 | boost::enable_if_c< |
50 | boost::unordered::detail::is_forward<I>::value, |
51 | ReturnType> |
52 | {}; |
53 | |
54 | template <typename I, typename ReturnType> |
55 | struct disable_if_forward : |
56 | boost::disable_if_c< |
57 | boost::unordered::detail::is_forward<I>::value, |
58 | ReturnType> |
59 | {}; |
60 | |
61 | //////////////////////////////////////////////////////////////////////////// |
62 | // primes |
63 | |
64 | #define BOOST_UNORDERED_PRIMES \ |
65 | (17ul)(29ul)(37ul)(53ul)(67ul)(79ul) \ |
66 | (97ul)(131ul)(193ul)(257ul)(389ul)(521ul)(769ul) \ |
67 | (1031ul)(1543ul)(2053ul)(3079ul)(6151ul)(12289ul)(24593ul) \ |
68 | (49157ul)(98317ul)(196613ul)(393241ul)(786433ul) \ |
69 | (1572869ul)(3145739ul)(6291469ul)(12582917ul)(25165843ul) \ |
70 | (50331653ul)(100663319ul)(201326611ul)(402653189ul)(805306457ul) \ |
71 | (1610612741ul)(3221225473ul)(4294967291ul) |
72 | |
73 | template<class T> struct prime_list_template |
74 | { |
75 | static std::size_t const value[]; |
76 | |
77 | #if !defined(SUNPRO_CC) |
78 | static std::ptrdiff_t const length; |
79 | #else |
80 | static std::ptrdiff_t const length |
81 | = BOOST_PP_SEQ_SIZE(BOOST_UNORDERED_PRIMES); |
82 | #endif |
83 | }; |
84 | |
85 | template<class T> |
86 | std::size_t const prime_list_template<T>::value[] = { |
87 | BOOST_PP_SEQ_ENUM(BOOST_UNORDERED_PRIMES) |
88 | }; |
89 | |
90 | #if !defined(SUNPRO_CC) |
91 | template<class T> |
92 | std::ptrdiff_t const prime_list_template<T>::length |
93 | = BOOST_PP_SEQ_SIZE(BOOST_UNORDERED_PRIMES); |
94 | #endif |
95 | |
96 | #undef BOOST_UNORDERED_PRIMES |
97 | |
98 | typedef prime_list_template<std::size_t> prime_list; |
99 | |
100 | // no throw |
101 | inline std::size_t next_prime(std::size_t num) { |
102 | std::size_t const* const prime_list_begin = prime_list::value; |
103 | std::size_t const* const prime_list_end = prime_list_begin + |
104 | prime_list::length; |
105 | std::size_t const* bound = |
106 | std::lower_bound(first: prime_list_begin, last: prime_list_end, val: num); |
107 | if(bound == prime_list_end) |
108 | bound--; |
109 | return *bound; |
110 | } |
111 | |
112 | // no throw |
113 | inline std::size_t prev_prime(std::size_t num) { |
114 | std::size_t const* const prime_list_begin = prime_list::value; |
115 | std::size_t const* const prime_list_end = prime_list_begin + |
116 | prime_list::length; |
117 | std::size_t const* bound = |
118 | std::upper_bound(first: prime_list_begin,last: prime_list_end, val: num); |
119 | if(bound != prime_list_begin) |
120 | bound--; |
121 | return *bound; |
122 | } |
123 | |
124 | //////////////////////////////////////////////////////////////////////////// |
125 | // insert_size/initial_size |
126 | |
127 | #if !defined(BOOST_NO_STD_DISTANCE) |
128 | |
129 | using ::std::distance; |
130 | |
131 | #else |
132 | |
133 | template <class ForwardIterator> |
134 | inline std::size_t distance(ForwardIterator i, ForwardIterator j) { |
135 | std::size_t x; |
136 | std::distance(i, j, x); |
137 | return x; |
138 | } |
139 | |
140 | #endif |
141 | |
142 | template <class I> |
143 | inline typename |
144 | boost::unordered::detail::enable_if_forward<I, std::size_t>::type |
145 | insert_size(I i, I j) |
146 | { |
147 | return std::distance(i, j); |
148 | } |
149 | |
150 | template <class I> |
151 | inline typename |
152 | boost::unordered::detail::disable_if_forward<I, std::size_t>::type |
153 | insert_size(I, I) |
154 | { |
155 | return 1; |
156 | } |
157 | |
158 | template <class I> |
159 | inline std::size_t initial_size(I i, I j, |
160 | std::size_t num_buckets = |
161 | boost::unordered::detail::default_bucket_count) |
162 | { |
163 | // TODO: Why +1? |
164 | return (std::max)( |
165 | boost::unordered::detail::insert_size(i, j) + 1, |
166 | num_buckets); |
167 | } |
168 | |
169 | //////////////////////////////////////////////////////////////////////////// |
170 | // compressed |
171 | |
172 | template <typename T, int Index> |
173 | struct compressed_base : private T |
174 | { |
175 | compressed_base(T const& x) : T(x) {} |
176 | compressed_base(T& x, move_tag) : T(boost::move(x)) {} |
177 | |
178 | T& get() { return *this; } |
179 | T const& get() const { return *this; } |
180 | }; |
181 | |
182 | template <typename T, int Index> |
183 | struct uncompressed_base |
184 | { |
185 | uncompressed_base(T const& x) : value_(x) {} |
186 | uncompressed_base(T& x, move_tag) : value_(boost::move(x)) {} |
187 | |
188 | T& get() { return value_; } |
189 | T const& get() const { return value_; } |
190 | private: |
191 | T value_; |
192 | }; |
193 | |
194 | template <typename T, int Index> |
195 | struct generate_base |
196 | : boost::detail::if_true< |
197 | boost::is_empty<T>::value |
198 | >:: BOOST_NESTED_TEMPLATE then< |
199 | boost::unordered::detail::compressed_base<T, Index>, |
200 | boost::unordered::detail::uncompressed_base<T, Index> |
201 | > |
202 | {}; |
203 | |
204 | template <typename T1, typename T2> |
205 | struct compressed |
206 | : private boost::unordered::detail::generate_base<T1, 1>::type, |
207 | private boost::unordered::detail::generate_base<T2, 2>::type |
208 | { |
209 | typedef typename generate_base<T1, 1>::type base1; |
210 | typedef typename generate_base<T2, 2>::type base2; |
211 | |
212 | typedef T1 first_type; |
213 | typedef T2 second_type; |
214 | |
215 | first_type& first() { |
216 | return static_cast<base1*>(this)->get(); |
217 | } |
218 | |
219 | first_type const& first() const { |
220 | return static_cast<base1 const*>(this)->get(); |
221 | } |
222 | |
223 | second_type& second() { |
224 | return static_cast<base2*>(this)->get(); |
225 | } |
226 | |
227 | second_type const& second() const { |
228 | return static_cast<base2 const*>(this)->get(); |
229 | } |
230 | |
231 | template <typename First, typename Second> |
232 | compressed(First const& x1, Second const& x2) |
233 | : base1(x1), base2(x2) {} |
234 | |
235 | compressed(compressed const& x) |
236 | : base1(x.first()), base2(x.second()) {} |
237 | |
238 | compressed(compressed& x, move_tag m) |
239 | : base1(x.first(), m), base2(x.second(), m) {} |
240 | |
241 | void assign(compressed const& x) |
242 | { |
243 | first() = x.first(); |
244 | second() = x.second(); |
245 | } |
246 | |
247 | void move_assign(compressed& x) |
248 | { |
249 | first() = boost::move(x.first()); |
250 | second() = boost::move(x.second()); |
251 | } |
252 | |
253 | void swap(compressed& x) |
254 | { |
255 | boost::swap(first(), x.first()); |
256 | boost::swap(second(), x.second()); |
257 | } |
258 | |
259 | private: |
260 | // Prevent assignment just to make use of assign or |
261 | // move_assign explicit. |
262 | compressed& operator=(compressed const&); |
263 | }; |
264 | }}} |
265 | |
266 | #endif |
267 | |