include/llvm/ADT/UniqueVector.h

   1
   2 //===-- llvm/ADT/UniqueVector.h ---------------------------------*- C++ -*-===//
   3 //
   4 //                     The LLVM Compiler Infrastructure
   5 //
   6 // This file was developed by James M. Laskey and is distributed under
   7 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   8 //
   9 //===----------------------------------------------------------------------===//
  10
  11 #ifndef LLVM_ADT_UNIQUEVECTOR_H
  12 #define LLVM_ADT_UNIQUEVECTOR_H
  13
  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<const 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     typename std::map<T, unsigned>::iterator MI = Map.lower_bound(Entry);
  39
  40     // See if entry exists, if so return prior ID.
  41     if (MI != Map.end() && MI->first == Entry) return MI->second;
  42
  43     // Compute ID for entry.
  44     unsigned ID = Vector.size() + 1;
  45
  46     // Insert in map.
  47     MI = Map.insert(MI, std::make_pair(Entry, ID));
  48
  49     // Insert in vector.
  50     Vector.push_back(&MI->first);
  51
  52     return ID;
  53   }
  54
  55   /// operator[] - Returns a reference to the entry with the specified ID.
  56   ///
  57   const T &operator[](unsigned ID) const { return *Vector[ID - 1]; }
  58
  59   /// size - Returns the number of entries in the vector.
  60   ///
  61   size_t size() const { return Vector.size(); }
  62
  63   /// empty - Returns true if the vector is empty.
  64   ///
  65   bool empty() const { return Vector.empty(); }
  66 };
  67
  68 } // End of namespace llvm
  69
  70 #endif // LLVM_ADT_UNIQUEVECTOR_H