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