X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FSTLExtras.h;h=b10a4f11f85710c2335dcb211cd7f3d38ac54c1a;hb=02d62886678db69e8cc86baec381c5d86517fb25;hp=32cf4590e9939cf1170aa1ac9afac2d7a1aa081b;hpb=1ddcf35b68a4c326c548272134611ce54b1afd25;p=oota-llvm.git

diff --git a/include/llvm/ADT/STLExtras.h b/include/llvm/ADT/STLExtras.h
index 32cf4590e99..b10a4f11f85 100644
--- a/include/llvm/ADT/STLExtras.h
+++ b/include/llvm/ADT/STLExtras.h
@@ -17,10 +17,13 @@
 #ifndef LLVM_ADT_STLEXTRAS_H
 #define LLVM_ADT_STLEXTRAS_H
 
+#include "llvm/Support/Compiler.h"
+#include <cassert>
 #include <cstddef> // for std::size_t
 #include <cstdlib> // for qsort
 #include <functional>
 #include <iterator>
+#include <memory>
 #include <utility> // for std::pair
 
 namespace llvm {
@@ -29,6 +32,16 @@ namespace llvm {
 //     Extra additions to <functional>
 //===----------------------------------------------------------------------===//
 
+template<class Ty>
+struct identity : public std::unary_function<Ty, Ty> {
+  Ty &operator()(Ty &self) const {
+    return self;
+  }
+  const Ty &operator()(const Ty &self) const {
+    return self;
+  }
+};
+
 template<class Ty>
 struct less_ptr : public std::binary_function<Ty, Ty, bool> {
   bool operator()(const Ty* left, const Ty* right) const {
@@ -43,13 +56,153 @@ 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,
+               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)...);
+  }
+};
+
+#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,
+               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()() 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,
+               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()(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,
+               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()(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,
+               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()(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:
 //
 //   for_each(V.begin(), B.end(), deleter<Interval>);
 //
 template <class T>
-static inline void deleter(T *Ptr) {
+inline void deleter(T *Ptr) {
   delete Ptr;
 }
 
@@ -85,8 +238,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
@@ -131,119 +282,52 @@ 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
-
-namespace
-{
-  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;
-    }
-  };
-}
+/// \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 {
+  template <typename T> bool operator()(const T &lhs, const T &rhs) const {
+    return lhs.first < rhs.first;
+  }
+};
 
-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 second component of a std::pair
+/// compares less than the second component of another std::pair.
+struct less_second {
+  template <typename T> bool operator()(const T &lhs, const T &rhs) const {
+    return lhs.second < rhs.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 (&x)[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>
-static inline int array_pod_sort_comparator(const void *P1, const void *P2) {
-  if (*reinterpret_cast<const T*>(P1) < *reinterpret_cast<const T*>(P2))
+inline int array_pod_sort_comparator(const void *P1, const void *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;
 }
 
-/// get_array_pad_sort_comparator - This is an internal helper function used to
+/// get_array_pod_sort_comparator - This is an internal helper function used to
 /// get type deduction of T right.
 template<typename T>
-static int (*get_array_pad_sort_comparator(const T &X))
+inline int (*get_array_pod_sort_comparator(const T &))
              (const void*, const void*) {
   return array_pod_sort_comparator<T>;
 }
@@ -258,27 +342,252 @@ static int (*get_array_pad_sort_comparator(const T &X))
 /// 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
 /// default to std::less.
 template<class IteratorTy>
-static inline void array_pod_sort(IteratorTy Start, IteratorTy End) {
+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_pad_sort_comparator(*Start));
+        get_array_pod_sort_comparator(*Start));
 }
 
-template<class IteratorTy>
-static inline void array_pod_sort(IteratorTy Start, IteratorTy End,
-                                  int (*Compare)(const void*, const void*)) {
+template <class IteratorTy>
+inline void array_pod_sort(
+    IteratorTy Start, IteratorTy End,
+    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), Compare);
+  qsort(&*Start, End - Start, sizeof(*Start),
+        reinterpret_cast<int (*)(const void *, const void *)>(Compare));
+}
+
+//===----------------------------------------------------------------------===//
+//     Extra additions to <algorithm>
+//===----------------------------------------------------------------------===//
+
+/// For a container of pointers, deletes the pointers and then clears the
+/// container.
+template<typename Container>
+void DeleteContainerPointers(Container &C) {
+  for (typename Container::iterator I = C.begin(), E = C.end(); I != E; ++I)
+    delete *I;
+  C.clear();
+}
+
+/// In a container of pairs (usually a map) whose second element is a pointer,
+/// deletes the second elements and then clears the container.
+template<typename Container>
+void DeleteContainerSeconds(Container &C) {
+  for (typename Container::iterator I = C.begin(), E = C.end(); I != E; ++I)
+    delete I->second;
+  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
+
+struct FreeDeleter {
+  void operator()(void* v) {
+    ::free(v);
+  }
+};
+
+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);
+  }
+};
+
+/// 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