LLVM API Documentation

STLExtras.h

Go to the documentation of this file.
00001 //===- llvm/ADT/STLExtras.h - Useful STL related functions ------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file contains some templates that are useful if you are working with the
00011 // STL at all.
00012 //
00013 // No library is required when using these functions.
00014 //
00015 //===----------------------------------------------------------------------===//
00016 
00017 #ifndef LLVM_ADT_STLEXTRAS_H
00018 #define LLVM_ADT_STLEXTRAS_H
00019 
00020 #include <cstddef> // for std::size_t
00021 #include <functional>
00022 #include <utility> // for std::pair
00023 #include "llvm/ADT/iterator.h"
00024 
00025 namespace llvm {
00026 
00027 //===----------------------------------------------------------------------===//
00028 //     Extra additions to <functional>
00029 //===----------------------------------------------------------------------===//
00030 
00031 template<class Ty>
00032 struct less_ptr : public std::binary_function<Ty, Ty, bool> {
00033   bool operator()(const Ty* left, const Ty* right) const {
00034     return *left < *right;
00035   }
00036 };
00037 
00038 template<class Ty>
00039 struct greater_ptr : public std::binary_function<Ty, Ty, bool> {
00040   bool operator()(const Ty* left, const Ty* right) const {
00041     return *right < *left;
00042   }
00043 };
00044 
00045 // deleter - Very very very simple method that is used to invoke operator
00046 // delete on something.  It is used like this:
00047 //
00048 //   for_each(V.begin(), B.end(), deleter<Interval>);
00049 //
00050 template <class T>
00051 static inline void deleter(T *Ptr) {
00052   delete Ptr;
00053 }
00054 
00055 
00056 
00057 //===----------------------------------------------------------------------===//
00058 //     Extra additions to <iterator>
00059 //===----------------------------------------------------------------------===//
00060 
00061 // mapped_iterator - This is a simple iterator adapter that causes a function to
00062 // be dereferenced whenever operator* is invoked on the iterator.
00063 //
00064 template <class RootIt, class UnaryFunc>
00065 class mapped_iterator {
00066   RootIt current;
00067   UnaryFunc Fn;
00068 public:
00069   typedef typename std::iterator_traits<RootIt>::iterator_category
00070           iterator_category;
00071   typedef typename std::iterator_traits<RootIt>::difference_type
00072           difference_type;
00073   typedef typename UnaryFunc::result_type value_type;
00074 
00075   typedef void pointer;
00076   //typedef typename UnaryFunc::result_type *pointer;
00077   typedef void reference;        // Can't modify value returned by fn
00078 
00079   typedef RootIt iterator_type;
00080   typedef mapped_iterator<RootIt, UnaryFunc> _Self;
00081 
00082   inline const RootIt &getCurrent() const { return current; }
00083   inline const UnaryFunc &getFunc() const { return Fn; }
00084 
00085   inline explicit mapped_iterator(const RootIt &I, UnaryFunc F)
00086     : current(I), Fn(F) {}
00087   inline mapped_iterator(const mapped_iterator &It)
00088     : current(It.current), Fn(It.Fn) {}
00089 
00090   inline value_type operator*() const {   // All this work to do this
00091     return Fn(*current);         // little change
00092   }
00093 
00094   _Self& operator++() { ++current; return *this; }
00095   _Self& operator--() { --current; return *this; }
00096   _Self  operator++(int) { _Self __tmp = *this; ++current; return __tmp; }
00097   _Self  operator--(int) { _Self __tmp = *this; --current; return __tmp; }
00098   _Self  operator+    (difference_type n) const {
00099     return _Self(current + n, Fn);
00100   }
00101   _Self& operator+=   (difference_type n) { current += n; return *this; }
00102   _Self  operator-    (difference_type n) const {
00103     return _Self(current - n, Fn);
00104   }
00105   _Self& operator-=   (difference_type n) { current -= n; return *this; }
00106   reference operator[](difference_type n) const { return *(*this + n); }
00107 
00108   inline bool operator!=(const _Self &X) const { return !operator==(X); }
00109   inline bool operator==(const _Self &X) const { return current == X.current; }
00110   inline bool operator< (const _Self &X) const { return current <  X.current; }
00111 
00112   inline difference_type operator-(const _Self &X) const {
00113     return current - X.current;
00114   }
00115 };
00116 
00117 template <class _Iterator, class Func>
00118 inline mapped_iterator<_Iterator, Func>
00119 operator+(typename mapped_iterator<_Iterator, Func>::difference_type N,
00120           const mapped_iterator<_Iterator, Func>& X) {
00121   return mapped_iterator<_Iterator, Func>(X.getCurrent() - N, X.getFunc());
00122 }
00123 
00124 
00125 // map_iterator - Provide a convenient way to create mapped_iterators, just like
00126 // make_pair is useful for creating pairs...
00127 //
00128 template <class ItTy, class FuncTy>
00129 inline mapped_iterator<ItTy, FuncTy> map_iterator(const ItTy &I, FuncTy F) {
00130   return mapped_iterator<ItTy, FuncTy>(I, F);
00131 }
00132 
00133 
00134 // next/prior - These functions unlike std::advance do not modify the
00135 // passed iterator but return a copy.
00136 //
00137 // next(myIt) returns copy of myIt incremented once
00138 // next(myIt, n) returns copy of myIt incremented n times
00139 // prior(myIt) returns copy of myIt decremented once
00140 // prior(myIt, n) returns copy of myIt decremented n times
00141 
00142 template <typename ItTy, typename Dist>
00143 inline ItTy next(ItTy it, Dist n)
00144 {
00145   std::advance(it, n);
00146   return it;
00147 }
00148 
00149 template <typename ItTy>
00150 inline ItTy next(ItTy it)
00151 {
00152   return ++it;
00153 }
00154 
00155 template <typename ItTy, typename Dist>
00156 inline ItTy prior(ItTy it, Dist n)
00157 {
00158   std::advance(it, -n);
00159   return it;
00160 }
00161 
00162 template <typename ItTy>
00163 inline ItTy prior(ItTy it)
00164 {
00165   return --it;
00166 }
00167 
00168 //===----------------------------------------------------------------------===//
00169 //     Extra additions to <utility>
00170 //===----------------------------------------------------------------------===//
00171 
00172 // tie - this function ties two objects and returns a temporary object
00173 // that is assignable from a std::pair. This can be used to make code
00174 // more readable when using values returned from functions bundled in
00175 // a std::pair. Since an example is worth 1000 words:
00176 //
00177 // typedef std::map<int, int> Int2IntMap;
00178 //
00179 // Int2IntMap myMap;
00180 // Int2IntMap::iterator where;
00181 // bool inserted;
00182 // tie(where, inserted) = myMap.insert(std::make_pair(123,456));
00183 //
00184 // if (inserted)
00185 //   // do stuff
00186 // else
00187 //   // do other stuff
00188 
00189 namespace
00190 {
00191   template <typename T1, typename T2>
00192   struct tier {
00193     typedef T1 &first_type;
00194     typedef T2 &second_type;
00195 
00196     first_type first;
00197     second_type second;
00198 
00199     tier(first_type f, second_type s) : first(f), second(s) { }
00200     tier& operator=(const std::pair<T1, T2>& p) {
00201       first = p.first;
00202       second = p.second;
00203       return *this;
00204     }
00205   };
00206 }
00207 
00208 template <typename T1, typename T2>
00209 inline tier<T1, T2> tie(T1& f, T2& s) {
00210   return tier<T1, T2>(f, s);
00211 }
00212 
00213 //===----------------------------------------------------------------------===//
00214 //     Extra additions for arrays
00215 //===----------------------------------------------------------------------===//
00216 
00217 /// Find where an array ends (for ending iterators)
00218 /// This returns a pointer to the byte immediately
00219 /// after the end of an array.
00220 template<class T, std::size_t N>
00221 inline T *array_endof(T (&x)[N]) {
00222   return x+N;
00223 }
00224 
00225 /// Find the length of an array.
00226 template<class T, std::size_t N>
00227 inline size_t array_lengthof(T (&x)[N]) {
00228   return N;
00229 }
00230 
00231 /// array_pod_sort_comparator - This is helper function for array_pod_sort,
00232 /// which just uses operator< on T.
00233 template<typename T>
00234 static inline int array_pod_sort_comparator(const void *P1, const void *P2) {
00235   if (*reinterpret_cast<const T*>(P1) < *reinterpret_cast<const T*>(P2))
00236     return -1;
00237   if (*reinterpret_cast<const T*>(P2) < *reinterpret_cast<const T*>(P1))
00238     return 1;
00239   return 0;
00240 }
00241 
00242 /// get_array_pad_sort_comparator - This is an internal helper function used to
00243 /// get type deduction of T right.
00244 template<typename T>
00245 static int (*get_array_pad_sort_comparator(const T &X))
00246              (const void*, const void*) {
00247   return array_pod_sort_comparator<T>;
00248 }
00249 
00250 
00251 /// array_pod_sort - This sorts an array with the specified start and end
00252 /// extent.  This is just like std::sort, except that it calls qsort instead of
00253 /// using an inlined template.  qsort is slightly slower than std::sort, but
00254 /// most sorts are not performance critical in LLVM and std::sort has to be
00255 /// template instantiated for each type, leading to significant measured code
00256 /// bloat.  This function should generally be used instead of std::sort where
00257 /// possible.
00258 ///
00259 /// This function assumes that you have simple POD-like types that can be
00260 /// compared with operator< and can be moved with memcpy.  If this isn't true,
00261 /// you should use std::sort.
00262 ///
00263 /// NOTE: If qsort_r were portable, we could allow a custom comparator and
00264 /// default to std::less.
00265 template<class IteratorTy>
00266 static inline void array_pod_sort(IteratorTy Start, IteratorTy End) {
00267   // Don't dereference start iterator of empty sequence.
00268   if (Start == End) return;
00269   qsort(&*Start, End-Start, sizeof(*Start),
00270         get_array_pad_sort_comparator(*Start));
00271 }
00272 
00273 } // End llvm namespace
00274 
00275 #endif