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 3956 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3967 static Handle<Derived> EnsureGrowable(Handle<Derived> table); | 3967 static Handle<Derived> EnsureGrowable(Handle<Derived> table); |
3968 | 3968 |
3969 // Returns an OrderedHashTable (possibly |table|) that's shrunken | 3969 // Returns an OrderedHashTable (possibly |table|) that's shrunken |
3970 // if possible. | 3970 // if possible. |
3971 static Handle<Derived> Shrink(Handle<Derived> table); | 3971 static Handle<Derived> Shrink(Handle<Derived> table); |
3972 | 3972 |
3973 // Returns a new empty OrderedHashTable and records the clearing so that | 3973 // Returns a new empty OrderedHashTable and records the clearing so that |
3974 // exisiting iterators can be updated. | 3974 // exisiting iterators can be updated. |
3975 static Handle<Derived> Clear(Handle<Derived> table); | 3975 static Handle<Derived> Clear(Handle<Derived> table); |
3976 | 3976 |
3977 // Returns an OrderedHashTable (possibly |table|) where |key| has been | |
3978 // removed. | |
3979 static Handle<Derived> Remove(Handle<Derived> table, Handle<Object> key, | |
3980 bool* was_present); | |
3981 | |
3982 // Returns kNotFound if the key isn't present. | |
3983 int FindEntry(Handle<Object> key, int hash); | |
3984 | |
3985 // Like the above, but doesn't require the caller to provide a hash. | |
3986 int FindEntry(Handle<Object> key); | |
3987 | |
3988 int NumberOfElements() { | 3977 int NumberOfElements() { |
3989 return Smi::cast(get(kNumberOfElementsIndex))->value(); | 3978 return Smi::cast(get(kNumberOfElementsIndex))->value(); |
3990 } | 3979 } |
3991 | 3980 |
3992 int NumberOfDeletedElements() { | 3981 int NumberOfDeletedElements() { |
3993 return Smi::cast(get(kNumberOfDeletedElementsIndex))->value(); | 3982 return Smi::cast(get(kNumberOfDeletedElementsIndex))->value(); |
3994 } | 3983 } |
3995 | 3984 |
3996 int UsedCapacity() { return NumberOfElements() + NumberOfDeletedElements(); } | 3985 int UsedCapacity() { return NumberOfElements() + NumberOfDeletedElements(); } |
3997 | 3986 |
3998 int NumberOfBuckets() { | 3987 int NumberOfBuckets() { |
3999 return Smi::cast(get(kNumberOfBucketsIndex))->value(); | 3988 return Smi::cast(get(kNumberOfBucketsIndex))->value(); |
4000 } | 3989 } |
4001 | 3990 |
4002 // Returns the index into the data table where the new entry | |
4003 // should be placed. The table is assumed to have enough space | |
4004 // for a new entry. | |
4005 int AddEntry(int hash); | |
4006 | |
4007 // Removes the entry, and puts the_hole in entrysize pointers | |
4008 // (leaving the hash table chain intact). | |
4009 void RemoveEntry(int entry); | |
4010 | |
4011 // Returns an index into |this| for the given entry. | 3991 // Returns an index into |this| for the given entry. |
4012 int EntryToIndex(int entry) { | 3992 int EntryToIndex(int entry) { |
4013 return kHashTableStartIndex + NumberOfBuckets() + (entry * kEntrySize); | 3993 return kHashTableStartIndex + NumberOfBuckets() + (entry * kEntrySize); |
4014 } | 3994 } |
4015 | 3995 |
4016 Object* KeyAt(int entry) { return get(EntryToIndex(entry)); } | 3996 Object* KeyAt(int entry) { return get(EntryToIndex(entry)); } |
4017 | 3997 |
4018 bool IsObsolete() { | 3998 bool IsObsolete() { |
4019 return !get(kNextTableIndex)->IsSmi(); | 3999 return !get(kNextTableIndex)->IsSmi(); |
4020 } | 4000 } |
(...skipping 50 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
4071 } | 4051 } |
4072 | 4052 |
4073 void SetNumberOfDeletedElements(int num) { | 4053 void SetNumberOfDeletedElements(int num) { |
4074 set(kNumberOfDeletedElementsIndex, Smi::FromInt(num)); | 4054 set(kNumberOfDeletedElementsIndex, Smi::FromInt(num)); |
4075 } | 4055 } |
4076 | 4056 |
4077 int Capacity() { | 4057 int Capacity() { |
4078 return NumberOfBuckets() * kLoadFactor; | 4058 return NumberOfBuckets() * kLoadFactor; |
4079 } | 4059 } |
4080 | 4060 |
4081 // Returns the next entry for the given entry. | |
4082 int ChainAt(int entry) { | |
4083 return Smi::cast(get(EntryToIndex(entry) + kChainOffset))->value(); | |
4084 } | |
4085 | |
4086 int HashToBucket(int hash) { | |
4087 return hash & (NumberOfBuckets() - 1); | |
4088 } | |
4089 | |
4090 int HashToEntry(int hash) { | |
4091 int bucket = HashToBucket(hash); | |
4092 return Smi::cast(get(kHashTableStartIndex + bucket))->value(); | |
4093 } | |
4094 | |
4095 void SetNextTable(Derived* next_table) { | 4061 void SetNextTable(Derived* next_table) { |
4096 set(kNextTableIndex, next_table); | 4062 set(kNextTableIndex, next_table); |
4097 } | 4063 } |
4098 | 4064 |
4099 void SetRemovedIndexAt(int index, int removed_index) { | 4065 void SetRemovedIndexAt(int index, int removed_index) { |
4100 return set(kRemovedHolesIndex + index, Smi::FromInt(removed_index)); | 4066 return set(kRemovedHolesIndex + index, Smi::FromInt(removed_index)); |
4101 } | 4067 } |
4102 | 4068 |
4103 static const int kRemovedHolesIndex = kHashTableStartIndex; | 4069 static const int kRemovedHolesIndex = kHashTableStartIndex; |
4104 | 4070 |
4105 static const int kMaxCapacity = | 4071 static const int kMaxCapacity = |
4106 (FixedArray::kMaxLength - kHashTableStartIndex) | 4072 (FixedArray::kMaxLength - kHashTableStartIndex) |
4107 / (1 + (kEntrySize * kLoadFactor)); | 4073 / (1 + (kEntrySize * kLoadFactor)); |
4108 }; | 4074 }; |
4109 | 4075 |
4110 | 4076 |
4111 class JSSetIterator; | 4077 class JSSetIterator; |
4112 | 4078 |
4113 | 4079 |
4114 class OrderedHashSet: public OrderedHashTable< | 4080 class OrderedHashSet: public OrderedHashTable< |
4115 OrderedHashSet, JSSetIterator, 1> { | 4081 OrderedHashSet, JSSetIterator, 1> { |
4116 public: | 4082 public: |
4117 DECLARE_CAST(OrderedHashSet) | 4083 DECLARE_CAST(OrderedHashSet) |
4118 | |
4119 bool Contains(Handle<Object> key); | |
4120 static Handle<OrderedHashSet> Add( | |
4121 Handle<OrderedHashSet> table, Handle<Object> key); | |
4122 }; | 4084 }; |
4123 | 4085 |
4124 | 4086 |
4125 class JSMapIterator; | 4087 class JSMapIterator; |
4126 | 4088 |
4127 | 4089 |
4128 class OrderedHashMap:public OrderedHashTable< | 4090 class OrderedHashMap |
4129 OrderedHashMap, JSMapIterator, 2> { | 4091 : public OrderedHashTable<OrderedHashMap, JSMapIterator, 2> { |
4130 public: | 4092 public: |
4131 DECLARE_CAST(OrderedHashMap) | 4093 DECLARE_CAST(OrderedHashMap) |
4132 | 4094 |
4133 Object* Lookup(Handle<Object> key); | |
4134 static Handle<OrderedHashMap> Put( | |
4135 Handle<OrderedHashMap> table, | |
4136 Handle<Object> key, | |
4137 Handle<Object> value); | |
4138 | |
4139 Object* ValueAt(int entry) { | 4095 Object* ValueAt(int entry) { |
4140 return get(EntryToIndex(entry) + kValueOffset); | 4096 return get(EntryToIndex(entry) + kValueOffset); |
4141 } | 4097 } |
4142 | 4098 |
4143 static const int kValueOffset = 1; | 4099 static const int kValueOffset = 1; |
4144 }; | 4100 }; |
4145 | 4101 |
4146 | 4102 |
4147 template <int entrysize> | 4103 template <int entrysize> |
4148 class WeakHashTableShape : public BaseShape<Handle<Object> > { | 4104 class WeakHashTableShape : public BaseShape<Handle<Object> > { |
(...skipping 6928 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
11077 } else { | 11033 } else { |
11078 value &= ~(1 << bit_position); | 11034 value &= ~(1 << bit_position); |
11079 } | 11035 } |
11080 return value; | 11036 return value; |
11081 } | 11037 } |
11082 }; | 11038 }; |
11083 | 11039 |
11084 } } // namespace v8::internal | 11040 } } // namespace v8::internal |
11085 | 11041 |
11086 #endif // V8_OBJECTS_H_ | 11042 #endif // V8_OBJECTS_H_ |
OLD | NEW |