1//===- llvm/ADT/STLExtras.h - Useful STL related functions ------*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file contains some templates that are useful if you are working with the
11// STL at all.
12//
13// No library is required when using these functions.
14//
15//===----------------------------------------------------------------------===//
16
17#ifndef LLVM_ADT_STLEXTRAS_H
18#define LLVM_ADT_STLEXTRAS_H
19
20#include "llvm/Support/Compiler.h"
21#include <cassert>
22#include <cstddef> // for std::size_t
23#include <cstdlib> // for qsort
24#include <functional>
25#include <iterator>
26#include <memory>
27#include <utility> // for std::pair
28
29namespace llvm {
30
31//===----------------------------------------------------------------------===//
32//     Extra additions to <functional>
33//===----------------------------------------------------------------------===//
34
35template<class Ty>
36struct identity : public std::unary_function<Ty, Ty> {
37  Ty &operator()(Ty &self) const {
38    return self;
39  }
40  const Ty &operator()(const Ty &self) const {
41    return self;
42  }
43};
44
45template<class Ty>
46struct less_ptr : public std::binary_function<Ty, Ty, bool> {
47  bool operator()(const Ty* left, const Ty* right) const {
48    return *left < *right;
49  }
50};
51
52template<class Ty>
53struct greater_ptr : public std::binary_function<Ty, Ty, bool> {
54  bool operator()(const Ty* left, const Ty* right) const {
55    return *right < *left;
56  }
57};
58
59/// An efficient, type-erasing, non-owning reference to a callable. This is
60/// intended for use as the type of a function parameter that is not used
61/// after the function in question returns.
62///
63/// This class does not own the callable, so it is not in general safe to store
64/// a function_ref.
65template<typename Fn> class function_ref;
66
67template<typename Ret, typename ...Params>
68class function_ref<Ret(Params...)> {
69  Ret (*callback)(intptr_t callable, Params ...params);
70  intptr_t callable;
71
72  template<typename Callable>
73  static Ret callback_fn(intptr_t callable, Params ...params) {
74    return (*reinterpret_cast<Callable*>(callable))(
75        std::forward<Params>(params)...);
76  }
77
78public:
79  template <typename Callable>
80  function_ref(Callable &&callable,
81               typename std::enable_if<
82                   !std::is_same<typename std::remove_reference<Callable>::type,
83                                 function_ref>::value>::type * = nullptr)
84      : callback(callback_fn<typename std::remove_reference<Callable>::type>),
85        callable(reinterpret_cast<intptr_t>(&callable)) {}
86  Ret operator()(Params ...params) const {
87    return callback(callable, std::forward<Params>(params)...);
88  }
89};
90
91// deleter - Very very very simple method that is used to invoke operator
92// delete on something.  It is used like this:
93//
94//   for_each(V.begin(), B.end(), deleter<Interval>);
95//
96template <class T>
97inline void deleter(T *Ptr) {
98  delete Ptr;
99}
100
101
102
103//===----------------------------------------------------------------------===//
104//     Extra additions to <iterator>
105//===----------------------------------------------------------------------===//
106
107// mapped_iterator - This is a simple iterator adapter that causes a function to
108// be dereferenced whenever operator* is invoked on the iterator.
109//
110template <class RootIt, class UnaryFunc>
111class mapped_iterator {
112  RootIt current;
113  UnaryFunc Fn;
114public:
115  typedef typename std::iterator_traits<RootIt>::iterator_category
116          iterator_category;
117  typedef typename std::iterator_traits<RootIt>::difference_type
118          difference_type;
119  typedef typename UnaryFunc::result_type value_type;
120
121  typedef void pointer;
122  //typedef typename UnaryFunc::result_type *pointer;
123  typedef void reference;        // Can't modify value returned by fn
124
125  typedef RootIt iterator_type;
126
127  inline const RootIt &getCurrent() const { return current; }
128  inline const UnaryFunc &getFunc() const { return Fn; }
129
130  inline explicit mapped_iterator(const RootIt &I, UnaryFunc F)
131    : current(I), Fn(F) {}
132
133  inline value_type operator*() const {   // All this work to do this
134    return Fn(*current);         // little change
135  }
136
137  mapped_iterator &operator++() {
138    ++current;
139    return *this;
140  }
141  mapped_iterator &operator--() {
142    --current;
143    return *this;
144  }
145  mapped_iterator operator++(int) {
146    mapped_iterator __tmp = *this;
147    ++current;
148    return __tmp;
149  }
150  mapped_iterator operator--(int) {
151    mapped_iterator __tmp = *this;
152    --current;
153    return __tmp;
154  }
155  mapped_iterator operator+(difference_type n) const {
156    return mapped_iterator(current + n, Fn);
157  }
158  mapped_iterator &operator+=(difference_type n) {
159    current += n;
160    return *this;
161  }
162  mapped_iterator operator-(difference_type n) const {
163    return mapped_iterator(current - n, Fn);
164  }
165  mapped_iterator &operator-=(difference_type n) {
166    current -= n;
167    return *this;
168  }
169  reference operator[](difference_type n) const { return *(*this + n); }
170
171  bool operator!=(const mapped_iterator &X) const { return !operator==(X); }
172  bool operator==(const mapped_iterator &X) const {
173    return current == X.current;
174  }
175  bool operator<(const mapped_iterator &X) const { return current < X.current; }
176
177  difference_type operator-(const mapped_iterator &X) const {
178    return current - X.current;
179  }
180};
181
182template <class Iterator, class Func>
183inline mapped_iterator<Iterator, Func>
184operator+(typename mapped_iterator<Iterator, Func>::difference_type N,
185          const mapped_iterator<Iterator, Func> &X) {
186  return mapped_iterator<Iterator, Func>(X.getCurrent() - N, X.getFunc());
187}
188
189
190// map_iterator - Provide a convenient way to create mapped_iterators, just like
191// make_pair is useful for creating pairs...
192//
193template <class ItTy, class FuncTy>
194inline mapped_iterator<ItTy, FuncTy> map_iterator(const ItTy &I, FuncTy F) {
195  return mapped_iterator<ItTy, FuncTy>(I, F);
196}
197
198//===----------------------------------------------------------------------===//
199//     Extra additions to <utility>
200//===----------------------------------------------------------------------===//
201
202/// \brief Function object to check whether the first component of a std::pair
203/// compares less than the first component of another std::pair.
204struct less_first {
205  template <typename T> bool operator()(const T &lhs, const T &rhs) const {
206    return lhs.first < rhs.first;
207  }
208};
209
210/// \brief Function object to check whether the second component of a std::pair
211/// compares less than the second component of another std::pair.
212struct less_second {
213  template <typename T> bool operator()(const T &lhs, const T &rhs) const {
214    return lhs.second < rhs.second;
215  }
216};
217
218// A subset of N3658. More stuff can be added as-needed.
219
220/// \brief Represents a compile-time sequence of integers.
221template <class T, T... I> struct integer_sequence {
222  typedef T value_type;
223
224  static LLVM_CONSTEXPR size_t size() { return sizeof...(I); }
225};
226
227/// \brief Alias for the common case of a sequence of size_ts.
228template <size_t... I>
229struct index_sequence : integer_sequence<std::size_t, I...> {};
230
231template <std::size_t N, std::size_t... I>
232struct build_index_impl : build_index_impl<N - 1, N - 1, I...> {};
233template <std::size_t... I>
234struct build_index_impl<0, I...> : index_sequence<I...> {};
235
236/// \brief Creates a compile-time integer sequence for a parameter pack.
237template <class... Ts>
238struct index_sequence_for : build_index_impl<sizeof...(Ts)> {};
239
240//===----------------------------------------------------------------------===//
241//     Extra additions for arrays
242//===----------------------------------------------------------------------===//
243
244/// Find the length of an array.
245template <class T, std::size_t N>
246LLVM_CONSTEXPR inline size_t array_lengthof(T (&)[N]) {
247  return N;
248}
249
250/// Adapt std::less<T> for array_pod_sort.
251template<typename T>
252inline int array_pod_sort_comparator(const void *P1, const void *P2) {
253  if (std::less<T>()(*reinterpret_cast<const T*>(P1),
254                     *reinterpret_cast<const T*>(P2)))
255    return -1;
256  if (std::less<T>()(*reinterpret_cast<const T*>(P2),
257                     *reinterpret_cast<const T*>(P1)))
258    return 1;
259  return 0;
260}
261
262/// get_array_pod_sort_comparator - This is an internal helper function used to
263/// get type deduction of T right.
264template<typename T>
265inline int (*get_array_pod_sort_comparator(const T &))
266             (const void*, const void*) {
267  return array_pod_sort_comparator<T>;
268}
269
270
271/// array_pod_sort - This sorts an array with the specified start and end
272/// extent.  This is just like std::sort, except that it calls qsort instead of
273/// using an inlined template.  qsort is slightly slower than std::sort, but
274/// most sorts are not performance critical in LLVM and std::sort has to be
275/// template instantiated for each type, leading to significant measured code
276/// bloat.  This function should generally be used instead of std::sort where
277/// possible.
278///
279/// This function assumes that you have simple POD-like types that can be
280/// compared with std::less and can be moved with memcpy.  If this isn't true,
281/// you should use std::sort.
282///
283/// NOTE: If qsort_r were portable, we could allow a custom comparator and
284/// default to std::less.
285template<class IteratorTy>
286inline void array_pod_sort(IteratorTy Start, IteratorTy End) {
287  // Don't inefficiently call qsort with one element or trigger undefined
288  // behavior with an empty sequence.
289  auto NElts = End - Start;
290  if (NElts <= 1) return;
291  qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start));
292}
293
294template <class IteratorTy>
295inline void array_pod_sort(
296    IteratorTy Start, IteratorTy End,
297    int (*Compare)(
298        const typename std::iterator_traits<IteratorTy>::value_type *,
299        const typename std::iterator_traits<IteratorTy>::value_type *)) {
300  // Don't inefficiently call qsort with one element or trigger undefined
301  // behavior with an empty sequence.
302  auto NElts = End - Start;
303  if (NElts <= 1) return;
304  qsort(&*Start, NElts, sizeof(*Start),
305        reinterpret_cast<int (*)(const void *, const void *)>(Compare));
306}
307
308//===----------------------------------------------------------------------===//
309//     Extra additions to <algorithm>
310//===----------------------------------------------------------------------===//
311
312/// For a container of pointers, deletes the pointers and then clears the
313/// container.
314template<typename Container>
315void DeleteContainerPointers(Container &C) {
316  for (typename Container::iterator I = C.begin(), E = C.end(); I != E; ++I)
317    delete *I;
318  C.clear();
319}
320
321/// In a container of pairs (usually a map) whose second element is a pointer,
322/// deletes the second elements and then clears the container.
323template<typename Container>
324void DeleteContainerSeconds(Container &C) {
325  for (typename Container::iterator I = C.begin(), E = C.end(); I != E; ++I)
326    delete I->second;
327  C.clear();
328}
329
330//===----------------------------------------------------------------------===//
331//     Extra additions to <memory>
332//===----------------------------------------------------------------------===//
333
334// Implement make_unique according to N3656.
335
336/// \brief Constructs a `new T()` with the given args and returns a
337///        `unique_ptr<T>` which owns the object.
338///
339/// Example:
340///
341///     auto p = make_unique<int>();
342///     auto p = make_unique<std::tuple<int, int>>(0, 1);
343template <class T, class... Args>
344typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
345make_unique(Args &&... args) {
346  return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
347}
348
349/// \brief Constructs a `new T[n]` with the given args and returns a
350///        `unique_ptr<T[]>` which owns the object.
351///
352/// \param n size of the new array.
353///
354/// Example:
355///
356///     auto p = make_unique<int[]>(2); // value-initializes the array with 0's.
357template <class T>
358typename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0,
359                        std::unique_ptr<T>>::type
360make_unique(size_t n) {
361  return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]());
362}
363
364/// This function isn't used and is only here to provide better compile errors.
365template <class T, class... Args>
366typename std::enable_if<std::extent<T>::value != 0>::type
367make_unique(Args &&...) = delete;
368
369struct FreeDeleter {
370  void operator()(void* v) {
371    ::free(v);
372  }
373};
374
375template<typename First, typename Second>
376struct pair_hash {
377  size_t operator()(const std::pair<First, Second> &P) const {
378    return std::hash<First>()(P.first) * 31 + std::hash<Second>()(P.second);
379  }
380};
381
382/// A functor like C++14's std::less<void> in its absence.
383struct less {
384  template <typename A, typename B> bool operator()(A &&a, B &&b) const {
385    return std::forward<A>(a) < std::forward<B>(b);
386  }
387};
388
389/// A functor like C++14's std::equal<void> in its absence.
390struct equal {
391  template <typename A, typename B> bool operator()(A &&a, B &&b) const {
392    return std::forward<A>(a) == std::forward<B>(b);
393  }
394};
395
396/// Binary functor that adapts to any other binary functor after dereferencing
397/// operands.
398template <typename T> struct deref {
399  T func;
400  // Could be further improved to cope with non-derivable functors and
401  // non-binary functors (should be a variadic template member function
402  // operator()).
403  template <typename A, typename B>
404  auto operator()(A &lhs, B &rhs) const -> decltype(func(*lhs, *rhs)) {
405    assert(lhs);
406    assert(rhs);
407    return func(*lhs, *rhs);
408  }
409};
410
411} // End llvm namespace
412
413#endif
414