//
// immer: immutable data structures for C++
// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
//
// This software is distributed under the Boost Software License, Version 1.0.
// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
//
#pragma once
#include <immer/config.hpp>
#include <cstddef>
#include <memory>
#include <new>
#include <type_traits>
#include <immer/detail/type_traits.hpp>
#if defined(_MSC_VER)
#include <intrin.h> // for __lzcnt*
#endif
namespace immer {
namespace detail {
template <typename T>
using aligned_storage_for =
typename std::aligned_storage<sizeof(T), alignof(T)>::type;
template <typename T>
T& auto_const_cast(const T& x)
{
return const_cast<T&>(x);
}
template <typename T>
T&& auto_const_cast(const T&& x)
{
return const_cast<T&&>(std::move(x));
}
template <typename Iter1, typename Iter2>
auto uninitialized_move(Iter1 in1, Iter1 in2, Iter2 out)
{
return std::uninitialized_copy(
std::make_move_iterator(in1), std::make_move_iterator(in2), out);
}
template <class T>
void destroy(T* first, T* last)
{
for (; first != last; ++first)
first->~T();
}
template <class T, class Size>
void destroy_n(T* p, Size n)
{
auto e = p + n;
for (; p != e; ++p)
p->~T();
}
template <typename Heap, typename T, typename... Args>
T* make(Args&&... args)
{
auto ptr = Heap::allocate(sizeof(T));
try {
return new (ptr) T{std::forward<Args>(args)...};
} catch (...) {
Heap::deallocate(sizeof(T), ptr);
throw;
}
}
struct not_supported_t
{};
struct empty_t
{};
template <typename T>
struct exact_t
{
T value;
exact_t(T v)
: value{v} {};
};
template <typename T>
inline constexpr auto clz_(T) -> not_supported_t
{
IMMER_UNREACHABLE;
return {};
}
#if defined(_MSC_VER)
// inline auto clz_(unsigned short x) { return __lzcnt16(x); }
// inline auto clz_(unsigned int x) { return __lzcnt(x); }
// inline auto clz_(unsigned __int64 x) { return __lzcnt64(x); }
#else
inline constexpr auto clz_(unsigned int x) { return __builtin_clz(x); }
inline constexpr auto clz_(unsigned long x) { return __builtin_clzl(x); }
inline constexpr auto clz_(unsigned long long x) { return __builtin_clzll(x); }
#endif
template <typename T>
inline constexpr T log2_aux(T x, T r = 0)
{
return x <= 1 ? r : log2_aux(x >> 1, r + 1);
}
template <typename T>
inline constexpr auto log2(T x) -> std::
enable_if_t<!std::is_same<decltype(clz_(x)), not_supported_t>::value, T>
{
return x == 0 ? 0 : sizeof(std::size_t) * 8 - 1 - clz_(x);
}
template <typename T>
inline constexpr auto log2(T x)
-> std::enable_if_t<std::is_same<decltype(clz_(x)), not_supported_t>::value,
T>
{
return log2_aux(x);
}
template <bool b, typename F>
auto static_if(F&& f) -> std::enable_if_t<b>
{
std::forward<F>(f)(empty_t{});
}
template <bool b, typename F>
auto static_if(F&& f) -> std::enable_if_t<!b>
{}
template <bool b, typename R = void, typename F1, typename F2>
auto static_if(F1&& f1, F2&& f2) -> std::enable_if_t<b, R>
{
return std::forward<F1>(f1)(empty_t{});
}
template <bool b, typename R = void, typename F1, typename F2>
auto static_if(F1&& f1, F2&& f2) -> std::enable_if_t<!b, R>
{
return std::forward<F2>(f2)(empty_t{});
}
template <typename T, T value>
struct constantly
{
template <typename... Args>
T operator()(Args&&...) const
{
return value;
}
};
/*!
* An alias to `std::distance`
*/
template <typename Iterator,
typename Sentinel,
std::enable_if_t<detail::std_distance_supports_v<Iterator, Sentinel>,
bool> = true>
typename std::iterator_traits<Iterator>::difference_type
distance(Iterator first, Sentinel last)
{
return std::distance(first, last);
}
/*!
* Equivalent of the `std::distance` applied to the sentinel-delimited
* forward range @f$ [first, last) @f$
*/
template <typename Iterator,
typename Sentinel,
std::enable_if_t<
(!detail::std_distance_supports_v<Iterator, Sentinel>) &&detail::
is_forward_iterator_v<Iterator> &&
detail::compatible_sentinel_v<Iterator, Sentinel> &&
(!detail::is_subtractable_v<Sentinel, Iterator>),
bool> = true>
typename std::iterator_traits<Iterator>::difference_type
distance(Iterator first, Sentinel last)
{
std::size_t result = 0;
while (first != last) {
++first;
++result;
}
return result;
}
/*!
* Equivalent of the `std::distance` applied to the sentinel-delimited
* random access range @f$ [first, last) @f$
*/
template <typename Iterator,
typename Sentinel,
std::enable_if_t<
(!detail::std_distance_supports_v<Iterator, Sentinel>) &&detail::
is_forward_iterator_v<Iterator> &&
detail::compatible_sentinel_v<Iterator, Sentinel> &&
detail::is_subtractable_v<Sentinel, Iterator>,
bool> = true>
typename std::iterator_traits<Iterator>::difference_type
distance(Iterator first, Sentinel last)
{
return last - first;
}
/*!
* An alias to `std::uninitialized_copy`
*/
template <
typename Iterator,
typename Sentinel,
typename SinkIter,
std::enable_if_t<
detail::std_uninitialized_copy_supports_v<Iterator, Sentinel, SinkIter>,
bool> = true>
SinkIter uninitialized_copy(Iterator first, Sentinel last, SinkIter d_first)
{
return std::uninitialized_copy(first, last, d_first);
}
/*!
* Equivalent of the `std::uninitialized_copy` applied to the
* sentinel-delimited forward range @f$ [first, last) @f$
*/
template <typename SourceIter,
typename Sent,
typename SinkIter,
std::enable_if_t<
(!detail::std_uninitialized_copy_supports_v<SourceIter,
Sent,
SinkIter>) &&detail::
compatible_sentinel_v<SourceIter, Sent> &&
detail::is_forward_iterator_v<SinkIter>,
bool> = true>
SinkIter uninitialized_copy(SourceIter first, Sent last, SinkIter d_first)
{
auto current = d_first;
try {
while (first != last) {
*current++ = *first;
++first;
}
} catch (...) {
using Value = typename std::iterator_traits<SinkIter>::value_type;
for (; d_first != current; ++d_first) {
d_first->~Value();
}
throw;
}
return current;
}
} // namespace detail
} // namespace immer
