OLD | NEW |
1 // Copyright 2012 the V8 project authors. All rights reserved. | 1 // Copyright 2012 the V8 project authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef V8_OBJECTS_H_ | 5 #ifndef V8_OBJECTS_H_ |
6 #define V8_OBJECTS_H_ | 6 #define V8_OBJECTS_H_ |
7 | 7 |
8 #include <iosfwd> | 8 #include <iosfwd> |
9 | 9 |
10 #include "src/allocation.h" | 10 #include "src/allocation.h" |
(...skipping 3283 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3294 DCHECK(UsesSeed); | 3294 DCHECK(UsesSeed); |
3295 return Hash(key); | 3295 return Hash(key); |
3296 } | 3296 } |
3297 static uint32_t HashForObject(Key key, Object* object) { return 0; } | 3297 static uint32_t HashForObject(Key key, Object* object) { return 0; } |
3298 static uint32_t SeededHashForObject(Key key, uint32_t seed, Object* object) { | 3298 static uint32_t SeededHashForObject(Key key, uint32_t seed, Object* object) { |
3299 DCHECK(UsesSeed); | 3299 DCHECK(UsesSeed); |
3300 return HashForObject(key, object); | 3300 return HashForObject(key, object); |
3301 } | 3301 } |
3302 }; | 3302 }; |
3303 | 3303 |
3304 template<typename Derived, typename Shape, typename Key> | 3304 |
3305 class HashTable: public FixedArray { | 3305 class HashTableBase : public FixedArray { |
3306 public: | 3306 public: |
3307 // Wrapper methods | |
3308 inline uint32_t Hash(Key key) { | |
3309 if (Shape::UsesSeed) { | |
3310 return Shape::SeededHash(key, GetHeap()->HashSeed()); | |
3311 } else { | |
3312 return Shape::Hash(key); | |
3313 } | |
3314 } | |
3315 | |
3316 inline uint32_t HashForObject(Key key, Object* object) { | |
3317 if (Shape::UsesSeed) { | |
3318 return Shape::SeededHashForObject(key, GetHeap()->HashSeed(), object); | |
3319 } else { | |
3320 return Shape::HashForObject(key, object); | |
3321 } | |
3322 } | |
3323 | |
3324 // Returns the number of elements in the hash table. | 3307 // Returns the number of elements in the hash table. |
3325 int NumberOfElements() { | 3308 int NumberOfElements() { |
3326 return Smi::cast(get(kNumberOfElementsIndex))->value(); | 3309 return Smi::cast(get(kNumberOfElementsIndex))->value(); |
3327 } | 3310 } |
3328 | 3311 |
3329 // Returns the number of deleted elements in the hash table. | 3312 // Returns the number of deleted elements in the hash table. |
3330 int NumberOfDeletedElements() { | 3313 int NumberOfDeletedElements() { |
3331 return Smi::cast(get(kNumberOfDeletedElementsIndex))->value(); | 3314 return Smi::cast(get(kNumberOfDeletedElementsIndex))->value(); |
3332 } | 3315 } |
3333 | 3316 |
(...skipping 10 matching lines...) Expand all Loading... |
3344 // a hash table. | 3327 // a hash table. |
3345 void ElementRemoved() { | 3328 void ElementRemoved() { |
3346 SetNumberOfElements(NumberOfElements() - 1); | 3329 SetNumberOfElements(NumberOfElements() - 1); |
3347 SetNumberOfDeletedElements(NumberOfDeletedElements() + 1); | 3330 SetNumberOfDeletedElements(NumberOfDeletedElements() + 1); |
3348 } | 3331 } |
3349 void ElementsRemoved(int n) { | 3332 void ElementsRemoved(int n) { |
3350 SetNumberOfElements(NumberOfElements() - n); | 3333 SetNumberOfElements(NumberOfElements() - n); |
3351 SetNumberOfDeletedElements(NumberOfDeletedElements() + n); | 3334 SetNumberOfDeletedElements(NumberOfDeletedElements() + n); |
3352 } | 3335 } |
3353 | 3336 |
3354 // Returns a new HashTable object. | |
3355 MUST_USE_RESULT static Handle<Derived> New( | |
3356 Isolate* isolate, | |
3357 int at_least_space_for, | |
3358 MinimumCapacity capacity_option = USE_DEFAULT_MINIMUM_CAPACITY, | |
3359 PretenureFlag pretenure = NOT_TENURED); | |
3360 | |
3361 // Computes the required capacity for a table holding the given | 3337 // Computes the required capacity for a table holding the given |
3362 // number of elements. May be more than HashTable::kMaxCapacity. | 3338 // number of elements. May be more than HashTable::kMaxCapacity. |
3363 static int ComputeCapacity(int at_least_space_for); | 3339 static inline int ComputeCapacity(int at_least_space_for); |
3364 | 3340 |
3365 // Returns the key at entry. | 3341 // Use a different heuristic to compute capacity when serializing. |
3366 Object* KeyAt(int entry) { return get(EntryToIndex(entry)); } | 3342 static inline int ComputeCapacityForSerialization(int at_least_space_for); |
3367 | 3343 |
3368 // Tells whether k is a real key. The hole and undefined are not allowed | 3344 // Tells whether k is a real key. The hole and undefined are not allowed |
3369 // as keys and can be used to indicate missing or deleted elements. | 3345 // as keys and can be used to indicate missing or deleted elements. |
3370 bool IsKey(Object* k) { | 3346 bool IsKey(Object* k) { |
3371 return !k->IsTheHole() && !k->IsUndefined(); | 3347 return !k->IsTheHole() && !k->IsUndefined(); |
3372 } | 3348 } |
3373 | 3349 |
3374 // Garbage collection support. | |
3375 void IteratePrefix(ObjectVisitor* visitor); | |
3376 void IterateElements(ObjectVisitor* visitor); | |
3377 | |
3378 DECLARE_CAST(HashTable) | |
3379 | |
3380 // Compute the probe offset (quadratic probing). | 3350 // Compute the probe offset (quadratic probing). |
3381 INLINE(static uint32_t GetProbeOffset(uint32_t n)) { | 3351 INLINE(static uint32_t GetProbeOffset(uint32_t n)) { |
3382 return (n + n * n) >> 1; | 3352 return (n + n * n) >> 1; |
3383 } | 3353 } |
3384 | 3354 |
3385 static const int kNumberOfElementsIndex = 0; | 3355 static const int kNumberOfElementsIndex = 0; |
3386 static const int kNumberOfDeletedElementsIndex = 1; | 3356 static const int kNumberOfDeletedElementsIndex = 1; |
3387 static const int kCapacityIndex = 2; | 3357 static const int kCapacityIndex = 2; |
3388 static const int kPrefixStartIndex = 3; | 3358 static const int kPrefixStartIndex = 3; |
3389 static const int kElementsStartIndex = | |
3390 kPrefixStartIndex + Shape::kPrefixSize; | |
3391 static const int kEntrySize = Shape::kEntrySize; | |
3392 static const int kElementsStartOffset = | |
3393 kHeaderSize + kElementsStartIndex * kPointerSize; | |
3394 static const int kCapacityOffset = | |
3395 kHeaderSize + kCapacityIndex * kPointerSize; | |
3396 | 3359 |
3397 // Constant used for denoting a absent entry. | 3360 // Constant used for denoting a absent entry. |
3398 static const int kNotFound = -1; | 3361 static const int kNotFound = -1; |
3399 | 3362 |
3400 // Maximal capacity of HashTable. Based on maximal length of underlying | |
3401 // FixedArray. Staying below kMaxCapacity also ensures that EntryToIndex | |
3402 // cannot overflow. | |
3403 static const int kMaxCapacity = | |
3404 (FixedArray::kMaxLength - kElementsStartOffset) / kEntrySize; | |
3405 | |
3406 // Find entry for key otherwise return kNotFound. | |
3407 inline int FindEntry(Key key); | |
3408 int FindEntry(Isolate* isolate, Key key); | |
3409 | |
3410 // Rehashes the table in-place. | |
3411 void Rehash(Key key); | |
3412 | |
3413 protected: | 3363 protected: |
3414 friend class ObjectHashTable; | |
3415 | |
3416 // Find the entry at which to insert element with the given key that | |
3417 // has the given hash value. | |
3418 uint32_t FindInsertionEntry(uint32_t hash); | |
3419 | |
3420 // Returns the index for an entry (of the key) | |
3421 static inline int EntryToIndex(int entry) { | |
3422 return (entry * kEntrySize) + kElementsStartIndex; | |
3423 } | |
3424 | |
3425 // Update the number of elements in the hash table. | 3364 // Update the number of elements in the hash table. |
3426 void SetNumberOfElements(int nof) { | 3365 void SetNumberOfElements(int nof) { |
3427 set(kNumberOfElementsIndex, Smi::FromInt(nof)); | 3366 set(kNumberOfElementsIndex, Smi::FromInt(nof)); |
3428 } | 3367 } |
3429 | 3368 |
3430 // Update the number of deleted elements in the hash table. | 3369 // Update the number of deleted elements in the hash table. |
3431 void SetNumberOfDeletedElements(int nod) { | 3370 void SetNumberOfDeletedElements(int nod) { |
3432 set(kNumberOfDeletedElementsIndex, Smi::FromInt(nod)); | 3371 set(kNumberOfDeletedElementsIndex, Smi::FromInt(nod)); |
3433 } | 3372 } |
3434 | 3373 |
3435 // Sets the capacity of the hash table. | |
3436 void SetCapacity(int capacity) { | |
3437 // To scale a computed hash code to fit within the hash table, we | |
3438 // use bit-wise AND with a mask, so the capacity must be positive | |
3439 // and non-zero. | |
3440 DCHECK(capacity > 0); | |
3441 DCHECK(capacity <= kMaxCapacity); | |
3442 set(kCapacityIndex, Smi::FromInt(capacity)); | |
3443 } | |
3444 | |
3445 | |
3446 // Returns probe entry. | 3374 // Returns probe entry. |
3447 static uint32_t GetProbe(uint32_t hash, uint32_t number, uint32_t size) { | 3375 static uint32_t GetProbe(uint32_t hash, uint32_t number, uint32_t size) { |
3448 DCHECK(base::bits::IsPowerOfTwo32(size)); | 3376 DCHECK(base::bits::IsPowerOfTwo32(size)); |
3449 return (hash + GetProbeOffset(number)) & (size - 1); | 3377 return (hash + GetProbeOffset(number)) & (size - 1); |
3450 } | 3378 } |
3451 | 3379 |
3452 inline static uint32_t FirstProbe(uint32_t hash, uint32_t size) { | 3380 inline static uint32_t FirstProbe(uint32_t hash, uint32_t size) { |
3453 return hash & (size - 1); | 3381 return hash & (size - 1); |
3454 } | 3382 } |
3455 | 3383 |
3456 inline static uint32_t NextProbe( | 3384 inline static uint32_t NextProbe( |
3457 uint32_t last, uint32_t number, uint32_t size) { | 3385 uint32_t last, uint32_t number, uint32_t size) { |
3458 return (last + number) & (size - 1); | 3386 return (last + number) & (size - 1); |
3459 } | 3387 } |
| 3388 }; |
| 3389 |
| 3390 |
| 3391 template <typename Derived, typename Shape, typename Key> |
| 3392 class HashTable : public HashTableBase { |
| 3393 public: |
| 3394 // Wrapper methods |
| 3395 inline uint32_t Hash(Key key) { |
| 3396 if (Shape::UsesSeed) { |
| 3397 return Shape::SeededHash(key, GetHeap()->HashSeed()); |
| 3398 } else { |
| 3399 return Shape::Hash(key); |
| 3400 } |
| 3401 } |
| 3402 |
| 3403 inline uint32_t HashForObject(Key key, Object* object) { |
| 3404 if (Shape::UsesSeed) { |
| 3405 return Shape::SeededHashForObject(key, GetHeap()->HashSeed(), object); |
| 3406 } else { |
| 3407 return Shape::HashForObject(key, object); |
| 3408 } |
| 3409 } |
| 3410 |
| 3411 // Returns a new HashTable object. |
| 3412 MUST_USE_RESULT static Handle<Derived> New( |
| 3413 Isolate* isolate, int at_least_space_for, |
| 3414 MinimumCapacity capacity_option = USE_DEFAULT_MINIMUM_CAPACITY, |
| 3415 PretenureFlag pretenure = NOT_TENURED); |
| 3416 |
| 3417 DECLARE_CAST(HashTable) |
| 3418 |
| 3419 // Garbage collection support. |
| 3420 void IteratePrefix(ObjectVisitor* visitor); |
| 3421 void IterateElements(ObjectVisitor* visitor); |
| 3422 |
| 3423 // Find entry for key otherwise return kNotFound. |
| 3424 inline int FindEntry(Key key); |
| 3425 int FindEntry(Isolate* isolate, Key key); |
| 3426 |
| 3427 // Rehashes the table in-place. |
| 3428 void Rehash(Key key); |
| 3429 |
| 3430 // Returns the key at entry. |
| 3431 Object* KeyAt(int entry) { return get(EntryToIndex(entry)); } |
| 3432 |
| 3433 static const int kElementsStartIndex = kPrefixStartIndex + Shape::kPrefixSize; |
| 3434 static const int kEntrySize = Shape::kEntrySize; |
| 3435 static const int kElementsStartOffset = |
| 3436 kHeaderSize + kElementsStartIndex * kPointerSize; |
| 3437 static const int kCapacityOffset = |
| 3438 kHeaderSize + kCapacityIndex * kPointerSize; |
| 3439 |
| 3440 protected: |
| 3441 friend class ObjectHashTable; |
| 3442 |
| 3443 // Find the entry at which to insert element with the given key that |
| 3444 // has the given hash value. |
| 3445 uint32_t FindInsertionEntry(uint32_t hash); |
3460 | 3446 |
3461 // Attempt to shrink hash table after removal of key. | 3447 // Attempt to shrink hash table after removal of key. |
3462 MUST_USE_RESULT static Handle<Derived> Shrink(Handle<Derived> table, Key key); | 3448 MUST_USE_RESULT static Handle<Derived> Shrink(Handle<Derived> table, Key key); |
3463 | 3449 |
3464 // Ensure enough space for n additional elements. | 3450 // Ensure enough space for n additional elements. |
3465 MUST_USE_RESULT static Handle<Derived> EnsureCapacity( | 3451 MUST_USE_RESULT static Handle<Derived> EnsureCapacity( |
3466 Handle<Derived> table, | 3452 Handle<Derived> table, |
3467 int n, | 3453 int n, |
3468 Key key, | 3454 Key key, |
3469 PretenureFlag pretenure = NOT_TENURED); | 3455 PretenureFlag pretenure = NOT_TENURED); |
3470 | 3456 |
| 3457 // Returns the index for an entry (of the key) |
| 3458 static inline int EntryToIndex(int entry) { |
| 3459 return (entry * kEntrySize) + kElementsStartIndex; |
| 3460 } |
| 3461 |
| 3462 // Sets the capacity of the hash table. |
| 3463 void SetCapacity(int capacity) { |
| 3464 // To scale a computed hash code to fit within the hash table, we |
| 3465 // use bit-wise AND with a mask, so the capacity must be positive |
| 3466 // and non-zero. |
| 3467 DCHECK(capacity > 0); |
| 3468 DCHECK(capacity <= kMaxCapacity); |
| 3469 set(kCapacityIndex, Smi::FromInt(capacity)); |
| 3470 } |
| 3471 |
| 3472 // Maximal capacity of HashTable. Based on maximal length of underlying |
| 3473 // FixedArray. Staying below kMaxCapacity also ensures that EntryToIndex |
| 3474 // cannot overflow. |
| 3475 static const int kMaxCapacity = |
| 3476 (FixedArray::kMaxLength - kElementsStartOffset) / kEntrySize; |
| 3477 |
3471 private: | 3478 private: |
3472 // Returns _expected_ if one of entries given by the first _probe_ probes is | 3479 // Returns _expected_ if one of entries given by the first _probe_ probes is |
3473 // equal to _expected_. Otherwise, returns the entry given by the probe | 3480 // equal to _expected_. Otherwise, returns the entry given by the probe |
3474 // number _probe_. | 3481 // number _probe_. |
3475 uint32_t EntryForProbe(Key key, Object* k, int probe, uint32_t expected); | 3482 uint32_t EntryForProbe(Key key, Object* k, int probe, uint32_t expected); |
3476 | 3483 |
3477 void Swap(uint32_t entry1, uint32_t entry2, WriteBarrierMode mode); | 3484 void Swap(uint32_t entry1, uint32_t entry2, WriteBarrierMode mode); |
3478 | 3485 |
3479 // Rehashes this hash-table into the new table. | 3486 // Rehashes this hash-table into the new table. |
3480 void Rehash(Handle<Derived> new_table, Key key); | 3487 void Rehash(Handle<Derived> new_table, Key key); |
(...skipping 7601 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
11082 } else { | 11089 } else { |
11083 value &= ~(1 << bit_position); | 11090 value &= ~(1 << bit_position); |
11084 } | 11091 } |
11085 return value; | 11092 return value; |
11086 } | 11093 } |
11087 }; | 11094 }; |
11088 | 11095 |
11089 } } // namespace v8::internal | 11096 } } // namespace v8::internal |
11090 | 11097 |
11091 #endif // V8_OBJECTS_H_ | 11098 #endif // V8_OBJECTS_H_ |
OLD | NEW |