LLVM  6.0.0svn
STLExtras.h
Go to the documentation of this file.
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 <algorithm> // for std::all_of
21 #include <cassert>
22 #include <cstddef> // for std::size_t
23 #include <cstdlib> // for qsort
24 #include <functional>
25 #include <iterator>
26 #include <limits>
27 #include <memory>
28 #include <tuple>
29 #include <utility> // for std::pair
30 
31 #include "llvm/ADT/Optional.h"
32 #include "llvm/ADT/SmallVector.h"
33 #include "llvm/ADT/iterator.h"
35 #include "llvm/Support/Compiler.h"
37 
38 namespace llvm {
39 
40 // Only used by compiler if both template types are the same. Useful when
41 // using SFINAE to test for the existence of member functions.
42 template <typename T, T> struct SameType;
43 
44 namespace detail {
45 
46 template <typename RangeT>
47 using IterOfRange = decltype(std::begin(std::declval<RangeT &>()));
48 
49 template <typename RangeT>
50 using ValueOfRange = typename std::remove_reference<decltype(
51  *std::begin(std::declval<RangeT &>()))>::type;
52 
53 } // End detail namespace
54 
55 //===----------------------------------------------------------------------===//
56 // Extra additions to <functional>
57 //===----------------------------------------------------------------------===//
58 
59 template<class Ty>
60 struct identity : public std::unary_function<Ty, Ty> {
61  Ty &operator()(Ty &self) const {
62  return self;
63  }
64  const Ty &operator()(const Ty &self) const {
65  return self;
66  }
67 };
68 
69 template<class Ty>
70 struct less_ptr : public std::binary_function<Ty, Ty, bool> {
71  bool operator()(const Ty* left, const Ty* right) const {
72  return *left < *right;
73  }
74 };
75 
76 template<class Ty>
77 struct greater_ptr : public std::binary_function<Ty, Ty, bool> {
78  bool operator()(const Ty* left, const Ty* right) const {
79  return *right < *left;
80  }
81 };
82 
83 /// An efficient, type-erasing, non-owning reference to a callable. This is
84 /// intended for use as the type of a function parameter that is not used
85 /// after the function in question returns.
86 ///
87 /// This class does not own the callable, so it is not in general safe to store
88 /// a function_ref.
89 template<typename Fn> class function_ref;
90 
91 template<typename Ret, typename ...Params>
92 class function_ref<Ret(Params...)> {
93  Ret (*callback)(intptr_t callable, Params ...params);
94  intptr_t callable;
95 
96  template<typename Callable>
97  static Ret callback_fn(intptr_t callable, Params ...params) {
98  return (*reinterpret_cast<Callable*>(callable))(
99  std::forward<Params>(params)...);
100  }
101 
102 public:
103  function_ref() : callback(nullptr) {}
104 
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()(Params ...params) const {
113  return callback(callable, std::forward<Params>(params)...);
114  }
115 
116  operator bool() const { return callback; }
117 };
118 
119 // deleter - Very very very simple method that is used to invoke operator
120 // delete on something. It is used like this:
121 //
122 // for_each(V.begin(), B.end(), deleter<Interval>);
123 //
124 template <class T>
125 inline void deleter(T *Ptr) {
126  delete Ptr;
127 }
128 
129 
130 
131 //===----------------------------------------------------------------------===//
132 // Extra additions to <iterator>
133 //===----------------------------------------------------------------------===//
134 
135 // mapped_iterator - This is a simple iterator adapter that causes a function to
136 // be applied whenever operator* is invoked on the iterator.
137 //
138 template <class RootIt, class UnaryFunc>
140  RootIt current;
141  UnaryFunc Fn;
142 public:
143  typedef typename std::iterator_traits<RootIt>::iterator_category
145  typedef typename std::iterator_traits<RootIt>::difference_type
147  typedef decltype(std::declval<UnaryFunc>()(*std::declval<RootIt>()))
148  value_type;
149 
150  typedef void pointer;
151  //typedef typename UnaryFunc::result_type *pointer;
152  typedef void reference; // Can't modify value returned by fn
153 
154  typedef RootIt iterator_type;
155 
156  inline const RootIt &getCurrent() const { return current; }
157  inline const UnaryFunc &getFunc() const { return Fn; }
158 
159  inline explicit mapped_iterator(const RootIt &I, UnaryFunc F)
160  : current(I), Fn(F) {}
161 
162  inline value_type operator*() const { // All this work to do this
163  return Fn(*current); // little change
164  }
165 
167  ++current;
168  return *this;
169  }
171  --current;
172  return *this;
173  }
175  mapped_iterator __tmp = *this;
176  ++current;
177  return __tmp;
178  }
180  mapped_iterator __tmp = *this;
181  --current;
182  return __tmp;
183  }
185  return mapped_iterator(current + n, Fn);
186  }
188  current += n;
189  return *this;
190  }
192  return mapped_iterator(current - n, Fn);
193  }
195  current -= n;
196  return *this;
197  }
198  reference operator[](difference_type n) const { return *(*this + n); }
199 
200  bool operator!=(const mapped_iterator &X) const { return !operator==(X); }
201  bool operator==(const mapped_iterator &X) const {
202  return current == X.current;
203  }
204  bool operator<(const mapped_iterator &X) const { return current < X.current; }
205 
207  return current - X.current;
208  }
209 };
210 
211 template <class Iterator, class Func>
216 }
217 
218 
219 // map_iterator - Provide a convenient way to create mapped_iterators, just like
220 // make_pair is useful for creating pairs...
221 //
222 template <class ItTy, class FuncTy>
223 inline mapped_iterator<ItTy, FuncTy> map_iterator(const ItTy &I, FuncTy F) {
225 }
226 
227 /// Helper to determine if type T has a member called rbegin().
228 template <typename Ty> class has_rbegin_impl {
229  typedef char yes[1];
230  typedef char no[2];
231 
232  template <typename Inner>
233  static yes& test(Inner *I, decltype(I->rbegin()) * = nullptr);
234 
235  template <typename>
236  static no& test(...);
237 
238 public:
239  static const bool value = sizeof(test<Ty>(nullptr)) == sizeof(yes);
240 };
241 
242 /// Metafunction to determine if T& or T has a member called rbegin().
243 template <typename Ty>
244 struct has_rbegin : has_rbegin_impl<typename std::remove_reference<Ty>::type> {
245 };
246 
247 // Returns an iterator_range over the given container which iterates in reverse.
248 // Note that the container must have rbegin()/rend() methods for this to work.
249 template <typename ContainerTy>
250 auto reverse(ContainerTy &&C,
251  typename std::enable_if<has_rbegin<ContainerTy>::value>::type * =
252  nullptr) -> decltype(make_range(C.rbegin(), C.rend())) {
253  return make_range(C.rbegin(), C.rend());
254 }
255 
256 // Returns a std::reverse_iterator wrapped around the given iterator.
257 template <typename IteratorTy>
258 std::reverse_iterator<IteratorTy> make_reverse_iterator(IteratorTy It) {
259  return std::reverse_iterator<IteratorTy>(It);
260 }
261 
262 // Returns an iterator_range over the given container which iterates in reverse.
263 // Note that the container must have begin()/end() methods which return
264 // bidirectional iterators for this to work.
265 template <typename ContainerTy>
266 auto reverse(
267  ContainerTy &&C,
268  typename std::enable_if<!has_rbegin<ContainerTy>::value>::type * = nullptr)
273 }
274 
275 /// An iterator adaptor that filters the elements of given inner iterators.
276 ///
277 /// The predicate parameter should be a callable object that accepts the wrapped
278 /// iterator's reference type and returns a bool. When incrementing or
279 /// decrementing the iterator, it will call the predicate on each element and
280 /// skip any where it returns false.
281 ///
282 /// \code
283 /// int A[] = { 1, 2, 3, 4 };
284 /// auto R = make_filter_range(A, [](int N) { return N % 2 == 1; });
285 /// // R contains { 1, 3 }.
286 /// \endcode
287 template <typename WrappedIteratorT, typename PredicateT>
289  : public iterator_adaptor_base<
290  filter_iterator<WrappedIteratorT, PredicateT>, WrappedIteratorT,
291  typename std::common_type<
292  std::forward_iterator_tag,
293  typename std::iterator_traits<
294  WrappedIteratorT>::iterator_category>::type> {
297  typename std::common_type<
298  std::forward_iterator_tag,
299  typename std::iterator_traits<WrappedIteratorT>::iterator_category>::
300  type>;
301 
302  struct PayloadType {
303  WrappedIteratorT End;
304  PredicateT Pred;
305  };
306 
307  Optional<PayloadType> Payload;
308 
309  void findNextValid() {
310  assert(Payload && "Payload should be engaged when findNextValid is called");
311  while (this->I != Payload->End && !Payload->Pred(*this->I))
312  BaseT::operator++();
313  }
314 
315  // Construct the begin iterator. The begin iterator requires to know where end
316  // is, so that it can properly stop when it hits end.
317  filter_iterator(WrappedIteratorT Begin, WrappedIteratorT End, PredicateT Pred)
318  : BaseT(std::move(Begin)),
319  Payload(PayloadType{std::move(End), std::move(Pred)}) {
320  findNextValid();
321  }
322 
323  // Construct the end iterator. It's not incrementable, so Payload doesn't
324  // have to be engaged.
325  filter_iterator(WrappedIteratorT End) : BaseT(End) {}
326 
327 public:
328  using BaseT::operator++;
329 
331  BaseT::operator++();
332  findNextValid();
333  return *this;
334  }
335 
336  template <typename RT, typename PT>
338  make_filter_range(RT &&, PT);
339 };
340 
341 /// Convenience function that takes a range of elements and a predicate,
342 /// and return a new filter_iterator range.
343 ///
344 /// FIXME: Currently if RangeT && is a rvalue reference to a temporary, the
345 /// lifetime of that temporary is not kept by the returned range object, and the
346 /// temporary is going to be dropped on the floor after the make_iterator_range
347 /// full expression that contains this function call.
348 template <typename RangeT, typename PredicateT>
350 make_filter_range(RangeT &&Range, PredicateT Pred) {
351  using FilterIteratorT =
353  return make_range(FilterIteratorT(std::begin(std::forward<RangeT>(Range)),
354  std::end(std::forward<RangeT>(Range)),
355  std::move(Pred)),
356  FilterIteratorT(std::end(std::forward<RangeT>(Range))));
357 }
358 
359 // forward declarations required by zip_shortest/zip_first
360 template <typename R, typename UnaryPredicate>
361 bool all_of(R &&range, UnaryPredicate P);
362 
363 template <size_t... I> struct index_sequence;
364 
365 template <class... Ts> struct index_sequence_for;
366 
367 namespace detail {
368 using std::declval;
369 
370 // We have to alias this since inlining the actual type at the usage site
371 // in the parameter list of iterator_facade_base<> below ICEs MSVC 2017.
372 template<typename... Iters> struct ZipTupleType {
373  typedef std::tuple<decltype(*declval<Iters>())...> type;
374 };
375 
376 template <typename ZipType, typename... Iters>
378  ZipType, typename std::common_type<std::bidirectional_iterator_tag,
379  typename std::iterator_traits<
380  Iters>::iterator_category...>::type,
381  // ^ TODO: Implement random access methods.
382  typename ZipTupleType<Iters...>::type,
383  typename std::iterator_traits<typename std::tuple_element<
384  0, std::tuple<Iters...>>::type>::difference_type,
385  // ^ FIXME: This follows boost::make_zip_iterator's assumption that all
386  // inner iterators have the same difference_type. It would fail if, for
387  // instance, the second field's difference_type were non-numeric while the
388  // first is.
389  typename ZipTupleType<Iters...>::type *,
390  typename ZipTupleType<Iters...>::type>;
391 
392 template <typename ZipType, typename... Iters>
393 struct zip_common : public zip_traits<ZipType, Iters...> {
394  using Base = zip_traits<ZipType, Iters...>;
395  using value_type = typename Base::value_type;
396 
397  std::tuple<Iters...> iterators;
398 
399 protected:
400  template <size_t... Ns> value_type deref(index_sequence<Ns...>) const {
401  return value_type(*std::get<Ns>(iterators)...);
402  }
403 
404  template <size_t... Ns>
405  decltype(iterators) tup_inc(index_sequence<Ns...>) const {
406  return std::tuple<Iters...>(std::next(std::get<Ns>(iterators))...);
407  }
408 
409  template <size_t... Ns>
410  decltype(iterators) tup_dec(index_sequence<Ns...>) const {
411  return std::tuple<Iters...>(std::prev(std::get<Ns>(iterators))...);
412  }
413 
414 public:
415  zip_common(Iters &&... ts) : iterators(std::forward<Iters>(ts)...) {}
416 
418 
419  const value_type operator*() const {
421  }
422 
423  ZipType &operator++() {
424  iterators = tup_inc(index_sequence_for<Iters...>{});
425  return *reinterpret_cast<ZipType *>(this);
426  }
427 
428  ZipType &operator--() {
429  static_assert(Base::IsBidirectional,
430  "All inner iterators must be at least bidirectional.");
431  iterators = tup_dec(index_sequence_for<Iters...>{});
432  return *reinterpret_cast<ZipType *>(this);
433  }
434 };
435 
436 template <typename... Iters>
437 struct zip_first : public zip_common<zip_first<Iters...>, Iters...> {
438  using Base = zip_common<zip_first<Iters...>, Iters...>;
439 
440  bool operator==(const zip_first<Iters...> &other) const {
441  return std::get<0>(this->iterators) == std::get<0>(other.iterators);
442  }
443 
444  zip_first(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
445 };
446 
447 template <typename... Iters>
448 class zip_shortest : public zip_common<zip_shortest<Iters...>, Iters...> {
449  template <size_t... Ns>
450  bool test(const zip_shortest<Iters...> &other, index_sequence<Ns...>) const {
451  return all_of(std::initializer_list<bool>{std::get<Ns>(this->iterators) !=
452  std::get<Ns>(other.iterators)...},
453  identity<bool>{});
454  }
455 
456 public:
457  using Base = zip_common<zip_shortest<Iters...>, Iters...>;
458 
459  bool operator==(const zip_shortest<Iters...> &other) const {
460  return !test(other, index_sequence_for<Iters...>{});
461  }
462 
463  zip_shortest(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
464 };
465 
466 template <template <typename...> class ItType, typename... Args> class zippy {
467 public:
468  using iterator = ItType<decltype(std::begin(std::declval<Args>()))...>;
469  using iterator_category = typename iterator::iterator_category;
470  using value_type = typename iterator::value_type;
471  using difference_type = typename iterator::difference_type;
472  using pointer = typename iterator::pointer;
473  using reference = typename iterator::reference;
474 
475 private:
476  std::tuple<Args...> ts;
477 
478  template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) const {
479  return iterator(std::begin(std::get<Ns>(ts))...);
480  }
481  template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) const {
482  return iterator(std::end(std::get<Ns>(ts))...);
483  }
484 
485 public:
486  iterator begin() const { return begin_impl(index_sequence_for<Args...>{}); }
487  iterator end() const { return end_impl(index_sequence_for<Args...>{}); }
488  zippy(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {}
489 };
490 } // End detail namespace
491 
492 /// zip iterator for two or more iteratable types.
493 template <typename T, typename U, typename... Args>
495  Args &&... args) {
496  return detail::zippy<detail::zip_shortest, T, U, Args...>(
497  std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
498 }
499 
500 /// zip iterator that, for the sake of efficiency, assumes the first iteratee to
501 /// be the shortest.
502 template <typename T, typename U, typename... Args>
504  Args &&... args) {
505  return detail::zippy<detail::zip_first, T, U, Args...>(
506  std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
507 }
508 
509 /// Iterator wrapper that concatenates sequences together.
510 ///
511 /// This can concatenate different iterators, even with different types, into
512 /// a single iterator provided the value types of all the concatenated
513 /// iterators expose `reference` and `pointer` types that can be converted to
514 /// `ValueT &` and `ValueT *` respectively. It doesn't support more
515 /// interesting/customized pointer or reference types.
516 ///
517 /// Currently this only supports forward or higher iterator categories as
518 /// inputs and always exposes a forward iterator interface.
519 template <typename ValueT, typename... IterTs>
521  : public iterator_facade_base<concat_iterator<ValueT, IterTs...>,
522  std::forward_iterator_tag, ValueT> {
523  typedef typename concat_iterator::iterator_facade_base BaseT;
524 
525  /// We store both the current and end iterators for each concatenated
526  /// sequence in a tuple of pairs.
527  ///
528  /// Note that something like iterator_range seems nice at first here, but the
529  /// range properties are of little benefit and end up getting in the way
530  /// because we need to do mutation on the current iterators.
531  std::tuple<std::pair<IterTs, IterTs>...> IterPairs;
532 
533  /// Attempts to increment a specific iterator.
534  ///
535  /// Returns true if it was able to increment the iterator. Returns false if
536  /// the iterator is already at the end iterator.
537  template <size_t Index> bool incrementHelper() {
538  auto &IterPair = std::get<Index>(IterPairs);
539  if (IterPair.first == IterPair.second)
540  return false;
541 
542  ++IterPair.first;
543  return true;
544  }
545 
546  /// Increments the first non-end iterator.
547  ///
548  /// It is an error to call this with all iterators at the end.
549  template <size_t... Ns> void increment(index_sequence<Ns...>) {
550  // Build a sequence of functions to increment each iterator if possible.
551  bool (concat_iterator::*IncrementHelperFns[])() = {
552  &concat_iterator::incrementHelper<Ns>...};
553 
554  // Loop over them, and stop as soon as we succeed at incrementing one.
555  for (auto &IncrementHelperFn : IncrementHelperFns)
556  if ((this->*IncrementHelperFn)())
557  return;
558 
559  llvm_unreachable("Attempted to increment an end concat iterator!");
560  }
561 
562  /// Returns null if the specified iterator is at the end. Otherwise,
563  /// dereferences the iterator and returns the address of the resulting
564  /// reference.
565  template <size_t Index> ValueT *getHelper() const {
566  auto &IterPair = std::get<Index>(IterPairs);
567  if (IterPair.first == IterPair.second)
568  return nullptr;
569 
570  return &*IterPair.first;
571  }
572 
573  /// Finds the first non-end iterator, dereferences, and returns the resulting
574  /// reference.
575  ///
576  /// It is an error to call this with all iterators at the end.
577  template <size_t... Ns> ValueT &get(index_sequence<Ns...>) const {
578  // Build a sequence of functions to get from iterator if possible.
579  ValueT *(concat_iterator::*GetHelperFns[])() const = {
580  &concat_iterator::getHelper<Ns>...};
581 
582  // Loop over them, and return the first result we find.
583  for (auto &GetHelperFn : GetHelperFns)
584  if (ValueT *P = (this->*GetHelperFn)())
585  return *P;
586 
587  llvm_unreachable("Attempted to get a pointer from an end concat iterator!");
588  }
589 
590 public:
591  /// Constructs an iterator from a squence of ranges.
592  ///
593  /// We need the full range to know how to switch between each of the
594  /// iterators.
595  template <typename... RangeTs>
596  explicit concat_iterator(RangeTs &&... Ranges)
597  : IterPairs({std::begin(Ranges), std::end(Ranges)}...) {}
598 
599  using BaseT::operator++;
601  increment(index_sequence_for<IterTs...>());
602  return *this;
603  }
604 
605  ValueT &operator*() const { return get(index_sequence_for<IterTs...>()); }
606 
607  bool operator==(const concat_iterator &RHS) const {
608  return IterPairs == RHS.IterPairs;
609  }
610 };
611 
612 namespace detail {
613 /// Helper to store a sequence of ranges being concatenated and access them.
614 ///
615 /// This is designed to facilitate providing actual storage when temporaries
616 /// are passed into the constructor such that we can use it as part of range
617 /// based for loops.
618 template <typename ValueT, typename... RangeTs> class concat_range {
619 public:
620  typedef concat_iterator<ValueT,
621  decltype(std::begin(std::declval<RangeTs &>()))...>
623 
624 private:
625  std::tuple<RangeTs...> Ranges;
626 
627  template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) {
628  return iterator(std::get<Ns>(Ranges)...);
629  }
630  template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) {
631  return iterator(make_range(std::end(std::get<Ns>(Ranges)),
632  std::end(std::get<Ns>(Ranges)))...);
633  }
634 
635 public:
636  iterator begin() { return begin_impl(index_sequence_for<RangeTs...>{}); }
637  iterator end() { return end_impl(index_sequence_for<RangeTs...>{}); }
638  concat_range(RangeTs &&... Ranges)
639  : Ranges(std::forward<RangeTs>(Ranges)...) {}
640 };
641 }
642 
643 /// Concatenated range across two or more ranges.
644 ///
645 /// The desired value type must be explicitly specified.
646 template <typename ValueT, typename... RangeTs>
647 detail::concat_range<ValueT, RangeTs...> concat(RangeTs &&... Ranges) {
648  static_assert(sizeof...(RangeTs) > 1,
649  "Need more than one range to concatenate!");
650  return detail::concat_range<ValueT, RangeTs...>(
651  std::forward<RangeTs>(Ranges)...);
652 }
653 
654 //===----------------------------------------------------------------------===//
655 // Extra additions to <utility>
656 //===----------------------------------------------------------------------===//
657 
658 /// \brief Function object to check whether the first component of a std::pair
659 /// compares less than the first component of another std::pair.
660 struct less_first {
661  template <typename T> bool operator()(const T &lhs, const T &rhs) const {
662  return lhs.first < rhs.first;
663  }
664 };
665 
666 /// \brief Function object to check whether the second component of a std::pair
667 /// compares less than the second component of another std::pair.
668 struct less_second {
669  template <typename T> bool operator()(const T &lhs, const T &rhs) const {
670  return lhs.second < rhs.second;
671  }
672 };
673 
674 // A subset of N3658. More stuff can be added as-needed.
675 
676 /// \brief Represents a compile-time sequence of integers.
677 template <class T, T... I> struct integer_sequence {
678  typedef T value_type;
679 
680  static constexpr size_t size() { return sizeof...(I); }
681 };
682 
683 /// \brief Alias for the common case of a sequence of size_ts.
684 template <size_t... I>
685 struct index_sequence : integer_sequence<std::size_t, I...> {};
686 
687 template <std::size_t N, std::size_t... I>
688 struct build_index_impl : build_index_impl<N - 1, N - 1, I...> {};
689 template <std::size_t... I>
690 struct build_index_impl<0, I...> : index_sequence<I...> {};
691 
692 /// \brief Creates a compile-time integer sequence for a parameter pack.
693 template <class... Ts>
694 struct index_sequence_for : build_index_impl<sizeof...(Ts)> {};
695 
696 /// Utility type to build an inheritance chain that makes it easy to rank
697 /// overload candidates.
698 template <int N> struct rank : rank<N - 1> {};
699 template <> struct rank<0> {};
700 
701 /// \brief traits class for checking whether type T is one of any of the given
702 /// types in the variadic list.
703 template <typename T, typename... Ts> struct is_one_of {
704  static const bool value = false;
705 };
706 
707 template <typename T, typename U, typename... Ts>
708 struct is_one_of<T, U, Ts...> {
709  static const bool value =
710  std::is_same<T, U>::value || is_one_of<T, Ts...>::value;
711 };
712 
713 /// \brief traits class for checking whether type T is a base class for all
714 /// the given types in the variadic list.
715 template <typename T, typename... Ts> struct are_base_of {
716  static const bool value = true;
717 };
718 
719 template <typename T, typename U, typename... Ts>
720 struct are_base_of<T, U, Ts...> {
721  static const bool value =
722  std::is_base_of<T, U>::value && are_base_of<T, Ts...>::value;
723 };
724 
725 //===----------------------------------------------------------------------===//
726 // Extra additions for arrays
727 //===----------------------------------------------------------------------===//
728 
729 /// Find the length of an array.
730 template <class T, std::size_t N>
731 constexpr inline size_t array_lengthof(T (&)[N]) {
732  return N;
733 }
734 
735 /// Adapt std::less<T> for array_pod_sort.
736 template<typename T>
737 inline int array_pod_sort_comparator(const void *P1, const void *P2) {
738  if (std::less<T>()(*reinterpret_cast<const T*>(P1),
739  *reinterpret_cast<const T*>(P2)))
740  return -1;
741  if (std::less<T>()(*reinterpret_cast<const T*>(P2),
742  *reinterpret_cast<const T*>(P1)))
743  return 1;
744  return 0;
745 }
746 
747 /// get_array_pod_sort_comparator - This is an internal helper function used to
748 /// get type deduction of T right.
749 template<typename T>
750 inline int (*get_array_pod_sort_comparator(const T &))
751  (const void*, const void*) {
752  return array_pod_sort_comparator<T>;
753 }
754 
755 
756 /// array_pod_sort - This sorts an array with the specified start and end
757 /// extent. This is just like std::sort, except that it calls qsort instead of
758 /// using an inlined template. qsort is slightly slower than std::sort, but
759 /// most sorts are not performance critical in LLVM and std::sort has to be
760 /// template instantiated for each type, leading to significant measured code
761 /// bloat. This function should generally be used instead of std::sort where
762 /// possible.
763 ///
764 /// This function assumes that you have simple POD-like types that can be
765 /// compared with std::less and can be moved with memcpy. If this isn't true,
766 /// you should use std::sort.
767 ///
768 /// NOTE: If qsort_r were portable, we could allow a custom comparator and
769 /// default to std::less.
770 template<class IteratorTy>
771 inline void array_pod_sort(IteratorTy Start, IteratorTy End) {
772  // Don't inefficiently call qsort with one element or trigger undefined
773  // behavior with an empty sequence.
774  auto NElts = End - Start;
775  if (NElts <= 1) return;
776  qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start));
777 }
778 
779 template <class IteratorTy>
780 inline void array_pod_sort(
781  IteratorTy Start, IteratorTy End,
782  int (*Compare)(
783  const typename std::iterator_traits<IteratorTy>::value_type *,
784  const typename std::iterator_traits<IteratorTy>::value_type *)) {
785  // Don't inefficiently call qsort with one element or trigger undefined
786  // behavior with an empty sequence.
787  auto NElts = End - Start;
788  if (NElts <= 1) return;
789  qsort(&*Start, NElts, sizeof(*Start),
790  reinterpret_cast<int (*)(const void *, const void *)>(Compare));
791 }
792 
793 //===----------------------------------------------------------------------===//
794 // Extra additions to <algorithm>
795 //===----------------------------------------------------------------------===//
796 
797 /// For a container of pointers, deletes the pointers and then clears the
798 /// container.
799 template<typename Container>
800 void DeleteContainerPointers(Container &C) {
801  for (auto V : C)
802  delete V;
803  C.clear();
804 }
805 
806 /// In a container of pairs (usually a map) whose second element is a pointer,
807 /// deletes the second elements and then clears the container.
808 template<typename Container>
809 void DeleteContainerSeconds(Container &C) {
810  for (auto &V : C)
811  delete V.second;
812  C.clear();
813 }
814 
815 /// Provide wrappers to std::all_of which take ranges instead of having to pass
816 /// begin/end explicitly.
817 template <typename R, typename UnaryPredicate>
818 bool all_of(R &&Range, UnaryPredicate P) {
819  return std::all_of(std::begin(Range), std::end(Range), P);
820 }
821 
822 /// Provide wrappers to std::any_of which take ranges instead of having to pass
823 /// begin/end explicitly.
824 template <typename R, typename UnaryPredicate>
825 bool any_of(R &&Range, UnaryPredicate P) {
826  return std::any_of(std::begin(Range), std::end(Range), P);
827 }
828 
829 /// Provide wrappers to std::none_of which take ranges instead of having to pass
830 /// begin/end explicitly.
831 template <typename R, typename UnaryPredicate>
832 bool none_of(R &&Range, UnaryPredicate P) {
833  return std::none_of(std::begin(Range), std::end(Range), P);
834 }
835 
836 /// Provide wrappers to std::find which take ranges instead of having to pass
837 /// begin/end explicitly.
838 template <typename R, typename T>
839 auto find(R &&Range, const T &Val) -> decltype(std::begin(Range)) {
840  return std::find(std::begin(Range), std::end(Range), Val);
841 }
842 
843 /// Provide wrappers to std::find_if which take ranges instead of having to pass
844 /// begin/end explicitly.
845 template <typename R, typename UnaryPredicate>
846 auto find_if(R &&Range, UnaryPredicate P) -> decltype(std::begin(Range)) {
847  return std::find_if(std::begin(Range), std::end(Range), P);
848 }
849 
850 template <typename R, typename UnaryPredicate>
851 auto find_if_not(R &&Range, UnaryPredicate P) -> decltype(std::begin(Range)) {
852  return std::find_if_not(std::begin(Range), std::end(Range), P);
853 }
854 
855 /// Provide wrappers to std::remove_if which take ranges instead of having to
856 /// pass begin/end explicitly.
857 template <typename R, typename UnaryPredicate>
858 auto remove_if(R &&Range, UnaryPredicate P) -> decltype(std::begin(Range)) {
859  return std::remove_if(std::begin(Range), std::end(Range), P);
860 }
861 
862 /// Provide wrappers to std::copy_if which take ranges instead of having to
863 /// pass begin/end explicitly.
864 template <typename R, typename OutputIt, typename UnaryPredicate>
865 OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P) {
866  return std::copy_if(std::begin(Range), std::end(Range), Out, P);
867 }
868 
869 /// Wrapper function around std::find to detect if an element exists
870 /// in a container.
871 template <typename R, typename E>
872 bool is_contained(R &&Range, const E &Element) {
873  return std::find(std::begin(Range), std::end(Range), Element) !=
874  std::end(Range);
875 }
876 
877 /// Wrapper function around std::count to count the number of times an element
878 /// \p Element occurs in the given range \p Range.
879 template <typename R, typename E>
880 auto count(R &&Range, const E &Element) -> typename std::iterator_traits<
881  decltype(std::begin(Range))>::difference_type {
882  return std::count(std::begin(Range), std::end(Range), Element);
883 }
884 
885 /// Wrapper function around std::count_if to count the number of times an
886 /// element satisfying a given predicate occurs in a range.
887 template <typename R, typename UnaryPredicate>
888 auto count_if(R &&Range, UnaryPredicate P) -> typename std::iterator_traits<
889  decltype(std::begin(Range))>::difference_type {
890  return std::count_if(std::begin(Range), std::end(Range), P);
891 }
892 
893 /// Wrapper function around std::transform to apply a function to a range and
894 /// store the result elsewhere.
895 template <typename R, typename OutputIt, typename UnaryPredicate>
896 OutputIt transform(R &&Range, OutputIt d_first, UnaryPredicate P) {
897  return std::transform(std::begin(Range), std::end(Range), d_first, P);
898 }
899 
900 /// Provide wrappers to std::partition which take ranges instead of having to
901 /// pass begin/end explicitly.
902 template <typename R, typename UnaryPredicate>
903 auto partition(R &&Range, UnaryPredicate P) -> decltype(std::begin(Range)) {
904  return std::partition(std::begin(Range), std::end(Range), P);
905 }
906 
907 /// \brief Given a range of type R, iterate the entire range and return a
908 /// SmallVector with elements of the vector. This is useful, for example,
909 /// when you want to iterate a range and then sort the results.
910 template <unsigned Size, typename R>
912 to_vector(R &&Range) {
913  return {std::begin(Range), std::end(Range)};
914 }
915 
916 /// Provide a container algorithm similar to C++ Library Fundamentals v2's
917 /// `erase_if` which is equivalent to:
918 ///
919 /// C.erase(remove_if(C, pred), C.end());
920 ///
921 /// This version works for any container with an erase method call accepting
922 /// two iterators.
923 template <typename Container, typename UnaryPredicate>
924 void erase_if(Container &C, UnaryPredicate P) {
925  C.erase(remove_if(C, P), C.end());
926 }
927 
928 //===----------------------------------------------------------------------===//
929 // Extra additions to <memory>
930 //===----------------------------------------------------------------------===//
931 
932 // Implement make_unique according to N3656.
933 
934 /// \brief Constructs a `new T()` with the given args and returns a
935 /// `unique_ptr<T>` which owns the object.
936 ///
937 /// Example:
938 ///
939 /// auto p = make_unique<int>();
940 /// auto p = make_unique<std::tuple<int, int>>(0, 1);
941 template <class T, class... Args>
942 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
943 make_unique(Args &&... args) {
944  return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
945 }
946 
947 /// \brief Constructs a `new T[n]` with the given args and returns a
948 /// `unique_ptr<T[]>` which owns the object.
949 ///
950 /// \param n size of the new array.
951 ///
952 /// Example:
953 ///
954 /// auto p = make_unique<int[]>(2); // value-initializes the array with 0's.
955 template <class T>
956 typename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0,
957  std::unique_ptr<T>>::type
958 make_unique(size_t n) {
959  return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]());
960 }
961 
962 /// This function isn't used and is only here to provide better compile errors.
963 template <class T, class... Args>
964 typename std::enable_if<std::extent<T>::value != 0>::type
965 make_unique(Args &&...) = delete;
966 
967 struct FreeDeleter {
968  void operator()(void* v) {
969  ::free(v);
970  }
971 };
972 
973 template<typename First, typename Second>
974 struct pair_hash {
975  size_t operator()(const std::pair<First, Second> &P) const {
976  return std::hash<First>()(P.first) * 31 + std::hash<Second>()(P.second);
977  }
978 };
979 
980 /// A functor like C++14's std::less<void> in its absence.
981 struct less {
982  template <typename A, typename B> bool operator()(A &&a, B &&b) const {
983  return std::forward<A>(a) < std::forward<B>(b);
984  }
985 };
986 
987 /// A functor like C++14's std::equal<void> in its absence.
988 struct equal {
989  template <typename A, typename B> bool operator()(A &&a, B &&b) const {
990  return std::forward<A>(a) == std::forward<B>(b);
991  }
992 };
993 
994 /// Binary functor that adapts to any other binary functor after dereferencing
995 /// operands.
996 template <typename T> struct deref {
997  T func;
998  // Could be further improved to cope with non-derivable functors and
999  // non-binary functors (should be a variadic template member function
1000  // operator()).
1001  template <typename A, typename B>
1002  auto operator()(A &lhs, B &rhs) const -> decltype(func(*lhs, *rhs)) {
1003  assert(lhs);
1004  assert(rhs);
1005  return func(*lhs, *rhs);
1006  }
1007 };
1008 
1009 namespace detail {
1010 template <typename R> class enumerator_iter;
1011 
1012 template <typename R> struct result_pair {
1013  friend class enumerator_iter<R>;
1014 
1015  result_pair() : Index(-1) {}
1016  result_pair(std::size_t Index, IterOfRange<R> Iter)
1017  : Index(Index), Iter(Iter) {}
1018 
1020  Index = Other.Index;
1021  Iter = Other.Iter;
1022  return *this;
1023  }
1024 
1025  std::size_t index() const { return Index; }
1026  const ValueOfRange<R> &value() const { return *Iter; }
1027  ValueOfRange<R> &value() { return *Iter; }
1028 
1029 private:
1030  std::size_t Index;
1031  IterOfRange<R> Iter;
1032 };
1033 
1034 template <typename R>
1035 class enumerator_iter
1036  : public iterator_facade_base<
1037  enumerator_iter<R>, std::forward_iterator_tag, result_pair<R>,
1038  typename std::iterator_traits<IterOfRange<R>>::difference_type,
1039  typename std::iterator_traits<IterOfRange<R>>::pointer,
1040  typename std::iterator_traits<IterOfRange<R>>::reference> {
1041  using result_type = result_pair<R>;
1042 
1043 public:
1045  : Result(std::numeric_limits<size_t>::max(), EndIter) { }
1046 
1047  enumerator_iter(std::size_t Index, IterOfRange<R> Iter)
1048  : Result(Index, Iter) {}
1049 
1050  result_type &operator*() { return Result; }
1051  const result_type &operator*() const { return Result; }
1052 
1054  assert(Result.Index != std::numeric_limits<size_t>::max());
1055  ++Result.Iter;
1056  ++Result.Index;
1057  return *this;
1058  }
1059 
1060  bool operator==(const enumerator_iter<R> &RHS) const {
1061  // Don't compare indices here, only iterators. It's possible for an end
1062  // iterator to have different indices depending on whether it was created
1063  // by calling std::end() versus incrementing a valid iterator.
1064  return Result.Iter == RHS.Result.Iter;
1065  }
1066 
1068  Result = Other.Result;
1069  return *this;
1070  }
1071 
1072 private:
1073  result_type Result;
1074 };
1075 
1076 template <typename R> class enumerator {
1077 public:
1078  explicit enumerator(R &&Range) : TheRange(std::forward<R>(Range)) {}
1079 
1081  return enumerator_iter<R>(0, std::begin(TheRange));
1082  }
1084  return enumerator_iter<R>(std::end(TheRange));
1085  }
1086 
1087 private:
1088  R TheRange;
1089 };
1090 }
1091 
1092 /// Given an input range, returns a new range whose values are are pair (A,B)
1093 /// such that A is the 0-based index of the item in the sequence, and B is
1094 /// the value from the original sequence. Example:
1095 ///
1096 /// std::vector<char> Items = {'A', 'B', 'C', 'D'};
1097 /// for (auto X : enumerate(Items)) {
1098 /// printf("Item %d - %c\n", X.index(), X.value());
1099 /// }
1100 ///
1101 /// Output:
1102 /// Item 0 - A
1103 /// Item 1 - B
1104 /// Item 2 - C
1105 /// Item 3 - D
1106 ///
1107 template <typename R> detail::enumerator<R> enumerate(R &&TheRange) {
1108  return detail::enumerator<R>(std::forward<R>(TheRange));
1109 }
1110 
1111 namespace detail {
1112 template <typename F, typename Tuple, std::size_t... I>
1114  -> decltype(std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...)) {
1115  return std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...);
1116 }
1117 }
1118 
1119 /// Given an input tuple (a1, a2, ..., an), pass the arguments of the
1120 /// tuple variadically to f as if by calling f(a1, a2, ..., an) and
1121 /// return the result.
1122 template <typename F, typename Tuple>
1123 auto apply_tuple(F &&f, Tuple &&t) -> decltype(detail::apply_tuple_impl(
1124  std::forward<F>(f), std::forward<Tuple>(t),
1126  std::tuple_size<typename std::decay<Tuple>::type>::value>{})) {
1127  using Indices = build_index_impl<
1128  std::tuple_size<typename std::decay<Tuple>::type>::value>;
1129 
1130  return detail::apply_tuple_impl(std::forward<F>(f), std::forward<Tuple>(t),
1131  Indices{});
1132 }
1133 } // End llvm namespace
1134 
1135 #endif
detail::concat_range< ValueT, RangeTs... > concat(RangeTs &&... Ranges)
Concatenated range across two or more ranges.
Definition: STLExtras.h:647
result_pair(std::size_t Index, IterOfRange< R > Iter)
Definition: STLExtras.h:1016
void DeleteContainerSeconds(Container &C)
In a container of pairs (usually a map) whose second element is a pointer, deletes the second element...
Definition: STLExtras.h:809
uint64_t CallInst * C
void DeleteContainerPointers(Container &C)
For a container of pointers, deletes the pointers and then clears the container.
Definition: STLExtras.h:800
bool operator()(const Ty *left, const Ty *right) const
Definition: STLExtras.h:78
ZipType & operator++()
Definition: STLExtras.h:423
bool operator==(const enumerator_iter< R > &RHS) const
Definition: STLExtras.h:1060
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:243
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
zippy(Args &&... ts_)
Definition: STLExtras.h:488
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
Ret operator()(Params ...params) const
Definition: STLExtras.h:112
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:234
bool operator()(const T &lhs, const T &rhs) const
Definition: STLExtras.h:661
APInt operator+(APInt a, const APInt &b)
Definition: APInt.h:2028
value_type operator*() const
Definition: STLExtras.h:162
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
typename std::remove_reference< decltype(*std::begin(std::declval< RangeT & >()))>::type ValueOfRange
Definition: STLExtras.h:51
decltype(iterators) tup_inc(index_sequence< Ns... >) const
Definition: STLExtras.h:405
Function object to check whether the second component of a std::pair compares less than the second co...
Definition: STLExtras.h:668
OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P)
Provide wrappers to std::copy_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:865
auto remove_if(R &&Range, UnaryPredicate P) -> decltype(std::begin(Range))
Provide wrappers to std::remove_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:858
typename iterator::value_type value_type
Definition: STLExtras.h:470
const Ty & operator()(const Ty &self) const
Definition: STLExtras.h:64
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
int(*)(const void *, const void *) get_array_pod_sort_comparator(const T &)
get_array_pod_sort_comparator - This is an internal helper function used to get type deduction of T r...
Definition: STLExtras.h:750
bool operator()(const T &lhs, const T &rhs) const
Definition: STLExtras.h:669
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:89
A functor like C++14&#39;s std::less<void> in its absence.
Definition: STLExtras.h:981
zip_common(Iters &&... ts)
Definition: STLExtras.h:415
enumerator_iter(IterOfRange< R > EndIter)
Definition: STLExtras.h:1044
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:818
filter_iterator & operator++()
Definition: STLExtras.h:330
std::enable_if<!std::is_array< T >::value, std::unique_ptr< T > >::type make_unique(Args &&... args)
Constructs a new T() with the given args and returns a unique_ptr<T> which owns the object...
Definition: STLExtras.h:943
mapped_iterator operator-(difference_type n) const
Definition: STLExtras.h:191
typename iterator::pointer pointer
Definition: STLExtras.h:472
int array_pod_sort_comparator(const void *P1, const void *P2)
Adapt std::less<T> for array_pod_sort.
Definition: STLExtras.h:737
Metafunction to determine if T& or T has a member called rbegin().
Definition: STLExtras.h:244
function_ref(Callable &&callable, typename std::enable_if< !std::is_same< typename std::remove_reference< Callable >::type, function_ref >::value >::type *=nullptr)
Definition: STLExtras.h:106
mapped_iterator(const RootIt &I, UnaryFunc F)
Definition: STLExtras.h:159
Ty & operator()(Ty &self) const
Definition: STLExtras.h:61
Definition: BitVector.h:920
concat_range(RangeTs &&... Ranges)
Definition: STLExtras.h:638
static F t[256]
void operator()(void *v)
Definition: STLExtras.h:968
auto find_if_not(R &&Range, UnaryPredicate P) -> decltype(std::begin(Range))
Definition: STLExtras.h:851
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:832
decltype(iterators) tup_dec(index_sequence< Ns... >) const
Definition: STLExtras.h:410
SmallVector< typename std::remove_const< detail::ValueOfRange< R > >::type, Size > to_vector(R &&Range)
Given a range of type R, iterate the entire range and return a SmallVector with elements of the vecto...
Definition: STLExtras.h:912
Alias for the common case of a sequence of size_ts.
Definition: STLExtras.h:363
mapped_iterator< ItTy, FuncTy > map_iterator(const ItTy &I, FuncTy F)
Definition: STLExtras.h:223
ELFYAML::ELF_STO Other
Definition: ELFYAML.cpp:695
std::iterator_traits< RootIt >::iterator_category iterator_category
Definition: STLExtras.h:144
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:250
bool operator()(const Ty *left, const Ty *right) const
Definition: STLExtras.h:71
#define F(x, y, z)
Definition: MD5.cpp:55
mapped_iterator & operator--()
Definition: STLExtras.h:170
#define T
enumerator_iter< R > & operator++()
Definition: STLExtras.h:1053
auto apply_tuple(F &&f, Tuple &&t) -> decltype(detail::apply_tuple_impl(std::forward< F >(f), std::forward< Tuple >(t), build_index_impl< std::tuple_size< typename std::decay< Tuple >::type >::value >
Given an input tuple (a1, a2, ..., an), pass the arguments of the tuple variadically to f as if by ca...
Definition: STLExtras.h:1123
auto count(R &&Range, const E &Element) -> typename std::iterator_traits< decltype(std::begin(Range))>::difference_type
Wrapper function around std::count to count the number of times an element Element occurs in the give...
Definition: STLExtras.h:880
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
Definition: iterator.h:68
enumerator_iter(std::size_t Index, IterOfRange< R > Iter)
Definition: STLExtras.h:1047
Helper to store a sequence of ranges being concatenated and access them.
Definition: STLExtras.h:618
traits class for checking whether type T is one of any of the given types in the variadic list...
Definition: STLExtras.h:703
ValueOfRange< R > & value()
Definition: STLExtras.h:1027
typename iterator::reference reference
Definition: STLExtras.h:473
#define P(N)
ItType< decltype(std::begin(std::declval< Args >()))... > iterator
Definition: STLExtras.h:468
std::iterator_traits< RootIt >::difference_type difference_type
Definition: STLExtras.h:146
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
Definition: STLExtras.h:771
const RootIt & getCurrent() const
Definition: STLExtras.h:156
auto operator()(A &lhs, B &rhs) const -> decltype(func(*lhs, *rhs))
Definition: STLExtras.h:1002
ZipType & operator--()
Definition: STLExtras.h:428
An iterator adaptor that filters the elements of given inner iterators.
Definition: STLExtras.h:288
CRTP base class for adapting an iterator to a different type.
Definition: iterator.h:208
bool operator<(const mapped_iterator &X) const
Definition: STLExtras.h:204
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&... args)
zip iterator for two or more iteratable types.
Definition: STLExtras.h:494
mapped_iterator & operator++()
Definition: STLExtras.h:166
const result_type & operator*() const
Definition: STLExtras.h:1051
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
#define A
Definition: LargeTest.cpp:12
Helper to determine if type T has a member called rbegin().
Definition: STLExtras.h:228
bool any_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:825
static const unsigned End
mapped_iterator operator++(int)
Definition: STLExtras.h:174
detail::zippy< detail::zip_first, T, U, Args... > zip_first(T &&t, U &&u, Args &&... args)
zip iterator that, for the sake of efficiency, assumes the first iteratee to be the shortest...
Definition: STLExtras.h:503
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
static constexpr size_t size()
Definition: STLExtras.h:680
iterator end() const
Definition: STLExtras.h:487
bool operator()(A &&a, B &&b) const
Definition: STLExtras.h:982
auto apply_tuple_impl(F &&f, Tuple &&t, index_sequence< I... >) -> decltype(std::forward< F >(f)(std::get< I >(std::forward< Tuple >(t))...))
Definition: STLExtras.h:1113
A functor like C++14&#39;s std::equal<void> in its absence.
Definition: STLExtras.h:988
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
#define E
Definition: LargeTest.cpp:27
value_type deref(index_sequence< Ns... >) const
Definition: STLExtras.h:400
auto find(R &&Range, const T &Val) -> decltype(std::begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:839
#define B
Definition: LargeTest.cpp:24
mapped_iterator operator+(difference_type n) const
Definition: STLExtras.h:184
mapped_iterator & operator+=(difference_type n)
Definition: STLExtras.h:187
difference_type operator-(const mapped_iterator &X) const
Definition: STLExtras.h:206
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
constexpr size_t array_lengthof(T(&)[N])
Find the length of an array.
Definition: STLExtras.h:731
always inline
Creates a compile-time integer sequence for a parameter pack.
Definition: STLExtras.h:365
const size_t N
typename iterator::difference_type difference_type
Definition: STLExtras.h:471
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2&#39;s erase_if which is equivalent t...
Definition: STLExtras.h:924
A range adaptor for a pair of iterators.
bool operator()(A &&a, B &&b) const
Definition: STLExtras.h:989
Represents a compile-time sequence of integers.
Definition: STLExtras.h:677
constexpr char Size[]
Key for Kernel::Arg::Metadata::mSize.
enumerator_iter< R > & operator=(const enumerator_iter< R > &Other)
Definition: STLExtras.h:1067
concat_iterator & operator++()
Definition: STLExtras.h:600
mapped_iterator operator--(int)
Definition: STLExtras.h:179
bool operator!=(const mapped_iterator &X) const
Definition: STLExtras.h:200
result_pair< R > & operator=(const result_pair< R > &Other)
Definition: STLExtras.h:1019
ValueT & operator*() const
Definition: STLExtras.h:605
auto partition(R &&Range, UnaryPredicate P) -> decltype(std::begin(Range))
Provide wrappers to std::partition which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:903
bool operator==(const zip_first< Iters... > &other) const
Definition: STLExtras.h:440
#define I(x, y, z)
Definition: MD5.cpp:58
bool operator==(const concat_iterator &RHS) const
Definition: STLExtras.h:607
typename iterator::iterator_category iterator_category
Definition: STLExtras.h:469
value_type operator*()
Definition: STLExtras.h:417
decltype(std::begin(std::declval< RangeT & >())) IterOfRange
Definition: STLExtras.h:47
const ValueOfRange< R > & value() const
Definition: STLExtras.h:1026
iterator_range< filter_iterator< detail::IterOfRange< RangeT >, PredicateT > > make_filter_range(RangeT &&Range, PredicateT Pred)
Convenience function that takes a range of elements and a predicate, and return a new filter_iterator...
Definition: STLExtras.h:350
std::tuple< Iters... > iterators
Definition: STLExtras.h:397
OutputIt transform(R &&Range, OutputIt d_first, UnaryPredicate P)
Wrapper function around std::transform to apply a function to a range and store the result elsewhere...
Definition: STLExtras.h:896
const value_type operator*() const
Definition: STLExtras.h:419
const UnaryFunc & getFunc() const
Definition: STLExtras.h:157
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
mapped_iterator & operator-=(difference_type n)
Definition: STLExtras.h:194
std::reverse_iterator< IteratorTy > make_reverse_iterator(IteratorTy It)
Definition: STLExtras.h:258
aarch64 promote const
traits class for checking whether type T is a base class for all the given types in the variadic list...
Definition: STLExtras.h:715
enumerator_iter< R > begin()
Definition: STLExtras.h:1080
bool operator==(const mapped_iterator &X) const
Definition: STLExtras.h:201
reference operator[](difference_type n) const
Definition: STLExtras.h:198
enumerator_iter< R > end()
Definition: STLExtras.h:1083
iterator begin() const
Definition: STLExtras.h:486
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1946
Binary functor that adapts to any other binary functor after dereferencing operands.
Definition: STLExtras.h:996
Iterator wrapper that concatenates sequences together.
Definition: STLExtras.h:520
std::tuple< decltype(*declval< Iters >))... > type
Definition: STLExtras.h:373
int * Ptr
Utility type to build an inheritance chain that makes it easy to rank overload candidates.
Definition: STLExtras.h:698
zip_shortest(Iters &&... ts)
Definition: STLExtras.h:463
concat_iterator< ValueT, decltype(std::begin(std::declval< RangeTs & >)))... > iterator
Definition: STLExtras.h:622
auto find_if(R &&Range, UnaryPredicate P) -> decltype(std::begin(Range))
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:846
void deleter(T *Ptr)
Definition: STLExtras.h:125
zip_first(Iters &&... ts)
Definition: STLExtras.h:444
std::size_t index() const
Definition: STLExtras.h:1025
Function object to check whether the first component of a std::pair compares less than the first comp...
Definition: STLExtras.h:660
auto count_if(R &&Range, UnaryPredicate P) -> typename std::iterator_traits< decltype(std::begin(Range))>::difference_type
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
Definition: STLExtras.h:888
concat_iterator(RangeTs &&... Ranges)
Constructs an iterator from a squence of ranges.
Definition: STLExtras.h:596
bool operator==(const zip_shortest< Iters... > &other) const
Definition: STLExtras.h:459
detail::enumerator< R > enumerate(R &&TheRange)
Given an input range, returns a new range whose values are are pair (A,B) such that A is the 0-based ...
Definition: STLExtras.h:1107
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:872
size_t operator()(const std::pair< First, Second > &P) const
Definition: STLExtras.h:975