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