Line data Source code
1 : //
2 : // immer: immutable data structures for C++
3 : // Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
4 : //
5 : // This software is distributed under the Boost Software License, Version 1.0.
6 : // See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
7 : //
8 :
9 : #pragma once
10 :
11 : #include <immer/config.hpp>
12 :
13 : #include <cstddef>
14 : #include <memory>
15 : #include <new>
16 : #include <type_traits>
17 :
18 : #include <immer/detail/type_traits.hpp>
19 :
20 : #if defined(_MSC_VER)
21 : #include <intrin.h> // for __lzcnt*
22 : #endif
23 :
24 : namespace immer {
25 : namespace detail {
26 :
27 : template <typename T>
28 : using aligned_storage_for =
29 : typename std::aligned_storage<sizeof(T), alignof(T)>::type;
30 :
31 : template <typename T>
32 4378459 : T& auto_const_cast(const T& x)
33 : {
34 4378459 : return const_cast<T&>(x);
35 : }
36 : template <typename T>
37 : T&& auto_const_cast(const T&& x)
38 : {
39 : return const_cast<T&&>(std::move(x));
40 : }
41 :
42 : template <typename Iter1, typename Iter2>
43 : auto uninitialized_move(Iter1 in1, Iter1 in2, Iter2 out)
44 : {
45 : return std::uninitialized_copy(
46 : std::make_move_iterator(in1), std::make_move_iterator(in2), out);
47 : }
48 :
49 : template <class T>
50 : void destroy(T* first, T* last)
51 : {
52 : for (; first != last; ++first)
53 : first->~T();
54 : }
55 :
56 : template <class T, class Size>
57 30239 : void destroy_n(T* p, Size n)
58 : {
59 30239 : auto e = p + n;
60 161568 : for (; p != e; ++p)
61 131329 : p->~T();
62 30239 : }
63 :
64 : template <typename Heap, typename T, typename... Args>
65 : T* make(Args&&... args)
66 : {
67 : auto ptr = Heap::allocate(sizeof(T));
68 : IMMER_TRY {
69 : return new (ptr) T{std::forward<Args>(args)...};
70 : }
71 : IMMER_CATCH (...) {
72 : Heap::deallocate(sizeof(T), ptr);
73 : IMMER_RETHROW;
74 : }
75 : }
76 :
77 : struct not_supported_t
78 : {};
79 : struct empty_t
80 : {};
81 :
82 : template <typename T>
83 : struct exact_t
84 : {
85 : T value;
86 : exact_t(T v)
87 : : value{v} {};
88 : };
89 :
90 : template <typename T>
91 : inline constexpr auto clz_(T) -> not_supported_t
92 : {
93 : IMMER_UNREACHABLE;
94 : return {};
95 : }
96 : #if defined(_MSC_VER)
97 : // inline auto clz_(unsigned short x) { return __lzcnt16(x); }
98 : // inline auto clz_(unsigned int x) { return __lzcnt(x); }
99 : // inline auto clz_(unsigned __int64 x) { return __lzcnt64(x); }
100 : #else
101 : inline constexpr auto clz_(unsigned int x) { return __builtin_clz(x); }
102 : inline constexpr auto clz_(unsigned long x) { return __builtin_clzl(x); }
103 : inline constexpr auto clz_(unsigned long long x) { return __builtin_clzll(x); }
104 : #endif
105 :
106 : template <typename T>
107 : inline constexpr T log2_aux(T x, T r = 0)
108 : {
109 : return x <= 1 ? r : log2_aux(x >> 1, r + 1);
110 : }
111 :
112 : template <typename T>
113 : inline constexpr auto log2(T x) -> std::
114 : enable_if_t<!std::is_same<decltype(clz_(x)), not_supported_t>::value, T>
115 : {
116 : return x == 0 ? 0 : sizeof(std::size_t) * 8 - 1 - clz_(x);
117 : }
118 :
119 : template <typename T>
120 : inline constexpr auto log2(T x)
121 : -> std::enable_if_t<std::is_same<decltype(clz_(x)), not_supported_t>::value,
122 : T>
123 : {
124 : return log2_aux(x);
125 : }
126 :
127 : template <typename T>
128 : constexpr T ipow(T num, unsigned int pow)
129 : {
130 : return pow == 0 ? 1 : num * ipow(num, pow - 1);
131 : }
132 :
133 : template <bool b, typename F>
134 : auto static_if(F&& f) -> std::enable_if_t<b>
135 : {
136 : std::forward<F>(f)(empty_t{});
137 : }
138 : template <bool b, typename F>
139 : auto static_if(F&& f) -> std::enable_if_t<!b>
140 : {}
141 :
142 : template <bool b, typename R = void, typename F1, typename F2>
143 : auto static_if(F1&& f1, F2&& f2) -> std::enable_if_t<b, R>
144 : {
145 : return std::forward<F1>(f1)(empty_t{});
146 : }
147 : template <bool b, typename R = void, typename F1, typename F2>
148 : auto static_if(F1&& f1, F2&& f2) -> std::enable_if_t<!b, R>
149 : {
150 : return std::forward<F2>(f2)(empty_t{});
151 : }
152 :
153 : template <typename T, T value>
154 : struct constantly
155 : {
156 : template <typename... Args>
157 1827 : T operator()(Args&&...) const
158 : {
159 : return value;
160 : }
161 : };
162 :
163 : /*!
164 : * An alias to `std::distance`
165 : */
166 : template <typename Iterator,
167 : typename Sentinel,
168 : std::enable_if_t<detail::std_distance_supports_v<Iterator, Sentinel>,
169 : bool> = true>
170 : typename std::iterator_traits<Iterator>::difference_type
171 : distance(Iterator first, Sentinel last)
172 : {
173 : return std::distance(first, last);
174 : }
175 :
176 : /*!
177 : * Equivalent of the `std::distance` applied to the sentinel-delimited
178 : * forward range @f$ [first, last) @f$
179 : */
180 : template <typename Iterator,
181 : typename Sentinel,
182 : std::enable_if_t<
183 : (!detail::std_distance_supports_v<Iterator, Sentinel>) &&detail::
184 : is_forward_iterator_v<Iterator> &&
185 : detail::compatible_sentinel_v<Iterator, Sentinel> &&
186 : (!detail::is_subtractable_v<Sentinel, Iterator>),
187 : bool> = true>
188 : typename std::iterator_traits<Iterator>::difference_type
189 : distance(Iterator first, Sentinel last)
190 : {
191 : std::size_t result = 0;
192 : while (first != last) {
193 : ++first;
194 : ++result;
195 : }
196 : return result;
197 : }
198 :
199 : /*!
200 : * Equivalent of the `std::distance` applied to the sentinel-delimited
201 : * random access range @f$ [first, last) @f$
202 : */
203 : template <typename Iterator,
204 : typename Sentinel,
205 : std::enable_if_t<
206 : (!detail::std_distance_supports_v<Iterator, Sentinel>) &&detail::
207 : is_forward_iterator_v<Iterator> &&
208 : detail::compatible_sentinel_v<Iterator, Sentinel> &&
209 : detail::is_subtractable_v<Sentinel, Iterator>,
210 : bool> = true>
211 : typename std::iterator_traits<Iterator>::difference_type
212 : distance(Iterator first, Sentinel last)
213 : {
214 : return last - first;
215 : }
216 :
217 : /*!
218 : * An alias to `std::uninitialized_copy`
219 : */
220 : template <
221 : typename Iterator,
222 : typename Sentinel,
223 : typename SinkIter,
224 : std::enable_if_t<
225 : detail::std_uninitialized_copy_supports_v<Iterator, Sentinel, SinkIter>,
226 : bool> = true>
227 : SinkIter uninitialized_copy(Iterator first, Sentinel last, SinkIter d_first)
228 : {
229 : return std::uninitialized_copy(first, last, d_first);
230 : }
231 :
232 : /*!
233 : * Equivalent of the `std::uninitialized_copy` applied to the
234 : * sentinel-delimited forward range @f$ [first, last) @f$
235 : */
236 : template <typename SourceIter,
237 : typename Sent,
238 : typename SinkIter,
239 : std::enable_if_t<
240 : (!detail::std_uninitialized_copy_supports_v<SourceIter,
241 : Sent,
242 : SinkIter>) &&detail::
243 : compatible_sentinel_v<SourceIter, Sent> &&
244 : detail::is_forward_iterator_v<SinkIter>,
245 : bool> = true>
246 : SinkIter uninitialized_copy(SourceIter first, Sent last, SinkIter d_first)
247 : {
248 : auto current = d_first;
249 : IMMER_TRY {
250 : while (first != last) {
251 : *current++ = *first;
252 : ++first;
253 : }
254 : }
255 : IMMER_CATCH (...) {
256 : using Value = typename std::iterator_traits<SinkIter>::value_type;
257 : for (; d_first != current; ++d_first) {
258 : d_first->~Value();
259 : }
260 : IMMER_RETHROW;
261 : }
262 : return current;
263 : }
264 :
265 : } // namespace detail
266 : } // namespace immer
|
