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 <limits> 27 #include <memory> 28 #include <tuple> 29 #include <utility> // for std::pair 30 31 #include "llvm/ADT/Optional.h" 32 #include "llvm/ADT/SmallVector.h" 33 #include "llvm/ADT/iterator.h" 34 #include "llvm/ADT/iterator_range.h" 35 #include "llvm/Support/Compiler.h" 36 #include "llvm/Support/ErrorHandling.h" 37 38 namespace llvm { 39 40 // Only used by compiler if both template types are the same. Useful when 41 // using SFINAE to test for the existence of member functions. 42 template <typename T, T> struct SameType; 43 44 namespace detail { 45 46 template <typename RangeT> 47 using IterOfRange = decltype(std::begin(std::declval<RangeT &>())); 48 49 template <typename RangeT> 50 using ValueOfRange = typename std::remove_reference<decltype( 51 *std::begin(std::declval<RangeT &>()))>::type; 52 53 } // End detail namespace 54 55 //===----------------------------------------------------------------------===// 56 // Extra additions to <functional> 57 //===----------------------------------------------------------------------===// 58 59 template<class Ty> 60 struct identity : public std::unary_function<Ty, Ty> { 61 Ty &operator()(Ty &self) const { 62 return self; 63 } 64 const Ty &operator()(const Ty &self) const { 65 return self; 66 } 67 }; 68 69 template<class Ty> 70 struct less_ptr : public std::binary_function<Ty, Ty, bool> { 71 bool operator()(const Ty* left, const Ty* right) const { 72 return *left < *right; 73 } 74 }; 75 76 template<class Ty> 77 struct greater_ptr : public std::binary_function<Ty, Ty, bool> { 78 bool operator()(const Ty* left, const Ty* right) const { 79 return *right < *left; 80 } 81 }; 82 83 /// An efficient, type-erasing, non-owning reference to a callable. This is 84 /// intended for use as the type of a function parameter that is not used 85 /// after the function in question returns. 86 /// 87 /// This class does not own the callable, so it is not in general safe to store 88 /// a function_ref. 89 template<typename Fn> class function_ref; 90 91 template<typename Ret, typename ...Params> 92 class function_ref<Ret(Params...)> { 93 Ret (*callback)(intptr_t callable, Params ...params); 94 intptr_t callable; 95 96 template<typename Callable> 97 static Ret callback_fn(intptr_t callable, Params ...params) { 98 return (*reinterpret_cast<Callable*>(callable))( 99 std::forward<Params>(params)...); 100 } 101 102 public: 103 template <typename Callable> 104 function_ref(Callable &&callable, 105 typename std::enable_if< 106 !std::is_same<typename std::remove_reference<Callable>::type, 107 function_ref>::value>::type * = nullptr) 108 : callback(callback_fn<typename std::remove_reference<Callable>::type>), 109 callable(reinterpret_cast<intptr_t>(&callable)) {} 110 Ret operator()(Params ...params) const { 111 return callback(callable, std::forward<Params>(params)...); 112 } 113 }; 114 115 // deleter - Very very very simple method that is used to invoke operator 116 // delete on something. It is used like this: 117 // 118 // for_each(V.begin(), B.end(), deleter<Interval>); 119 // 120 template <class T> 121 inline void deleter(T *Ptr) { 122 delete Ptr; 123 } 124 125 126 127 //===----------------------------------------------------------------------===// 128 // Extra additions to <iterator> 129 //===----------------------------------------------------------------------===// 130 131 // mapped_iterator - This is a simple iterator adapter that causes a function to 132 // be applied whenever operator* is invoked on the iterator. 133 // 134 template <class RootIt, class UnaryFunc> 135 class mapped_iterator { 136 RootIt current; 137 UnaryFunc Fn; 138 public: 139 typedef typename std::iterator_traits<RootIt>::iterator_category 140 iterator_category; 141 typedef typename std::iterator_traits<RootIt>::difference_type 142 difference_type; 143 typedef decltype(std::declval<UnaryFunc>()(*std::declval<RootIt>())) 144 value_type; 145 146 typedef void pointer; 147 //typedef typename UnaryFunc::result_type *pointer; 148 typedef void reference; // Can't modify value returned by fn 149 150 typedef RootIt iterator_type; 151 152 inline const RootIt &getCurrent() const { return current; } 153 inline const UnaryFunc &getFunc() const { return Fn; } 154 155 inline explicit mapped_iterator(const RootIt &I, UnaryFunc F) 156 : current(I), Fn(F) {} 157 158 inline value_type operator*() const { // All this work to do this 159 return Fn(*current); // little change 160 } 161 162 mapped_iterator &operator++() { 163 ++current; 164 return *this; 165 } 166 mapped_iterator &operator--() { 167 --current; 168 return *this; 169 } 170 mapped_iterator operator++(int) { 171 mapped_iterator __tmp = *this; 172 ++current; 173 return __tmp; 174 } 175 mapped_iterator operator--(int) { 176 mapped_iterator __tmp = *this; 177 --current; 178 return __tmp; 179 } 180 mapped_iterator operator+(difference_type n) const { 181 return mapped_iterator(current + n, Fn); 182 } 183 mapped_iterator &operator+=(difference_type n) { 184 current += n; 185 return *this; 186 } 187 mapped_iterator operator-(difference_type n) const { 188 return mapped_iterator(current - n, Fn); 189 } 190 mapped_iterator &operator-=(difference_type n) { 191 current -= n; 192 return *this; 193 } 194 reference operator[](difference_type n) const { return *(*this + n); } 195 196 bool operator!=(const mapped_iterator &X) const { return !operator==(X); } 197 bool operator==(const mapped_iterator &X) const { 198 return current == X.current; 199 } 200 bool operator<(const mapped_iterator &X) const { return current < X.current; } 201 202 difference_type operator-(const mapped_iterator &X) const { 203 return current - X.current; 204 } 205 }; 206 207 template <class Iterator, class Func> 208 inline mapped_iterator<Iterator, Func> 209 operator+(typename mapped_iterator<Iterator, Func>::difference_type N, 210 const mapped_iterator<Iterator, Func> &X) { 211 return mapped_iterator<Iterator, Func>(X.getCurrent() - N, X.getFunc()); 212 } 213 214 215 // map_iterator - Provide a convenient way to create mapped_iterators, just like 216 // make_pair is useful for creating pairs... 217 // 218 template <class ItTy, class FuncTy> 219 inline mapped_iterator<ItTy, FuncTy> map_iterator(const ItTy &I, FuncTy F) { 220 return mapped_iterator<ItTy, FuncTy>(I, F); 221 } 222 223 /// Helper to determine if type T has a member called rbegin(). 224 template <typename Ty> class has_rbegin_impl { 225 typedef char yes[1]; 226 typedef char no[2]; 227 228 template <typename Inner> 229 static yes& test(Inner *I, decltype(I->rbegin()) * = nullptr); 230 231 template <typename> 232 static no& test(...); 233 234 public: 235 static const bool value = sizeof(test<Ty>(nullptr)) == sizeof(yes); 236 }; 237 238 /// Metafunction to determine if T& or T has a member called rbegin(). 239 template <typename Ty> 240 struct has_rbegin : has_rbegin_impl<typename std::remove_reference<Ty>::type> { 241 }; 242 243 // Returns an iterator_range over the given container which iterates in reverse. 244 // Note that the container must have rbegin()/rend() methods for this to work. 245 template <typename ContainerTy> 246 auto reverse(ContainerTy &&C, 247 typename std::enable_if<has_rbegin<ContainerTy>::value>::type * = 248 nullptr) -> decltype(make_range(C.rbegin(), C.rend())) { 249 return make_range(C.rbegin(), C.rend()); 250 } 251 252 // Returns a std::reverse_iterator wrapped around the given iterator. 253 template <typename IteratorTy> 254 std::reverse_iterator<IteratorTy> make_reverse_iterator(IteratorTy It) { 255 return std::reverse_iterator<IteratorTy>(It); 256 } 257 258 // Returns an iterator_range over the given container which iterates in reverse. 259 // Note that the container must have begin()/end() methods which return 260 // bidirectional iterators for this to work. 261 template <typename ContainerTy> 262 auto reverse( 263 ContainerTy &&C, 264 typename std::enable_if<!has_rbegin<ContainerTy>::value>::type * = nullptr) 265 -> decltype(make_range(llvm::make_reverse_iterator(std::end(C)), 266 llvm::make_reverse_iterator(std::begin(C)))) { 267 return make_range(llvm::make_reverse_iterator(std::end(C)), 268 llvm::make_reverse_iterator(std::begin(C))); 269 } 270 271 /// An iterator adaptor that filters the elements of given inner iterators. 272 /// 273 /// The predicate parameter should be a callable object that accepts the wrapped 274 /// iterator's reference type and returns a bool. When incrementing or 275 /// decrementing the iterator, it will call the predicate on each element and 276 /// skip any where it returns false. 277 /// 278 /// \code 279 /// int A[] = { 1, 2, 3, 4 }; 280 /// auto R = make_filter_range(A, [](int N) { return N % 2 == 1; }); 281 /// // R contains { 1, 3 }. 282 /// \endcode 283 template <typename WrappedIteratorT, typename PredicateT> 284 class filter_iterator 285 : public iterator_adaptor_base< 286 filter_iterator<WrappedIteratorT, PredicateT>, WrappedIteratorT, 287 typename std::common_type< 288 std::forward_iterator_tag, 289 typename std::iterator_traits< 290 WrappedIteratorT>::iterator_category>::type> { 291 using BaseT = iterator_adaptor_base< 292 filter_iterator<WrappedIteratorT, PredicateT>, WrappedIteratorT, 293 typename std::common_type< 294 std::forward_iterator_tag, 295 typename std::iterator_traits<WrappedIteratorT>::iterator_category>:: 296 type>; 297 298 struct PayloadType { 299 WrappedIteratorT End; 300 PredicateT Pred; 301 }; 302 303 Optional<PayloadType> Payload; 304 305 void findNextValid() { 306 assert(Payload && "Payload should be engaged when findNextValid is called"); 307 while (this->I != Payload->End && !Payload->Pred(*this->I)) 308 BaseT::operator++(); 309 } 310 311 // Construct the begin iterator. The begin iterator requires to know where end 312 // is, so that it can properly stop when it hits end. 313 filter_iterator(WrappedIteratorT Begin, WrappedIteratorT End, PredicateT Pred) 314 : BaseT(std::move(Begin)), 315 Payload(PayloadType{std::move(End), std::move(Pred)}) { 316 findNextValid(); 317 } 318 319 // Construct the end iterator. It's not incrementable, so Payload doesn't 320 // have to be engaged. 321 filter_iterator(WrappedIteratorT End) : BaseT(End) {} 322 323 public: 324 using BaseT::operator++; 325 326 filter_iterator &operator++() { 327 BaseT::operator++(); 328 findNextValid(); 329 return *this; 330 } 331 332 template <typename RT, typename PT> 333 friend iterator_range<filter_iterator<detail::IterOfRange<RT>, PT>> 334 make_filter_range(RT &&, PT); 335 }; 336 337 /// Convenience function that takes a range of elements and a predicate, 338 /// and return a new filter_iterator range. 339 /// 340 /// FIXME: Currently if RangeT && is a rvalue reference to a temporary, the 341 /// lifetime of that temporary is not kept by the returned range object, and the 342 /// temporary is going to be dropped on the floor after the make_iterator_range 343 /// full expression that contains this function call. 344 template <typename RangeT, typename PredicateT> 345 iterator_range<filter_iterator<detail::IterOfRange<RangeT>, PredicateT>> 346 make_filter_range(RangeT &&Range, PredicateT Pred) { 347 using FilterIteratorT = 348 filter_iterator<detail::IterOfRange<RangeT>, PredicateT>; 349 return make_range(FilterIteratorT(std::begin(std::forward<RangeT>(Range)), 350 std::end(std::forward<RangeT>(Range)), 351 std::move(Pred)), 352 FilterIteratorT(std::end(std::forward<RangeT>(Range)))); 353 } 354 355 // forward declarations required by zip_shortest/zip_first 356 template <typename R, typename UnaryPredicate> 357 bool all_of(R &&range, UnaryPredicate P); 358 359 template <size_t... I> struct index_sequence; 360 361 template <class... Ts> struct index_sequence_for; 362 363 namespace detail { 364 using std::declval; 365 366 // We have to alias this since inlining the actual type at the usage site 367 // in the parameter list of iterator_facade_base<> below ICEs MSVC 2017. 368 template<typename... Iters> struct ZipTupleType { 369 typedef std::tuple<decltype(*declval<Iters>())...> type; 370 }; 371 372 template <typename ZipType, typename... Iters> 373 using zip_traits = iterator_facade_base< 374 ZipType, typename std::common_type<std::bidirectional_iterator_tag, 375 typename std::iterator_traits< 376 Iters>::iterator_category...>::type, 377 // ^ TODO: Implement random access methods. 378 typename ZipTupleType<Iters...>::type, 379 typename std::iterator_traits<typename std::tuple_element< 380 0, std::tuple<Iters...>>::type>::difference_type, 381 // ^ FIXME: This follows boost::make_zip_iterator's assumption that all 382 // inner iterators have the same difference_type. It would fail if, for 383 // instance, the second field's difference_type were non-numeric while the 384 // first is. 385 typename ZipTupleType<Iters...>::type *, 386 typename ZipTupleType<Iters...>::type>; 387 388 template <typename ZipType, typename... Iters> 389 struct zip_common : public zip_traits<ZipType, Iters...> { 390 using Base = zip_traits<ZipType, Iters...>; 391 using value_type = typename Base::value_type; 392 393 std::tuple<Iters...> iterators; 394 395 protected: 396 template <size_t... Ns> value_type deref(index_sequence<Ns...>) const { 397 return value_type(*std::get<Ns>(iterators)...); 398 } 399 400 template <size_t... Ns> 401 decltype(iterators) tup_inc(index_sequence<Ns...>) const { 402 return std::tuple<Iters...>(std::next(std::get<Ns>(iterators))...); 403 } 404 405 template <size_t... Ns> 406 decltype(iterators) tup_dec(index_sequence<Ns...>) const { 407 return std::tuple<Iters...>(std::prev(std::get<Ns>(iterators))...); 408 } 409 410 public: 411 zip_common(Iters &&... ts) : iterators(std::forward<Iters>(ts)...) {} 412 413 value_type operator*() { return deref(index_sequence_for<Iters...>{}); } 414 415 const value_type operator*() const { 416 return deref(index_sequence_for<Iters...>{}); 417 } 418 419 ZipType &operator++() { 420 iterators = tup_inc(index_sequence_for<Iters...>{}); 421 return *reinterpret_cast<ZipType *>(this); 422 } 423 424 ZipType &operator--() { 425 static_assert(Base::IsBidirectional, 426 "All inner iterators must be at least bidirectional."); 427 iterators = tup_dec(index_sequence_for<Iters...>{}); 428 return *reinterpret_cast<ZipType *>(this); 429 } 430 }; 431 432 template <typename... Iters> 433 struct zip_first : public zip_common<zip_first<Iters...>, Iters...> { 434 using Base = zip_common<zip_first<Iters...>, Iters...>; 435 436 bool operator==(const zip_first<Iters...> &other) const { 437 return std::get<0>(this->iterators) == std::get<0>(other.iterators); 438 } 439 440 zip_first(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {} 441 }; 442 443 template <typename... Iters> 444 class zip_shortest : public zip_common<zip_shortest<Iters...>, Iters...> { 445 template <size_t... Ns> 446 bool test(const zip_shortest<Iters...> &other, index_sequence<Ns...>) const { 447 return all_of(std::initializer_list<bool>{std::get<Ns>(this->iterators) != 448 std::get<Ns>(other.iterators)...}, 449 identity<bool>{}); 450 } 451 452 public: 453 using Base = zip_common<zip_shortest<Iters...>, Iters...>; 454 455 bool operator==(const zip_shortest<Iters...> &other) const { 456 return !test(other, index_sequence_for<Iters...>{}); 457 } 458 459 zip_shortest(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {} 460 }; 461 462 template <template <typename...> class ItType, typename... Args> class zippy { 463 public: 464 using iterator = ItType<decltype(std::begin(std::declval<Args>()))...>; 465 using iterator_category = typename iterator::iterator_category; 466 using value_type = typename iterator::value_type; 467 using difference_type = typename iterator::difference_type; 468 using pointer = typename iterator::pointer; 469 using reference = typename iterator::reference; 470 471 private: 472 std::tuple<Args...> ts; 473 474 template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) const { 475 return iterator(std::begin(std::get<Ns>(ts))...); 476 } 477 template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) const { 478 return iterator(std::end(std::get<Ns>(ts))...); 479 } 480 481 public: 482 iterator begin() const { return begin_impl(index_sequence_for<Args...>{}); } 483 iterator end() const { return end_impl(index_sequence_for<Args...>{}); } 484 zippy(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {} 485 }; 486 } // End detail namespace 487 488 /// zip iterator for two or more iteratable types. 489 template <typename T, typename U, typename... Args> 490 detail::zippy<detail::zip_shortest, T, U, Args...> zip(T &&t, U &&u, 491 Args &&... args) { 492 return detail::zippy<detail::zip_shortest, T, U, Args...>( 493 std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...); 494 } 495 496 /// zip iterator that, for the sake of efficiency, assumes the first iteratee to 497 /// be the shortest. 498 template <typename T, typename U, typename... Args> 499 detail::zippy<detail::zip_first, T, U, Args...> zip_first(T &&t, U &&u, 500 Args &&... args) { 501 return detail::zippy<detail::zip_first, T, U, Args...>( 502 std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...); 503 } 504 505 /// Iterator wrapper that concatenates sequences together. 506 /// 507 /// This can concatenate different iterators, even with different types, into 508 /// a single iterator provided the value types of all the concatenated 509 /// iterators expose `reference` and `pointer` types that can be converted to 510 /// `ValueT &` and `ValueT *` respectively. It doesn't support more 511 /// interesting/customized pointer or reference types. 512 /// 513 /// Currently this only supports forward or higher iterator categories as 514 /// inputs and always exposes a forward iterator interface. 515 template <typename ValueT, typename... IterTs> 516 class concat_iterator 517 : public iterator_facade_base<concat_iterator<ValueT, IterTs...>, 518 std::forward_iterator_tag, ValueT> { 519 typedef typename concat_iterator::iterator_facade_base BaseT; 520 521 /// We store both the current and end iterators for each concatenated 522 /// sequence in a tuple of pairs. 523 /// 524 /// Note that something like iterator_range seems nice at first here, but the 525 /// range properties are of little benefit and end up getting in the way 526 /// because we need to do mutation on the current iterators. 527 std::tuple<std::pair<IterTs, IterTs>...> IterPairs; 528 529 /// Attempts to increment a specific iterator. 530 /// 531 /// Returns true if it was able to increment the iterator. Returns false if 532 /// the iterator is already at the end iterator. 533 template <size_t Index> bool incrementHelper() { 534 auto &IterPair = std::get<Index>(IterPairs); 535 if (IterPair.first == IterPair.second) 536 return false; 537 538 ++IterPair.first; 539 return true; 540 } 541 542 /// Increments the first non-end iterator. 543 /// 544 /// It is an error to call this with all iterators at the end. 545 template <size_t... Ns> void increment(index_sequence<Ns...>) { 546 // Build a sequence of functions to increment each iterator if possible. 547 bool (concat_iterator::*IncrementHelperFns[])() = { 548 &concat_iterator::incrementHelper<Ns>...}; 549 550 // Loop over them, and stop as soon as we succeed at incrementing one. 551 for (auto &IncrementHelperFn : IncrementHelperFns) 552 if ((this->*IncrementHelperFn)()) 553 return; 554 555 llvm_unreachable("Attempted to increment an end concat iterator!"); 556 } 557 558 /// Returns null if the specified iterator is at the end. Otherwise, 559 /// dereferences the iterator and returns the address of the resulting 560 /// reference. 561 template <size_t Index> ValueT *getHelper() const { 562 auto &IterPair = std::get<Index>(IterPairs); 563 if (IterPair.first == IterPair.second) 564 return nullptr; 565 566 return &*IterPair.first; 567 } 568 569 /// Finds the first non-end iterator, dereferences, and returns the resulting 570 /// reference. 571 /// 572 /// It is an error to call this with all iterators at the end. 573 template <size_t... Ns> ValueT &get(index_sequence<Ns...>) const { 574 // Build a sequence of functions to get from iterator if possible. 575 ValueT *(concat_iterator::*GetHelperFns[])() const = { 576 &concat_iterator::getHelper<Ns>...}; 577 578 // Loop over them, and return the first result we find. 579 for (auto &GetHelperFn : GetHelperFns) 580 if (ValueT *P = (this->*GetHelperFn)()) 581 return *P; 582 583 llvm_unreachable("Attempted to get a pointer from an end concat iterator!"); 584 } 585 586 public: 587 /// Constructs an iterator from a squence of ranges. 588 /// 589 /// We need the full range to know how to switch between each of the 590 /// iterators. 591 template <typename... RangeTs> 592 explicit concat_iterator(RangeTs &&... Ranges) 593 : IterPairs({std::begin(Ranges), std::end(Ranges)}...) {} 594 595 using BaseT::operator++; 596 concat_iterator &operator++() { 597 increment(index_sequence_for<IterTs...>()); 598 return *this; 599 } 600 601 ValueT &operator*() const { return get(index_sequence_for<IterTs...>()); } 602 603 bool operator==(const concat_iterator &RHS) const { 604 return IterPairs == RHS.IterPairs; 605 } 606 }; 607 608 namespace detail { 609 /// Helper to store a sequence of ranges being concatenated and access them. 610 /// 611 /// This is designed to facilitate providing actual storage when temporaries 612 /// are passed into the constructor such that we can use it as part of range 613 /// based for loops. 614 template <typename ValueT, typename... RangeTs> class concat_range { 615 public: 616 typedef concat_iterator<ValueT, 617 decltype(std::begin(std::declval<RangeTs &>()))...> 618 iterator; 619 620 private: 621 std::tuple<RangeTs...> Ranges; 622 623 template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) { 624 return iterator(std::get<Ns>(Ranges)...); 625 } 626 template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) { 627 return iterator(make_range(std::end(std::get<Ns>(Ranges)), 628 std::end(std::get<Ns>(Ranges)))...); 629 } 630 631 public: 632 iterator begin() { return begin_impl(index_sequence_for<RangeTs...>{}); } 633 iterator end() { return end_impl(index_sequence_for<RangeTs...>{}); } 634 concat_range(RangeTs &&... Ranges) 635 : Ranges(std::forward<RangeTs>(Ranges)...) {} 636 }; 637 } 638 639 /// Concatenated range across two or more ranges. 640 /// 641 /// The desired value type must be explicitly specified. 642 template <typename ValueT, typename... RangeTs> 643 detail::concat_range<ValueT, RangeTs...> concat(RangeTs &&... Ranges) { 644 static_assert(sizeof...(RangeTs) > 1, 645 "Need more than one range to concatenate!"); 646 return detail::concat_range<ValueT, RangeTs...>( 647 std::forward<RangeTs>(Ranges)...); 648 } 649 650 //===----------------------------------------------------------------------===// 651 // Extra additions to <utility> 652 //===----------------------------------------------------------------------===// 653 654 /// \brief Function object to check whether the first component of a std::pair 655 /// compares less than the first component of another std::pair. 656 struct less_first { 657 template <typename T> bool operator()(const T &lhs, const T &rhs) const { 658 return lhs.first < rhs.first; 659 } 660 }; 661 662 /// \brief Function object to check whether the second component of a std::pair 663 /// compares less than the second component of another std::pair. 664 struct less_second { 665 template <typename T> bool operator()(const T &lhs, const T &rhs) const { 666 return lhs.second < rhs.second; 667 } 668 }; 669 670 // A subset of N3658. More stuff can be added as-needed. 671 672 /// \brief Represents a compile-time sequence of integers. 673 template <class T, T... I> struct integer_sequence { 674 typedef T value_type; 675 676 static constexpr size_t size() { return sizeof...(I); } 677 }; 678 679 /// \brief Alias for the common case of a sequence of size_ts. 680 template <size_t... I> 681 struct index_sequence : integer_sequence<std::size_t, I...> {}; 682 683 template <std::size_t N, std::size_t... I> 684 struct build_index_impl : build_index_impl<N - 1, N - 1, I...> {}; 685 template <std::size_t... I> 686 struct build_index_impl<0, I...> : index_sequence<I...> {}; 687 688 /// \brief Creates a compile-time integer sequence for a parameter pack. 689 template <class... Ts> 690 struct index_sequence_for : build_index_impl<sizeof...(Ts)> {}; 691 692 /// Utility type to build an inheritance chain that makes it easy to rank 693 /// overload candidates. 694 template <int N> struct rank : rank<N - 1> {}; 695 template <> struct rank<0> {}; 696 697 /// \brief traits class for checking whether type T is one of any of the given 698 /// types in the variadic list. 699 template <typename T, typename... Ts> struct is_one_of { 700 static const bool value = false; 701 }; 702 703 template <typename T, typename U, typename... Ts> 704 struct is_one_of<T, U, Ts...> { 705 static const bool value = 706 std::is_same<T, U>::value || is_one_of<T, Ts...>::value; 707 }; 708 709 /// \brief traits class for checking whether type T is a base class for all 710 /// the given types in the variadic list. 711 template <typename T, typename... Ts> struct are_base_of { 712 static const bool value = true; 713 }; 714 715 template <typename T, typename U, typename... Ts> 716 struct are_base_of<T, U, Ts...> { 717 static const bool value = 718 std::is_base_of<T, U>::value && are_base_of<T, Ts...>::value; 719 }; 720 721 //===----------------------------------------------------------------------===// 722 // Extra additions for arrays 723 //===----------------------------------------------------------------------===// 724 725 /// Find the length of an array. 726 template <class T, std::size_t N> 727 constexpr inline size_t array_lengthof(T (&)[N]) { 728 return N; 729 } 730 731 /// Adapt std::less<T> for array_pod_sort. 732 template<typename T> 733 inline int array_pod_sort_comparator(const void *P1, const void *P2) { 734 if (std::less<T>()(*reinterpret_cast<const T*>(P1), 735 *reinterpret_cast<const T*>(P2))) 736 return -1; 737 if (std::less<T>()(*reinterpret_cast<const T*>(P2), 738 *reinterpret_cast<const T*>(P1))) 739 return 1; 740 return 0; 741 } 742 743 /// get_array_pod_sort_comparator - This is an internal helper function used to 744 /// get type deduction of T right. 745 template<typename T> 746 inline int (*get_array_pod_sort_comparator(const T &)) 747 (const void*, const void*) { 748 return array_pod_sort_comparator<T>; 749 } 750 751 752 /// array_pod_sort - This sorts an array with the specified start and end 753 /// extent. This is just like std::sort, except that it calls qsort instead of 754 /// using an inlined template. qsort is slightly slower than std::sort, but 755 /// most sorts are not performance critical in LLVM and std::sort has to be 756 /// template instantiated for each type, leading to significant measured code 757 /// bloat. This function should generally be used instead of std::sort where 758 /// possible. 759 /// 760 /// This function assumes that you have simple POD-like types that can be 761 /// compared with std::less and can be moved with memcpy. If this isn't true, 762 /// you should use std::sort. 763 /// 764 /// NOTE: If qsort_r were portable, we could allow a custom comparator and 765 /// default to std::less. 766 template<class IteratorTy> 767 inline void array_pod_sort(IteratorTy Start, IteratorTy End) { 768 // Don't inefficiently call qsort with one element or trigger undefined 769 // behavior with an empty sequence. 770 auto NElts = End - Start; 771 if (NElts <= 1) return; 772 qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start)); 773 } 774 775 template <class IteratorTy> 776 inline void array_pod_sort( 777 IteratorTy Start, IteratorTy End, 778 int (*Compare)( 779 const typename std::iterator_traits<IteratorTy>::value_type *, 780 const typename std::iterator_traits<IteratorTy>::value_type *)) { 781 // Don't inefficiently call qsort with one element or trigger undefined 782 // behavior with an empty sequence. 783 auto NElts = End - Start; 784 if (NElts <= 1) return; 785 qsort(&*Start, NElts, sizeof(*Start), 786 reinterpret_cast<int (*)(const void *, const void *)>(Compare)); 787 } 788 789 //===----------------------------------------------------------------------===// 790 // Extra additions to <algorithm> 791 //===----------------------------------------------------------------------===// 792 793 /// For a container of pointers, deletes the pointers and then clears the 794 /// container. 795 template<typename Container> 796 void DeleteContainerPointers(Container &C) { 797 for (auto V : C) 798 delete V; 799 C.clear(); 800 } 801 802 /// In a container of pairs (usually a map) whose second element is a pointer, 803 /// deletes the second elements and then clears the container. 804 template<typename Container> 805 void DeleteContainerSeconds(Container &C) { 806 for (auto &V : C) 807 delete V.second; 808 C.clear(); 809 } 810 811 /// Provide wrappers to std::all_of which take ranges instead of having to pass 812 /// begin/end explicitly. 813 template <typename R, typename UnaryPredicate> 814 bool all_of(R &&Range, UnaryPredicate P) { 815 return std::all_of(std::begin(Range), std::end(Range), P); 816 } 817 818 /// Provide wrappers to std::any_of which take ranges instead of having to pass 819 /// begin/end explicitly. 820 template <typename R, typename UnaryPredicate> 821 bool any_of(R &&Range, UnaryPredicate P) { 822 return std::any_of(std::begin(Range), std::end(Range), P); 823 } 824 825 /// Provide wrappers to std::none_of which take ranges instead of having to pass 826 /// begin/end explicitly. 827 template <typename R, typename UnaryPredicate> 828 bool none_of(R &&Range, UnaryPredicate P) { 829 return std::none_of(std::begin(Range), std::end(Range), P); 830 } 831 832 /// Provide wrappers to std::find which take ranges instead of having to pass 833 /// begin/end explicitly. 834 template <typename R, typename T> 835 auto find(R &&Range, const T &Val) -> decltype(std::begin(Range)) { 836 return std::find(std::begin(Range), std::end(Range), Val); 837 } 838 839 /// Provide wrappers to std::find_if which take ranges instead of having to pass 840 /// begin/end explicitly. 841 template <typename R, typename UnaryPredicate> 842 auto find_if(R &&Range, UnaryPredicate P) -> decltype(std::begin(Range)) { 843 return std::find_if(std::begin(Range), std::end(Range), P); 844 } 845 846 template <typename R, typename UnaryPredicate> 847 auto find_if_not(R &&Range, UnaryPredicate P) -> decltype(std::begin(Range)) { 848 return std::find_if_not(std::begin(Range), std::end(Range), P); 849 } 850 851 /// Provide wrappers to std::remove_if which take ranges instead of having to 852 /// pass begin/end explicitly. 853 template <typename R, typename UnaryPredicate> 854 auto remove_if(R &&Range, UnaryPredicate P) -> decltype(std::begin(Range)) { 855 return std::remove_if(std::begin(Range), std::end(Range), P); 856 } 857 858 /// Provide wrappers to std::copy_if which take ranges instead of having to 859 /// pass begin/end explicitly. 860 template <typename R, typename OutputIt, typename UnaryPredicate> 861 OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P) { 862 return std::copy_if(std::begin(Range), std::end(Range), Out, P); 863 } 864 865 /// Wrapper function around std::find to detect if an element exists 866 /// in a container. 867 template <typename R, typename E> 868 bool is_contained(R &&Range, const E &Element) { 869 return std::find(std::begin(Range), std::end(Range), Element) != 870 std::end(Range); 871 } 872 873 /// Wrapper function around std::count to count the number of times an element 874 /// \p Element occurs in the given range \p Range. 875 template <typename R, typename E> 876 auto count(R &&Range, const E &Element) -> typename std::iterator_traits< 877 decltype(std::begin(Range))>::difference_type { 878 return std::count(std::begin(Range), std::end(Range), Element); 879 } 880 881 /// Wrapper function around std::count_if to count the number of times an 882 /// element satisfying a given predicate occurs in a range. 883 template <typename R, typename UnaryPredicate> 884 auto count_if(R &&Range, UnaryPredicate P) -> typename std::iterator_traits< 885 decltype(std::begin(Range))>::difference_type { 886 return std::count_if(std::begin(Range), std::end(Range), P); 887 } 888 889 /// Wrapper function around std::transform to apply a function to a range and 890 /// store the result elsewhere. 891 template <typename R, typename OutputIt, typename UnaryPredicate> 892 OutputIt transform(R &&Range, OutputIt d_first, UnaryPredicate P) { 893 return std::transform(std::begin(Range), std::end(Range), d_first, P); 894 } 895 896 /// Provide wrappers to std::partition which take ranges instead of having to 897 /// pass begin/end explicitly. 898 template <typename R, typename UnaryPredicate> 899 auto partition(R &&Range, UnaryPredicate P) -> decltype(std::begin(Range)) { 900 return std::partition(std::begin(Range), std::end(Range), P); 901 } 902 903 /// \brief Given a range of type R, iterate the entire range and return a 904 /// SmallVector with elements of the vector. This is useful, for example, 905 /// when you want to iterate a range and then sort the results. 906 template <unsigned Size, typename R> 907 SmallVector<typename std::remove_const<detail::ValueOfRange<R>>::type, Size> 908 to_vector(R &&Range) { 909 return {std::begin(Range), std::end(Range)}; 910 } 911 912 /// Provide a container algorithm similar to C++ Library Fundamentals v2's 913 /// `erase_if` which is equivalent to: 914 /// 915 /// C.erase(remove_if(C, pred), C.end()); 916 /// 917 /// This version works for any container with an erase method call accepting 918 /// two iterators. 919 template <typename Container, typename UnaryPredicate> 920 void erase_if(Container &C, UnaryPredicate P) { 921 C.erase(remove_if(C, P), C.end()); 922 } 923 924 //===----------------------------------------------------------------------===// 925 // Extra additions to <memory> 926 //===----------------------------------------------------------------------===// 927 928 // Implement make_unique according to N3656. 929 930 /// \brief Constructs a `new T()` with the given args and returns a 931 /// `unique_ptr<T>` which owns the object. 932 /// 933 /// Example: 934 /// 935 /// auto p = make_unique<int>(); 936 /// auto p = make_unique<std::tuple<int, int>>(0, 1); 937 template <class T, class... Args> 938 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type 939 make_unique(Args &&... args) { 940 return std::unique_ptr<T>(new T(std::forward<Args>(args)...)); 941 } 942 943 /// \brief Constructs a `new T[n]` with the given args and returns a 944 /// `unique_ptr<T[]>` which owns the object. 945 /// 946 /// \param n size of the new array. 947 /// 948 /// Example: 949 /// 950 /// auto p = make_unique<int[]>(2); // value-initializes the array with 0's. 951 template <class T> 952 typename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0, 953 std::unique_ptr<T>>::type 954 make_unique(size_t n) { 955 return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]()); 956 } 957 958 /// This function isn't used and is only here to provide better compile errors. 959 template <class T, class... Args> 960 typename std::enable_if<std::extent<T>::value != 0>::type 961 make_unique(Args &&...) = delete; 962 963 struct FreeDeleter { 964 void operator()(void* v) { 965 ::free(v); 966 } 967 }; 968 969 template<typename First, typename Second> 970 struct pair_hash { 971 size_t operator()(const std::pair<First, Second> &P) const { 972 return std::hash<First>()(P.first) * 31 + std::hash<Second>()(P.second); 973 } 974 }; 975 976 /// A functor like C++14's std::less<void> in its absence. 977 struct less { 978 template <typename A, typename B> bool operator()(A &&a, B &&b) const { 979 return std::forward<A>(a) < std::forward<B>(b); 980 } 981 }; 982 983 /// A functor like C++14's std::equal<void> in its absence. 984 struct equal { 985 template <typename A, typename B> bool operator()(A &&a, B &&b) const { 986 return std::forward<A>(a) == std::forward<B>(b); 987 } 988 }; 989 990 /// Binary functor that adapts to any other binary functor after dereferencing 991 /// operands. 992 template <typename T> struct deref { 993 T func; 994 // Could be further improved to cope with non-derivable functors and 995 // non-binary functors (should be a variadic template member function 996 // operator()). 997 template <typename A, typename B> 998 auto operator()(A &lhs, B &rhs) const -> decltype(func(*lhs, *rhs)) { 999 assert(lhs); 1000 assert(rhs); 1001 return func(*lhs, *rhs); 1002 } 1003 }; 1004 1005 namespace detail { 1006 template <typename R> class enumerator_iter; 1007 1008 template <typename R> struct result_pair { 1009 friend class enumerator_iter<R>; 1010 1011 result_pair() : Index(-1) {} 1012 result_pair(std::size_t Index, IterOfRange<R> Iter) 1013 : Index(Index), Iter(Iter) {} 1014 1015 result_pair<R> &operator=(const result_pair<R> &Other) { 1016 Index = Other.Index; 1017 Iter = Other.Iter; 1018 return *this; 1019 } 1020 1021 std::size_t index() const { return Index; } 1022 const ValueOfRange<R> &value() const { return *Iter; } 1023 ValueOfRange<R> &value() { return *Iter; } 1024 1025 private: 1026 std::size_t Index; 1027 IterOfRange<R> Iter; 1028 }; 1029 1030 template <typename R> 1031 class enumerator_iter 1032 : public iterator_facade_base< 1033 enumerator_iter<R>, std::forward_iterator_tag, result_pair<R>, 1034 typename std::iterator_traits<IterOfRange<R>>::difference_type, 1035 typename std::iterator_traits<IterOfRange<R>>::pointer, 1036 typename std::iterator_traits<IterOfRange<R>>::reference> { 1037 using result_type = result_pair<R>; 1038 1039 public: 1040 explicit enumerator_iter(IterOfRange<R> EndIter) 1041 : Result(std::numeric_limits<size_t>::max(), EndIter) { } 1042 1043 enumerator_iter(std::size_t Index, IterOfRange<R> Iter) 1044 : Result(Index, Iter) {} 1045 1046 result_type &operator*() { return Result; } 1047 const result_type &operator*() const { return Result; } 1048 1049 enumerator_iter<R> &operator++() { 1050 assert(Result.Index != std::numeric_limits<size_t>::max()); 1051 ++Result.Iter; 1052 ++Result.Index; 1053 return *this; 1054 } 1055 1056 bool operator==(const enumerator_iter<R> &RHS) const { 1057 // Don't compare indices here, only iterators. It's possible for an end 1058 // iterator to have different indices depending on whether it was created 1059 // by calling std::end() versus incrementing a valid iterator. 1060 return Result.Iter == RHS.Result.Iter; 1061 } 1062 1063 enumerator_iter<R> &operator=(const enumerator_iter<R> &Other) { 1064 Result = Other.Result; 1065 return *this; 1066 } 1067 1068 private: 1069 result_type Result; 1070 }; 1071 1072 template <typename R> class enumerator { 1073 public: 1074 explicit enumerator(R &&Range) : TheRange(std::forward<R>(Range)) {} 1075 1076 enumerator_iter<R> begin() { 1077 return enumerator_iter<R>(0, std::begin(TheRange)); 1078 } 1079 enumerator_iter<R> end() { 1080 return enumerator_iter<R>(std::end(TheRange)); 1081 } 1082 1083 private: 1084 R TheRange; 1085 }; 1086 } 1087 1088 /// Given an input range, returns a new range whose values are are pair (A,B) 1089 /// such that A is the 0-based index of the item in the sequence, and B is 1090 /// the value from the original sequence. Example: 1091 /// 1092 /// std::vector<char> Items = {'A', 'B', 'C', 'D'}; 1093 /// for (auto X : enumerate(Items)) { 1094 /// printf("Item %d - %c\n", X.index(), X.value()); 1095 /// } 1096 /// 1097 /// Output: 1098 /// Item 0 - A 1099 /// Item 1 - B 1100 /// Item 2 - C 1101 /// Item 3 - D 1102 /// 1103 template <typename R> detail::enumerator<R> enumerate(R &&TheRange) { 1104 return detail::enumerator<R>(std::forward<R>(TheRange)); 1105 } 1106 1107 namespace detail { 1108 template <typename F, typename Tuple, std::size_t... I> 1109 auto apply_tuple_impl(F &&f, Tuple &&t, index_sequence<I...>) 1110 -> decltype(std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...)) { 1111 return std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...); 1112 } 1113 } 1114 1115 /// Given an input tuple (a1, a2, ..., an), pass the arguments of the 1116 /// tuple variadically to f as if by calling f(a1, a2, ..., an) and 1117 /// return the result. 1118 template <typename F, typename Tuple> 1119 auto apply_tuple(F &&f, Tuple &&t) -> decltype(detail::apply_tuple_impl( 1120 std::forward<F>(f), std::forward<Tuple>(t), 1121 build_index_impl< 1122 std::tuple_size<typename std::decay<Tuple>::type>::value>{})) { 1123 using Indices = build_index_impl< 1124 std::tuple_size<typename std::decay<Tuple>::type>::value>; 1125 1126 return detail::apply_tuple_impl(std::forward<F>(f), std::forward<Tuple>(t), 1127 Indices{}); 1128 } 1129 } // End llvm namespace 1130 1131 #endif 1132