1 //===- llvm/ADT/STLExtras.h - Useful STL related functions ------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file contains some templates that are useful if you are working with the
13 // No library is required when using these functions.
15 //===----------------------------------------------------------------------===//
17 #ifndef LLVM_ADT_STLEXTRAS_H
18 #define LLVM_ADT_STLEXTRAS_H
20 #include "llvm/Support/Compiler.h"
21 #include <cstddef> // for std::size_t
22 #include <cstdlib> // for qsort
26 #include <utility> // for std::pair
30 //===----------------------------------------------------------------------===//
31 // Extra additions to <functional>
32 //===----------------------------------------------------------------------===//
35 struct identity : public std::unary_function<Ty, Ty> {
36 Ty &operator()(Ty &self) const {
39 const Ty &operator()(const Ty &self) const {
45 struct less_ptr : public std::binary_function<Ty, Ty, bool> {
46 bool operator()(const Ty* left, const Ty* right) const {
47 return *left < *right;
52 struct greater_ptr : public std::binary_function<Ty, Ty, bool> {
53 bool operator()(const Ty* left, const Ty* right) const {
54 return *right < *left;
58 /// An efficient, type-erasing, non-owning reference to a callable. This is
59 /// intended for use as the type of a function parameter that is not used
60 /// after the function in question returns.
62 /// This class does not own the callable, so it is not in general safe to store
64 template<typename Fn> class function_ref;
66 #if LLVM_HAS_VARIADIC_TEMPLATES
68 template<typename Ret, typename ...Params>
69 class function_ref<Ret(Params...)> {
70 Ret (*callback)(void *callable, Params ...params);
73 template<typename Callable>
74 static Ret callback_fn(void *callable, Params ...params) {
75 return (*reinterpret_cast<Callable*>(callable))(
76 std::forward<Params>(params)...);
80 template<typename Callable>
81 function_ref(Callable &&callable)
82 : callback(callback_fn<typename std::remove_reference<Callable>::type>),
83 callable(reinterpret_cast<void *>(&callable)) {}
84 Ret operator()(Params ...params) const {
85 return callback(callable, std::forward<Params>(params)...);
91 template<typename Ret>
92 class function_ref<Ret()> {
93 Ret (*callback)(void *callable);
96 template<typename Callable>
97 static Ret callback_fn(void *callable) {
98 return (*reinterpret_cast<Callable*>(callable))();
102 template<typename Callable>
103 function_ref(Callable &&callable)
104 : callback(callback_fn<typename std::remove_reference<Callable>::type>),
105 callable(reinterpret_cast<void *>(&callable)) {}
106 Ret operator()() const { return callback(callable); }
109 template<typename Ret, typename Param1>
110 class function_ref<Ret(Param1)> {
111 Ret (*callback)(void *callable, Param1 param1);
114 template<typename Callable>
115 static Ret callback_fn(void *callable, Param1 param1) {
116 return (*reinterpret_cast<Callable*>(callable))(
117 std::forward<Param1>(param1));
121 template<typename Callable>
122 function_ref(Callable &&callable)
123 : callback(callback_fn<typename std::remove_reference<Callable>::type>),
124 callable(reinterpret_cast<void *>(&callable)) {}
125 Ret operator()(Param1 param1) {
126 return callback(callable, std::forward<Param1>(param1));
130 template<typename Ret, typename Param1, typename Param2>
131 class function_ref<Ret(Param1, Param2)> {
132 Ret (*callback)(void *callable, Param1 param1, Param2 param2);
135 template<typename Callable>
136 static Ret callback_fn(void *callable, Param1 param1, Param2 param2) {
137 return (*reinterpret_cast<Callable*>(callable))(
138 std::forward<Param1>(param1),
139 std::forward<Param2>(param2));
143 template<typename Callable>
144 function_ref(Callable &&callable)
145 : callback(callback_fn<typename std::remove_reference<Callable>::type>),
146 callable(reinterpret_cast<void *>(&callable)) {}
147 Ret operator()(Param1 param1, Param2 param2) {
148 return callback(callable,
149 std::forward<Param1>(param1),
150 std::forward<Param2>(param2));
154 template<typename Ret, typename Param1, typename Param2, typename Param3>
155 class function_ref<Ret(Param1, Param2, Param3)> {
156 Ret (*callback)(void *callable, Param1 param1, Param2 param2, Param3 param3);
159 template<typename Callable>
160 static Ret callback_fn(void *callable, Param1 param1, Param2 param2,
162 return (*reinterpret_cast<Callable*>(callable))(
163 std::forward<Param1>(param1),
164 std::forward<Param2>(param2),
165 std::forward<Param3>(param3));
169 template<typename Callable>
170 function_ref(Callable &&callable)
171 : callback(callback_fn<typename std::remove_reference<Callable>::type>),
172 callable(reinterpret_cast<void *>(&callable)) {}
173 Ret operator()(Param1 param1, Param2 param2, Param3 param3) {
174 return callback(callable,
175 std::forward<Param1>(param1),
176 std::forward<Param2>(param2),
177 std::forward<Param3>(param3));
183 // deleter - Very very very simple method that is used to invoke operator
184 // delete on something. It is used like this:
186 // for_each(V.begin(), B.end(), deleter<Interval>);
189 inline void deleter(T *Ptr) {
195 //===----------------------------------------------------------------------===//
196 // Extra additions to <iterator>
197 //===----------------------------------------------------------------------===//
199 // mapped_iterator - This is a simple iterator adapter that causes a function to
200 // be dereferenced whenever operator* is invoked on the iterator.
202 template <class RootIt, class UnaryFunc>
203 class mapped_iterator {
207 typedef typename std::iterator_traits<RootIt>::iterator_category
209 typedef typename std::iterator_traits<RootIt>::difference_type
211 typedef typename UnaryFunc::result_type value_type;
213 typedef void pointer;
214 //typedef typename UnaryFunc::result_type *pointer;
215 typedef void reference; // Can't modify value returned by fn
217 typedef RootIt iterator_type;
218 typedef mapped_iterator<RootIt, UnaryFunc> _Self;
220 inline const RootIt &getCurrent() const { return current; }
221 inline const UnaryFunc &getFunc() const { return Fn; }
223 inline explicit mapped_iterator(const RootIt &I, UnaryFunc F)
224 : current(I), Fn(F) {}
226 inline value_type operator*() const { // All this work to do this
227 return Fn(*current); // little change
230 _Self& operator++() { ++current; return *this; }
231 _Self& operator--() { --current; return *this; }
232 _Self operator++(int) { _Self __tmp = *this; ++current; return __tmp; }
233 _Self operator--(int) { _Self __tmp = *this; --current; return __tmp; }
234 _Self operator+ (difference_type n) const {
235 return _Self(current + n, Fn);
237 _Self& operator+= (difference_type n) { current += n; return *this; }
238 _Self operator- (difference_type n) const {
239 return _Self(current - n, Fn);
241 _Self& operator-= (difference_type n) { current -= n; return *this; }
242 reference operator[](difference_type n) const { return *(*this + n); }
244 inline bool operator!=(const _Self &X) const { return !operator==(X); }
245 inline bool operator==(const _Self &X) const { return current == X.current; }
246 inline bool operator< (const _Self &X) const { return current < X.current; }
248 inline difference_type operator-(const _Self &X) const {
249 return current - X.current;
253 template <class _Iterator, class Func>
254 inline mapped_iterator<_Iterator, Func>
255 operator+(typename mapped_iterator<_Iterator, Func>::difference_type N,
256 const mapped_iterator<_Iterator, Func>& X) {
257 return mapped_iterator<_Iterator, Func>(X.getCurrent() - N, X.getFunc());
261 // map_iterator - Provide a convenient way to create mapped_iterators, just like
262 // make_pair is useful for creating pairs...
264 template <class ItTy, class FuncTy>
265 inline mapped_iterator<ItTy, FuncTy> map_iterator(const ItTy &I, FuncTy F) {
266 return mapped_iterator<ItTy, FuncTy>(I, F);
269 //===----------------------------------------------------------------------===//
270 // Extra additions to <utility>
271 //===----------------------------------------------------------------------===//
273 /// \brief Function object to check whether the first component of a std::pair
274 /// compares less than the first component of another std::pair.
276 template <typename T> bool operator()(const T &lhs, const T &rhs) const {
277 return lhs.first < rhs.first;
281 /// \brief Function object to check whether the second component of a std::pair
282 /// compares less than the second component of another std::pair.
284 template <typename T> bool operator()(const T &lhs, const T &rhs) const {
285 return lhs.second < rhs.second;
289 //===----------------------------------------------------------------------===//
290 // Extra additions for arrays
291 //===----------------------------------------------------------------------===//
293 /// Find the length of an array.
294 template <class T, std::size_t N>
295 LLVM_CONSTEXPR inline size_t array_lengthof(T (&)[N]) {
299 /// Adapt std::less<T> for array_pod_sort.
301 inline int array_pod_sort_comparator(const void *P1, const void *P2) {
302 if (std::less<T>()(*reinterpret_cast<const T*>(P1),
303 *reinterpret_cast<const T*>(P2)))
305 if (std::less<T>()(*reinterpret_cast<const T*>(P2),
306 *reinterpret_cast<const T*>(P1)))
311 /// get_array_pod_sort_comparator - This is an internal helper function used to
312 /// get type deduction of T right.
314 inline int (*get_array_pod_sort_comparator(const T &))
315 (const void*, const void*) {
316 return array_pod_sort_comparator<T>;
320 /// array_pod_sort - This sorts an array with the specified start and end
321 /// extent. This is just like std::sort, except that it calls qsort instead of
322 /// using an inlined template. qsort is slightly slower than std::sort, but
323 /// most sorts are not performance critical in LLVM and std::sort has to be
324 /// template instantiated for each type, leading to significant measured code
325 /// bloat. This function should generally be used instead of std::sort where
328 /// This function assumes that you have simple POD-like types that can be
329 /// compared with std::less and can be moved with memcpy. If this isn't true,
330 /// you should use std::sort.
332 /// NOTE: If qsort_r were portable, we could allow a custom comparator and
333 /// default to std::less.
334 template<class IteratorTy>
335 inline void array_pod_sort(IteratorTy Start, IteratorTy End) {
336 // Don't dereference start iterator of empty sequence.
337 if (Start == End) return;
338 qsort(&*Start, End-Start, sizeof(*Start),
339 get_array_pod_sort_comparator(*Start));
342 template <class IteratorTy>
343 inline void array_pod_sort(
344 IteratorTy Start, IteratorTy End,
346 const typename std::iterator_traits<IteratorTy>::value_type *,
347 const typename std::iterator_traits<IteratorTy>::value_type *)) {
348 // Don't dereference start iterator of empty sequence.
349 if (Start == End) return;
350 qsort(&*Start, End - Start, sizeof(*Start),
351 reinterpret_cast<int (*)(const void *, const void *)>(Compare));
354 //===----------------------------------------------------------------------===//
355 // Extra additions to <algorithm>
356 //===----------------------------------------------------------------------===//
358 /// For a container of pointers, deletes the pointers and then clears the
360 template<typename Container>
361 void DeleteContainerPointers(Container &C) {
362 for (typename Container::iterator I = C.begin(), E = C.end(); I != E; ++I)
367 /// In a container of pairs (usually a map) whose second element is a pointer,
368 /// deletes the second elements and then clears the container.
369 template<typename Container>
370 void DeleteContainerSeconds(Container &C) {
371 for (typename Container::iterator I = C.begin(), E = C.end(); I != E; ++I)
376 //===----------------------------------------------------------------------===//
377 // Extra additions to <memory>
378 //===----------------------------------------------------------------------===//
380 #if LLVM_HAS_VARIADIC_TEMPLATES
382 // Implement make_unique according to N3656.
384 /// \brief Constructs a `new T()` with the given args and returns a
385 /// `unique_ptr<T>` which owns the object.
389 /// auto p = make_unique<int>();
390 /// auto p = make_unique<std::tuple<int, int>>(0, 1);
391 template <class T, class... Args>
392 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
393 make_unique(Args &&... args) {
394 return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
397 /// \brief Constructs a `new T[n]` with the given args and returns a
398 /// `unique_ptr<T[]>` which owns the object.
400 /// \param n size of the new array.
404 /// auto p = make_unique<int[]>(2); // value-initializes the array with 0's.
406 typename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0,
407 std::unique_ptr<T>>::type
408 make_unique(size_t n) {
409 return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]());
412 /// This function isn't used and is only here to provide better compile errors.
413 template <class T, class... Args>
414 typename std::enable_if<std::extent<T>::value != 0>::type
415 make_unique(Args &&...) LLVM_DELETED_FUNCTION;
420 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
422 return std::unique_ptr<T>(new T());
425 template <class T, class Arg1>
426 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
427 make_unique(Arg1 &&arg1) {
428 return std::unique_ptr<T>(new T(std::forward<Arg1>(arg1)));
431 template <class T, class Arg1, class Arg2>
432 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
433 make_unique(Arg1 &&arg1, Arg2 &&arg2) {
434 return std::unique_ptr<T>(
435 new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2)));
438 template <class T, class Arg1, class Arg2, class Arg3>
439 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
440 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3) {
441 return std::unique_ptr<T>(new T(std::forward<Arg1>(arg1),
442 std::forward<Arg2>(arg2),
443 std::forward<Arg3>(arg3)));
446 template <class T, class Arg1, class Arg2, class Arg3, class Arg4>
447 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
448 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4) {
449 return std::unique_ptr<T>(
450 new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
451 std::forward<Arg3>(arg3), std::forward<Arg4>(arg4)));
454 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5>
455 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
456 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5) {
457 return std::unique_ptr<T>(
458 new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
459 std::forward<Arg3>(arg3), std::forward<Arg4>(arg4),
460 std::forward<Arg5>(arg5)));
463 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5,
465 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
466 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5,
468 return std::unique_ptr<T>(
469 new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
470 std::forward<Arg3>(arg3), std::forward<Arg4>(arg4),
471 std::forward<Arg5>(arg5), std::forward<Arg6>(arg6)));
474 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5,
475 class Arg6, class Arg7>
476 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
477 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5,
478 Arg6 &&arg6, Arg7 &&arg7) {
479 return std::unique_ptr<T>(
480 new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
481 std::forward<Arg3>(arg3), std::forward<Arg4>(arg4),
482 std::forward<Arg5>(arg5), std::forward<Arg6>(arg6),
483 std::forward<Arg7>(arg7)));
486 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5,
487 class Arg6, class Arg7, class Arg8>
488 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
489 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5,
490 Arg6 &&arg6, Arg7 &&arg7, Arg8 &&arg8) {
491 return std::unique_ptr<T>(
492 new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
493 std::forward<Arg3>(arg3), std::forward<Arg4>(arg4),
494 std::forward<Arg5>(arg5), std::forward<Arg6>(arg6),
495 std::forward<Arg7>(arg7), std::forward<Arg8>(arg8)));
498 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5,
499 class Arg6, class Arg7, class Arg8, class Arg9>
500 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
501 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5,
502 Arg6 &&arg6, Arg7 &&arg7, Arg8 &&arg8, Arg9 &&arg9) {
503 return std::unique_ptr<T>(
504 new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
505 std::forward<Arg3>(arg3), std::forward<Arg4>(arg4),
506 std::forward<Arg5>(arg5), std::forward<Arg6>(arg6),
507 std::forward<Arg7>(arg7), std::forward<Arg8>(arg8),
508 std::forward<Arg9>(arg9)));
511 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5,
512 class Arg6, class Arg7, class Arg8, class Arg9, class Arg10>
513 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
514 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5,
515 Arg6 &&arg6, Arg7 &&arg7, Arg8 &&arg8, Arg9 &&arg9, Arg10 &&arg10) {
516 return std::unique_ptr<T>(
517 new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
518 std::forward<Arg3>(arg3), std::forward<Arg4>(arg4),
519 std::forward<Arg5>(arg5), std::forward<Arg6>(arg6),
520 std::forward<Arg7>(arg7), std::forward<Arg8>(arg8),
521 std::forward<Arg9>(arg9), std::forward<Arg10>(arg10)));
525 typename std::enable_if<std::is_array<T>::value &&std::extent<T>::value == 0,
526 std::unique_ptr<T>>::type
527 make_unique(size_t n) {
528 return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]());
533 template<typename First, typename Second>
535 size_t operator()(const std::pair<First, Second> &P) const {
536 return std::hash<First>()(P.first) * 31 + std::hash<Second>()(P.second);
540 } // End llvm namespace