117 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef LLVM_LIB_TRANSFORMS_OBJCARC_BLOTMAPVECTOR_H10#define LLVM_LIB_TRANSFORMS_OBJCARC_BLOTMAPVECTOR_H11 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_CHECKS33 ~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#endif46 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 = Map.try_emplace(Arg);57 if (Pair.second) {58 size_t Num = Vector.size();59 Pair.first->second = Num;60 Vector.push_back(std::make_pair(Arg, ValueT()));61 return Vector[Num].second;62 }63 return Vector[Pair.first->second].second;64 }65 66 std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &InsertPair) {67 std::pair<typename MapTy::iterator, bool> Pair =68 Map.insert(std::make_pair(InsertPair.first, size_t(0)));69 if (Pair.second) {70 size_t Num = Vector.size();71 Pair.first->second = Num;72 Vector.push_back(InsertPair);73 return std::make_pair(Vector.begin() + Num, true);74 }75 return std::make_pair(Vector.begin() + Pair.first->second, false);76 }77 78 iterator find(const KeyT &Key) {79 typename MapTy::iterator It = Map.find(Key);80 if (It == Map.end())81 return Vector.end();82 return Vector.begin() + It->second;83 }84 85 const_iterator find(const KeyT &Key) const {86 typename MapTy::const_iterator It = Map.find(Key);87 if (It == Map.end())88 return Vector.end();89 return Vector.begin() + It->second;90 }91 92 /// This is similar to erase, but instead of removing the element from the93 /// vector, it just zeros out the key in the vector. This leaves iterators94 /// intact, but clients must be prepared for zeroed-out keys when iterating.95 void blot(const KeyT &Key) {96 typename MapTy::iterator It = Map.find(Key);97 if (It == Map.end())98 return;99 Vector[It->second].first = KeyT();100 Map.erase(It);101 }102 103 void clear() {104 Map.clear();105 Vector.clear();106 }107 108 bool empty() const {109 assert(Map.empty() == Vector.empty());110 return Map.empty();111 }112};113 114} // end namespace llvm115 116#endif // LLVM_LIB_TRANSFORMS_OBJCARC_BLOTMAPVECTOR_H117