1 // Copyright 2014 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef TOOLS_GN_UNIQUE_VECTOR_H_ 6 #define TOOLS_GN_UNIQUE_VECTOR_H_ 7 8 #include <stddef.h> 9 10 #include <algorithm> 11 #include <unordered_set> 12 #include <vector> 13 14 namespace internal { 15 16 // This class allows us to insert things by reference into a hash table which 17 // avoids copies. The hash function of a UniquifyRef is that of the object it 18 // points to. 19 // 20 // There are two ways it can store data: (1) by (vector*, index) which is used 21 // to refer to the array in UniqueVector and make it work even when the 22 // underlying vector is reallocated; (2) by T* which is used to do lookups 23 // into the hash table of things that aren't in a vector yet. 24 // 25 // It also caches the hash value which allows us to query and then insert 26 // without recomputing the hash. 27 template <typename T> 28 class UniquifyRef { 29 public: 30 UniquifyRef() = default; 31 32 // Initialize with a pointer to a value. UniquifyRef(const T * v)33 explicit UniquifyRef(const T* v) : value_(v) { FillHashValue(); } 34 35 // Initialize with an array + index. UniquifyRef(const std::vector<T> * v,size_t i)36 UniquifyRef(const std::vector<T>* v, size_t i) : vect_(v), index_(i) { 37 FillHashValue(); 38 } 39 40 // Initialize with an array + index and a known hash value to prevent 41 // re-hashing. UniquifyRef(const std::vector<T> * v,size_t i,size_t hash_value)42 UniquifyRef(const std::vector<T>* v, size_t i, size_t hash_value) 43 : vect_(v), index_(i), hash_val_(hash_value) {} 44 value()45 const T& value() const { return value_ ? *value_ : (*vect_)[index_]; } hash_val()46 size_t hash_val() const { return hash_val_; } index()47 size_t index() const { return index_; } 48 49 private: FillHashValue()50 void FillHashValue() { 51 std::hash<T> h; 52 hash_val_ = h(value()); 53 } 54 55 // When non-null, points to the object. 56 const T* value_ = nullptr; 57 58 // When value is null these are used. 59 const std::vector<T>* vect_ = nullptr; 60 size_t index_ = static_cast<size_t>(-1); 61 62 size_t hash_val_ = 0; 63 }; 64 65 template <typename T> 66 inline bool operator==(const UniquifyRef<T>& a, const UniquifyRef<T>& b) { 67 return a.value() == b.value(); 68 } 69 70 template <typename T> 71 inline bool operator<(const UniquifyRef<T>& a, const UniquifyRef<T>& b) { 72 return a.value() < b.value(); 73 } 74 75 } // namespace internal 76 77 namespace std { 78 79 template <typename T> 80 struct hash<internal::UniquifyRef<T>> { 81 std::size_t operator()(const internal::UniquifyRef<T>& v) const { 82 return v.hash_val(); 83 } 84 }; 85 86 } // namespace std 87 88 // An ordered set optimized for GN's usage. Such sets are used to store lists 89 // of configs and libraries, and are appended to but not randomly inserted 90 // into. 91 template <typename T> 92 class UniqueVector { 93 public: 94 using Vector = std::vector<T>; 95 using iterator = typename Vector::iterator; 96 using const_iterator = typename Vector::const_iterator; 97 98 const Vector& vector() const { return vector_; } 99 size_t size() const { return vector_.size(); } 100 bool empty() const { return vector_.empty(); } 101 void clear() { 102 vector_.clear(); 103 set_.clear(); 104 } 105 void reserve(size_t s) { vector_.reserve(s); } 106 107 const T& operator[](size_t index) const { return vector_[index]; } 108 109 const_iterator begin() const { return vector_.begin(); } 110 iterator begin() { return vector_.begin(); } 111 const_iterator end() const { return vector_.end(); } 112 iterator end() { return vector_.end(); } 113 114 // Returns true if the item was appended, false if it already existed (and 115 // thus the vector was not modified). 116 bool push_back(const T& t) { 117 Ref ref(&t); 118 if (set_.find(ref) != set_.end()) 119 return false; // Already have this one. 120 121 vector_.push_back(t); 122 set_.insert(Ref(&vector_, vector_.size() - 1, ref.hash_val())); 123 return true; 124 } 125 126 bool push_back(T&& t) { 127 Ref ref(&t); 128 if (set_.find(ref) != set_.end()) 129 return false; // Already have this one. 130 131 auto ref_hash_val = ref.hash_val(); // Save across moving t. 132 133 vector_.push_back(std::move(t)); // Invalidates |ref|. 134 set_.insert(Ref(&vector_, vector_.size() - 1, ref_hash_val)); 135 return true; 136 } 137 138 // Appends a range of items from an iterator. 139 template <typename iter> 140 void Append(const iter& begin, const iter& end) { 141 for (iter i = begin; i != end; ++i) 142 push_back(*i); 143 } 144 145 // Returns the index of the item matching the given value in the list, or 146 // (size_t)(-1) if it's not found. 147 size_t IndexOf(const T& t) const { 148 Ref ref(&t); 149 typename HashSet::const_iterator found = set_.find(ref); 150 if (found == set_.end()) 151 return static_cast<size_t>(-1); 152 return found->index(); 153 } 154 155 private: 156 using Ref = internal::UniquifyRef<T>; 157 using HashSet = std::unordered_set<Ref>; 158 159 HashSet set_; 160 Vector vector_; 161 }; 162 163 #endif // TOOLS_GN_UNIQUE_VECTOR_H_ 164