Details | Last modification | View Log | RSS feed
| Rev | Author | Line No. | Line |
|---|---|---|---|
| 14 | pmbaty | 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 |