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.
5 #ifndef TOOLS_GN_UNIQUE_VECTOR_H_
6 #define TOOLS_GN_UNIQUE_VECTOR_H_
10 #include "base/containers/hash_tables.h"
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
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.
23 // It also caches the hash value which allows us to query and then insert
24 // without recomputing the hash.
31 index_(static_cast<size_t>(-1)),
35 // Initialize with a pointer to a value.
36 UniquifyRef(const T* v)
39 index_(static_cast<size_t>(-1)) {
43 // Initialize with an array + index.
44 UniquifyRef(const std::vector<T>* v, size_t i)
51 // Initialize with an array + index and a known hash value to prevent
53 UniquifyRef(const std::vector<T>* v, size_t i, size_t hash_value)
57 hash_val_(hash_value) {
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_; }
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());
76 // When non-null, points to the object.
79 // When value is null these are used.
80 const std::vector<T>* vect_;
86 template<typename T> inline bool operator==(const UniquifyRef<T>& a,
87 const UniquifyRef<T>& b) {
88 return a.value() == b.value();
91 template<typename T> inline bool operator<(const UniquifyRef<T>& a,
92 const UniquifyRef<T>& b) {
93 return a.value() < b.value();
96 } // namespace internal
98 namespace BASE_HASH_NAMESPACE {
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 {
106 #elif defined(COMPILER_MSVC)
108 inline size_t hash_value(const internal::UniquifyRef<T>& v) {
111 #endif // COMPILER...
113 } // namespace BASE_HASH_NAMESPACE
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
121 typedef std::vector<T> Vector;
122 typedef typename Vector::iterator iterator;
123 typedef typename Vector::const_iterator const_iterator;
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); }
131 const T& operator[](size_t index) const { return vector_[index]; }
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(); }
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) {
142 if (set_.find(ref) != set_.end())
143 return false; // Already have this one.
145 vector_.push_back(t);
146 set_.insert(Ref(&vector_, vector_.size() - 1, ref.hash_val()));
150 // Like push_back but swaps in the type to avoid a copy.
151 bool PushBackViaSwap(T* t) {
155 if (set_.find(ref) != set_.end())
156 return false; // Already have this one.
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()));
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)
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 {
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();
182 typedef internal::UniquifyRef<T> Ref;
183 typedef base::hash_set<Ref> HashSet;
189 #endif // TOOLS_GN_UNIQUE_VECTOR_H_