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 |
69 // - JSWeakCollection | 71 // - JSWeakCollection |
70 // - JSWeakMap | 72 // - JSWeakMap |
71 // - JSWeakSet | 73 // - JSWeakSet |
72 // - JSRegExp | 74 // - JSRegExp |
73 // - JSFunction | 75 // - JSFunction |
74 // - JSGeneratorObject | 76 // - JSGeneratorObject |
75 // - JSModule | 77 // - JSModule |
76 // - GlobalObject | 78 // - GlobalObject |
77 // - JSGlobalObject | 79 // - JSGlobalObject |
78 // - JSBuiltinsObject | 80 // - JSBuiltinsObject |
(...skipping 359 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
438 V(JS_GLOBAL_OBJECT_TYPE) \ | 440 V(JS_GLOBAL_OBJECT_TYPE) \ |
439 V(JS_BUILTINS_OBJECT_TYPE) \ | 441 V(JS_BUILTINS_OBJECT_TYPE) \ |
440 V(JS_GLOBAL_PROXY_TYPE) \ | 442 V(JS_GLOBAL_PROXY_TYPE) \ |
441 V(JS_ARRAY_TYPE) \ | 443 V(JS_ARRAY_TYPE) \ |
442 V(JS_ARRAY_BUFFER_TYPE) \ | 444 V(JS_ARRAY_BUFFER_TYPE) \ |
443 V(JS_TYPED_ARRAY_TYPE) \ | 445 V(JS_TYPED_ARRAY_TYPE) \ |
444 V(JS_DATA_VIEW_TYPE) \ | 446 V(JS_DATA_VIEW_TYPE) \ |
445 V(JS_PROXY_TYPE) \ | 447 V(JS_PROXY_TYPE) \ |
446 V(JS_SET_TYPE) \ | 448 V(JS_SET_TYPE) \ |
447 V(JS_MAP_TYPE) \ | 449 V(JS_MAP_TYPE) \ |
| 450 V(JS_SET_ITERATOR_TYPE) \ |
| 451 V(JS_MAP_ITERATOR_TYPE) \ |
448 V(JS_WEAK_MAP_TYPE) \ | 452 V(JS_WEAK_MAP_TYPE) \ |
449 V(JS_WEAK_SET_TYPE) \ | 453 V(JS_WEAK_SET_TYPE) \ |
450 V(JS_REGEXP_TYPE) \ | 454 V(JS_REGEXP_TYPE) \ |
451 \ | 455 \ |
452 V(JS_FUNCTION_TYPE) \ | 456 V(JS_FUNCTION_TYPE) \ |
453 V(JS_FUNCTION_PROXY_TYPE) \ | 457 V(JS_FUNCTION_PROXY_TYPE) \ |
454 V(DEBUG_INFO_TYPE) \ | 458 V(DEBUG_INFO_TYPE) \ |
455 V(BREAK_POINT_INFO_TYPE) | 459 V(BREAK_POINT_INFO_TYPE) |
456 | 460 |
457 | 461 |
(...skipping 328 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
786 JS_MODULE_TYPE, | 790 JS_MODULE_TYPE, |
787 JS_GLOBAL_OBJECT_TYPE, | 791 JS_GLOBAL_OBJECT_TYPE, |
788 JS_BUILTINS_OBJECT_TYPE, | 792 JS_BUILTINS_OBJECT_TYPE, |
789 JS_GLOBAL_PROXY_TYPE, | 793 JS_GLOBAL_PROXY_TYPE, |
790 JS_ARRAY_TYPE, | 794 JS_ARRAY_TYPE, |
791 JS_ARRAY_BUFFER_TYPE, | 795 JS_ARRAY_BUFFER_TYPE, |
792 JS_TYPED_ARRAY_TYPE, | 796 JS_TYPED_ARRAY_TYPE, |
793 JS_DATA_VIEW_TYPE, | 797 JS_DATA_VIEW_TYPE, |
794 JS_SET_TYPE, | 798 JS_SET_TYPE, |
795 JS_MAP_TYPE, | 799 JS_MAP_TYPE, |
| 800 JS_SET_ITERATOR_TYPE, |
| 801 JS_MAP_ITERATOR_TYPE, |
796 JS_WEAK_MAP_TYPE, | 802 JS_WEAK_MAP_TYPE, |
797 JS_WEAK_SET_TYPE, | 803 JS_WEAK_SET_TYPE, |
798 | 804 |
799 JS_REGEXP_TYPE, | 805 JS_REGEXP_TYPE, |
800 | 806 |
801 JS_FUNCTION_TYPE, // LAST_JS_OBJECT_TYPE, LAST_JS_RECEIVER_TYPE | 807 JS_FUNCTION_TYPE, // LAST_JS_OBJECT_TYPE, LAST_JS_RECEIVER_TYPE |
802 | 808 |
803 // Pseudo-types | 809 // Pseudo-types |
804 FIRST_TYPE = 0x0, | 810 FIRST_TYPE = 0x0, |
805 LAST_TYPE = JS_FUNCTION_TYPE, | 811 LAST_TYPE = JS_FUNCTION_TYPE, |
(...skipping 227 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1033 V(Boolean) \ | 1039 V(Boolean) \ |
1034 V(JSArray) \ | 1040 V(JSArray) \ |
1035 V(JSArrayBuffer) \ | 1041 V(JSArrayBuffer) \ |
1036 V(JSArrayBufferView) \ | 1042 V(JSArrayBufferView) \ |
1037 V(JSTypedArray) \ | 1043 V(JSTypedArray) \ |
1038 V(JSDataView) \ | 1044 V(JSDataView) \ |
1039 V(JSProxy) \ | 1045 V(JSProxy) \ |
1040 V(JSFunctionProxy) \ | 1046 V(JSFunctionProxy) \ |
1041 V(JSSet) \ | 1047 V(JSSet) \ |
1042 V(JSMap) \ | 1048 V(JSMap) \ |
| 1049 V(JSSetIterator) \ |
| 1050 V(JSMapIterator) \ |
1043 V(JSWeakCollection) \ | 1051 V(JSWeakCollection) \ |
1044 V(JSWeakMap) \ | 1052 V(JSWeakMap) \ |
1045 V(JSWeakSet) \ | 1053 V(JSWeakSet) \ |
1046 V(JSRegExp) \ | 1054 V(JSRegExp) \ |
1047 V(HashTable) \ | 1055 V(HashTable) \ |
1048 V(Dictionary) \ | 1056 V(Dictionary) \ |
1049 V(StringTable) \ | 1057 V(StringTable) \ |
1050 V(JSFunctionResultCache) \ | 1058 V(JSFunctionResultCache) \ |
1051 V(NormalizedMapCache) \ | 1059 V(NormalizedMapCache) \ |
1052 V(CompilationCacheTable) \ | 1060 V(CompilationCacheTable) \ |
(...skipping 3263 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
4316 // equality operator and Object::GetHash() for the hash function. | 4324 // equality operator and Object::GetHash() for the hash function. |
4317 // | 4325 // |
4318 // Based on the "Deterministic Hash Table" as described by Jason Orendorff at | 4326 // Based on the "Deterministic Hash Table" as described by Jason Orendorff at |
4319 // https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables | 4327 // https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables |
4320 // Originally attributed to Tyler Close. | 4328 // Originally attributed to Tyler Close. |
4321 // | 4329 // |
4322 // Memory layout: | 4330 // Memory layout: |
4323 // [0]: bucket count | 4331 // [0]: bucket count |
4324 // [1]: element count | 4332 // [1]: element count |
4325 // [2]: deleted element count | 4333 // [2]: deleted element count |
4326 // [3..(NumberOfBuckets() - 1)]: "hash table", where each item is an offset | 4334 // [3]: live iterators (doubly-linked list) |
| 4335 // [4..(NumberOfBuckets() - 1)]: "hash table", where each item is an offset |
4327 // into the data table (see below) where the | 4336 // into the data table (see below) where the |
4328 // first item in this bucket is stored. | 4337 // first item in this bucket is stored. |
4329 // [3 + NumberOfBuckets()..length]: "data table", an array of length | 4338 // [4 + NumberOfBuckets()..length]: "data table", an array of length |
4330 // Capacity() * kEntrySize, where the first entrysize | 4339 // Capacity() * kEntrySize, where the first entrysize |
4331 // items are handled by the derived class and the | 4340 // items are handled by the derived class and the |
4332 // item at kChainOffset is another entry into the | 4341 // item at kChainOffset is another entry into the |
4333 // data table indicating the next entry in this hash | 4342 // data table indicating the next entry in this hash |
4334 // bucket. | 4343 // bucket. |
4335 template<class Derived, int entrysize> | 4344 template<class Derived, class Iterator, int entrysize> |
4336 class OrderedHashTable: public FixedArray { | 4345 class OrderedHashTable: public FixedArray { |
4337 public: | 4346 public: |
4338 // Returns an OrderedHashTable with a capacity of at least |capacity|. | 4347 // Returns an OrderedHashTable with a capacity of at least |capacity|. |
4339 static Handle<Derived> Allocate( | 4348 static Handle<Derived> Allocate( |
4340 Isolate* isolate, int capacity, PretenureFlag pretenure = NOT_TENURED); | 4349 Isolate* isolate, int capacity, PretenureFlag pretenure = NOT_TENURED); |
4341 | 4350 |
4342 // Returns an OrderedHashTable (possibly |table|) with enough space | 4351 // Returns an OrderedHashTable (possibly |table|) with enough space |
4343 // to add at least one new element. | 4352 // to add at least one new element. |
4344 static Handle<Derived> EnsureGrowable(Handle<Derived> table); | 4353 static Handle<Derived> EnsureGrowable(Handle<Derived> table); |
4345 | 4354 |
4346 // Returns an OrderedHashTable (possibly |table|) that's shrunken | 4355 // Returns an OrderedHashTable (possibly |table|) that's shrunken |
4347 // if possible. | 4356 // if possible. |
4348 static Handle<Derived> Shrink(Handle<Derived> table); | 4357 static Handle<Derived> Shrink(Handle<Derived> table); |
4349 | 4358 |
| 4359 // Returns a new empty OrderedHashTable and updates all the iterators to |
| 4360 // point to the new table. |
| 4361 static Handle<Derived> Clear(Handle<Derived> table); |
| 4362 |
4350 // Returns kNotFound if the key isn't present. | 4363 // Returns kNotFound if the key isn't present. |
4351 int FindEntry(Object* key); | 4364 int FindEntry(Object* key); |
4352 | 4365 |
4353 int NumberOfElements() { | 4366 int NumberOfElements() { |
4354 return Smi::cast(get(kNumberOfElementsIndex))->value(); | 4367 return Smi::cast(get(kNumberOfElementsIndex))->value(); |
4355 } | 4368 } |
4356 | 4369 |
4357 int NumberOfDeletedElements() { | 4370 int NumberOfDeletedElements() { |
4358 return Smi::cast(get(kNumberOfDeletedElementsIndex))->value(); | 4371 return Smi::cast(get(kNumberOfDeletedElementsIndex))->value(); |
4359 } | 4372 } |
4360 | 4373 |
| 4374 int UsedCapacity() { return NumberOfElements() + NumberOfDeletedElements(); } |
| 4375 |
4361 int NumberOfBuckets() { | 4376 int NumberOfBuckets() { |
4362 return Smi::cast(get(kNumberOfBucketsIndex))->value(); | 4377 return Smi::cast(get(kNumberOfBucketsIndex))->value(); |
4363 } | 4378 } |
4364 | 4379 |
| 4380 Object* iterators() { return get(kIteratorsIndex); } |
| 4381 |
| 4382 void set_iterators(Object* value) { set(kIteratorsIndex, value); } |
| 4383 |
4365 // Returns the index into the data table where the new entry | 4384 // Returns the index into the data table where the new entry |
4366 // should be placed. The table is assumed to have enough space | 4385 // should be placed. The table is assumed to have enough space |
4367 // for a new entry. | 4386 // for a new entry. |
4368 int AddEntry(int hash); | 4387 int AddEntry(int hash); |
4369 | 4388 |
4370 // Removes the entry, and puts the_hole in entrysize pointers | 4389 // Removes the entry, and puts the_hole in entrysize pointers |
4371 // (leaving the hash table chain intact). | 4390 // (leaving the hash table chain intact). |
4372 void RemoveEntry(int entry); | 4391 void RemoveEntry(int entry); |
4373 | 4392 |
4374 // Returns an index into |this| for the given entry. | 4393 // Returns an index into |this| for the given entry. |
4375 int EntryToIndex(int entry) { | 4394 int EntryToIndex(int entry) { |
4376 return kHashTableStartIndex + NumberOfBuckets() + (entry * kEntrySize); | 4395 return kHashTableStartIndex + NumberOfBuckets() + (entry * kEntrySize); |
4377 } | 4396 } |
4378 | 4397 |
| 4398 Object* KeyAt(int entry) { return get(EntryToIndex(entry)); } |
| 4399 |
4379 static const int kNotFound = -1; | 4400 static const int kNotFound = -1; |
| 4401 static const int kMinCapacity = 4; |
4380 | 4402 |
4381 private: | 4403 private: |
4382 static Handle<Derived> Rehash(Handle<Derived> table, int new_capacity); | 4404 static Handle<Derived> Rehash(Handle<Derived> table, int new_capacity); |
4383 | 4405 |
4384 void SetNumberOfBuckets(int num) { | 4406 void SetNumberOfBuckets(int num) { |
4385 set(kNumberOfBucketsIndex, Smi::FromInt(num)); | 4407 set(kNumberOfBucketsIndex, Smi::FromInt(num)); |
4386 } | 4408 } |
4387 | 4409 |
4388 void SetNumberOfElements(int num) { | 4410 void SetNumberOfElements(int num) { |
4389 set(kNumberOfElementsIndex, Smi::FromInt(num)); | 4411 set(kNumberOfElementsIndex, Smi::FromInt(num)); |
4390 } | 4412 } |
4391 | 4413 |
4392 void SetNumberOfDeletedElements(int num) { | 4414 void SetNumberOfDeletedElements(int num) { |
4393 set(kNumberOfDeletedElementsIndex, Smi::FromInt(num)); | 4415 set(kNumberOfDeletedElementsIndex, Smi::FromInt(num)); |
4394 } | 4416 } |
4395 | 4417 |
4396 int Capacity() { | 4418 int Capacity() { |
4397 return NumberOfBuckets() * kLoadFactor; | 4419 return NumberOfBuckets() * kLoadFactor; |
4398 } | 4420 } |
4399 | 4421 |
4400 Object* KeyAt(int entry) { return get(EntryToIndex(entry)); } | |
4401 | |
4402 // Returns the next entry for the given entry. | 4422 // Returns the next entry for the given entry. |
4403 int ChainAt(int entry) { | 4423 int ChainAt(int entry) { |
4404 return Smi::cast(get(EntryToIndex(entry) + kChainOffset))->value(); | 4424 return Smi::cast(get(EntryToIndex(entry) + kChainOffset))->value(); |
4405 } | 4425 } |
4406 | 4426 |
4407 int HashToBucket(int hash) { | 4427 int HashToBucket(int hash) { |
4408 return hash & (NumberOfBuckets() - 1); | 4428 return hash & (NumberOfBuckets() - 1); |
4409 } | 4429 } |
4410 | 4430 |
4411 int HashToEntry(int hash) { | 4431 int HashToEntry(int hash) { |
4412 int bucket = HashToBucket(hash); | 4432 int bucket = HashToBucket(hash); |
4413 return Smi::cast(get(kHashTableStartIndex + bucket))->value(); | 4433 return Smi::cast(get(kHashTableStartIndex + bucket))->value(); |
4414 } | 4434 } |
4415 | 4435 |
4416 static const int kNumberOfBucketsIndex = 0; | 4436 static const int kNumberOfBucketsIndex = 0; |
4417 static const int kNumberOfElementsIndex = kNumberOfBucketsIndex + 1; | 4437 static const int kNumberOfElementsIndex = kNumberOfBucketsIndex + 1; |
4418 static const int kNumberOfDeletedElementsIndex = kNumberOfElementsIndex + 1; | 4438 static const int kNumberOfDeletedElementsIndex = kNumberOfElementsIndex + 1; |
4419 static const int kHashTableStartIndex = kNumberOfDeletedElementsIndex + 1; | 4439 static const int kIteratorsIndex = kNumberOfDeletedElementsIndex + 1; |
| 4440 static const int kHashTableStartIndex = kIteratorsIndex + 1; |
4420 | 4441 |
4421 static const int kEntrySize = entrysize + 1; | 4442 static const int kEntrySize = entrysize + 1; |
4422 static const int kChainOffset = entrysize; | 4443 static const int kChainOffset = entrysize; |
4423 | 4444 |
4424 static const int kLoadFactor = 2; | 4445 static const int kLoadFactor = 2; |
4425 static const int kMaxCapacity = | 4446 static const int kMaxCapacity = |
4426 (FixedArray::kMaxLength - kHashTableStartIndex) | 4447 (FixedArray::kMaxLength - kHashTableStartIndex) |
4427 / (1 + (kEntrySize * kLoadFactor)); | 4448 / (1 + (kEntrySize * kLoadFactor)); |
4428 }; | 4449 }; |
4429 | 4450 |
4430 | 4451 |
4431 class OrderedHashSet: public OrderedHashTable<OrderedHashSet, 1> { | 4452 class JSSetIterator; |
| 4453 |
| 4454 |
| 4455 class OrderedHashSet: public OrderedHashTable< |
| 4456 OrderedHashSet, JSSetIterator, 1> { |
4432 public: | 4457 public: |
4433 static OrderedHashSet* cast(Object* obj) { | 4458 static OrderedHashSet* cast(Object* obj) { |
4434 ASSERT(obj->IsOrderedHashTable()); | 4459 ASSERT(obj->IsOrderedHashTable()); |
4435 return reinterpret_cast<OrderedHashSet*>(obj); | 4460 return reinterpret_cast<OrderedHashSet*>(obj); |
4436 } | 4461 } |
4437 | 4462 |
4438 bool Contains(Object* key); | 4463 bool Contains(Object* key); |
4439 static Handle<OrderedHashSet> Add( | 4464 static Handle<OrderedHashSet> Add( |
4440 Handle<OrderedHashSet> table, Handle<Object> key); | 4465 Handle<OrderedHashSet> table, Handle<Object> key); |
4441 static Handle<OrderedHashSet> Remove( | 4466 static Handle<OrderedHashSet> Remove( |
4442 Handle<OrderedHashSet> table, Handle<Object> key); | 4467 Handle<OrderedHashSet> table, Handle<Object> key); |
4443 }; | 4468 }; |
4444 | 4469 |
4445 | 4470 |
4446 class OrderedHashMap: public OrderedHashTable<OrderedHashMap, 2> { | 4471 class JSMapIterator; |
| 4472 |
| 4473 |
| 4474 class OrderedHashMap:public OrderedHashTable< |
| 4475 OrderedHashMap, JSMapIterator, 2> { |
4447 public: | 4476 public: |
4448 static OrderedHashMap* cast(Object* obj) { | 4477 static OrderedHashMap* cast(Object* obj) { |
4449 ASSERT(obj->IsOrderedHashTable()); | 4478 ASSERT(obj->IsOrderedHashTable()); |
4450 return reinterpret_cast<OrderedHashMap*>(obj); | 4479 return reinterpret_cast<OrderedHashMap*>(obj); |
4451 } | 4480 } |
4452 | 4481 |
4453 Object* Lookup(Object* key); | 4482 Object* Lookup(Object* key); |
4454 static Handle<OrderedHashMap> Put( | 4483 static Handle<OrderedHashMap> Put( |
4455 Handle<OrderedHashMap> table, | 4484 Handle<OrderedHashMap> table, |
4456 Handle<Object> key, | 4485 Handle<Object> key, |
(...skipping 3134 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
7591 static const int kContinuationOffset = kReceiverOffset + kPointerSize; | 7620 static const int kContinuationOffset = kReceiverOffset + kPointerSize; |
7592 static const int kOperandStackOffset = kContinuationOffset + kPointerSize; | 7621 static const int kOperandStackOffset = kContinuationOffset + kPointerSize; |
7593 static const int kStackHandlerIndexOffset = | 7622 static const int kStackHandlerIndexOffset = |
7594 kOperandStackOffset + kPointerSize; | 7623 kOperandStackOffset + kPointerSize; |
7595 static const int kSize = kStackHandlerIndexOffset + kPointerSize; | 7624 static const int kSize = kStackHandlerIndexOffset + kPointerSize; |
7596 | 7625 |
7597 // Resume mode, for use by runtime functions. | 7626 // Resume mode, for use by runtime functions. |
7598 enum ResumeMode { NEXT, THROW }; | 7627 enum ResumeMode { NEXT, THROW }; |
7599 | 7628 |
7600 // Yielding from a generator returns an object with the following inobject | 7629 // Yielding from a generator returns an object with the following inobject |
7601 // properties. See Context::generator_result_map() for the map. | 7630 // properties. See Context::iterator_result_map() for the map. |
7602 static const int kResultValuePropertyIndex = 0; | 7631 static const int kResultValuePropertyIndex = 0; |
7603 static const int kResultDonePropertyIndex = 1; | 7632 static const int kResultDonePropertyIndex = 1; |
7604 static const int kResultPropertyCount = 2; | 7633 static const int kResultPropertyCount = 2; |
7605 | 7634 |
7606 static const int kResultValuePropertyOffset = JSObject::kHeaderSize; | 7635 static const int kResultValuePropertyOffset = JSObject::kHeaderSize; |
7607 static const int kResultDonePropertyOffset = | 7636 static const int kResultDonePropertyOffset = |
7608 kResultValuePropertyOffset + kPointerSize; | 7637 kResultValuePropertyOffset + kPointerSize; |
7609 static const int kResultSize = kResultDonePropertyOffset + kPointerSize; | 7638 static const int kResultSize = kResultDonePropertyOffset + kPointerSize; |
7610 | 7639 |
7611 private: | 7640 private: |
(...skipping 2458 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
10070 DECLARE_VERIFIER(JSMap) | 10099 DECLARE_VERIFIER(JSMap) |
10071 | 10100 |
10072 static const int kTableOffset = JSObject::kHeaderSize; | 10101 static const int kTableOffset = JSObject::kHeaderSize; |
10073 static const int kSize = kTableOffset + kPointerSize; | 10102 static const int kSize = kTableOffset + kPointerSize; |
10074 | 10103 |
10075 private: | 10104 private: |
10076 DISALLOW_IMPLICIT_CONSTRUCTORS(JSMap); | 10105 DISALLOW_IMPLICIT_CONSTRUCTORS(JSMap); |
10077 }; | 10106 }; |
10078 | 10107 |
10079 | 10108 |
| 10109 // OrderedHashTableIterator is an iterator that iterates over the keys and |
| 10110 // values of an OrderedHashTable. |
| 10111 // |
| 10112 // The hash table has a reference to the iterator and the iterators themselves |
| 10113 // have references to the [next_iterator] and [previous_iterator], thus creating |
| 10114 // a double linked list. |
| 10115 // |
| 10116 // When the hash table changes the iterators are called to update their [index] |
| 10117 // and [count]. The hash table calls [EntryRemoved], [TableCompacted] as well |
| 10118 // as [TableCleared]. |
| 10119 // |
| 10120 // When an iterator is done it closes itself. It removes itself from the double |
| 10121 // linked list and it sets its [table] to undefined, no longer keeping the |
| 10122 // [table] alive. |
| 10123 template<class Derived, class TableType> |
| 10124 class OrderedHashTableIterator: public JSObject { |
| 10125 public: |
| 10126 // [table]: the backing hash table mapping keys to values. |
| 10127 DECL_ACCESSORS(table, Object) |
| 10128 |
| 10129 // [index]: The index into the data table. |
| 10130 DECL_ACCESSORS(index, Smi) |
| 10131 |
| 10132 // [count]: The logical index into the data table, ignoring the holes. |
| 10133 DECL_ACCESSORS(count, Smi) |
| 10134 |
| 10135 // [kind]: The kind of iteration this is. One of the [Kind] enum values. |
| 10136 DECL_ACCESSORS(kind, Smi) |
| 10137 |
| 10138 // [next_iterator]: Used as a double linked list for the live iterators. |
| 10139 DECL_ACCESSORS(next_iterator, Object) |
| 10140 |
| 10141 // [previous_iterator]: Used as a double linked list for the live iterators. |
| 10142 DECL_ACCESSORS(previous_iterator, Object) |
| 10143 |
| 10144 #ifdef OBJECT_PRINT |
| 10145 void OrderedHashTableIteratorPrint(FILE* out); |
| 10146 #endif |
| 10147 |
| 10148 static const int kTableOffset = JSObject::kHeaderSize; |
| 10149 static const int kIndexOffset = kTableOffset + kPointerSize; |
| 10150 static const int kCountOffset = kIndexOffset + kPointerSize; |
| 10151 static const int kKindOffset = kCountOffset + kPointerSize; |
| 10152 static const int kNextIteratorOffset = kKindOffset + kPointerSize; |
| 10153 static const int kPreviousIteratorOffset = kNextIteratorOffset + kPointerSize; |
| 10154 static const int kSize = kPreviousIteratorOffset + kPointerSize; |
| 10155 |
| 10156 enum Kind { |
| 10157 kKindKeys = 1, |
| 10158 kKindValues = 2, |
| 10159 kKindEntries = 3 |
| 10160 }; |
| 10161 |
| 10162 // Called by the underlying [table] when an entry is removed. |
| 10163 void EntryRemoved(int index); |
| 10164 |
| 10165 // Called by the underlying [table] when it is compacted/rehashed. |
| 10166 void TableCompacted() { |
| 10167 // All holes have been removed so index is now same as count. |
| 10168 set_index(count()); |
| 10169 } |
| 10170 |
| 10171 // Called by the underlying [table] when it is cleared. |
| 10172 void TableCleared() { |
| 10173 set_index(Smi::FromInt(0)); |
| 10174 set_count(Smi::FromInt(0)); |
| 10175 } |
| 10176 |
| 10177 // Removes the iterator from the double linked list and removes its reference |
| 10178 // back to the [table]. |
| 10179 void Close(); |
| 10180 |
| 10181 // Returns an iterator result object: {value: any, done: boolean} and moves |
| 10182 // the index to the next valid entry. Closes the iterator if moving past the |
| 10183 // end. |
| 10184 static Handle<JSObject> Next(Handle<Derived> iterator); |
| 10185 |
| 10186 protected: |
| 10187 static Handle<Derived> CreateInternal( |
| 10188 Handle<Map> map, Handle<TableType> table, int kind); |
| 10189 |
| 10190 private: |
| 10191 // Ensures [index] is not pointing to a hole. |
| 10192 void Seek(); |
| 10193 |
| 10194 // Moves [index] to next valid entry. Closes the iterator if moving past the |
| 10195 // end. |
| 10196 void MoveNext(); |
| 10197 |
| 10198 bool Closed() { |
| 10199 return table()->IsUndefined(); |
| 10200 } |
| 10201 |
| 10202 DISALLOW_IMPLICIT_CONSTRUCTORS(OrderedHashTableIterator); |
| 10203 }; |
| 10204 |
| 10205 |
| 10206 class JSSetIterator: public OrderedHashTableIterator<JSSetIterator, |
| 10207 OrderedHashSet> { |
| 10208 public: |
| 10209 // Creates a new iterator associated with [table]. |
| 10210 // [kind] needs to be one of the OrderedHashTableIterator Kind enum values. |
| 10211 static inline Handle<JSSetIterator> Create( |
| 10212 Handle<OrderedHashSet> table, int kind); |
| 10213 |
| 10214 // Dispatched behavior. |
| 10215 DECLARE_PRINTER(JSSetIterator) |
| 10216 DECLARE_VERIFIER(JSSetIterator) |
| 10217 |
| 10218 // Casting. |
| 10219 static inline JSSetIterator* cast(Object* obj); |
| 10220 |
| 10221 static Handle<Object> ValueForKind( |
| 10222 Handle<JSSetIterator> iterator, int entry_index); |
| 10223 |
| 10224 private: |
| 10225 DISALLOW_IMPLICIT_CONSTRUCTORS(JSSetIterator); |
| 10226 }; |
| 10227 |
| 10228 |
| 10229 class JSMapIterator: public OrderedHashTableIterator<JSMapIterator, |
| 10230 OrderedHashMap> { |
| 10231 public: |
| 10232 // Creates a new iterator associated with [table]. |
| 10233 // [kind] needs to be one of the OrderedHashTableIterator Kind enum values. |
| 10234 static inline Handle<JSMapIterator> Create( |
| 10235 Handle<OrderedHashMap> table, int kind); |
| 10236 |
| 10237 // Dispatched behavior. |
| 10238 DECLARE_PRINTER(JSMapIterator) |
| 10239 DECLARE_VERIFIER(JSMapIterator) |
| 10240 |
| 10241 // Casting. |
| 10242 static inline JSMapIterator* cast(Object* obj); |
| 10243 |
| 10244 static Handle<Object> ValueForKind( |
| 10245 Handle<JSMapIterator> iterator, int entry_index); |
| 10246 |
| 10247 private: |
| 10248 DISALLOW_IMPLICIT_CONSTRUCTORS(JSMapIterator); |
| 10249 }; |
| 10250 |
| 10251 |
10080 // Base class for both JSWeakMap and JSWeakSet | 10252 // Base class for both JSWeakMap and JSWeakSet |
10081 class JSWeakCollection: public JSObject { | 10253 class JSWeakCollection: public JSObject { |
10082 public: | 10254 public: |
10083 // [table]: the backing hash table mapping keys to values. | 10255 // [table]: the backing hash table mapping keys to values. |
10084 DECL_ACCESSORS(table, Object) | 10256 DECL_ACCESSORS(table, Object) |
10085 | 10257 |
10086 // [next]: linked list of encountered weak maps during GC. | 10258 // [next]: linked list of encountered weak maps during GC. |
10087 DECL_ACCESSORS(next, Object) | 10259 DECL_ACCESSORS(next, Object) |
10088 | 10260 |
10089 static const int kTableOffset = JSObject::kHeaderSize; | 10261 static const int kTableOffset = JSObject::kHeaderSize; |
(...skipping 1010 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
11100 } else { | 11272 } else { |
11101 value &= ~(1 << bit_position); | 11273 value &= ~(1 << bit_position); |
11102 } | 11274 } |
11103 return value; | 11275 return value; |
11104 } | 11276 } |
11105 }; | 11277 }; |
11106 | 11278 |
11107 } } // namespace v8::internal | 11279 } } // namespace v8::internal |
11108 | 11280 |
11109 #endif // V8_OBJECTS_H_ | 11281 #endif // V8_OBJECTS_H_ |
OLD | NEW |