1 //===- llvm/ADT/UniqueVector.h ----------------------------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #ifndef LLVM_ADT_UNIQUEVECTOR_H 10 #define LLVM_ADT_UNIQUEVECTOR_H 11 12 #include <cassert> 13 #include <cstddef> 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 using VectorType = typename std::vector<T>; 27 using iterator = typename VectorType::iterator; 28 using const_iterator = typename VectorType::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 VectorType Vector; 36 37 public: 38 /// insert - Append entry to the vector if it doesn't already exist. Returns 39 /// the entry's index + 1 to be used as a unique ID. insert(const T & Entry)40 unsigned insert(const T &Entry) { 41 // Check if the entry is already in the map. 42 unsigned &Val = Map[Entry]; 43 44 // See if entry exists, if so return prior ID. 45 if (Val) return Val; 46 47 // Compute ID for entry. 48 Val = static_cast<unsigned>(Vector.size()) + 1; 49 50 // Insert in vector. 51 Vector.push_back(Entry); 52 return Val; 53 } 54 55 /// idFor - return the ID for an existing entry. Returns 0 if the entry is 56 /// not found. idFor(const T & Entry)57 unsigned idFor(const T &Entry) const { 58 // Search for entry in the map. 59 typename std::map<T, unsigned>::const_iterator MI = Map.find(Entry); 60 61 // See if entry exists, if so return ID. 62 if (MI != Map.end()) return MI->second; 63 64 // No luck. 65 return 0; 66 } 67 68 /// operator[] - Returns a reference to the entry with the specified ID. 69 const T &operator[](unsigned ID) const { 70 assert(ID-1 < size() && "ID is 0 or out of range!"); 71 return Vector[ID - 1]; 72 } 73 74 /// Return an iterator to the start of the vector. begin()75 iterator begin() { return Vector.begin(); } 76 77 /// Return an iterator to the start of the vector. begin()78 const_iterator begin() const { return Vector.begin(); } 79 80 /// Return an iterator to the end of the vector. end()81 iterator end() { return Vector.end(); } 82 83 /// Return an iterator to the end of the vector. end()84 const_iterator end() const { return Vector.end(); } 85 86 /// size - Returns the number of entries in the vector. size()87 size_t size() const { return Vector.size(); } 88 89 /// empty - Returns true if the vector is empty. empty()90 bool empty() const { return Vector.empty(); } 91 92 /// reset - Clears all the entries. reset()93 void reset() { 94 Map.clear(); 95 Vector.resize(0, 0); 96 } 97 }; 98 99 } // end namespace llvm 100 101 #endif // LLVM_ADT_UNIQUEVECTOR_H 102