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 MUST_USE_RESULT static Handle<Derived> New( | 3739 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: | |
3857 // Returns _expected_ if one of entries given by the first _probe_ probes is | 3846 // Returns _expected_ if one of entries given by the first _probe_ probes is |
3858 // equal to _expected_. Otherwise, returns the entry given by the probe | 3847 // equal to _expected_. Otherwise, returns the entry given by the probe |
3859 // number _probe_. | 3848 // number _probe_. |
3860 uint32_t EntryForProbe(Key key, Object* k, int probe, uint32_t expected); | 3849 uint32_t EntryForProbe(Key key, Object* k, int probe, uint32_t expected); |
3861 | 3850 |
3862 void Swap(uint32_t entry1, uint32_t entry2, WriteBarrierMode mode); | 3851 void Swap(uint32_t entry1, uint32_t entry2, WriteBarrierMode mode); |
3863 | 3852 |
3864 // Rehashes this hash-table into the new table. | 3853 // Rehashes this hash-table into the new table. |
3865 void Rehash(Handle<Derived> new_table, Key key); | 3854 void Rehash(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); |
3866 }; | 3869 }; |
3867 | 3870 |
3868 | 3871 |
3869 // HashTableKey is an abstract superclass for virtual key behavior. | 3872 // HashTableKey is an abstract superclass for virtual key behavior. |
3870 class HashTableKey { | 3873 class HashTableKey { |
3871 public: | 3874 public: |
3872 // Returns whether the other object matches this key. | 3875 // Returns whether the other object matches this key. |
3873 virtual bool IsMatch(Object* other) = 0; | 3876 virtual bool IsMatch(Object* other) = 0; |
3874 // Returns the hash value for this key. | 3877 // Returns the hash value for this key. |
3875 virtual uint32_t Hash() = 0; | 3878 virtual uint32_t Hash() = 0; |
(...skipping 222 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
4098 Handle<Derived> dictionary, | 4101 Handle<Derived> dictionary, |
4099 Key key, | 4102 Key key, |
4100 Handle<Object> value, | 4103 Handle<Object> value, |
4101 PropertyDetails details, | 4104 PropertyDetails details, |
4102 uint32_t hash); | 4105 uint32_t hash); |
4103 | 4106 |
4104 // Generate new enumeration indices to avoid enumeration index overflow. | 4107 // Generate new enumeration indices to avoid enumeration index overflow. |
4105 static void GenerateNewEnumerationIndices(Handle<Derived> dictionary); | 4108 static void GenerateNewEnumerationIndices(Handle<Derived> dictionary); |
4106 static const int kMaxNumberKeyIndex = DerivedHashTable::kPrefixStartIndex; | 4109 static const int kMaxNumberKeyIndex = DerivedHashTable::kPrefixStartIndex; |
4107 static const int kNextEnumerationIndexIndex = kMaxNumberKeyIndex + 1; | 4110 static const int kNextEnumerationIndexIndex = kMaxNumberKeyIndex + 1; |
4108 | |
4109 private: | |
4110 // This is to hide HashTable::New() which could clash with Dictionary::New(). | |
4111 // The latter one must be used for creating Dictionary and successors. | |
4112 MUST_USE_RESULT static Handle<Derived> New( | |
4113 Isolate* isolate, | |
4114 int at_least_space_for, | |
4115 MinimumCapacity capacity_option, | |
4116 PretenureFlag pretenure); | |
4117 }; | 4111 }; |
4118 | 4112 |
4119 | 4113 |
4120 class NameDictionaryShape : public BaseShape<Handle<Name> > { | 4114 class NameDictionaryShape : public BaseShape<Handle<Name> > { |
4121 public: | 4115 public: |
4122 static inline bool IsMatch(Handle<Name> key, Object* other); | 4116 static inline bool IsMatch(Handle<Name> key, Object* other); |
4123 static inline uint32_t Hash(Handle<Name> key); | 4117 static inline uint32_t Hash(Handle<Name> key); |
4124 static inline uint32_t HashForObject(Handle<Name> key, Object* object); | 4118 static inline uint32_t HashForObject(Handle<Name> key, Object* object); |
4125 MUST_USE_RESULT static inline MaybeObject* AsObject(Heap* heap, | 4119 MUST_USE_RESULT static inline MaybeObject* AsObject(Heap* heap, |
4126 Handle<Name> key); | 4120 Handle<Name> key); |
(...skipping 7162 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
11289 } else { | 11283 } else { |
11290 value &= ~(1 << bit_position); | 11284 value &= ~(1 << bit_position); |
11291 } | 11285 } |
11292 return value; | 11286 return value; |
11293 } | 11287 } |
11294 }; | 11288 }; |
11295 | 11289 |
11296 } } // namespace v8::internal | 11290 } } // namespace v8::internal |
11297 | 11291 |
11298 #endif // V8_OBJECTS_H_ | 11292 #endif // V8_OBJECTS_H_ |
OLD | NEW |