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 <algorithm> 9 10 #include "base/containers/hash_tables.h" 11 12 namespace internal { 13 14 // This lass allows us to insert things by reference into a hash table which 15 // avoids copies. The hash function of a UniquifyRef is that of the object it 16 // points to. 17 // 18 // There are two ways it can store data: (1) by (vector*, index) which is used 19 // to refer to the array in UniqueVector and make it work even when the 20 // underlying vector is reallocated; (2) by T* which is used to do lookups 21 // into the hash table of things that aren't in a vector yet. 22 // 23 // It also caches the hash value which allows us to query and then insert 24 // without recomputing the hash. 25 template<typename T> 26 class UniquifyRef { 27 public: 28 UniquifyRef() 29 : value_(NULL), 30 vect_(NULL), 31 index_(static_cast<size_t>(-1)), 32 hash_val_(0) { 33 } 34 35 // Initialize with a pointer to a value. 36 UniquifyRef(const T* v) 37 : value_(v), 38 vect_(NULL), 39 index_(static_cast<size_t>(-1)) { 40 FillHashValue(); 41 } 42 43 // Initialize with an array + index. 44 UniquifyRef(const std::vector<T>* v, size_t i) 45 : value_(NULL), 46 vect_(v), 47 index_(i) { 48 FillHashValue(); 49 } 50 51 // Initialize with an array + index and a known hash value to prevent 52 // re-hashing. 53 UniquifyRef(const std::vector<T>* v, size_t i, size_t hash_value) 54 : value_(NULL), 55 vect_(v), 56 index_(i), 57 hash_val_(hash_value) { 58 } 59 60 const T& value() const { return value_ ? *value_ : (*vect_)[index_]; } 61 size_t hash_val() const { return hash_val_; } 62 size_t index() const { return index_; } 63 64 private: 65 void FillHashValue() { 66 #if defined(COMPILER_GCC) 67 BASE_HASH_NAMESPACE::hash<T> h; 68 hash_val_ = h(value()); 69 #elif defined(COMPILER_MSVC) 70 hash_val_ = BASE_HASH_NAMESPACE::hash_value(value()); 71 #else 72 #error write me 73 #endif // COMPILER... 74 } 75 76 // When non-null, points to the object. 77 const T* value_; 78 79 // When value is null these are used. 80 const std::vector<T>* vect_; 81 size_t index_; 82 83 size_t hash_val_; 84 }; 85 86 template<typename T> inline bool operator==(const UniquifyRef<T>& a, 87 const UniquifyRef<T>& b) { 88 return a.value() == b.value(); 89 } 90 91 template<typename T> inline bool operator<(const UniquifyRef<T>& a, 92 const UniquifyRef<T>& b) { 93 return a.value() < b.value(); 94 } 95 96 } // namespace internal 97 98 namespace BASE_HASH_NAMESPACE { 99 100 #if defined(COMPILER_GCC) 101 template<typename T> struct hash< internal::UniquifyRef<T> > { 102 std::size_t operator()(const internal::UniquifyRef<T>& v) const { 103 return v.hash_val(); 104 } 105 }; 106 #elif defined(COMPILER_MSVC) 107 template<typename T> 108 inline size_t hash_value(const internal::UniquifyRef<T>& v) { 109 return v.hash_val(); 110 } 111 #endif // COMPILER... 112 113 } // namespace BASE_HASH_NAMESPACE 114 115 // An ordered set optimized for GN's usage. Such sets are used to store lists 116 // of configs and libraries, and are appended to but not randomly inserted 117 // into. 118 template<typename T> 119 class UniqueVector { 120 public: 121 typedef std::vector<T> Vector; 122 typedef typename Vector::iterator iterator; 123 typedef typename Vector::const_iterator const_iterator; 124 125 const Vector& vector() const { return vector_; } 126 size_t size() const { return vector_.size(); } 127 bool empty() const { return vector_.empty(); } 128 void clear() { vector_.clear(); set_.clear(); } 129 void reserve(size_t s) { vector_.reserve(s); } 130 131 const T& operator[](size_t index) const { return vector_[index]; } 132 133 const_iterator begin() const { return vector_.begin(); } 134 iterator begin() { return vector_.begin(); } 135 const_iterator end() const { return vector_.end(); } 136 iterator end() { return vector_.end(); } 137 138 // Returns true if the item was appended, false if it already existed (and 139 // thus the vector was not modified). 140 bool push_back(const T& t) { 141 Ref ref(&t); 142 if (set_.find(ref) != set_.end()) 143 return false; // Already have this one. 144 145 vector_.push_back(t); 146 set_.insert(Ref(&vector_, vector_.size() - 1, ref.hash_val())); 147 return true; 148 } 149 150 // Like push_back but swaps in the type to avoid a copy. 151 bool PushBackViaSwap(T* t) { 152 using std::swap; 153 154 Ref ref(t); 155 if (set_.find(ref) != set_.end()) 156 return false; // Already have this one. 157 158 size_t new_index = vector_.size(); 159 vector_.resize(new_index + 1); 160 swap(vector_[new_index], *t); 161 set_.insert(Ref(&vector_, vector_.size() - 1, ref.hash_val())); 162 return true; 163 } 164 165 // Appends a range of items from an iterator. 166 template<typename iter> void Append(const iter& begin, const iter& end) { 167 for (iter i = begin; i != end; ++i) 168 push_back(*i); 169 } 170 171 // Returns the index of the item matching the given value in the list, or 172 // (size_t)(-1) if it's not found. 173 size_t IndexOf(const T& t) const { 174 Ref ref(&t); 175 typename HashSet::const_iterator found = set_.find(ref); 176 if (found == set_.end()) 177 return static_cast<size_t>(-1); 178 return found->index(); 179 } 180 181 private: 182 typedef internal::UniquifyRef<T> Ref; 183 typedef base::hash_set<Ref> HashSet; 184 185 HashSet set_; 186 Vector vector_; 187 }; 188 189 #endif // TOOLS_GN_UNIQUE_VECTOR_H_ 190
