LLVM API Documentation

DenseMap.h

Go to the documentation of this file.
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