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