include/llvm/ADT/UniqueVector.h

   1 //===-- llvm/ADT/UniqueVector.h ---------------------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by James M. Laskey and is distributed under
   6 // the University of Illinois Open Source 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 = 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