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