#define LLVM_ADT_STLEXTRAS_H
#include "llvm/Support/Compiler.h"
+#include <algorithm> // for std::all_of
+#include <cassert>
#include <cstddef> // for std::size_t
#include <cstdlib> // for qsort
#include <functional>
/// 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)(void *callable, Params ...params);
- void *callable;
+ Ret (*callback)(intptr_t callable, Params ...params);
+ intptr_t callable;
template<typename Callable>
- static Ret callback_fn(void *callable, Params ...params) {
+ 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)
+ template <typename Callable>
+ function_ref(Callable &&callable,
+ typename std::enable_if<
+ !std::is_same<typename std::remove_reference<Callable>::type,
+ function_ref>::value>::type * = nullptr)
: callback(callback_fn<typename std::remove_reference<Callable>::type>),
- callable(reinterpret_cast<void *>(&callable)) {}
+ 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)(void *callable);
- void *callable;
-
- template<typename Callable>
- static Ret callback_fn(void *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<void *>(&callable)) {}
- Ret operator()() const { return callback(callable); }
-};
-
-template<typename Ret, typename Param1>
-class function_ref<Ret(Param1)> {
- Ret (*callback)(void *callable, Param1 param1);
- void *callable;
-
- template<typename Callable>
- static Ret callback_fn(void *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<void *>(&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)(void *callable, Param1 param1, Param2 param2);
- void *callable;
-
- template<typename Callable>
- static Ret callback_fn(void *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<void *>(&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)(void *callable, Param1 param1, Param2 param2, Param3 param3);
- void *callable;
-
- template<typename Callable>
- static Ret callback_fn(void *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<void *>(&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:
//
typedef void reference; // Can't modify value returned by fn
typedef RootIt iterator_type;
- typedef mapped_iterator<RootIt, UnaryFunc> _Self;
inline const RootIt &getCurrent() const { return current; }
inline const UnaryFunc &getFunc() const { return Fn; }
return Fn(*current); // little change
}
- _Self& operator++() { ++current; return *this; }
- _Self& operator--() { --current; return *this; }
- _Self operator++(int) { _Self __tmp = *this; ++current; return __tmp; }
- _Self operator--(int) { _Self __tmp = *this; --current; return __tmp; }
- _Self operator+ (difference_type n) const {
- return _Self(current + n, Fn);
+ mapped_iterator &operator++() {
+ ++current;
+ return *this;
+ }
+ mapped_iterator &operator--() {
+ --current;
+ return *this;
+ }
+ mapped_iterator operator++(int) {
+ mapped_iterator __tmp = *this;
+ ++current;
+ return __tmp;
}
- _Self& operator+= (difference_type n) { current += n; return *this; }
- _Self operator- (difference_type n) const {
- return _Self(current - n, Fn);
+ mapped_iterator operator--(int) {
+ mapped_iterator __tmp = *this;
+ --current;
+ return __tmp;
+ }
+ mapped_iterator operator+(difference_type n) const {
+ return mapped_iterator(current + n, Fn);
+ }
+ mapped_iterator &operator+=(difference_type n) {
+ current += n;
+ return *this;
+ }
+ mapped_iterator operator-(difference_type n) const {
+ return mapped_iterator(current - n, Fn);
+ }
+ mapped_iterator &operator-=(difference_type n) {
+ current -= n;
+ return *this;
}
- _Self& operator-= (difference_type n) { current -= n; return *this; }
reference operator[](difference_type n) const { return *(*this + n); }
- inline bool operator!=(const _Self &X) const { return !operator==(X); }
- inline bool operator==(const _Self &X) const { return current == X.current; }
- inline bool operator< (const _Self &X) const { return current < X.current; }
+ bool operator!=(const mapped_iterator &X) const { return !operator==(X); }
+ bool operator==(const mapped_iterator &X) const {
+ return current == X.current;
+ }
+ bool operator<(const mapped_iterator &X) const { return current < X.current; }
- inline difference_type operator-(const _Self &X) const {
+ difference_type operator-(const mapped_iterator &X) const {
return current - X.current;
}
};
-template <class _Iterator, class Func>
-inline mapped_iterator<_Iterator, Func>
-operator+(typename mapped_iterator<_Iterator, Func>::difference_type N,
- const mapped_iterator<_Iterator, Func>& X) {
- return mapped_iterator<_Iterator, Func>(X.getCurrent() - N, X.getFunc());
+template <class Iterator, class Func>
+inline mapped_iterator<Iterator, Func>
+operator+(typename mapped_iterator<Iterator, Func>::difference_type N,
+ const mapped_iterator<Iterator, Func> &X) {
+ return mapped_iterator<Iterator, Func>(X.getCurrent() - N, X.getFunc());
}
return mapped_iterator<ItTy, FuncTy>(I, F);
}
+/// \brief Metafunction to determine if type T has a member called rbegin().
+template <typename T> struct has_rbegin {
+ template <typename U> static char(&f(const U &, decltype(&U::rbegin)))[1];
+ static char(&f(...))[2];
+ const static bool value = sizeof(f(std::declval<T>(), nullptr)) == 1;
+};
+
+// Returns an iterator_range over the given container which iterates in reverse.
+// Note that the container must have rbegin()/rend() methods for this to work.
+template <typename ContainerTy>
+auto reverse(ContainerTy &&C,
+ typename std::enable_if<has_rbegin<ContainerTy>::value>::type * =
+ nullptr) -> decltype(make_range(C.rbegin(), C.rend())) {
+ return make_range(C.rbegin(), C.rend());
+}
+
+// Returns a std::reverse_iterator wrapped around the given iterator.
+template <typename IteratorTy>
+std::reverse_iterator<IteratorTy> make_reverse_iterator(IteratorTy It) {
+ return std::reverse_iterator<IteratorTy>(It);
+}
+
+// Returns an iterator_range over the given container which iterates in reverse.
+// Note that the container must have begin()/end() methods which return
+// bidirectional iterators for this to work.
+template <typename ContainerTy>
+auto reverse(
+ ContainerTy &&C,
+ typename std::enable_if<!has_rbegin<ContainerTy>::value>::type * = nullptr)
+ -> decltype(make_range(llvm::make_reverse_iterator(std::end(C)),
+ llvm::make_reverse_iterator(std::begin(C)))) {
+ return make_range(llvm::make_reverse_iterator(std::end(C)),
+ llvm::make_reverse_iterator(std::begin(C)));
+}
+
//===----------------------------------------------------------------------===//
// Extra additions to <utility>
//===----------------------------------------------------------------------===//
}
};
+// A subset of N3658. More stuff can be added as-needed.
+
+/// \brief Represents a compile-time sequence of integers.
+template <class T, T... I> struct integer_sequence {
+ typedef T value_type;
+
+ static LLVM_CONSTEXPR size_t size() { return sizeof...(I); }
+};
+
+/// \brief Alias for the common case of a sequence of size_ts.
+template <size_t... I>
+struct index_sequence : integer_sequence<std::size_t, I...> {};
+
+template <std::size_t N, std::size_t... I>
+struct build_index_impl : build_index_impl<N - 1, N - 1, I...> {};
+template <std::size_t... I>
+struct build_index_impl<0, I...> : index_sequence<I...> {};
+
+/// \brief Creates a compile-time integer sequence for a parameter pack.
+template <class... Ts>
+struct index_sequence_for : build_index_impl<sizeof...(Ts)> {};
+
//===----------------------------------------------------------------------===//
// Extra additions for arrays
//===----------------------------------------------------------------------===//
/// default to std::less.
template<class IteratorTy>
inline void array_pod_sort(IteratorTy Start, IteratorTy End) {
- // Don't dereference start iterator of empty sequence.
- if (Start == End) return;
- qsort(&*Start, End-Start, sizeof(*Start),
- get_array_pod_sort_comparator(*Start));
+ // Don't inefficiently call qsort with one element or trigger undefined
+ // behavior with an empty sequence.
+ auto NElts = End - Start;
+ if (NElts <= 1) return;
+ qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start));
}
template <class IteratorTy>
int (*Compare)(
const typename std::iterator_traits<IteratorTy>::value_type *,
const typename std::iterator_traits<IteratorTy>::value_type *)) {
- // Don't dereference start iterator of empty sequence.
- if (Start == End) return;
- qsort(&*Start, End - Start, sizeof(*Start),
+ // Don't inefficiently call qsort with one element or trigger undefined
+ // behavior with an empty sequence.
+ auto NElts = End - Start;
+ if (NElts <= 1) return;
+ qsort(&*Start, NElts, sizeof(*Start),
reinterpret_cast<int (*)(const void *, const void *)>(Compare));
}
C.clear();
}
+/// Provide wrappers to std::all_of which take ranges instead of having to pass
+/// begin/end explicitly.
+template<typename R, class UnaryPredicate>
+bool all_of(R &&Range, UnaryPredicate &&P) {
+ return std::all_of(Range.begin(), Range.end(),
+ std::forward<UnaryPredicate>(P));
+}
+
+/// Provide wrappers to std::any_of which take ranges instead of having to pass
+/// begin/end explicitly.
+template <typename R, class UnaryPredicate>
+bool any_of(R &&Range, UnaryPredicate &&P) {
+ return std::any_of(Range.begin(), Range.end(),
+ std::forward<UnaryPredicate>(P));
+}
+
+/// Provide wrappers to std::find which take ranges instead of having to pass
+/// begin/end explicitly.
+template<typename R, class T>
+auto find(R &&Range, const T &val) -> decltype(Range.begin()) {
+ return std::find(Range.begin(), Range.end(), val);
+}
+
//===----------------------------------------------------------------------===//
// 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
/// 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]());
-}
+make_unique(Args &&...) = delete;
-#endif
+struct FreeDeleter {
+ void operator()(void* v) {
+ ::free(v);
+ }
+};
template<typename First, typename Second>
struct pair_hash {
}
};
+/// A functor like C++14's std::less<void> in its absence.
+struct less {
+ template <typename A, typename B> bool operator()(A &&a, B &&b) const {
+ return std::forward<A>(a) < std::forward<B>(b);
+ }
+};
+
+/// A functor like C++14's std::equal<void> in its absence.
+struct equal {
+ template <typename A, typename B> bool operator()(A &&a, B &&b) const {
+ return std::forward<A>(a) == std::forward<B>(b);
+ }
+};
+
+/// Binary functor that adapts to any other binary functor after dereferencing
+/// operands.
+template <typename T> struct deref {
+ T func;
+ // Could be further improved to cope with non-derivable functors and
+ // non-binary functors (should be a variadic template member function
+ // operator()).
+ template <typename A, typename B>
+ auto operator()(A &lhs, B &rhs) const -> decltype(func(*lhs, *rhs)) {
+ assert(lhs);
+ assert(rhs);
+ return func(*lhs, *rhs);
+ }
+};
+
} // End llvm namespace
#endif
projects / oota-llvm.git / blobdiff