llvm/lib/Transforms/ObjCARC/BlotMapVector.h

   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
  18 namespace llvm {
  19
  20 /// An associative container with fast insertion-order (deterministic)
  21 /// iteration over its elements. Plus the special blot operation.
  22 template <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
  31 public:
  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