1894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===-- llvm/ADT/UniqueVector.h ---------------------------------*- C++ -*-===// 2894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 3894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// The LLVM Compiler Infrastructure 4894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 5894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file is distributed under the University of Illinois Open Source 6894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// License. See LICENSE.TXT for details. 7894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 8894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 9894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 10894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#ifndef LLVM_ADT_UNIQUEVECTOR_H 11894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#define LLVM_ADT_UNIQUEVECTOR_H 12894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 13894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include <cassert> 14894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include <map> 15894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include <vector> 16894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 17894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumannamespace llvm { 18894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 19894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 20894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// UniqueVector - This class produces a sequential ID number (base 1) for each 21894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// unique entry that is added. T is the type of entries in the vector. This 22894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// class should have an implementation of operator== and of operator<. 23894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// Entries can be fetched using operator[] with the entry ID. 24894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate<class T> class UniqueVector { 25894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanprivate: 26894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Map - Used to handle the correspondence of entry to ID. 27894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::map<T, unsigned> Map; 28894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 29894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Vector - ID ordered vector of entries. Entries can be indexed by ID - 1. 30894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // 31894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::vector<T> Vector; 32894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 33894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanpublic: 34894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// insert - Append entry to the vector if it doesn't already exist. Returns 35894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// the entry's index + 1 to be used as a unique ID. 36894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned insert(const T &Entry) { 37894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Check if the entry is already in the map. 38894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned &Val = Map[Entry]; 39894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 40894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // See if entry exists, if so return prior ID. 41894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Val) return Val; 42894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 43894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Compute ID for entry. 44894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Val = static_cast<unsigned>(Vector.size()) + 1; 45894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 46894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Insert in vector. 47894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Vector.push_back(Entry); 48894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Val; 49894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 50894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 51894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// idFor - return the ID for an existing entry. Returns 0 if the entry is 52894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// not found. 53894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned idFor(const T &Entry) const { 54894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Search for entry in the map. 55894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typename std::map<T, unsigned>::const_iterator MI = Map.find(Entry); 56894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 57894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // See if entry exists, if so return ID. 58894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MI != Map.end()) return MI->second; 59894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 60894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // No luck. 61894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return 0; 62894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 63894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 64894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// operator[] - Returns a reference to the entry with the specified ID. 65894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 66894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const T &operator[](unsigned ID) const { 67894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(ID-1 < size() && "ID is 0 or out of range!"); 68894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Vector[ID - 1]; 69894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 70894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 71894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// size - Returns the number of entries in the vector. 72894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 73894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman size_t size() const { return Vector.size(); } 74894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 75894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// empty - Returns true if the vector is empty. 76894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 77894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool empty() const { return Vector.empty(); } 78894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 79894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// reset - Clears all the entries. 80894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 81894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void reset() { 82894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Map.clear(); 83894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Vector.resize(0, 0); 84894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 85894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman}; 86894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 87894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} // End of namespace llvm 88894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 89894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#endif // LLVM_ADT_UNIQUEVECTOR_H 90