OLD | NEW |
---|---|
(Empty) | |
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 struct allows us to insert things by reference into a hash table. This | |
viettrungluu
2014/08/06 19:43:52
Which struct are you talking about?
(Actually, th
| |
15 // is used to avoid copying strings just to uniquify them. The hash function | |
16 // of a UniquifyRef is that of the object it points to. | |
17 // | |
18 // It also caches the hash value which allows us to query and then insert | |
19 // without recomputing the hash. | |
20 template<typename T> | |
21 class UniquifyRef { | |
22 public: | |
23 UniquifyRef() | |
24 : value_(NULL), | |
25 vect_(NULL), | |
26 index_(static_cast<size_t>(-1)), | |
27 hash_val_(0) { | |
28 } | |
29 | |
30 // Initialize with a pointer to a value. | |
31 UniquifyRef(const T* v) | |
32 : value_(v), | |
33 vect_(NULL), | |
34 index_(static_cast<size_t>(-1)) { | |
35 FillHashValue(); | |
36 } | |
37 | |
38 // Initialize with an array + index. | |
39 UniquifyRef(const std::vector<T>* v, size_t i) | |
viettrungluu
2014/08/06 19:43:52
Why would you use this instead of passing &v[i] to
brettw
2014/08/06 20:13:03
I clarified the class-level comment. The vector*+i
| |
40 : value_(NULL), | |
41 vect_(v), | |
42 index_(i) { | |
43 FillHashValue(); | |
44 } | |
45 | |
46 // Initialize with an array + index and a know hash value to prevent | |
viettrungluu
2014/08/06 19:43:52
s/know/known/ I assume.
| |
47 // re-hashing. | |
48 UniquifyRef(const std::vector<T>* v, size_t i, size_t hash_value) | |
49 : value_(NULL), | |
50 vect_(v), | |
51 index_(i), | |
52 hash_val_(hash_value) { | |
53 } | |
54 | |
55 const T& value() const { return value_ ? *value_ : (*vect_)[index_]; } | |
56 size_t hash_val() const { return hash_val_; } | |
57 size_t index() const { return index_; } | |
58 | |
59 private: | |
60 void FillHashValue() { | |
61 #if defined(COMPILER_GCC) | |
62 BASE_HASH_NAMESPACE::hash<T> h; | |
63 hash_val_ = h(value()); | |
64 #elif defined(COMPILER_MSVC) | |
65 hash_val_ = BASE_HASH_NAMESPACE::hash_value(value()); | |
66 #else | |
67 #error write me | |
68 #endif // COMPILER... | |
69 } | |
70 | |
71 // When non-null, points to the object. | |
72 const T* value_; | |
73 | |
74 // When value is null these are used. | |
75 const std::vector<T>* vect_; | |
76 size_t index_; | |
77 | |
78 size_t hash_val_; | |
79 }; | |
80 | |
81 template<typename T> inline bool operator==(const UniquifyRef<T>& a, | |
82 const UniquifyRef<T>& b) { | |
83 return a.value() == b.value(); | |
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 } // namespace internal | |
92 | |
93 namespace BASE_HASH_NAMESPACE { | |
94 | |
95 #if defined(COMPILER_GCC) | |
96 template<typename T> struct hash< internal::UniquifyRef<T> > { | |
97 std::size_t operator()(const internal::UniquifyRef<T>& v) const { | |
98 return v.hash_val(); | |
99 } | |
100 }; | |
101 #elif defined(COMPILER_MSVC) | |
102 template<typename T> | |
103 inline size_t hash_value(const internal::UniquifyRef<T>& v) { | |
104 return v.hash_val(); | |
105 } | |
106 #endif // COMPILER... | |
107 | |
108 } // namespace BASE_HASH_NAMESPACE | |
109 | |
110 // An ordered set optimized for GN's usage. Such sets are used to store lists | |
111 // of configs and libraries, and are appended to but not | |
viettrungluu
2014/08/06 19:43:52
appended to but not ... what?
| |
112 template<typename T> | |
113 class UniqueVector { | |
114 public: | |
115 typedef std::vector<T> Vector; | |
116 typedef typename Vector::iterator iterator; | |
117 typedef typename Vector::const_iterator const_iterator; | |
118 const size_t npos = static_cast<size_t>(-1); | |
119 | |
120 const Vector& vector() const { return vector_; } | |
121 size_t size() const { return vector_.size(); } | |
122 bool empty() const { return vector_.empty(); } | |
123 void clear() { vector_.clear(); set_.clear(); } | |
124 void reserve(size_t s) { vector_.reserve(s); } | |
125 | |
126 const T& operator[](size_t index) const { return vector_[index]; } | |
127 | |
128 const_iterator begin() const { return vector_.begin(); } | |
129 iterator begin() { return vector_.begin(); } | |
130 const_iterator end() const { return vector_.end(); } | |
131 iterator end() { return vector_.end(); } | |
132 | |
133 // Returns true if the item was appended, false if it already existed (and | |
134 // thus the vector was not modified). | |
135 bool push_back(const T& t) { | |
136 Ref ref(&t); | |
137 if (set_.find(ref) != set_.end()) | |
138 return false; // Already have this one. | |
139 | |
140 vector_.push_back(t); | |
141 set_.insert(Ref(&vector_, vector_.size() - 1, ref.hash_val())); | |
142 return true; | |
143 } | |
144 | |
145 // Like push_back but swaps in the type to avoid a copy. | |
146 bool PushBackViaSwap(T* t) { | |
147 using std::swap; | |
148 | |
149 Ref ref(t); | |
150 if (set_.find(ref) != set_.end()) | |
151 return false; // Already have this one. | |
152 | |
153 size_t new_index = vector_.size(); | |
154 vector_.resize(new_index + 1); | |
155 swap(vector_[new_index], *t); | |
156 set_.insert(Ref(&vector_, vector_.size() - 1, ref.hash_val())); | |
157 return true; | |
158 } | |
159 | |
160 // Appends a range of items from an iterator. | |
161 template<typename iter> void Append(const iter& begin, const iter& end) { | |
162 for (iter i = begin; i < end; i++) | |
viettrungluu
2014/08/06 19:43:52
Generally preferred:
!= end
++i
| |
163 push_back(*i); | |
viettrungluu
2014/08/06 19:43:52
Maybe you should have a (debug-only) assertion abo
brettw
2014/08/06 20:13:03
This calls push_back which handles duplicate eleme
| |
164 } | |
165 | |
166 // Returns the index of the item matching the given value in the list, or | |
167 // npos if it's not found. | |
168 size_t IndexOf(const T& t) const { | |
169 Ref ref(&t); | |
170 typename HashSet::const_iterator found = set_.find(ref); | |
171 if (found == set_.end()) | |
172 return npos; | |
173 return found->index(); | |
174 } | |
175 | |
176 private: | |
177 typedef internal::UniquifyRef<T> Ref; | |
178 typedef base::hash_set<Ref> HashSet; | |
179 | |
180 HashSet set_; | |
181 Vector vector_; | |
182 }; | |
183 | |
184 #endif // TOOLS_GN_UNIQUE_VECTOR_H_ | |
OLD | NEW |