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