MapVector.h revision 888fae7b49f5d39f2371edb78566476396e30c75 
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  std::pair<KeyT, ValueT>       &front()       { return Vector.front(); }
68  const std::pair<KeyT, ValueT> &front() const { return Vector.front(); }
69  std::pair<KeyT, ValueT>       &back()        { return Vector.back(); }
70  const std::pair<KeyT, ValueT> &back()  const { return Vector.back(); }
71
72  void clear() {
73    Map.clear();
74    Vector.clear();
75  }
76
77  ValueT &operator[](const KeyT &Key) {
78    std::pair<KeyT, unsigned> Pair = std::make_pair(Key, 0);
79    std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
80    unsigned &I = Result.first->second;
81    if (Result.second) {
82      Vector.push_back(std::make_pair(Key, ValueT()));
83      I = Vector.size() - 1;
84    }
85    return Vector[I].second;
86  }
87
88  ValueT lookup(const KeyT &Key) const {
89    typename MapType::const_iterator Pos = Map.find(Key);
90    return Pos == Map.end()? ValueT() : Vector[Pos->second].second;
91  }
92
93  std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
94    std::pair<KeyT, unsigned> Pair = std::make_pair(KV.first, 0);
95    std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
96    unsigned &I = Result.first->second;
97    if (Result.second) {
98      Vector.push_back(std::make_pair(KV.first, KV.second));
99      I = Vector.size() - 1;
100      return std::make_pair(llvm::prior(end()), true);
101    }
102    return std::make_pair(begin() + I, false);
103  }
104
105  unsigned count(const KeyT &Key) const {
106    typename MapType::const_iterator Pos = Map.find(Key);
107    return Pos == Map.end()? 0 : 1;
108  }
109
110  iterator find(const KeyT &Key) {
111    typename MapType::const_iterator Pos = Map.find(Key);
112    return Pos == Map.end()? Vector.end() :
113                            (Vector.begin() + Pos->second);
114  }
115
116  const_iterator find(const KeyT &Key) const {
117    typename MapType::const_iterator Pos = Map.find(Key);
118    return Pos == Map.end()? Vector.end() :
119                            (Vector.begin() + Pos->second);
120  }
121
122  /// \brief Erase entry with the given key.
123  void erase(const KeyT &key) {
124    typename MapType::iterator Pos = Map.find(key);
125    if (Pos == Map.end())
126      return;
127
128    Vector.erase(Vector.begin() + Pos->second);
129    Map.erase(Pos);
130  }
131};
132
133}
134
135#endif
136