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)(intptr_t callable, Params ...params);
73 template<typename Callable>
74 static Ret callback_fn(intptr_t callable, Params ...params) {
75 return (*reinterpret_cast<Callable*>(callable))(
76 std::forward<Params>(params)...);
80 template <typename Callable>
81 function_ref(Callable &&callable,
82 typename std::enable_if<
83 !std::is_same<typename std::remove_reference<Callable>::type,
84 function_ref>::value>::type * = nullptr)
85 : callback(callback_fn<typename std::remove_reference<Callable>::type>),
86 callable(reinterpret_cast<intptr_t>(&callable)) {}
87 Ret operator()(Params ...params) const {
88 return callback(callable, std::forward<Params>(params)...);
94 template<typename Ret>
95 class function_ref<Ret()> {
96 Ret (*callback)(intptr_t callable);
99 template<typename Callable>
100 static Ret callback_fn(intptr_t callable) {
101 return (*reinterpret_cast<Callable*>(callable))();
105 template<typename Callable>
106 function_ref(Callable &&callable,
107 typename std::enable_if<
108 !std::is_same<typename std::remove_reference<Callable>::type,
109 function_ref>::value>::type * = nullptr)
110 : callback(callback_fn<typename std::remove_reference<Callable>::type>),
111 callable(reinterpret_cast<intptr_t>(&callable)) {}
112 Ret operator()() const { return callback(callable); }
115 template<typename Ret, typename Param1>
116 class function_ref<Ret(Param1)> {
117 Ret (*callback)(intptr_t callable, Param1 param1);
120 template<typename Callable>
121 static Ret callback_fn(intptr_t callable, Param1 param1) {
122 return (*reinterpret_cast<Callable*>(callable))(
123 std::forward<Param1>(param1));
127 template<typename Callable>
128 function_ref(Callable &&callable,
129 typename std::enable_if<
130 !std::is_same<typename std::remove_reference<Callable>::type,
131 function_ref>::value>::type * = nullptr)
132 : callback(callback_fn<typename std::remove_reference<Callable>::type>),
133 callable(reinterpret_cast<intptr_t>(&callable)) {}
134 Ret operator()(Param1 param1) {
135 return callback(callable, std::forward<Param1>(param1));
139 template<typename Ret, typename Param1, typename Param2>
140 class function_ref<Ret(Param1, Param2)> {
141 Ret (*callback)(intptr_t callable, Param1 param1, Param2 param2);
144 template<typename Callable>
145 static Ret callback_fn(intptr_t callable, Param1 param1, Param2 param2) {
146 return (*reinterpret_cast<Callable*>(callable))(
147 std::forward<Param1>(param1),
148 std::forward<Param2>(param2));
152 template<typename Callable>
153 function_ref(Callable &&callable,
154 typename std::enable_if<
155 !std::is_same<typename std::remove_reference<Callable>::type,
156 function_ref>::value>::type * = nullptr)
157 : callback(callback_fn<typename std::remove_reference<Callable>::type>),
158 callable(reinterpret_cast<intptr_t>(&callable)) {}
159 Ret operator()(Param1 param1, Param2 param2) {
160 return callback(callable,
161 std::forward<Param1>(param1),
162 std::forward<Param2>(param2));
166 template<typename Ret, typename Param1, typename Param2, typename Param3>
167 class function_ref<Ret(Param1, Param2, Param3)> {
168 Ret (*callback)(intptr_t callable, Param1 param1, Param2 param2, Param3 param3);
171 template<typename Callable>
172 static Ret callback_fn(intptr_t callable, Param1 param1, Param2 param2,
174 return (*reinterpret_cast<Callable*>(callable))(
175 std::forward<Param1>(param1),
176 std::forward<Param2>(param2),
177 std::forward<Param3>(param3));
181 template<typename Callable>
182 function_ref(Callable &&callable,
183 typename std::enable_if<
184 !std::is_same<typename std::remove_reference<Callable>::type,
185 function_ref>::value>::type * = nullptr)
186 : callback(callback_fn<typename std::remove_reference<Callable>::type>),
187 callable(reinterpret_cast<intptr_t>(&callable)) {}
188 Ret operator()(Param1 param1, Param2 param2, Param3 param3) {
189 return callback(callable,
190 std::forward<Param1>(param1),
191 std::forward<Param2>(param2),
192 std::forward<Param3>(param3));
198 // deleter - Very very very simple method that is used to invoke operator
199 // delete on something. It is used like this:
201 // for_each(V.begin(), B.end(), deleter<Interval>);
204 inline void deleter(T *Ptr) {
210 //===----------------------------------------------------------------------===//
211 // Extra additions to <iterator>
212 //===----------------------------------------------------------------------===//
214 // mapped_iterator - This is a simple iterator adapter that causes a function to
215 // be dereferenced whenever operator* is invoked on the iterator.
217 template <class RootIt, class UnaryFunc>
218 class mapped_iterator {
222 typedef typename std::iterator_traits<RootIt>::iterator_category
224 typedef typename std::iterator_traits<RootIt>::difference_type
226 typedef typename UnaryFunc::result_type value_type;
228 typedef void pointer;
229 //typedef typename UnaryFunc::result_type *pointer;
230 typedef void reference; // Can't modify value returned by fn
232 typedef RootIt iterator_type;
233 typedef mapped_iterator<RootIt, UnaryFunc> _Self;
235 inline const RootIt &getCurrent() const { return current; }
236 inline const UnaryFunc &getFunc() const { return Fn; }
238 inline explicit mapped_iterator(const RootIt &I, UnaryFunc F)
239 : current(I), Fn(F) {}
241 inline value_type operator*() const { // All this work to do this
242 return Fn(*current); // little change
245 _Self& operator++() { ++current; return *this; }
246 _Self& operator--() { --current; return *this; }
247 _Self operator++(int) { _Self __tmp = *this; ++current; return __tmp; }
248 _Self operator--(int) { _Self __tmp = *this; --current; return __tmp; }
249 _Self operator+ (difference_type n) const {
250 return _Self(current + n, Fn);
252 _Self& operator+= (difference_type n) { current += n; return *this; }
253 _Self operator- (difference_type n) const {
254 return _Self(current - n, Fn);
256 _Self& operator-= (difference_type n) { current -= n; return *this; }
257 reference operator[](difference_type n) const { return *(*this + n); }
259 inline bool operator!=(const _Self &X) const { return !operator==(X); }
260 inline bool operator==(const _Self &X) const { return current == X.current; }
261 inline bool operator< (const _Self &X) const { return current < X.current; }
263 inline difference_type operator-(const _Self &X) const {
264 return current - X.current;
268 template <class _Iterator, class Func>
269 inline mapped_iterator<_Iterator, Func>
270 operator+(typename mapped_iterator<_Iterator, Func>::difference_type N,
271 const mapped_iterator<_Iterator, Func>& X) {
272 return mapped_iterator<_Iterator, Func>(X.getCurrent() - N, X.getFunc());
276 // map_iterator - Provide a convenient way to create mapped_iterators, just like
277 // make_pair is useful for creating pairs...
279 template <class ItTy, class FuncTy>
280 inline mapped_iterator<ItTy, FuncTy> map_iterator(const ItTy &I, FuncTy F) {
281 return mapped_iterator<ItTy, FuncTy>(I, F);
284 //===----------------------------------------------------------------------===//
285 // Extra additions to <utility>
286 //===----------------------------------------------------------------------===//
288 /// \brief Function object to check whether the first component of a std::pair
289 /// compares less than the first component of another std::pair.
291 template <typename T> bool operator()(const T &lhs, const T &rhs) const {
292 return lhs.first < rhs.first;
296 /// \brief Function object to check whether the second component of a std::pair
297 /// compares less than the second component of another std::pair.
299 template <typename T> bool operator()(const T &lhs, const T &rhs) const {
300 return lhs.second < rhs.second;
304 //===----------------------------------------------------------------------===//
305 // Extra additions for arrays
306 //===----------------------------------------------------------------------===//
308 /// Find the length of an array.
309 template <class T, std::size_t N>
310 LLVM_CONSTEXPR inline size_t array_lengthof(T (&)[N]) {
314 /// Adapt std::less<T> for array_pod_sort.
316 inline int array_pod_sort_comparator(const void *P1, const void *P2) {
317 if (std::less<T>()(*reinterpret_cast<const T*>(P1),
318 *reinterpret_cast<const T*>(P2)))
320 if (std::less<T>()(*reinterpret_cast<const T*>(P2),
321 *reinterpret_cast<const T*>(P1)))
326 /// get_array_pod_sort_comparator - This is an internal helper function used to
327 /// get type deduction of T right.
329 inline int (*get_array_pod_sort_comparator(const T &))
330 (const void*, const void*) {
331 return array_pod_sort_comparator<T>;
335 /// array_pod_sort - This sorts an array with the specified start and end
336 /// extent. This is just like std::sort, except that it calls qsort instead of
337 /// using an inlined template. qsort is slightly slower than std::sort, but
338 /// most sorts are not performance critical in LLVM and std::sort has to be
339 /// template instantiated for each type, leading to significant measured code
340 /// bloat. This function should generally be used instead of std::sort where
343 /// This function assumes that you have simple POD-like types that can be
344 /// compared with std::less and can be moved with memcpy. If this isn't true,
345 /// you should use std::sort.
347 /// NOTE: If qsort_r were portable, we could allow a custom comparator and
348 /// default to std::less.
349 template<class IteratorTy>
350 inline void array_pod_sort(IteratorTy Start, IteratorTy End) {
351 // Don't dereference start iterator of empty sequence.
352 if (Start == End) return;
353 qsort(&*Start, End-Start, sizeof(*Start),
354 get_array_pod_sort_comparator(*Start));
357 template <class IteratorTy>
358 inline void array_pod_sort(
359 IteratorTy Start, IteratorTy End,
361 const typename std::iterator_traits<IteratorTy>::value_type *,
362 const typename std::iterator_traits<IteratorTy>::value_type *)) {
363 // Don't dereference start iterator of empty sequence.
364 if (Start == End) return;
365 qsort(&*Start, End - Start, sizeof(*Start),
366 reinterpret_cast<int (*)(const void *, const void *)>(Compare));
369 //===----------------------------------------------------------------------===//
370 // Extra additions to <algorithm>
371 //===----------------------------------------------------------------------===//
373 /// For a container of pointers, deletes the pointers and then clears the
375 template<typename Container>
376 void DeleteContainerPointers(Container &C) {
377 for (typename Container::iterator I = C.begin(), E = C.end(); I != E; ++I)
382 /// In a container of pairs (usually a map) whose second element is a pointer,
383 /// deletes the second elements and then clears the container.
384 template<typename Container>
385 void DeleteContainerSeconds(Container &C) {
386 for (typename Container::iterator I = C.begin(), E = C.end(); I != E; ++I)
391 //===----------------------------------------------------------------------===//
392 // Extra additions to <memory>
393 //===----------------------------------------------------------------------===//
395 #if LLVM_HAS_VARIADIC_TEMPLATES
397 // Implement make_unique according to N3656.
399 /// \brief Constructs a `new T()` with the given args and returns a
400 /// `unique_ptr<T>` which owns the object.
404 /// auto p = make_unique<int>();
405 /// auto p = make_unique<std::tuple<int, int>>(0, 1);
406 template <class T, class... Args>
407 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
408 make_unique(Args &&... args) {
409 return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
412 /// \brief Constructs a `new T[n]` with the given args and returns a
413 /// `unique_ptr<T[]>` which owns the object.
415 /// \param n size of the new array.
419 /// auto p = make_unique<int[]>(2); // value-initializes the array with 0's.
421 typename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0,
422 std::unique_ptr<T>>::type
423 make_unique(size_t n) {
424 return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]());
427 /// This function isn't used and is only here to provide better compile errors.
428 template <class T, class... Args>
429 typename std::enable_if<std::extent<T>::value != 0>::type
430 make_unique(Args &&...) LLVM_DELETED_FUNCTION;
435 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
437 return std::unique_ptr<T>(new T());
440 template <class T, class Arg1>
441 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
442 make_unique(Arg1 &&arg1) {
443 return std::unique_ptr<T>(new T(std::forward<Arg1>(arg1)));
446 template <class T, class Arg1, class Arg2>
447 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
448 make_unique(Arg1 &&arg1, Arg2 &&arg2) {
449 return std::unique_ptr<T>(
450 new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2)));
453 template <class T, class Arg1, class Arg2, class Arg3>
454 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
455 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3) {
456 return std::unique_ptr<T>(new T(std::forward<Arg1>(arg1),
457 std::forward<Arg2>(arg2),
458 std::forward<Arg3>(arg3)));
461 template <class T, class Arg1, class Arg2, class Arg3, class Arg4>
462 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
463 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4) {
464 return std::unique_ptr<T>(
465 new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
466 std::forward<Arg3>(arg3), std::forward<Arg4>(arg4)));
469 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5>
470 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
471 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5) {
472 return std::unique_ptr<T>(
473 new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
474 std::forward<Arg3>(arg3), std::forward<Arg4>(arg4),
475 std::forward<Arg5>(arg5)));
478 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5,
480 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
481 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5,
483 return std::unique_ptr<T>(
484 new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
485 std::forward<Arg3>(arg3), std::forward<Arg4>(arg4),
486 std::forward<Arg5>(arg5), std::forward<Arg6>(arg6)));
489 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5,
490 class Arg6, class Arg7>
491 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
492 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5,
493 Arg6 &&arg6, Arg7 &&arg7) {
494 return std::unique_ptr<T>(
495 new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
496 std::forward<Arg3>(arg3), std::forward<Arg4>(arg4),
497 std::forward<Arg5>(arg5), std::forward<Arg6>(arg6),
498 std::forward<Arg7>(arg7)));
501 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5,
502 class Arg6, class Arg7, class Arg8>
503 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
504 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5,
505 Arg6 &&arg6, Arg7 &&arg7, Arg8 &&arg8) {
506 return std::unique_ptr<T>(
507 new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
508 std::forward<Arg3>(arg3), std::forward<Arg4>(arg4),
509 std::forward<Arg5>(arg5), std::forward<Arg6>(arg6),
510 std::forward<Arg7>(arg7), std::forward<Arg8>(arg8)));
513 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5,
514 class Arg6, class Arg7, class Arg8, class Arg9>
515 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
516 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5,
517 Arg6 &&arg6, Arg7 &&arg7, Arg8 &&arg8, Arg9 &&arg9) {
518 return std::unique_ptr<T>(
519 new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
520 std::forward<Arg3>(arg3), std::forward<Arg4>(arg4),
521 std::forward<Arg5>(arg5), std::forward<Arg6>(arg6),
522 std::forward<Arg7>(arg7), std::forward<Arg8>(arg8),
523 std::forward<Arg9>(arg9)));
526 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5,
527 class Arg6, class Arg7, class Arg8, class Arg9, class Arg10>
528 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
529 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5,
530 Arg6 &&arg6, Arg7 &&arg7, Arg8 &&arg8, Arg9 &&arg9, Arg10 &&arg10) {
531 return std::unique_ptr<T>(
532 new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
533 std::forward<Arg3>(arg3), std::forward<Arg4>(arg4),
534 std::forward<Arg5>(arg5), std::forward<Arg6>(arg6),
535 std::forward<Arg7>(arg7), std::forward<Arg8>(arg8),
536 std::forward<Arg9>(arg9), std::forward<Arg10>(arg10)));
540 typename std::enable_if<std::is_array<T>::value &&std::extent<T>::value == 0,
541 std::unique_ptr<T>>::type
542 make_unique(size_t n) {
543 return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]());
549 void operator()(void* v) {
554 template<typename First, typename Second>
556 size_t operator()(const std::pair<First, Second> &P) const {
557 return std::hash<First>()(P.first) * 31 + std::hash<Second>()(P.second);
561 } // End llvm namespace