MapVector.h revision 3b62b01f9a6fbecbc8aa22750d797459f8ae6417 
1//===- llvm/ADT/MapVector.h - Map with deterministic value order *- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file implements a map that also provides access to all stored values
11// in a deterministic order via the getValues method. Note that the iteration
12// order itself is just the DenseMap order and not deterministic. The interface
13// is purposefully minimal.
14//
15//===----------------------------------------------------------------------===//
16
17#ifndef LLVM_ADT_MAPVECTOR_H
18#define LLVM_ADT_MAPVECTOR_H
19
20#include "llvm/ADT/ArrayRef.h"
21#include "llvm/ADT/DenseMap.h"
22#include <vector>
23
24namespace llvm {
25
26/// This class implements a map that also provides access to all stored values
27/// in a deterministic order. The values are kept in a std::vector and the
28/// mapping is done with DenseMap from Keys to indexes in that vector.
29template<typename KeyT, typename ValueT>
30class MapVector {
31  typedef llvm::DenseMap<KeyT, unsigned> MapType;
32  typedef std::vector<ValueT> VectorType;
33  typedef typename VectorType::size_type SizeType;
34
35  MapType Map;
36  VectorType Vector;
37
38public:
39  // The keys and values are not stored close to each other, so the iterator
40  // operator->() cannot return a pointer to a std::pair like a DenseMap does.
41  // Instead it returns a FakePair that contains references to Key and Value.
42  // This lets code using this to look the same as if using a regular DenseMap.
43  template<bool IsConst>
44  struct FakePair {
45    typedef typename conditional<IsConst, const ValueT, ValueT>::type VT;
46    const KeyT &first;
47    VT &second;
48    FakePair(const KeyT &K, VT &V) : first(K), second(V) {
49    }
50    FakePair *operator->() {
51      return this;
52    }
53  };
54
55  template<bool IsConst>
56  class IteratorTemplate {
57    typedef typename MapType::const_iterator WrappedIteratorType;
58    WrappedIteratorType WrappedI;
59    typedef
60      typename conditional<IsConst, const VectorType, VectorType>::type VT;
61    VT &VecRef;
62    typedef FakePair<IsConst> PairType;
63    friend class IteratorTemplate<true>;
64
65  public:
66    IteratorTemplate(WrappedIteratorType I, VT &V) :
67      WrappedI(I), VecRef(V) {
68    }
69
70    // If IsConst is true this is a converting constructor from iterator to
71    // const_iterator and the default copy constructor is used.
72    // Otherwise this is a copy constructor for iterator.
73    IteratorTemplate(const IteratorTemplate<false>& I) :
74      WrappedI(I.WrappedI), VecRef(I.VecRef) {
75    }
76
77    bool operator!=(const IteratorTemplate &RHS) const {
78      return WrappedI != RHS.WrappedI;
79    }
80
81    IteratorTemplate &operator++() {  // Preincrement
82      ++WrappedI;
83      return *this;
84    }
85
86    PairType operator->() {
87      unsigned Pos = WrappedI->second;
88      PairType Ret(WrappedI->first, VecRef[Pos]);
89      return Ret;
90    }
91  };
92
93  typedef IteratorTemplate<false> iterator;
94  typedef IteratorTemplate<true> const_iterator;
95
96  SizeType size() const {
97    return Vector.size();
98  }
99
100  iterator begin() {
101    return iterator(Map.begin(), this->Vector);
102  }
103
104  const_iterator begin() const {
105    return const_iterator(Map.begin(), this->Vector);
106  }
107
108  iterator end() {
109    return iterator(Map.end(), this->Vector);
110  }
111
112  const_iterator end() const {
113    return const_iterator(Map.end(), this->Vector);
114  }
115
116  bool empty() const {
117    return Map.empty();
118  }
119
120  typedef typename VectorType::iterator value_iterator;
121  typedef typename VectorType::const_iterator const_value_iterator;
122
123  value_iterator value_begin() {
124    return Vector.begin();
125  }
126
127  const_value_iterator value_begin() const {
128    return Vector.begin();
129  }
130
131  value_iterator value_end() {
132    return Vector.end();
133  }
134
135  const_value_iterator value_end() const {
136    return Vector.end();
137  }
138
139  ValueT &operator[](const KeyT &Key) {
140    std::pair<KeyT, unsigned> Pair = std::make_pair(Key, 0);
141    std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
142    unsigned &I = Result.first->second;
143    if (Result.second) {
144      Vector.push_back(ValueT());
145      I = Vector.size() - 1;
146    }
147    return Vector[I];
148  }
149};
150
151}
152
153#endif
154