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 35namespace 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. 39template <typename T, T> struct SameType; 40 41namespace detail { 42 43template <typename RangeT> 44using IterOfRange = decltype(std::begin(std::declval<RangeT &>())); 45 46} // End detail namespace 47 48//===----------------------------------------------------------------------===// 49// Extra additions to <functional> 50//===----------------------------------------------------------------------===// 51 52template<class Ty> 53struct 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 62template<class Ty> 63struct 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 69template<class Ty> 70struct 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. 82template<typename Fn> class function_ref; 83 84template<typename Ret, typename ...Params> 85class 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 95public: 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// 113template <class T> 114inline 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// 127template <class RootIt, class UnaryFunc> 128class mapped_iterator { 129 RootIt current; 130 UnaryFunc Fn; 131public: 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 201template <class Iterator, class Func> 202inline mapped_iterator<Iterator, Func> 203operator+(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// 212template <class ItTy, class FuncTy> 213inline 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(). 218template <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 228public: 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(). 233template <typename Ty> 234struct 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. 239template <typename ContainerTy> 240auto 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. 247template <typename IteratorTy> 248std::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. 255template <typename ContainerTy> 256auto 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 277template <typename WrappedIteratorT, typename PredicateT> 278class 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 317public: 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. 338template <typename RangeT, typename PredicateT> 339iterator_range<filter_iterator<detail::IterOfRange<RangeT>, PredicateT>> 340make_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 350template <typename R, typename UnaryPredicate> 351bool all_of(R &&range, UnaryPredicate P); 352 353template <size_t... I> struct index_sequence; 354 355template <class... Ts> struct index_sequence_for; 356 357namespace detail { 358template <typename... Iters> class zip_first { 359public: 360 typedef std::input_iterator_tag iterator_category; 361 typedef std::tuple<decltype(*std::declval<Iters>())...> value_type; 362 std::tuple<Iters...> iterators; 363 364private: 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 373public: 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 384template <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 392public: 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 400template <template <typename...> class ItType, typename... Args> class zippy { 401public: 402 typedef ItType<decltype(std::begin(std::declval<Args>()))...> iterator; 403 404private: 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 414public: 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. 422template <typename T, typename U, typename... Args> 423detail::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. 431template <typename T, typename U, typename... Args> 432detail::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. 444struct 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. 452struct 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. 461template <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. 468template <size_t... I> 469struct index_sequence : integer_sequence<std::size_t, I...> {}; 470 471template <std::size_t N, std::size_t... I> 472struct build_index_impl : build_index_impl<N - 1, N - 1, I...> {}; 473template <std::size_t... I> 474struct build_index_impl<0, I...> : index_sequence<I...> {}; 475 476/// \brief Creates a compile-time integer sequence for a parameter pack. 477template <class... Ts> 478struct 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. 482template <int N> struct rank : rank<N - 1> {}; 483template <> 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. 487template <typename T, typename... Ts> struct is_one_of { 488 static const bool value = false; 489}; 490 491template <typename T, typename U, typename... Ts> 492struct 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. 502template <class T, std::size_t N> 503constexpr inline size_t array_lengthof(T (&)[N]) { 504 return N; 505} 506 507/// Adapt std::less<T> for array_pod_sort. 508template<typename T> 509inline 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. 521template<typename T> 522inline 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. 542template<class IteratorTy> 543inline 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 551template <class IteratorTy> 552inline 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. 571template<typename Container> 572void 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. 580template<typename Container> 581void 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. 589template <typename R, typename UnaryPredicate> 590bool 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. 596template <typename R, typename UnaryPredicate> 597bool 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. 603template <typename R, typename UnaryPredicate> 604bool 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. 610template <typename R, typename T> 611auto 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. 617template <typename R, typename UnaryPredicate> 618auto find_if(R &&Range, UnaryPredicate P) -> decltype(std::begin(Range)) { 619 return std::find_if(std::begin(Range), std::end(Range), P); 620} 621 622template <typename R, typename UnaryPredicate> 623auto 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. 629template <typename R, typename UnaryPredicate> 630auto 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. 636template <typename R, typename E> 637bool 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. 644template <typename R, typename E> 645auto 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. 652template <typename R, typename UnaryPredicate> 653auto 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. 660template <typename R, typename OutputIt, typename UnaryPredicate> 661OutputIt 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); 678template <class T, class... Args> 679typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type 680make_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. 692template <class T> 693typename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0, 694 std::unique_ptr<T>>::type 695make_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. 700template <class T, class... Args> 701typename std::enable_if<std::extent<T>::value != 0>::type 702make_unique(Args &&...) = delete; 703 704struct FreeDeleter { 705 void operator()(void* v) { 706 ::free(v); 707 } 708}; 709 710template<typename First, typename Second> 711struct 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. 718struct 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. 725struct 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. 733template <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 746namespace detail { 747template <typename R> class enumerator_impl { 748public: 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 780public: 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 786private: 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/// 806template <typename R> detail::enumerator_impl<R> enumerate(R &&Range) { 807 return detail::enumerator_impl<R>(std::forward<R>(Range)); 808} 809 810namespace detail { 811template <typename F, typename Tuple, std::size_t... I> 812auto 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. 821template <typename F, typename Tuple> 822auto 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