diff options
Diffstat (limited to 'immer/detail/util.hpp')
| -rw-r--r-- | immer/detail/util.hpp | 258 |
1 files changed, 258 insertions, 0 deletions
diff --git a/immer/detail/util.hpp b/immer/detail/util.hpp new file mode 100644 index 000000000000..fb2a520fc78f --- /dev/null +++ b/immer/detail/util.hpp @@ -0,0 +1,258 @@ +// +// 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 |