Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

Rev

Blame | Last modification | View Log | Download | RSS feed

  1. //===- llvm/ADT/UniqueVector.h ----------------------------------*- C++ -*-===//
  2. //
  3. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
  4. // See https://llvm.org/LICENSE.txt for license information.
  5. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
  6. //
  7. //===----------------------------------------------------------------------===//
  8.  
  9. #ifndef LLVM_ADT_UNIQUEVECTOR_H
  10. #define LLVM_ADT_UNIQUEVECTOR_H
  11.  
  12. #include <cassert>
  13. #include <cstddef>
  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. public:
  26.   using VectorType = typename std::vector<T>;
  27.   using iterator = typename VectorType::iterator;
  28.   using const_iterator = typename VectorType::const_iterator;
  29.  
  30. private:
  31.   // Map - Used to handle the correspondence of entry to ID.
  32.   std::map<T, unsigned> Map;
  33.  
  34.   // Vector - ID ordered vector of entries. Entries can be indexed by ID - 1.
  35.   VectorType Vector;
  36.  
  37. public:
  38.   /// insert - Append entry to the vector if it doesn't already exist.  Returns
  39.   /// the entry's index + 1 to be used as a unique ID.
  40.   unsigned insert(const T &Entry) {
  41.     // Check if the entry is already in the map.
  42.     unsigned &Val = Map[Entry];
  43.  
  44.     // See if entry exists, if so return prior ID.
  45.     if (Val) return Val;
  46.  
  47.     // Compute ID for entry.
  48.     Val = static_cast<unsigned>(Vector.size()) + 1;
  49.  
  50.     // Insert in vector.
  51.     Vector.push_back(Entry);
  52.     return Val;
  53.   }
  54.  
  55.   /// idFor - return the ID for an existing entry.  Returns 0 if the entry is
  56.   /// not found.
  57.   unsigned idFor(const T &Entry) const {
  58.     // Search for entry in the map.
  59.     typename std::map<T, unsigned>::const_iterator MI = Map.find(Entry);
  60.  
  61.     // See if entry exists, if so return ID.
  62.     if (MI != Map.end()) return MI->second;
  63.  
  64.     // No luck.
  65.     return 0;
  66.   }
  67.  
  68.   /// operator[] - Returns a reference to the entry with the specified ID.
  69.   const T &operator[](unsigned ID) const {
  70.     assert(ID-1 < size() && "ID is 0 or out of range!");
  71.     return Vector[ID - 1];
  72.   }
  73.  
  74.   /// Return an iterator to the start of the vector.
  75.   iterator begin() { return Vector.begin(); }
  76.  
  77.   /// Return an iterator to the start of the vector.
  78.   const_iterator begin() const { return Vector.begin(); }
  79.  
  80.   /// Return an iterator to the end of the vector.
  81.   iterator end() { return Vector.end(); }
  82.  
  83.   /// Return an iterator to the end of the vector.
  84.   const_iterator end() const { return Vector.end(); }
  85.  
  86.   /// size - Returns the number of entries in the vector.
  87.   size_t size() const { return Vector.size(); }
  88.  
  89.   /// empty - Returns true if the vector is empty.
  90.   bool empty() const { return Vector.empty(); }
  91.  
  92.   /// reset - Clears all the entries.
  93.   void reset() {
  94.     Map.clear();
  95.     Vector.resize(0, 0);
  96.   }
  97. };
  98.  
  99. } // end namespace llvm
  100.  
  101. #endif // LLVM_ADT_UNIQUEVECTOR_H
  102.