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