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 <algorithm> // for std::all_of 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#include "llvm/ADT/iterator_range.h" 30#include "llvm/Support/Compiler.h" 31 32namespace llvm { 33 34//===----------------------------------------------------------------------===// 35// Extra additions to <functional> 36//===----------------------------------------------------------------------===// 37 38template<class Ty> 39struct identity : public std::unary_function<Ty, Ty> { 40 Ty &operator()(Ty &self) const { 41 return self; 42 } 43 const Ty &operator()(const Ty &self) const { 44 return self; 45 } 46}; 47 48template<class Ty> 49struct less_ptr : public std::binary_function<Ty, Ty, bool> { 50 bool operator()(const Ty* left, const Ty* right) const { 51 return *left < *right; 52 } 53}; 54 55template<class Ty> 56struct greater_ptr : public std::binary_function<Ty, Ty, bool> { 57 bool operator()(const Ty* left, const Ty* right) const { 58 return *right < *left; 59 } 60}; 61 62/// An efficient, type-erasing, non-owning reference to a callable. This is 63/// intended for use as the type of a function parameter that is not used 64/// after the function in question returns. 65/// 66/// This class does not own the callable, so it is not in general safe to store 67/// a function_ref. 68template<typename Fn> class function_ref; 69 70template<typename Ret, typename ...Params> 71class function_ref<Ret(Params...)> { 72 Ret (*callback)(intptr_t callable, Params ...params); 73 intptr_t callable; 74 75 template<typename Callable> 76 static Ret callback_fn(intptr_t callable, Params ...params) { 77 return (*reinterpret_cast<Callable*>(callable))( 78 std::forward<Params>(params)...); 79 } 80 81public: 82 template <typename Callable> 83 function_ref(Callable &&callable, 84 typename std::enable_if< 85 !std::is_same<typename std::remove_reference<Callable>::type, 86 function_ref>::value>::type * = nullptr) 87 : callback(callback_fn<typename std::remove_reference<Callable>::type>), 88 callable(reinterpret_cast<intptr_t>(&callable)) {} 89 Ret operator()(Params ...params) const { 90 return callback(callable, std::forward<Params>(params)...); 91 } 92}; 93 94// deleter - Very very very simple method that is used to invoke operator 95// delete on something. It is used like this: 96// 97// for_each(V.begin(), B.end(), deleter<Interval>); 98// 99template <class T> 100inline void deleter(T *Ptr) { 101 delete Ptr; 102} 103 104 105 106//===----------------------------------------------------------------------===// 107// Extra additions to <iterator> 108//===----------------------------------------------------------------------===// 109 110// mapped_iterator - This is a simple iterator adapter that causes a function to 111// be dereferenced whenever operator* is invoked on the iterator. 112// 113template <class RootIt, class UnaryFunc> 114class mapped_iterator { 115 RootIt current; 116 UnaryFunc Fn; 117public: 118 typedef typename std::iterator_traits<RootIt>::iterator_category 119 iterator_category; 120 typedef typename std::iterator_traits<RootIt>::difference_type 121 difference_type; 122 typedef typename std::result_of< 123 UnaryFunc(decltype(*std::declval<RootIt>()))> 124 ::type value_type; 125 126 typedef void pointer; 127 //typedef typename UnaryFunc::result_type *pointer; 128 typedef void reference; // Can't modify value returned by fn 129 130 typedef RootIt iterator_type; 131 132 inline const RootIt &getCurrent() const { return current; } 133 inline const UnaryFunc &getFunc() const { return Fn; } 134 135 inline explicit mapped_iterator(const RootIt &I, UnaryFunc F) 136 : current(I), Fn(F) {} 137 138 inline value_type operator*() const { // All this work to do this 139 return Fn(*current); // little change 140 } 141 142 mapped_iterator &operator++() { 143 ++current; 144 return *this; 145 } 146 mapped_iterator &operator--() { 147 --current; 148 return *this; 149 } 150 mapped_iterator operator++(int) { 151 mapped_iterator __tmp = *this; 152 ++current; 153 return __tmp; 154 } 155 mapped_iterator operator--(int) { 156 mapped_iterator __tmp = *this; 157 --current; 158 return __tmp; 159 } 160 mapped_iterator operator+(difference_type n) const { 161 return mapped_iterator(current + n, Fn); 162 } 163 mapped_iterator &operator+=(difference_type n) { 164 current += n; 165 return *this; 166 } 167 mapped_iterator operator-(difference_type n) const { 168 return mapped_iterator(current - n, Fn); 169 } 170 mapped_iterator &operator-=(difference_type n) { 171 current -= n; 172 return *this; 173 } 174 reference operator[](difference_type n) const { return *(*this + n); } 175 176 bool operator!=(const mapped_iterator &X) const { return !operator==(X); } 177 bool operator==(const mapped_iterator &X) const { 178 return current == X.current; 179 } 180 bool operator<(const mapped_iterator &X) const { return current < X.current; } 181 182 difference_type operator-(const mapped_iterator &X) const { 183 return current - X.current; 184 } 185}; 186 187template <class Iterator, class Func> 188inline mapped_iterator<Iterator, Func> 189operator+(typename mapped_iterator<Iterator, Func>::difference_type N, 190 const mapped_iterator<Iterator, Func> &X) { 191 return mapped_iterator<Iterator, Func>(X.getCurrent() - N, X.getFunc()); 192} 193 194 195// map_iterator - Provide a convenient way to create mapped_iterators, just like 196// make_pair is useful for creating pairs... 197// 198template <class ItTy, class FuncTy> 199inline mapped_iterator<ItTy, FuncTy> map_iterator(const ItTy &I, FuncTy F) { 200 return mapped_iterator<ItTy, FuncTy>(I, F); 201} 202 203/// \brief Metafunction to determine if type T has a member called rbegin(). 204template <typename T> struct has_rbegin { 205 template <typename U> static char(&f(const U &, decltype(&U::rbegin)))[1]; 206 static char(&f(...))[2]; 207 const static bool value = sizeof(f(std::declval<T>(), nullptr)) == 1; 208}; 209 210// Returns an iterator_range over the given container which iterates in reverse. 211// Note that the container must have rbegin()/rend() methods for this to work. 212template <typename ContainerTy> 213auto reverse(ContainerTy &&C, 214 typename std::enable_if<has_rbegin<ContainerTy>::value>::type * = 215 nullptr) -> decltype(make_range(C.rbegin(), C.rend())) { 216 return make_range(C.rbegin(), C.rend()); 217} 218 219// Returns a std::reverse_iterator wrapped around the given iterator. 220template <typename IteratorTy> 221std::reverse_iterator<IteratorTy> make_reverse_iterator(IteratorTy It) { 222 return std::reverse_iterator<IteratorTy>(It); 223} 224 225// Returns an iterator_range over the given container which iterates in reverse. 226// Note that the container must have begin()/end() methods which return 227// bidirectional iterators for this to work. 228template <typename ContainerTy> 229auto reverse( 230 ContainerTy &&C, 231 typename std::enable_if<!has_rbegin<ContainerTy>::value>::type * = nullptr) 232 -> decltype(make_range(llvm::make_reverse_iterator(std::end(C)), 233 llvm::make_reverse_iterator(std::begin(C)))) { 234 return make_range(llvm::make_reverse_iterator(std::end(C)), 235 llvm::make_reverse_iterator(std::begin(C))); 236} 237 238//===----------------------------------------------------------------------===// 239// Extra additions to <utility> 240//===----------------------------------------------------------------------===// 241 242/// \brief Function object to check whether the first component of a std::pair 243/// compares less than the first component of another std::pair. 244struct less_first { 245 template <typename T> bool operator()(const T &lhs, const T &rhs) const { 246 return lhs.first < rhs.first; 247 } 248}; 249 250/// \brief Function object to check whether the second component of a std::pair 251/// compares less than the second component of another std::pair. 252struct less_second { 253 template <typename T> bool operator()(const T &lhs, const T &rhs) const { 254 return lhs.second < rhs.second; 255 } 256}; 257 258// A subset of N3658. More stuff can be added as-needed. 259 260/// \brief Represents a compile-time sequence of integers. 261template <class T, T... I> struct integer_sequence { 262 typedef T value_type; 263 264 static LLVM_CONSTEXPR size_t size() { return sizeof...(I); } 265}; 266 267/// \brief Alias for the common case of a sequence of size_ts. 268template <size_t... I> 269struct index_sequence : integer_sequence<std::size_t, I...> {}; 270 271template <std::size_t N, std::size_t... I> 272struct build_index_impl : build_index_impl<N - 1, N - 1, I...> {}; 273template <std::size_t... I> 274struct build_index_impl<0, I...> : index_sequence<I...> {}; 275 276/// \brief Creates a compile-time integer sequence for a parameter pack. 277template <class... Ts> 278struct index_sequence_for : build_index_impl<sizeof...(Ts)> {}; 279 280//===----------------------------------------------------------------------===// 281// Extra additions for arrays 282//===----------------------------------------------------------------------===// 283 284/// Find the length of an array. 285template <class T, std::size_t N> 286LLVM_CONSTEXPR inline size_t array_lengthof(T (&)[N]) { 287 return N; 288} 289 290/// Adapt std::less<T> for array_pod_sort. 291template<typename T> 292inline int array_pod_sort_comparator(const void *P1, const void *P2) { 293 if (std::less<T>()(*reinterpret_cast<const T*>(P1), 294 *reinterpret_cast<const T*>(P2))) 295 return -1; 296 if (std::less<T>()(*reinterpret_cast<const T*>(P2), 297 *reinterpret_cast<const T*>(P1))) 298 return 1; 299 return 0; 300} 301 302/// get_array_pod_sort_comparator - This is an internal helper function used to 303/// get type deduction of T right. 304template<typename T> 305inline int (*get_array_pod_sort_comparator(const T &)) 306 (const void*, const void*) { 307 return array_pod_sort_comparator<T>; 308} 309 310 311/// array_pod_sort - This sorts an array with the specified start and end 312/// extent. This is just like std::sort, except that it calls qsort instead of 313/// using an inlined template. qsort is slightly slower than std::sort, but 314/// most sorts are not performance critical in LLVM and std::sort has to be 315/// template instantiated for each type, leading to significant measured code 316/// bloat. This function should generally be used instead of std::sort where 317/// possible. 318/// 319/// This function assumes that you have simple POD-like types that can be 320/// compared with std::less and can be moved with memcpy. If this isn't true, 321/// you should use std::sort. 322/// 323/// NOTE: If qsort_r were portable, we could allow a custom comparator and 324/// default to std::less. 325template<class IteratorTy> 326inline void array_pod_sort(IteratorTy Start, IteratorTy End) { 327 // Don't inefficiently call qsort with one element or trigger undefined 328 // behavior with an empty sequence. 329 auto NElts = End - Start; 330 if (NElts <= 1) return; 331 qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start)); 332} 333 334template <class IteratorTy> 335inline void array_pod_sort( 336 IteratorTy Start, IteratorTy End, 337 int (*Compare)( 338 const typename std::iterator_traits<IteratorTy>::value_type *, 339 const typename std::iterator_traits<IteratorTy>::value_type *)) { 340 // Don't inefficiently call qsort with one element or trigger undefined 341 // behavior with an empty sequence. 342 auto NElts = End - Start; 343 if (NElts <= 1) return; 344 qsort(&*Start, NElts, sizeof(*Start), 345 reinterpret_cast<int (*)(const void *, const void *)>(Compare)); 346} 347 348//===----------------------------------------------------------------------===// 349// Extra additions to <algorithm> 350//===----------------------------------------------------------------------===// 351 352/// For a container of pointers, deletes the pointers and then clears the 353/// container. 354template<typename Container> 355void DeleteContainerPointers(Container &C) { 356 for (typename Container::iterator I = C.begin(), E = C.end(); I != E; ++I) 357 delete *I; 358 C.clear(); 359} 360 361/// In a container of pairs (usually a map) whose second element is a pointer, 362/// deletes the second elements and then clears the container. 363template<typename Container> 364void DeleteContainerSeconds(Container &C) { 365 for (typename Container::iterator I = C.begin(), E = C.end(); I != E; ++I) 366 delete I->second; 367 C.clear(); 368} 369 370/// Provide wrappers to std::all_of which take ranges instead of having to pass 371/// begin/end explicitly. 372template<typename R, class UnaryPredicate> 373bool all_of(R &&Range, UnaryPredicate &&P) { 374 return std::all_of(Range.begin(), Range.end(), 375 std::forward<UnaryPredicate>(P)); 376} 377 378/// Provide wrappers to std::any_of which take ranges instead of having to pass 379/// begin/end explicitly. 380template <typename R, class UnaryPredicate> 381bool any_of(R &&Range, UnaryPredicate &&P) { 382 return std::any_of(Range.begin(), Range.end(), 383 std::forward<UnaryPredicate>(P)); 384} 385 386/// Provide wrappers to std::none_of which take ranges instead of having to pass 387/// begin/end explicitly. 388template <typename R, class UnaryPredicate> 389bool none_of(R &&Range, UnaryPredicate &&P) { 390 return std::none_of(Range.begin(), Range.end(), 391 std::forward<UnaryPredicate>(P)); 392} 393 394/// Provide wrappers to std::find which take ranges instead of having to pass 395/// begin/end explicitly. 396template<typename R, class T> 397auto find(R &&Range, const T &val) -> decltype(Range.begin()) { 398 return std::find(Range.begin(), Range.end(), val); 399} 400 401/// Provide wrappers to std::find_if which take ranges instead of having to pass 402/// begin/end explicitly. 403template <typename R, class T> 404auto find_if(R &&Range, const T &Pred) -> decltype(Range.begin()) { 405 return std::find_if(Range.begin(), Range.end(), Pred); 406} 407 408/// Provide wrappers to std::remove_if which take ranges instead of having to 409/// pass begin/end explicitly. 410template<typename R, class UnaryPredicate> 411auto remove_if(R &&Range, UnaryPredicate &&P) -> decltype(Range.begin()) { 412 return std::remove_if(Range.begin(), Range.end(), P); 413} 414 415/// Wrapper function around std::find to detect if an element exists 416/// in a container. 417template <typename R, typename E> 418bool is_contained(R &&Range, const E &Element) { 419 return std::find(Range.begin(), Range.end(), Element) != Range.end(); 420} 421 422/// Wrapper function around std::count_if to count the number of times an 423/// element satisfying a given predicate occurs in a range. 424template <typename R, typename UnaryPredicate> 425auto count_if(R &&Range, UnaryPredicate &&P) 426 -> typename std::iterator_traits<decltype(Range.begin())>::difference_type { 427 return std::count_if(Range.begin(), Range.end(), P); 428} 429 430/// Wrapper function around std::transform to apply a function to a range and 431/// store the result elsewhere. 432template <typename R, class OutputIt, typename UnaryPredicate> 433OutputIt transform(R &&Range, OutputIt d_first, UnaryPredicate &&P) { 434 return std::transform(Range.begin(), Range.end(), d_first, 435 std::forward<UnaryPredicate>(P)); 436} 437 438//===----------------------------------------------------------------------===// 439// Extra additions to <memory> 440//===----------------------------------------------------------------------===// 441 442// Implement make_unique according to N3656. 443 444/// \brief Constructs a `new T()` with the given args and returns a 445/// `unique_ptr<T>` which owns the object. 446/// 447/// Example: 448/// 449/// auto p = make_unique<int>(); 450/// auto p = make_unique<std::tuple<int, int>>(0, 1); 451template <class T, class... Args> 452typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type 453make_unique(Args &&... args) { 454 return std::unique_ptr<T>(new T(std::forward<Args>(args)...)); 455} 456 457/// \brief Constructs a `new T[n]` with the given args and returns a 458/// `unique_ptr<T[]>` which owns the object. 459/// 460/// \param n size of the new array. 461/// 462/// Example: 463/// 464/// auto p = make_unique<int[]>(2); // value-initializes the array with 0's. 465template <class T> 466typename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0, 467 std::unique_ptr<T>>::type 468make_unique(size_t n) { 469 return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]()); 470} 471 472/// This function isn't used and is only here to provide better compile errors. 473template <class T, class... Args> 474typename std::enable_if<std::extent<T>::value != 0>::type 475make_unique(Args &&...) = delete; 476 477struct FreeDeleter { 478 void operator()(void* v) { 479 ::free(v); 480 } 481}; 482 483template<typename First, typename Second> 484struct pair_hash { 485 size_t operator()(const std::pair<First, Second> &P) const { 486 return std::hash<First>()(P.first) * 31 + std::hash<Second>()(P.second); 487 } 488}; 489 490/// A functor like C++14's std::less<void> in its absence. 491struct less { 492 template <typename A, typename B> bool operator()(A &&a, B &&b) const { 493 return std::forward<A>(a) < std::forward<B>(b); 494 } 495}; 496 497/// A functor like C++14's std::equal<void> in its absence. 498struct equal { 499 template <typename A, typename B> bool operator()(A &&a, B &&b) const { 500 return std::forward<A>(a) == std::forward<B>(b); 501 } 502}; 503 504/// Binary functor that adapts to any other binary functor after dereferencing 505/// operands. 506template <typename T> struct deref { 507 T func; 508 // Could be further improved to cope with non-derivable functors and 509 // non-binary functors (should be a variadic template member function 510 // operator()). 511 template <typename A, typename B> 512 auto operator()(A &lhs, B &rhs) const -> decltype(func(*lhs, *rhs)) { 513 assert(lhs); 514 assert(rhs); 515 return func(*lhs, *rhs); 516 } 517}; 518 519} // End llvm namespace 520 521#endif 522