LLVM API Documentation

UniqueVector.h

Go to the documentation of this file.
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