1e3f71b4198cebee9c9f2534c39bd3e19740eee6aChris Lattner//===- llvm/ADT/IndexedMap.h - An index map implementation ------*- C++ -*-===// 230eed211c99246392edf49c1bc6e9fb2a8f7a0f6Alkis Evlogimenos// 34d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos// The LLVM Compiler Infrastructure 44d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 730eed211c99246392edf49c1bc6e9fb2a8f7a0f6Alkis Evlogimenos// 84d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos//===----------------------------------------------------------------------===// 94d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos// 10e3f71b4198cebee9c9f2534c39bd3e19740eee6aChris Lattner// This file implements an indexed map. The index map template takes two 114d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos// types. The first is the mapped type and the second is a functor 1200fa65be8344944b080cd790678e027e10942ffdChris Lattner// that maps its argument to a size_t. On instantiation a "null" value 134d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos// can be provided to be used as a "does not exist" indicator in the 144d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos// map. A member function grow() is provided that given the value of 154d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos// the maximally indexed key (the argument of the functor) makes sure 164d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos// the map has enough space for it. 174d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos// 184d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos//===----------------------------------------------------------------------===// 194d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos 20e3f71b4198cebee9c9f2534c39bd3e19740eee6aChris Lattner#ifndef LLVM_ADT_INDEXEDMAP_H 21e3f71b4198cebee9c9f2534c39bd3e19740eee6aChris Lattner#define LLVM_ADT_INDEXEDMAP_H 224d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos 23c0ccb8bb17028fe0dda139c0972c0125d10e6053Andrew Trick#include "llvm/ADT/STLExtras.h" 244c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/ADT/SmallVector.h" 25a2769a33c94f021a609a462b28ebea069eba6f74Misha Brukman#include <cassert> 26df8d5e908fe83dafe98a05086956e7b0943af1e0Alkis Evlogimenos#include <functional> 274d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos 284d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenosnamespace llvm { 294d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos 30c0ccb8bb17028fe0dda139c0972c0125d10e6053Andrew Tricktemplate <typename T, typename ToIndexT = llvm::identity<unsigned> > 3194c002a190cd2e3a52b1510bc997e53d63af0b3bChris Lattner class IndexedMap { 324d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos typedef typename ToIndexT::argument_type IndexT; 334c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // Prefer SmallVector with zero inline storage over std::vector. IndexedMaps 344c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // can grow very large and SmallVector grows more efficiently as long as T 354c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // is trivially copyable. 364c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar typedef SmallVector<T, 0> StorageT; 374d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos StorageT storage_; 384d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos T nullVal_; 394d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos ToIndexT toIndex_; 404d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos 415501e568b396f3e58f3d642e77139c790eda9df9Alkis Evlogimenos public: 4294c002a190cd2e3a52b1510bc997e53d63af0b3bChris Lattner IndexedMap() : nullVal_(T()) { } 434d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos 4494c002a190cd2e3a52b1510bc997e53d63af0b3bChris Lattner explicit IndexedMap(const T& val) : nullVal_(val) { } 454d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos 464d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos typename StorageT::reference operator[](IndexT n) { 475501e568b396f3e58f3d642e77139c790eda9df9Alkis Evlogimenos assert(toIndex_(n) < storage_.size() && "index out of bounds!"); 485501e568b396f3e58f3d642e77139c790eda9df9Alkis Evlogimenos return storage_[toIndex_(n)]; 494d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos } 504d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos 514d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos typename StorageT::const_reference operator[](IndexT n) const { 525501e568b396f3e58f3d642e77139c790eda9df9Alkis Evlogimenos assert(toIndex_(n) < storage_.size() && "index out of bounds!"); 535501e568b396f3e58f3d642e77139c790eda9df9Alkis Evlogimenos return storage_[toIndex_(n)]; 544d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos } 554d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos 56994c727b5790e5c976e32c75364d78eb9b22a568Jakob Stoklund Olesen void reserve(typename StorageT::size_type s) { 57994c727b5790e5c976e32c75364d78eb9b22a568Jakob Stoklund Olesen storage_.reserve(s); 58994c727b5790e5c976e32c75364d78eb9b22a568Jakob Stoklund Olesen } 59994c727b5790e5c976e32c75364d78eb9b22a568Jakob Stoklund Olesen 6042e9c963921776cb498c33b6c6c03f29971316f3Jakob Stoklund Olesen void resize(typename StorageT::size_type s) { 6142e9c963921776cb498c33b6c6c03f29971316f3Jakob Stoklund Olesen storage_.resize(s, nullVal_); 6242e9c963921776cb498c33b6c6c03f29971316f3Jakob Stoklund Olesen } 6342e9c963921776cb498c33b6c6c03f29971316f3Jakob Stoklund Olesen 644d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos void clear() { 655501e568b396f3e58f3d642e77139c790eda9df9Alkis Evlogimenos storage_.clear(); 664d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos } 674d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos 684d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos void grow(IndexT n) { 695501e568b396f3e58f3d642e77139c790eda9df9Alkis Evlogimenos unsigned NewSize = toIndex_(n) + 1; 705501e568b396f3e58f3d642e77139c790eda9df9Alkis Evlogimenos if (NewSize > storage_.size()) 7142e9c963921776cb498c33b6c6c03f29971316f3Jakob Stoklund Olesen resize(NewSize); 724d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos } 73fc093bd0810b6e726c02c2430f77618fd7255541Alkis Evlogimenos 74358de24dc121cd21911f3248b599178c86e9b467Jakob Stoklund Olesen bool inBounds(IndexT n) const { 75358de24dc121cd21911f3248b599178c86e9b467Jakob Stoklund Olesen return toIndex_(n) < storage_.size(); 76358de24dc121cd21911f3248b599178c86e9b467Jakob Stoklund Olesen } 77358de24dc121cd21911f3248b599178c86e9b467Jakob Stoklund Olesen 78fc093bd0810b6e726c02c2430f77618fd7255541Alkis Evlogimenos typename StorageT::size_type size() const { 79fc093bd0810b6e726c02c2430f77618fd7255541Alkis Evlogimenos return storage_.size(); 80fc093bd0810b6e726c02c2430f77618fd7255541Alkis Evlogimenos } 815501e568b396f3e58f3d642e77139c790eda9df9Alkis Evlogimenos }; 824d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos 834d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos} // End llvm namespace 844d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos 854d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos#endif 86