include/llvm/ADT/STLExtras.h

   1 //===- llvm/ADT/STLExtras.h - Useful STL related functions ------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file contains some templates that are useful if you are working with the
  11 // STL at all.
  12 //
  13 // No library is required when using these functions.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #ifndef LLVM_ADT_STLEXTRAS_H
  18 #define LLVM_ADT_STLEXTRAS_H
  19
  20 #include "llvm/Support/Compiler.h"
  21 #include <cstddef> // for std::size_t
  22 #include <cstdlib> // for qsort
  23 #include <functional>
  24 #include <iterator>
  25 #include <memory>
  26 #include <utility> // for std::pair
  27
  28 namespace llvm {
  29
  30 //===----------------------------------------------------------------------===//
  31 //     Extra additions to <functional>
  32 //===----------------------------------------------------------------------===//
  33
  34 template<class Ty>
  35 struct identity : public std::unary_function<Ty, Ty> {
  36   Ty &operator()(Ty &self) const {
  37     return self;
  38   }
  39   const Ty &operator()(const Ty &self) const {
  40     return self;
  41   }
  42 };
  43
  44 template<class Ty>
  45 struct less_ptr : public std::binary_function<Ty, Ty, bool> {
  46   bool operator()(const Ty* left, const Ty* right) const {
  47     return *left < *right;
  48   }
  49 };
  50
  51 template<class Ty>
  52 struct greater_ptr : public std::binary_function<Ty, Ty, bool> {
  53   bool operator()(const Ty* left, const Ty* right) const {
  54     return *right < *left;
  55   }
  56 };
  57
  58 // deleter - Very very very simple method that is used to invoke operator
  59 // delete on something.  It is used like this:
  60 //
  61 //   for_each(V.begin(), B.end(), deleter<Interval>);
  62 //
  63 template <class T>
  64 inline void deleter(T *Ptr) {
  65   delete Ptr;
  66 }
  67
  68
  69
  70 //===----------------------------------------------------------------------===//
  71 //     Extra additions to <iterator>
  72 //===----------------------------------------------------------------------===//
  73
  74 // mapped_iterator - This is a simple iterator adapter that causes a function to
  75 // be dereferenced whenever operator* is invoked on the iterator.
  76 //
  77 template <class RootIt, class UnaryFunc>
  78 class mapped_iterator {
  79   RootIt current;
  80   UnaryFunc Fn;
  81 public:
  82   typedef typename std::iterator_traits<RootIt>::iterator_category
  83           iterator_category;
  84   typedef typename std::iterator_traits<RootIt>::difference_type
  85           difference_type;
  86   typedef typename UnaryFunc::result_type value_type;
  87
  88   typedef void pointer;
  89   //typedef typename UnaryFunc::result_type *pointer;
  90   typedef void reference;        // Can't modify value returned by fn
  91
  92   typedef RootIt iterator_type;
  93   typedef mapped_iterator<RootIt, UnaryFunc> _Self;
  94
  95   inline const RootIt &getCurrent() const { return current; }
  96   inline const UnaryFunc &getFunc() const { return Fn; }
  97
  98   inline explicit mapped_iterator(const RootIt &I, UnaryFunc F)
  99     : current(I), Fn(F) {}
 100
 101   inline value_type operator*() const {   // All this work to do this
 102     return Fn(*current);         // little change
 103   }
 104
 105   _Self& operator++() { ++current; return *this; }
 106   _Self& operator--() { --current; return *this; }
 107   _Self  operator++(int) { _Self __tmp = *this; ++current; return __tmp; }
 108   _Self  operator--(int) { _Self __tmp = *this; --current; return __tmp; }
 109   _Self  operator+    (difference_type n) const {
 110     return _Self(current + n, Fn);
 111   }
 112   _Self& operator+=   (difference_type n) { current += n; return *this; }
 113   _Self  operator-    (difference_type n) const {
 114     return _Self(current - n, Fn);
 115   }
 116   _Self& operator-=   (difference_type n) { current -= n; return *this; }
 117   reference operator[](difference_type n) const { return *(*this + n); }
 118
 119   inline bool operator!=(const _Self &X) const { return !operator==(X); }
 120   inline bool operator==(const _Self &X) const { return current == X.current; }
 121   inline bool operator< (const _Self &X) const { return current <  X.current; }
 122
 123   inline difference_type operator-(const _Self &X) const {
 124     return current - X.current;
 125   }
 126 };
 127
 128 template <class _Iterator, class Func>
 129 inline mapped_iterator<_Iterator, Func>
 130 operator+(typename mapped_iterator<_Iterator, Func>::difference_type N,
 131           const mapped_iterator<_Iterator, Func>& X) {
 132   return mapped_iterator<_Iterator, Func>(X.getCurrent() - N, X.getFunc());
 133 }
 134
 135
 136 // map_iterator - Provide a convenient way to create mapped_iterators, just like
 137 // make_pair is useful for creating pairs...
 138 //
 139 template <class ItTy, class FuncTy>
 140 inline mapped_iterator<ItTy, FuncTy> map_iterator(const ItTy &I, FuncTy F) {
 141   return mapped_iterator<ItTy, FuncTy>(I, F);
 142 }
 143
 144 //===----------------------------------------------------------------------===//
 145 //     Extra additions to <utility>
 146 //===----------------------------------------------------------------------===//
 147
 148 /// \brief Function object to check whether the first component of a std::pair
 149 /// compares less than the first component of another std::pair.
 150 struct less_first {
 151   template <typename T> bool operator()(const T &lhs, const T &rhs) const {
 152     return lhs.first < rhs.first;
 153   }
 154 };
 155
 156 /// \brief Function object to check whether the second component of a std::pair
 157 /// compares less than the second component of another std::pair.
 158 struct less_second {
 159   template <typename T> bool operator()(const T &lhs, const T &rhs) const {
 160     return lhs.second < rhs.second;
 161   }
 162 };
 163
 164 //===----------------------------------------------------------------------===//
 165 //     Extra additions for arrays
 166 //===----------------------------------------------------------------------===//
 167
 168 /// Find the length of an array.
 169 template <class T, std::size_t N>
 170 LLVM_CONSTEXPR inline size_t array_lengthof(T (&)[N]) {
 171   return N;
 172 }
 173
 174 /// Adapt std::less<T> for array_pod_sort.
 175 template<typename T>
 176 inline int array_pod_sort_comparator(const void *P1, const void *P2) {
 177   if (std::less<T>()(*reinterpret_cast<const T*>(P1),
 178                      *reinterpret_cast<const T*>(P2)))
 179     return -1;
 180   if (std::less<T>()(*reinterpret_cast<const T*>(P2),
 181                      *reinterpret_cast<const T*>(P1)))
 182     return 1;
 183   return 0;
 184 }
 185
 186 /// get_array_pod_sort_comparator - This is an internal helper function used to
 187 /// get type deduction of T right.
 188 template<typename T>
 189 inline int (*get_array_pod_sort_comparator(const T &))
 190              (const void*, const void*) {
 191   return array_pod_sort_comparator<T>;
 192 }
 193
 194
 195 /// array_pod_sort - This sorts an array with the specified start and end
 196 /// extent.  This is just like std::sort, except that it calls qsort instead of
 197 /// using an inlined template.  qsort is slightly slower than std::sort, but
 198 /// most sorts are not performance critical in LLVM and std::sort has to be
 199 /// template instantiated for each type, leading to significant measured code
 200 /// bloat.  This function should generally be used instead of std::sort where
 201 /// possible.
 202 ///
 203 /// This function assumes that you have simple POD-like types that can be
 204 /// compared with std::less and can be moved with memcpy.  If this isn't true,
 205 /// you should use std::sort.
 206 ///
 207 /// NOTE: If qsort_r were portable, we could allow a custom comparator and
 208 /// default to std::less.
 209 template<class IteratorTy>
 210 inline void array_pod_sort(IteratorTy Start, IteratorTy End) {
 211   // Don't dereference start iterator of empty sequence.
 212   if (Start == End) return;
 213   qsort(&*Start, End-Start, sizeof(*Start),
 214         get_array_pod_sort_comparator(*Start));
 215 }
 216
 217 template <class IteratorTy>
 218 inline void array_pod_sort(
 219     IteratorTy Start, IteratorTy End,
 220     int (*Compare)(
 221         const typename std::iterator_traits<IteratorTy>::value_type *,
 222         const typename std::iterator_traits<IteratorTy>::value_type *)) {
 223   // Don't dereference start iterator of empty sequence.
 224   if (Start == End) return;
 225   qsort(&*Start, End - Start, sizeof(*Start),
 226         reinterpret_cast<int (*)(const void *, const void *)>(Compare));
 227 }
 228
 229 //===----------------------------------------------------------------------===//
 230 //     Extra additions to <algorithm>
 231 //===----------------------------------------------------------------------===//
 232
 233 /// For a container of pointers, deletes the pointers and then clears the
 234 /// container.
 235 template<typename Container>
 236 void DeleteContainerPointers(Container &C) {
 237   for (typename Container::iterator I = C.begin(), E = C.end(); I != E; ++I)
 238     delete *I;
 239   C.clear();
 240 }
 241
 242 /// In a container of pairs (usually a map) whose second element is a pointer,
 243 /// deletes the second elements and then clears the container.
 244 template<typename Container>
 245 void DeleteContainerSeconds(Container &C) {
 246   for (typename Container::iterator I = C.begin(), E = C.end(); I != E; ++I)
 247     delete I->second;
 248   C.clear();
 249 }
 250
 251 //===----------------------------------------------------------------------===//
 252 //     Extra additions to <memory>
 253 //===----------------------------------------------------------------------===//
 254
 255 #if LLVM_HAS_VARIADIC_TEMPLATES
 256
 257 // Implement make_unique according to N3656.
 258
 259 /// \brief Constructs a `new T()` with the given args and returns a
 260 ///        `unique_ptr<T>` which owns the object.
 261 ///
 262 /// Example:
 263 ///
 264 ///     auto p = make_unique<int>();
 265 ///     auto p = make_unique<std::tuple<int, int>>(0, 1);
 266 template <class T, class... Args>
 267 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 268 make_unique(Args &&... args) {
 269   return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
 270 }
 271
 272 /// \brief Constructs a `new T[n]` with the given args and returns a
 273 ///        `unique_ptr<T[]>` which owns the object.
 274 ///
 275 /// \param n size of the new array.
 276 ///
 277 /// Example:
 278 ///
 279 ///     auto p = make_unique<int[]>(2); // value-initializes the array with 0's.
 280 template <class T>
 281 typename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0,
 282                         std::unique_ptr<T>>::type
 283 make_unique(size_t n) {
 284   return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]());
 285 }
 286
 287 /// This function isn't used and is only here to provide better compile errors.
 288 template <class T, class... Args>
 289 typename std::enable_if<std::extent<T>::value != 0>::type
 290 make_unique(Args &&...) LLVM_DELETED_FUNCTION;
 291
 292 #else
 293
 294 template <class T>
 295 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 296 make_unique() {
 297   return std::unique_ptr<T>(new T());
 298 }
 299
 300 template <class T, class Arg1>
 301 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 302 make_unique(Arg1 &&arg1) {
 303   return std::unique_ptr<T>(new T(std::forward<Arg1>(arg1)));
 304 }
 305
 306 template <class T, class Arg1, class Arg2>
 307 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 308 make_unique(Arg1 &&arg1, Arg2 &&arg2) {
 309   return std::unique_ptr<T>(
 310       new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2)));
 311 }
 312
 313 template <class T, class Arg1, class Arg2, class Arg3>
 314 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 315 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3) {
 316   return std::unique_ptr<T>(new T(std::forward<Arg1>(arg1),
 317                                   std::forward<Arg2>(arg2),
 318                                   std::forward<Arg3>(arg3)));
 319 }
 320
 321 template <class T, class Arg1, class Arg2, class Arg3, class Arg4>
 322 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 323 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4) {
 324   return std::unique_ptr<T>(
 325       new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
 326             std::forward<Arg3>(arg3), std::forward<Arg4>(arg4)));
 327 }
 328
 329 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5>
 330 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 331 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5) {
 332   return std::unique_ptr<T>(
 333       new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
 334             std::forward<Arg3>(arg3), std::forward<Arg4>(arg4),
 335             std::forward<Arg5>(arg5)));
 336 }
 337
 338 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5,
 339           class Arg6>
 340 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 341 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5,
 342             Arg6 &&arg6) {
 343   return std::unique_ptr<T>(
 344       new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
 345             std::forward<Arg3>(arg3), std::forward<Arg4>(arg4),
 346             std::forward<Arg5>(arg5), std::forward<Arg6>(arg6)));
 347 }
 348
 349 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5,
 350           class Arg6, class Arg7>
 351 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 352 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5,
 353             Arg6 &&arg6, Arg7 &&arg7) {
 354   return std::unique_ptr<T>(
 355       new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
 356             std::forward<Arg3>(arg3), std::forward<Arg4>(arg4),
 357             std::forward<Arg5>(arg5), std::forward<Arg6>(arg6),
 358             std::forward<Arg7>(arg7)));
 359 }
 360
 361 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5,
 362           class Arg6, class Arg7, class Arg8>
 363 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 364 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5,
 365             Arg6 &&arg6, Arg7 &&arg7, Arg8 &&arg8) {
 366   return std::unique_ptr<T>(
 367       new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
 368             std::forward<Arg3>(arg3), std::forward<Arg4>(arg4),
 369             std::forward<Arg5>(arg5), std::forward<Arg6>(arg6),
 370             std::forward<Arg7>(arg7), std::forward<Arg8>(arg8)));
 371 }
 372
 373 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5,
 374           class Arg6, class Arg7, class Arg8, class Arg9>
 375 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 376 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5,
 377             Arg6 &&arg6, Arg7 &&arg7, Arg8 &&arg8, Arg9 &&arg9) {
 378   return std::unique_ptr<T>(
 379       new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
 380             std::forward<Arg3>(arg3), std::forward<Arg4>(arg4),
 381             std::forward<Arg5>(arg5), std::forward<Arg6>(arg6),
 382             std::forward<Arg7>(arg7), std::forward<Arg8>(arg8),
 383             std::forward<Arg9>(arg9)));
 384 }
 385
 386 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5,
 387           class Arg6, class Arg7, class Arg8, class Arg9, class Arg10>
 388 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 389 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5,
 390             Arg6 &&arg6, Arg7 &&arg7, Arg8 &&arg8, Arg9 &&arg9, Arg10 &&arg10) {
 391   return std::unique_ptr<T>(
 392       new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
 393             std::forward<Arg3>(arg3), std::forward<Arg4>(arg4),
 394             std::forward<Arg5>(arg5), std::forward<Arg6>(arg6),
 395             std::forward<Arg7>(arg7), std::forward<Arg8>(arg8),
 396             std::forward<Arg9>(arg9), std::forward<Arg10>(arg10)));
 397 }
 398
 399 template <class T>
 400 typename std::enable_if<std::is_array<T>::value &&std::extent<T>::value == 0,
 401                         std::unique_ptr<T>>::type
 402 make_unique(size_t n) {
 403   return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]());
 404 }
 405
 406 #endif
 407
 408 } // End llvm namespace
 409
 410 #endif