MapVector.h revision cd81d94322a39503e4a3e87b6ee03d4fcb3465fb 
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 <vector>
22
23namespace llvm {
24
25/// This class implements a map that also provides access to all stored values
26/// in a deterministic order. The values are kept in a std::vector and the
27/// mapping is done with DenseMap from Keys to indexes in that vector.
28template<typename KeyT, typename ValueT,
29         typename MapType = llvm::DenseMap<KeyT, unsigned>,
30         typename VectorType = std::vector<std::pair<KeyT, ValueT> > >
31class MapVector {
32  typedef typename VectorType::size_type size_type;
33
34  MapType Map;
35  VectorType Vector;
36
37public:
38  typedef typename VectorType::iterator iterator;
39  typedef typename VectorType::const_iterator const_iterator;
40
41  size_type size() const {
42    return Vector.size();
43  }
44
45  iterator begin() {
46    return Vector.begin();
47  }
48
49  const_iterator begin() const {
50    return Vector.begin();
51  }
52
53  iterator end() {
54    return Vector.end();
55  }
56
57  const_iterator end() const {
58    return Vector.end();
59  }
60
61  bool empty() const {
62    return Vector.empty();
63  }
64
65  std::pair<KeyT, ValueT>       &front()       { return Vector.front(); }
66  const std::pair<KeyT, ValueT> &front() const { return Vector.front(); }
67  std::pair<KeyT, ValueT>       &back()        { return Vector.back(); }
68  const std::pair<KeyT, ValueT> &back()  const { return Vector.back(); }
69
70  void clear() {
71    Map.clear();
72    Vector.clear();
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  /// Returns an iterator to the element following the one which was removed,
129  /// which may be end().
130  typename VectorType::iterator erase(typename VectorType::iterator Iterator) {
131    typename MapType::iterator MapIterator = Map.find(Iterator->first);
132    Map.erase(MapIterator);
133    return Vector.erase(Iterator);
134  }
135};
136
137}
138
139#endif
140