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 <tuple> 28 #include <utility> // for std::pair 29 30 #include "llvm/ADT/Optional.h" 31 #include "llvm/ADT/iterator.h" 32 #include "llvm/ADT/iterator_range.h" 33 #include "llvm/Support/Compiler.h" 34 35 namespace llvm { 36 37 // Only used by compiler if both template types are the same. Useful when 38 // using SFINAE to test for the existence of member functions. 39 template <typename T, T> struct SameType; 40 41 namespace detail { 42 43 template <typename RangeT> 44 using IterOfRange = decltype(std::begin(std::declval<RangeT &>())); 45 46 } // End detail namespace 47 48 //===----------------------------------------------------------------------===// 49 // Extra additions to <functional> 50 //===----------------------------------------------------------------------===// 51 52 template<class Ty> 53 struct identity : public std::unary_function<Ty, Ty> { 54 Ty &operator()(Ty &self) const { 55 return self; 56 } 57 const Ty &operator()(const Ty &self) const { 58 return self; 59 } 60 }; 61 62 template<class Ty> 63 struct less_ptr : public std::binary_function<Ty, Ty, bool> { 64 bool operator()(const Ty* left, const Ty* right) const { 65 return *left < *right; 66 } 67 }; 68 69 template<class Ty> 70 struct greater_ptr : public std::binary_function<Ty, Ty, bool> { 71 bool operator()(const Ty* left, const Ty* right) const { 72 return *right < *left; 73 } 74 }; 75 76 /// An efficient, type-erasing, non-owning reference to a callable. This is 77 /// intended for use as the type of a function parameter that is not used 78 /// after the function in question returns. 79 /// 80 /// This class does not own the callable, so it is not in general safe to store 81 /// a function_ref. 82 template<typename Fn> class function_ref; 83 84 template<typename Ret, typename ...Params> 85 class function_ref<Ret(Params...)> { 86 Ret (*callback)(intptr_t callable, Params ...params); 87 intptr_t callable; 88 89 template<typename Callable> 90 static Ret callback_fn(intptr_t callable, Params ...params) { 91 return (*reinterpret_cast<Callable*>(callable))( 92 std::forward<Params>(params)...); 93 } 94 95 public: 96 template <typename Callable> 97 function_ref(Callable &&callable, 98 typename std::enable_if< 99 !std::is_same<typename std::remove_reference<Callable>::type, 100 function_ref>::value>::type * = nullptr) 101 : callback(callback_fn<typename std::remove_reference<Callable>::type>), 102 callable(reinterpret_cast<intptr_t>(&callable)) {} 103 Ret operator()(Params ...params) const { 104 return callback(callable, std::forward<Params>(params)...); 105 } 106 }; 107 108 // deleter - Very very very simple method that is used to invoke operator 109 // delete on something. It is used like this: 110 // 111 // for_each(V.begin(), B.end(), deleter<Interval>); 112 // 113 template <class T> 114 inline void deleter(T *Ptr) { 115 delete Ptr; 116 } 117 118 119 120 //===----------------------------------------------------------------------===// 121 // Extra additions to <iterator> 122 //===----------------------------------------------------------------------===// 123 124 // mapped_iterator - This is a simple iterator adapter that causes a function to 125 // be dereferenced whenever operator* is invoked on the iterator. 126 // 127 template <class RootIt, class UnaryFunc> 128 class mapped_iterator { 129 RootIt current; 130 UnaryFunc Fn; 131 public: 132 typedef typename std::iterator_traits<RootIt>::iterator_category 133 iterator_category; 134 typedef typename std::iterator_traits<RootIt>::difference_type 135 difference_type; 136 typedef typename std::result_of< 137 UnaryFunc(decltype(*std::declval<RootIt>()))> 138 ::type value_type; 139 140 typedef void pointer; 141 //typedef typename UnaryFunc::result_type *pointer; 142 typedef void reference; // Can't modify value returned by fn 143 144 typedef RootIt iterator_type; 145 146 inline const RootIt &getCurrent() const { return current; } 147 inline const UnaryFunc &getFunc() const { return Fn; } 148 149 inline explicit mapped_iterator(const RootIt &I, UnaryFunc F) 150 : current(I), Fn(F) {} 151 152 inline value_type operator*() const { // All this work to do this 153 return Fn(*current); // little change 154 } 155 156 mapped_iterator &operator++() { 157 ++current; 158 return *this; 159 } 160 mapped_iterator &operator--() { 161 --current; 162 return *this; 163 } 164 mapped_iterator operator++(int) { 165 mapped_iterator __tmp = *this; 166 ++current; 167 return __tmp; 168 } 169 mapped_iterator operator--(int) { 170 mapped_iterator __tmp = *this; 171 --current; 172 return __tmp; 173 } 174 mapped_iterator operator+(difference_type n) const { 175 return mapped_iterator(current + n, Fn); 176 } 177 mapped_iterator &operator+=(difference_type n) { 178 current += n; 179 return *this; 180 } 181 mapped_iterator operator-(difference_type n) const { 182 return mapped_iterator(current - n, Fn); 183 } 184 mapped_iterator &operator-=(difference_type n) { 185 current -= n; 186 return *this; 187 } 188 reference operator[](difference_type n) const { return *(*this + n); } 189 190 bool operator!=(const mapped_iterator &X) const { return !operator==(X); } 191 bool operator==(const mapped_iterator &X) const { 192 return current == X.current; 193 } 194 bool operator<(const mapped_iterator &X) const { return current < X.current; } 195 196 difference_type operator-(const mapped_iterator &X) const { 197 return current - X.current; 198 } 199 }; 200 201 template <class Iterator, class Func> 202 inline mapped_iterator<Iterator, Func> 203 operator+(typename mapped_iterator<Iterator, Func>::difference_type N, 204 const mapped_iterator<Iterator, Func> &X) { 205 return mapped_iterator<Iterator, Func>(X.getCurrent() - N, X.getFunc()); 206 } 207 208 209 // map_iterator - Provide a convenient way to create mapped_iterators, just like 210 // make_pair is useful for creating pairs... 211 // 212 template <class ItTy, class FuncTy> 213 inline mapped_iterator<ItTy, FuncTy> map_iterator(const ItTy &I, FuncTy F) { 214 return mapped_iterator<ItTy, FuncTy>(I, F); 215 } 216 217 /// Helper to determine if type T has a member called rbegin(). 218 template <typename Ty> class has_rbegin_impl { 219 typedef char yes[1]; 220 typedef char no[2]; 221 222 template <typename Inner> 223 static yes& test(Inner *I, decltype(I->rbegin()) * = nullptr); 224 225 template <typename> 226 static no& test(...); 227 228 public: 229 static const bool value = sizeof(test<Ty>(nullptr)) == sizeof(yes); 230 }; 231 232 /// Metafunction to determine if T& or T has a member called rbegin(). 233 template <typename Ty> 234 struct has_rbegin : has_rbegin_impl<typename std::remove_reference<Ty>::type> { 235 }; 236 237 // Returns an iterator_range over the given container which iterates in reverse. 238 // Note that the container must have rbegin()/rend() methods for this to work. 239 template <typename ContainerTy> 240 auto reverse(ContainerTy &&C, 241 typename std::enable_if<has_rbegin<ContainerTy>::value>::type * = 242 nullptr) -> decltype(make_range(C.rbegin(), C.rend())) { 243 return make_range(C.rbegin(), C.rend()); 244 } 245 246 // Returns a std::reverse_iterator wrapped around the given iterator. 247 template <typename IteratorTy> 248 std::reverse_iterator<IteratorTy> make_reverse_iterator(IteratorTy It) { 249 return std::reverse_iterator<IteratorTy>(It); 250 } 251 252 // Returns an iterator_range over the given container which iterates in reverse. 253 // Note that the container must have begin()/end() methods which return 254 // bidirectional iterators for this to work. 255 template <typename ContainerTy> 256 auto reverse( 257 ContainerTy &&C, 258 typename std::enable_if<!has_rbegin<ContainerTy>::value>::type * = nullptr) 259 -> decltype(make_range(llvm::make_reverse_iterator(std::end(C)), 260 llvm::make_reverse_iterator(std::begin(C)))) { 261 return make_range(llvm::make_reverse_iterator(std::end(C)), 262 llvm::make_reverse_iterator(std::begin(C))); 263 } 264 265 /// An iterator adaptor that filters the elements of given inner iterators. 266 /// 267 /// The predicate parameter should be a callable object that accepts the wrapped 268 /// iterator's reference type and returns a bool. When incrementing or 269 /// decrementing the iterator, it will call the predicate on each element and 270 /// skip any where it returns false. 271 /// 272 /// \code 273 /// int A[] = { 1, 2, 3, 4 }; 274 /// auto R = make_filter_range(A, [](int N) { return N % 2 == 1; }); 275 /// // R contains { 1, 3 }. 276 /// \endcode 277 template <typename WrappedIteratorT, typename PredicateT> 278 class filter_iterator 279 : public iterator_adaptor_base< 280 filter_iterator<WrappedIteratorT, PredicateT>, WrappedIteratorT, 281 typename std::common_type< 282 std::forward_iterator_tag, 283 typename std::iterator_traits< 284 WrappedIteratorT>::iterator_category>::type> { 285 using BaseT = iterator_adaptor_base< 286 filter_iterator<WrappedIteratorT, PredicateT>, WrappedIteratorT, 287 typename std::common_type< 288 std::forward_iterator_tag, 289 typename std::iterator_traits<WrappedIteratorT>::iterator_category>:: 290 type>; 291 292 struct PayloadType { 293 WrappedIteratorT End; 294 PredicateT Pred; 295 }; 296 297 Optional<PayloadType> Payload; 298 299 void findNextValid() { 300 assert(Payload && "Payload should be engaged when findNextValid is called"); 301 while (this->I != Payload->End && !Payload->Pred(*this->I)) 302 BaseT::operator++(); 303 } 304 305 // Construct the begin iterator. The begin iterator requires to know where end 306 // is, so that it can properly stop when it hits end. 307 filter_iterator(WrappedIteratorT Begin, WrappedIteratorT End, PredicateT Pred) 308 : BaseT(std::move(Begin)), 309 Payload(PayloadType{std::move(End), std::move(Pred)}) { 310 findNextValid(); 311 } 312 313 // Construct the end iterator. It's not incrementable, so Payload doesn't 314 // have to be engaged. 315 filter_iterator(WrappedIteratorT End) : BaseT(End) {} 316 317 public: 318 using BaseT::operator++; 319 320 filter_iterator &operator++() { 321 BaseT::operator++(); 322 findNextValid(); 323 return *this; 324 } 325 326 template <typename RT, typename PT> 327 friend iterator_range<filter_iterator<detail::IterOfRange<RT>, PT>> 328 make_filter_range(RT &&, PT); 329 }; 330 331 /// Convenience function that takes a range of elements and a predicate, 332 /// and return a new filter_iterator range. 333 /// 334 /// FIXME: Currently if RangeT && is a rvalue reference to a temporary, the 335 /// lifetime of that temporary is not kept by the returned range object, and the 336 /// temporary is going to be dropped on the floor after the make_iterator_range 337 /// full expression that contains this function call. 338 template <typename RangeT, typename PredicateT> 339 iterator_range<filter_iterator<detail::IterOfRange<RangeT>, PredicateT>> 340 make_filter_range(RangeT &&Range, PredicateT Pred) { 341 using FilterIteratorT = 342 filter_iterator<detail::IterOfRange<RangeT>, PredicateT>; 343 return make_range(FilterIteratorT(std::begin(std::forward<RangeT>(Range)), 344 std::end(std::forward<RangeT>(Range)), 345 std::move(Pred)), 346 FilterIteratorT(std::end(std::forward<RangeT>(Range)))); 347 } 348 349 // forward declarations required by zip_shortest/zip_first 350 template <typename R, typename UnaryPredicate> 351 bool all_of(R &&range, UnaryPredicate P); 352 353 template <size_t... I> struct index_sequence; 354 355 template <class... Ts> struct index_sequence_for; 356 357 namespace detail { 358 template <typename... Iters> class zip_first { 359 public: 360 typedef std::input_iterator_tag iterator_category; 361 typedef std::tuple<decltype(*std::declval<Iters>())...> value_type; 362 std::tuple<Iters...> iterators; 363 364 private: 365 template <size_t... Ns> value_type deres(index_sequence<Ns...>) { 366 return value_type(*std::get<Ns>(iterators)...); 367 } 368 369 template <size_t... Ns> decltype(iterators) tup_inc(index_sequence<Ns...>) { 370 return std::tuple<Iters...>(std::next(std::get<Ns>(iterators))...); 371 } 372 373 public: 374 value_type operator*() { return deres(index_sequence_for<Iters...>{}); } 375 376 void operator++() { iterators = tup_inc(index_sequence_for<Iters...>{}); } 377 378 bool operator!=(const zip_first<Iters...> &other) const { 379 return std::get<0>(iterators) != std::get<0>(other.iterators); 380 } 381 zip_first(Iters &&... ts) : iterators(std::forward<Iters>(ts)...) {} 382 }; 383 384 template <typename... Iters> class zip_shortest : public zip_first<Iters...> { 385 template <size_t... Ns> 386 bool test(const zip_first<Iters...> &other, index_sequence<Ns...>) const { 387 return all_of(std::initializer_list<bool>{std::get<Ns>(this->iterators) != 388 std::get<Ns>(other.iterators)...}, 389 identity<bool>{}); 390 } 391 392 public: 393 bool operator!=(const zip_first<Iters...> &other) const { 394 return test(other, index_sequence_for<Iters...>{}); 395 } 396 zip_shortest(Iters &&... ts) 397 : zip_first<Iters...>(std::forward<Iters>(ts)...) {} 398 }; 399 400 template <template <typename...> class ItType, typename... Args> class zippy { 401 public: 402 typedef ItType<decltype(std::begin(std::declval<Args>()))...> iterator; 403 404 private: 405 std::tuple<Args...> ts; 406 407 template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) { 408 return iterator(std::begin(std::get<Ns>(ts))...); 409 } 410 template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) { 411 return iterator(std::end(std::get<Ns>(ts))...); 412 } 413 414 public: 415 iterator begin() { return begin_impl(index_sequence_for<Args...>{}); } 416 iterator end() { return end_impl(index_sequence_for<Args...>{}); } 417 zippy(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {} 418 }; 419 } // End detail namespace 420 421 /// zip iterator for two or more iteratable types. 422 template <typename T, typename U, typename... Args> 423 detail::zippy<detail::zip_shortest, T, U, Args...> zip(T &&t, U &&u, 424 Args &&... args) { 425 return detail::zippy<detail::zip_shortest, T, U, Args...>( 426 std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...); 427 } 428 429 /// zip iterator that, for the sake of efficiency, assumes the first iteratee to 430 /// be the shortest. 431 template <typename T, typename U, typename... Args> 432 detail::zippy<detail::zip_first, T, U, Args...> zip_first(T &&t, U &&u, 433 Args &&... args) { 434 return detail::zippy<detail::zip_first, T, U, Args...>( 435 std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...); 436 } 437 438 //===----------------------------------------------------------------------===// 439 // Extra additions to <utility> 440 //===----------------------------------------------------------------------===// 441 442 /// \brief Function object to check whether the first component of a std::pair 443 /// compares less than the first component of another std::pair. 444 struct less_first { 445 template <typename T> bool operator()(const T &lhs, const T &rhs) const { 446 return lhs.first < rhs.first; 447 } 448 }; 449 450 /// \brief Function object to check whether the second component of a std::pair 451 /// compares less than the second component of another std::pair. 452 struct less_second { 453 template <typename T> bool operator()(const T &lhs, const T &rhs) const { 454 return lhs.second < rhs.second; 455 } 456 }; 457 458 // A subset of N3658. More stuff can be added as-needed. 459 460 /// \brief Represents a compile-time sequence of integers. 461 template <class T, T... I> struct integer_sequence { 462 typedef T value_type; 463 464 static constexpr size_t size() { return sizeof...(I); } 465 }; 466 467 /// \brief Alias for the common case of a sequence of size_ts. 468 template <size_t... I> 469 struct index_sequence : integer_sequence<std::size_t, I...> {}; 470 471 template <std::size_t N, std::size_t... I> 472 struct build_index_impl : build_index_impl<N - 1, N - 1, I...> {}; 473 template <std::size_t... I> 474 struct build_index_impl<0, I...> : index_sequence<I...> {}; 475 476 /// \brief Creates a compile-time integer sequence for a parameter pack. 477 template <class... Ts> 478 struct index_sequence_for : build_index_impl<sizeof...(Ts)> {}; 479 480 /// Utility type to build an inheritance chain that makes it easy to rank 481 /// overload candidates. 482 template <int N> struct rank : rank<N - 1> {}; 483 template <> struct rank<0> {}; 484 485 /// \brief traits class for checking whether type T is one of any of the given 486 /// types in the variadic list. 487 template <typename T, typename... Ts> struct is_one_of { 488 static const bool value = false; 489 }; 490 491 template <typename T, typename U, typename... Ts> 492 struct is_one_of<T, U, Ts...> { 493 static const bool value = 494 std::is_same<T, U>::value || is_one_of<T, Ts...>::value; 495 }; 496 497 //===----------------------------------------------------------------------===// 498 // Extra additions for arrays 499 //===----------------------------------------------------------------------===// 500 501 /// Find the length of an array. 502 template <class T, std::size_t N> 503 constexpr inline size_t array_lengthof(T (&)[N]) { 504 return N; 505 } 506 507 /// Adapt std::less<T> for array_pod_sort. 508 template<typename T> 509 inline int array_pod_sort_comparator(const void *P1, const void *P2) { 510 if (std::less<T>()(*reinterpret_cast<const T*>(P1), 511 *reinterpret_cast<const T*>(P2))) 512 return -1; 513 if (std::less<T>()(*reinterpret_cast<const T*>(P2), 514 *reinterpret_cast<const T*>(P1))) 515 return 1; 516 return 0; 517 } 518 519 /// get_array_pod_sort_comparator - This is an internal helper function used to 520 /// get type deduction of T right. 521 template<typename T> 522 inline int (*get_array_pod_sort_comparator(const T &)) 523 (const void*, const void*) { 524 return array_pod_sort_comparator<T>; 525 } 526 527 528 /// array_pod_sort - This sorts an array with the specified start and end 529 /// extent. This is just like std::sort, except that it calls qsort instead of 530 /// using an inlined template. qsort is slightly slower than std::sort, but 531 /// most sorts are not performance critical in LLVM and std::sort has to be 532 /// template instantiated for each type, leading to significant measured code 533 /// bloat. This function should generally be used instead of std::sort where 534 /// possible. 535 /// 536 /// This function assumes that you have simple POD-like types that can be 537 /// compared with std::less and can be moved with memcpy. If this isn't true, 538 /// you should use std::sort. 539 /// 540 /// NOTE: If qsort_r were portable, we could allow a custom comparator and 541 /// default to std::less. 542 template<class IteratorTy> 543 inline void array_pod_sort(IteratorTy Start, IteratorTy End) { 544 // Don't inefficiently call qsort with one element or trigger undefined 545 // behavior with an empty sequence. 546 auto NElts = End - Start; 547 if (NElts <= 1) return; 548 qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start)); 549 } 550 551 template <class IteratorTy> 552 inline void array_pod_sort( 553 IteratorTy Start, IteratorTy End, 554 int (*Compare)( 555 const typename std::iterator_traits<IteratorTy>::value_type *, 556 const typename std::iterator_traits<IteratorTy>::value_type *)) { 557 // Don't inefficiently call qsort with one element or trigger undefined 558 // behavior with an empty sequence. 559 auto NElts = End - Start; 560 if (NElts <= 1) return; 561 qsort(&*Start, NElts, sizeof(*Start), 562 reinterpret_cast<int (*)(const void *, const void *)>(Compare)); 563 } 564 565 //===----------------------------------------------------------------------===// 566 // Extra additions to <algorithm> 567 //===----------------------------------------------------------------------===// 568 569 /// For a container of pointers, deletes the pointers and then clears the 570 /// container. 571 template<typename Container> 572 void DeleteContainerPointers(Container &C) { 573 for (auto V : C) 574 delete V; 575 C.clear(); 576 } 577 578 /// In a container of pairs (usually a map) whose second element is a pointer, 579 /// deletes the second elements and then clears the container. 580 template<typename Container> 581 void DeleteContainerSeconds(Container &C) { 582 for (auto &V : C) 583 delete V.second; 584 C.clear(); 585 } 586 587 /// Provide wrappers to std::all_of which take ranges instead of having to pass 588 /// begin/end explicitly. 589 template <typename R, typename UnaryPredicate> 590 bool all_of(R &&Range, UnaryPredicate P) { 591 return std::all_of(std::begin(Range), std::end(Range), P); 592 } 593 594 /// Provide wrappers to std::any_of which take ranges instead of having to pass 595 /// begin/end explicitly. 596 template <typename R, typename UnaryPredicate> 597 bool any_of(R &&Range, UnaryPredicate P) { 598 return std::any_of(std::begin(Range), std::end(Range), P); 599 } 600 601 /// Provide wrappers to std::none_of which take ranges instead of having to pass 602 /// begin/end explicitly. 603 template <typename R, typename UnaryPredicate> 604 bool none_of(R &&Range, UnaryPredicate P) { 605 return std::none_of(std::begin(Range), std::end(Range), P); 606 } 607 608 /// Provide wrappers to std::find which take ranges instead of having to pass 609 /// begin/end explicitly. 610 template <typename R, typename T> 611 auto find(R &&Range, const T &Val) -> decltype(std::begin(Range)) { 612 return std::find(std::begin(Range), std::end(Range), Val); 613 } 614 615 /// Provide wrappers to std::find_if which take ranges instead of having to pass 616 /// begin/end explicitly. 617 template <typename R, typename UnaryPredicate> 618 auto find_if(R &&Range, UnaryPredicate P) -> decltype(std::begin(Range)) { 619 return std::find_if(std::begin(Range), std::end(Range), P); 620 } 621 622 template <typename R, typename UnaryPredicate> 623 auto find_if_not(R &&Range, UnaryPredicate P) -> decltype(std::begin(Range)) { 624 return std::find_if_not(std::begin(Range), std::end(Range), P); 625 } 626 627 /// Provide wrappers to std::remove_if which take ranges instead of having to 628 /// pass begin/end explicitly. 629 template <typename R, typename UnaryPredicate> 630 auto remove_if(R &&Range, UnaryPredicate P) -> decltype(std::begin(Range)) { 631 return std::remove_if(std::begin(Range), std::end(Range), P); 632 } 633 634 /// Wrapper function around std::find to detect if an element exists 635 /// in a container. 636 template <typename R, typename E> 637 bool is_contained(R &&Range, const E &Element) { 638 return std::find(std::begin(Range), std::end(Range), Element) != 639 std::end(Range); 640 } 641 642 /// Wrapper function around std::count to count the number of times an element 643 /// \p Element occurs in the given range \p Range. 644 template <typename R, typename E> 645 auto count(R &&Range, const E &Element) -> typename std::iterator_traits< 646 decltype(std::begin(Range))>::difference_type { 647 return std::count(std::begin(Range), std::end(Range), Element); 648 } 649 650 /// Wrapper function around std::count_if to count the number of times an 651 /// element satisfying a given predicate occurs in a range. 652 template <typename R, typename UnaryPredicate> 653 auto count_if(R &&Range, UnaryPredicate P) -> typename std::iterator_traits< 654 decltype(std::begin(Range))>::difference_type { 655 return std::count_if(std::begin(Range), std::end(Range), P); 656 } 657 658 /// Wrapper function around std::transform to apply a function to a range and 659 /// store the result elsewhere. 660 template <typename R, typename OutputIt, typename UnaryPredicate> 661 OutputIt transform(R &&Range, OutputIt d_first, UnaryPredicate P) { 662 return std::transform(std::begin(Range), std::end(Range), d_first, P); 663 } 664 665 //===----------------------------------------------------------------------===// 666 // Extra additions to <memory> 667 //===----------------------------------------------------------------------===// 668 669 // Implement make_unique according to N3656. 670 671 /// \brief Constructs a `new T()` with the given args and returns a 672 /// `unique_ptr<T>` which owns the object. 673 /// 674 /// Example: 675 /// 676 /// auto p = make_unique<int>(); 677 /// auto p = make_unique<std::tuple<int, int>>(0, 1); 678 template <class T, class... Args> 679 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type 680 make_unique(Args &&... args) { 681 return std::unique_ptr<T>(new T(std::forward<Args>(args)...)); 682 } 683 684 /// \brief Constructs a `new T[n]` with the given args and returns a 685 /// `unique_ptr<T[]>` which owns the object. 686 /// 687 /// \param n size of the new array. 688 /// 689 /// Example: 690 /// 691 /// auto p = make_unique<int[]>(2); // value-initializes the array with 0's. 692 template <class T> 693 typename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0, 694 std::unique_ptr<T>>::type 695 make_unique(size_t n) { 696 return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]()); 697 } 698 699 /// This function isn't used and is only here to provide better compile errors. 700 template <class T, class... Args> 701 typename std::enable_if<std::extent<T>::value != 0>::type 702 make_unique(Args &&...) = delete; 703 704 struct FreeDeleter { 705 void operator()(void* v) { 706 ::free(v); 707 } 708 }; 709 710 template<typename First, typename Second> 711 struct pair_hash { 712 size_t operator()(const std::pair<First, Second> &P) const { 713 return std::hash<First>()(P.first) * 31 + std::hash<Second>()(P.second); 714 } 715 }; 716 717 /// A functor like C++14's std::less<void> in its absence. 718 struct less { 719 template <typename A, typename B> bool operator()(A &&a, B &&b) const { 720 return std::forward<A>(a) < std::forward<B>(b); 721 } 722 }; 723 724 /// A functor like C++14's std::equal<void> in its absence. 725 struct equal { 726 template <typename A, typename B> bool operator()(A &&a, B &&b) const { 727 return std::forward<A>(a) == std::forward<B>(b); 728 } 729 }; 730 731 /// Binary functor that adapts to any other binary functor after dereferencing 732 /// operands. 733 template <typename T> struct deref { 734 T func; 735 // Could be further improved to cope with non-derivable functors and 736 // non-binary functors (should be a variadic template member function 737 // operator()). 738 template <typename A, typename B> 739 auto operator()(A &lhs, B &rhs) const -> decltype(func(*lhs, *rhs)) { 740 assert(lhs); 741 assert(rhs); 742 return func(*lhs, *rhs); 743 } 744 }; 745 746 namespace detail { 747 template <typename R> class enumerator_impl { 748 public: 749 template <typename X> struct result_pair { 750 result_pair(std::size_t Index, X Value) : Index(Index), Value(Value) {} 751 752 const std::size_t Index; 753 X Value; 754 }; 755 756 class iterator { 757 typedef 758 typename std::iterator_traits<IterOfRange<R>>::reference iter_reference; 759 typedef result_pair<iter_reference> result_type; 760 761 public: 762 iterator(IterOfRange<R> &&Iter, std::size_t Index) 763 : Iter(Iter), Index(Index) {} 764 765 result_type operator*() const { return result_type(Index, *Iter); } 766 767 iterator &operator++() { 768 ++Iter; 769 ++Index; 770 return *this; 771 } 772 773 bool operator!=(const iterator &RHS) const { return Iter != RHS.Iter; } 774 775 private: 776 IterOfRange<R> Iter; 777 std::size_t Index; 778 }; 779 780 public: 781 explicit enumerator_impl(R &&Range) : Range(std::forward<R>(Range)) {} 782 783 iterator begin() { return iterator(std::begin(Range), 0); } 784 iterator end() { return iterator(std::end(Range), std::size_t(-1)); } 785 786 private: 787 R Range; 788 }; 789 } 790 791 /// Given an input range, returns a new range whose values are are pair (A,B) 792 /// such that A is the 0-based index of the item in the sequence, and B is 793 /// the value from the original sequence. Example: 794 /// 795 /// std::vector<char> Items = {'A', 'B', 'C', 'D'}; 796 /// for (auto X : enumerate(Items)) { 797 /// printf("Item %d - %c\n", X.Index, X.Value); 798 /// } 799 /// 800 /// Output: 801 /// Item 0 - A 802 /// Item 1 - B 803 /// Item 2 - C 804 /// Item 3 - D 805 /// 806 template <typename R> detail::enumerator_impl<R> enumerate(R &&Range) { 807 return detail::enumerator_impl<R>(std::forward<R>(Range)); 808 } 809 810 namespace detail { 811 template <typename F, typename Tuple, std::size_t... I> 812 auto apply_tuple_impl(F &&f, Tuple &&t, index_sequence<I...>) 813 -> decltype(std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...)) { 814 return std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...); 815 } 816 } 817 818 /// Given an input tuple (a1, a2, ..., an), pass the arguments of the 819 /// tuple variadically to f as if by calling f(a1, a2, ..., an) and 820 /// return the result. 821 template <typename F, typename Tuple> 822 auto apply_tuple(F &&f, Tuple &&t) -> decltype(detail::apply_tuple_impl( 823 std::forward<F>(f), std::forward<Tuple>(t), 824 build_index_impl< 825 std::tuple_size<typename std::decay<Tuple>::type>::value>{})) { 826 using Indices = build_index_impl< 827 std::tuple_size<typename std::decay<Tuple>::type>::value>; 828 829 return detail::apply_tuple_impl(std::forward<F>(f), std::forward<Tuple>(t), 830 Indices{}); 831 } 832 } // End llvm namespace 833 834 #endif 835