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