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 "llvm/Support/Compiler.h" 21 #include <cassert> 22 #include <cstddef> // for std::size_t 23 #include <cstdlib> // for qsort 24 #include <functional> 25 #include <iterator> 26 #include <memory> 27 #include <utility> // for std::pair 28 29 namespace llvm { 30 31 //===----------------------------------------------------------------------===// 32 // Extra additions to <functional> 33 //===----------------------------------------------------------------------===// 34 35 template<class Ty> 36 struct identity : public std::unary_function<Ty, Ty> { 37 Ty &operator()(Ty &self) const { 38 return self; 39 } 40 const Ty &operator()(const Ty &self) const { 41 return self; 42 } 43 }; 44 45 template<class Ty> 46 struct less_ptr : public std::binary_function<Ty, Ty, bool> { 47 bool operator()(const Ty* left, const Ty* right) const { 48 return *left < *right; 49 } 50 }; 51 52 template<class Ty> 53 struct greater_ptr : public std::binary_function<Ty, Ty, bool> { 54 bool operator()(const Ty* left, const Ty* right) const { 55 return *right < *left; 56 } 57 }; 58 59 /// An efficient, type-erasing, non-owning reference to a callable. This is 60 /// intended for use as the type of a function parameter that is not used 61 /// after the function in question returns. 62 /// 63 /// This class does not own the callable, so it is not in general safe to store 64 /// a function_ref. 65 template<typename Fn> class function_ref; 66 67 template<typename Ret, typename ...Params> 68 class function_ref<Ret(Params...)> { 69 Ret (*callback)(intptr_t callable, Params ...params); 70 intptr_t callable; 71 72 template<typename Callable> 73 static Ret callback_fn(intptr_t callable, Params ...params) { 74 return (*reinterpret_cast<Callable*>(callable))( 75 std::forward<Params>(params)...); 76 } 77 78 public: 79 template <typename Callable> 80 function_ref(Callable &&callable, 81 typename std::enable_if< 82 !std::is_same<typename std::remove_reference<Callable>::type, 83 function_ref>::value>::type * = nullptr) 84 : callback(callback_fn<typename std::remove_reference<Callable>::type>), 85 callable(reinterpret_cast<intptr_t>(&callable)) {} 86 Ret operator()(Params ...params) const { 87 return callback(callable, std::forward<Params>(params)...); 88 } 89 }; 90 91 // deleter - Very very very simple method that is used to invoke operator 92 // delete on something. It is used like this: 93 // 94 // for_each(V.begin(), B.end(), deleter<Interval>); 95 // 96 template <class T> 97 inline void deleter(T *Ptr) { 98 delete Ptr; 99 } 100 101 102 103 //===----------------------------------------------------------------------===// 104 // Extra additions to <iterator> 105 //===----------------------------------------------------------------------===// 106 107 // mapped_iterator - This is a simple iterator adapter that causes a function to 108 // be dereferenced whenever operator* is invoked on the iterator. 109 // 110 template <class RootIt, class UnaryFunc> 111 class mapped_iterator { 112 RootIt current; 113 UnaryFunc Fn; 114 public: 115 typedef typename std::iterator_traits<RootIt>::iterator_category 116 iterator_category; 117 typedef typename std::iterator_traits<RootIt>::difference_type 118 difference_type; 119 typedef typename UnaryFunc::result_type value_type; 120 121 typedef void pointer; 122 //typedef typename UnaryFunc::result_type *pointer; 123 typedef void reference; // Can't modify value returned by fn 124 125 typedef RootIt iterator_type; 126 127 inline const RootIt &getCurrent() const { return current; } 128 inline const UnaryFunc &getFunc() const { return Fn; } 129 130 inline explicit mapped_iterator(const RootIt &I, UnaryFunc F) 131 : current(I), Fn(F) {} 132 133 inline value_type operator*() const { // All this work to do this 134 return Fn(*current); // little change 135 } 136 137 mapped_iterator &operator++() { 138 ++current; 139 return *this; 140 } 141 mapped_iterator &operator--() { 142 --current; 143 return *this; 144 } 145 mapped_iterator operator++(int) { 146 mapped_iterator __tmp = *this; 147 ++current; 148 return __tmp; 149 } 150 mapped_iterator operator--(int) { 151 mapped_iterator __tmp = *this; 152 --current; 153 return __tmp; 154 } 155 mapped_iterator operator+(difference_type n) const { 156 return mapped_iterator(current + n, Fn); 157 } 158 mapped_iterator &operator+=(difference_type n) { 159 current += n; 160 return *this; 161 } 162 mapped_iterator operator-(difference_type n) const { 163 return mapped_iterator(current - n, Fn); 164 } 165 mapped_iterator &operator-=(difference_type n) { 166 current -= n; 167 return *this; 168 } 169 reference operator[](difference_type n) const { return *(*this + n); } 170 171 bool operator!=(const mapped_iterator &X) const { return !operator==(X); } 172 bool operator==(const mapped_iterator &X) const { 173 return current == X.current; 174 } 175 bool operator<(const mapped_iterator &X) const { return current < X.current; } 176 177 difference_type operator-(const mapped_iterator &X) const { 178 return current - X.current; 179 } 180 }; 181 182 template <class Iterator, class Func> 183 inline mapped_iterator<Iterator, Func> 184 operator+(typename mapped_iterator<Iterator, Func>::difference_type N, 185 const mapped_iterator<Iterator, Func> &X) { 186 return mapped_iterator<Iterator, Func>(X.getCurrent() - N, X.getFunc()); 187 } 188 189 190 // map_iterator - Provide a convenient way to create mapped_iterators, just like 191 // make_pair is useful for creating pairs... 192 // 193 template <class ItTy, class FuncTy> 194 inline mapped_iterator<ItTy, FuncTy> map_iterator(const ItTy &I, FuncTy F) { 195 return mapped_iterator<ItTy, FuncTy>(I, F); 196 } 197 198 //===----------------------------------------------------------------------===// 199 // Extra additions to <utility> 200 //===----------------------------------------------------------------------===// 201 202 /// \brief Function object to check whether the first component of a std::pair 203 /// compares less than the first component of another std::pair. 204 struct less_first { 205 template <typename T> bool operator()(const T &lhs, const T &rhs) const { 206 return lhs.first < rhs.first; 207 } 208 }; 209 210 /// \brief Function object to check whether the second component of a std::pair 211 /// compares less than the second component of another std::pair. 212 struct less_second { 213 template <typename T> bool operator()(const T &lhs, const T &rhs) const { 214 return lhs.second < rhs.second; 215 } 216 }; 217 218 // A subset of N3658. More stuff can be added as-needed. 219 220 /// \brief Represents a compile-time sequence of integers. 221 template <class T, T... I> struct integer_sequence { 222 typedef T value_type; 223 224 static LLVM_CONSTEXPR size_t size() { return sizeof...(I); } 225 }; 226 227 /// \brief Alias for the common case of a sequence of size_ts. 228 template <size_t... I> 229 struct index_sequence : integer_sequence<std::size_t, I...> {}; 230 231 template <std::size_t N, std::size_t... I> 232 struct build_index_impl : build_index_impl<N - 1, N - 1, I...> {}; 233 template <std::size_t... I> 234 struct build_index_impl<0, I...> : index_sequence<I...> {}; 235 236 /// \brief Creates a compile-time integer sequence for a parameter pack. 237 template <class... Ts> 238 struct index_sequence_for : build_index_impl<sizeof...(Ts)> {}; 239 240 //===----------------------------------------------------------------------===// 241 // Extra additions for arrays 242 //===----------------------------------------------------------------------===// 243 244 /// Find the length of an array. 245 template <class T, std::size_t N> 246 LLVM_CONSTEXPR inline size_t array_lengthof(T (&)[N]) { 247 return N; 248 } 249 250 /// Adapt std::less<T> for array_pod_sort. 251 template<typename T> 252 inline int array_pod_sort_comparator(const void *P1, const void *P2) { 253 if (std::less<T>()(*reinterpret_cast<const T*>(P1), 254 *reinterpret_cast<const T*>(P2))) 255 return -1; 256 if (std::less<T>()(*reinterpret_cast<const T*>(P2), 257 *reinterpret_cast<const T*>(P1))) 258 return 1; 259 return 0; 260 } 261 262 /// get_array_pod_sort_comparator - This is an internal helper function used to 263 /// get type deduction of T right. 264 template<typename T> 265 inline int (*get_array_pod_sort_comparator(const T &)) 266 (const void*, const void*) { 267 return array_pod_sort_comparator<T>; 268 } 269 270 271 /// array_pod_sort - This sorts an array with the specified start and end 272 /// extent. This is just like std::sort, except that it calls qsort instead of 273 /// using an inlined template. qsort is slightly slower than std::sort, but 274 /// most sorts are not performance critical in LLVM and std::sort has to be 275 /// template instantiated for each type, leading to significant measured code 276 /// bloat. This function should generally be used instead of std::sort where 277 /// possible. 278 /// 279 /// This function assumes that you have simple POD-like types that can be 280 /// compared with std::less and can be moved with memcpy. If this isn't true, 281 /// you should use std::sort. 282 /// 283 /// NOTE: If qsort_r were portable, we could allow a custom comparator and 284 /// default to std::less. 285 template<class IteratorTy> 286 inline void array_pod_sort(IteratorTy Start, IteratorTy End) { 287 // Don't inefficiently call qsort with one element or trigger undefined 288 // behavior with an empty sequence. 289 auto NElts = End - Start; 290 if (NElts <= 1) return; 291 qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start)); 292 } 293 294 template <class IteratorTy> 295 inline void array_pod_sort( 296 IteratorTy Start, IteratorTy End, 297 int (*Compare)( 298 const typename std::iterator_traits<IteratorTy>::value_type *, 299 const typename std::iterator_traits<IteratorTy>::value_type *)) { 300 // Don't inefficiently call qsort with one element or trigger undefined 301 // behavior with an empty sequence. 302 auto NElts = End - Start; 303 if (NElts <= 1) return; 304 qsort(&*Start, NElts, sizeof(*Start), 305 reinterpret_cast<int (*)(const void *, const void *)>(Compare)); 306 } 307 308 //===----------------------------------------------------------------------===// 309 // Extra additions to <algorithm> 310 //===----------------------------------------------------------------------===// 311 312 /// For a container of pointers, deletes the pointers and then clears the 313 /// container. 314 template<typename Container> 315 void DeleteContainerPointers(Container &C) { 316 for (typename Container::iterator I = C.begin(), E = C.end(); I != E; ++I) 317 delete *I; 318 C.clear(); 319 } 320 321 /// In a container of pairs (usually a map) whose second element is a pointer, 322 /// deletes the second elements and then clears the container. 323 template<typename Container> 324 void DeleteContainerSeconds(Container &C) { 325 for (typename Container::iterator I = C.begin(), E = C.end(); I != E; ++I) 326 delete I->second; 327 C.clear(); 328 } 329 330 //===----------------------------------------------------------------------===// 331 // Extra additions to <memory> 332 //===----------------------------------------------------------------------===// 333 334 // Implement make_unique according to N3656. 335 336 /// \brief Constructs a `new T()` with the given args and returns a 337 /// `unique_ptr<T>` which owns the object. 338 /// 339 /// Example: 340 /// 341 /// auto p = make_unique<int>(); 342 /// auto p = make_unique<std::tuple<int, int>>(0, 1); 343 template <class T, class... Args> 344 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type 345 make_unique(Args &&... args) { 346 return std::unique_ptr<T>(new T(std::forward<Args>(args)...)); 347 } 348 349 /// \brief Constructs a `new T[n]` with the given args and returns a 350 /// `unique_ptr<T[]>` which owns the object. 351 /// 352 /// \param n size of the new array. 353 /// 354 /// Example: 355 /// 356 /// auto p = make_unique<int[]>(2); // value-initializes the array with 0's. 357 template <class T> 358 typename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0, 359 std::unique_ptr<T>>::type 360 make_unique(size_t n) { 361 return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]()); 362 } 363 364 /// This function isn't used and is only here to provide better compile errors. 365 template <class T, class... Args> 366 typename std::enable_if<std::extent<T>::value != 0>::type 367 make_unique(Args &&...) = delete; 368 369 struct FreeDeleter { 370 void operator()(void* v) { 371 ::free(v); 372 } 373 }; 374 375 template<typename First, typename Second> 376 struct pair_hash { 377 size_t operator()(const std::pair<First, Second> &P) const { 378 return std::hash<First>()(P.first) * 31 + std::hash<Second>()(P.second); 379 } 380 }; 381 382 /// A functor like C++14's std::less<void> in its absence. 383 struct less { 384 template <typename A, typename B> bool operator()(A &&a, B &&b) const { 385 return std::forward<A>(a) < std::forward<B>(b); 386 } 387 }; 388 389 /// A functor like C++14's std::equal<void> in its absence. 390 struct equal { 391 template <typename A, typename B> bool operator()(A &&a, B &&b) const { 392 return std::forward<A>(a) == std::forward<B>(b); 393 } 394 }; 395 396 /// Binary functor that adapts to any other binary functor after dereferencing 397 /// operands. 398 template <typename T> struct deref { 399 T func; 400 // Could be further improved to cope with non-derivable functors and 401 // non-binary functors (should be a variadic template member function 402 // operator()). 403 template <typename A, typename B> 404 auto operator()(A &lhs, B &rhs) const -> decltype(func(*lhs, *rhs)) { 405 assert(lhs); 406 assert(rhs); 407 return func(*lhs, *rhs); 408 } 409 }; 410 411 } // End llvm namespace 412 413 #endif 414