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 /// array_pod_sort_comparator - This is helper function for array_pod_sort,
 175 /// which just uses operator< on T.
 176 template<typename T>
 177 inline int array_pod_sort_comparator(const void *P1, const void *P2) {
 178   if (*reinterpret_cast<const T*>(P1) < *reinterpret_cast<const T*>(P2))
 179     return -1;
 180   if (*reinterpret_cast<const T*>(P2) < *reinterpret_cast<const T*>(P1))
 181     return 1;
 182   return 0;
 183 }
 184
 185 /// get_array_pod_sort_comparator - This is an internal helper function used to
 186 /// get type deduction of T right.
 187 template<typename T>
 188 inline int (*get_array_pod_sort_comparator(const T &))
 189              (const void*, const void*) {
 190   return array_pod_sort_comparator<T>;
 191 }
 192
 193
 194 /// array_pod_sort - This sorts an array with the specified start and end
 195 /// extent.  This is just like std::sort, except that it calls qsort instead of
 196 /// using an inlined template.  qsort is slightly slower than std::sort, but
 197 /// most sorts are not performance critical in LLVM and std::sort has to be
 198 /// template instantiated for each type, leading to significant measured code
 199 /// bloat.  This function should generally be used instead of std::sort where
 200 /// possible.
 201 ///
 202 /// This function assumes that you have simple POD-like types that can be
 203 /// compared with operator< and can be moved with memcpy.  If this isn't true,
 204 /// you should use std::sort.
 205 ///
 206 /// NOTE: If qsort_r were portable, we could allow a custom comparator and
 207 /// default to std::less.
 208 template<class IteratorTy>
 209 inline void array_pod_sort(IteratorTy Start, IteratorTy End) {
 210   // Don't dereference start iterator of empty sequence.
 211   if (Start == End) return;
 212   qsort(&*Start, End-Start, sizeof(*Start),
 213         get_array_pod_sort_comparator(*Start));
 214 }
 215
 216 template <class IteratorTy>
 217 inline void array_pod_sort(
 218     IteratorTy Start, IteratorTy End,
 219     int (*Compare)(
 220         const typename std::iterator_traits<IteratorTy>::value_type *,
 221         const typename std::iterator_traits<IteratorTy>::value_type *)) {
 222   // Don't dereference start iterator of empty sequence.
 223   if (Start == End) return;
 224   qsort(&*Start, End - Start, sizeof(*Start),
 225         reinterpret_cast<int (*)(const void *, const void *)>(Compare));
 226 }
 227
 228 //===----------------------------------------------------------------------===//
 229 //     Extra additions to <algorithm>
 230 //===----------------------------------------------------------------------===//
 231
 232 /// For a container of pointers, deletes the pointers and then clears the
 233 /// container.
 234 template<typename Container>
 235 void DeleteContainerPointers(Container &C) {
 236   for (typename Container::iterator I = C.begin(), E = C.end(); I != E; ++I)
 237     delete *I;
 238   C.clear();
 239 }
 240
 241 /// In a container of pairs (usually a map) whose second element is a pointer,
 242 /// deletes the second elements and then clears the container.
 243 template<typename Container>
 244 void DeleteContainerSeconds(Container &C) {
 245   for (typename Container::iterator I = C.begin(), E = C.end(); I != E; ++I)
 246     delete I->second;
 247   C.clear();
 248 }
 249
 250 //===----------------------------------------------------------------------===//
 251 //     Extra additions to <memory>
 252 //===----------------------------------------------------------------------===//
 253
 254 #if LLVM_HAS_VARIADIC_TEMPLATES
 255
 256 // Implement make_unique according to N3656.
 257
 258 /// \brief Constructs a `new T()` with the given args and returns a
 259 ///        `unique_ptr<T>` which owns the object.
 260 ///
 261 /// Example:
 262 ///
 263 ///     auto p = make_unique<int>();
 264 ///     auto p = make_unique<std::tuple<int, int>>(0, 1);
 265 template <class T, class... Args>
 266 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 267 make_unique(Args &&... args) {
 268   return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
 269 }
 270
 271 /// \brief Constructs a `new T[n]` with the given args and returns a
 272 ///        `unique_ptr<T[]>` which owns the object.
 273 ///
 274 /// \param n size of the new array.
 275 ///
 276 /// Example:
 277 ///
 278 ///     auto p = make_unique<int[]>(2); // value-initializes the array with 0's.
 279 template <class T>
 280 typename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0,
 281                         std::unique_ptr<T>>::type
 282 make_unique(size_t n) {
 283   return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]());
 284 }
 285
 286 /// This function isn't used and is only here to provide better compile errors.
 287 template <class T, class... Args>
 288 typename std::enable_if<std::extent<T>::value != 0>::type
 289 make_unique(Args &&...) LLVM_DELETED_FUNCTION;
 290
 291 #else
 292
 293 template <class T>
 294 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 295 make_unique() {
 296   return std::unique_ptr<T>(new T());
 297 }
 298
 299 template <class T, class Arg1>
 300 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 301 make_unique(Arg1 &&arg1) {
 302   return std::unique_ptr<T>(new T(std::forward<Arg1>(arg1)));
 303 }
 304
 305 template <class T, class Arg1, class Arg2>
 306 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 307 make_unique(Arg1 &&arg1, Arg2 &&arg2) {
 308   return std::unique_ptr<T>(
 309       new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2)));
 310 }
 311
 312 template <class T, class Arg1, class Arg2, class Arg3>
 313 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 314 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3) {
 315   return std::unique_ptr<T>(new T(std::forward<Arg1>(arg1),
 316                                   std::forward<Arg2>(arg2),
 317                                   std::forward<Arg3>(arg3)));
 318 }
 319
 320 template <class T, class Arg1, class Arg2, class Arg3, class Arg4>
 321 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 322 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4) {
 323   return std::unique_ptr<T>(
 324       new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
 325             std::forward<Arg3>(arg3), std::forward<Arg4>(arg4)));
 326 }
 327
 328 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5>
 329 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 330 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5) {
 331   return std::unique_ptr<T>(
 332       new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
 333             std::forward<Arg3>(arg3), std::forward<Arg4>(arg4),
 334             std::forward<Arg5>(arg5)));
 335 }
 336
 337 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5,
 338           class Arg6>
 339 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 340 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5,
 341             Arg6 &&arg6) {
 342   return std::unique_ptr<T>(
 343       new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
 344             std::forward<Arg3>(arg3), std::forward<Arg4>(arg4),
 345             std::forward<Arg5>(arg5), std::forward<Arg6>(arg6)));
 346 }
 347
 348 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5,
 349           class Arg6, class Arg7>
 350 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 351 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5,
 352             Arg6 &&arg6, Arg7 &&arg7) {
 353   return std::unique_ptr<T>(
 354       new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
 355             std::forward<Arg3>(arg3), std::forward<Arg4>(arg4),
 356             std::forward<Arg5>(arg5), std::forward<Arg6>(arg6),
 357             std::forward<Arg7>(arg7)));
 358 }
 359
 360 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5,
 361           class Arg6, class Arg7, class Arg8>
 362 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 363 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5,
 364             Arg6 &&arg6, Arg7 &&arg7, Arg8 &&arg8) {
 365   return std::unique_ptr<T>(
 366       new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
 367             std::forward<Arg3>(arg3), std::forward<Arg4>(arg4),
 368             std::forward<Arg5>(arg5), std::forward<Arg6>(arg6),
 369             std::forward<Arg7>(arg7), std::forward<Arg8>(arg8)));
 370 }
 371
 372 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5,
 373           class Arg6, class Arg7, class Arg8, class Arg9>
 374 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 375 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5,
 376             Arg6 &&arg6, Arg7 &&arg7, Arg8 &&arg8, Arg9 &&arg9) {
 377   return std::unique_ptr<T>(
 378       new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
 379             std::forward<Arg3>(arg3), std::forward<Arg4>(arg4),
 380             std::forward<Arg5>(arg5), std::forward<Arg6>(arg6),
 381             std::forward<Arg7>(arg7), std::forward<Arg8>(arg8),
 382             std::forward<Arg9>(arg9)));
 383 }
 384
 385 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5,
 386           class Arg6, class Arg7, class Arg8, class Arg9, class Arg10>
 387 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 388 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5,
 389             Arg6 &&arg6, Arg7 &&arg7, Arg8 &&arg8, Arg9 &&arg9, Arg10 &&arg10) {
 390   return std::unique_ptr<T>(
 391       new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
 392             std::forward<Arg3>(arg3), std::forward<Arg4>(arg4),
 393             std::forward<Arg5>(arg5), std::forward<Arg6>(arg6),
 394             std::forward<Arg7>(arg7), std::forward<Arg8>(arg8),
 395             std::forward<Arg9>(arg9), std::forward<Arg10>(arg10)));
 396 }
 397
 398 template <class T>
 399 typename std::enable_if<std::is_array<T>::value &&std::extent<T>::value == 0,
 400                         std::unique_ptr<T>>::type
 401 make_unique(size_t n) {
 402   return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]());
 403 }
 404
 405 #endif
 406
 407 } // End llvm namespace
 408
 409 #endif