Line data    Source code

       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 <cstddef>
      15             : #include <map>
      16             : #include <vector>
      17             : 
      18             : namespace llvm {
      19             : 
      20             : //===----------------------------------------------------------------------===//
      21             : /// UniqueVector - This class produces a sequential ID number (base 1) for each
      22             : /// unique entry that is added.  T is the type of entries in the vector. This
      23             : /// class should have an implementation of operator== and of operator<.
      24             : /// Entries can be fetched using operator[] with the entry ID.
      25        9672 : template<class T> class UniqueVector {
      26             : public:
      27             :   using VectorType = typename std::vector<T>;
      28             :   using iterator = typename VectorType::iterator;
      29             :   using const_iterator = typename VectorType::const_iterator;
      30             : 
      31             : private:
      32             :   // Map - Used to handle the correspondence of entry to ID.
      33             :   std::map<T, unsigned> Map;
      34             : 
      35             :   // Vector - ID ordered vector of entries. Entries can be indexed by ID - 1.
      36             :   VectorType Vector;
      37             : 
      38             : public:
      39             :   /// insert - Append entry to the vector if it doesn't already exist.  Returns
      40             :   /// the entry's index + 1 to be used as a unique ID.
      41     1801670 :   unsigned insert(const T &Entry) {
      42             :     // Check if the entry is already in the map.
      43     1801670 :     unsigned &Val = Map[Entry];
      44             : 
      45             :     // See if entry exists, if so return prior ID.
      46     1801670 :     if (Val) return Val;
      47             : 
      48             :     // Compute ID for entry.
      49     1562482 :     Val = static_cast<unsigned>(Vector.size()) + 1;
      50             : 
      51             :     // Insert in vector.
      52     1562482 :     Vector.push_back(Entry);
      53     1562482 :     return Val;
      54             :   }
      55             : 
      56             :   /// idFor - return the ID for an existing entry.  Returns 0 if the entry is
      57             :   /// not found.
      58             :   unsigned idFor(const T &Entry) const {
      59             :     // Search for entry in the map.
      60             :     typename std::map<T, unsigned>::const_iterator MI = Map.find(Entry);
      61             : 
      62             :     // See if entry exists, if so return ID.
      63        2675 :     if (MI != Map.end()) return MI->second;
      64             : 
      65             :     // No luck.
      66             :     return 0;
      67             :   }
      68             : 
      69             :   /// operator[] - Returns a reference to the entry with the specified ID.
      70             :   const T &operator[](unsigned ID) const {
      71             :     assert(ID-1 < size() && "ID is 0 or out of range!");
      72       43464 :     return Vector[ID - 1];
      73             :   }
      74             : 
      75             :   /// Return an iterator to the start of the vector.
      76             :   iterator begin() { return Vector.begin(); }
      77             : 
      78             :   /// Return an iterator to the start of the vector.
      79        4709 :   const_iterator begin() const { return Vector.begin(); }
      80             : 
      81             :   /// Return an iterator to the end of the vector.
      82             :   iterator end() { return Vector.end(); }
      83             : 
      84             :   /// Return an iterator to the end of the vector.
      85        4709 :   const_iterator end() const { return Vector.end(); }
      86             : 
      87             :   /// size - Returns the number of entries in the vector.
      88             :   size_t size() const { return Vector.size(); }
      89             : 
      90             :   /// empty - Returns true if the vector is empty.
      91             :   bool empty() const { return Vector.empty(); }
      92             : 
      93             :   /// reset - Clears all the entries.
      94             :   void reset() {
      95             :     Map.clear();
      96             :     Vector.resize(0, 0);
      97             :   }
      98             : };
      99             : 
     100             : } // end namespace llvm
     101             : 
     102             : #endif // LLVM_ADT_UNIQUEVECTOR_H