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