1276479Sdim//===- llvm/ADT/MapVector.h - Map w/ deterministic value order --*- C++ -*-===// 2243789Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6243789Sdim// 7243789Sdim//===----------------------------------------------------------------------===// 8243789Sdim// 9243789Sdim// This file implements a map that provides insertion order iteration. The 10243789Sdim// interface is purposefully minimal. The key is assumed to be cheap to copy 11243789Sdim// and 2 copies are kept, one for indexing in a DenseMap, one for iteration in 12243789Sdim// a std::vector. 13243789Sdim// 14243789Sdim//===----------------------------------------------------------------------===// 15243789Sdim 16243789Sdim#ifndef LLVM_ADT_MAPVECTOR_H 17243789Sdim#define LLVM_ADT_MAPVECTOR_H 18243789Sdim 19243789Sdim#include "llvm/ADT/DenseMap.h" 20280031Sdim#include "llvm/ADT/SmallVector.h" 21321369Sdim#include <algorithm> 22321369Sdim#include <cassert> 23321369Sdim#include <cstddef> 24321369Sdim#include <iterator> 25321369Sdim#include <type_traits> 26321369Sdim#include <utility> 27243789Sdim#include <vector> 28243789Sdim 29243789Sdimnamespace llvm { 30243789Sdim 31243789Sdim/// This class implements a map that also provides access to all stored values 32243789Sdim/// in a deterministic order. The values are kept in a std::vector and the 33243789Sdim/// mapping is done with DenseMap from Keys to indexes in that vector. 34243789Sdimtemplate<typename KeyT, typename ValueT, 35321369Sdim typename MapType = DenseMap<KeyT, unsigned>, 36321369Sdim typename VectorType = std::vector<std::pair<KeyT, ValueT>>> 37243789Sdimclass MapVector { 38243789Sdim MapType Map; 39243789Sdim VectorType Vector; 40243789Sdim 41341825Sdim static_assert( 42341825Sdim std::is_integral<typename MapType::mapped_type>::value, 43341825Sdim "The mapped_type of the specified Map must be an integral type"); 44341825Sdim 45243789Sdimpublic: 46341825Sdim using value_type = typename VectorType::value_type; 47341825Sdim using size_type = typename VectorType::size_type; 48341825Sdim 49321369Sdim using iterator = typename VectorType::iterator; 50321369Sdim using const_iterator = typename VectorType::const_iterator; 51321369Sdim using reverse_iterator = typename VectorType::reverse_iterator; 52321369Sdim using const_reverse_iterator = typename VectorType::const_reverse_iterator; 53243789Sdim 54314564Sdim /// Clear the MapVector and return the underlying vector. 55314564Sdim VectorType takeVector() { 56314564Sdim Map.clear(); 57314564Sdim return std::move(Vector); 58314564Sdim } 59314564Sdim 60280031Sdim size_type size() const { return Vector.size(); } 61243789Sdim 62327952Sdim /// Grow the MapVector so that it can contain at least \p NumEntries items 63327952Sdim /// before resizing again. 64327952Sdim void reserve(size_type NumEntries) { 65327952Sdim Map.reserve(NumEntries); 66327952Sdim Vector.reserve(NumEntries); 67327952Sdim } 68327952Sdim 69280031Sdim iterator begin() { return Vector.begin(); } 70280031Sdim const_iterator begin() const { return Vector.begin(); } 71280031Sdim iterator end() { return Vector.end(); } 72280031Sdim const_iterator end() const { return Vector.end(); } 73243789Sdim 74280031Sdim reverse_iterator rbegin() { return Vector.rbegin(); } 75280031Sdim const_reverse_iterator rbegin() const { return Vector.rbegin(); } 76280031Sdim reverse_iterator rend() { return Vector.rend(); } 77280031Sdim const_reverse_iterator rend() const { return Vector.rend(); } 78243789Sdim 79243789Sdim bool empty() const { 80243789Sdim return Vector.empty(); 81243789Sdim } 82243789Sdim 83249423Sdim std::pair<KeyT, ValueT> &front() { return Vector.front(); } 84249423Sdim const std::pair<KeyT, ValueT> &front() const { return Vector.front(); } 85249423Sdim std::pair<KeyT, ValueT> &back() { return Vector.back(); } 86249423Sdim const std::pair<KeyT, ValueT> &back() const { return Vector.back(); } 87249423Sdim 88243789Sdim void clear() { 89243789Sdim Map.clear(); 90243789Sdim Vector.clear(); 91243789Sdim } 92243789Sdim 93288943Sdim void swap(MapVector &RHS) { 94288943Sdim std::swap(Map, RHS.Map); 95288943Sdim std::swap(Vector, RHS.Vector); 96288943Sdim } 97288943Sdim 98243789Sdim ValueT &operator[](const KeyT &Key) { 99341825Sdim std::pair<KeyT, typename MapType::mapped_type> Pair = std::make_pair(Key, 0); 100243789Sdim std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair); 101341825Sdim auto &I = Result.first->second; 102243789Sdim if (Result.second) { 103243789Sdim Vector.push_back(std::make_pair(Key, ValueT())); 104243789Sdim I = Vector.size() - 1; 105243789Sdim } 106243789Sdim return Vector[I].second; 107243789Sdim } 108243789Sdim 109314564Sdim // Returns a copy of the value. Only allowed if ValueT is copyable. 110249423Sdim ValueT lookup(const KeyT &Key) const { 111314564Sdim static_assert(std::is_copy_constructible<ValueT>::value, 112314564Sdim "Cannot call lookup() if ValueT is not copyable."); 113249423Sdim typename MapType::const_iterator Pos = Map.find(Key); 114249423Sdim return Pos == Map.end()? ValueT() : Vector[Pos->second].second; 115249423Sdim } 116249423Sdim 117249423Sdim std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { 118341825Sdim std::pair<KeyT, typename MapType::mapped_type> Pair = std::make_pair(KV.first, 0); 119249423Sdim std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair); 120341825Sdim auto &I = Result.first->second; 121249423Sdim if (Result.second) { 122249423Sdim Vector.push_back(std::make_pair(KV.first, KV.second)); 123249423Sdim I = Vector.size() - 1; 124276479Sdim return std::make_pair(std::prev(end()), true); 125249423Sdim } 126249423Sdim return std::make_pair(begin() + I, false); 127249423Sdim } 128249423Sdim 129314564Sdim std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) { 130314564Sdim // Copy KV.first into the map, then move it into the vector. 131341825Sdim std::pair<KeyT, typename MapType::mapped_type> Pair = std::make_pair(KV.first, 0); 132314564Sdim std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair); 133341825Sdim auto &I = Result.first->second; 134314564Sdim if (Result.second) { 135314564Sdim Vector.push_back(std::move(KV)); 136314564Sdim I = Vector.size() - 1; 137314564Sdim return std::make_pair(std::prev(end()), true); 138314564Sdim } 139314564Sdim return std::make_pair(begin() + I, false); 140314564Sdim } 141314564Sdim 142276479Sdim size_type count(const KeyT &Key) const { 143243789Sdim typename MapType::const_iterator Pos = Map.find(Key); 144243789Sdim return Pos == Map.end()? 0 : 1; 145243789Sdim } 146249423Sdim 147249423Sdim iterator find(const KeyT &Key) { 148249423Sdim typename MapType::const_iterator Pos = Map.find(Key); 149249423Sdim return Pos == Map.end()? Vector.end() : 150249423Sdim (Vector.begin() + Pos->second); 151249423Sdim } 152249423Sdim 153249423Sdim const_iterator find(const KeyT &Key) const { 154249423Sdim typename MapType::const_iterator Pos = Map.find(Key); 155249423Sdim return Pos == Map.end()? Vector.end() : 156249423Sdim (Vector.begin() + Pos->second); 157249423Sdim } 158249423Sdim 159341825Sdim /// Remove the last element from the vector. 160249423Sdim void pop_back() { 161249423Sdim typename MapType::iterator Pos = Map.find(Vector.back().first); 162249423Sdim Map.erase(Pos); 163249423Sdim Vector.pop_back(); 164249423Sdim } 165276479Sdim 166341825Sdim /// Remove the element given by Iterator. 167276479Sdim /// 168276479Sdim /// Returns an iterator to the element following the one which was removed, 169276479Sdim /// which may be end(). 170276479Sdim /// 171276479Sdim /// \note This is a deceivingly expensive operation (linear time). It's 172276479Sdim /// usually better to use \a remove_if() if possible. 173276479Sdim typename VectorType::iterator erase(typename VectorType::iterator Iterator) { 174276479Sdim Map.erase(Iterator->first); 175276479Sdim auto Next = Vector.erase(Iterator); 176276479Sdim if (Next == Vector.end()) 177276479Sdim return Next; 178276479Sdim 179276479Sdim // Update indices in the map. 180276479Sdim size_t Index = Next - Vector.begin(); 181276479Sdim for (auto &I : Map) { 182276479Sdim assert(I.second != Index && "Index was already erased!"); 183276479Sdim if (I.second > Index) 184276479Sdim --I.second; 185276479Sdim } 186276479Sdim return Next; 187276479Sdim } 188276479Sdim 189341825Sdim /// Remove all elements with the key value Key. 190280031Sdim /// 191280031Sdim /// Returns the number of elements removed. 192280031Sdim size_type erase(const KeyT &Key) { 193280031Sdim auto Iterator = find(Key); 194280031Sdim if (Iterator == end()) 195280031Sdim return 0; 196280031Sdim erase(Iterator); 197280031Sdim return 1; 198280031Sdim } 199280031Sdim 200341825Sdim /// Remove the elements that match the predicate. 201276479Sdim /// 202276479Sdim /// Erase all elements that match \c Pred in a single pass. Takes linear 203276479Sdim /// time. 204276479Sdim template <class Predicate> void remove_if(Predicate Pred); 205243789Sdim}; 206243789Sdim 207276479Sdimtemplate <typename KeyT, typename ValueT, typename MapType, typename VectorType> 208276479Sdimtemplate <class Function> 209276479Sdimvoid MapVector<KeyT, ValueT, MapType, VectorType>::remove_if(Function Pred) { 210276479Sdim auto O = Vector.begin(); 211276479Sdim for (auto I = O, E = Vector.end(); I != E; ++I) { 212276479Sdim if (Pred(*I)) { 213276479Sdim // Erase from the map. 214276479Sdim Map.erase(I->first); 215276479Sdim continue; 216276479Sdim } 217276479Sdim 218276479Sdim if (I != O) { 219276479Sdim // Move the value and update the index in the map. 220276479Sdim *O = std::move(*I); 221276479Sdim Map[O->first] = O - Vector.begin(); 222276479Sdim } 223276479Sdim ++O; 224276479Sdim } 225276479Sdim // Erase trailing entries in the vector. 226276479Sdim Vector.erase(O, Vector.end()); 227243789Sdim} 228243789Sdim 229341825Sdim/// A MapVector that performs no allocations if smaller than a certain 230280031Sdim/// size. 231280031Sdimtemplate <typename KeyT, typename ValueT, unsigned N> 232280031Sdimstruct SmallMapVector 233280031Sdim : MapVector<KeyT, ValueT, SmallDenseMap<KeyT, unsigned, N>, 234280031Sdim SmallVector<std::pair<KeyT, ValueT>, N>> { 235280031Sdim}; 236280031Sdim 237276479Sdim} // end namespace llvm 238276479Sdim 239321369Sdim#endif // LLVM_ADT_MAPVECTOR_H 240