X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FSTLExtras.h;h=3aa81833532156290fb545aa01c72797a09973c2;hb=65c98b9da474d0562f883d6001f31ba5b2b95183;hp=5ebceb346a082482d70598b49a270ce45bca1d58;hpb=9bb2188b0e196d2724e128152ef4d4b581adf3bc;p=oota-llvm.git diff --git a/include/llvm/ADT/STLExtras.h b/include/llvm/ADT/STLExtras.h index 5ebceb346a0..3aa81833532 100644 --- a/include/llvm/ADT/STLExtras.h +++ b/include/llvm/ADT/STLExtras.h @@ -1,25 +1,27 @@ -//===- STLExtras.h - Useful functions when working with the STL -*- C++ -*-===// -// +//===- llvm/ADT/STLExtras.h - Useful STL related functions ------*- C++ -*-===// +// // The LLVM Compiler Infrastructure // -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. -// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// //===----------------------------------------------------------------------===// // // 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 SUPPORT_STLEXTRAS_H -#define SUPPORT_STLEXTRAS_H +#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 "Support/iterator" namespace llvm { @@ -27,41 +29,38 @@ namespace llvm { // Extra additions to //===----------------------------------------------------------------------===// -// bind_obj - Often times you want to apply the member function of an object -// as a unary functor. This macro is shorthand that makes it happen less -// verbosely. -// -// Example: -// struct Summer { void accumulate(int x); } -// vector Numbers; -// Summer MyS; -// for_each(Numbers.begin(), Numbers.end(), -// bind_obj(&MyS, &Summer::accumulate)); -// -// TODO: When I get lots of extra time, convert this from an evil macro -// -#define bind_obj(OBJ, METHOD) std::bind1st(std::mem_fun(METHOD), OBJ) - +template +struct identity : public std::unary_function { + Ty &operator()(Ty &self) const { + return self; + } + const Ty &operator()(const Ty &self) const { + return self; + } +}; -// bitwise_or - This is a simple functor that applys operator| on its two -// arguments to get a boolean result. -// template -struct bitwise_or : public std::binary_function { - bool operator()(const Ty& left, const Ty& right) const { - return left | right; +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 { + return *right < *left; + } +}; // deleter - Very very very simple method that is used to invoke operator -// delete on something. It is used like this: +// delete on something. It is used like this: // // for_each(V.begin(), B.end(), deleter); // -template -static inline void deleter(T *Ptr) { - delete Ptr; +template +inline void deleter(T *Ptr) { + delete Ptr; } @@ -73,9 +72,6 @@ static inline void deleter(T *Ptr) { // mapped_iterator - This is a simple iterator adapter that causes a function to // be dereferenced whenever operator* is invoked on the iterator. // -// It turns out that this is disturbingly similar to boost::transform_iterator -// -#if 1 template class mapped_iterator { RootIt current; @@ -94,14 +90,15 @@ public: typedef RootIt iterator_type; typedef mapped_iterator _Self; - inline RootIt &getCurrent() const { return current; } + 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 + inline value_type operator*() const { // All this work to do this return Fn(*current); // little change } @@ -109,11 +106,15 @@ 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); } + 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; } @@ -125,34 +126,12 @@ public: }; template -inline mapped_iterator<_Iterator, Func> +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()); } -#else - -// This fails to work, because some iterators are not classes, for example -// vector iterators are commonly value_type **'s -template -class mapped_iterator : public RootIt { - UnaryFunc Fn; -public: - typedef typename UnaryFunc::result_type value_type; - typedef typename UnaryFunc::result_type *pointer; - typedef void reference; // Can't modify value returned by fn - - typedef mapped_iterator _Self; - typedef RootIt super; - inline explicit mapped_iterator(const RootIt &I) : super(I) {} - inline mapped_iterator(const super &It) : super(It) {} - - inline value_type operator*() const { // All this work to do - return Fn(super::operator*()); // this little thing - } -}; -#endif // map_iterator - Provide a convenient way to create mapped_iterators, just like // make_pair is useful for creating pairs... @@ -163,78 +142,40 @@ inline mapped_iterator map_iterator(const ItTy &I, FuncTy F) { } -//===----------------------------------------------------------------------===// -// Extra additions to -//===----------------------------------------------------------------------===// - -// apply_until - Apply a functor to a sequence continually, unless the -// functor returns true. Return true if the functor returned true, return false -// if the functor never returned true. -// -template -bool apply_until(InputIt First, InputIt Last, Function Func) { - for ( ; First != Last; ++First) - if (Func(*First)) return true; - return false; -} - - -// reduce - Reduce a sequence values into a single value, given an initial -// value and an operator. +// next/prior - These functions unlike std::advance do not modify the +// passed iterator but return a copy. // -template -ValueType reduce(InputIt First, InputIt Last, Function Func, ValueType Value) { - for ( ; First != Last; ++First) - Value = Func(*First, Value); - return Value; -} - -#if 1 // This is likely to be more efficient +// 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 -// reduce_apply - Reduce the result of applying a function to each value in a -// sequence, given an initial value, an operator, a function, and a sequence. -// -template -inline ValueType reduce_apply(InputIt First, InputIt Last, Function Func, - ValueType Value, TransFunc XForm) { - for ( ; First != Last; ++First) - Value = Func(XForm(*First), Value); - return Value; +template +inline ItTy next(ItTy it, Dist n) +{ + std::advance(it, n); + return it; } -#else // This is arguably more elegant - -// reduce_apply - Reduce the result of applying a function to each value in a -// sequence, given an initial value, an operator, a function, and a sequence. -// -template -inline ValueType reduce_apply2(InputIt First, InputIt Last, Function Func, - ValueType Value, TransFunc XForm) { - return reduce(map_iterator(First, XForm), map_iterator(Last, XForm), - Func, Value); +template +inline ItTy next(ItTy it) +{ + return ++it; } -#endif - -// reduce_apply_bool - Reduce the result of applying a (bool returning) function -// to each value in a sequence. All of the bools returned by the mapped -// function are bitwise or'd together, and the result is returned. -// -template -inline bool reduce_apply_bool(InputIt First, InputIt Last, Function Func) { - return reduce_apply(First, Last, bitwise_or(), false, Func); +template +inline ItTy prior(ItTy it, Dist n) +{ + std::advance(it, -n); + return it; } - -// map - This function maps the specified input sequence into the specified -// output iterator, applying a unary function in between. -// -template -inline OutIt mapto(InIt Begin, InIt End, OutIt Dest, Functor F) { - return copy(map_iterator(Begin, F), map_iterator(End, F), Dest); +template +inline ItTy prior(ItTy it) +{ + return --it; } - //===----------------------------------------------------------------------===// // Extra additions to //===----------------------------------------------------------------------===// @@ -245,7 +186,7 @@ inline OutIt mapto(InIt Begin, InIt End, OutIt Dest, Functor F) { // a std::pair. Since an example is worth 1000 words: // // typedef std::map Int2IntMap; -// +// // Int2IntMap myMap; // Int2IntMap::iterator where; // bool inserted; @@ -255,31 +196,137 @@ inline OutIt mapto(InIt Begin, InIt End, OutIt Dest, Functor F) { // // 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) { return tier(f, s); } +/// \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; + } +}; + +/// \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; + } +}; + +//===----------------------------------------------------------------------===// +// 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 (&)[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_pod_sort_comparator - This is an internal helper function used to +/// get type deduction of T right. +template +inline int (*get_array_pod_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_pod_sort_comparator(*Start)); +} + +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 dereference start iterator of empty sequence. + if (Start == End) return; + qsort(&*Start, End - Start, 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(); +} + } // End llvm namespace #endif