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