1894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===- llvm/ADT/STLExtras.h - Useful STL related functions ------*- C++ -*-===// 2894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 3894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// The LLVM Compiler Infrastructure 4894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 5894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file is distributed under the University of Illinois Open Source 6894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// License. See LICENSE.TXT for details. 7894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 8894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 9894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 10894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file contains some templates that are useful if you are working with the 11894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// STL at all. 12894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 13894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// No library is required when using these functions. 14894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 15894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 16894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 17894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#ifndef LLVM_ADT_STLEXTRAS_H 18894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#define LLVM_ADT_STLEXTRAS_H 19894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 20894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include <cstddef> // for std::size_t 21894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include <cstdlib> // for qsort 22894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include <functional> 23894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include <iterator> 24894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include <utility> // for std::pair 25894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 26894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumannamespace llvm { 27894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 28894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 29894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// Extra additions to <functional> 30894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 31894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 32894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate<class Ty> 33894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstruct less_ptr : public std::binary_function<Ty, Ty, bool> { 34894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool operator()(const Ty* left, const Ty* right) const { 35894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return *left < *right; 36894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 37894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman}; 38894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 39894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate<class Ty> 40894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstruct greater_ptr : public std::binary_function<Ty, Ty, bool> { 41894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool operator()(const Ty* left, const Ty* right) const { 42894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return *right < *left; 43894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 44894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman}; 45894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 46894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// deleter - Very very very simple method that is used to invoke operator 47894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// delete on something. It is used like this: 48894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 49894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// for_each(V.begin(), B.end(), deleter<Interval>); 50894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 51894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate <class T> 52894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic inline void deleter(T *Ptr) { 53894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman delete Ptr; 54894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 55894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 56894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 57894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 58894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 59894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// Extra additions to <iterator> 60894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 61894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 62894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// mapped_iterator - This is a simple iterator adapter that causes a function to 63894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// be dereferenced whenever operator* is invoked on the iterator. 64894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 65894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate <class RootIt, class UnaryFunc> 66894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass mapped_iterator { 67894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RootIt current; 68894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman UnaryFunc Fn; 69894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanpublic: 70894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef typename std::iterator_traits<RootIt>::iterator_category 71894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman iterator_category; 72894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef typename std::iterator_traits<RootIt>::difference_type 73894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman difference_type; 74894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef typename UnaryFunc::result_type value_type; 75894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 76894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef void pointer; 77894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman //typedef typename UnaryFunc::result_type *pointer; 78894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef void reference; // Can't modify value returned by fn 79894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 80894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef RootIt iterator_type; 81894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef mapped_iterator<RootIt, UnaryFunc> _Self; 82894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 83894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline const RootIt &getCurrent() const { return current; } 84894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline const UnaryFunc &getFunc() const { return Fn; } 85894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 86894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline explicit mapped_iterator(const RootIt &I, UnaryFunc F) 87894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman : current(I), Fn(F) {} 88894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline mapped_iterator(const mapped_iterator &It) 89894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman : current(It.current), Fn(It.Fn) {} 90894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 91894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline value_type operator*() const { // All this work to do this 92894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Fn(*current); // little change 93894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 94894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 95894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman _Self& operator++() { ++current; return *this; } 96894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman _Self& operator--() { --current; return *this; } 97894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman _Self operator++(int) { _Self __tmp = *this; ++current; return __tmp; } 98894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman _Self operator--(int) { _Self __tmp = *this; --current; return __tmp; } 99894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman _Self operator+ (difference_type n) const { 100894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return _Self(current + n, Fn); 101894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 102894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman _Self& operator+= (difference_type n) { current += n; return *this; } 103894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman _Self operator- (difference_type n) const { 104894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return _Self(current - n, Fn); 105894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 106894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman _Self& operator-= (difference_type n) { current -= n; return *this; } 107894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman reference operator[](difference_type n) const { return *(*this + n); } 108894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 109894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline bool operator!=(const _Self &X) const { return !operator==(X); } 110894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline bool operator==(const _Self &X) const { return current == X.current; } 111894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline bool operator< (const _Self &X) const { return current < X.current; } 112894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 113894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline difference_type operator-(const _Self &X) const { 114894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return current - X.current; 115894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 116894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman}; 117894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 118894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate <class _Iterator, class Func> 119894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumaninline mapped_iterator<_Iterator, Func> 120894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanoperator+(typename mapped_iterator<_Iterator, Func>::difference_type N, 121894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const mapped_iterator<_Iterator, Func>& X) { 122894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return mapped_iterator<_Iterator, Func>(X.getCurrent() - N, X.getFunc()); 123894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 124894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 125894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 126894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// map_iterator - Provide a convenient way to create mapped_iterators, just like 127894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// make_pair is useful for creating pairs... 128894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 129894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate <class ItTy, class FuncTy> 130894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumaninline mapped_iterator<ItTy, FuncTy> map_iterator(const ItTy &I, FuncTy F) { 131894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return mapped_iterator<ItTy, FuncTy>(I, F); 132894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 133894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 134894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 135894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// next/prior - These functions unlike std::advance do not modify the 136894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// passed iterator but return a copy. 137894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 138894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// next(myIt) returns copy of myIt incremented once 139894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// next(myIt, n) returns copy of myIt incremented n times 140894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// prior(myIt) returns copy of myIt decremented once 141894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// prior(myIt, n) returns copy of myIt decremented n times 142894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 143894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate <typename ItTy, typename Dist> 144894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumaninline ItTy next(ItTy it, Dist n) 145894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman{ 146894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::advance(it, n); 147894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return it; 148894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 149894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 150894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate <typename ItTy> 151894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumaninline ItTy next(ItTy it) 152894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman{ 153894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return ++it; 154894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 155894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 156894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate <typename ItTy, typename Dist> 157894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumaninline ItTy prior(ItTy it, Dist n) 158894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman{ 159894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::advance(it, -n); 160894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return it; 161894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 162894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 163894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate <typename ItTy> 164894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumaninline ItTy prior(ItTy it) 165894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman{ 166894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return --it; 167894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 168894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 169894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 170894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// Extra additions to <utility> 171894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 172894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 173894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// tie - this function ties two objects and returns a temporary object 174894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// that is assignable from a std::pair. This can be used to make code 175894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// more readable when using values returned from functions bundled in 176894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// a std::pair. Since an example is worth 1000 words: 177894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 178894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// typedef std::map<int, int> Int2IntMap; 179894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 180894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// Int2IntMap myMap; 181894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// Int2IntMap::iterator where; 182894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// bool inserted; 183894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// tie(where, inserted) = myMap.insert(std::make_pair(123,456)); 184894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 185894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// if (inserted) 186894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// // do stuff 187894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// else 188894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// // do other stuff 18919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate <typename T1, typename T2> 19019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanstruct tier { 19119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef T1 &first_type; 19219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef T2 &second_type; 19319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 19419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman first_type first; 19519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman second_type second; 19619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 19719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman tier(first_type f, second_type s) : first(f), second(s) { } 19819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman tier& operator=(const std::pair<T1, T2>& p) { 19919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman first = p.first; 20019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman second = p.second; 20119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return *this; 20219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 20319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman}; 204894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 205894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate <typename T1, typename T2> 206894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumaninline tier<T1, T2> tie(T1& f, T2& s) { 207894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return tier<T1, T2>(f, s); 208894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 209894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 210894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 211894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// Extra additions for arrays 212894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 213894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 214894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// Find where an array ends (for ending iterators) 215894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// This returns a pointer to the byte immediately 216894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// after the end of an array. 217894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate<class T, std::size_t N> 218894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumaninline T *array_endof(T (&x)[N]) { 219894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return x+N; 220894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 221894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 222894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// Find the length of an array. 223894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate<class T, std::size_t N> 22419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumaninline size_t array_lengthof(T (&)[N]) { 225894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return N; 226894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 227894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 228894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// array_pod_sort_comparator - This is helper function for array_pod_sort, 229894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// which just uses operator< on T. 230894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate<typename T> 231894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic inline int array_pod_sort_comparator(const void *P1, const void *P2) { 232894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (*reinterpret_cast<const T*>(P1) < *reinterpret_cast<const T*>(P2)) 233894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return -1; 234894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (*reinterpret_cast<const T*>(P2) < *reinterpret_cast<const T*>(P1)) 235894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return 1; 236894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return 0; 237894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 238894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 239894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// get_array_pad_sort_comparator - This is an internal helper function used to 240894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// get type deduction of T right. 241894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate<typename T> 24219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanstatic int (*get_array_pad_sort_comparator(const T &)) 243894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman (const void*, const void*) { 244894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return array_pod_sort_comparator<T>; 245894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 246894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 247894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 248894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// array_pod_sort - This sorts an array with the specified start and end 249894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// extent. This is just like std::sort, except that it calls qsort instead of 250894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// using an inlined template. qsort is slightly slower than std::sort, but 251894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// most sorts are not performance critical in LLVM and std::sort has to be 252894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// template instantiated for each type, leading to significant measured code 253894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// bloat. This function should generally be used instead of std::sort where 254894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// possible. 255894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 256894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// This function assumes that you have simple POD-like types that can be 257894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// compared with operator< and can be moved with memcpy. If this isn't true, 258894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// you should use std::sort. 259894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 260894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// NOTE: If qsort_r were portable, we could allow a custom comparator and 261894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// default to std::less. 262894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate<class IteratorTy> 263894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic inline void array_pod_sort(IteratorTy Start, IteratorTy End) { 264894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Don't dereference start iterator of empty sequence. 265894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Start == End) return; 266894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman qsort(&*Start, End-Start, sizeof(*Start), 267894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman get_array_pad_sort_comparator(*Start)); 268894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 269894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 270894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate<class IteratorTy> 271894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic inline void array_pod_sort(IteratorTy Start, IteratorTy End, 272894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman int (*Compare)(const void*, const void*)) { 273894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Don't dereference start iterator of empty sequence. 274894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Start == End) return; 275894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman qsort(&*Start, End-Start, sizeof(*Start), Compare); 276894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 277894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 278894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 279894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// Extra additions to <algorithm> 280894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 281894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 282894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// For a container of pointers, deletes the pointers and then clears the 283894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// container. 284894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate<typename Container> 285894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid DeleteContainerPointers(Container &C) { 286894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (typename Container::iterator I = C.begin(), E = C.end(); I != E; ++I) 287894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman delete *I; 288894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman C.clear(); 289894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 290894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 291894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// In a container of pairs (usually a map) whose second element is a pointer, 292894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// deletes the second elements and then clears the container. 293894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate<typename Container> 294894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid DeleteContainerSeconds(Container &C) { 295894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (typename Container::iterator I = C.begin(), E = C.end(); I != E; ++I) 296894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman delete I->second; 297894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman C.clear(); 298894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 299894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 300894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} // End llvm namespace 301894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 302894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#endif 303