12061Sjkh//===- BlotMapVector.h - A MapVector with the blot operation ----*- C++ -*-===// 250479Speter// 32061Sjkh// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 438666Sjb// See https://llvm.org/LICENSE.txt for license information. 532427Sjb// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6111131Sru// 7111131Sru//===----------------------------------------------------------------------===// 8217733Sbz 9217733Sbz#ifndef LLVM_LIB_TRANSFORMS_OBJCARC_BLOTMAPVECTOR_H 1038666Sjb#define LLVM_LIB_TRANSFORMS_OBJCARC_BLOTMAPVECTOR_H 1138666Sjb 1238666Sjb#include "llvm/ADT/DenseMap.h" 13159363Strhodes#include <cassert> 1464049Salex#include <cstddef> 1564049Salex#include <utility> 16116679Ssimokawa#include <vector> 1766071Smarkm 18116679Ssimokawanamespace llvm { 1973504Sobrien 20204661Simp/// An associative container with fast insertion-order (deterministic) 21232907Sjmallett/// iteration over its elements. Plus the special blot operation. 22158962Snetchildtemplate <class KeyT, class ValueT> class BlotMapVector { 23223148Sru /// Map keys to indices in Vector. 24169597Sdes using MapTy = DenseMap<KeyT, size_t>; 25169597Sdes MapTy Map; 26169597Sdes 27169597Sdes /// Keys and values. 28231821Spluknet using VectorTy = std::vector<std::pair<KeyT, ValueT>>; 29169597Sdes VectorTy Vector; 30169597Sdes 31169597Sdespublic: 32217815Sbz#ifdef EXPENSIVE_CHECKS 33217815Sbz ~BlotMapVector() { 34218524Sjhb assert(Vector.size() >= Map.size()); // May differ due to blotting. 35253002Salfred for (typename MapTy::const_iterator I = Map.begin(), E = Map.end(); I != E; 36253002Salfred ++I) { 37253002Salfred assert(I->second < Vector.size()); 38253002Salfred assert(Vector[I->second].first == I->first); 39253002Salfred } 40253003Salfred for (typename VectorTy::const_iterator I = Vector.begin(), E = Vector.end(); 4132427Sjb I != E; ++I) 4238666Sjb assert(!I->first || (Map.count(I->first) && 43108451Sschweikh Map[I->first] == size_t(I - Vector.begin()))); 4438666Sjb } 4538666Sjb#endif 4638666Sjb 4738666Sjb using iterator = typename VectorTy::iterator; 4817308Speter using const_iterator = typename VectorTy::const_iterator; 49217273Simp 50217294Simp iterator begin() { return Vector.begin(); } 5119175Sbde iterator end() { return Vector.end(); } 5296205Sjwd const_iterator begin() const { return Vector.begin(); } 53217297Simp const_iterator end() const { return Vector.end(); } 54217297Simp 5538042Sbde ValueT &operator[](const KeyT &Arg) { 5696205Sjwd std::pair<typename MapTy::iterator, bool> Pair = 5796205Sjwd Map.insert(std::make_pair(Arg, size_t(0))); 5838042Sbde if (Pair.second) { 5996205Sjwd size_t Num = Vector.size(); 60159363Strhodes Pair.first->second = Num; 61159363Strhodes Vector.push_back(std::make_pair(Arg, ValueT())); 6217308Speter return Vector[Num].second; 6396205Sjwd } 6496205Sjwd return Vector[Pair.first->second].second; 6517308Speter } 66148330Snetchild 67148330Snetchild std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &InsertPair) { 68148330Snetchild std::pair<typename MapTy::iterator, bool> Pair = 69148330Snetchild Map.insert(std::make_pair(InsertPair.first, size_t(0))); 70159831Sobrien if (Pair.second) { 71148330Snetchild size_t Num = Vector.size(); 72148330Snetchild Pair.first->second = Num; 73148330Snetchild Vector.push_back(InsertPair); 74251107Screes return std::make_pair(Vector.begin() + Num, true); 75251107Screes } 76148330Snetchild return std::make_pair(Vector.begin() + Pair.first->second, false); 77148330Snetchild } 7896205Sjwd 7996205Sjwd iterator find(const KeyT &Key) { 8096205Sjwd typename MapTy::iterator It = Map.find(Key); 81162147Sru if (It == Map.end()) 82162147Sru return Vector.end(); 8398723Sdillon return Vector.begin() + It->second; 8498723Sdillon } 8598723Sdillon 8638666Sjb const_iterator find(const KeyT &Key) const { 8738666Sjb typename MapTy::const_iterator It = Map.find(Key); 8817308Speter if (It == Map.end()) 89123311Speter return Vector.end(); 90123311Speter return Vector.begin() + It->second; 91123311Speter } 92123311Speter 93175833Sjhb /// This is similar to erase, but instead of removing the element from the 94175833Sjhb /// vector, it just zeros out the key in the vector. This leaves iterators 95169597Sdes /// intact, but clients must be prepared for zeroed-out keys when iterating. 96169597Sdes void blot(const KeyT &Key) { 97169597Sdes typename MapTy::iterator It = Map.find(Key); 98169597Sdes if (It == Map.end()) 99219177Snwhitehorn return; 100219177Snwhitehorn Vector[It->second].first = KeyT(); 101238051Sobrien Map.erase(It); 102219177Snwhitehorn } 103219177Snwhitehorn 104158962Snetchild void clear() { 105156840Sru Map.clear(); 106123311Speter Vector.clear(); 107137288Speter } 108209128Sraj 109209128Sraj bool empty() const { 110156740Sru assert(Map.empty() == Vector.empty()); 1112061Sjkh return Map.empty(); 11297769Sru } 11397252Sru}; 114119579Sru 11597252Sru} // end namespace llvm 11695730Sru 11795793Sru#endif // LLVM_LIB_TRANSFORMS_OBJCARC_BLOTMAPVECTOR_H 118111617Sru