Fixed lint errors:

[oota-llvm.git] / include / llvm / ADT / STLExtras.h

diff --git a/include/llvm/ADT/STLExtras.h b/include/llvm/ADT/STLExtras.h
index e009939cec190726e5808f431ed7cadefd59295c..964e7e07ef7d57a67ef37ef61cb4599c44bc5063 100644 (file)
--- a/include/llvm/ADT/STLExtras.h
+++ b/include/llvm/ADT/STLExtras.h
@@ -10,16 +10,16 @@
 // This file contains some templates that are useful if you are working with the
 // STL at all.
 //
-// No library is required when using these functinons.
+// No library is required when using these functions.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_STLEXTRAS_H
 #define LLVM_ADT_STLEXTRAS_H
 
+#include <cstddef> // for std::size_t
 #include <functional>
 #include <utility> // for std::pair
-#include <cstring> // for std::size_t
 #include "llvm/ADT/iterator.h"
 
 namespace llvm {
@@ -204,7 +204,7 @@ inline tier<T1, T2> tie(T1& f, T2& s) {
 }
 
 //===----------------------------------------------------------------------===//
-//     Extra additions to arrays
+//     Extra additions for arrays
 //===----------------------------------------------------------------------===//
 
 /// Find where an array ends (for ending iterators)
@@ -221,6 +221,48 @@ inline size_t array_lengthof(T (&x)[N]) {
   return N;
 }
 
+/// array_pod_sort_comparator - This is helper function for array_pod_sort,
+/// which just uses operator< on T.
+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))
+    return -1;
+  if (*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 type deduction of T right.
+template<typename T>
+static int (*get_array_pad_sort_comparator(const T &X))
+             (const void*, const void*) {
+  return array_pod_sort_comparator<T>;
+}
+
+
+/// array_pod_sort - This sorts an array with the specified start and end
+/// extent.  This is just like std::sort, except that it calls qsort instead of
+/// using an inlined template.  qsort is slightly slower than std::sort, but
+/// most sorts are not performance critical in LLVM and std::sort has to be
+/// template instantiated for each type, leading to significant measured code
+/// bloat.  This function should generally be used instead of std::sort where
+/// 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,
+/// 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) {
+  // Don't dereference start iterator of empty sequence.
+  if (Start == End) return;
+  qsort(&*Start, End-Start, sizeof(*Start),
+        get_array_pad_sort_comparator(*Start));
+}
+
 } // End llvm namespace
 
 #endif