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   inline mapped_iterator(const mapped_iterator &It)
 101     : current(It.current), Fn(It.Fn) {}
 102
 103   inline value_type operator*() const {   // All this work to do this
 104     return Fn(*current);         // little change
 105   }
 106
 107   _Self& operator++() { ++current; return *this; }
 108   _Self& operator--() { --current; return *this; }
 109   _Self  operator++(int) { _Self __tmp = *this; ++current; return __tmp; }
 110   _Self  operator--(int) { _Self __tmp = *this; --current; return __tmp; }
 111   _Self  operator+    (difference_type n) const {
 112     return _Self(current + n, Fn);
 113   }
 114   _Self& operator+=   (difference_type n) { current += n; return *this; }
 115   _Self  operator-    (difference_type n) const {
 116     return _Self(current - n, Fn);
 117   }
 118   _Self& operator-=   (difference_type n) { current -= n; return *this; }
 119   reference operator[](difference_type n) const { return *(*this + n); }
 120
 121   inline bool operator!=(const _Self &X) const { return !operator==(X); }
 122   inline bool operator==(const _Self &X) const { return current == X.current; }
 123   inline bool operator< (const _Self &X) const { return current <  X.current; }
 124
 125   inline difference_type operator-(const _Self &X) const {
 126     return current - X.current;
 127   }
 128 };
 129
 130 template <class _Iterator, class Func>
 131 inline mapped_iterator<_Iterator, Func>
 132 operator+(typename mapped_iterator<_Iterator, Func>::difference_type N,
 133           const mapped_iterator<_Iterator, Func>& X) {
 134   return mapped_iterator<_Iterator, Func>(X.getCurrent() - N, X.getFunc());
 135 }
 136
 137
 138 // map_iterator - Provide a convenient way to create mapped_iterators, just like
 139 // make_pair is useful for creating pairs...
 140 //
 141 template <class ItTy, class FuncTy>
 142 inline mapped_iterator<ItTy, FuncTy> map_iterator(const ItTy &I, FuncTy F) {
 143   return mapped_iterator<ItTy, FuncTy>(I, F);
 144 }
 145
 146 //===----------------------------------------------------------------------===//
 147 //     Extra additions to <utility>
 148 //===----------------------------------------------------------------------===//
 149
 150 /// \brief Function object to check whether the first component of a std::pair
 151 /// compares less than the first component of another std::pair.
 152 struct less_first {
 153   template <typename T> bool operator()(const T &lhs, const T &rhs) const {
 154     return lhs.first < rhs.first;
 155   }
 156 };
 157
 158 /// \brief Function object to check whether the second component of a std::pair
 159 /// compares less than the second component of another std::pair.
 160 struct less_second {
 161   template <typename T> bool operator()(const T &lhs, const T &rhs) const {
 162     return lhs.second < rhs.second;
 163   }
 164 };
 165
 166 //===----------------------------------------------------------------------===//
 167 //     Extra additions for arrays
 168 //===----------------------------------------------------------------------===//
 169
 170 /// Find where an array ends (for ending iterators)
 171 /// This returns a pointer to the byte immediately
 172 /// after the end of an array.
 173 template<class T, std::size_t N>
 174 inline T *array_endof(T (&x)[N]) {
 175   return x+N;
 176 }
 177
 178 /// Find the length of an array.
 179 template<class T, std::size_t N>
 180 inline size_t array_lengthof(T (&)[N]) {
 181   return N;
 182 }
 183
 184 /// array_pod_sort_comparator - This is helper function for array_pod_sort,
 185 /// which just uses operator< on T.
 186 template<typename T>
 187 inline int array_pod_sort_comparator(const void *P1, const void *P2) {
 188   if (*reinterpret_cast<const T*>(P1) < *reinterpret_cast<const T*>(P2))
 189     return -1;
 190   if (*reinterpret_cast<const T*>(P2) < *reinterpret_cast<const T*>(P1))
 191     return 1;
 192   return 0;
 193 }
 194
 195 /// get_array_pod_sort_comparator - This is an internal helper function used to
 196 /// get type deduction of T right.
 197 template<typename T>
 198 inline int (*get_array_pod_sort_comparator(const T &))
 199              (const void*, const void*) {
 200   return array_pod_sort_comparator<T>;
 201 }
 202
 203
 204 /// array_pod_sort - This sorts an array with the specified start and end
 205 /// extent.  This is just like std::sort, except that it calls qsort instead of
 206 /// using an inlined template.  qsort is slightly slower than std::sort, but
 207 /// most sorts are not performance critical in LLVM and std::sort has to be
 208 /// template instantiated for each type, leading to significant measured code
 209 /// bloat.  This function should generally be used instead of std::sort where
 210 /// possible.
 211 ///
 212 /// This function assumes that you have simple POD-like types that can be
 213 /// compared with operator< and can be moved with memcpy.  If this isn't true,
 214 /// you should use std::sort.
 215 ///
 216 /// NOTE: If qsort_r were portable, we could allow a custom comparator and
 217 /// default to std::less.
 218 template<class IteratorTy>
 219 inline void array_pod_sort(IteratorTy Start, IteratorTy End) {
 220   // Don't dereference start iterator of empty sequence.
 221   if (Start == End) return;
 222   qsort(&*Start, End-Start, sizeof(*Start),
 223         get_array_pod_sort_comparator(*Start));
 224 }
 225
 226 template <class IteratorTy>
 227 inline void array_pod_sort(
 228     IteratorTy Start, IteratorTy End,
 229     int (*Compare)(
 230         const typename std::iterator_traits<IteratorTy>::value_type *,
 231         const typename std::iterator_traits<IteratorTy>::value_type *)) {
 232   // Don't dereference start iterator of empty sequence.
 233   if (Start == End) return;
 234   qsort(&*Start, End - Start, sizeof(*Start),
 235         reinterpret_cast<int (*)(const void *, const void *)>(Compare));
 236 }
 237
 238 //===----------------------------------------------------------------------===//
 239 //     Extra additions to <algorithm>
 240 //===----------------------------------------------------------------------===//
 241
 242 /// For a container of pointers, deletes the pointers and then clears the
 243 /// container.
 244 template<typename Container>
 245 void DeleteContainerPointers(Container &C) {
 246   for (typename Container::iterator I = C.begin(), E = C.end(); I != E; ++I)
 247     delete *I;
 248   C.clear();
 249 }
 250
 251 /// In a container of pairs (usually a map) whose second element is a pointer,
 252 /// deletes the second elements and then clears the container.
 253 template<typename Container>
 254 void DeleteContainerSeconds(Container &C) {
 255   for (typename Container::iterator I = C.begin(), E = C.end(); I != E; ++I)
 256     delete I->second;
 257   C.clear();
 258 }
 259
 260 //===----------------------------------------------------------------------===//
 261 //     Extra additions to <memory>
 262 //===----------------------------------------------------------------------===//
 263
 264 #if LLVM_HAS_VARIADIC_TEMPLATES
 265
 266 /// Implement make_unique according to N3656.
 267 ///
 268 /// template<class T, class... Args> unique_ptr<T> make_unique(Args&&... args);
 269 /// Remarks: This function shall not participate in overload resolution unless
 270 ///          T is not an array.
 271 /// Returns: unique_ptr<T>(new T(std::forward<Args>(args)...)).
 272 ///
 273 /// template<class T> unique_ptr<T> make_unique(size_t n);
 274 /// Remarks: This function shall not participate in overload resolution unless
 275 ///          T is an array of unknown bound.
 276 /// Returns: unique_ptr<T>(new typename remove_extent<T>::type[n]()).
 277 ///
 278 /// template<class T, class... Args> unspecified make_unique(Args&&...) = delete;
 279 /// Remarks: This function shall not participate in overload resolution unless
 280 ///          T is an array of known bound.
 281 ///
 282 /// Use scenarios:
 283 ///
 284 /// Single object case:
 285 ///
 286 /// auto p0 = make_unique<int>();
 287 ///
 288 /// auto p2 = make_unique<std::tuple<int, int>>(0, 1);
 289 ///
 290 /// Array case:
 291 ///
 292 /// auto p1 = make_unique<int[]>(2); // value-initializes the array with 0's.
 293 ///
 294 template <class T, class... Args>
 295 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 296 make_unique(Args &&... args) {
 297   return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
 298 }
 299
 300 template <class T>
 301 typename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0,
 302                         std::unique_ptr<T>>::type
 303 make_unique(size_t n) {
 304   return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]());
 305 }
 306
 307 template <class T, class... Args>
 308 typename std::enable_if<std::extent<T>::value != 0>::type
 309 make_unique(Args &&...) LLVM_DELETED_FUNCTION;
 310
 311 #else
 312
 313 template <class T>
 314 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 315 make_unique() {
 316   return std::unique_ptr<T>(new T());
 317 }
 318
 319 template <class T, class Arg1>
 320 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 321 make_unique(Arg1 &&arg1) {
 322   return std::unique_ptr<T>(new T(std::forward<Arg1>(arg1)));
 323 }
 324
 325 template <class T, class Arg1, class Arg2>
 326 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 327 make_unique(Arg1 &&arg1, Arg2 &&arg2) {
 328   return std::unique_ptr<T>(
 329       new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2)));
 330 }
 331
 332 template <class T, class Arg1, class Arg2, class Arg3>
 333 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 334 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3) {
 335   return std::unique_ptr<T>(new T(std::forward<Arg1>(arg1),
 336                                   std::forward<Arg2>(arg2),
 337                                   std::forward<Arg3>(arg3)));
 338 }
 339
 340 template <class T, class Arg1, class Arg2, class Arg3, class Arg4>
 341 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 342 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4) {
 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 }
 347
 348 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5>
 349 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 350 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5) {
 351   return std::unique_ptr<T>(
 352       new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
 353             std::forward<Arg3>(arg3), std::forward<Arg4>(arg4),
 354             std::forward<Arg5>(arg5)));
 355 }
 356
 357 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5,
 358           class Arg6>
 359 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 360 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5,
 361             Arg6 &&arg6) {
 362   return std::unique_ptr<T>(
 363       new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
 364             std::forward<Arg3>(arg3), std::forward<Arg4>(arg4),
 365             std::forward<Arg5>(arg5), std::forward<Arg6>(arg6)));
 366 }
 367
 368 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5,
 369           class Arg6, class Arg7>
 370 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 371 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5,
 372             Arg6 &&arg6, Arg7 &&arg7) {
 373   return std::unique_ptr<T>(
 374       new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
 375             std::forward<Arg3>(arg3), std::forward<Arg4>(arg4),
 376             std::forward<Arg5>(arg5), std::forward<Arg6>(arg6),
 377             std::forward<Arg7>(arg7)));
 378 }
 379
 380 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5,
 381           class Arg6, class Arg7, class Arg8>
 382 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 383 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5,
 384             Arg6 &&arg6, Arg7 &&arg7, Arg8 &&arg8) {
 385   return std::unique_ptr<T>(
 386       new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
 387             std::forward<Arg3>(arg3), std::forward<Arg4>(arg4),
 388             std::forward<Arg5>(arg5), std::forward<Arg6>(arg6),
 389             std::forward<Arg7>(arg7), std::forward<Arg8>(arg8)));
 390 }
 391
 392 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5,
 393           class Arg6, class Arg7, class Arg8, class Arg9>
 394 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 395 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5,
 396             Arg6 &&arg6, Arg7 &&arg7, Arg8 &&arg8, Arg9 &&arg9) {
 397   return std::unique_ptr<T>(
 398       new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
 399             std::forward<Arg3>(arg3), std::forward<Arg4>(arg4),
 400             std::forward<Arg5>(arg5), std::forward<Arg6>(arg6),
 401             std::forward<Arg7>(arg7), std::forward<Arg8>(arg8),
 402             std::forward<Arg9>(arg9)));
 403 }
 404
 405 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5,
 406           class Arg6, class Arg7, class Arg8, class Arg9, class Arg10>
 407 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 408 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5,
 409             Arg6 &&arg6, Arg7 &&arg7, Arg8 &&arg8, Arg9 &&arg9, Arg10 &&arg10) {
 410   return std::unique_ptr<T>(
 411       new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
 412             std::forward<Arg3>(arg3), std::forward<Arg4>(arg4),
 413             std::forward<Arg5>(arg5), std::forward<Arg6>(arg6),
 414             std::forward<Arg7>(arg7), std::forward<Arg8>(arg8),
 415             std::forward<Arg9>(arg9), std::forward<Arg10>(arg10)));
 416 }
 417
 418 template <class T>
 419 typename std::enable_if<std::is_array<T>::value &&std::extent<T>::value == 0,
 420                         std::unique_ptr<T>>::type
 421 make_unique(size_t n) {
 422   return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]());
 423 }
 424
 425 #endif
 426
 427 } // End llvm namespace
 428
 429 #endif