X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FSTLExtras.h;h=aee500d4fb6c92abe8fc2250735a75a78bf08a8a;hb=94c22716d60ff5edf6a98a3c67e0faa001be1142;hp=f1883959d762c351250bfc6388ac772a409bfdf2;hpb=43d1fd449f1a0ac9d9dafa0b9569bb6b2e976198;p=oota-llvm.git diff --git a/include/llvm/ADT/STLExtras.h b/include/llvm/ADT/STLExtras.h index f1883959d76..aee500d4fb6 100644 --- a/include/llvm/ADT/STLExtras.h +++ b/include/llvm/ADT/STLExtras.h @@ -10,17 +10,18 @@ // 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 // for std::size_t +#include // for qsort #include +#include #include // for std::pair -#include // for std::size_t -#include "llvm/ADT/iterator.h" namespace llvm { @@ -28,6 +29,23 @@ 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 { + return *left < *right; + } +}; + template struct greater_ptr : public std::binary_function { bool operator()(const Ty* left, const Ty* right) const { @@ -41,7 +59,7 @@ struct greater_ptr : public std::binary_function { // for_each(V.begin(), B.end(), deleter); // template -static inline void deleter(T *Ptr) { +inline void deleter(T *Ptr) { delete Ptr; } @@ -73,6 +91,7 @@ public: 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) {} @@ -87,9 +106,13 @@ public: _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); } @@ -106,7 +129,7 @@ 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); + return mapped_iterator<_Iterator, Func>(X.getCurrent() - N, X.getFunc()); } @@ -137,8 +160,7 @@ inline ItTy next(ItTy it, Dist n) template inline ItTy next(ItTy it) { - std::advance(it, 1); - return it; + return ++it; } template @@ -151,8 +173,7 @@ inline ItTy prior(ItTy it, Dist n) template inline ItTy prior(ItTy it) { - std::advance(it, -1); - return it; + return --it; } //===----------------------------------------------------------------------===// @@ -175,25 +196,21 @@ inline ItTy prior(ItTy it) // // 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 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 inline tier tie(T1& f, T2& s) { @@ -201,7 +218,7 @@ inline tier tie(T1& f, T2& s) { } //===----------------------------------------------------------------------===// -// Extra additions to arrays +// Extra additions for arrays //===----------------------------------------------------------------------===// /// Find where an array ends (for ending iterators) @@ -214,10 +231,82 @@ inline T *array_endof(T (&x)[N]) { /// Find the length of an array. template -inline size_t array_lengthof(T (&x)[N]) { +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. +template +inline int array_pod_sort_comparator(const void *P1, const void *P2) { + if (*reinterpret_cast(P1) < *reinterpret_cast(P2)) + return -1; + if (*reinterpret_cast(P2) < *reinterpret_cast(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 +inline int (*get_array_pad_sort_comparator(const T &)) + (const void*, const void*) { + return array_pod_sort_comparator; +} + + +/// 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 +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)); +} + +template +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); +} + +//===----------------------------------------------------------------------===// +// 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(); +} + } // End llvm namespace #endif