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