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