LLVM API Documentation
00001 00002 //===-- llvm/ADT/UniqueVector.h ---------------------------------*- C++ -*-===// 00003 // 00004 // The LLVM Compiler Infrastructure 00005 // 00006 // This file was developed by James M. Laskey and is distributed under 00007 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00008 // 00009 //===----------------------------------------------------------------------===// 00010 00011 #ifndef LLVM_ADT_UNIQUEVECTOR_H 00012 #define LLVM_ADT_UNIQUEVECTOR_H 00013 00014 #include <map> 00015 #include <vector> 00016 00017 namespace llvm { 00018 00019 //===----------------------------------------------------------------------===// 00020 /// UniqueVector - This class produces a sequential ID number (base 1) for each 00021 /// unique entry that is added. T is the type of entries in the vector. This 00022 /// class should have an implementation of operator== and of operator<. 00023 /// Entries can be fetched using operator[] with the entry ID. 00024 template<class T> class UniqueVector { 00025 private: 00026 // Map - Used to handle the correspondence of entry to ID. 00027 std::map<T, unsigned> Map; 00028 00029 // Vector - ID ordered vector of entries. Entries can be indexed by ID - 1. 00030 // 00031 std::vector<const T *> Vector; 00032 00033 public: 00034 /// insert - Append entry to the vector if it doesn't already exist. Returns 00035 /// the entry's index + 1 to be used as a unique ID. 00036 unsigned insert(const T &Entry) { 00037 // Check if the entry is already in the map. 00038 typename std::map<T, unsigned>::iterator MI = Map.lower_bound(Entry); 00039 00040 // See if entry exists, if so return prior ID. 00041 if (MI != Map.end() && MI->first == Entry) return MI->second; 00042 00043 // Compute ID for entry. 00044 unsigned ID = Vector.size() + 1; 00045 00046 // Insert in map. 00047 MI = Map.insert(MI, std::make_pair(Entry, ID)); 00048 00049 // Insert in vector. 00050 Vector.push_back(&MI->first); 00051 00052 return ID; 00053 } 00054 00055 /// idFor - return the ID for an existing entry. Returns 0 if the entry is 00056 /// not found. 00057 unsigned idFor(const T &Entry) const { 00058 // Search for entry in the map. 00059 typename std::map<T, unsigned>::iterator MI = Map.find(Entry); 00060 00061 // See if entry exists, if so return ID. 00062 if (MI != Map.end()) return MI->second; 00063 00064 // No luck. 00065 return 0; 00066 } 00067 00068 /// operator[] - Returns a reference to the entry with the specified ID. 00069 /// 00070 const T &operator[](unsigned ID) const { return *Vector[ID - 1]; } 00071 00072 /// size - Returns the number of entries in the vector. 00073 /// 00074 size_t size() const { return Vector.size(); } 00075 00076 /// empty - Returns true if the vector is empty. 00077 /// 00078 bool empty() const { return Vector.empty(); } 00079 00080 /// reset - Clears all the entries. 00081 /// 00082 void reset() { 00083 Map.clear(); 00084 Vector.resize(0, 0); 00085 } 00086 }; 00087 00088 } // End of namespace llvm 00089 00090 #endif // LLVM_ADT_UNIQUEVECTOR_H