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 using VectorType = typename std::vector<T>; 28 using iterator = typename VectorType::iterator; 29 using const_iterator = typename VectorType::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 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 const T &operator[](unsigned ID) const { 71 assert(ID-1 < size() && "ID is 0 or out of range!"); 72 return Vector[ID - 1]; 73 } 74 75 /// \brief Return an iterator to the start of the vector. 76 iterator begin() { return Vector.begin(); } 77 78 /// \brief Return an iterator to the start of the vector. 79 const_iterator begin() const { return Vector.begin(); } 80 81 /// \brief Return an iterator to the end of the vector. 82 iterator end() { return Vector.end(); } 83 84 /// \brief Return an iterator to the end of the vector. 85 const_iterator end() const { return Vector.end(); } 86 87 /// size - Returns the number of entries in the vector. 88 size_t size() const { return Vector.size(); } 89 90 /// empty - Returns true if the vector is empty. 91 bool empty() const { return Vector.empty(); } 92 93 /// reset - Clears all the entries. 94 void reset() { 95 Map.clear(); 96 Vector.resize(0, 0); 97 } 98 }; 99 100 } // end namespace llvm 101 102 #endif // LLVM_ADT_UNIQUEVECTOR_H 103
