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 <cstddef> // for std::size_t 22 #include <cstdlib> // for qsort 23 #include <functional> 24 #include <iterator> 25 #include <memory> 26 #include <utility> // for std::pair 27 28 namespace llvm { 29 30 //===----------------------------------------------------------------------===// 31 // Extra additions to <functional> 32 //===----------------------------------------------------------------------===// 33 34 template<class Ty> 35 struct identity : public std::unary_function<Ty, Ty> { 36 Ty &operator()(Ty &self) const { 37 return self; 38 } 39 const Ty &operator()(const Ty &self) const { 40 return self; 41 } 42 }; 43 44 template<class Ty> 45 struct less_ptr : public std::binary_function<Ty, Ty, bool> { 46 bool operator()(const Ty* left, const Ty* right) const { 47 return *left < *right; 48 } 49 }; 50 51 template<class Ty> 52 struct greater_ptr : public std::binary_function<Ty, Ty, bool> { 53 bool operator()(const Ty* left, const Ty* right) const { 54 return *right < *left; 55 } 56 }; 57 58 /// An efficient, type-erasing, non-owning reference to a callable. This is 59 /// intended for use as the type of a function parameter that is not used 60 /// after the function in question returns. 61 /// 62 /// This class does not own the callable, so it is not in general safe to store 63 /// a function_ref. 64 template<typename Fn> class function_ref; 65 66 #if LLVM_HAS_VARIADIC_TEMPLATES 67 68 template<typename Ret, typename ...Params> 69 class function_ref<Ret(Params...)> { 70 Ret (*callback)(intptr_t callable, Params ...params); 71 intptr_t callable; 72 73 template<typename Callable> 74 static Ret callback_fn(intptr_t callable, Params ...params) { 75 return (*reinterpret_cast<Callable*>(callable))( 76 std::forward<Params>(params)...); 77 } 78 79 public: 80 template<typename Callable> 81 function_ref(Callable &&callable) 82 : callback(callback_fn<typename std::remove_reference<Callable>::type>), 83 callable(reinterpret_cast<intptr_t>(&callable)) {} 84 Ret operator()(Params ...params) const { 85 return callback(callable, std::forward<Params>(params)...); 86 } 87 }; 88 89 #else 90 91 template<typename Ret> 92 class function_ref<Ret()> { 93 Ret (*callback)(intptr_t callable); 94 intptr_t callable; 95 96 template<typename Callable> 97 static Ret callback_fn(intptr_t callable) { 98 return (*reinterpret_cast<Callable*>(callable))(); 99 } 100 101 public: 102 template<typename Callable> 103 function_ref(Callable &&callable) 104 : callback(callback_fn<typename std::remove_reference<Callable>::type>), 105 callable(reinterpret_cast<intptr_t>(&callable)) {} 106 Ret operator()() const { return callback(callable); } 107 }; 108 109 template<typename Ret, typename Param1> 110 class function_ref<Ret(Param1)> { 111 Ret (*callback)(intptr_t callable, Param1 param1); 112 intptr_t callable; 113 114 template<typename Callable> 115 static Ret callback_fn(intptr_t callable, Param1 param1) { 116 return (*reinterpret_cast<Callable*>(callable))( 117 std::forward<Param1>(param1)); 118 } 119 120 public: 121 template<typename Callable> 122 function_ref(Callable &&callable) 123 : callback(callback_fn<typename std::remove_reference<Callable>::type>), 124 callable(reinterpret_cast<intptr_t>(&callable)) {} 125 Ret operator()(Param1 param1) { 126 return callback(callable, std::forward<Param1>(param1)); 127 } 128 }; 129 130 template<typename Ret, typename Param1, typename Param2> 131 class function_ref<Ret(Param1, Param2)> { 132 Ret (*callback)(intptr_t callable, Param1 param1, Param2 param2); 133 intptr_t callable; 134 135 template<typename Callable> 136 static Ret callback_fn(intptr_t callable, Param1 param1, Param2 param2) { 137 return (*reinterpret_cast<Callable*>(callable))( 138 std::forward<Param1>(param1), 139 std::forward<Param2>(param2)); 140 } 141 142 public: 143 template<typename Callable> 144 function_ref(Callable &&callable) 145 : callback(callback_fn<typename std::remove_reference<Callable>::type>), 146 callable(reinterpret_cast<intptr_t>(&callable)) {} 147 Ret operator()(Param1 param1, Param2 param2) { 148 return callback(callable, 149 std::forward<Param1>(param1), 150 std::forward<Param2>(param2)); 151 } 152 }; 153 154 template<typename Ret, typename Param1, typename Param2, typename Param3> 155 class function_ref<Ret(Param1, Param2, Param3)> { 156 Ret (*callback)(intptr_t callable, Param1 param1, Param2 param2, Param3 param3); 157 intptr_t callable; 158 159 template<typename Callable> 160 static Ret callback_fn(intptr_t callable, Param1 param1, Param2 param2, 161 Param3 param3) { 162 return (*reinterpret_cast<Callable*>(callable))( 163 std::forward<Param1>(param1), 164 std::forward<Param2>(param2), 165 std::forward<Param3>(param3)); 166 } 167 168 public: 169 template<typename Callable> 170 function_ref(Callable &&callable) 171 : callback(callback_fn<typename std::remove_reference<Callable>::type>), 172 callable(reinterpret_cast<intptr_t>(&callable)) {} 173 Ret operator()(Param1 param1, Param2 param2, Param3 param3) { 174 return callback(callable, 175 std::forward<Param1>(param1), 176 std::forward<Param2>(param2), 177 std::forward<Param3>(param3)); 178 } 179 }; 180 181 #endif 182 183 // deleter - Very very very simple method that is used to invoke operator 184 // delete on something. It is used like this: 185 // 186 // for_each(V.begin(), B.end(), deleter<Interval>); 187 // 188 template <class T> 189 inline void deleter(T *Ptr) { 190 delete Ptr; 191 } 192 193 194 195 //===----------------------------------------------------------------------===// 196 // Extra additions to <iterator> 197 //===----------------------------------------------------------------------===// 198 199 // mapped_iterator - This is a simple iterator adapter that causes a function to 200 // be dereferenced whenever operator* is invoked on the iterator. 201 // 202 template <class RootIt, class UnaryFunc> 203 class mapped_iterator { 204 RootIt current; 205 UnaryFunc Fn; 206 public: 207 typedef typename std::iterator_traits<RootIt>::iterator_category 208 iterator_category; 209 typedef typename std::iterator_traits<RootIt>::difference_type 210 difference_type; 211 typedef typename UnaryFunc::result_type value_type; 212 213 typedef void pointer; 214 //typedef typename UnaryFunc::result_type *pointer; 215 typedef void reference; // Can't modify value returned by fn 216 217 typedef RootIt iterator_type; 218 typedef mapped_iterator<RootIt, UnaryFunc> _Self; 219 220 inline const RootIt &getCurrent() const { return current; } 221 inline const UnaryFunc &getFunc() const { return Fn; } 222 223 inline explicit mapped_iterator(const RootIt &I, UnaryFunc F) 224 : current(I), Fn(F) {} 225 226 inline value_type operator*() const { // All this work to do this 227 return Fn(*current); // little change 228 } 229 230 _Self& operator++() { ++current; return *this; } 231 _Self& operator--() { --current; return *this; } 232 _Self operator++(int) { _Self __tmp = *this; ++current; return __tmp; } 233 _Self operator--(int) { _Self __tmp = *this; --current; return __tmp; } 234 _Self operator+ (difference_type n) const { 235 return _Self(current + n, Fn); 236 } 237 _Self& operator+= (difference_type n) { current += n; return *this; } 238 _Self operator- (difference_type n) const { 239 return _Self(current - n, Fn); 240 } 241 _Self& operator-= (difference_type n) { current -= n; return *this; } 242 reference operator[](difference_type n) const { return *(*this + n); } 243 244 inline bool operator!=(const _Self &X) const { return !operator==(X); } 245 inline bool operator==(const _Self &X) const { return current == X.current; } 246 inline bool operator< (const _Self &X) const { return current < X.current; } 247 248 inline difference_type operator-(const _Self &X) const { 249 return current - X.current; 250 } 251 }; 252 253 template <class _Iterator, class Func> 254 inline mapped_iterator<_Iterator, Func> 255 operator+(typename mapped_iterator<_Iterator, Func>::difference_type N, 256 const mapped_iterator<_Iterator, Func>& X) { 257 return mapped_iterator<_Iterator, Func>(X.getCurrent() - N, X.getFunc()); 258 } 259 260 261 // map_iterator - Provide a convenient way to create mapped_iterators, just like 262 // make_pair is useful for creating pairs... 263 // 264 template <class ItTy, class FuncTy> 265 inline mapped_iterator<ItTy, FuncTy> map_iterator(const ItTy &I, FuncTy F) { 266 return mapped_iterator<ItTy, FuncTy>(I, F); 267 } 268 269 //===----------------------------------------------------------------------===// 270 // Extra additions to <utility> 271 //===----------------------------------------------------------------------===// 272 273 /// \brief Function object to check whether the first component of a std::pair 274 /// compares less than the first component of another std::pair. 275 struct less_first { 276 template <typename T> bool operator()(const T &lhs, const T &rhs) const { 277 return lhs.first < rhs.first; 278 } 279 }; 280 281 /// \brief Function object to check whether the second component of a std::pair 282 /// compares less than the second component of another std::pair. 283 struct less_second { 284 template <typename T> bool operator()(const T &lhs, const T &rhs) const { 285 return lhs.second < rhs.second; 286 } 287 }; 288 289 //===----------------------------------------------------------------------===// 290 // Extra additions for arrays 291 //===----------------------------------------------------------------------===// 292 293 /// Find the length of an array. 294 template <class T, std::size_t N> 295 LLVM_CONSTEXPR inline size_t array_lengthof(T (&)[N]) { 296 return N; 297 } 298 299 /// Adapt std::less<T> for array_pod_sort. 300 template<typename T> 301 inline int array_pod_sort_comparator(const void *P1, const void *P2) { 302 if (std::less<T>()(*reinterpret_cast<const T*>(P1), 303 *reinterpret_cast<const T*>(P2))) 304 return -1; 305 if (std::less<T>()(*reinterpret_cast<const T*>(P2), 306 *reinterpret_cast<const T*>(P1))) 307 return 1; 308 return 0; 309 } 310 311 /// get_array_pod_sort_comparator - This is an internal helper function used to 312 /// get type deduction of T right. 313 template<typename T> 314 inline int (*get_array_pod_sort_comparator(const T &)) 315 (const void*, const void*) { 316 return array_pod_sort_comparator<T>; 317 } 318 319 320 /// array_pod_sort - This sorts an array with the specified start and end 321 /// extent. This is just like std::sort, except that it calls qsort instead of 322 /// using an inlined template. qsort is slightly slower than std::sort, but 323 /// most sorts are not performance critical in LLVM and std::sort has to be 324 /// template instantiated for each type, leading to significant measured code 325 /// bloat. This function should generally be used instead of std::sort where 326 /// possible. 327 /// 328 /// This function assumes that you have simple POD-like types that can be 329 /// compared with std::less and can be moved with memcpy. If this isn't true, 330 /// you should use std::sort. 331 /// 332 /// NOTE: If qsort_r were portable, we could allow a custom comparator and 333 /// default to std::less. 334 template<class IteratorTy> 335 inline void array_pod_sort(IteratorTy Start, IteratorTy End) { 336 // Don't dereference start iterator of empty sequence. 337 if (Start == End) return; 338 qsort(&*Start, End-Start, sizeof(*Start), 339 get_array_pod_sort_comparator(*Start)); 340 } 341 342 template <class IteratorTy> 343 inline void array_pod_sort( 344 IteratorTy Start, IteratorTy End, 345 int (*Compare)( 346 const typename std::iterator_traits<IteratorTy>::value_type *, 347 const typename std::iterator_traits<IteratorTy>::value_type *)) { 348 // Don't dereference start iterator of empty sequence. 349 if (Start == End) return; 350 qsort(&*Start, End - Start, sizeof(*Start), 351 reinterpret_cast<int (*)(const void *, const void *)>(Compare)); 352 } 353 354 //===----------------------------------------------------------------------===// 355 // Extra additions to <algorithm> 356 //===----------------------------------------------------------------------===// 357 358 /// For a container of pointers, deletes the pointers and then clears the 359 /// container. 360 template<typename Container> 361 void DeleteContainerPointers(Container &C) { 362 for (typename Container::iterator I = C.begin(), E = C.end(); I != E; ++I) 363 delete *I; 364 C.clear(); 365 } 366 367 /// In a container of pairs (usually a map) whose second element is a pointer, 368 /// deletes the second elements and then clears the container. 369 template<typename Container> 370 void DeleteContainerSeconds(Container &C) { 371 for (typename Container::iterator I = C.begin(), E = C.end(); I != E; ++I) 372 delete I->second; 373 C.clear(); 374 } 375 376 //===----------------------------------------------------------------------===// 377 // Extra additions to <memory> 378 //===----------------------------------------------------------------------===// 379 380 #if LLVM_HAS_VARIADIC_TEMPLATES 381 382 // Implement make_unique according to N3656. 383 384 /// \brief Constructs a `new T()` with the given args and returns a 385 /// `unique_ptr<T>` which owns the object. 386 /// 387 /// Example: 388 /// 389 /// auto p = make_unique<int>(); 390 /// auto p = make_unique<std::tuple<int, int>>(0, 1); 391 template <class T, class... Args> 392 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type 393 make_unique(Args &&... args) { 394 return std::unique_ptr<T>(new T(std::forward<Args>(args)...)); 395 } 396 397 /// \brief Constructs a `new T[n]` with the given args and returns a 398 /// `unique_ptr<T[]>` which owns the object. 399 /// 400 /// \param n size of the new array. 401 /// 402 /// Example: 403 /// 404 /// auto p = make_unique<int[]>(2); // value-initializes the array with 0's. 405 template <class T> 406 typename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0, 407 std::unique_ptr<T>>::type 408 make_unique(size_t n) { 409 return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]()); 410 } 411 412 /// This function isn't used and is only here to provide better compile errors. 413 template <class T, class... Args> 414 typename std::enable_if<std::extent<T>::value != 0>::type 415 make_unique(Args &&...) LLVM_DELETED_FUNCTION; 416 417 #else 418 419 template <class T> 420 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type 421 make_unique() { 422 return std::unique_ptr<T>(new T()); 423 } 424 425 template <class T, class Arg1> 426 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type 427 make_unique(Arg1 &&arg1) { 428 return std::unique_ptr<T>(new T(std::forward<Arg1>(arg1))); 429 } 430 431 template <class T, class Arg1, class Arg2> 432 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type 433 make_unique(Arg1 &&arg1, Arg2 &&arg2) { 434 return std::unique_ptr<T>( 435 new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2))); 436 } 437 438 template <class T, class Arg1, class Arg2, class Arg3> 439 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type 440 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3) { 441 return std::unique_ptr<T>(new T(std::forward<Arg1>(arg1), 442 std::forward<Arg2>(arg2), 443 std::forward<Arg3>(arg3))); 444 } 445 446 template <class T, class Arg1, class Arg2, class Arg3, class Arg4> 447 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type 448 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4) { 449 return std::unique_ptr<T>( 450 new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2), 451 std::forward<Arg3>(arg3), std::forward<Arg4>(arg4))); 452 } 453 454 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5> 455 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type 456 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5) { 457 return std::unique_ptr<T>( 458 new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2), 459 std::forward<Arg3>(arg3), std::forward<Arg4>(arg4), 460 std::forward<Arg5>(arg5))); 461 } 462 463 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5, 464 class Arg6> 465 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type 466 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5, 467 Arg6 &&arg6) { 468 return std::unique_ptr<T>( 469 new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2), 470 std::forward<Arg3>(arg3), std::forward<Arg4>(arg4), 471 std::forward<Arg5>(arg5), std::forward<Arg6>(arg6))); 472 } 473 474 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5, 475 class Arg6, class Arg7> 476 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type 477 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5, 478 Arg6 &&arg6, Arg7 &&arg7) { 479 return std::unique_ptr<T>( 480 new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2), 481 std::forward<Arg3>(arg3), std::forward<Arg4>(arg4), 482 std::forward<Arg5>(arg5), std::forward<Arg6>(arg6), 483 std::forward<Arg7>(arg7))); 484 } 485 486 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5, 487 class Arg6, class Arg7, class Arg8> 488 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type 489 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5, 490 Arg6 &&arg6, Arg7 &&arg7, Arg8 &&arg8) { 491 return std::unique_ptr<T>( 492 new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2), 493 std::forward<Arg3>(arg3), std::forward<Arg4>(arg4), 494 std::forward<Arg5>(arg5), std::forward<Arg6>(arg6), 495 std::forward<Arg7>(arg7), std::forward<Arg8>(arg8))); 496 } 497 498 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5, 499 class Arg6, class Arg7, class Arg8, class Arg9> 500 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type 501 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5, 502 Arg6 &&arg6, Arg7 &&arg7, Arg8 &&arg8, Arg9 &&arg9) { 503 return std::unique_ptr<T>( 504 new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2), 505 std::forward<Arg3>(arg3), std::forward<Arg4>(arg4), 506 std::forward<Arg5>(arg5), std::forward<Arg6>(arg6), 507 std::forward<Arg7>(arg7), std::forward<Arg8>(arg8), 508 std::forward<Arg9>(arg9))); 509 } 510 511 template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5, 512 class Arg6, class Arg7, class Arg8, class Arg9, class Arg10> 513 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type 514 make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5, 515 Arg6 &&arg6, Arg7 &&arg7, Arg8 &&arg8, Arg9 &&arg9, Arg10 &&arg10) { 516 return std::unique_ptr<T>( 517 new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2), 518 std::forward<Arg3>(arg3), std::forward<Arg4>(arg4), 519 std::forward<Arg5>(arg5), std::forward<Arg6>(arg6), 520 std::forward<Arg7>(arg7), std::forward<Arg8>(arg8), 521 std::forward<Arg9>(arg9), std::forward<Arg10>(arg10))); 522 } 523 524 template <class T> 525 typename std::enable_if<std::is_array<T>::value &&std::extent<T>::value == 0, 526 std::unique_ptr<T>>::type 527 make_unique(size_t n) { 528 return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]()); 529 } 530 531 #endif 532 533 template<typename First, typename Second> 534 struct pair_hash { 535 size_t operator()(const std::pair<First, Second> &P) const { 536 return std::hash<First>()(P.first) * 31 + std::hash<Second>()(P.second); 537 } 538 }; 539 540 } // End llvm namespace 541 542 #endif 543
