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 73 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
84 // - JSFunctionProxy | 84 // - JSFunctionProxy |
85 // - FixedArrayBase | 85 // - FixedArrayBase |
86 // - ByteArray | 86 // - ByteArray |
87 // - FixedArray | 87 // - FixedArray |
88 // - DescriptorArray | 88 // - DescriptorArray |
89 // - HashTable | 89 // - HashTable |
90 // - Dictionary | 90 // - Dictionary |
91 // - StringTable | 91 // - StringTable |
92 // - CompilationCacheTable | 92 // - CompilationCacheTable |
93 // - CodeCacheHashTable | 93 // - CodeCacheHashTable |
94 // - MapCache | 94 // - MapCache |
Michael Starzinger
2014/04/02 12:09:37
nit: Can we add the three new classes into the hie
adamk
2014/04/02 22:01:10
Done.
| |
95 // - Context | 95 // - Context |
96 // - JSFunctionResultCache | 96 // - JSFunctionResultCache |
97 // - ScopeInfo | 97 // - ScopeInfo |
98 // - TransitionArray | 98 // - TransitionArray |
99 // - FixedDoubleArray | 99 // - FixedDoubleArray |
100 // - ExternalArray | 100 // - ExternalArray |
101 // - ExternalUint8ClampedArray | 101 // - ExternalUint8ClampedArray |
102 // - ExternalInt8Array | 102 // - ExternalInt8Array |
103 // - ExternalUint8Array | 103 // - ExternalUint8Array |
104 // - ExternalInt16Array | 104 // - ExternalInt16Array |
(...skipping 4137 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
4242 void AddEntry(int entry, Object* key, Object* value); | 4242 void AddEntry(int entry, Object* key, Object* value); |
4243 void RemoveEntry(int entry); | 4243 void RemoveEntry(int entry); |
4244 | 4244 |
4245 // Returns the index to the value of an entry. | 4245 // Returns the index to the value of an entry. |
4246 static inline int EntryToValueIndex(int entry) { | 4246 static inline int EntryToValueIndex(int entry) { |
4247 return EntryToIndex(entry) + 1; | 4247 return EntryToIndex(entry) + 1; |
4248 } | 4248 } |
4249 }; | 4249 }; |
4250 | 4250 |
4251 | 4251 |
4252 // OrderedHashTable is a HashTable with Object keys that preserves | |
4253 // insertion order. There are Map and Set interfaces (OrderedHashMap | |
4254 // and OrderedHashTable, below). It is meant to be used by JSMap/JSSet. | |
4255 // | |
4256 // Only Object* keys are supported, with Object::SameValue() used as the | |
4257 // equality operator and Object::GetHash() for the hash function. | |
4258 // | |
4259 // Based on the "Deterministic Hash Table" as described by Jason Orendorff at | |
4260 // https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables | |
4261 // Originally attributed to Tyler Close. | |
4262 // | |
4263 // Memory layout: | |
4264 // [0]: bucket count | |
4265 // [1]: element count | |
4266 // [2]: deleted element count | |
4267 // [3]: "hash table", an array of length NumberOfBuckets() entry numbers | |
Michael Starzinger
2014/04/02 12:09:37
nit: Can we somehow visually note that the "hash t
adamk
2014/04/02 22:01:10
Explained more. This could probably use some more
| |
4268 // followed by "data table", an array of length NumberOfBuckets() * | |
4269 // kLoadFactor entries | |
4270 template<int entrysize> | |
4271 class OrderedHashTable: public FixedArray { | |
4272 public: | |
4273 // Returns an OrderedHashTable with a capacity of at least |capacity|, | |
4274 // or returns a Failure if a GC occurs. | |
4275 MUST_USE_RESULT static MaybeObject* Allocate(Heap* heap, int capacity); | |
4276 | |
4277 // Returns an OrderedHashTable (possibly |this|) with enough space | |
4278 // to add at least one new element, or returns a Failure if a GC occurs. | |
4279 MUST_USE_RESULT MaybeObject* EnsureGrowable(); | |
4280 | |
4281 static OrderedHashTable* cast(Object* obj) { | |
4282 ASSERT(obj->IsFixedArray()); // TODO(adamk): Make a map for this | |
4283 return reinterpret_cast<OrderedHashTable*>(obj); | |
4284 } | |
4285 | |
4286 // Returns kNotFound if the key isn't present. | |
4287 int FindEntry(Object* key); | |
4288 | |
4289 int NumberOfElements() { | |
4290 return Smi::cast(get(kNumberOfElementsIndex))->value(); | |
4291 } | |
4292 | |
4293 int NumberOfDeletedElements() { | |
4294 return Smi::cast(get(kNumberOfDeletedElementsIndex))->value(); | |
4295 } | |
4296 | |
4297 int NumberOfBuckets() { | |
4298 return Smi::cast(get(kNumberOfBucketsIndex))->value(); | |
4299 } | |
4300 | |
4301 // Returns the index into the data table where the new entry | |
4302 // should be placed. The table is assumed to have enough space | |
4303 // for a new entry. | |
4304 int AddEntry(int hash); | |
4305 | |
4306 // Removes the entry, and puts the_hole in entrysize pointers | |
4307 // (leaving the hash table chain intact). | |
4308 void RemoveEntry(int entry); | |
4309 | |
4310 // Returns an index into |this| for the given entry. | |
4311 int EntryToIndex(int entry) { | |
4312 return kHashTableStartIndex + NumberOfBuckets() + (entry * kEntrySize); | |
4313 } | |
4314 | |
4315 MUST_USE_RESULT MaybeObject* Shrink(); | |
4316 MUST_USE_RESULT MaybeObject* Rehash(OrderedHashTable* new_table); | |
4317 | |
4318 static const int kNotFound = -1; | |
4319 | |
4320 private: | |
4321 void SetNumberOfBuckets(int num) { | |
4322 set(kNumberOfBucketsIndex, Smi::FromInt(num)); | |
4323 } | |
4324 | |
4325 void SetNumberOfElements(int num) { | |
4326 set(kNumberOfElementsIndex, Smi::FromInt(num)); | |
4327 } | |
4328 | |
4329 void SetNumberOfDeletedElements(int num) { | |
4330 set(kNumberOfDeletedElementsIndex, Smi::FromInt(num)); | |
4331 } | |
4332 | |
4333 int Capacity() { | |
4334 return NumberOfBuckets() * kLoadFactor; | |
4335 } | |
4336 | |
4337 Object* KeyAt(int entry) { return get(EntryToIndex(entry)); } | |
4338 | |
4339 // Returns the next entry for the given entry. | |
4340 int ChainAt(int entry) { | |
4341 return Smi::cast(get(EntryToIndex(entry) + kChainOffset))->value(); | |
4342 } | |
4343 | |
4344 int HashToBucket(int hash) { | |
4345 return hash & (NumberOfBuckets() - 1); | |
4346 } | |
4347 | |
4348 int HashToEntry(int hash) { | |
4349 int bucket = HashToBucket(hash); | |
4350 return Smi::cast(get(kHashTableStartIndex + bucket))->value(); | |
4351 } | |
4352 | |
4353 static const int kNumberOfBucketsIndex = 0; | |
4354 static const int kNumberOfElementsIndex = kNumberOfBucketsIndex + 1; | |
4355 static const int kNumberOfDeletedElementsIndex = kNumberOfElementsIndex + 1; | |
4356 static const int kHashTableStartIndex = kNumberOfDeletedElementsIndex + 1; | |
4357 | |
4358 static const int kEntrySize = entrysize + 1; | |
4359 static const int kChainOffset = entrysize; | |
4360 | |
4361 static const int kLoadFactor = 2; | |
4362 static const int kMaxCapacity = | |
4363 (FixedArray::kMaxLength - kHashTableStartIndex) | |
4364 / (1 + (kEntrySize * kLoadFactor)); | |
4365 }; | |
4366 | |
4367 | |
4368 class OrderedHashSet: public OrderedHashTable<1> { | |
4369 public: | |
4370 static OrderedHashSet* cast(Object* obj) { | |
4371 ASSERT(obj->IsFixedArray()); // TODO(adamk): Make a map for this | |
4372 return reinterpret_cast<OrderedHashSet*>(obj); | |
4373 } | |
4374 | |
4375 bool Contains(Object* key); | |
4376 static Handle<OrderedHashSet> Add( | |
4377 Handle<OrderedHashSet> table, Handle<Object> key); | |
4378 static Handle<OrderedHashSet> Remove( | |
4379 Handle<OrderedHashSet> table, Handle<Object> key); | |
4380 static Handle<OrderedHashSet> EnsureGrowable(Handle<OrderedHashSet> table); | |
4381 static Handle<OrderedHashSet> Shrink(Handle<OrderedHashSet> table); | |
4382 }; | |
4383 | |
4384 | |
4385 class OrderedHashMap: public OrderedHashTable<2> { | |
4386 public: | |
4387 static OrderedHashMap* cast(Object* obj) { | |
4388 ASSERT(obj->IsFixedArray()); // TODO(adamk): Make a map for this | |
4389 return reinterpret_cast<OrderedHashMap*>(obj); | |
4390 } | |
4391 | |
4392 Object* Lookup(Object* key); | |
4393 static Handle<OrderedHashMap> Put( | |
4394 Handle<OrderedHashMap> table, | |
4395 Handle<Object> key, | |
4396 Handle<Object> value); | |
4397 static Handle<OrderedHashMap> EnsureGrowable(Handle<OrderedHashMap> table); | |
4398 static Handle<OrderedHashMap> Shrink(Handle<OrderedHashMap> table); | |
4399 | |
4400 private: | |
4401 Object* ValueAt(int entry) { | |
4402 return get(EntryToIndex(entry) + kValueOffset); | |
4403 } | |
4404 | |
4405 static const int kValueOffset = 1; | |
4406 }; | |
4407 | |
4408 | |
4252 template <int entrysize> | 4409 template <int entrysize> |
4253 class WeakHashTableShape : public BaseShape<Object*> { | 4410 class WeakHashTableShape : public BaseShape<Object*> { |
4254 public: | 4411 public: |
4255 static inline bool IsMatch(Object* key, Object* other); | 4412 static inline bool IsMatch(Object* key, Object* other); |
4256 static inline uint32_t Hash(Object* key); | 4413 static inline uint32_t Hash(Object* key); |
4257 static inline uint32_t HashForObject(Object* key, Object* object); | 4414 static inline uint32_t HashForObject(Object* key, Object* object); |
4258 MUST_USE_RESULT static inline MaybeObject* AsObject(Heap* heap, | 4415 MUST_USE_RESULT static inline MaybeObject* AsObject(Heap* heap, |
4259 Object* key); | 4416 Object* key); |
4260 static const int kPrefixSize = 0; | 4417 static const int kPrefixSize = 0; |
4261 static const int kEntrySize = entrysize; | 4418 static const int kEntrySize = entrysize; |
(...skipping 6524 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
10786 } else { | 10943 } else { |
10787 value &= ~(1 << bit_position); | 10944 value &= ~(1 << bit_position); |
10788 } | 10945 } |
10789 return value; | 10946 return value; |
10790 } | 10947 } |
10791 }; | 10948 }; |
10792 | 10949 |
10793 } } // namespace v8::internal | 10950 } } // namespace v8::internal |
10794 | 10951 |
10795 #endif // V8_OBJECTS_H_ | 10952 #endif // V8_OBJECTS_H_ |
OLD | NEW |