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