1193323Sed//===-- llvm/ADT/UniqueVector.h ---------------------------------*- C++ -*-===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed 10193323Sed#ifndef LLVM_ADT_UNIQUEVECTOR_H 11193323Sed#define LLVM_ADT_UNIQUEVECTOR_H 12193323Sed 13193323Sed#include <cassert> 14193323Sed#include <map> 15193323Sed#include <vector> 16193323Sed 17193323Sednamespace llvm { 18193323Sed 19193323Sed//===----------------------------------------------------------------------===// 20193323Sed/// UniqueVector - This class produces a sequential ID number (base 1) for each 21193323Sed/// unique entry that is added. T is the type of entries in the vector. This 22193323Sed/// class should have an implementation of operator== and of operator<. 23193323Sed/// Entries can be fetched using operator[] with the entry ID. 24193323Sedtemplate<class T> class UniqueVector { 25193323Sedprivate: 26193323Sed // Map - Used to handle the correspondence of entry to ID. 27193323Sed std::map<T, unsigned> Map; 28193323Sed 29193323Sed // Vector - ID ordered vector of entries. Entries can be indexed by ID - 1. 30193323Sed // 31193323Sed std::vector<T> Vector; 32193323Sed 33193323Sedpublic: 34193323Sed /// insert - Append entry to the vector if it doesn't already exist. Returns 35193323Sed /// the entry's index + 1 to be used as a unique ID. 36193323Sed unsigned insert(const T &Entry) { 37193323Sed // Check if the entry is already in the map. 38193323Sed unsigned &Val = Map[Entry]; 39193323Sed 40193323Sed // See if entry exists, if so return prior ID. 41193323Sed if (Val) return Val; 42193323Sed 43193323Sed // Compute ID for entry. 44193323Sed Val = static_cast<unsigned>(Vector.size()) + 1; 45193323Sed 46193323Sed // Insert in vector. 47193323Sed Vector.push_back(Entry); 48193323Sed return Val; 49193323Sed } 50193323Sed 51193323Sed /// idFor - return the ID for an existing entry. Returns 0 if the entry is 52193323Sed /// not found. 53193323Sed unsigned idFor(const T &Entry) const { 54193323Sed // Search for entry in the map. 55193323Sed typename std::map<T, unsigned>::const_iterator MI = Map.find(Entry); 56193323Sed 57193323Sed // See if entry exists, if so return ID. 58193323Sed if (MI != Map.end()) return MI->second; 59193323Sed 60193323Sed // No luck. 61193323Sed return 0; 62193323Sed } 63193323Sed 64193323Sed /// operator[] - Returns a reference to the entry with the specified ID. 65193323Sed /// 66193323Sed const T &operator[](unsigned ID) const { 67193323Sed assert(ID-1 < size() && "ID is 0 or out of range!"); 68193323Sed return Vector[ID - 1]; 69193323Sed } 70193323Sed 71193323Sed /// size - Returns the number of entries in the vector. 72193323Sed /// 73193323Sed size_t size() const { return Vector.size(); } 74193323Sed 75193323Sed /// empty - Returns true if the vector is empty. 76193323Sed /// 77193323Sed bool empty() const { return Vector.empty(); } 78193323Sed 79193323Sed /// reset - Clears all the entries. 80193323Sed /// 81193323Sed void reset() { 82193323Sed Map.clear(); 83193323Sed Vector.resize(0, 0); 84193323Sed } 85193323Sed}; 86193323Sed 87193323Sed} // End of namespace llvm 88193323Sed 89193323Sed#endif // LLVM_ADT_UNIQUEVECTOR_H 90