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