MapVector.h revision fc8657be3470e5b3b63705c9252251acba3c1606
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 <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 SizeType;
34
35  MapType Map;
36  VectorType Vector;
37
38public:
39  typedef typename VectorType::iterator iterator;
40  typedef typename VectorType::const_iterator const_iterator;
41
42  SizeType size() const {
43    return Vector.size();
44  }
45
46  iterator begin() {
47    return Vector.begin();
48  }
49
50  const_iterator begin() const {
51    return Vector.begin();
52  }
53
54  iterator end() {
55    return Vector.end();
56  }
57
58  const_iterator end() const {
59    return Vector.end();
60  }
61
62  bool empty() const {
63    return Vector.empty();
64  }
65
66  void clear() {
67    Map.clear();
68    Vector.clear();
69  }
70
71  ValueT &operator[](const KeyT &Key) {
72    std::pair<KeyT, unsigned> Pair = std::make_pair(Key, 0);
73    std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
74    unsigned &I = Result.first->second;
75    if (Result.second) {
76      Vector.push_back(std::make_pair(Key, ValueT()));
77      I = Vector.size() - 1;
78    }
79    return Vector[I].second;
80  }
81
82  ValueT lookup(const KeyT &Key) const {
83    typename MapType::const_iterator Pos = Map.find(Key);
84    return Pos == Map.end()? ValueT() : Vector[Pos->second].second;
85  }
86
87  unsigned count(const KeyT &Key) const {
88    typename MapType::const_iterator Pos = Map.find(Key);
89    return Pos == Map.end()? 0 : 1;
90  }
91
92  iterator find(const KeyT &Key) {
93    typename MapType::const_iterator Pos = Map.find(Key);
94    return Pos == Map.end()? Vector.end() :
95                            (Vector.begin() + Pos->second);
96  }
97
98  const_iterator find(const KeyT &Key) const {
99    typename MapType::const_iterator Pos = Map.find(Key);
100    return Pos == Map.end()? Vector.end() :
101                            (Vector.begin() + Pos->second);
102  }
103};
104
105}
106
107#endif
108