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.
insert(const T & Entry)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.
idFor(const T & Entry)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.
begin()75   iterator begin() { return Vector.begin(); }
76 
77   /// Return an iterator to the start of the vector.
begin()78   const_iterator begin() const { return Vector.begin(); }
79 
80   /// Return an iterator to the end of the vector.
end()81   iterator end() { return Vector.end(); }
82 
83   /// Return an iterator to the end of the vector.
end()84   const_iterator end() const { return Vector.end(); }
85 
86   /// size - Returns the number of entries in the vector.
size()87   size_t size() const { return Vector.size(); }
88 
89   /// empty - Returns true if the vector is empty.
empty()90   bool empty() const { return Vector.empty(); }
91 
92   /// reset - Clears all the entries.
reset()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