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
24namespace immer {
25namespace detail {
26
27template <typename T>
28using aligned_storage_for =
29 typename std::aligned_storage<sizeof(T), alignof(T)>::type;
30
31template <typename T>
32T& auto_const_cast(const T& x) { return const_cast<T&>(x); }
33template <typename T>
34T&& auto_const_cast(const T&& x) { return const_cast<T&&>(std::move(x)); }
35
36template <typename Iter1, typename Iter2>
37auto 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
44template <class T>
45void destroy(T* first, T* last)
46{
47 for (; first != last; ++first)
48 first->~T();
49}
50
51template <class T, class Size>
52void destroy_n(T* p, Size n)
53{
54 auto e = p + n;
55 for (; p != e; ++p)
56 p->~T();
57}
58
59template <typename Heap, typename T, typename... Args>
60T* 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
71struct not_supported_t {};
72struct empty_t {};
73
74template <typename T>
75struct exact_t
76{
77 T value;
78 exact_t(T v) : value{v} {};
79};
80
81template <typename T>
82inline 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
88inline constexpr auto clz_(unsigned int x) { return __builtin_clz(x); }
89inline constexpr auto clz_(unsigned long x) { return __builtin_clzl(x); }
90inline constexpr auto clz_(unsigned long long x) { return __builtin_clzll(x); }
91#endif
92
93template <typename T>
94inline constexpr T log2_aux(T x, T r = 0)
95{
96 return x <= 1 ? r : log2_aux(x >> 1, r + 1);
97}
98
99template <typename T>
100inline 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
106template <typename T>
107inline 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
113template <bool b, typename F>
114auto static_if(F&& f) -> std::enable_if_t<b>
115{ std::forward<F>(f)(empty_t{}); }
116template <bool b, typename F>
117auto static_if(F&& f) -> std::enable_if_t<!b>
118{}
119
120template <bool b, typename R=void, typename F1, typename F2>
121auto static_if(F1&& f1, F2&& f2) -> std::enable_if_t<b, R>
122{ return std::forward<F1>(f1)(empty_t{}); }
123template <bool b, typename R=void, typename F1, typename F2>
124auto static_if(F1&& f1, F2&& f2) -> std::enable_if_t<!b, R>
125{ return std::forward<F2>(f2)(empty_t{}); }
126
127template <typename T, T value>
128struct constantly
129{
130 template <typename... Args>
131 T operator() (Args&&...) const { return value; }
132};
133
134/*!
135 * An alias to `std::distance`
136 */
137template <typename Iterator, typename Sentinel,
138 std::enable_if_t
139 <detail::std_distance_supports_v<Iterator,Sentinel>, bool> = true>
140typename std::iterator_traits<Iterator>::difference_type
141distance(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 */
150template <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>
156typename std::iterator_traits<Iterator>::difference_type
157distance(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 */
171template <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>
177typename std::iterator_traits<Iterator>::difference_type
178distance(Iterator first, Sentinel last)
179{
180 return last - first;
181}
182
183
184
185/*!
186 * An alias to `std::uninitialized_copy`
187 */
188template <typename Iterator, typename Sentinel, typename SinkIter,
189 std::enable_if_t
190 <detail::std_uninitialized_copy_supports_v
191 <Iterator,Sentinel,SinkIter>, bool> = true>
192SinkIter 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 */
201template <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>
206SinkIter 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