X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FSTLExtras.h;h=b68345a1dcf6ccd2e5e09b65a544a24192254612;hb=00552e3875ee5f382db6c98286a241a7d0efe1b8;hp=7c2a147bc885dcc5f57a1d0bab6d9da350ef4881;hpb=e45bc94232040786131bf0aee9eaed0cc44bb534;p=oota-llvm.git

diff --git a/include/llvm/ADT/STLExtras.h b/include/llvm/ADT/STLExtras.h
index 7c2a147bc88..b68345a1dcf 100644
--- a/include/llvm/ADT/STLExtras.h
+++ b/include/llvm/ADT/STLExtras.h
@@ -18,6 +18,8 @@
 #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>
@@ -55,6 +57,38 @@ 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;
+
+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,
+               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<intptr_t>(&callable)) {}
+  Ret operator()(Params ...params) const {
+    return callback(callable, std::forward<Params>(params)...);
+  }
+};
+
 // deleter - Very very very simple method that is used to invoke operator
 // delete on something.  It is used like this:
 //
@@ -90,7 +124,6 @@ public:
   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; }
@@ -102,34 +135,56 @@ public:
     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());
 }
 
 
@@ -161,6 +216,28 @@ struct less_second {
   }
 };
 
+// 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
 //===----------------------------------------------------------------------===//
@@ -208,10 +285,11 @@ inline int (*get_array_pod_sort_comparator(const T &))
 /// 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>
@@ -220,9 +298,11 @@ inline void array_pod_sort(
     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));
 }
 
@@ -248,12 +328,18 @@ void DeleteContainerSeconds(Container &C) {
   C.clear();
 }
 
+/// Provide wrappers to std::all_of which take ranges instead of having to pass
+/// being/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));
+}
+
 //===----------------------------------------------------------------------===//
 //     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
@@ -287,123 +373,49 @@ make_unique(size_t 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)));
-}
+make_unique(Args &&...) = delete;
 
-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)));
-}
+struct FreeDeleter {
+  void operator()(void* v) {
+    ::free(v);
+  }
+};
 
-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<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);
+  }
+};
 
-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)));
-}
+/// 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);
+  }
+};
 
-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]());
-}
+/// 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);
+  }
+};
 
-#endif
+/// 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