LLVM API Documentation
00001 //===- llvm/ADT/DenseMap.h - A dense map implmentation ----------*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements a dense map. A dense map template takes two 00011 // types. The first is the mapped type and the second is a functor 00012 // that maps its argument to a size_t. On instantiation a "null" value 00013 // can be provided to be used as a "does not exist" indicator in the 00014 // map. A member function grow() is provided that given the value of 00015 // the maximally indexed key (the argument of the functor) makes sure 00016 // the map has enough space for it. 00017 // 00018 //===----------------------------------------------------------------------===// 00019 00020 #ifndef LLVM_ADT_DENSEMAP_H 00021 #define LLVM_ADT_DENSEMAP_H 00022 00023 #include <functional> 00024 #include <vector> 00025 #include <cassert> 00026 00027 namespace llvm { 00028 00029 struct IdentityFunctor : std::unary_function<unsigned, unsigned> { 00030 unsigned operator()(unsigned Index) const { 00031 return Index; 00032 } 00033 }; 00034 00035 template <typename T, typename ToIndexT = IdentityFunctor> 00036 class DenseMap { 00037 typedef typename ToIndexT::argument_type IndexT; 00038 typedef std::vector<T> StorageT; 00039 StorageT storage_; 00040 T nullVal_; 00041 ToIndexT toIndex_; 00042 00043 public: 00044 DenseMap() : nullVal_(T()) { } 00045 00046 explicit DenseMap(const T& val) : nullVal_(val) { } 00047 00048 typename StorageT::reference operator[](IndexT n) { 00049 assert(toIndex_(n) < storage_.size() && "index out of bounds!"); 00050 return storage_[toIndex_(n)]; 00051 } 00052 00053 typename StorageT::const_reference operator[](IndexT n) const { 00054 assert(toIndex_(n) < storage_.size() && "index out of bounds!"); 00055 return storage_[toIndex_(n)]; 00056 } 00057 00058 void clear() { 00059 storage_.clear(); 00060 } 00061 00062 void grow(IndexT n) { 00063 unsigned NewSize = toIndex_(n) + 1; 00064 if (NewSize > storage_.size()) 00065 storage_.resize(NewSize, nullVal_); 00066 } 00067 00068 typename StorageT::size_type size() const { 00069 return storage_.size(); 00070 } 00071 }; 00072 00073 } // End llvm namespace 00074 00075 #endif