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 <new> |
15 | #include <type_traits> |
16 | #include <memory> |
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 | T& auto_const_cast(const T& x) { return const_cast<T&>(x); } |
33 | template <typename T> |
34 | T&& auto_const_cast(const T&& x) { return const_cast<T&&>(std::move(x)); } |
35 | |
36 | template <typename Iter1, typename Iter2> |
37 | auto uninitialized_move(Iter1 in1, Iter1 in2, Iter2 out) |
38 | { |
39 | return std::uninitialized_copy(std::make_move_iterator(in1), |
40 | std::make_move_iterator(in2), |
41 | out); |
42 | } |
43 | |
44 | template <class T> |
45 | void destroy(T* first, T* last) |
46 | { |
47 | for (; first != last; ++first) |
48 | first->~T(); |
49 | } |
50 | |
51 | template <class T, class Size> |
52 | void destroy_n(T* p, Size n) |
53 | { |
54 | auto e = p + n; |
55 | for (; p != e; ++p) |
56 | p->~T(); |
57 | } |
58 | |
59 | template <typename Heap, typename T, typename... Args> |
60 | T* make(Args&& ...args) |
61 | { |
62 | auto ptr = Heap::allocate(sizeof(T)); |
63 | try { |
64 | return new (ptr) T{std::forward<Args>(args)...}; |
65 | } catch (...) { |
66 | Heap::deallocate(sizeof(T), ptr); |
67 | throw; |
68 | } |
69 | } |
70 | |
71 | struct not_supported_t {}; |
72 | struct empty_t {}; |
73 | |
74 | template <typename T> |
75 | struct exact_t |
76 | { |
77 | T value; |
78 | exact_t(T v) : value{v} {}; |
79 | }; |
80 | |
81 | template <typename T> |
82 | inline constexpr auto clz_(T) -> not_supported_t { IMMER_UNREACHABLE; return {}; } |
83 | #if defined(_MSC_VER) |
84 | // inline auto clz_(unsigned short x) { return __lzcnt16(x); } |
85 | // inline auto clz_(unsigned int x) { return __lzcnt(x); } |
86 | // inline auto clz_(unsigned __int64 x) { return __lzcnt64(x); } |
87 | #else |
88 | inline constexpr auto clz_(unsigned int x) { return __builtin_clz(x); } |
89 | inline constexpr auto clz_(unsigned long x) { return __builtin_clzl(x); } |
90 | inline constexpr auto clz_(unsigned long long x) { return __builtin_clzll(x); } |
91 | #endif |
92 | |
93 | template <typename T> |
94 | inline constexpr T log2_aux(T x, T r = 0) |
95 | { |
96 | return x <= 1 ? r : log2_aux(x >> 1, r + 1); |
97 | } |
98 | |
99 | template <typename T> |
100 | inline constexpr auto log2(T x) |
101 | -> std::enable_if_t<!std::is_same<decltype(clz_(x)), not_supported_t>::value, T> |
102 | { |
103 | return x == 0 ? 0 : sizeof(std::size_t) * 8 - 1 - clz_(x); |
104 | } |
105 | |
106 | template <typename T> |
107 | inline constexpr auto log2(T x) |
108 | -> std::enable_if_t<std::is_same<decltype(clz_(x)), not_supported_t>::value, T> |
109 | { |
110 | return log2_aux(x); |
111 | } |
112 | |
113 | template <bool b, typename F> |
114 | auto static_if(F&& f) -> std::enable_if_t<b> |
115 | { std::forward<F>(f)(empty_t{}); } |
116 | template <bool b, typename F> |
117 | auto static_if(F&& f) -> std::enable_if_t<!b> |
118 | {} |
119 | |
120 | template <bool b, typename R=void, typename F1, typename F2> |
121 | auto static_if(F1&& f1, F2&& f2) -> std::enable_if_t<b, R> |
122 | { return std::forward<F1>(f1)(empty_t{}); } |
123 | template <bool b, typename R=void, typename F1, typename F2> |
124 | auto static_if(F1&& f1, F2&& f2) -> std::enable_if_t<!b, R> |
125 | { return std::forward<F2>(f2)(empty_t{}); } |
126 | |
127 | template <typename T, T value> |
128 | struct constantly |
129 | { |
130 | template <typename... Args> |
131 | T operator() (Args&&...) const { return value; } |
132 | }; |
133 | |
134 | /*! |
135 | * An alias to `std::distance` |
136 | */ |
137 | template <typename Iterator, typename Sentinel, |
138 | std::enable_if_t |
139 | <detail::std_distance_supports_v<Iterator,Sentinel>, bool> = true> |
140 | typename std::iterator_traits<Iterator>::difference_type |
141 | distance(Iterator first, Sentinel last) |
142 | { |
143 | return std::distance(first, last); |
144 | } |
145 | |
146 | /*! |
147 | * Equivalent of the `std::distance` applied to the sentinel-delimited |
148 | * forward range @f$ [first, last) @f$ |
149 | */ |
150 | template <typename Iterator, typename Sentinel, |
151 | std::enable_if_t |
152 | <(!detail::std_distance_supports_v<Iterator,Sentinel>) |
153 | && detail::is_forward_iterator_v<Iterator> |
154 | && detail::compatible_sentinel_v<Iterator,Sentinel> |
155 | && (!detail::is_subtractable_v<Sentinel, Iterator>), bool> = true> |
156 | typename std::iterator_traits<Iterator>::difference_type |
157 | distance(Iterator first, Sentinel last) |
158 | { |
159 | std::size_t result = 0; |
160 | while (first != last) { |
161 | ++first; |
162 | ++result; |
163 | } |
164 | return result; |
165 | } |
166 | |
167 | /*! |
168 | * Equivalent of the `std::distance` applied to the sentinel-delimited |
169 | * random access range @f$ [first, last) @f$ |
170 | */ |
171 | template <typename Iterator, typename Sentinel, |
172 | std::enable_if_t |
173 | <(!detail::std_distance_supports_v<Iterator,Sentinel>) |
174 | && detail::is_forward_iterator_v<Iterator> |
175 | && detail::compatible_sentinel_v<Iterator,Sentinel> |
176 | && detail::is_subtractable_v<Sentinel, Iterator>, bool> = true> |
177 | typename std::iterator_traits<Iterator>::difference_type |
178 | distance(Iterator first, Sentinel last) |
179 | { |
180 | return last - first; |
181 | } |
182 | |
183 | |
184 | |
185 | /*! |
186 | * An alias to `std::uninitialized_copy` |
187 | */ |
188 | template <typename Iterator, typename Sentinel, typename SinkIter, |
189 | std::enable_if_t |
190 | <detail::std_uninitialized_copy_supports_v |
191 | <Iterator,Sentinel,SinkIter>, bool> = true> |
192 | SinkIter uninitialized_copy(Iterator first, Sentinel last, SinkIter d_first) |
193 | { |
194 | return std::uninitialized_copy(first, last, d_first); |
195 | } |
196 | |
197 | /*! |
198 | * Equivalent of the `std::uninitialized_copy` applied to the |
199 | * sentinel-delimited forward range @f$ [first, last) @f$ |
200 | */ |
201 | template <typename SourceIter, typename Sent, typename SinkIter, |
202 | std::enable_if_t |
203 | <(!detail::std_uninitialized_copy_supports_v<SourceIter, Sent, SinkIter>) |
204 | && detail::compatible_sentinel_v<SourceIter,Sent> |
205 | && detail::is_forward_iterator_v<SinkIter>, bool> = true> |
206 | SinkIter uninitialized_copy(SourceIter first, Sent last, SinkIter d_first) |
207 | { |
208 | auto current = d_first; |
209 | try { |
210 | while (first != last) { |
211 | *current++ = *first; |
212 | ++first; |
213 | } |
214 | } catch (...) { |
215 | using Value = typename std::iterator_traits<SinkIter>::value_type; |
216 | for (;d_first != current; ++d_first){ |
217 | d_first->~Value(); |
218 | } |
219 | throw; |
220 | } |
221 | return current; |
222 | } |
223 | |
224 | } // namespace detail |
225 | } // namespace immer |
226 | |