// 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 {
typedef mapped_iterator<RootIt, UnaryFunc> _Self;
inline const RootIt &getCurrent() const { return current; }
+ inline const UnaryFunc &getFunc() const { return Fn; }
inline explicit mapped_iterator(const RootIt &I, UnaryFunc F)
: current(I), Fn(F) {}
_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); }
+ _Self operator+ (difference_type n) const {
+ return _Self(current + n, Fn);
+ }
_Self& operator+= (difference_type n) { current += n; return *this; }
- _Self operator- (difference_type n) const { return _Self(current - n); }
+ _Self operator- (difference_type n) const {
+ return _Self(current - n, Fn);
+ }
_Self& operator-= (difference_type n) { current -= n; return *this; }
reference operator[](difference_type n) const { return *(*this + n); }
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);
+ return mapped_iterator<_Iterator, Func>(X.getCurrent() - N, X.getFunc());
}
template <typename ItTy>
inline ItTy next(ItTy it)
{
- std::advance(it, 1);
- return it;
+ return ++it;
}
template <typename ItTy, typename Dist>
template <typename ItTy>
inline ItTy prior(ItTy it)
{
- std::advance(it, -1);
- return it;
+ return --it;
}
//===----------------------------------------------------------------------===//
}
//===----------------------------------------------------------------------===//
-// Extra additions to arrays
+// Extra additions for arrays
//===----------------------------------------------------------------------===//
/// Find where an array ends (for ending iterators)
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