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 32 namespace llvm { 33 34 //===----------------------------------------------------------------------===// 35 // Extra additions to <functional> 36 //===----------------------------------------------------------------------===// 37 38 template<class Ty> 39 struct 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 48 template<class Ty> 49 struct 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 55 template<class Ty> 56 struct 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. 68 template<typename Fn> class function_ref; 69 70 template<typename Ret, typename ...Params> 71 class 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 81 public: 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 // 99 template <class T> 100 inline 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 // 113 template <class RootIt, class UnaryFunc> 114 class mapped_iterator { 115 RootIt current; 116 UnaryFunc Fn; 117 public: 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 187 template <class Iterator, class Func> 188 inline mapped_iterator<Iterator, Func> 189 operator+(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 // 198 template <class ItTy, class FuncTy> 199 inline 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(). 204 template <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. 212 template <typename ContainerTy> 213 auto 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. 220 template <typename IteratorTy> 221 std::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. 228 template <typename ContainerTy> 229 auto 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. 244 struct 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. 252 struct 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. 261 template <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. 268 template <size_t... I> 269 struct index_sequence : integer_sequence<std::size_t, I...> {}; 270 271 template <std::size_t N, std::size_t... I> 272 struct build_index_impl : build_index_impl<N - 1, N - 1, I...> {}; 273 template <std::size_t... I> 274 struct build_index_impl<0, I...> : index_sequence<I...> {}; 275 276 /// \brief Creates a compile-time integer sequence for a parameter pack. 277 template <class... Ts> 278 struct index_sequence_for : build_index_impl<sizeof...(Ts)> {}; 279 280 //===----------------------------------------------------------------------===// 281 // Extra additions for arrays 282 //===----------------------------------------------------------------------===// 283 284 /// Find the length of an array. 285 template <class T, std::size_t N> 286 LLVM_CONSTEXPR inline size_t array_lengthof(T (&)[N]) { 287 return N; 288 } 289 290 /// Adapt std::less<T> for array_pod_sort. 291 template<typename T> 292 inline 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. 304 template<typename T> 305 inline 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. 325 template<class IteratorTy> 326 inline 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 334 template <class IteratorTy> 335 inline 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. 354 template<typename Container> 355 void 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. 363 template<typename Container> 364 void 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. 372 template<typename R, class UnaryPredicate> 373 bool 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. 380 template <typename R, class UnaryPredicate> 381 bool 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. 388 template <typename R, class UnaryPredicate> 389 bool 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. 396 template<typename R, class T> 397 auto 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. 403 template <typename R, class T> 404 auto 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. 410 template<typename R, class UnaryPredicate> 411 auto 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. 417 template <typename R, typename E> 418 bool 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. 424 template <typename R, typename UnaryPredicate> 425 auto 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. 432 template <typename R, class OutputIt, typename UnaryPredicate> 433 OutputIt 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); 451 template <class T, class... Args> 452 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type 453 make_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. 465 template <class T> 466 typename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0, 467 std::unique_ptr<T>>::type 468 make_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. 473 template <class T, class... Args> 474 typename std::enable_if<std::extent<T>::value != 0>::type 475 make_unique(Args &&...) = delete; 476 477 struct FreeDeleter { 478 void operator()(void* v) { 479 ::free(v); 480 } 481 }; 482 483 template<typename First, typename Second> 484 struct 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. 491 struct 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. 498 struct 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. 506 template <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