X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FSTLExtras.h;h=0605e522d7e775a11e186fcb22056e9ca0fa1f8b;hb=a53ce4e0be51725468c589b1d0a070b30fffacde;hp=5b7b88b90085270c74e1c9a455175a3b3d024d7a;hpb=99ccb1fae75d3d7296c11f1ec4a6eb5e1cbbe4d4;p=oota-llvm.git

diff --git a/include/llvm/ADT/STLExtras.h b/include/llvm/ADT/STLExtras.h
index 5b7b88b9008..0605e522d7e 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>
@@ -63,123 +65,30 @@ struct greater_ptr : public std::binary_function<Ty, Ty, bool> {
 /// 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:
 //
@@ -215,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; }
@@ -227,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;
   }
-  _Self& operator+=   (difference_type n) { current += n; return *this; }
-  _Self  operator-    (difference_type n) const {
-    return _Self(current - n, Fn);
+  mapped_iterator &operator--() {
+    --current;
+    return *this;
+  }
+  mapped_iterator operator++(int) {
+    mapped_iterator __tmp = *this;
+    ++current;
+    return __tmp;
+  }
+  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());
 }
 
 
@@ -266,6 +196,30 @@ inline mapped_iterator<ItTy, FuncTy> map_iterator(const ItTy &I, FuncTy F) {
   return mapped_iterator<ItTy, FuncTy>(I, F);
 }
 
+// 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)->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)
+  ->decltype(make_range(make_reverse_iterator(std::end(C)),
+                        make_reverse_iterator(std::begin(C)))) {
+  return make_range(make_reverse_iterator(std::end(C)),
+                    make_reverse_iterator(std::begin(C)));
+}
+
 //===----------------------------------------------------------------------===//
 //     Extra additions to <utility>
 //===----------------------------------------------------------------------===//
@@ -286,6 +240,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
 //===----------------------------------------------------------------------===//
@@ -333,10 +309,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>
@@ -345,9 +322,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));
 }
 
@@ -373,12 +352,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
@@ -412,123 +397,13 @@ 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)));
-}
+make_unique(Args &&...) = delete;
 
-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
+struct FreeDeleter {
+  void operator()(void* v) {
+    ::free(v);
+  }
+};
 
 template<typename First, typename Second>
 struct pair_hash {
@@ -537,6 +412,35 @@ 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