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 /// An efficient, type-erasing, non-owning reference to a callable. This is
  59 /// intended for use as the type of a function parameter that is not used
  60 /// after the function in question returns.
  61 ///
  62 /// This class does not own the callable, so it is not in general safe to store
  63 /// a function_ref.
  64 template<typename Fn> class function_ref;
  65
  66 #if LLVM_HAS_VARIADIC_TEMPLATES
  67
  68 template<typename Ret, typename ...Params>
  69 class function_ref<Ret(Params...)> {
  70   Ret (*callback)(void *callable, Params ...params);
  71   void *callable;
  72
  73   template<typename Callable>
  74   static Ret callback_fn(void *callable, Params ...params) {
  75     return (*reinterpret_cast<Callable*>(callable))(
  76         std::forward<Params>(params)...);
  77   }
  78
  79 public:
  80   template<typename Callable>
  81   function_ref(Callable &&callable)
  82       : callback(callback_fn<typename std::remove_reference<Callable>::type>),
  83         callable(reinterpret_cast<void *>(&callable)) {}
  84   Ret operator()(Params ...params) const {
  85     return callback(callable, std::forward<Params>(params)...);
  86   }
  87 };
  88
  89 #else
  90
  91 template<typename Ret>
  92 class function_ref<Ret()> {
  93   Ret (*callback)(void *callable);
  94   void *callable;
  95
  96   template<typename Callable>
  97   static Ret callback_fn(void *callable) {
  98     return (*reinterpret_cast<Callable*>(callable))();
  99   }
 100
 101 public:
 102   template<typename Callable>
 103   function_ref(Callable &&callable)
 104       : callback(callback_fn<typename std::remove_reference<Callable>::type>),
 105         callable(reinterpret_cast<void *>(&callable)) {}
 106   Ret operator()() const { return callback(callable); }
 107 };
 108
 109 template<typename Ret, typename Param1>
 110 class function_ref<Ret(Param1)> {
 111   Ret (*callback)(void *callable, Param1 param1);
 112   void *callable;
 113
 114   template<typename Callable>
 115   static Ret callback_fn(void *callable, Param1 param1) {
 116     return (*reinterpret_cast<Callable*>(callable))(
 117         std::forward<Param1>(param1));
 118   }
 119
 120 public:
 121   template<typename Callable>
 122   function_ref(Callable &&callable)
 123       : callback(callback_fn<typename std::remove_reference<Callable>::type>),
 124         callable(reinterpret_cast<void *>(&callable)) {}
 125   Ret operator()(Param1 param1) {
 126     return callback(callable, std::forward<Param1>(param1));
 127   }
 128 };
 129
 130 template<typename Ret, typename Param1, typename Param2>
 131 class function_ref<Ret(Param1, Param2)> {
 132   Ret (*callback)(void *callable, Param1 param1, Param2 param2);
 133   void *callable;
 134
 135   template<typename Callable>
 136   static Ret callback_fn(void *callable, Param1 param1, Param2 param2) {
 137     return (*reinterpret_cast<Callable*>(callable))(
 138         std::forward<Param1>(param1),
 139         std::forward<Param2>(param2));
 140   }
 141
 142 public:
 143   template<typename Callable>
 144   function_ref(Callable &&callable)
 145       : callback(callback_fn<typename std::remove_reference<Callable>::type>),
 146         callable(reinterpret_cast<void *>(&callable)) {}
 147   Ret operator()(Param1 param1, Param2 param2) {
 148     return callback(callable,
 149                     std::forward<Param1>(param1),
 150                     std::forward<Param2>(param2));
 151   }
 152 };
 153
 154 template<typename Ret, typename Param1, typename Param2, typename Param3>
 155 class function_ref<Ret(Param1, Param2, Param3)> {
 156   Ret (*callback)(void *callable, Param1 param1, Param2 param2, Param3 param3);
 157   void *callable;
 158
 159   template<typename Callable>
 160   static Ret callback_fn(void *callable, Param1 param1, Param2 param2,
 161                          Param3 param3) {
 162     return (*reinterpret_cast<Callable*>(callable))(
 163         std::forward<Param1>(param1),
 164         std::forward<Param2>(param2),
 165         std::forward<Param3>(param3));
 166   }
 167
 168 public:
 169   template<typename Callable>
 170   function_ref(Callable &&callable)
 171       : callback(callback_fn<typename std::remove_reference<Callable>::type>),
 172         callable(reinterpret_cast<void *>(&callable)) {}
 173   Ret operator()(Param1 param1, Param2 param2, Param3 param3) {
 174     return callback(callable,
 175                     std::forward<Param1>(param1),
 176                     std::forward<Param2>(param2),
 177                     std::forward<Param3>(param3));
 178   }
 179 };
 180
 181 #endif
 182
 183 // deleter - Very very very simple method that is used to invoke operator
 184 // delete on something.  It is used like this:
 185 //
 186 //   for_each(V.begin(), B.end(), deleter<Interval>);
 187 //
 188 template <class T>
 189 inline void deleter(T *Ptr) {
 190   delete Ptr;
 191 }
 192
 193
 194
 195 //===----------------------------------------------------------------------===//
 196 //     Extra additions to <iterator>
 197 //===----------------------------------------------------------------------===//
 198
 199 // mapped_iterator - This is a simple iterator adapter that causes a function to
 200 // be dereferenced whenever operator* is invoked on the iterator.
 201 //
 202 template <class RootIt, class UnaryFunc>
 203 class mapped_iterator {
 204   RootIt current;
 205   UnaryFunc Fn;
 206 public:
 207   typedef typename std::iterator_traits<RootIt>::iterator_category
 208           iterator_category;
 209   typedef typename std::iterator_traits<RootIt>::difference_type
 210           difference_type;
 211   typedef typename UnaryFunc::result_type value_type;
 212
 213   typedef void pointer;
 214   //typedef typename UnaryFunc::result_type *pointer;
 215   typedef void reference;        // Can't modify value returned by fn
 216
 217   typedef RootIt iterator_type;
 218   typedef mapped_iterator<RootIt, UnaryFunc> _Self;
 219
 220   inline const RootIt &getCurrent() const { return current; }
 221   inline const UnaryFunc &getFunc() const { return Fn; }
 222
 223   inline explicit mapped_iterator(const RootIt &I, UnaryFunc F)
 224     : current(I), Fn(F) {}
 225
 226   inline value_type operator*() const {   // All this work to do this
 227     return Fn(*current);         // little change
 228   }
 229
 230   _Self& operator++() { ++current; return *this; }
 231   _Self& operator--() { --current; return *this; }
 232   _Self  operator++(int) { _Self __tmp = *this; ++current; return __tmp; }
 233   _Self  operator--(int) { _Self __tmp = *this; --current; return __tmp; }
 234   _Self  operator+    (difference_type n) const {
 235     return _Self(current + n, Fn);
 236   }
 237   _Self& operator+=   (difference_type n) { current += n; return *this; }
 238   _Self  operator-    (difference_type n) const {
 239     return _Self(current - n, Fn);
 240   }
 241   _Self& operator-=   (difference_type n) { current -= n; return *this; }
 242   reference operator[](difference_type n) const { return *(*this + n); }
 243
 244   inline bool operator!=(const _Self &X) const { return !operator==(X); }
 245   inline bool operator==(const _Self &X) const { return current == X.current; }
 246   inline bool operator< (const _Self &X) const { return current <  X.current; }
 247
 248   inline difference_type operator-(const _Self &X) const {
 249     return current - X.current;
 250   }
 251 };
 252
 253 template <class _Iterator, class Func>
 254 inline mapped_iterator<_Iterator, Func>
 255 operator+(typename mapped_iterator<_Iterator, Func>::difference_type N,
 256           const mapped_iterator<_Iterator, Func>& X) {
 257   return mapped_iterator<_Iterator, Func>(X.getCurrent() - N, X.getFunc());
 258 }
 259
 260
 261 // map_iterator - Provide a convenient way to create mapped_iterators, just like
 262 // make_pair is useful for creating pairs...
 263 //
 264 template <class ItTy, class FuncTy>
 265 inline mapped_iterator<ItTy, FuncTy> map_iterator(const ItTy &I, FuncTy F) {
 266   return mapped_iterator<ItTy, FuncTy>(I, F);
 267 }
 268
 269 //===----------------------------------------------------------------------===//
 270 //     Extra additions to <utility>
 271 //===----------------------------------------------------------------------===//
 272
 273 /// \brief Function object to check whether the first component of a std::pair
 274 /// compares less than the first component of another std::pair.
 275 struct less_first {
 276   template <typename T> bool operator()(const T &lhs, const T &rhs) const {
 277     return lhs.first < rhs.first;
 278   }
 279 };
 280
 281 /// \brief Function object to check whether the second component of a std::pair
 282 /// compares less than the second component of another std::pair.
 283 struct less_second {
 284   template <typename T> bool operator()(const T &lhs, const T &rhs) const {
 285     return lhs.second < rhs.second;
 286   }
 287 };
 288
 289 //===----------------------------------------------------------------------===//
 290 //     Extra additions for arrays
 291 //===----------------------------------------------------------------------===//
 292
 293 /// Find the length of an array.
 294 template <class T, std::size_t N>
 295 LLVM_CONSTEXPR inline size_t array_lengthof(T (&)[N]) {
 296   return N;
 297 }
 298
 299 /// Adapt std::less<T> for array_pod_sort.
 300 template<typename T>
 301 inline int array_pod_sort_comparator(const void *P1, const void *P2) {
 302   if (std::less<T>()(*reinterpret_cast<const T*>(P1),
 303                      *reinterpret_cast<const T*>(P2)))
 304     return -1;
 305   if (std::less<T>()(*reinterpret_cast<const T*>(P2),
 306                      *reinterpret_cast<const T*>(P1)))
 307     return 1;
 308   return 0;
 309 }
 310
 311 /// get_array_pod_sort_comparator - This is an internal helper function used to
 312 /// get type deduction of T right.
 313 template<typename T>
 314 inline int (*get_array_pod_sort_comparator(const T &))
 315              (const void*, const void*) {
 316   return array_pod_sort_comparator<T>;
 317 }
 318
 319
 320 /// array_pod_sort - This sorts an array with the specified start and end
 321 /// extent.  This is just like std::sort, except that it calls qsort instead of
 322 /// using an inlined template.  qsort is slightly slower than std::sort, but
 323 /// most sorts are not performance critical in LLVM and std::sort has to be
 324 /// template instantiated for each type, leading to significant measured code
 325 /// bloat.  This function should generally be used instead of std::sort where
 326 /// possible.
 327 ///
 328 /// This function assumes that you have simple POD-like types that can be
 329 /// compared with std::less and can be moved with memcpy.  If this isn't true,
 330 /// you should use std::sort.
 331 ///
 332 /// NOTE: If qsort_r were portable, we could allow a custom comparator and
 333 /// default to std::less.
 334 template<class IteratorTy>
 335 inline void array_pod_sort(IteratorTy Start, IteratorTy End) {
 336   // Don't dereference start iterator of empty sequence.
 337   if (Start == End) return;
 338   qsort(&*Start, End-Start, sizeof(*Start),
 339         get_array_pod_sort_comparator(*Start));
 340 }
 341
 342 template <class IteratorTy>
 343 inline void array_pod_sort(
 344     IteratorTy Start, IteratorTy End,
 345     int (*Compare)(
 346         const typename std::iterator_traits<IteratorTy>::value_type *,
 347         const typename std::iterator_traits<IteratorTy>::value_type *)) {
 348   // Don't dereference start iterator of empty sequence.
 349   if (Start == End) return;
 350   qsort(&*Start, End - Start, sizeof(*Start),
 351         reinterpret_cast<int (*)(const void *, const void *)>(Compare));
 352 }
 353
 354 //===----------------------------------------------------------------------===//
 355 //     Extra additions to <algorithm>
 356 //===----------------------------------------------------------------------===//
 357
 358 /// For a container of pointers, deletes the pointers and then clears the
 359 /// container.
 360 template<typename Container>
 361 void DeleteContainerPointers(Container &C) {
 362   for (typename Container::iterator I = C.begin(), E = C.end(); I != E; ++I)
 363     delete *I;
 364   C.clear();
 365 }
 366
 367 /// In a container of pairs (usually a map) whose second element is a pointer,
 368 /// deletes the second elements and then clears the container.
 369 template<typename Container>
 370 void DeleteContainerSeconds(Container &C) {
 371   for (typename Container::iterator I = C.begin(), E = C.end(); I != E; ++I)
 372     delete I->second;
 373   C.clear();
 374 }
 375
 376 //===----------------------------------------------------------------------===//
 377 //     Extra additions to <memory>
 378 //===----------------------------------------------------------------------===//
 379
 380 #if LLVM_HAS_VARIADIC_TEMPLATES
 381
 382 // Implement make_unique according to N3656.
 383
 384 /// \brief Constructs a `new T()` with the given args and returns a
 385 ///        `unique_ptr<T>` which owns the object.
 386 ///
 387 /// Example:
 388 ///
 389 ///     auto p = make_unique<int>();
 390 ///     auto p = make_unique<std::tuple<int, int>>(0, 1);
 391 template <class T, class... Args>
 392 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 393 make_unique(Args &&... args) {
 394   return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
 395 }
 396
 397 /// \brief Constructs a `new T[n]` with the given args and returns a
 398 ///        `unique_ptr<T[]>` which owns the object.
 399 ///
 400 /// \param n size of the new array.
 401 ///
 402 /// Example:
 403 ///
 404 ///     auto p = make_unique<int[]>(2); // value-initializes the array with 0's.
 405 template <class T>
 406 typename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0,
 407                         std::unique_ptr<T>>::type
 408 make_unique(size_t n) {
 409   return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]());
 410 }
 411
 412 /// This function isn't used and is only here to provide better compile errors.
 413 template <class T, class... Args>
 414 typename std::enable_if<std::extent<T>::value != 0>::type
 415 make_unique(Args &&...) LLVM_DELETED_FUNCTION;
 416
 417 #else
 418
 419 template <class T>
 420 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 421 make_unique() {
 422   return std::unique_ptr<T>(new T());
 423 }
 424
 425 template <class T, class Arg1>
 426 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 427 make_unique(Arg1 &&arg1) {
 428   return std::unique_ptr<T>(new T(std::forward<Arg1>(arg1)));
 429 }
 430
 431 template <class T, class Arg1, class Arg2>
 432 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 433 make_unique(Arg1 &&arg1, Arg2 &&arg2) {
 434   return std::unique_ptr<T>(
 435       new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2)));
 436 }
 437
 438 template <class T, class Arg1, class Arg2, class Arg3>
 439 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 440 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3) {
 441   return std::unique_ptr<T>(new T(std::forward<Arg1>(arg1),
 442                                   std::forward<Arg2>(arg2),
 443                                   std::forward<Arg3>(arg3)));
 444 }
 445
 446 template <class T, class Arg1, class Arg2, class Arg3, class Arg4>
 447 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 448 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4) {
 449   return std::unique_ptr<T>(
 450       new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
 451             std::forward<Arg3>(arg3), std::forward<Arg4>(arg4)));
 452 }
 453
 454 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5>
 455 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 456 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5) {
 457   return std::unique_ptr<T>(
 458       new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
 459             std::forward<Arg3>(arg3), std::forward<Arg4>(arg4),
 460             std::forward<Arg5>(arg5)));
 461 }
 462
 463 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5,
 464           class Arg6>
 465 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 466 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5,
 467             Arg6 &&arg6) {
 468   return std::unique_ptr<T>(
 469       new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
 470             std::forward<Arg3>(arg3), std::forward<Arg4>(arg4),
 471             std::forward<Arg5>(arg5), std::forward<Arg6>(arg6)));
 472 }
 473
 474 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5,
 475           class Arg6, class Arg7>
 476 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 477 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5,
 478             Arg6 &&arg6, Arg7 &&arg7) {
 479   return std::unique_ptr<T>(
 480       new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
 481             std::forward<Arg3>(arg3), std::forward<Arg4>(arg4),
 482             std::forward<Arg5>(arg5), std::forward<Arg6>(arg6),
 483             std::forward<Arg7>(arg7)));
 484 }
 485
 486 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5,
 487           class Arg6, class Arg7, class Arg8>
 488 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 489 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5,
 490             Arg6 &&arg6, Arg7 &&arg7, Arg8 &&arg8) {
 491   return std::unique_ptr<T>(
 492       new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
 493             std::forward<Arg3>(arg3), std::forward<Arg4>(arg4),
 494             std::forward<Arg5>(arg5), std::forward<Arg6>(arg6),
 495             std::forward<Arg7>(arg7), std::forward<Arg8>(arg8)));
 496 }
 497
 498 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5,
 499           class Arg6, class Arg7, class Arg8, class Arg9>
 500 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 501 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5,
 502             Arg6 &&arg6, Arg7 &&arg7, Arg8 &&arg8, Arg9 &&arg9) {
 503   return std::unique_ptr<T>(
 504       new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
 505             std::forward<Arg3>(arg3), std::forward<Arg4>(arg4),
 506             std::forward<Arg5>(arg5), std::forward<Arg6>(arg6),
 507             std::forward<Arg7>(arg7), std::forward<Arg8>(arg8),
 508             std::forward<Arg9>(arg9)));
 509 }
 510
 511 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5,
 512           class Arg6, class Arg7, class Arg8, class Arg9, class Arg10>
 513 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
 514 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5,
 515             Arg6 &&arg6, Arg7 &&arg7, Arg8 &&arg8, Arg9 &&arg9, Arg10 &&arg10) {
 516   return std::unique_ptr<T>(
 517       new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
 518             std::forward<Arg3>(arg3), std::forward<Arg4>(arg4),
 519             std::forward<Arg5>(arg5), std::forward<Arg6>(arg6),
 520             std::forward<Arg7>(arg7), std::forward<Arg8>(arg8),
 521             std::forward<Arg9>(arg9), std::forward<Arg10>(arg10)));
 522 }
 523
 524 template <class T>
 525 typename std::enable_if<std::is_array<T>::value &&std::extent<T>::value == 0,
 526                         std::unique_ptr<T>>::type
 527 make_unique(size_t n) {
 528   return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]());
 529 }
 530
 531 #endif
 532
 533 } // End llvm namespace
 534
 535 #endif