15f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer//===- llvm/ADT/IndexedMap.h - An index map implementation ------*- C++ -*-===// 25f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer// 35f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer// The LLVM Compiler Infrastructure 45f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer// 55f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer// This file is distributed under the University of Illinois Open Source 65f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer// License. See LICENSE.TXT for details. 75f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer// 85f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer//===----------------------------------------------------------------------===// 95f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer// 105f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer// This file implements an indexed map. The index map template takes two 115f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer// types. The first is the mapped type and the second is a functor 125f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer// that maps its argument to a size_t. On instantiation a "null" value 135f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer// can be provided to be used as a "does not exist" indicator in the 145f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer// map. A member function grow() is provided that given the value of 155f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer// the maximally indexed key (the argument of the functor) makes sure 165f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer// the map has enough space for it. 179dc1f530c086d2c16f8cba758b0f59a5bf41323aChris Lattner// 180a449eed1dd2439b4b9c0a6291084816eab390c1Ted Kremenek//===----------------------------------------------------------------------===// 199dc1f530c086d2c16f8cba758b0f59a5bf41323aChris Lattner 205f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer#ifndef LLVM_ADT_INDEXEDMAP_H 215f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer#define LLVM_ADT_INDEXEDMAP_H 225f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer 235f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer#include "llvm/ADT/STLExtras.h" 245f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer#include <cassert> 255f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer#include <functional> 265f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer#include <vector> 275f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer 285f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencernamespace llvm { 29b7489d8129136437953d412e2a6cf0ef87f4a461Chris Lattner 30b7489d8129136437953d412e2a6cf0ef87f4a461Chris Lattnertemplate <typename T, typename ToIndexT = llvm::identity<unsigned> > 31b7489d8129136437953d412e2a6cf0ef87f4a461Chris Lattner class IndexedMap { 325f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer typedef typename ToIndexT::argument_type IndexT; 33b7489d8129136437953d412e2a6cf0ef87f4a461Chris Lattner typedef std::vector<T> StorageT; 349dc1f530c086d2c16f8cba758b0f59a5bf41323aChris Lattner StorageT storage_; 359dc1f530c086d2c16f8cba758b0f59a5bf41323aChris Lattner T nullVal_; 36b7489d8129136437953d412e2a6cf0ef87f4a461Chris Lattner ToIndexT toIndex_; 37b7489d8129136437953d412e2a6cf0ef87f4a461Chris Lattner 38b7489d8129136437953d412e2a6cf0ef87f4a461Chris Lattner public: 39b7489d8129136437953d412e2a6cf0ef87f4a461Chris Lattner IndexedMap() : nullVal_(T()) { } 40b7489d8129136437953d412e2a6cf0ef87f4a461Chris Lattner 41b7489d8129136437953d412e2a6cf0ef87f4a461Chris Lattner explicit IndexedMap(const T& val) : nullVal_(val) { } 42b7489d8129136437953d412e2a6cf0ef87f4a461Chris Lattner 43b7489d8129136437953d412e2a6cf0ef87f4a461Chris Lattner typename StorageT::reference operator[](IndexT n) { 44d1623a81992a24abbfcd5520b32a0dd90857b8a8Chris Lattner assert(toIndex_(n) < storage_.size() && "index out of bounds!"); 45b7489d8129136437953d412e2a6cf0ef87f4a461Chris Lattner return storage_[toIndex_(n)]; 4631bb8be680ee2facf7fbb3c6c87b9bbd20248328Chris Lattner } 472c64b7b9381be4ff62fbdc404ed3f14c8086898dChris Lattner 48b7489d8129136437953d412e2a6cf0ef87f4a461Chris Lattner typename StorageT::const_reference operator[](IndexT n) const { 49b7489d8129136437953d412e2a6cf0ef87f4a461Chris Lattner assert(toIndex_(n) < storage_.size() && "index out of bounds!"); 502c64b7b9381be4ff62fbdc404ed3f14c8086898dChris Lattner return storage_[toIndex_(n)]; 515f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer } 525f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer 535f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer void reserve(typename StorageT::size_type s) { 545f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer storage_.reserve(s); 559dc1f530c086d2c16f8cba758b0f59a5bf41323aChris Lattner } 569dc1f530c086d2c16f8cba758b0f59a5bf41323aChris Lattner 579dc1f530c086d2c16f8cba758b0f59a5bf41323aChris Lattner void resize(typename StorageT::size_type s) { 58b7489d8129136437953d412e2a6cf0ef87f4a461Chris Lattner storage_.resize(s, nullVal_); 59b7489d8129136437953d412e2a6cf0ef87f4a461Chris Lattner } 60b7489d8129136437953d412e2a6cf0ef87f4a461Chris Lattner 61b7489d8129136437953d412e2a6cf0ef87f4a461Chris Lattner void clear() { 62b7489d8129136437953d412e2a6cf0ef87f4a461Chris Lattner storage_.clear(); 63b7489d8129136437953d412e2a6cf0ef87f4a461Chris Lattner } 64b7489d8129136437953d412e2a6cf0ef87f4a461Chris Lattner 659dc1f530c086d2c16f8cba758b0f59a5bf41323aChris Lattner void grow(IndexT n) { 669dc1f530c086d2c16f8cba758b0f59a5bf41323aChris Lattner unsigned NewSize = toIndex_(n) + 1; 675f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer if (NewSize > storage_.size()) 685f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer resize(NewSize); 692c64b7b9381be4ff62fbdc404ed3f14c8086898dChris Lattner } 705f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer 712c64b7b9381be4ff62fbdc404ed3f14c8086898dChris Lattner bool inBounds(IndexT n) const { 725f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer return toIndex_(n) < storage_.size(); 735f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer } 745f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer 755f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer typename StorageT::size_type size() const { 764cabcfea26bc3465d8723fe7997ab4a1a657aea8Chris Lattner return storage_.size(); 775f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer } 789dc1f530c086d2c16f8cba758b0f59a5bf41323aChris Lattner }; 799dc1f530c086d2c16f8cba758b0f59a5bf41323aChris Lattner 805f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer} // End llvm namespace 815f016e2cb5d11daeb237544de1c5d59f20fe1a6eReid Spencer 82d1623a81992a24abbfcd5520b32a0dd90857b8a8Chris Lattner#endif 83d1623a81992a24abbfcd5520b32a0dd90857b8a8Chris Lattner