Home | History | Annotate | Download | only in ADT
      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 <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 private:
     26   // Map - Used to handle the correspondence of entry to ID.
     27   std::map<T, unsigned> Map;
     28 
     29   // Vector - ID ordered vector of entries. Entries can be indexed by ID - 1.
     30   //
     31   std::vector<T> Vector;
     32 
     33 public:
     34   /// insert - Append entry to the vector if it doesn't already exist.  Returns
     35   /// the entry's index + 1 to be used as a unique ID.
     36   unsigned insert(const T &Entry) {
     37     // Check if the entry is already in the map.
     38     unsigned &Val = Map[Entry];
     39 
     40     // See if entry exists, if so return prior ID.
     41     if (Val) return Val;
     42 
     43     // Compute ID for entry.
     44     Val = static_cast<unsigned>(Vector.size()) + 1;
     45 
     46     // Insert in vector.
     47     Vector.push_back(Entry);
     48     return Val;
     49   }
     50 
     51   /// idFor - return the ID for an existing entry.  Returns 0 if the entry is
     52   /// not found.
     53   unsigned idFor(const T &Entry) const {
     54     // Search for entry in the map.
     55     typename std::map<T, unsigned>::const_iterator MI = Map.find(Entry);
     56 
     57     // See if entry exists, if so return ID.
     58     if (MI != Map.end()) return MI->second;
     59 
     60     // No luck.
     61     return 0;
     62   }
     63 
     64   /// operator[] - Returns a reference to the entry with the specified ID.
     65   ///
     66   const T &operator[](unsigned ID) const {
     67     assert(ID-1 < size() && "ID is 0 or out of range!");
     68     return Vector[ID - 1];
     69   }
     70 
     71   /// size - Returns the number of entries in the vector.
     72   ///
     73   size_t size() const { return Vector.size(); }
     74 
     75   /// empty - Returns true if the vector is empty.
     76   ///
     77   bool empty() const { return Vector.empty(); }
     78 
     79   /// reset - Clears all the entries.
     80   ///
     81   void reset() {
     82     Map.clear();
     83     Vector.resize(0, 0);
     84   }
     85 };
     86 
     87 } // End of namespace llvm
     88 
     89 #endif // LLVM_ADT_UNIQUEVECTOR_H
     90