MapVector.h revision 289c39965b1b799a22534d759fdf0a26302430d7
13b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola//===- llvm/ADT/MapVector.h - Map with 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/ArrayRef.h" 213b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola#include "llvm/ADT/DenseMap.h" 223b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola#include <vector> 233b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola 243b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindolanamespace llvm { 253b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola 263b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola/// This class implements a map that also provides access to all stored values 273b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola/// in a deterministic order. The values are kept in a std::vector and the 283b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola/// mapping is done with DenseMap from Keys to indexes in that vector. 29289c39965b1b799a22534d759fdf0a26302430d7Douglas Gregortemplate<typename KeyT, typename ValueT, 30289c39965b1b799a22534d759fdf0a26302430d7Douglas Gregor typename MapType = llvm::DenseMap<KeyT, unsigned>, 31289c39965b1b799a22534d759fdf0a26302430d7Douglas Gregor typename VectorType = std::vector<std::pair<KeyT, ValueT> >> 323b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindolaclass MapVector { 333b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola typedef typename VectorType::size_type SizeType; 343b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola 353b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola MapType Map; 363b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola VectorType Vector; 373b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola 383b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindolapublic: 39c312f098999d4640cf91934632ccecfc9ef30b85Rafael Espindola typedef typename VectorType::iterator iterator; 40c312f098999d4640cf91934632ccecfc9ef30b85Rafael Espindola typedef typename VectorType::const_iterator const_iterator; 413b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola 423b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola SizeType size() const { 433b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola return Vector.size(); 443b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola } 453b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola 463b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola iterator begin() { 47c312f098999d4640cf91934632ccecfc9ef30b85Rafael Espindola return Vector.begin(); 483b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola } 493b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola 503b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola const_iterator begin() const { 51c312f098999d4640cf91934632ccecfc9ef30b85Rafael Espindola return Vector.begin(); 523b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola } 533b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola 543b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola iterator end() { 55c312f098999d4640cf91934632ccecfc9ef30b85Rafael Espindola return Vector.end(); 563b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola } 573b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola 583b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola const_iterator end() const { 593b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola return Vector.end(); 603b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola } 613b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola 62c312f098999d4640cf91934632ccecfc9ef30b85Rafael Espindola bool empty() const { 63c312f098999d4640cf91934632ccecfc9ef30b85Rafael Espindola return Vector.empty(); 643b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola } 653b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola 66289c39965b1b799a22534d759fdf0a26302430d7Douglas Gregor void clear() { 67289c39965b1b799a22534d759fdf0a26302430d7Douglas Gregor Map.clear(); 68289c39965b1b799a22534d759fdf0a26302430d7Douglas Gregor Vector.clear(); 69289c39965b1b799a22534d759fdf0a26302430d7Douglas Gregor } 70289c39965b1b799a22534d759fdf0a26302430d7Douglas Gregor 713b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola ValueT &operator[](const KeyT &Key) { 723b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola std::pair<KeyT, unsigned> Pair = std::make_pair(Key, 0); 733b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair); 743b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola unsigned &I = Result.first->second; 753b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola if (Result.second) { 76c312f098999d4640cf91934632ccecfc9ef30b85Rafael Espindola Vector.push_back(std::make_pair(Key, ValueT())); 773b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola I = Vector.size() - 1; 783b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola } 79c312f098999d4640cf91934632ccecfc9ef30b85Rafael Espindola return Vector[I].second; 803b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola } 813b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola}; 823b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola 833b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola} 843b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola 853b62b01f9a6fbecbc8aa22750d797459f8ae6417Rafael Espindola#endif 86