BlotMapVector.h revision 321369 
1//===- BlotMapVector.h - A MapVector with the blot operation -*- 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#include "llvm/ADT/DenseMap.h"
11#include <algorithm>
12#include <vector>
13
14namespace llvm {
15/// \brief An associative container with fast insertion-order (deterministic)
16/// iteration over its elements. Plus the special blot operation.
17template <class KeyT, class ValueT> class BlotMapVector {
18  /// Map keys to indices in Vector.
19  typedef DenseMap<KeyT, size_t> MapTy;
20  MapTy Map;
21
22  typedef std::vector<std::pair<KeyT, ValueT>> VectorTy;
23  /// Keys and values.
24  VectorTy Vector;
25
26public:
27  typedef typename VectorTy::iterator iterator;
28  typedef typename VectorTy::const_iterator const_iterator;
29  iterator begin() { return Vector.begin(); }
30  iterator end() { return Vector.end(); }
31  const_iterator begin() const { return Vector.begin(); }
32  const_iterator end() const { return Vector.end(); }
33
34#ifdef EXPENSIVE_CHECKS
35  ~BlotMapVector() {
36    assert(Vector.size() >= Map.size()); // May differ due to blotting.
37    for (typename MapTy::const_iterator I = Map.begin(), E = Map.end(); I != E;
38         ++I) {
39      assert(I->second < Vector.size());
40      assert(Vector[I->second].first == I->first);
41    }
42    for (typename VectorTy::const_iterator I = Vector.begin(), E = Vector.end();
43         I != E; ++I)
44      assert(!I->first || (Map.count(I->first) &&
45                           Map[I->first] == size_t(I - Vector.begin())));
46  }
47#endif
48
49  ValueT &operator[](const KeyT &Arg) {
50    std::pair<typename MapTy::iterator, bool> Pair =
51        Map.insert(std::make_pair(Arg, size_t(0)));
52    if (Pair.second) {
53      size_t Num = Vector.size();
54      Pair.first->second = Num;
55      Vector.push_back(std::make_pair(Arg, ValueT()));
56      return Vector[Num].second;
57    }
58    return Vector[Pair.first->second].second;
59  }
60
61  std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &InsertPair) {
62    std::pair<typename MapTy::iterator, bool> Pair =
63        Map.insert(std::make_pair(InsertPair.first, size_t(0)));
64    if (Pair.second) {
65      size_t Num = Vector.size();
66      Pair.first->second = Num;
67      Vector.push_back(InsertPair);
68      return std::make_pair(Vector.begin() + Num, true);
69    }
70    return std::make_pair(Vector.begin() + Pair.first->second, false);
71  }
72
73  iterator find(const KeyT &Key) {
74    typename MapTy::iterator It = Map.find(Key);
75    if (It == Map.end())
76      return Vector.end();
77    return Vector.begin() + It->second;
78  }
79
80  const_iterator find(const KeyT &Key) const {
81    typename MapTy::const_iterator It = Map.find(Key);
82    if (It == Map.end())
83      return Vector.end();
84    return Vector.begin() + It->second;
85  }
86
87  /// This is similar to erase, but instead of removing the element from the
88  /// vector, it just zeros out the key in the vector. This leaves iterators
89  /// intact, but clients must be prepared for zeroed-out keys when iterating.
90  void blot(const KeyT &Key) {
91    typename MapTy::iterator It = Map.find(Key);
92    if (It == Map.end())
93      return;
94    Vector[It->second].first = KeyT();
95    Map.erase(It);
96  }
97
98  void clear() {
99    Map.clear();
100    Vector.clear();
101  }
102
103  bool empty() const {
104    assert(Map.empty() == Vector.empty());
105    return Map.empty();
106  }
107};
108} //
109