diff options
Diffstat (limited to 'include/llvm/ADT/STLExtras.h')
| -rw-r--r-- | include/llvm/ADT/STLExtras.h | 388 |
1 files changed, 299 insertions, 89 deletions
diff --git a/include/llvm/ADT/STLExtras.h b/include/llvm/ADT/STLExtras.h index 3aa8183353215..1cef3933b5d6b 100644 --- a/include/llvm/ADT/STLExtras.h +++ b/include/llvm/ADT/STLExtras.h @@ -17,10 +17,12 @@ #ifndef LLVM_ADT_STLEXTRAS_H #define LLVM_ADT_STLEXTRAS_H +#include "llvm/Support/Compiler.h" #include <cstddef> // for std::size_t #include <cstdlib> // for qsort #include <functional> #include <iterator> +#include <memory> #include <utility> // for std::pair namespace llvm { @@ -53,6 +55,131 @@ struct greater_ptr : public std::binary_function<Ty, Ty, bool> { } }; +/// An efficient, type-erasing, non-owning reference to a callable. This is +/// intended for use as the type of a function parameter that is not used +/// after the function in question returns. +/// +/// This class does not own the callable, so it is not in general safe to store +/// a function_ref. +template<typename Fn> class function_ref; + +#if LLVM_HAS_VARIADIC_TEMPLATES + +template<typename Ret, typename ...Params> +class function_ref<Ret(Params...)> { + Ret (*callback)(intptr_t callable, Params ...params); + intptr_t callable; + + template<typename Callable> + static Ret callback_fn(intptr_t callable, Params ...params) { + return (*reinterpret_cast<Callable*>(callable))( + std::forward<Params>(params)...); + } + +public: + template<typename Callable> + function_ref(Callable &&callable) + : callback(callback_fn<typename std::remove_reference<Callable>::type>), + callable(reinterpret_cast<intptr_t>(&callable)) {} + Ret operator()(Params ...params) const { + return callback(callable, std::forward<Params>(params)...); + } +}; + +#else + +template<typename Ret> +class function_ref<Ret()> { + Ret (*callback)(intptr_t callable); + intptr_t callable; + + template<typename Callable> + static Ret callback_fn(intptr_t callable) { + return (*reinterpret_cast<Callable*>(callable))(); + } + +public: + template<typename Callable> + function_ref(Callable &&callable) + : callback(callback_fn<typename std::remove_reference<Callable>::type>), + callable(reinterpret_cast<intptr_t>(&callable)) {} + Ret operator()() const { return callback(callable); } +}; + +template<typename Ret, typename Param1> +class function_ref<Ret(Param1)> { + Ret (*callback)(intptr_t callable, Param1 param1); + intptr_t callable; + + template<typename Callable> + static Ret callback_fn(intptr_t callable, Param1 param1) { + return (*reinterpret_cast<Callable*>(callable))( + std::forward<Param1>(param1)); + } + +public: + template<typename Callable> + function_ref(Callable &&callable) + : callback(callback_fn<typename std::remove_reference<Callable>::type>), + callable(reinterpret_cast<intptr_t>(&callable)) {} + Ret operator()(Param1 param1) { + return callback(callable, std::forward<Param1>(param1)); + } +}; + +template<typename Ret, typename Param1, typename Param2> +class function_ref<Ret(Param1, Param2)> { + Ret (*callback)(intptr_t callable, Param1 param1, Param2 param2); + intptr_t callable; + + template<typename Callable> + static Ret callback_fn(intptr_t callable, Param1 param1, Param2 param2) { + return (*reinterpret_cast<Callable*>(callable))( + std::forward<Param1>(param1), + std::forward<Param2>(param2)); + } + +public: + template<typename Callable> + function_ref(Callable &&callable) + : callback(callback_fn<typename std::remove_reference<Callable>::type>), + callable(reinterpret_cast<intptr_t>(&callable)) {} + Ret operator()(Param1 param1, Param2 param2) { + return callback(callable, + std::forward<Param1>(param1), + std::forward<Param2>(param2)); + } +}; + +template<typename Ret, typename Param1, typename Param2, typename Param3> +class function_ref<Ret(Param1, Param2, Param3)> { + Ret (*callback)(intptr_t callable, Param1 param1, Param2 param2, Param3 param3); + intptr_t callable; + + template<typename Callable> + static Ret callback_fn(intptr_t callable, Param1 param1, Param2 param2, + Param3 param3) { + return (*reinterpret_cast<Callable*>(callable))( + std::forward<Param1>(param1), + std::forward<Param2>(param2), + std::forward<Param3>(param3)); + } + +public: + template<typename Callable> + function_ref(Callable &&callable) + : callback(callback_fn<typename std::remove_reference<Callable>::type>), + callable(reinterpret_cast<intptr_t>(&callable)) {} + Ret operator()(Param1 param1, Param2 param2, Param3 param3) { + return callback(callable, + std::forward<Param1>(param1), + std::forward<Param2>(param2), + std::forward<Param3>(param3)); + } +}; + +#endif + // deleter - Very very very simple method that is used to invoke operator // delete on something. It is used like this: // @@ -95,8 +222,6 @@ public: inline explicit mapped_iterator(const RootIt &I, UnaryFunc F) : current(I), Fn(F) {} - inline mapped_iterator(const mapped_iterator &It) - : current(It.current), Fn(It.Fn) {} inline value_type operator*() const { // All this work to do this return Fn(*current); // little change @@ -141,82 +266,10 @@ inline mapped_iterator<ItTy, FuncTy> map_iterator(const ItTy &I, FuncTy F) { return mapped_iterator<ItTy, FuncTy>(I, F); } - -// next/prior - These functions unlike std::advance do not modify the -// passed iterator but return a copy. -// -// next(myIt) returns copy of myIt incremented once -// next(myIt, n) returns copy of myIt incremented n times -// prior(myIt) returns copy of myIt decremented once -// prior(myIt, n) returns copy of myIt decremented n times - -template <typename ItTy, typename Dist> -inline ItTy next(ItTy it, Dist n) -{ - std::advance(it, n); - return it; -} - -template <typename ItTy> -inline ItTy next(ItTy it) -{ - return ++it; -} - -template <typename ItTy, typename Dist> -inline ItTy prior(ItTy it, Dist n) -{ - std::advance(it, -n); - return it; -} - -template <typename ItTy> -inline ItTy prior(ItTy it) -{ - return --it; -} - //===----------------------------------------------------------------------===// // Extra additions to <utility> //===----------------------------------------------------------------------===// -// tie - this function ties two objects and returns a temporary object -// that is assignable from a std::pair. This can be used to make code -// more readable when using values returned from functions bundled in -// a std::pair. Since an example is worth 1000 words: -// -// typedef std::map<int, int> Int2IntMap; -// -// Int2IntMap myMap; -// Int2IntMap::iterator where; -// bool inserted; -// tie(where, inserted) = myMap.insert(std::make_pair(123,456)); -// -// if (inserted) -// // do stuff -// else -// // do other stuff -template <typename T1, typename T2> -struct tier { - typedef T1 &first_type; - typedef T2 &second_type; - - first_type first; - second_type second; - - tier(first_type f, second_type s) : first(f), second(s) { } - tier& operator=(const std::pair<T1, T2>& p) { - first = p.first; - second = p.second; - return *this; - } -}; - -template <typename T1, typename T2> -inline tier<T1, T2> tie(T1& f, T2& s) { - return tier<T1, T2>(f, s); -} - /// \brief Function object to check whether the first component of a std::pair /// compares less than the first component of another std::pair. struct less_first { @@ -237,27 +290,20 @@ struct less_second { // Extra additions for arrays //===----------------------------------------------------------------------===// -/// Find where an array ends (for ending iterators) -/// This returns a pointer to the byte immediately -/// after the end of an array. -template<class T, std::size_t N> -inline T *array_endof(T (&x)[N]) { - return x+N; -} - /// Find the length of an array. -template<class T, std::size_t N> -inline size_t array_lengthof(T (&)[N]) { +template <class T, std::size_t N> +LLVM_CONSTEXPR inline size_t array_lengthof(T (&)[N]) { return N; } -/// array_pod_sort_comparator - This is helper function for array_pod_sort, -/// which just uses operator< on T. +/// Adapt std::less<T> for array_pod_sort. template<typename T> inline int array_pod_sort_comparator(const void *P1, const void *P2) { - if (*reinterpret_cast<const T*>(P1) < *reinterpret_cast<const T*>(P2)) + if (std::less<T>()(*reinterpret_cast<const T*>(P1), + *reinterpret_cast<const T*>(P2))) return -1; - if (*reinterpret_cast<const T*>(P2) < *reinterpret_cast<const T*>(P1)) + if (std::less<T>()(*reinterpret_cast<const T*>(P2), + *reinterpret_cast<const T*>(P1))) return 1; return 0; } @@ -280,7 +326,7 @@ inline int (*get_array_pod_sort_comparator(const T &)) /// possible. /// /// This function assumes that you have simple POD-like types that can be -/// compared with operator< and can be moved with memcpy. If this isn't true, +/// compared with std::less and can be moved with memcpy. If this isn't true, /// you should use std::sort. /// /// NOTE: If qsort_r were portable, we could allow a custom comparator and @@ -327,6 +373,170 @@ void DeleteContainerSeconds(Container &C) { C.clear(); } +//===----------------------------------------------------------------------===// +// Extra additions to <memory> +//===----------------------------------------------------------------------===// + +#if LLVM_HAS_VARIADIC_TEMPLATES + +// Implement make_unique according to N3656. + +/// \brief Constructs a `new T()` with the given args and returns a +/// `unique_ptr<T>` which owns the object. +/// +/// Example: +/// +/// auto p = make_unique<int>(); +/// auto p = make_unique<std::tuple<int, int>>(0, 1); +template <class T, class... Args> +typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type +make_unique(Args &&... args) { + return std::unique_ptr<T>(new T(std::forward<Args>(args)...)); +} + +/// \brief Constructs a `new T[n]` with the given args and returns a +/// `unique_ptr<T[]>` which owns the object. +/// +/// \param n size of the new array. +/// +/// Example: +/// +/// auto p = make_unique<int[]>(2); // value-initializes the array with 0's. +template <class T> +typename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0, + std::unique_ptr<T>>::type +make_unique(size_t n) { + return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]()); +} + +/// This function isn't used and is only here to provide better compile errors. +template <class T, class... Args> +typename std::enable_if<std::extent<T>::value != 0>::type +make_unique(Args &&...) LLVM_DELETED_FUNCTION; + +#else + +template <class T> +typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type +make_unique() { + return std::unique_ptr<T>(new T()); +} + +template <class T, class Arg1> +typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type +make_unique(Arg1 &&arg1) { + return std::unique_ptr<T>(new T(std::forward<Arg1>(arg1))); +} + +template <class T, class Arg1, class Arg2> +typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type +make_unique(Arg1 &&arg1, Arg2 &&arg2) { + return std::unique_ptr<T>( + new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2))); +} + +template <class T, class Arg1, class Arg2, class Arg3> +typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type +make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3) { + return std::unique_ptr<T>(new T(std::forward<Arg1>(arg1), + std::forward<Arg2>(arg2), + std::forward<Arg3>(arg3))); +} + +template <class T, class Arg1, class Arg2, class Arg3, class Arg4> +typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type +make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4) { + return std::unique_ptr<T>( + new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2), + std::forward<Arg3>(arg3), std::forward<Arg4>(arg4))); +} + +template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5> +typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type +make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5) { + return std::unique_ptr<T>( + new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2), + std::forward<Arg3>(arg3), std::forward<Arg4>(arg4), + std::forward<Arg5>(arg5))); +} + +template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5, + class Arg6> +typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type +make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5, + Arg6 &&arg6) { + return std::unique_ptr<T>( + new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2), + std::forward<Arg3>(arg3), std::forward<Arg4>(arg4), + std::forward<Arg5>(arg5), std::forward<Arg6>(arg6))); +} + +template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5, + class Arg6, class Arg7> +typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type +make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5, + Arg6 &&arg6, Arg7 &&arg7) { + return std::unique_ptr<T>( + new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2), + std::forward<Arg3>(arg3), std::forward<Arg4>(arg4), + std::forward<Arg5>(arg5), std::forward<Arg6>(arg6), + std::forward<Arg7>(arg7))); +} + +template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5, + class Arg6, class Arg7, class Arg8> +typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type +make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5, + Arg6 &&arg6, Arg7 &&arg7, Arg8 &&arg8) { + return std::unique_ptr<T>( + new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2), + std::forward<Arg3>(arg3), std::forward<Arg4>(arg4), + std::forward<Arg5>(arg5), std::forward<Arg6>(arg6), + std::forward<Arg7>(arg7), std::forward<Arg8>(arg8))); +} + +template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5, + class Arg6, class Arg7, class Arg8, class Arg9> +typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type +make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5, + Arg6 &&arg6, Arg7 &&arg7, Arg8 &&arg8, Arg9 &&arg9) { + return std::unique_ptr<T>( + new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2), + std::forward<Arg3>(arg3), std::forward<Arg4>(arg4), + std::forward<Arg5>(arg5), std::forward<Arg6>(arg6), + std::forward<Arg7>(arg7), std::forward<Arg8>(arg8), + std::forward<Arg9>(arg9))); +} + +template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5, + class Arg6, class Arg7, class Arg8, class Arg9, class Arg10> +typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type +make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5, + Arg6 &&arg6, Arg7 &&arg7, Arg8 &&arg8, Arg9 &&arg9, Arg10 &&arg10) { + return std::unique_ptr<T>( + new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2), + std::forward<Arg3>(arg3), std::forward<Arg4>(arg4), + std::forward<Arg5>(arg5), std::forward<Arg6>(arg6), + std::forward<Arg7>(arg7), std::forward<Arg8>(arg8), + std::forward<Arg9>(arg9), std::forward<Arg10>(arg10))); +} + +template <class T> +typename std::enable_if<std::is_array<T>::value &&std::extent<T>::value == 0, + std::unique_ptr<T>>::type +make_unique(size_t n) { + return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]()); +} + +#endif + +template<typename First, typename Second> +struct pair_hash { + size_t operator()(const std::pair<First, Second> &P) const { + return std::hash<First>()(P.first) * 31 + std::hash<Second>()(P.second); + } +}; + } // End llvm namespace #endif |