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 public: 26 typedef typename std::vector<T> VectorType; 27 typedef typename VectorType::iterator iterator; 28 typedef typename VectorType::const_iterator const_iterator; 29 30 private: 31 // Map - Used to handle the correspondence of entry to ID. 32 std::map<T, unsigned> Map; 33 34 // Vector - ID ordered vector of entries. Entries can be indexed by ID - 1. 35 // 36 VectorType Vector; 37 38 public: 39 /// insert - Append entry to the vector if it doesn't already exist. Returns 40 /// the entry's index + 1 to be used as a unique ID. 41 unsigned insert(const T &Entry) { 42 // Check if the entry is already in the map. 43 unsigned &Val = Map[Entry]; 44 45 // See if entry exists, if so return prior ID. 46 if (Val) return Val; 47 48 // Compute ID for entry. 49 Val = static_cast<unsigned>(Vector.size()) + 1; 50 51 // Insert in vector. 52 Vector.push_back(Entry); 53 return Val; 54 } 55 56 /// idFor - return the ID for an existing entry. Returns 0 if the entry is 57 /// not found. 58 unsigned idFor(const T &Entry) const { 59 // Search for entry in the map. 60 typename std::map<T, unsigned>::const_iterator MI = Map.find(Entry); 61 62 // See if entry exists, if so return ID. 63 if (MI != Map.end()) return MI->second; 64 65 // No luck. 66 return 0; 67 } 68 69 /// operator[] - Returns a reference to the entry with the specified ID. 70 /// 71 const T &operator[](unsigned ID) const { 72 assert(ID-1 < size() && "ID is 0 or out of range!"); 73 return Vector[ID - 1]; 74 } 75 76 /// \brief Return an iterator to the start of the vector. 77 iterator begin() { return Vector.begin(); } 78 79 /// \brief Return an iterator to the start of the vector. 80 const_iterator begin() const { return Vector.begin(); } 81 82 /// \brief Return an iterator to the end of the vector. 83 iterator end() { return Vector.end(); } 84 85 /// \brief Return an iterator to the end of the vector. 86 const_iterator end() const { return Vector.end(); } 87 88 /// size - Returns the number of entries in the vector. 89 /// 90 size_t size() const { return Vector.size(); } 91 92 /// empty - Returns true if the vector is empty. 93 /// 94 bool empty() const { return Vector.empty(); } 95 96 /// reset - Clears all the entries. 97 /// 98 void reset() { 99 Map.clear(); 100 Vector.resize(0, 0); 101 } 102 }; 103 104 } // End of namespace llvm 105 106 #endif // LLVM_ADT_UNIQUEVECTOR_H 107
