1 //===-- llvm/ADT/UniqueVector.h ---------------------------------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 10 #ifndef LLVM_ADT_UNIQUEVECTOR_H 11 #define LLVM_ADT_UNIQUEVECTOR_H 12 13 #include <cassert> 14 #include <map> 15 #include <vector> 16 17 namespace llvm { 18 19 //===----------------------------------------------------------------------===// 20 /// UniqueVector - This class produces a sequential ID number (base 1) for each 21 /// unique entry that is added. T is the type of entries in the vector. This 22 /// class should have an implementation of operator== and of operator<. 23 /// Entries can be fetched using operator[] with the entry ID. 24 template<class T> class UniqueVector { 25 private: 26 // Map - Used to handle the correspondence of entry to ID. 27 std::map<T, unsigned> Map; 28 29 // Vector - ID ordered vector of entries. Entries can be indexed by ID - 1. 30 // 31 std::vector<T> Vector; 32 33 public: 34 /// insert - Append entry to the vector if it doesn't already exist. Returns 35 /// the entry's index + 1 to be used as a unique ID. 36 unsigned insert(const T &Entry) { 37 // Check if the entry is already in the map. 38 unsigned &Val = Map[Entry]; 39 40 // See if entry exists, if so return prior ID. 41 if (Val) return Val; 42 43 // Compute ID for entry. 44 Val = static_cast<unsigned>(Vector.size()) + 1; 45 46 // Insert in vector. 47 Vector.push_back(Entry); 48 return Val; 49 } 50 51 /// idFor - return the ID for an existing entry. Returns 0 if the entry is 52 /// not found. 53 unsigned idFor(const T &Entry) const { 54 // Search for entry in the map. 55 typename std::map<T, unsigned>::const_iterator MI = Map.find(Entry); 56 57 // See if entry exists, if so return ID. 58 if (MI != Map.end()) return MI->second; 59 60 // No luck. 61 return 0; 62 } 63 64 /// operator[] - Returns a reference to the entry with the specified ID. 65 /// 66 const T &operator[](unsigned ID) const { 67 assert(ID-1 < size() && "ID is 0 or out of range!"); 68 return Vector[ID - 1]; 69 } 70 71 /// size - Returns the number of entries in the vector. 72 /// 73 size_t size() const { return Vector.size(); } 74 75 /// empty - Returns true if the vector is empty. 76 /// 77 bool empty() const { return Vector.empty(); } 78 79 /// reset - Clears all the entries. 80 /// 81 void reset() { 82 Map.clear(); 83 Vector.resize(0, 0); 84 } 85 }; 86 87 } // End of namespace llvm 88 89 #endif // LLVM_ADT_UNIQUEVECTOR_H 90
