136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines//===- llvm/ADT/MapVector.h - Map w/ deterministic value order --*- C++ -*-===// 23b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola// 33b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola// The LLVM Compiler Infrastructure 43b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola// 53b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola// This file is distributed under the University of Illinois Open Source 63b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola// License. See LICENSE.TXT for details. 73b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola// 83b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola//===----------------------------------------------------------------------===// 93b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola// 10c312f098999d4640cf91934632ccecfc9ef30b85Rafael Espindola// This file implements a map that provides insertion order iteration. The 11c312f098999d4640cf91934632ccecfc9ef30b85Rafael Espindola// interface is purposefully minimal. The key is assumed to be cheap to copy 12c312f098999d4640cf91934632ccecfc9ef30b85Rafael Espindola// and 2 copies are kept, one for indexing in a DenseMap, one for iteration in 13c312f098999d4640cf91934632ccecfc9ef30b85Rafael Espindola// a std::vector. 143b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola// 153b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola//===----------------------------------------------------------------------===// 163b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola 173b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola#ifndef LLVM_ADT_MAPVECTOR_H 183b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola#define LLVM_ADT_MAPVECTOR_H 193b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola 203b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola#include "llvm/ADT/DenseMap.h" 213b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola#include <vector> 223b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola 233b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindolanamespace llvm { 243b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola 253b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola/// This class implements a map that also provides access to all stored values 263b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola/// in a deterministic order. The values are kept in a std::vector and the 273b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola/// mapping is done with DenseMap from Keys to indexes in that vector. 28289c39965b1b799a22534d759fdf0a26302430d7Douglas Gregortemplate<typename KeyT, typename ValueT, 29289c39965b1b799a22534d759fdf0a26302430d7Douglas Gregor typename MapType = llvm::DenseMap<KeyT, unsigned>, 3062430fd1a1d901956dfbac7b0ab49e2e653d6fc5Douglas Gregor typename VectorType = std::vector<std::pair<KeyT, ValueT> > > 313b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindolaclass MapVector { 32cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines typedef typename VectorType::size_type size_type; 333b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola 343b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola MapType Map; 353b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola VectorType Vector; 363b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola 373b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindolapublic: 38c312f098999d4640cf91934632ccecfc9ef30b85Rafael Espindola typedef typename VectorType::iterator iterator; 39c312f098999d4640cf91934632ccecfc9ef30b85Rafael Espindola typedef typename VectorType::const_iterator const_iterator; 403b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola 41cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines size_type size() const { 423b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola return Vector.size(); 433b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola } 443b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola 453b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola iterator begin() { 46c312f098999d4640cf91934632ccecfc9ef30b85Rafael Espindola return Vector.begin(); 473b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola } 483b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola 493b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola const_iterator begin() const { 50c312f098999d4640cf91934632ccecfc9ef30b85Rafael Espindola return Vector.begin(); 513b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola } 523b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola 533b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola iterator end() { 54c312f098999d4640cf91934632ccecfc9ef30b85Rafael Espindola return Vector.end(); 553b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola } 563b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola 573b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola const_iterator end() const { 583b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola return Vector.end(); 593b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola } 603b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola 61c312f098999d4640cf91934632ccecfc9ef30b85Rafael Espindola bool empty() const { 62c312f098999d4640cf91934632ccecfc9ef30b85Rafael Espindola return Vector.empty(); 633b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola } 643b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola 65888fae7b49f5d39f2371edb78566476396e30c75Douglas Gregor std::pair<KeyT, ValueT> &front() { return Vector.front(); } 66888fae7b49f5d39f2371edb78566476396e30c75Douglas Gregor const std::pair<KeyT, ValueT> &front() const { return Vector.front(); } 67888fae7b49f5d39f2371edb78566476396e30c75Douglas Gregor std::pair<KeyT, ValueT> &back() { return Vector.back(); } 68888fae7b49f5d39f2371edb78566476396e30c75Douglas Gregor const std::pair<KeyT, ValueT> &back() const { return Vector.back(); } 69888fae7b49f5d39f2371edb78566476396e30c75Douglas Gregor 70289c39965b1b799a22534d759fdf0a26302430d7Douglas Gregor void clear() { 71289c39965b1b799a22534d759fdf0a26302430d7Douglas Gregor Map.clear(); 72289c39965b1b799a22534d759fdf0a26302430d7Douglas Gregor Vector.clear(); 73289c39965b1b799a22534d759fdf0a26302430d7Douglas Gregor } 74289c39965b1b799a22534d759fdf0a26302430d7Douglas Gregor 753b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola ValueT &operator[](const KeyT &Key) { 763b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola std::pair<KeyT, unsigned> Pair = std::make_pair(Key, 0); 773b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair); 783b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola unsigned &I = Result.first->second; 793b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola if (Result.second) { 80c312f098999d4640cf91934632ccecfc9ef30b85Rafael Espindola Vector.push_back(std::make_pair(Key, ValueT())); 813b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola I = Vector.size() - 1; 823b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola } 83c312f098999d4640cf91934632ccecfc9ef30b85Rafael Espindola return Vector[I].second; 843b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola } 858161d81239f1d125cb1aeaf0be6916c36d4cdf2fDouglas Gregor 86fc8657be3470e5b3b63705c9252251acba3c1606Benjamin Kramer ValueT lookup(const KeyT &Key) const { 87fc8657be3470e5b3b63705c9252251acba3c1606Benjamin Kramer typename MapType::const_iterator Pos = Map.find(Key); 88fc8657be3470e5b3b63705c9252251acba3c1606Benjamin Kramer return Pos == Map.end()? ValueT() : Vector[Pos->second].second; 89fc8657be3470e5b3b63705c9252251acba3c1606Benjamin Kramer } 90fc8657be3470e5b3b63705c9252251acba3c1606Benjamin Kramer 916bbf4ff9c545c881422da37494b1ccb9c18d9c6aNick Lewycky std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { 926bbf4ff9c545c881422da37494b1ccb9c18d9c6aNick Lewycky std::pair<KeyT, unsigned> Pair = std::make_pair(KV.first, 0); 936bbf4ff9c545c881422da37494b1ccb9c18d9c6aNick Lewycky std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair); 946bbf4ff9c545c881422da37494b1ccb9c18d9c6aNick Lewycky unsigned &I = Result.first->second; 956bbf4ff9c545c881422da37494b1ccb9c18d9c6aNick Lewycky if (Result.second) { 966bbf4ff9c545c881422da37494b1ccb9c18d9c6aNick Lewycky Vector.push_back(std::make_pair(KV.first, KV.second)); 976bbf4ff9c545c881422da37494b1ccb9c18d9c6aNick Lewycky I = Vector.size() - 1; 9836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return std::make_pair(std::prev(end()), true); 996bbf4ff9c545c881422da37494b1ccb9c18d9c6aNick Lewycky } 1006bbf4ff9c545c881422da37494b1ccb9c18d9c6aNick Lewycky return std::make_pair(begin() + I, false); 1016bbf4ff9c545c881422da37494b1ccb9c18d9c6aNick Lewycky } 1026bbf4ff9c545c881422da37494b1ccb9c18d9c6aNick Lewycky 103cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines size_type count(const KeyT &Key) const { 1048161d81239f1d125cb1aeaf0be6916c36d4cdf2fDouglas Gregor typename MapType::const_iterator Pos = Map.find(Key); 1058161d81239f1d125cb1aeaf0be6916c36d4cdf2fDouglas Gregor return Pos == Map.end()? 0 : 1; 1068161d81239f1d125cb1aeaf0be6916c36d4cdf2fDouglas Gregor } 107009cf9e9a3a386f89db2686a105736481aed10caSergei Larin 108009cf9e9a3a386f89db2686a105736481aed10caSergei Larin iterator find(const KeyT &Key) { 109009cf9e9a3a386f89db2686a105736481aed10caSergei Larin typename MapType::const_iterator Pos = Map.find(Key); 110009cf9e9a3a386f89db2686a105736481aed10caSergei Larin return Pos == Map.end()? Vector.end() : 111009cf9e9a3a386f89db2686a105736481aed10caSergei Larin (Vector.begin() + Pos->second); 112009cf9e9a3a386f89db2686a105736481aed10caSergei Larin } 113009cf9e9a3a386f89db2686a105736481aed10caSergei Larin 114009cf9e9a3a386f89db2686a105736481aed10caSergei Larin const_iterator find(const KeyT &Key) const { 115009cf9e9a3a386f89db2686a105736481aed10caSergei Larin typename MapType::const_iterator Pos = Map.find(Key); 116009cf9e9a3a386f89db2686a105736481aed10caSergei Larin return Pos == Map.end()? Vector.end() : 117009cf9e9a3a386f89db2686a105736481aed10caSergei Larin (Vector.begin() + Pos->second); 118009cf9e9a3a386f89db2686a105736481aed10caSergei Larin } 119888fae7b49f5d39f2371edb78566476396e30c75Douglas Gregor 1201f1713ff7a53c9c491c59886984f6a0534ce3630Douglas Gregor /// \brief Remove the last element from the vector. 1211f1713ff7a53c9c491c59886984f6a0534ce3630Douglas Gregor void pop_back() { 1221f1713ff7a53c9c491c59886984f6a0534ce3630Douglas Gregor typename MapType::iterator Pos = Map.find(Vector.back().first); 123888fae7b49f5d39f2371edb78566476396e30c75Douglas Gregor Map.erase(Pos); 1241f1713ff7a53c9c491c59886984f6a0534ce3630Douglas Gregor Vector.pop_back(); 125888fae7b49f5d39f2371edb78566476396e30c75Douglas Gregor } 126cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 127cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /// \brief Remove the element given by Iterator. 128cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /// Returns an iterator to the element following the one which was removed, 129cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /// which may be end(). 130cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines typename VectorType::iterator erase(typename VectorType::iterator Iterator) { 131cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines typename MapType::iterator MapIterator = Map.find(Iterator->first); 132cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Map.erase(MapIterator); 133cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return Vector.erase(Iterator); 134cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 1353b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola}; 1363b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola 1373b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola} 1383b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola 1393b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola#endif 140