1551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer//===- llvm/ADT/STLExtras.h - Useful STL related functions ------*- C++ -*-===// 29769ab22265b313171d201b5928688524a01bd87Misha Brukman// 3b2109ce97881269a610fa4afbcbca350e975174dJohn Criswell// The LLVM Compiler Infrastructure 4b2109ce97881269a610fa4afbcbca350e975174dJohn Criswell// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 79769ab22265b313171d201b5928688524a01bd87Misha Brukman// 8b2109ce97881269a610fa4afbcbca350e975174dJohn Criswell//===----------------------------------------------------------------------===// 918d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner// 1018d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner// This file contains some templates that are useful if you are working with the 1118d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner// STL at all. 1218d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner// 13ccc776fd83b4d200f54cd84af71888e9a740f8fdNick Lewycky// No library is required when using these functions. 1418d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner// 1518d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner//===----------------------------------------------------------------------===// 1618d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner 17551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#ifndef LLVM_ADT_STLEXTRAS_H 18551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#define LLVM_ADT_STLEXTRAS_H 1918d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner 2036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Support/Compiler.h" 21ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include <cassert> 22a2769a33c94f021a609a462b28ebea069eba6f74Misha Brukman#include <cstddef> // for std::size_t 2390c583fff0535d441717425ad4428d85eb2a00a9Benjamin Kramer#include <cstdlib> // for qsort 2418d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner#include <functional> 25f0891be8bdbeeadb39da5575273b6645755fa383Gabor Greif#include <iterator> 2636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include <memory> 279bb2188b0e196d2724e128152ef4d4b581adf3bcBrian Gaeke#include <utility> // for std::pair 2818d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner 29d0fde30ce850b78371fd1386338350591f9ff494Brian Gaekenamespace llvm { 30d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 3118d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner//===----------------------------------------------------------------------===// 3242e018c8057effef5ed1494b999052981d8cf195Chris Lattner// Extra additions to <functional> 3342e018c8057effef5ed1494b999052981d8cf195Chris Lattner//===----------------------------------------------------------------------===// 3442e018c8057effef5ed1494b999052981d8cf195Chris Lattner 357b32639362c4cbb438d71492897d9f84c89d9e57Alkis Evlogimenostemplate<class Ty> 36c0ccb8bb17028fe0dda139c0972c0125d10e6053Andrew Trickstruct identity : public std::unary_function<Ty, Ty> { 37c0ccb8bb17028fe0dda139c0972c0125d10e6053Andrew Trick Ty &operator()(Ty &self) const { 38c0ccb8bb17028fe0dda139c0972c0125d10e6053Andrew Trick return self; 39c0ccb8bb17028fe0dda139c0972c0125d10e6053Andrew Trick } 40c0ccb8bb17028fe0dda139c0972c0125d10e6053Andrew Trick const Ty &operator()(const Ty &self) const { 41c0ccb8bb17028fe0dda139c0972c0125d10e6053Andrew Trick return self; 42c0ccb8bb17028fe0dda139c0972c0125d10e6053Andrew Trick } 43c0ccb8bb17028fe0dda139c0972c0125d10e6053Andrew Trick}; 44c0ccb8bb17028fe0dda139c0972c0125d10e6053Andrew Trick 45c0ccb8bb17028fe0dda139c0972c0125d10e6053Andrew Tricktemplate<class Ty> 46094da67bd781708e76ab37c76e7a87d86404be05Daniel Dunbarstruct less_ptr : public std::binary_function<Ty, Ty, bool> { 47094da67bd781708e76ab37c76e7a87d86404be05Daniel Dunbar bool operator()(const Ty* left, const Ty* right) const { 48094da67bd781708e76ab37c76e7a87d86404be05Daniel Dunbar return *left < *right; 49094da67bd781708e76ab37c76e7a87d86404be05Daniel Dunbar } 50094da67bd781708e76ab37c76e7a87d86404be05Daniel Dunbar}; 51094da67bd781708e76ab37c76e7a87d86404be05Daniel Dunbar 52094da67bd781708e76ab37c76e7a87d86404be05Daniel Dunbartemplate<class Ty> 537b32639362c4cbb438d71492897d9f84c89d9e57Alkis Evlogimenosstruct greater_ptr : public std::binary_function<Ty, Ty, bool> { 547b32639362c4cbb438d71492897d9f84c89d9e57Alkis Evlogimenos bool operator()(const Ty* left, const Ty* right) const { 557b32639362c4cbb438d71492897d9f84c89d9e57Alkis Evlogimenos return *right < *left; 567b32639362c4cbb438d71492897d9f84c89d9e57Alkis Evlogimenos } 577b32639362c4cbb438d71492897d9f84c89d9e57Alkis Evlogimenos}; 587b32639362c4cbb438d71492897d9f84c89d9e57Alkis Evlogimenos 59dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// An efficient, type-erasing, non-owning reference to a callable. This is 60dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// intended for use as the type of a function parameter that is not used 61dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// after the function in question returns. 62dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// 63dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// This class does not own the callable, so it is not in general safe to store 64dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// a function_ref. 65dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinestemplate<typename Fn> class function_ref; 66dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 67dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinestemplate<typename Ret, typename ...Params> 68dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesclass function_ref<Ret(Params...)> { 69dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Ret (*callback)(intptr_t callable, Params ...params); 70dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines intptr_t callable; 71dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 72dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines template<typename Callable> 73dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines static Ret callback_fn(intptr_t callable, Params ...params) { 74dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return (*reinterpret_cast<Callable*>(callable))( 75dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::forward<Params>(params)...); 76dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 77dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 78dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinespublic: 7937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines template <typename Callable> 8037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines function_ref(Callable &&callable, 8137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines typename std::enable_if< 8237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines !std::is_same<typename std::remove_reference<Callable>::type, 8337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines function_ref>::value>::type * = nullptr) 84dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines : callback(callback_fn<typename std::remove_reference<Callable>::type>), 85dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines callable(reinterpret_cast<intptr_t>(&callable)) {} 86dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Ret operator()(Params ...params) const { 87dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return callback(callable, std::forward<Params>(params)...); 88dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 89dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines}; 90dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 91577b15f70e3a1461033858e357f8ed3e10705c21Chris Lattner// deleter - Very very very simple method that is used to invoke operator 929769ab22265b313171d201b5928688524a01bd87Misha Brukman// delete on something. It is used like this: 93577b15f70e3a1461033858e357f8ed3e10705c21Chris Lattner// 94876509614b608f1af885d978c7d2a1e34f807e33Chris Lattner// for_each(V.begin(), B.end(), deleter<Interval>); 95577b15f70e3a1461033858e357f8ed3e10705c21Chris Lattner// 969769ab22265b313171d201b5928688524a01bd87Misha Brukmantemplate <class T> 97305b515c2787f47adecbe120e4b4bef55c5e5525Chandler Carruthinline void deleter(T *Ptr) { 989769ab22265b313171d201b5928688524a01bd87Misha Brukman delete Ptr; 99577b15f70e3a1461033858e357f8ed3e10705c21Chris Lattner} 100577b15f70e3a1461033858e357f8ed3e10705c21Chris Lattner 101577b15f70e3a1461033858e357f8ed3e10705c21Chris Lattner 102577b15f70e3a1461033858e357f8ed3e10705c21Chris Lattner 10342e018c8057effef5ed1494b999052981d8cf195Chris Lattner//===----------------------------------------------------------------------===// 10418d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner// Extra additions to <iterator> 10518d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner//===----------------------------------------------------------------------===// 10618d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner 10718d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner// mapped_iterator - This is a simple iterator adapter that causes a function to 10818d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner// be dereferenced whenever operator* is invoked on the iterator. 10918d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner// 11018d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattnertemplate <class RootIt, class UnaryFunc> 11118d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattnerclass mapped_iterator { 11218d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner RootIt current; 113643afb3b01318f9ce20558ffef374b377b1f1df7Chris Lattner UnaryFunc Fn; 11418d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattnerpublic: 115697954c15da58bd8b186dbafdedd8b06db770201Chris Lattner typedef typename std::iterator_traits<RootIt>::iterator_category 11618d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner iterator_category; 117697954c15da58bd8b186dbafdedd8b06db770201Chris Lattner typedef typename std::iterator_traits<RootIt>::difference_type 11818d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner difference_type; 11918d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner typedef typename UnaryFunc::result_type value_type; 120d063725c3c6e36b711106f06e0cab11a1283f349Chris Lattner 121d063725c3c6e36b711106f06e0cab11a1283f349Chris Lattner typedef void pointer; 122d063725c3c6e36b711106f06e0cab11a1283f349Chris Lattner //typedef typename UnaryFunc::result_type *pointer; 12318d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner typedef void reference; // Can't modify value returned by fn 12418d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner 12518d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner typedef RootIt iterator_type; 12618d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner 12782493289e0234e0172313e845fb87306cf3687acChris Lattner inline const RootIt &getCurrent() const { return current; } 1283d4227bec59358199c7d53fad8f03fd075723fcfDan Gohman inline const UnaryFunc &getFunc() const { return Fn; } 12918d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner 130643afb3b01318f9ce20558ffef374b377b1f1df7Chris Lattner inline explicit mapped_iterator(const RootIt &I, UnaryFunc F) 131643afb3b01318f9ce20558ffef374b377b1f1df7Chris Lattner : current(I), Fn(F) {} 13218d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner 1339769ab22265b313171d201b5928688524a01bd87Misha Brukman inline value_type operator*() const { // All this work to do this 134643afb3b01318f9ce20558ffef374b377b1f1df7Chris Lattner return Fn(*current); // little change 13518d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner } 13618d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner 1374c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar mapped_iterator &operator++() { 1384c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar ++current; 1394c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return *this; 1403d4227bec59358199c7d53fad8f03fd075723fcfDan Gohman } 1414c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar mapped_iterator &operator--() { 1424c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar --current; 1434c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return *this; 1444c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 1454c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar mapped_iterator operator++(int) { 1464c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar mapped_iterator __tmp = *this; 1474c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar ++current; 1484c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return __tmp; 1494c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 1504c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar mapped_iterator operator--(int) { 1514c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar mapped_iterator __tmp = *this; 1524c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar --current; 1534c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return __tmp; 1544c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 1554c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar mapped_iterator operator+(difference_type n) const { 1564c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return mapped_iterator(current + n, Fn); 1574c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 1584c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar mapped_iterator &operator+=(difference_type n) { 1594c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar current += n; 1604c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return *this; 1614c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 1624c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar mapped_iterator operator-(difference_type n) const { 1634c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return mapped_iterator(current - n, Fn); 1644c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 1654c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar mapped_iterator &operator-=(difference_type n) { 1664c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar current -= n; 1674c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return *this; 1683d4227bec59358199c7d53fad8f03fd075723fcfDan Gohman } 1699769ab22265b313171d201b5928688524a01bd87Misha Brukman reference operator[](difference_type n) const { return *(*this + n); } 17018d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner 1714c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar bool operator!=(const mapped_iterator &X) const { return !operator==(X); } 1724c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar bool operator==(const mapped_iterator &X) const { 1734c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return current == X.current; 1744c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 1754c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar bool operator<(const mapped_iterator &X) const { return current < X.current; } 17618d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner 1774c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar difference_type operator-(const mapped_iterator &X) const { 17818d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner return current - X.current; 17918d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner } 18018d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner}; 18118d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner 1824c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainartemplate <class Iterator, class Func> 1834c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarinline mapped_iterator<Iterator, Func> 1844c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainaroperator+(typename mapped_iterator<Iterator, Func>::difference_type N, 1854c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar const mapped_iterator<Iterator, Func> &X) { 1864c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return mapped_iterator<Iterator, Func>(X.getCurrent() - N, X.getFunc()); 18718d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner} 18818d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner 18918d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner 19018d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner// map_iterator - Provide a convenient way to create mapped_iterators, just like 19118d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner// make_pair is useful for creating pairs... 19218d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner// 19318d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattnertemplate <class ItTy, class FuncTy> 19418d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattnerinline mapped_iterator<ItTy, FuncTy> map_iterator(const ItTy &I, FuncTy F) { 195643afb3b01318f9ce20558ffef374b377b1f1df7Chris Lattner return mapped_iterator<ItTy, FuncTy>(I, F); 19618d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner} 19718d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner 198e292da29bfeb2faad71a568e9cbb706affd5f330Alkis Evlogimenos//===----------------------------------------------------------------------===// 199e292da29bfeb2faad71a568e9cbb706affd5f330Alkis Evlogimenos// Extra additions to <utility> 200e292da29bfeb2faad71a568e9cbb706affd5f330Alkis Evlogimenos//===----------------------------------------------------------------------===// 201e292da29bfeb2faad71a568e9cbb706affd5f330Alkis Evlogimenos 2020b6962f4be35aca7054ff68ef9bbbb2e03617d31Benjamin Kramer/// \brief Function object to check whether the first component of a std::pair 2030b6962f4be35aca7054ff68ef9bbbb2e03617d31Benjamin Kramer/// compares less than the first component of another std::pair. 2040b6962f4be35aca7054ff68ef9bbbb2e03617d31Benjamin Kramerstruct less_first { 2050b6962f4be35aca7054ff68ef9bbbb2e03617d31Benjamin Kramer template <typename T> bool operator()(const T &lhs, const T &rhs) const { 2060b6962f4be35aca7054ff68ef9bbbb2e03617d31Benjamin Kramer return lhs.first < rhs.first; 2070b6962f4be35aca7054ff68ef9bbbb2e03617d31Benjamin Kramer } 2080b6962f4be35aca7054ff68ef9bbbb2e03617d31Benjamin Kramer}; 2090b6962f4be35aca7054ff68ef9bbbb2e03617d31Benjamin Kramer 2100b6962f4be35aca7054ff68ef9bbbb2e03617d31Benjamin Kramer/// \brief Function object to check whether the second component of a std::pair 2110b6962f4be35aca7054ff68ef9bbbb2e03617d31Benjamin Kramer/// compares less than the second component of another std::pair. 2120b6962f4be35aca7054ff68ef9bbbb2e03617d31Benjamin Kramerstruct less_second { 2130b6962f4be35aca7054ff68ef9bbbb2e03617d31Benjamin Kramer template <typename T> bool operator()(const T &lhs, const T &rhs) const { 2140b6962f4be35aca7054ff68ef9bbbb2e03617d31Benjamin Kramer return lhs.second < rhs.second; 2150b6962f4be35aca7054ff68ef9bbbb2e03617d31Benjamin Kramer } 2160b6962f4be35aca7054ff68ef9bbbb2e03617d31Benjamin Kramer}; 2170b6962f4be35aca7054ff68ef9bbbb2e03617d31Benjamin Kramer 218ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// A subset of N3658. More stuff can be added as-needed. 219ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 220ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// \brief Represents a compile-time sequence of integers. 221ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinestemplate <class T, T... I> struct integer_sequence { 222ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines typedef T value_type; 223ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 224ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines static LLVM_CONSTEXPR size_t size() { return sizeof...(I); } 225ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines}; 226ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 227ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// \brief Alias for the common case of a sequence of size_ts. 228ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinestemplate <size_t... I> 229ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesstruct index_sequence : integer_sequence<std::size_t, I...> {}; 230ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 231ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinestemplate <std::size_t N, std::size_t... I> 232ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesstruct build_index_impl : build_index_impl<N - 1, N - 1, I...> {}; 233ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinestemplate <std::size_t... I> 234ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesstruct build_index_impl<0, I...> : index_sequence<I...> {}; 235ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 236ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// \brief Creates a compile-time integer sequence for a parameter pack. 237ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinestemplate <class... Ts> 238ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesstruct index_sequence_for : build_index_impl<sizeof...(Ts)> {}; 239ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 240718cb665ca6ce2bc4d8e8479f46a45db91b49f86Owen Anderson//===----------------------------------------------------------------------===// 24199d0015735f8e2aee1a4b99e39ffdaadc8a1dba8Chris Lattner// Extra additions for arrays 242718cb665ca6ce2bc4d8e8479f46a45db91b49f86Owen Anderson//===----------------------------------------------------------------------===// 243718cb665ca6ce2bc4d8e8479f46a45db91b49f86Owen Anderson 244718cb665ca6ce2bc4d8e8479f46a45db91b49f86Owen Anderson/// Find the length of an array. 245dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinestemplate <class T, std::size_t N> 246dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesLLVM_CONSTEXPR inline size_t array_lengthof(T (&)[N]) { 247718cb665ca6ce2bc4d8e8479f46a45db91b49f86Owen Anderson return N; 248718cb665ca6ce2bc4d8e8479f46a45db91b49f86Owen Anderson} 249718cb665ca6ce2bc4d8e8479f46a45db91b49f86Owen Anderson 250dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// Adapt std::less<T> for array_pod_sort. 251545fc87454aabbc8ef8720811ab5dbd5588b537bChris Lattnertemplate<typename T> 252305b515c2787f47adecbe120e4b4bef55c5e5525Chandler Carruthinline int array_pod_sort_comparator(const void *P1, const void *P2) { 253dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (std::less<T>()(*reinterpret_cast<const T*>(P1), 254dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines *reinterpret_cast<const T*>(P2))) 255545fc87454aabbc8ef8720811ab5dbd5588b537bChris Lattner return -1; 256dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (std::less<T>()(*reinterpret_cast<const T*>(P2), 257dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines *reinterpret_cast<const T*>(P1))) 258545fc87454aabbc8ef8720811ab5dbd5588b537bChris Lattner return 1; 259545fc87454aabbc8ef8720811ab5dbd5588b537bChris Lattner return 0; 26099d0015735f8e2aee1a4b99e39ffdaadc8a1dba8Chris Lattner} 2613a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 262d5227545359a4816e52fd100b225ae140ec9b03aAndrew Trick/// get_array_pod_sort_comparator - This is an internal helper function used to 263c65fc3bd27a84281da9819b5fe89a01535a14ecfChris Lattner/// get type deduction of T right. 264c65fc3bd27a84281da9819b5fe89a01535a14ecfChris Lattnertemplate<typename T> 265d5227545359a4816e52fd100b225ae140ec9b03aAndrew Trickinline int (*get_array_pod_sort_comparator(const T &)) 266c65fc3bd27a84281da9819b5fe89a01535a14ecfChris Lattner (const void*, const void*) { 267c65fc3bd27a84281da9819b5fe89a01535a14ecfChris Lattner return array_pod_sort_comparator<T>; 268c65fc3bd27a84281da9819b5fe89a01535a14ecfChris Lattner} 269c65fc3bd27a84281da9819b5fe89a01535a14ecfChris Lattner 27099d0015735f8e2aee1a4b99e39ffdaadc8a1dba8Chris Lattner 27199d0015735f8e2aee1a4b99e39ffdaadc8a1dba8Chris Lattner/// array_pod_sort - This sorts an array with the specified start and end 27299d0015735f8e2aee1a4b99e39ffdaadc8a1dba8Chris Lattner/// extent. This is just like std::sort, except that it calls qsort instead of 27399d0015735f8e2aee1a4b99e39ffdaadc8a1dba8Chris Lattner/// using an inlined template. qsort is slightly slower than std::sort, but 27499d0015735f8e2aee1a4b99e39ffdaadc8a1dba8Chris Lattner/// most sorts are not performance critical in LLVM and std::sort has to be 27599d0015735f8e2aee1a4b99e39ffdaadc8a1dba8Chris Lattner/// template instantiated for each type, leading to significant measured code 27699d0015735f8e2aee1a4b99e39ffdaadc8a1dba8Chris Lattner/// bloat. This function should generally be used instead of std::sort where 27799d0015735f8e2aee1a4b99e39ffdaadc8a1dba8Chris Lattner/// possible. 27899d0015735f8e2aee1a4b99e39ffdaadc8a1dba8Chris Lattner/// 27999d0015735f8e2aee1a4b99e39ffdaadc8a1dba8Chris Lattner/// This function assumes that you have simple POD-like types that can be 280dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// compared with std::less and can be moved with memcpy. If this isn't true, 281545fc87454aabbc8ef8720811ab5dbd5588b537bChris Lattner/// you should use std::sort. 28299d0015735f8e2aee1a4b99e39ffdaadc8a1dba8Chris Lattner/// 28399d0015735f8e2aee1a4b99e39ffdaadc8a1dba8Chris Lattner/// NOTE: If qsort_r were portable, we could allow a custom comparator and 28499d0015735f8e2aee1a4b99e39ffdaadc8a1dba8Chris Lattner/// default to std::less. 28599d0015735f8e2aee1a4b99e39ffdaadc8a1dba8Chris Lattnertemplate<class IteratorTy> 286305b515c2787f47adecbe120e4b4bef55c5e5525Chandler Carruthinline void array_pod_sort(IteratorTy Start, IteratorTy End) { 2874c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // Don't inefficiently call qsort with one element or trigger undefined 2884c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // behavior with an empty sequence. 2894c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar auto NElts = End - Start; 2904c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (NElts <= 1) return; 2914c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start)); 29299d0015735f8e2aee1a4b99e39ffdaadc8a1dba8Chris Lattner} 2933a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2940d293e45b66c742fdbc3998209bb20ed6c5806bfBenjamin Kramertemplate <class IteratorTy> 2950d293e45b66c742fdbc3998209bb20ed6c5806bfBenjamin Kramerinline void array_pod_sort( 2960d293e45b66c742fdbc3998209bb20ed6c5806bfBenjamin Kramer IteratorTy Start, IteratorTy End, 2970d293e45b66c742fdbc3998209bb20ed6c5806bfBenjamin Kramer int (*Compare)( 2980d293e45b66c742fdbc3998209bb20ed6c5806bfBenjamin Kramer const typename std::iterator_traits<IteratorTy>::value_type *, 2990d293e45b66c742fdbc3998209bb20ed6c5806bfBenjamin Kramer const typename std::iterator_traits<IteratorTy>::value_type *)) { 3004c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // Don't inefficiently call qsort with one element or trigger undefined 3014c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // behavior with an empty sequence. 3024c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar auto NElts = End - Start; 3034c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (NElts <= 1) return; 3044c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar qsort(&*Start, NElts, sizeof(*Start), 3050d293e45b66c742fdbc3998209bb20ed6c5806bfBenjamin Kramer reinterpret_cast<int (*)(const void *, const void *)>(Compare)); 3069806f833a6697b835f1c795a1bd2f26a84d49d3cChris Lattner} 307c0ccb8bb17028fe0dda139c0972c0125d10e6053Andrew Trick 3085c213dc78cc717c30908212049e35cfdb950fa24Jeffrey Yasskin//===----------------------------------------------------------------------===// 3095c213dc78cc717c30908212049e35cfdb950fa24Jeffrey Yasskin// Extra additions to <algorithm> 3105c213dc78cc717c30908212049e35cfdb950fa24Jeffrey Yasskin//===----------------------------------------------------------------------===// 3115c213dc78cc717c30908212049e35cfdb950fa24Jeffrey Yasskin 3125c213dc78cc717c30908212049e35cfdb950fa24Jeffrey Yasskin/// For a container of pointers, deletes the pointers and then clears the 3135c213dc78cc717c30908212049e35cfdb950fa24Jeffrey Yasskin/// container. 3145c213dc78cc717c30908212049e35cfdb950fa24Jeffrey Yasskintemplate<typename Container> 3155c213dc78cc717c30908212049e35cfdb950fa24Jeffrey Yasskinvoid DeleteContainerPointers(Container &C) { 3165c213dc78cc717c30908212049e35cfdb950fa24Jeffrey Yasskin for (typename Container::iterator I = C.begin(), E = C.end(); I != E; ++I) 3175c213dc78cc717c30908212049e35cfdb950fa24Jeffrey Yasskin delete *I; 3185c213dc78cc717c30908212049e35cfdb950fa24Jeffrey Yasskin C.clear(); 3195c213dc78cc717c30908212049e35cfdb950fa24Jeffrey Yasskin} 3205c213dc78cc717c30908212049e35cfdb950fa24Jeffrey Yasskin 3215c213dc78cc717c30908212049e35cfdb950fa24Jeffrey Yasskin/// In a container of pairs (usually a map) whose second element is a pointer, 3225c213dc78cc717c30908212049e35cfdb950fa24Jeffrey Yasskin/// deletes the second elements and then clears the container. 3235c213dc78cc717c30908212049e35cfdb950fa24Jeffrey Yasskintemplate<typename Container> 3245c213dc78cc717c30908212049e35cfdb950fa24Jeffrey Yasskinvoid DeleteContainerSeconds(Container &C) { 3255c213dc78cc717c30908212049e35cfdb950fa24Jeffrey Yasskin for (typename Container::iterator I = C.begin(), E = C.end(); I != E; ++I) 3265c213dc78cc717c30908212049e35cfdb950fa24Jeffrey Yasskin delete I->second; 3275c213dc78cc717c30908212049e35cfdb950fa24Jeffrey Yasskin C.clear(); 3285c213dc78cc717c30908212049e35cfdb950fa24Jeffrey Yasskin} 3295c213dc78cc717c30908212049e35cfdb950fa24Jeffrey Yasskin 33036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines//===----------------------------------------------------------------------===// 33136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// Extra additions to <memory> 33236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines//===----------------------------------------------------------------------===// 33336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 33436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// Implement make_unique according to N3656. 33536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 33636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \brief Constructs a `new T()` with the given args and returns a 33736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// `unique_ptr<T>` which owns the object. 33836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 33936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Example: 34036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 34136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// auto p = make_unique<int>(); 34236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// auto p = make_unique<std::tuple<int, int>>(0, 1); 34336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinestemplate <class T, class... Args> 34436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinestypename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type 34536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesmake_unique(Args &&... args) { 34636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return std::unique_ptr<T>(new T(std::forward<Args>(args)...)); 34736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 34836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 34936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \brief Constructs a `new T[n]` with the given args and returns a 35036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// `unique_ptr<T[]>` which owns the object. 35136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 35236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \param n size of the new array. 35336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 35436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Example: 35536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 35636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// auto p = make_unique<int[]>(2); // value-initializes the array with 0's. 35736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinestemplate <class T> 35836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinestypename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0, 35936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::unique_ptr<T>>::type 36036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesmake_unique(size_t n) { 36136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]()); 36236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 36336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 36436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// This function isn't used and is only here to provide better compile errors. 36536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinestemplate <class T, class... Args> 36636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinestypename std::enable_if<std::extent<T>::value != 0>::type 367ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesmake_unique(Args &&...) = delete; 36836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 36937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesstruct FreeDeleter { 37037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void operator()(void* v) { 37137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines ::free(v); 37237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 37337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines}; 37437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 375dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinestemplate<typename First, typename Second> 376dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesstruct pair_hash { 377dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines size_t operator()(const std::pair<First, Second> &P) const { 378dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return std::hash<First>()(P.first) * 31 + std::hash<Second>()(P.second); 379dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 380dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines}; 381dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 382ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// A functor like C++14's std::less<void> in its absence. 383ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesstruct less { 384ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines template <typename A, typename B> bool operator()(A &&a, B &&b) const { 385ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return std::forward<A>(a) < std::forward<B>(b); 386ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 387ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines}; 388ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 389ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// A functor like C++14's std::equal<void> in its absence. 390ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesstruct equal { 391ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines template <typename A, typename B> bool operator()(A &&a, B &&b) const { 392ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return std::forward<A>(a) == std::forward<B>(b); 393ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 394ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines}; 395ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 396ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// Binary functor that adapts to any other binary functor after dereferencing 397ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// operands. 398ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinestemplate <typename T> struct deref { 399ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines T func; 400ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // Could be further improved to cope with non-derivable functors and 401ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // non-binary functors (should be a variadic template member function 402ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // operator()). 403ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines template <typename A, typename B> 404ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines auto operator()(A &lhs, B &rhs) const -> decltype(func(*lhs, *rhs)) { 405ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines assert(lhs); 406ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines assert(rhs); 407ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return func(*lhs, *rhs); 408ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 409ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines}; 410ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 411d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke} // End llvm namespace 412d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 41318d64ede9a4aee9dd66fde04e6ff8ffcae0c9925Chris Lattner#endif 414