X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FSTLExtras.h;h=b68345a1dcf6ccd2e5e09b65a544a24192254612;hb=00552e3875ee5f382db6c98286a241a7d0efe1b8;hp=a8b613307da1f2d302c83fe39bea5866c16334f2;hpb=9806f833a6697b835f1c795a1bd2f26a84d49d3c;p=oota-llvm.git diff --git a/include/llvm/ADT/STLExtras.h b/include/llvm/ADT/STLExtras.h index a8b613307da..b68345a1dcf 100644 --- a/include/llvm/ADT/STLExtras.h +++ b/include/llvm/ADT/STLExtras.h @@ -17,9 +17,14 @@ #ifndef LLVM_ADT_STLEXTRAS_H #define LLVM_ADT_STLEXTRAS_H +#include "llvm/Support/Compiler.h" +#include // for std::all_of +#include #include // for std::size_t +#include // for qsort #include #include +#include #include // for std::pair namespace llvm { @@ -28,6 +33,16 @@ namespace llvm { // Extra additions to //===----------------------------------------------------------------------===// +template +struct identity : public std::unary_function { + Ty &operator()(Ty &self) const { + return self; + } + const Ty &operator()(const Ty &self) const { + return self; + } +}; + template struct less_ptr : public std::binary_function { bool operator()(const Ty* left, const Ty* right) const { @@ -42,13 +57,45 @@ struct greater_ptr : public std::binary_function { } }; +/// 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 class function_ref; + +template +class function_ref { + Ret (*callback)(intptr_t callable, Params ...params); + intptr_t callable; + + template + static Ret callback_fn(intptr_t callable, Params ...params) { + return (*reinterpret_cast(callable))( + std::forward(params)...); + } + +public: + template + function_ref(Callable &&callable, + typename std::enable_if< + !std::is_same::type, + function_ref>::value>::type * = nullptr) + : callback(callback_fn::type>), + callable(reinterpret_cast(&callable)) {} + Ret operator()(Params ...params) const { + return callback(callable, std::forward(params)...); + } +}; + // 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); // template -static inline void deleter(T *Ptr) { +inline void deleter(T *Ptr) { delete Ptr; } @@ -77,48 +124,67 @@ public: typedef void reference; // Can't modify value returned by fn typedef RootIt iterator_type; - typedef mapped_iterator _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) {} - 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 } - _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; + } + mapped_iterator operator--(int) { + mapped_iterator __tmp = *this; + --current; + return __tmp; + } + mapped_iterator operator+(difference_type n) const { + return mapped_iterator(current + n, Fn); } - _Self& operator+= (difference_type n) { current += n; return *this; } - _Self operator- (difference_type n) const { - return _Self(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 -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 +inline mapped_iterator +operator+(typename mapped_iterator::difference_type N, + const mapped_iterator &X) { + return mapped_iterator(X.getCurrent() - N, X.getFunc()); } @@ -130,119 +196,74 @@ inline mapped_iterator map_iterator(const ItTy &I, FuncTy F) { return mapped_iterator(I, F); } +//===----------------------------------------------------------------------===// +// Extra additions to +//===----------------------------------------------------------------------===// + +/// \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 bool operator()(const T &lhs, const T &rhs) const { + return lhs.first < rhs.first; + } +}; -// 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 -inline ItTy next(ItTy it, Dist n) -{ - std::advance(it, n); - return it; -} +/// \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 bool operator()(const T &lhs, const T &rhs) const { + return lhs.second < rhs.second; + } +}; -template -inline ItTy next(ItTy it) -{ - return ++it; -} +// A subset of N3658. More stuff can be added as-needed. -template -inline ItTy prior(ItTy it, Dist n) -{ - std::advance(it, -n); - return it; -} +/// \brief Represents a compile-time sequence of integers. +template struct integer_sequence { + typedef T value_type; -template -inline ItTy prior(ItTy it) -{ - return --it; -} + static LLVM_CONSTEXPR size_t size() { return sizeof...(I); } +}; -//===----------------------------------------------------------------------===// -// Extra additions to -//===----------------------------------------------------------------------===// +/// \brief Alias for the common case of a sequence of size_ts. +template +struct index_sequence : integer_sequence {}; -// 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 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 - 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& p) { - first = p.first; - second = p.second; - return *this; - } - }; -} +template +struct build_index_impl : build_index_impl {}; +template +struct build_index_impl<0, I...> : index_sequence {}; -template -inline tier tie(T1& f, T2& s) { - return tier(f, s); -} +/// \brief Creates a compile-time integer sequence for a parameter pack. +template +struct index_sequence_for : build_index_impl {}; //===----------------------------------------------------------------------===// // 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 -inline T *array_endof(T (&x)[N]) { - return x+N; -} - /// Find the length of an array. -template -inline size_t array_lengthof(T (&x)[N]) { +template +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 for array_pod_sort. template -static inline int array_pod_sort_comparator(const void *P1, const void *P2) { - if (*reinterpret_cast(P1) < *reinterpret_cast(P2)) +inline int array_pod_sort_comparator(const void *P1, const void *P2) { + if (std::less()(*reinterpret_cast(P1), + *reinterpret_cast(P2))) return -1; - if (*reinterpret_cast(P2) < *reinterpret_cast(P1)) + if (std::less()(*reinterpret_cast(P2), + *reinterpret_cast(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 -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; } @@ -257,27 +278,145 @@ 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 -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)); +inline void array_pod_sort(IteratorTy Start, IteratorTy End) { + // 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 -static inline void array_pod_sort(IteratorTy Start, IteratorTy End, - int (*Compare)(const void*, const void*)) { - // Don't dereference start iterator of empty sequence. - if (Start == End) return; - qsort(&*Start, End-Start, sizeof(*Start), Compare); +template +inline void array_pod_sort( + IteratorTy Start, IteratorTy End, + int (*Compare)( + const typename std::iterator_traits::value_type *, + const typename std::iterator_traits::value_type *)) { + // 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(Compare)); +} + +//===----------------------------------------------------------------------===// +// Extra additions to +//===----------------------------------------------------------------------===// + +/// For a container of pointers, deletes the pointers and then clears the +/// container. +template +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 +void DeleteContainerSeconds(Container &C) { + for (typename Container::iterator I = C.begin(), E = C.end(); I != E; ++I) + delete I->second; + C.clear(); +} + +/// Provide wrappers to std::all_of which take ranges instead of having to pass +/// being/end explicitly. +template +bool all_of(R &&Range, UnaryPredicate &&P) { + return std::all_of(Range.begin(), Range.end(), + std::forward(P)); +} + +//===----------------------------------------------------------------------===// +// Extra additions to +//===----------------------------------------------------------------------===// + +// Implement make_unique according to N3656. + +/// \brief Constructs a `new T()` with the given args and returns a +/// `unique_ptr` which owns the object. +/// +/// Example: +/// +/// auto p = make_unique(); +/// auto p = make_unique>(0, 1); +template +typename std::enable_if::value, std::unique_ptr>::type +make_unique(Args &&... args) { + return std::unique_ptr(new T(std::forward(args)...)); +} + +/// \brief Constructs a `new T[n]` with the given args and returns a +/// `unique_ptr` which owns the object. +/// +/// \param n size of the new array. +/// +/// Example: +/// +/// auto p = make_unique(2); // value-initializes the array with 0's. +template +typename std::enable_if::value && std::extent::value == 0, + std::unique_ptr>::type +make_unique(size_t n) { + return std::unique_ptr(new typename std::remove_extent::type[n]()); } - + +/// This function isn't used and is only here to provide better compile errors. +template +typename std::enable_if::value != 0>::type +make_unique(Args &&...) = delete; + +struct FreeDeleter { + void operator()(void* v) { + ::free(v); + } +}; + +template +struct pair_hash { + size_t operator()(const std::pair &P) const { + return std::hash()(P.first) * 31 + std::hash()(P.second); + } +}; + +/// A functor like C++14's std::less in its absence. +struct less { + template bool operator()(A &&a, B &&b) const { + return std::forward(a) < std::forward(b); + } +}; + +/// A functor like C++14's std::equal in its absence. +struct equal { + template bool operator()(A &&a, B &&b) const { + return std::forward(a) == std::forward(b); + } +}; + +/// Binary functor that adapts to any other binary functor after dereferencing +/// operands. +template 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 + auto operator()(A &lhs, B &rhs) const -> decltype(func(*lhs, *rhs)) { + assert(lhs); + assert(rhs); + return func(*lhs, *rhs); + } +}; + } // End llvm namespace #endif