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