MapVector.h revision 6bbf4ff9c545c881422da37494b1ccb9c18d9c6a
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 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/ArrayRef.h"
21#include "llvm/ADT/DenseMap.h"
22#include "llvm/ADT/STLExtras.h"
23#include <vector>
24
25namespace llvm {
26
27/// This class implements a map that also provides access to all stored values
28/// in a deterministic order. The values are kept in a std::vector and the
29/// mapping is done with DenseMap from Keys to indexes in that vector.
30template<typename KeyT, typename ValueT,
31         typename MapType = llvm::DenseMap<KeyT, unsigned>,
32         typename VectorType = std::vector<std::pair<KeyT, ValueT> > >
33class MapVector {
34  typedef typename VectorType::size_type SizeType;
35
36  MapType Map;
37  VectorType Vector;
38
39public:
40  typedef typename VectorType::iterator iterator;
41  typedef typename VectorType::const_iterator const_iterator;
42
43  SizeType size() const {
44    return Vector.size();
45  }
46
47  iterator begin() {
48    return Vector.begin();
49  }
50
51  const_iterator begin() const {
52    return Vector.begin();
53  }
54
55  iterator end() {
56    return Vector.end();
57  }
58
59  const_iterator end() const {
60    return Vector.end();
61  }
62
63  bool empty() const {
64    return Vector.empty();
65  }
66
67  void clear() {
68    Map.clear();
69    Vector.clear();
70  }
71
72  ValueT &operator[](const KeyT &Key) {
73    std::pair<KeyT, unsigned> Pair = std::make_pair(Key, 0);
74    std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
75    unsigned &I = Result.first->second;
76    if (Result.second) {
77      Vector.push_back(std::make_pair(Key, ValueT()));
78      I = Vector.size() - 1;
79    }
80    return Vector[I].second;
81  }
82
83  ValueT lookup(const KeyT &Key) const {
84    typename MapType::const_iterator Pos = Map.find(Key);
85    return Pos == Map.end()? ValueT() : Vector[Pos->second].second;
86  }
87
88  std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
89    std::pair<KeyT, unsigned> Pair = std::make_pair(KV.first, 0);
90    std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
91    unsigned &I = Result.first->second;
92    if (Result.second) {
93      Vector.push_back(std::make_pair(KV.first, KV.second));
94      I = Vector.size() - 1;
95      return std::make_pair(llvm::prior(end()), true);
96    }
97    return std::make_pair(begin() + I, false);
98  }
99
100  unsigned count(const KeyT &Key) const {
101    typename MapType::const_iterator Pos = Map.find(Key);
102    return Pos == Map.end()? 0 : 1;
103  }
104
105  iterator find(const KeyT &Key) {
106    typename MapType::const_iterator Pos = Map.find(Key);
107    return Pos == Map.end()? Vector.end() :
108                            (Vector.begin() + Pos->second);
109  }
110
111  const_iterator find(const KeyT &Key) const {
112    typename MapType::const_iterator Pos = Map.find(Key);
113    return Pos == Map.end()? Vector.end() :
114                            (Vector.begin() + Pos->second);
115  }
116};
117
118}
119
120#endif
121