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