OLD | NEW |
1 // Copyright 2013 the V8 project authors. All rights reserved. | 1 // Copyright 2013 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
(...skipping 46 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
57 explicit Unique(Handle<T> handle) { | 57 explicit Unique(Handle<T> handle) { |
58 if (handle.is_null()) { | 58 if (handle.is_null()) { |
59 raw_address_ = NULL; | 59 raw_address_ = NULL; |
60 } else { | 60 } else { |
61 raw_address_ = reinterpret_cast<Address>(*handle); | 61 raw_address_ = reinterpret_cast<Address>(*handle); |
62 ASSERT_NE(raw_address_, NULL); | 62 ASSERT_NE(raw_address_, NULL); |
63 } | 63 } |
64 handle_ = handle; | 64 handle_ = handle; |
65 } | 65 } |
66 | 66 |
67 // TODO(titzer): this is a hack to migrate to Unique<T> incrementally. | |
68 Unique(Address raw_address, Handle<T> handle) | |
69 : raw_address_(raw_address), handle_(handle) { } | |
70 | |
71 // Constructor for handling automatic up casting. | 67 // Constructor for handling automatic up casting. |
72 // Ex. Unique<JSFunction> can be passed when Unique<Object> is expected. | 68 // Ex. Unique<JSFunction> can be passed when Unique<Object> is expected. |
73 template <class S> Unique(Unique<S> uniq) { | 69 template <class S> Unique(Unique<S> uniq) { |
74 #ifdef DEBUG | 70 #ifdef DEBUG |
75 T* a = NULL; | 71 T* a = NULL; |
76 S* b = NULL; | 72 S* b = NULL; |
77 a = b; // Fake assignment to enforce type checks. | 73 a = b; // Fake assignment to enforce type checks. |
78 USE(a); | 74 USE(a); |
79 #endif | 75 #endif |
80 raw_address_ = uniq.raw_address_; | 76 raw_address_ = uniq.raw_address_; |
(...skipping 54 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
135 size_++; | 131 size_++; |
136 return; | 132 return; |
137 } | 133 } |
138 } | 134 } |
139 // Append the element to the the end. | 135 // Append the element to the the end. |
140 Grow(size_ + 1, zone); | 136 Grow(size_ + 1, zone); |
141 array_[size_++] = uniq; | 137 array_[size_++] = uniq; |
142 } | 138 } |
143 | 139 |
144 // Compare this set against another set. O(|this|). | 140 // Compare this set against another set. O(|this|). |
145 bool Equals(UniqueSet<T>* that) const { | 141 bool Equals(UniqueSet<T>* that) { |
146 if (that->size_ != this->size_) return false; | 142 if (that->size_ != this->size_) return false; |
147 for (int i = 0; i < this->size_; i++) { | 143 for (int i = 0; i < this->size_; i++) { |
148 if (this->array_[i] != that->array_[i]) return false; | 144 if (this->array_[i] != that->array_[i]) return false; |
149 } | 145 } |
150 return true; | 146 return true; |
151 } | 147 } |
152 | 148 |
153 template <typename U> | |
154 bool Contains(Unique<U> elem) const { | |
155 // TODO(titzer): use binary search for larger sets. | |
156 for (int i = 0; i < size_; i++) { | |
157 if (this->array_[i] == elem) return true; | |
158 } | |
159 return false; | |
160 } | |
161 | |
162 // Check if this set is a subset of the given set. O(|this| + |that|). | 149 // Check if this set is a subset of the given set. O(|this| + |that|). |
163 bool IsSubset(UniqueSet<T>* that) const { | 150 bool IsSubset(UniqueSet<T>* that) { |
164 if (that->size_ < this->size_) return false; | 151 if (that->size_ < this->size_) return false; |
165 int j = 0; | 152 int j = 0; |
166 for (int i = 0; i < this->size_; i++) { | 153 for (int i = 0; i < this->size_; i++) { |
167 Unique<T> sought = this->array_[i]; | 154 Unique<T> sought = this->array_[i]; |
168 while (true) { | 155 while (true) { |
169 if (sought == that->array_[j++]) break; | 156 if (sought == that->array_[j++]) break; |
170 // Fail whenever there are more elements in {this} than {that}. | 157 // Fail whenever there are more elements in {this} than {that}. |
171 if ((this->size_ - i) > (that->size_ - j)) return false; | 158 if ((this->size_ - i) > (that->size_ - j)) return false; |
172 } | 159 } |
173 } | 160 } |
174 return true; | 161 return true; |
175 } | 162 } |
176 | 163 |
177 // Returns a new set representing the intersection of this set and the other. | 164 // Returns a new set representing the intersection of this set and the other. |
178 // O(|this| + |that|). | 165 // O(|this| + |that|). |
179 UniqueSet<T>* Intersect(UniqueSet<T>* that, Zone* zone) const { | 166 UniqueSet<T>* Intersect(UniqueSet<T>* that, Zone* zone) { |
180 if (that->size_ == 0 || this->size_ == 0) return new(zone) UniqueSet<T>(); | 167 if (that->size_ == 0 || this->size_ == 0) return new(zone) UniqueSet<T>(); |
181 | 168 |
182 UniqueSet<T>* out = new(zone) UniqueSet<T>(); | 169 UniqueSet<T>* out = new(zone) UniqueSet<T>(); |
183 out->Grow(Min(this->size_, that->size_), zone); | 170 out->Grow(Min(this->size_, that->size_), zone); |
184 | 171 |
185 int i = 0, j = 0, k = 0; | 172 int i = 0, j = 0, k = 0; |
186 while (i < this->size_ && j < that->size_) { | 173 while (i < this->size_ && j < that->size_) { |
187 Unique<T> a = this->array_[i]; | 174 Unique<T> a = this->array_[i]; |
188 Unique<T> b = that->array_[j]; | 175 Unique<T> b = that->array_[j]; |
189 if (a == b) { | 176 if (a == b) { |
190 out->array_[k++] = a; | 177 out->array_[k++] = a; |
191 i++; | 178 i++; |
192 j++; | 179 j++; |
193 } else if (a.raw_address_ < b.raw_address_) { | 180 } else if (a.raw_address_ < b.raw_address_) { |
194 i++; | 181 i++; |
195 } else { | 182 } else { |
196 j++; | 183 j++; |
197 } | 184 } |
198 } | 185 } |
199 | 186 |
200 out->size_ = k; | 187 out->size_ = k; |
201 return out; | 188 return out; |
202 } | 189 } |
203 | 190 |
204 // Returns a new set representing the union of this set and the other. | 191 // Returns a new set representing the union of this set and the other. |
205 // O(|this| + |that|). | 192 // O(|this| + |that|). |
206 UniqueSet<T>* Union(UniqueSet<T>* that, Zone* zone) const { | 193 UniqueSet<T>* Union(UniqueSet<T>* that, Zone* zone) { |
207 if (that->size_ == 0) return this->Copy(zone); | 194 if (that->size_ == 0) return this->Copy(zone); |
208 if (this->size_ == 0) return that->Copy(zone); | 195 if (this->size_ == 0) return that->Copy(zone); |
209 | 196 |
210 UniqueSet<T>* out = new(zone) UniqueSet<T>(); | 197 UniqueSet<T>* out = new(zone) UniqueSet<T>(); |
211 out->Grow(this->size_ + that->size_, zone); | 198 out->Grow(this->size_ + that->size_, zone); |
212 | 199 |
213 int i = 0, j = 0, k = 0; | 200 int i = 0, j = 0, k = 0; |
214 while (i < this->size_ && j < that->size_) { | 201 while (i < this->size_ && j < that->size_) { |
215 Unique<T> a = this->array_[i]; | 202 Unique<T> a = this->array_[i]; |
216 Unique<T> b = that->array_[j]; | 203 Unique<T> b = that->array_[j]; |
(...skipping 11 matching lines...) Expand all Loading... |
228 } | 215 } |
229 | 216 |
230 while (i < this->size_) out->array_[k++] = this->array_[i++]; | 217 while (i < this->size_) out->array_[k++] = this->array_[i++]; |
231 while (j < that->size_) out->array_[k++] = that->array_[j++]; | 218 while (j < that->size_) out->array_[k++] = that->array_[j++]; |
232 | 219 |
233 out->size_ = k; | 220 out->size_ = k; |
234 return out; | 221 return out; |
235 } | 222 } |
236 | 223 |
237 // Makes an exact copy of this set. O(|this| + |that|). | 224 // Makes an exact copy of this set. O(|this| + |that|). |
238 UniqueSet<T>* Copy(Zone* zone) const { | 225 UniqueSet<T>* Copy(Zone* zone) { |
239 UniqueSet<T>* copy = new(zone) UniqueSet<T>(); | 226 UniqueSet<T>* copy = new(zone) UniqueSet<T>(); |
240 copy->size_ = this->size_; | 227 copy->size_ = this->size_; |
241 copy->capacity_ = this->size_; | 228 copy->capacity_ = this->size_; |
242 copy->array_ = zone->NewArray<Unique<T> >(this->size_); | 229 copy->array_ = zone->NewArray<Unique<T> >(this->size_); |
243 memcpy(copy->array_, this->array_, this->size_ * sizeof(Unique<T>)); | 230 memcpy(copy->array_, this->array_, this->size_ * sizeof(Unique<T>)); |
244 return copy; | 231 return copy; |
245 } | 232 } |
246 | 233 |
247 inline int size() const { | 234 inline int size() { |
248 return size_; | 235 return size_; |
249 } | 236 } |
250 | 237 |
251 inline Unique<T> at(int index) const { | |
252 ASSERT(index >= 0 && index < size_); | |
253 return array_[index]; | |
254 } | |
255 | |
256 private: | 238 private: |
257 // These sets should be small, since operations are implemented with simple | 239 // These sets should be small, since operations are implemented with simple |
258 // linear algorithms. Enforce a maximum size. | 240 // linear algorithms. Enforce a maximum size. |
259 static const int kMaxCapacity = 65535; | 241 static const int kMaxCapacity = 65535; |
260 | 242 |
261 uint16_t size_; | 243 uint16_t size_; |
262 uint16_t capacity_; | 244 uint16_t capacity_; |
263 Unique<T>* array_; | 245 Unique<T>* array_; |
264 | 246 |
265 // Grow the size of internal storage to be at least {size} elements. | 247 // Grow the size of internal storage to be at least {size} elements. |
266 void Grow(int size, Zone* zone) { | 248 void Grow(int size, Zone* zone) { |
267 CHECK(size < kMaxCapacity); // Enforce maximum size. | 249 CHECK(size < kMaxCapacity); // Enforce maximum size. |
268 if (capacity_ < size) { | 250 if (capacity_ < size) { |
269 int new_capacity = 2 * capacity_ + size; | 251 int new_capacity = 2 * capacity_ + size; |
270 if (new_capacity > kMaxCapacity) new_capacity = kMaxCapacity; | 252 if (new_capacity > kMaxCapacity) new_capacity = kMaxCapacity; |
271 Unique<T>* new_array = zone->NewArray<Unique<T> >(new_capacity); | 253 Unique<T>* new_array = zone->NewArray<Unique<T> >(new_capacity); |
272 if (size_ > 0) { | 254 if (size_ > 0) { |
273 memcpy(new_array, array_, size_ * sizeof(Unique<T>)); | 255 memcpy(new_array, array_, size_ * sizeof(Unique<T>)); |
274 } | 256 } |
275 capacity_ = new_capacity; | 257 capacity_ = new_capacity; |
276 array_ = new_array; | 258 array_ = new_array; |
277 } | 259 } |
278 } | 260 } |
279 }; | 261 }; |
280 | 262 |
281 | 263 |
282 } } // namespace v8::internal | 264 } } // namespace v8::internal |
283 | 265 |
284 #endif // V8_HYDROGEN_UNIQUE_H_ | 266 #endif // V8_HYDROGEN_UNIQUE_H_ |
OLD | NEW |