1193323Sed//===- llvm/ADT/IndexedMap.h - An index map implementation ------*- C++ -*-===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file implements an indexed map. The index map template takes two 11193323Sed// types. The first is the mapped type and the second is a functor 12193323Sed// that maps its argument to a size_t. On instantiation a "null" value 13193323Sed// can be provided to be used as a "does not exist" indicator in the 14193323Sed// map. A member function grow() is provided that given the value of 15193323Sed// the maximally indexed key (the argument of the functor) makes sure 16193323Sed// the map has enough space for it. 17193323Sed// 18193323Sed//===----------------------------------------------------------------------===// 19193323Sed 20193323Sed#ifndef LLVM_ADT_INDEXEDMAP_H 21193323Sed#define LLVM_ADT_INDEXEDMAP_H 22193323Sed 23239462Sdim#include "llvm/ADT/STLExtras.h" 24193323Sed#include <cassert> 25193323Sed#include <functional> 26193323Sed#include <vector> 27193323Sed 28193323Sednamespace llvm { 29193323Sed 30239462Sdimtemplate <typename T, typename ToIndexT = llvm::identity<unsigned> > 31193323Sed class IndexedMap { 32193323Sed typedef typename ToIndexT::argument_type IndexT; 33193323Sed typedef std::vector<T> StorageT; 34193323Sed StorageT storage_; 35193323Sed T nullVal_; 36193323Sed ToIndexT toIndex_; 37193323Sed 38193323Sed public: 39193323Sed IndexedMap() : nullVal_(T()) { } 40193323Sed 41193323Sed explicit IndexedMap(const T& val) : nullVal_(val) { } 42193323Sed 43193323Sed typename StorageT::reference operator[](IndexT n) { 44193323Sed assert(toIndex_(n) < storage_.size() && "index out of bounds!"); 45193323Sed return storage_[toIndex_(n)]; 46193323Sed } 47193323Sed 48193323Sed typename StorageT::const_reference operator[](IndexT n) const { 49193323Sed assert(toIndex_(n) < storage_.size() && "index out of bounds!"); 50193323Sed return storage_[toIndex_(n)]; 51193323Sed } 52193323Sed 53218893Sdim void reserve(typename StorageT::size_type s) { 54218893Sdim storage_.reserve(s); 55218893Sdim } 56218893Sdim 57218893Sdim void resize(typename StorageT::size_type s) { 58218893Sdim storage_.resize(s, nullVal_); 59218893Sdim } 60218893Sdim 61193323Sed void clear() { 62193323Sed storage_.clear(); 63193323Sed } 64193323Sed 65193323Sed void grow(IndexT n) { 66193323Sed unsigned NewSize = toIndex_(n) + 1; 67193323Sed if (NewSize > storage_.size()) 68218893Sdim resize(NewSize); 69193323Sed } 70193323Sed 71218893Sdim bool inBounds(IndexT n) const { 72218893Sdim return toIndex_(n) < storage_.size(); 73218893Sdim } 74218893Sdim 75193323Sed typename StorageT::size_type size() const { 76193323Sed return storage_.size(); 77193323Sed } 78193323Sed }; 79193323Sed 80193323Sed} // End llvm namespace 81193323Sed 82193323Sed#endif 83