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 29namespace llvm { 30 31//===----------------------------------------------------------------------===// 32// Extra additions to <functional> 33//===----------------------------------------------------------------------===// 34 35template<class Ty> 36struct 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 45template<class Ty> 46struct 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 52template<class Ty> 53struct 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. 65template<typename Fn> class function_ref; 66 67template<typename Ret, typename ...Params> 68class 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 78public: 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// 96template <class T> 97inline 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// 110template <class RootIt, class UnaryFunc> 111class mapped_iterator { 112 RootIt current; 113 UnaryFunc Fn; 114public: 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 182template <class Iterator, class Func> 183inline mapped_iterator<Iterator, Func> 184operator+(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// 193template <class ItTy, class FuncTy> 194inline 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. 204struct 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. 212struct 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. 221template <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. 228template <size_t... I> 229struct index_sequence : integer_sequence<std::size_t, I...> {}; 230 231template <std::size_t N, std::size_t... I> 232struct build_index_impl : build_index_impl<N - 1, N - 1, I...> {}; 233template <std::size_t... I> 234struct build_index_impl<0, I...> : index_sequence<I...> {}; 235 236/// \brief Creates a compile-time integer sequence for a parameter pack. 237template <class... Ts> 238struct index_sequence_for : build_index_impl<sizeof...(Ts)> {}; 239 240//===----------------------------------------------------------------------===// 241// Extra additions for arrays 242//===----------------------------------------------------------------------===// 243 244/// Find the length of an array. 245template <class T, std::size_t N> 246LLVM_CONSTEXPR inline size_t array_lengthof(T (&)[N]) { 247 return N; 248} 249 250/// Adapt std::less<T> for array_pod_sort. 251template<typename T> 252inline 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. 264template<typename T> 265inline 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. 285template<class IteratorTy> 286inline 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 294template <class IteratorTy> 295inline 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. 314template<typename Container> 315void 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. 323template<typename Container> 324void 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); 343template <class T, class... Args> 344typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type 345make_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. 357template <class T> 358typename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0, 359 std::unique_ptr<T>>::type 360make_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. 365template <class T, class... Args> 366typename std::enable_if<std::extent<T>::value != 0>::type 367make_unique(Args &&...) = delete; 368 369struct FreeDeleter { 370 void operator()(void* v) { 371 ::free(v); 372 } 373}; 374 375template<typename First, typename Second> 376struct 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. 383struct 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. 390struct 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. 398template <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