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

source code of boost/boost/unordered/detail/util.hpp