DenseMap.h revision 00fa65be8344944b080cd790678e027e10942ffd 
1//===- DenseMap.h - A dense map implmentation -------------------*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file was developed by the LLVM research group and is distributed under
6// the University of Illinois Open Source License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file implements a dense map. A dense map template takes two
11// types. The first is the mapped type and the second is a functor
12// that maps its argument to a size_t. On instantiation a "null" value
13// can be provided to be used as a "does not exist" indicator in the
14// map. A member function grow() is provided that given the value of
15// the maximally indexed key (the argument of the functor) makes sure
16// the map has enough space for it.
17//
18//===----------------------------------------------------------------------===//
19
20#ifndef SUPPORT_DENSEMAP_H
21#define SUPPORT_DENSEMAP_H
22
23#include <vector>
24
25namespace llvm {
26
27template <typename T, typename ToIndexT>
28class DenseMap {
29    typedef typename ToIndexT::argument_type IndexT;
30    typedef std::vector<T> StorageT;
31    StorageT storage_;
32    T nullVal_;
33    ToIndexT toIndex_;
34
35public:
36    DenseMap() { }
37
38    explicit DenseMap(const T& val) : nullVal_(val) { }
39
40    typename StorageT::reference operator[](IndexT n) {
41        assert(toIndex_(n) < storage_.size() && "index out of bounds!");
42        return storage_[toIndex_(n)];
43    }
44
45    typename StorageT::const_reference operator[](IndexT n) const {
46        assert(toIndex_(n) < storage_.size() && "index out of bounds!");
47        return storage_[toIndex_(n)];
48    }
49
50    void clear() {
51        storage_.clear();
52    }
53
54    void grow(IndexT n) {
55        unsigned NewSize = toIndex_(n) + 1;
56        if (NewSize > storage_.size())
57            storage_.resize(NewSize, nullVal_);
58    }
59};
60
61} // End llvm namespace
62
63#endif
64