#ifndef LLVM_ADT_INDEXEDMAP_H
#define LLVM_ADT_INDEXEDMAP_H
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallVector.h"
#include <cassert>
#include <functional>
-#include <vector>
namespace llvm {
- struct IdentityFunctor : public std::unary_function<unsigned, unsigned> {
- unsigned operator()(unsigned Index) const {
- return Index;
- }
- };
-
- template <typename T, typename ToIndexT = IdentityFunctor>
+template <typename T, typename ToIndexT = llvm::identity<unsigned> >
class IndexedMap {
typedef typename ToIndexT::argument_type IndexT;
- typedef std::vector<T> StorageT;
+ // Prefer SmallVector with zero inline storage over std::vector. IndexedMaps
+ // can grow very large and SmallVector grows more efficiently as long as T
+ // is trivially copyable.
+ typedef SmallVector<T, 0> StorageT;
StorageT storage_;
T nullVal_;
ToIndexT toIndex_;
storage_.reserve(s);
}
+ void resize(typename StorageT::size_type s) {
+ storage_.resize(s, nullVal_);
+ }
+
void clear() {
storage_.clear();
}
void grow(IndexT n) {
unsigned NewSize = toIndex_(n) + 1;
if (NewSize > storage_.size())
- storage_.resize(NewSize, nullVal_);
+ resize(NewSize);
}
bool inBounds(IndexT n) const {