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> {
operatoridentity36 Ty &operator()(Ty &self) const {
37 return self;
38 }
operatoridentity39 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> {
operatorless_ptr46 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> {
operatorgreater_ptr53 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>
callback_fn(intptr_t callable,Params...params)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>
function_ref(Callable && callable)81 function_ref(Callable &&callable)
82 : callback(callback_fn<typename std::remove_reference<Callable>::type>),
83 callable(reinterpret_cast<intptr_t>(&callable)) {}
operator()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>
callback_fn(intptr_t callable)97 static Ret callback_fn(intptr_t callable) {
98 return (*reinterpret_cast<Callable*>(callable))();
99 }
100
101 public:
102 template<typename Callable>
function_ref(Callable && callable)103 function_ref(Callable &&callable)
104 : callback(callback_fn<typename std::remove_reference<Callable>::type>),
105 callable(reinterpret_cast<intptr_t>(&callable)) {}
operator()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>
callback_fn(intptr_t callable,Param1 param1)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>
function_ref(Callable && callable)122 function_ref(Callable &&callable)
123 : callback(callback_fn<typename std::remove_reference<Callable>::type>),
124 callable(reinterpret_cast<intptr_t>(&callable)) {}
operator()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>
callback_fn(intptr_t callable,Param1 param1,Param2 param2)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>
function_ref(Callable && callable)144 function_ref(Callable &&callable)
145 : callback(callback_fn<typename std::remove_reference<Callable>::type>),
146 callable(reinterpret_cast<intptr_t>(&callable)) {}
operator()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>
callback_fn(intptr_t callable,Param1 param1,Param2 param2,Param3 param3)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>
function_ref(Callable && callable)170 function_ref(Callable &&callable)
171 : callback(callback_fn<typename std::remove_reference<Callable>::type>),
172 callable(reinterpret_cast<intptr_t>(&callable)) {}
operator()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>
deleter(T * Ptr)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
getCurrent()220 inline const RootIt &getCurrent() const { return current; }
getFunc()221 inline const UnaryFunc &getFunc() const { return Fn; }
222
mapped_iterator(const RootIt & I,UnaryFunc F)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>
map_iterator(const ItTy & I,FuncTy F)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 {
operatorless_first276 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 {
operatorless_second284 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>
array_lengthof(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>
array_pod_sort_comparator(const void * P1,const void * P2)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>
get_array_pod_sort_comparator(const 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>
array_pod_sort(IteratorTy Start,IteratorTy End)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>
array_pod_sort(IteratorTy Start,IteratorTy End,int (* Compare)(const typename std::iterator_traits<IteratorTy>::value_type *,const typename std::iterator_traits<IteratorTy>::value_type *))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>
DeleteContainerPointers(Container & C)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>
DeleteContainerSeconds(Container & C)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
make_unique(Args &&...args)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
make_unique(size_t n)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
make_unique()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
make_unique(Arg1 && arg1)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
make_unique(Arg1 && arg1,Arg2 && arg2)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
make_unique(Arg1 && arg1,Arg2 && arg2,Arg3 && arg3)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
make_unique(Arg1 && arg1,Arg2 && arg2,Arg3 && arg3,Arg4 && arg4)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
make_unique(Arg1 && arg1,Arg2 && arg2,Arg3 && arg3,Arg4 && arg4,Arg5 && arg5)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
make_unique(Arg1 && arg1,Arg2 && arg2,Arg3 && arg3,Arg4 && arg4,Arg5 && arg5,Arg6 && arg6)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
make_unique(Arg1 && arg1,Arg2 && arg2,Arg3 && arg3,Arg4 && arg4,Arg5 && arg5,Arg6 && arg6,Arg7 && arg7)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
make_unique(Arg1 && arg1,Arg2 && arg2,Arg3 && arg3,Arg4 && arg4,Arg5 && arg5,Arg6 && arg6,Arg7 && arg7,Arg8 && arg8)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
make_unique(Arg1 && arg1,Arg2 && arg2,Arg3 && arg3,Arg4 && arg4,Arg5 && arg5,Arg6 && arg6,Arg7 && arg7,Arg8 && arg8,Arg9 && arg9)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
make_unique(Arg1 && arg1,Arg2 && arg2,Arg3 && arg3,Arg4 && arg4,Arg5 && arg5,Arg6 && arg6,Arg7 && arg7,Arg8 && arg8,Arg9 && arg9,Arg10 && arg10)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
make_unique(size_t n)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 {
operatorpair_hash535 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