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 48 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
59 // - HeapObject (superclass for everything allocated in the heap) | 59 // - HeapObject (superclass for everything allocated in the heap) |
60 // - JSReceiver (suitable for property access) | 60 // - JSReceiver (suitable for property access) |
61 // - JSObject | 61 // - JSObject |
62 // - JSArray | 62 // - JSArray |
63 // - JSArrayBuffer | 63 // - JSArrayBuffer |
64 // - JSArrayBufferView | 64 // - JSArrayBufferView |
65 // - JSTypedArray | 65 // - JSTypedArray |
66 // - JSDataView | 66 // - JSDataView |
67 // - JSSet | 67 // - JSSet |
68 // - JSMap | 68 // - JSMap |
69 // - JSSetIterator | |
70 // - JSMapIterator | |
71 // - JSWeakCollection | 69 // - JSWeakCollection |
72 // - JSWeakMap | 70 // - JSWeakMap |
73 // - JSWeakSet | 71 // - JSWeakSet |
74 // - JSRegExp | 72 // - JSRegExp |
75 // - JSFunction | 73 // - JSFunction |
76 // - JSGeneratorObject | 74 // - JSGeneratorObject |
77 // - JSModule | 75 // - JSModule |
78 // - GlobalObject | 76 // - GlobalObject |
79 // - JSGlobalObject | 77 // - JSGlobalObject |
80 // - JSBuiltinsObject | 78 // - JSBuiltinsObject |
(...skipping 359 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
440 V(JS_GLOBAL_OBJECT_TYPE) \ | 438 V(JS_GLOBAL_OBJECT_TYPE) \ |
441 V(JS_BUILTINS_OBJECT_TYPE) \ | 439 V(JS_BUILTINS_OBJECT_TYPE) \ |
442 V(JS_GLOBAL_PROXY_TYPE) \ | 440 V(JS_GLOBAL_PROXY_TYPE) \ |
443 V(JS_ARRAY_TYPE) \ | 441 V(JS_ARRAY_TYPE) \ |
444 V(JS_ARRAY_BUFFER_TYPE) \ | 442 V(JS_ARRAY_BUFFER_TYPE) \ |
445 V(JS_TYPED_ARRAY_TYPE) \ | 443 V(JS_TYPED_ARRAY_TYPE) \ |
446 V(JS_DATA_VIEW_TYPE) \ | 444 V(JS_DATA_VIEW_TYPE) \ |
447 V(JS_PROXY_TYPE) \ | 445 V(JS_PROXY_TYPE) \ |
448 V(JS_SET_TYPE) \ | 446 V(JS_SET_TYPE) \ |
449 V(JS_MAP_TYPE) \ | 447 V(JS_MAP_TYPE) \ |
450 V(JS_SET_ITERATOR_TYPE) \ | |
451 V(JS_MAP_ITERATOR_TYPE) \ | |
452 V(JS_WEAK_MAP_TYPE) \ | 448 V(JS_WEAK_MAP_TYPE) \ |
453 V(JS_WEAK_SET_TYPE) \ | 449 V(JS_WEAK_SET_TYPE) \ |
454 V(JS_REGEXP_TYPE) \ | 450 V(JS_REGEXP_TYPE) \ |
455 \ | 451 \ |
456 V(JS_FUNCTION_TYPE) \ | 452 V(JS_FUNCTION_TYPE) \ |
457 V(JS_FUNCTION_PROXY_TYPE) \ | 453 V(JS_FUNCTION_PROXY_TYPE) \ |
458 V(DEBUG_INFO_TYPE) \ | 454 V(DEBUG_INFO_TYPE) \ |
459 V(BREAK_POINT_INFO_TYPE) | 455 V(BREAK_POINT_INFO_TYPE) |
460 | 456 |
461 | 457 |
(...skipping 328 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
790 JS_MODULE_TYPE, | 786 JS_MODULE_TYPE, |
791 JS_GLOBAL_OBJECT_TYPE, | 787 JS_GLOBAL_OBJECT_TYPE, |
792 JS_BUILTINS_OBJECT_TYPE, | 788 JS_BUILTINS_OBJECT_TYPE, |
793 JS_GLOBAL_PROXY_TYPE, | 789 JS_GLOBAL_PROXY_TYPE, |
794 JS_ARRAY_TYPE, | 790 JS_ARRAY_TYPE, |
795 JS_ARRAY_BUFFER_TYPE, | 791 JS_ARRAY_BUFFER_TYPE, |
796 JS_TYPED_ARRAY_TYPE, | 792 JS_TYPED_ARRAY_TYPE, |
797 JS_DATA_VIEW_TYPE, | 793 JS_DATA_VIEW_TYPE, |
798 JS_SET_TYPE, | 794 JS_SET_TYPE, |
799 JS_MAP_TYPE, | 795 JS_MAP_TYPE, |
800 JS_SET_ITERATOR_TYPE, | |
801 JS_MAP_ITERATOR_TYPE, | |
802 JS_WEAK_MAP_TYPE, | 796 JS_WEAK_MAP_TYPE, |
803 JS_WEAK_SET_TYPE, | 797 JS_WEAK_SET_TYPE, |
804 | 798 |
805 JS_REGEXP_TYPE, | 799 JS_REGEXP_TYPE, |
806 | 800 |
807 JS_FUNCTION_TYPE, // LAST_JS_OBJECT_TYPE, LAST_JS_RECEIVER_TYPE | 801 JS_FUNCTION_TYPE, // LAST_JS_OBJECT_TYPE, LAST_JS_RECEIVER_TYPE |
808 | 802 |
809 // Pseudo-types | 803 // Pseudo-types |
810 FIRST_TYPE = 0x0, | 804 FIRST_TYPE = 0x0, |
811 LAST_TYPE = JS_FUNCTION_TYPE, | 805 LAST_TYPE = JS_FUNCTION_TYPE, |
(...skipping 240 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1052 V(Boolean) \ | 1046 V(Boolean) \ |
1053 V(JSArray) \ | 1047 V(JSArray) \ |
1054 V(JSArrayBuffer) \ | 1048 V(JSArrayBuffer) \ |
1055 V(JSArrayBufferView) \ | 1049 V(JSArrayBufferView) \ |
1056 V(JSTypedArray) \ | 1050 V(JSTypedArray) \ |
1057 V(JSDataView) \ | 1051 V(JSDataView) \ |
1058 V(JSProxy) \ | 1052 V(JSProxy) \ |
1059 V(JSFunctionProxy) \ | 1053 V(JSFunctionProxy) \ |
1060 V(JSSet) \ | 1054 V(JSSet) \ |
1061 V(JSMap) \ | 1055 V(JSMap) \ |
1062 V(JSSetIterator) \ | |
1063 V(JSMapIterator) \ | |
1064 V(JSWeakCollection) \ | 1056 V(JSWeakCollection) \ |
1065 V(JSWeakMap) \ | 1057 V(JSWeakMap) \ |
1066 V(JSWeakSet) \ | 1058 V(JSWeakSet) \ |
1067 V(JSRegExp) \ | 1059 V(JSRegExp) \ |
1068 V(HashTable) \ | 1060 V(HashTable) \ |
1069 V(Dictionary) \ | 1061 V(Dictionary) \ |
1070 V(StringTable) \ | 1062 V(StringTable) \ |
1071 V(JSFunctionResultCache) \ | 1063 V(JSFunctionResultCache) \ |
1072 V(NormalizedMapCache) \ | 1064 V(NormalizedMapCache) \ |
1073 V(CompilationCacheTable) \ | 1065 V(CompilationCacheTable) \ |
(...skipping 3242 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
4316 // equality operator and Object::GetHash() for the hash function. | 4308 // equality operator and Object::GetHash() for the hash function. |
4317 // | 4309 // |
4318 // Based on the "Deterministic Hash Table" as described by Jason Orendorff at | 4310 // Based on the "Deterministic Hash Table" as described by Jason Orendorff at |
4319 // https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables | 4311 // https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables |
4320 // Originally attributed to Tyler Close. | 4312 // Originally attributed to Tyler Close. |
4321 // | 4313 // |
4322 // Memory layout: | 4314 // Memory layout: |
4323 // [0]: bucket count | 4315 // [0]: bucket count |
4324 // [1]: element count | 4316 // [1]: element count |
4325 // [2]: deleted element count | 4317 // [2]: deleted element count |
4326 // [3]: live iterators (doubly-linked list) | 4318 // [3..(NumberOfBuckets() - 1)]: "hash table", where each item is an offset |
4327 // [4..(NumberOfBuckets() - 1)]: "hash table", where each item is an offset | |
4328 // into the data table (see below) where the | 4319 // into the data table (see below) where the |
4329 // first item in this bucket is stored. | 4320 // first item in this bucket is stored. |
4330 // [4 + NumberOfBuckets()..length]: "data table", an array of length | 4321 // [3 + NumberOfBuckets()..length]: "data table", an array of length |
4331 // Capacity() * kEntrySize, where the first entrysize | 4322 // Capacity() * kEntrySize, where the first entrysize |
4332 // items are handled by the derived class and the | 4323 // items are handled by the derived class and the |
4333 // item at kChainOffset is another entry into the | 4324 // item at kChainOffset is another entry into the |
4334 // data table indicating the next entry in this hash | 4325 // data table indicating the next entry in this hash |
4335 // bucket. | 4326 // bucket. |
4336 template<class Derived, class Iterator, int entrysize> | 4327 template<class Derived, int entrysize> |
4337 class OrderedHashTable: public FixedArray { | 4328 class OrderedHashTable: public FixedArray { |
4338 public: | 4329 public: |
4339 // Returns an OrderedHashTable with a capacity of at least |capacity|. | 4330 // Returns an OrderedHashTable with a capacity of at least |capacity|. |
4340 static Handle<Derived> Allocate( | 4331 static Handle<Derived> Allocate( |
4341 Isolate* isolate, int capacity, PretenureFlag pretenure = NOT_TENURED); | 4332 Isolate* isolate, int capacity, PretenureFlag pretenure = NOT_TENURED); |
4342 | 4333 |
4343 // Returns an OrderedHashTable (possibly |table|) with enough space | 4334 // Returns an OrderedHashTable (possibly |table|) with enough space |
4344 // to add at least one new element. | 4335 // to add at least one new element. |
4345 static Handle<Derived> EnsureGrowable(Handle<Derived> table); | 4336 static Handle<Derived> EnsureGrowable(Handle<Derived> table); |
4346 | 4337 |
4347 // Returns an OrderedHashTable (possibly |table|) that's shrunken | 4338 // Returns an OrderedHashTable (possibly |table|) that's shrunken |
4348 // if possible. | 4339 // if possible. |
4349 static Handle<Derived> Shrink(Handle<Derived> table); | 4340 static Handle<Derived> Shrink(Handle<Derived> table); |
4350 | 4341 |
4351 // Returns a new empty OrderedHashTable and updates all the iterators to | |
4352 // point to the new table. | |
4353 static Handle<Derived> Clear(Handle<Derived> table); | |
4354 | |
4355 // Returns kNotFound if the key isn't present. | 4342 // Returns kNotFound if the key isn't present. |
4356 int FindEntry(Object* key); | 4343 int FindEntry(Object* key); |
4357 | 4344 |
4358 int NumberOfElements() { | 4345 int NumberOfElements() { |
4359 return Smi::cast(get(kNumberOfElementsIndex))->value(); | 4346 return Smi::cast(get(kNumberOfElementsIndex))->value(); |
4360 } | 4347 } |
4361 | 4348 |
4362 int NumberOfDeletedElements() { | 4349 int NumberOfDeletedElements() { |
4363 return Smi::cast(get(kNumberOfDeletedElementsIndex))->value(); | 4350 return Smi::cast(get(kNumberOfDeletedElementsIndex))->value(); |
4364 } | 4351 } |
4365 | 4352 |
4366 int UsedCapacity() { return NumberOfElements() + NumberOfDeletedElements(); } | |
4367 | |
4368 int NumberOfBuckets() { | 4353 int NumberOfBuckets() { |
4369 return Smi::cast(get(kNumberOfBucketsIndex))->value(); | 4354 return Smi::cast(get(kNumberOfBucketsIndex))->value(); |
4370 } | 4355 } |
4371 | 4356 |
4372 Object* iterators() { return get(kIteratorsIndex); } | |
4373 | |
4374 void set_iterators(Object* value) { set(kIteratorsIndex, value); } | |
4375 | |
4376 // Returns the index into the data table where the new entry | 4357 // Returns the index into the data table where the new entry |
4377 // should be placed. The table is assumed to have enough space | 4358 // should be placed. The table is assumed to have enough space |
4378 // for a new entry. | 4359 // for a new entry. |
4379 int AddEntry(int hash); | 4360 int AddEntry(int hash); |
4380 | 4361 |
4381 // Removes the entry, and puts the_hole in entrysize pointers | 4362 // Removes the entry, and puts the_hole in entrysize pointers |
4382 // (leaving the hash table chain intact). | 4363 // (leaving the hash table chain intact). |
4383 void RemoveEntry(int entry); | 4364 void RemoveEntry(int entry); |
4384 | 4365 |
4385 // Returns an index into |this| for the given entry. | 4366 // Returns an index into |this| for the given entry. |
4386 int EntryToIndex(int entry) { | 4367 int EntryToIndex(int entry) { |
4387 return kHashTableStartIndex + NumberOfBuckets() + (entry * kEntrySize); | 4368 return kHashTableStartIndex + NumberOfBuckets() + (entry * kEntrySize); |
4388 } | 4369 } |
4389 | 4370 |
4390 Object* KeyAt(int entry) { return get(EntryToIndex(entry)); } | |
4391 | |
4392 static const int kNotFound = -1; | 4371 static const int kNotFound = -1; |
4393 static const int kMinCapacity = 4; | |
4394 | 4372 |
4395 private: | 4373 private: |
4396 static Handle<Derived> Rehash(Handle<Derived> table, int new_capacity); | 4374 static Handle<Derived> Rehash(Handle<Derived> table, int new_capacity); |
4397 | 4375 |
4398 void SetNumberOfBuckets(int num) { | 4376 void SetNumberOfBuckets(int num) { |
4399 set(kNumberOfBucketsIndex, Smi::FromInt(num)); | 4377 set(kNumberOfBucketsIndex, Smi::FromInt(num)); |
4400 } | 4378 } |
4401 | 4379 |
4402 void SetNumberOfElements(int num) { | 4380 void SetNumberOfElements(int num) { |
4403 set(kNumberOfElementsIndex, Smi::FromInt(num)); | 4381 set(kNumberOfElementsIndex, Smi::FromInt(num)); |
4404 } | 4382 } |
4405 | 4383 |
4406 void SetNumberOfDeletedElements(int num) { | 4384 void SetNumberOfDeletedElements(int num) { |
4407 set(kNumberOfDeletedElementsIndex, Smi::FromInt(num)); | 4385 set(kNumberOfDeletedElementsIndex, Smi::FromInt(num)); |
4408 } | 4386 } |
4409 | 4387 |
4410 int Capacity() { | 4388 int Capacity() { |
4411 return NumberOfBuckets() * kLoadFactor; | 4389 return NumberOfBuckets() * kLoadFactor; |
4412 } | 4390 } |
4413 | 4391 |
| 4392 Object* KeyAt(int entry) { return get(EntryToIndex(entry)); } |
| 4393 |
4414 // Returns the next entry for the given entry. | 4394 // Returns the next entry for the given entry. |
4415 int ChainAt(int entry) { | 4395 int ChainAt(int entry) { |
4416 return Smi::cast(get(EntryToIndex(entry) + kChainOffset))->value(); | 4396 return Smi::cast(get(EntryToIndex(entry) + kChainOffset))->value(); |
4417 } | 4397 } |
4418 | 4398 |
4419 int HashToBucket(int hash) { | 4399 int HashToBucket(int hash) { |
4420 return hash & (NumberOfBuckets() - 1); | 4400 return hash & (NumberOfBuckets() - 1); |
4421 } | 4401 } |
4422 | 4402 |
4423 int HashToEntry(int hash) { | 4403 int HashToEntry(int hash) { |
4424 int bucket = HashToBucket(hash); | 4404 int bucket = HashToBucket(hash); |
4425 return Smi::cast(get(kHashTableStartIndex + bucket))->value(); | 4405 return Smi::cast(get(kHashTableStartIndex + bucket))->value(); |
4426 } | 4406 } |
4427 | 4407 |
4428 static const int kNumberOfBucketsIndex = 0; | 4408 static const int kNumberOfBucketsIndex = 0; |
4429 static const int kNumberOfElementsIndex = kNumberOfBucketsIndex + 1; | 4409 static const int kNumberOfElementsIndex = kNumberOfBucketsIndex + 1; |
4430 static const int kNumberOfDeletedElementsIndex = kNumberOfElementsIndex + 1; | 4410 static const int kNumberOfDeletedElementsIndex = kNumberOfElementsIndex + 1; |
4431 static const int kIteratorsIndex = kNumberOfDeletedElementsIndex + 1; | 4411 static const int kHashTableStartIndex = kNumberOfDeletedElementsIndex + 1; |
4432 static const int kHashTableStartIndex = kIteratorsIndex + 1; | |
4433 | 4412 |
4434 static const int kEntrySize = entrysize + 1; | 4413 static const int kEntrySize = entrysize + 1; |
4435 static const int kChainOffset = entrysize; | 4414 static const int kChainOffset = entrysize; |
4436 | 4415 |
4437 static const int kLoadFactor = 2; | 4416 static const int kLoadFactor = 2; |
4438 static const int kMaxCapacity = | 4417 static const int kMaxCapacity = |
4439 (FixedArray::kMaxLength - kHashTableStartIndex) | 4418 (FixedArray::kMaxLength - kHashTableStartIndex) |
4440 / (1 + (kEntrySize * kLoadFactor)); | 4419 / (1 + (kEntrySize * kLoadFactor)); |
4441 }; | 4420 }; |
4442 | 4421 |
4443 | 4422 |
4444 class JSSetIterator; | 4423 class OrderedHashSet: public OrderedHashTable<OrderedHashSet, 1> { |
4445 | |
4446 | |
4447 class OrderedHashSet: public OrderedHashTable< | |
4448 OrderedHashSet, JSSetIterator, 1> { | |
4449 public: | 4424 public: |
4450 static OrderedHashSet* cast(Object* obj) { | 4425 static OrderedHashSet* cast(Object* obj) { |
4451 ASSERT(obj->IsOrderedHashTable()); | 4426 ASSERT(obj->IsOrderedHashTable()); |
4452 return reinterpret_cast<OrderedHashSet*>(obj); | 4427 return reinterpret_cast<OrderedHashSet*>(obj); |
4453 } | 4428 } |
4454 | 4429 |
4455 bool Contains(Object* key); | 4430 bool Contains(Object* key); |
4456 static Handle<OrderedHashSet> Add( | 4431 static Handle<OrderedHashSet> Add( |
4457 Handle<OrderedHashSet> table, Handle<Object> key); | 4432 Handle<OrderedHashSet> table, Handle<Object> key); |
4458 static Handle<OrderedHashSet> Remove( | 4433 static Handle<OrderedHashSet> Remove( |
4459 Handle<OrderedHashSet> table, Handle<Object> key); | 4434 Handle<OrderedHashSet> table, Handle<Object> key); |
4460 }; | 4435 }; |
4461 | 4436 |
4462 | 4437 |
4463 class JSMapIterator; | 4438 class OrderedHashMap: public OrderedHashTable<OrderedHashMap, 2> { |
4464 | |
4465 | |
4466 class OrderedHashMap:public OrderedHashTable< | |
4467 OrderedHashMap, JSMapIterator, 2> { | |
4468 public: | 4439 public: |
4469 static OrderedHashMap* cast(Object* obj) { | 4440 static OrderedHashMap* cast(Object* obj) { |
4470 ASSERT(obj->IsOrderedHashTable()); | 4441 ASSERT(obj->IsOrderedHashTable()); |
4471 return reinterpret_cast<OrderedHashMap*>(obj); | 4442 return reinterpret_cast<OrderedHashMap*>(obj); |
4472 } | 4443 } |
4473 | 4444 |
4474 Object* Lookup(Object* key); | 4445 Object* Lookup(Object* key); |
4475 static Handle<OrderedHashMap> Put( | 4446 static Handle<OrderedHashMap> Put( |
4476 Handle<OrderedHashMap> table, | 4447 Handle<OrderedHashMap> table, |
4477 Handle<Object> key, | 4448 Handle<Object> key, |
(...skipping 3118 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
7596 static const int kContinuationOffset = kReceiverOffset + kPointerSize; | 7567 static const int kContinuationOffset = kReceiverOffset + kPointerSize; |
7597 static const int kOperandStackOffset = kContinuationOffset + kPointerSize; | 7568 static const int kOperandStackOffset = kContinuationOffset + kPointerSize; |
7598 static const int kStackHandlerIndexOffset = | 7569 static const int kStackHandlerIndexOffset = |
7599 kOperandStackOffset + kPointerSize; | 7570 kOperandStackOffset + kPointerSize; |
7600 static const int kSize = kStackHandlerIndexOffset + kPointerSize; | 7571 static const int kSize = kStackHandlerIndexOffset + kPointerSize; |
7601 | 7572 |
7602 // Resume mode, for use by runtime functions. | 7573 // Resume mode, for use by runtime functions. |
7603 enum ResumeMode { NEXT, THROW }; | 7574 enum ResumeMode { NEXT, THROW }; |
7604 | 7575 |
7605 // Yielding from a generator returns an object with the following inobject | 7576 // Yielding from a generator returns an object with the following inobject |
7606 // properties. See Context::iterator_result_map() for the map. | 7577 // properties. See Context::generator_result_map() for the map. |
7607 static const int kResultValuePropertyIndex = 0; | 7578 static const int kResultValuePropertyIndex = 0; |
7608 static const int kResultDonePropertyIndex = 1; | 7579 static const int kResultDonePropertyIndex = 1; |
7609 static const int kResultPropertyCount = 2; | 7580 static const int kResultPropertyCount = 2; |
7610 | 7581 |
7611 static const int kResultValuePropertyOffset = JSObject::kHeaderSize; | 7582 static const int kResultValuePropertyOffset = JSObject::kHeaderSize; |
7612 static const int kResultDonePropertyOffset = | 7583 static const int kResultDonePropertyOffset = |
7613 kResultValuePropertyOffset + kPointerSize; | 7584 kResultValuePropertyOffset + kPointerSize; |
7614 static const int kResultSize = kResultDonePropertyOffset + kPointerSize; | 7585 static const int kResultSize = kResultDonePropertyOffset + kPointerSize; |
7615 | 7586 |
7616 private: | 7587 private: |
(...skipping 2450 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
10067 DECLARE_VERIFIER(JSMap) | 10038 DECLARE_VERIFIER(JSMap) |
10068 | 10039 |
10069 static const int kTableOffset = JSObject::kHeaderSize; | 10040 static const int kTableOffset = JSObject::kHeaderSize; |
10070 static const int kSize = kTableOffset + kPointerSize; | 10041 static const int kSize = kTableOffset + kPointerSize; |
10071 | 10042 |
10072 private: | 10043 private: |
10073 DISALLOW_IMPLICIT_CONSTRUCTORS(JSMap); | 10044 DISALLOW_IMPLICIT_CONSTRUCTORS(JSMap); |
10074 }; | 10045 }; |
10075 | 10046 |
10076 | 10047 |
10077 // OrderedHashTableIterator is an iterator that iterates over the keys and | |
10078 // values of an OrderedHashTable. | |
10079 // | |
10080 // The hash table has a reference to the iterator and the iterators themselves | |
10081 // have references to the [next_iterator] and [previous_iterator], thus creating | |
10082 // a double linked list. | |
10083 // | |
10084 // When the hash table changes the iterators are called to update their [index] | |
10085 // and [count]. The hash table calls [EntryRemoved], [TableCompacted] as well | |
10086 // as [TableCleared]. | |
10087 // | |
10088 // When an iterator is done it closes itself. It removes itself from the double | |
10089 // linked list and it sets its [table] to undefined, no longer keeping the | |
10090 // [table] alive. | |
10091 template<class Derived, class TableType> | |
10092 class OrderedHashTableIterator: public JSObject { | |
10093 public: | |
10094 // [table]: the backing hash table mapping keys to values. | |
10095 DECL_ACCESSORS(table, Object) | |
10096 | |
10097 // [index]: The index into the data table. | |
10098 DECL_ACCESSORS(index, Smi) | |
10099 | |
10100 // [count]: The logical index into the data table, ignoring the holes. | |
10101 DECL_ACCESSORS(count, Smi) | |
10102 | |
10103 // [kind]: The kind of iteration this is. One of the [Kind] enum values. | |
10104 DECL_ACCESSORS(kind, Smi) | |
10105 | |
10106 // [next_iterator]: Used as a double linked list for the live iterators. | |
10107 DECL_ACCESSORS(next_iterator, Object) | |
10108 | |
10109 // [previous_iterator]: Used as a double linked list for the live iterators. | |
10110 DECL_ACCESSORS(previous_iterator, Object) | |
10111 | |
10112 void OrderedHashTableIteratorPrint(FILE* out); | |
10113 | |
10114 static const int kTableOffset = JSObject::kHeaderSize; | |
10115 static const int kIndexOffset = kTableOffset + kPointerSize; | |
10116 static const int kCountOffset = kIndexOffset + kPointerSize; | |
10117 static const int kKindOffset = kCountOffset + kPointerSize; | |
10118 static const int kNextIteratorOffset = kKindOffset + kPointerSize; | |
10119 static const int kPreviousIteratorOffset = kNextIteratorOffset + kPointerSize; | |
10120 static const int kSize = kPreviousIteratorOffset + kPointerSize; | |
10121 | |
10122 enum Kind { | |
10123 kKindKeys = 1, | |
10124 kKindValues = 2, | |
10125 kKindEntries = 3 | |
10126 }; | |
10127 | |
10128 // Called by the underlying [table] when an entry is removed. | |
10129 void EntryRemoved(int index); | |
10130 | |
10131 // Called by the underlying [table] when it is compacted/rehashed. | |
10132 void TableCompacted() { | |
10133 // All holes have been removed so index is now same as count. | |
10134 set_index(count()); | |
10135 } | |
10136 | |
10137 // Called by the underlying [table] when it is cleared. | |
10138 void TableCleared() { | |
10139 set_index(Smi::FromInt(0)); | |
10140 set_count(Smi::FromInt(0)); | |
10141 } | |
10142 | |
10143 // Removes the iterator from the double linked list and removes its reference | |
10144 // back to the [table]. | |
10145 void Close(); | |
10146 | |
10147 // Returns an iterator result object: {value: any, done: boolean} and moves | |
10148 // the index to the next valid entry. Closes the iterator if moving past the | |
10149 // end. | |
10150 static Handle<JSObject> Next(Handle<Derived> iterator); | |
10151 | |
10152 protected: | |
10153 static Handle<Derived> CreateInternal( | |
10154 Handle<Map> map, Handle<TableType> table, int kind); | |
10155 | |
10156 private: | |
10157 // Ensures [index] is not pointing to a hole. | |
10158 void Seek(); | |
10159 | |
10160 // Moves [index] to next valid entry. Closes the iterator if moving past the | |
10161 // end. | |
10162 void MoveNext(); | |
10163 | |
10164 bool Closed() { | |
10165 return table()->IsUndefined(); | |
10166 } | |
10167 | |
10168 DISALLOW_IMPLICIT_CONSTRUCTORS(OrderedHashTableIterator); | |
10169 }; | |
10170 | |
10171 | |
10172 class JSSetIterator: public OrderedHashTableIterator<JSSetIterator, | |
10173 OrderedHashSet> { | |
10174 public: | |
10175 // Creates a new iterator associated with [table]. | |
10176 // [kind] needs to be one of the OrderedHashTableIterator Kind enum values. | |
10177 static Handle<JSSetIterator> Create(Handle<OrderedHashSet> table, int kind); | |
10178 | |
10179 // Dispatched behavior. | |
10180 DECLARE_PRINTER(JSSetIterator) | |
10181 DECLARE_VERIFIER(JSSetIterator) | |
10182 | |
10183 // Casting. | |
10184 static inline JSSetIterator* cast(Object* obj); | |
10185 | |
10186 static Handle<Object> ValueForKind( | |
10187 Handle<JSSetIterator> iterator, int entry_index); | |
10188 | |
10189 private: | |
10190 DISALLOW_IMPLICIT_CONSTRUCTORS(JSSetIterator); | |
10191 }; | |
10192 | |
10193 | |
10194 class JSMapIterator: public OrderedHashTableIterator<JSMapIterator, | |
10195 OrderedHashMap> { | |
10196 public: | |
10197 // Creates a new iterator associated with [table]. | |
10198 // [kind] needs to be one of the OrderedHashTableIterator Kind enum values. | |
10199 static Handle<JSMapIterator> Create(Handle<OrderedHashMap> table, int kind); | |
10200 | |
10201 // Dispatched behavior. | |
10202 DECLARE_PRINTER(JSMapIterator) | |
10203 DECLARE_VERIFIER(JSMapIterator) | |
10204 | |
10205 // Casting. | |
10206 static inline JSMapIterator* cast(Object* obj); | |
10207 | |
10208 static Handle<Object> ValueForKind( | |
10209 Handle<JSMapIterator> iterator, int entry_index); | |
10210 | |
10211 private: | |
10212 DISALLOW_IMPLICIT_CONSTRUCTORS(JSMapIterator); | |
10213 }; | |
10214 | |
10215 | |
10216 // Base class for both JSWeakMap and JSWeakSet | 10048 // Base class for both JSWeakMap and JSWeakSet |
10217 class JSWeakCollection: public JSObject { | 10049 class JSWeakCollection: public JSObject { |
10218 public: | 10050 public: |
10219 // [table]: the backing hash table mapping keys to values. | 10051 // [table]: the backing hash table mapping keys to values. |
10220 DECL_ACCESSORS(table, Object) | 10052 DECL_ACCESSORS(table, Object) |
10221 | 10053 |
10222 // [next]: linked list of encountered weak maps during GC. | 10054 // [next]: linked list of encountered weak maps during GC. |
10223 DECL_ACCESSORS(next, Object) | 10055 DECL_ACCESSORS(next, Object) |
10224 | 10056 |
10225 static const int kTableOffset = JSObject::kHeaderSize; | 10057 static const int kTableOffset = JSObject::kHeaderSize; |
(...skipping 1010 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
11236 } else { | 11068 } else { |
11237 value &= ~(1 << bit_position); | 11069 value &= ~(1 << bit_position); |
11238 } | 11070 } |
11239 return value; | 11071 return value; |
11240 } | 11072 } |
11241 }; | 11073 }; |
11242 | 11074 |
11243 } } // namespace v8::internal | 11075 } } // namespace v8::internal |
11244 | 11076 |
11245 #endif // V8_OBJECTS_H_ | 11077 #endif // V8_OBJECTS_H_ |
OLD | NEW |