1 //===- llvm/ADT/MapVector.h - Map w/ 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 provides insertion order iteration. The
11 // interface is purposefully minimal. The key is assumed to be cheap to copy
12 // and 2 copies are kept, one for indexing in a DenseMap, one for iteration in
13 // a std::vector.
14 //
15 //===----------------------------------------------------------------------===//
16
17 #ifndef LLVM_ADT_MAPVECTOR_H
18 #define LLVM_ADT_MAPVECTOR_H
19
20 #include "llvm/ADT/DenseMap.h"
21 #include "llvm/ADT/SmallVector.h"
22 #include <vector>
23
24 namespace 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.
29 template<typename KeyT, typename ValueT,
30 typename MapType = llvm::DenseMap<KeyT, unsigned>,
31 typename VectorType = std::vector<std::pair<KeyT, ValueT> > >
32 class MapVector {
33 typedef typename VectorType::size_type size_type;
34
35 MapType Map;
36 VectorType Vector;
37
38 public:
39 typedef typename VectorType::iterator iterator;
40 typedef typename VectorType::const_iterator const_iterator;
41 typedef typename VectorType::reverse_iterator reverse_iterator;
42 typedef typename VectorType::const_reverse_iterator const_reverse_iterator;
43
size()44 size_type size() const { return Vector.size(); }
45
begin()46 iterator begin() { return Vector.begin(); }
begin()47 const_iterator begin() const { return Vector.begin(); }
end()48 iterator end() { return Vector.end(); }
end()49 const_iterator end() const { return Vector.end(); }
50
rbegin()51 reverse_iterator rbegin() { return Vector.rbegin(); }
rbegin()52 const_reverse_iterator rbegin() const { return Vector.rbegin(); }
rend()53 reverse_iterator rend() { return Vector.rend(); }
rend()54 const_reverse_iterator rend() const { return Vector.rend(); }
55
empty()56 bool empty() const {
57 return Vector.empty();
58 }
59
front()60 std::pair<KeyT, ValueT> &front() { return Vector.front(); }
front()61 const std::pair<KeyT, ValueT> &front() const { return Vector.front(); }
back()62 std::pair<KeyT, ValueT> &back() { return Vector.back(); }
back()63 const std::pair<KeyT, ValueT> &back() const { return Vector.back(); }
64
clear()65 void clear() {
66 Map.clear();
67 Vector.clear();
68 }
69
70 ValueT &operator[](const KeyT &Key) {
71 std::pair<KeyT, unsigned> Pair = std::make_pair(Key, 0);
72 std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
73 unsigned &I = Result.first->second;
74 if (Result.second) {
75 Vector.push_back(std::make_pair(Key, ValueT()));
76 I = Vector.size() - 1;
77 }
78 return Vector[I].second;
79 }
80
lookup(const KeyT & Key)81 ValueT lookup(const KeyT &Key) const {
82 typename MapType::const_iterator Pos = Map.find(Key);
83 return Pos == Map.end()? ValueT() : Vector[Pos->second].second;
84 }
85
insert(const std::pair<KeyT,ValueT> & KV)86 std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
87 std::pair<KeyT, unsigned> Pair = std::make_pair(KV.first, 0);
88 std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
89 unsigned &I = Result.first->second;
90 if (Result.second) {
91 Vector.push_back(std::make_pair(KV.first, KV.second));
92 I = Vector.size() - 1;
93 return std::make_pair(std::prev(end()), true);
94 }
95 return std::make_pair(begin() + I, false);
96 }
97
count(const KeyT & Key)98 size_type count(const KeyT &Key) const {
99 typename MapType::const_iterator Pos = Map.find(Key);
100 return Pos == Map.end()? 0 : 1;
101 }
102
find(const KeyT & Key)103 iterator find(const KeyT &Key) {
104 typename MapType::const_iterator Pos = Map.find(Key);
105 return Pos == Map.end()? Vector.end() :
106 (Vector.begin() + Pos->second);
107 }
108
find(const KeyT & Key)109 const_iterator find(const KeyT &Key) const {
110 typename MapType::const_iterator Pos = Map.find(Key);
111 return Pos == Map.end()? Vector.end() :
112 (Vector.begin() + Pos->second);
113 }
114
115 /// \brief Remove the last element from the vector.
pop_back()116 void pop_back() {
117 typename MapType::iterator Pos = Map.find(Vector.back().first);
118 Map.erase(Pos);
119 Vector.pop_back();
120 }
121
122 /// \brief Remove the element given by Iterator.
123 ///
124 /// Returns an iterator to the element following the one which was removed,
125 /// which may be end().
126 ///
127 /// \note This is a deceivingly expensive operation (linear time). It's
128 /// usually better to use \a remove_if() if possible.
erase(typename VectorType::iterator Iterator)129 typename VectorType::iterator erase(typename VectorType::iterator Iterator) {
130 Map.erase(Iterator->first);
131 auto Next = Vector.erase(Iterator);
132 if (Next == Vector.end())
133 return Next;
134
135 // Update indices in the map.
136 size_t Index = Next - Vector.begin();
137 for (auto &I : Map) {
138 assert(I.second != Index && "Index was already erased!");
139 if (I.second > Index)
140 --I.second;
141 }
142 return Next;
143 }
144
145 /// \brief Remove all elements with the key value Key.
146 ///
147 /// Returns the number of elements removed.
erase(const KeyT & Key)148 size_type erase(const KeyT &Key) {
149 auto Iterator = find(Key);
150 if (Iterator == end())
151 return 0;
152 erase(Iterator);
153 return 1;
154 }
155
156 /// \brief Remove the elements that match the predicate.
157 ///
158 /// Erase all elements that match \c Pred in a single pass. Takes linear
159 /// time.
160 template <class Predicate> void remove_if(Predicate Pred);
161 };
162
163 template <typename KeyT, typename ValueT, typename MapType, typename VectorType>
164 template <class Function>
remove_if(Function Pred)165 void MapVector<KeyT, ValueT, MapType, VectorType>::remove_if(Function Pred) {
166 auto O = Vector.begin();
167 for (auto I = O, E = Vector.end(); I != E; ++I) {
168 if (Pred(*I)) {
169 // Erase from the map.
170 Map.erase(I->first);
171 continue;
172 }
173
174 if (I != O) {
175 // Move the value and update the index in the map.
176 *O = std::move(*I);
177 Map[O->first] = O - Vector.begin();
178 }
179 ++O;
180 }
181 // Erase trailing entries in the vector.
182 Vector.erase(O, Vector.end());
183 }
184
185 /// \brief A MapVector that performs no allocations if smaller than a certain
186 /// size.
187 template <typename KeyT, typename ValueT, unsigned N>
188 struct SmallMapVector
189 : MapVector<KeyT, ValueT, SmallDenseMap<KeyT, unsigned, N>,
190 SmallVector<std::pair<KeyT, ValueT>, N>> {
191 };
192
193 } // end namespace llvm
194
195 #endif
196