OLD | NEW |
1 // Copyright 2012 the V8 project authors. All rights reserved. | 1 // Copyright 2012 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 3718 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3729 | 3729 |
3730 // Returns a new HashTable object. Might return Failure. | 3730 // Returns a new HashTable object. Might return Failure. |
3731 // TODO(ishell): this will be eventually replaced by New(). | 3731 // TODO(ishell): this will be eventually replaced by New(). |
3732 MUST_USE_RESULT static MaybeObject* Allocate( | 3732 MUST_USE_RESULT static MaybeObject* Allocate( |
3733 Heap* heap, | 3733 Heap* heap, |
3734 int at_least_space_for, | 3734 int at_least_space_for, |
3735 MinimumCapacity capacity_option = USE_DEFAULT_MINIMUM_CAPACITY, | 3735 MinimumCapacity capacity_option = USE_DEFAULT_MINIMUM_CAPACITY, |
3736 PretenureFlag pretenure = NOT_TENURED); | 3736 PretenureFlag pretenure = NOT_TENURED); |
3737 | 3737 |
3738 // Returns a new HashTable object. | 3738 // Returns a new HashTable object. |
3739 static Handle<Derived> New( | 3739 MUST_USE_RESULT static Handle<Derived> New( |
3740 Isolate* isolate, | 3740 Isolate* isolate, |
3741 int at_least_space_for, | 3741 int at_least_space_for, |
3742 MinimumCapacity capacity_option = USE_DEFAULT_MINIMUM_CAPACITY, | 3742 MinimumCapacity capacity_option = USE_DEFAULT_MINIMUM_CAPACITY, |
3743 PretenureFlag pretenure = NOT_TENURED); | 3743 PretenureFlag pretenure = NOT_TENURED); |
3744 | 3744 |
3745 // Computes the required capacity for a table holding the given | 3745 // Computes the required capacity for a table holding the given |
3746 // number of elements. May be more than HashTable::kMaxCapacity. | 3746 // number of elements. May be more than HashTable::kMaxCapacity. |
3747 static int ComputeCapacity(int at_least_space_for); | 3747 static int ComputeCapacity(int at_least_space_for); |
3748 | 3748 |
3749 // Returns the key at entry. | 3749 // Returns the key at entry. |
(...skipping 86 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3836 | 3836 |
3837 inline static uint32_t FirstProbe(uint32_t hash, uint32_t size) { | 3837 inline static uint32_t FirstProbe(uint32_t hash, uint32_t size) { |
3838 return hash & (size - 1); | 3838 return hash & (size - 1); |
3839 } | 3839 } |
3840 | 3840 |
3841 inline static uint32_t NextProbe( | 3841 inline static uint32_t NextProbe( |
3842 uint32_t last, uint32_t number, uint32_t size) { | 3842 uint32_t last, uint32_t number, uint32_t size) { |
3843 return (last + number) & (size - 1); | 3843 return (last + number) & (size - 1); |
3844 } | 3844 } |
3845 | 3845 |
| 3846 // Attempt to shrink hash table after removal of key. |
| 3847 static Handle<Derived> Shrink(Handle<Derived> table, Key key); |
| 3848 |
| 3849 // Ensure enough space for n additional elements. |
| 3850 MUST_USE_RESULT static Handle<Derived> EnsureCapacity( |
| 3851 Handle<Derived> table, |
| 3852 int n, |
| 3853 Key key, |
| 3854 PretenureFlag pretenure = NOT_TENURED); |
| 3855 |
| 3856 private: |
3846 // Returns _expected_ if one of entries given by the first _probe_ probes is | 3857 // Returns _expected_ if one of entries given by the first _probe_ probes is |
3847 // equal to _expected_. Otherwise, returns the entry given by the probe | 3858 // equal to _expected_. Otherwise, returns the entry given by the probe |
3848 // number _probe_. | 3859 // number _probe_. |
3849 uint32_t EntryForProbe(Key key, Object* k, int probe, uint32_t expected); | 3860 uint32_t EntryForProbe(Key key, Object* k, int probe, uint32_t expected); |
3850 | 3861 |
3851 void Swap(uint32_t entry1, uint32_t entry2, WriteBarrierMode mode); | 3862 void Swap(uint32_t entry1, uint32_t entry2, WriteBarrierMode mode); |
3852 | 3863 |
3853 // Rehashes this hash-table into the new table. | 3864 // Rehashes this hash-table into the new table. |
3854 void Rehash(Derived* new_table, Key key); | 3865 void Rehash(Handle<Derived> new_table, Key key); |
3855 | |
3856 // Attempt to shrink hash table after removal of key. | |
3857 static Handle<Derived> Shrink(Handle<Derived> table, Key key); | |
3858 | |
3859 // Ensure enough space for n additional elements. | |
3860 MUST_USE_RESULT MaybeObject* EnsureCapacity( | |
3861 int n, | |
3862 Key key, | |
3863 PretenureFlag pretenure = NOT_TENURED); | |
3864 static Handle<Derived> EnsureCapacity( | |
3865 Handle<Derived> table, | |
3866 int n, | |
3867 Key key, | |
3868 PretenureFlag pretenure = NOT_TENURED); | |
3869 }; | 3866 }; |
3870 | 3867 |
3871 | 3868 |
3872 // HashTableKey is an abstract superclass for virtual key behavior. | 3869 // HashTableKey is an abstract superclass for virtual key behavior. |
3873 class HashTableKey { | 3870 class HashTableKey { |
3874 public: | 3871 public: |
3875 // Returns whether the other object matches this key. | 3872 // Returns whether the other object matches this key. |
3876 virtual bool IsMatch(Object* other) = 0; | 3873 virtual bool IsMatch(Object* other) = 0; |
3877 // Returns the hash value for this key. | 3874 // Returns the hash value for this key. |
3878 virtual uint32_t Hash() = 0; | 3875 virtual uint32_t Hash() = 0; |
(...skipping 7404 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
11283 } else { | 11280 } else { |
11284 value &= ~(1 << bit_position); | 11281 value &= ~(1 << bit_position); |
11285 } | 11282 } |
11286 return value; | 11283 return value; |
11287 } | 11284 } |
11288 }; | 11285 }; |
11289 | 11286 |
11290 } } // namespace v8::internal | 11287 } } // namespace v8::internal |
11291 | 11288 |
11292 #endif // V8_OBJECTS_H_ | 11289 #endif // V8_OBJECTS_H_ |
OLD | NEW |