Changeset 38016 in webkit for trunk/JavaScriptCore
- Timestamp:
- Oct 30, 2008, 5:12:50 PM (17 years ago)
- Location:
- trunk/JavaScriptCore
- Files:
-
- 1 deleted
- 12 edited
- 1 moved
-
ChangeLog (modified) (1 diff)
-
GNUmakefile.am (modified) (2 diffs)
-
JavaScriptCore.exp (modified) (3 diffs)
-
JavaScriptCore.pri (modified) (1 diff)
-
JavaScriptCore.vcproj/JavaScriptCore/JavaScriptCore.vcproj (modified) (1 diff)
-
JavaScriptCore.xcodeproj/project.pbxproj (modified) (7 diffs)
-
kjs/AllInOneFile.cpp (modified) (1 diff)
-
kjs/identifier.h (modified) (1 diff)
-
runtime/JSObject.cpp (modified) (1 diff)
-
runtime/JSObject.h (modified) (1 diff)
-
runtime/PropertyMap.cpp (deleted)
-
runtime/PropertyMapHashTable.h (moved) (moved from trunk/JavaScriptCore/runtime/PropertyMap.h ) (2 diffs)
-
runtime/StructureID.cpp (modified) (13 diffs)
-
runtime/StructureID.h (modified) (8 diffs)
Legend:
- Unmodified
- Added
- Removed
-
trunk/JavaScriptCore/ChangeLog
r38012 r38016 1 2008-10-30 Sam Weinig <[email protected]> 2 3 Reviewed by Cameron Zwarich and Geoffrey Garen. 4 5 Fix for https://bugs.webkit.org/show_bug.cgi?id=21989 6 Merge PropertyMap and StructureID 7 8 - Move PropertyMap code into StructureID in preparation for lazily 9 creating the map on gets. 10 - Make remove with transition explicit by adding removePropertyTransition. 11 - Make the put/remove without transition explicit. 12 - Make cache invalidation part of put/remove without transition. 13 14 1% speedup on SunSpider; 0.5% speedup on v8 suite. 15 16 * GNUmakefile.am: 17 * JavaScriptCore.exp: 18 * JavaScriptCore.pri: 19 * JavaScriptCore.vcproj/JavaScriptCore/JavaScriptCore.vcproj: 20 * JavaScriptCore.xcodeproj/project.pbxproj: 21 * JavaScriptCoreSources.bkl: 22 * kjs/AllInOneFile.cpp: 23 * kjs/identifier.h: 24 * runtime/JSObject.cpp: 25 (JSC::JSObject::removeDirect): 26 * runtime/JSObject.h: 27 (JSC::JSObject::putDirect): 28 * runtime/PropertyMap.cpp: Removed. 29 * runtime/PropertyMap.h: Removed. 30 * runtime/PropertyMapHashTable.h: Copied from runtime/PropertyMap.h. 31 * runtime/StructureID.cpp: 32 (JSC::StructureID::dumpStatistics): 33 (JSC::StructureID::StructureID): 34 (JSC::StructureID::~StructureID): 35 (JSC::StructureID::getEnumerablePropertyNames): 36 (JSC::StructureID::addPropertyTransition): 37 (JSC::StructureID::removePropertyTransition): 38 (JSC::StructureID::toDictionaryTransition): 39 (JSC::StructureID::changePrototypeTransition): 40 (JSC::StructureID::getterSetterTransition): 41 (JSC::StructureID::addPropertyWithoutTransition): 42 (JSC::StructureID::removePropertyWithoutTransition): 43 (JSC::PropertyMapStatisticsExitLogger::~PropertyMapStatisticsExitLogger): 44 (JSC::StructureID::checkConsistency): 45 (JSC::StructureID::copyPropertyTable): 46 (JSC::StructureID::get): 47 (JSC::StructureID::put): 48 (JSC::StructureID::remove): 49 (JSC::StructureID::insertIntoPropertyMapHashTable): 50 (JSC::StructureID::expandPropertyMapHashTable): 51 (JSC::StructureID::createPropertyMapHashTable): 52 (JSC::StructureID::rehashPropertyMapHashTable): 53 (JSC::comparePropertyMapEntryIndices): 54 (JSC::StructureID::getEnumerablePropertyNamesInternal): 55 * runtime/StructureID.h: 56 (JSC::StructureID::propertyStorageSize): 57 (JSC::StructureID::isEmpty): 58 (JSC::StructureID::get): 59 1 60 2008-10-30 Cameron Zwarich <[email protected]> 2 61 -
trunk/JavaScriptCore/GNUmakefile.am
r37985 r38016 219 219 JavaScriptCore/runtime/ObjectConstructor.h \ 220 220 JavaScriptCore/runtime/ObjectPrototype.h \ 221 JavaScriptCore/runtime/PropertyMap .h \221 JavaScriptCore/runtime/PropertyMapHashTable.h \ 222 222 JavaScriptCore/runtime/PropertySlot.h \ 223 223 JavaScriptCore/runtime/PrototypeFunction.h \ … … 376 376 JavaScriptCore/runtime/ObjectConstructor.cpp \ 377 377 JavaScriptCore/runtime/ObjectPrototype.cpp \ 378 JavaScriptCore/runtime/PropertyMap.cpp \379 378 JavaScriptCore/runtime/PropertySlot.cpp \ 380 379 JavaScriptCore/runtime/PrototypeFunction.cpp \ -
trunk/JavaScriptCore/JavaScriptCore.exp
r37989 r38016 110 110 __ZN3JSC11ProfileNode4sortEPFbRKN3WTF6RefPtrIS0_EES5_E 111 111 __ZN3JSC11ProgramNode6createEPNS_12JSGlobalDataEPNS_14SourceElementsEPN3WTF6VectorISt4pairINS_10IdentifierEjELm16EEEPNS6_INS5_6RefPtrINS_12FuncDeclNodeEEELm16EEERKNS_10SourceCodeEji 112 __ZN3JSC11PropertyMap3putERKNS_10IdentifierEj113 __ZN3JSC11PropertyMapD1Ev114 112 __ZN3JSC11StructureID17stopIgnoringLeaksEv 115 113 __ZN3JSC11StructureID18startIgnoringLeaksEv … … 119 117 __ZN3JSC11StructureID25changePrototypeTransitionEPS0_PNS_7JSValueE 120 118 __ZN3JSC11StructureID27growPropertyStorageCapacityEv 119 __ZN3JSC11StructureID28addPropertyWithoutTransitionERKNS_10IdentifierEj 121 120 __ZN3JSC11StructureIDC1EPNS_7JSValueERKNS_8TypeInfoE 122 121 __ZN3JSC11StructureIDD1Ev … … 304 303 __ZN3WTF8CollatorD1Ev 305 304 __ZN3WTF8fastFreeEPv 306 __ZNK3JSC11 PropertyMap3getERKNS_10IdentifierERj305 __ZNK3JSC11StructureID3getERKNS_10IdentifierERj 307 306 __ZNK3JSC12DateInstance7getTimeERdRi 308 307 __ZNK3JSC12StringObject12toThisStringEPNS_9ExecStateE -
trunk/JavaScriptCore/JavaScriptCore.pri
r37945 r38016 123 123 kjs/operations.cpp \ 124 124 kjs/Parser.cpp \ 125 runtime/PropertyMap.cpp \126 125 kjs/PropertyNameArray.cpp \ 127 126 runtime/PropertySlot.cpp \ -
trunk/JavaScriptCore/JavaScriptCore.vcproj/JavaScriptCore/JavaScriptCore.vcproj
r37985 r38016 750 750 </File> 751 751 <File 752 RelativePath="..\..\runtime\PropertyMap.cpp" 753 > 754 </File> 755 <File 756 RelativePath="..\..\runtime\PropertyMap.h" 752 RelativePath="..\..\runtime\PropertyMapHashTable.h" 757 753 > 758 754 </File> -
trunk/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
r37985 r38016 232 232 BC18C4510E16F5CD00B34460 /* ProfileNode.h in Headers */ = {isa = PBXBuildFile; fileRef = 95AB83550DA43B4400BC83F3 /* ProfileNode.h */; settings = {ATTRIBUTES = (Private, ); }; }; 233 233 BC18C4520E16F5CD00B34460 /* Profiler.h in Headers */ = {isa = PBXBuildFile; fileRef = 95AB832F0DA42CAD00BC83F3 /* Profiler.h */; settings = {ATTRIBUTES = (Private, ); }; }; 234 BC18C4530E16F5CD00B34460 /* PropertyMap.h in Headers */ = {isa = PBXBuildFile; fileRef = F692A87A0255597D01FF60F7 /* PropertyMap.h */; settings = {ATTRIBUTES = (Private, ); }; };235 234 BC18C4540E16F5CD00B34460 /* PropertyNameArray.h in Headers */ = {isa = PBXBuildFile; fileRef = 65400C100A69BAF200509887 /* PropertyNameArray.h */; settings = {ATTRIBUTES = (Private, ); }; }; 236 235 BC18C4550E16F5CD00B34460 /* PropertySlot.h in Headers */ = {isa = PBXBuildFile; fileRef = 65621E6C089E859700760F35 /* PropertySlot.h */; settings = {ATTRIBUTES = (Private, ); }; }; … … 284 283 BC7F8FB90E19D1C3008632C0 /* JSNumberCell.h in Headers */ = {isa = PBXBuildFile; fileRef = BC7F8FB80E19D1C3008632C0 /* JSNumberCell.h */; settings = {ATTRIBUTES = (Private, ); }; }; 285 284 BC9041480EB9250900FE26FA /* StructureIDTransitionTable.h in Headers */ = {isa = PBXBuildFile; fileRef = BC9041470EB9250900FE26FA /* StructureIDTransitionTable.h */; settings = {ATTRIBUTES = (Private, ); }; }; 285 BC95437D0EBA70FD0072B6D3 /* PropertyMapHashTable.h in Headers */ = {isa = PBXBuildFile; fileRef = BC95437C0EBA70FD0072B6D3 /* PropertyMapHashTable.h */; settings = {ATTRIBUTES = (Private, ); }; }; 286 286 BCD202C20E1706A7002C7E82 /* RegExpConstructor.h in Headers */ = {isa = PBXBuildFile; fileRef = BCD202BE0E1706A7002C7E82 /* RegExpConstructor.h */; }; 287 287 BCD202C40E1706A7002C7E82 /* RegExpPrototype.h in Headers */ = {isa = PBXBuildFile; fileRef = BCD202C00E1706A7002C7E82 /* RegExpPrototype.h */; }; … … 657 657 BC8F3CCF0DAF17BA00577A80 /* ConstructData.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ConstructData.h; sourceTree = "<group>"; }; 658 658 BC9041470EB9250900FE26FA /* StructureIDTransitionTable.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = StructureIDTransitionTable.h; sourceTree = "<group>"; }; 659 BC95437C0EBA70FD0072B6D3 /* PropertyMapHashTable.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = PropertyMapHashTable.h; sourceTree = "<group>"; }; 659 660 BC9BB95B0E19680600DF8855 /* InternalFunction.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = InternalFunction.cpp; sourceTree = "<group>"; }; 660 661 BCA62DFE0E2826230004F30D /* CallData.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CallData.cpp; sourceTree = "<group>"; }; … … 729 730 F692A8770255597D01FF60F7 /* operations.cpp */ = {isa = PBXFileReference; fileEncoding = 30; indentWidth = 4; lastKnownFileType = sourcecode.cpp.cpp; path = operations.cpp; sourceTree = "<group>"; tabWidth = 8; }; 730 731 F692A8780255597D01FF60F7 /* operations.h */ = {isa = PBXFileReference; fileEncoding = 30; indentWidth = 4; lastKnownFileType = sourcecode.c.h; path = operations.h; sourceTree = "<group>"; tabWidth = 8; }; 731 F692A8790255597D01FF60F7 /* PropertyMap.cpp */ = {isa = PBXFileReference; fileEncoding = 30; indentWidth = 4; lastKnownFileType = sourcecode.cpp.cpp; path = PropertyMap.cpp; sourceTree = "<group>"; tabWidth = 8; };732 F692A87A0255597D01FF60F7 /* PropertyMap.h */ = {isa = PBXFileReference; fileEncoding = 30; indentWidth = 4; lastKnownFileType = sourcecode.c.h; path = PropertyMap.h; sourceTree = "<group>"; tabWidth = 8; };733 732 F692A87B0255597D01FF60F7 /* RegExpObject.cpp */ = {isa = PBXFileReference; fileEncoding = 30; indentWidth = 4; lastKnownFileType = sourcecode.cpp.cpp; path = RegExpObject.cpp; sourceTree = "<group>"; tabWidth = 8; }; 734 733 F692A87C0255597D01FF60F7 /* RegExpObject.h */ = {isa = PBXFileReference; fileEncoding = 30; indentWidth = 4; lastKnownFileType = sourcecode.c.h; path = RegExpObject.h; sourceTree = "<group>"; tabWidth = 8; }; … … 1246 1245 BC2680C80E16D4E900A06E92 /* ObjectPrototype.cpp */, 1247 1246 BC2680C90E16D4E900A06E92 /* ObjectPrototype.h */, 1248 F692A8790255597D01FF60F7 /* PropertyMap.cpp */, 1249 F692A87A0255597D01FF60F7 /* PropertyMap.h */, 1247 BC95437C0EBA70FD0072B6D3 /* PropertyMapHashTable.h */, 1250 1248 65621E6B089E859700760F35 /* PropertySlot.cpp */, 1251 1249 65621E6C089E859700760F35 /* PropertySlot.h */, … … 1463 1461 BC18C4510E16F5CD00B34460 /* ProfileNode.h in Headers */, 1464 1462 BC18C4520E16F5CD00B34460 /* Profiler.h in Headers */, 1465 BC18C4530E16F5CD00B34460 /* PropertyMap.h in Headers */,1466 1463 BC18C4540E16F5CD00B34460 /* PropertyNameArray.h in Headers */, 1467 1464 BC18C4550E16F5CD00B34460 /* PropertySlot.h in Headers */, … … 1552 1549 14F3488F0E95EF8A003648BC /* CollectorHeapIterator.h in Headers */, 1553 1550 BC9041480EB9250900FE26FA /* StructureIDTransitionTable.h in Headers */, 1551 BC95437D0EBA70FD0072B6D3 /* PropertyMapHashTable.h in Headers */, 1554 1552 ); 1555 1553 runOnlyForDeploymentPostprocessing = 0; -
trunk/JavaScriptCore/kjs/AllInOneFile.cpp
r37938 r38016 86 86 #include "operations.cpp" 87 87 #include "Parser.cpp" 88 #include "runtime/PropertyMap.cpp"89 88 #include "runtime/PropertySlot.cpp" 90 89 #include "PropertyNameArray.cpp" -
trunk/JavaScriptCore/kjs/identifier.h
r36291 r38016 30 30 31 31 class Identifier { 32 friend class PropertyMap;32 friend class StructureID; 33 33 public: 34 34 Identifier() { } -
trunk/JavaScriptCore/runtime/JSObject.cpp
r37989 r38016 468 468 size_t offset; 469 469 if (m_structureID->isDictionary()) { 470 offset = m_structureID->remove (propertyName);471 if (offset != WTF::notFound) {470 offset = m_structureID->removePropertyWithoutTransition(propertyName); 471 if (offset != WTF::notFound) 472 472 m_propertyStorage[offset] = jsUndefined(); 473 m_structureID->clearEnumerationCache();474 }475 473 return; 476 474 } 477 475 478 RefPtr<StructureID> structureID = StructureID::toDictionaryTransition(m_structureID); 479 offset = structureID->remove(propertyName); 476 RefPtr<StructureID> structureID = StructureID::removePropertyTransition(m_structureID, propertyName, offset); 480 477 if (offset != WTF::notFound) 481 478 m_propertyStorage[offset] = jsUndefined(); -
trunk/JavaScriptCore/runtime/JSObject.h
r37989 r38016 400 400 401 401 size_t currentCapacity = m_structureID->propertyStorageCapacity(); 402 offset = m_structureID->put(propertyName, attributes); 403 if (m_structureID->propertyStorageSize() > m_structureID->propertyStorageCapacity()) { 404 m_structureID->growPropertyStorageCapacity(); 402 offset = m_structureID->addPropertyWithoutTransition(propertyName, attributes); 403 if (currentCapacity != m_structureID->propertyStorageCapacity()) 405 404 allocatePropertyStorage(currentCapacity, m_structureID->propertyStorageCapacity()); 406 } 407 405 406 ASSERT(offset < m_structureID->propertyStorageCapacity()); 408 407 m_propertyStorage[offset] = value; 409 408 slot.setNewProperty(this, offset); 410 m_structureID->clearEnumerationCache();411 409 return; 412 410 } -
trunk/JavaScriptCore/runtime/PropertyMapHashTable.h
r37989 r38016 19 19 */ 20 20 21 #ifndef PropertyMap _h22 #define PropertyMap _h21 #ifndef PropertyMapHashTable_h 22 #define PropertyMapHashTable_h 23 23 24 #include "PropertySlot.h" 25 #include "identifier.h" 26 #include <wtf/OwnArrayPtr.h> 27 #include <wtf/NotFound.h> 28 29 #ifndef NDEBUG 30 #define DUMP_PROPERTYMAP_STATS 0 31 #else 32 #define DUMP_PROPERTYMAP_STATS 0 33 #endif 24 #include "ustring.h" 34 25 35 26 namespace JSC { 36 37 class JSObject;38 class PropertyNameArray;39 40 typedef JSValue** PropertyStorage;41 27 42 28 struct PropertyMapEntry { … … 87 73 }; 88 74 89 class PropertyMap {90 public:91 PropertyMap();92 ~PropertyMap();93 94 PropertyMap& operator=(const PropertyMap&);95 96 size_t get(const Identifier& propertyName) const;97 size_t get(const Identifier& propertyName, unsigned& attributes) const;98 size_t put(const Identifier& propertyName, unsigned attributes);99 size_t remove(const Identifier& propertyName);100 101 void getEnumerablePropertyNames(PropertyNameArray&) const;102 103 bool isEmpty() const { return !m_table; }104 unsigned storageSize() const { return m_table ? m_table->keyCount + m_deletedOffsets.size() : 0; }105 106 size_t propertyMapSize() const107 {108 return sizeof(PropertyMap) + (m_table ? PropertyMapHashTable::allocationSize(m_table->size) : 0);109 }110 111 static const unsigned emptyEntryIndex = 0;112 113 private:114 typedef PropertyMapEntry Entry;115 typedef PropertyMapHashTable Table;116 117 void expand();118 void rehash();119 void rehash(unsigned newTableSize);120 void createTable();121 122 void insert(const Entry&);123 124 void checkConsistency();125 126 Table* m_table;127 Vector<unsigned> m_deletedOffsets;128 };129 130 inline PropertyMap::PropertyMap()131 : m_table(0)132 {133 }134 135 inline size_t PropertyMap::get(const Identifier& propertyName) const136 {137 ASSERT(!propertyName.isNull());138 139 if (!m_table)140 return WTF::notFound;141 142 UString::Rep* rep = propertyName._ustring.rep();143 144 unsigned i = rep->computedHash();145 146 #if DUMP_PROPERTYMAP_STATS147 ++numProbes;148 #endif149 150 unsigned entryIndex = m_table->entryIndices[i & m_table->sizeMask];151 if (entryIndex == emptyEntryIndex)152 return WTF::notFound;153 154 if (rep == m_table->entries()[entryIndex - 1].key)155 return m_table->entries()[entryIndex - 1].offset;156 157 #if DUMP_PROPERTYMAP_STATS158 ++numCollisions;159 #endif160 161 unsigned k = 1 | WTF::doubleHash(rep->computedHash());162 163 while (1) {164 i += k;165 166 #if DUMP_PROPERTYMAP_STATS167 ++numRehashes;168 #endif169 170 entryIndex = m_table->entryIndices[i & m_table->sizeMask];171 if (entryIndex == emptyEntryIndex)172 return WTF::notFound;173 174 if (rep == m_table->entries()[entryIndex - 1].key)175 return m_table->entries()[entryIndex - 1].offset;176 }177 }178 179 75 } // namespace JSC 180 76 181 #endif // PropertyMap _h77 #endif // PropertyMapHashTable_h -
trunk/JavaScriptCore/runtime/StructureID.cpp
r37989 r38016 38 38 #endif 39 39 40 #ifndef NDEBUG 41 #define DO_PROPERTYMAP_CONSTENCY_CHECK 0 42 #else 43 #define DO_PROPERTYMAP_CONSTENCY_CHECK 0 44 #endif 45 40 46 using namespace std; 47 using WTF::doubleHash; 41 48 42 49 namespace JSC { 50 51 // Choose a number for the following so that most property maps are smaller, 52 // but it's not going to blow out the stack to allocate this number of pointers. 53 static const int smallMapThreshold = 1024; 54 55 // The point at which the function call overhead of the qsort implementation 56 // becomes small compared to the inefficiency of insertion sort. 57 static const unsigned tinyMapThreshold = 20; 43 58 44 59 #ifndef NDEBUG … … 76 91 } 77 92 78 totalPropertyMapsSize += structureID->m_propertyMap.propertyMapSize(); 93 if (structureID->m_propertyTable) 94 totalPropertyMapsSize += PropertyMapHashTable::allocationSize(m_propertyTable->size);; 79 95 } 80 96 … … 97 113 , m_nameInPrevious(0) 98 114 , m_transitionCount(0) 115 , m_propertyTable(0) 99 116 , m_propertyStorageCapacity(JSObject::inlineStorageCapacity) 100 117 , m_cachedTransistionOffset(WTF::notFound) … … 141 158 delete m_transitions.table; 142 159 160 if (m_propertyTable) { 161 unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount; 162 for (unsigned i = 1; i <= entryCount; i++) { 163 if (UString::Rep* key = m_propertyTable->entries()[i].key) 164 key->deref(); 165 } 166 fastFree(m_propertyTable); 167 } 168 143 169 #ifndef NDEBUG 144 170 #if ENABLE(JSC_MULTIPLE_THREADS) … … 185 211 } 186 212 187 m_propertyMap.getEnumerablePropertyNames(propertyNames);213 getEnumerablePropertyNamesInternal(propertyNames); 188 214 189 215 // Add properties from the static hashtables of properties … … 256 282 if (structureID->m_transitionCount > s_maxTransitionLength) { 257 283 RefPtr<StructureID> transition = toDictionaryTransition(structureID); 258 offset = transition-> m_propertyMap.put(propertyName, attributes);259 if (transition-> m_propertyMap.storageSize() > transition->propertyStorageCapacity())284 offset = transition->put(propertyName, attributes); 285 if (transition->propertyStorageSize() > transition->propertyStorageCapacity()) 260 286 transition->growPropertyStorageCapacity(); 261 287 return transition.release(); … … 268 294 transition->m_attributesInPrevious = attributes; 269 295 transition->m_transitionCount = structureID->m_transitionCount + 1; 270 transition->m_propertyMap = structureID->m_propertyMap; 296 transition->m_propertyTable = structureID->copyPropertyTable(); 297 transition->m_deletedOffsets = structureID->m_deletedOffsets; 271 298 transition->m_propertyStorageCapacity = structureID->m_propertyStorageCapacity; 272 299 transition->m_hasGetterSetterProperties = structureID->m_hasGetterSetterProperties; 273 300 274 offset = transition-> m_propertyMap.put(propertyName, attributes);275 if (transition-> m_propertyMap.storageSize() > transition->propertyStorageCapacity())301 offset = transition->put(propertyName, attributes); 302 if (transition->propertyStorageSize() > transition->propertyStorageCapacity()) 276 303 transition->growPropertyStorageCapacity(); 277 304 … … 294 321 } 295 322 296 PassRefPtr<StructureID> StructureID:: toDictionaryTransition(StructureID* structureID)323 PassRefPtr<StructureID> StructureID::removePropertyTransition(StructureID* structureID, const Identifier& propertyName, size_t& offset) 297 324 { 298 325 ASSERT(!structureID->m_isDictionary); … … 300 327 RefPtr<StructureID> transition = create(structureID->m_prototype, structureID->typeInfo()); 301 328 transition->m_isDictionary = true; 302 transition->m_propertyMap = structureID->m_propertyMap; 329 transition->m_propertyTable = structureID->copyPropertyTable(); 330 transition->m_deletedOffsets = structureID->m_deletedOffsets; 331 transition->m_propertyStorageCapacity = structureID->m_propertyStorageCapacity; 332 transition->m_hasGetterSetterProperties = structureID->m_hasGetterSetterProperties; 333 334 offset = transition->remove(propertyName); 335 336 return transition.release(); 337 } 338 339 PassRefPtr<StructureID> StructureID::toDictionaryTransition(StructureID* structureID) 340 { 341 ASSERT(!structureID->m_isDictionary); 342 343 RefPtr<StructureID> transition = create(structureID->m_prototype, structureID->typeInfo()); 344 transition->m_isDictionary = true; 345 transition->m_propertyTable = structureID->copyPropertyTable(); 346 transition->m_deletedOffsets = structureID->m_deletedOffsets; 303 347 transition->m_propertyStorageCapacity = structureID->m_propertyStorageCapacity; 304 348 transition->m_hasGetterSetterProperties = structureID->m_hasGetterSetterProperties; … … 321 365 RefPtr<StructureID> transition = create(prototype, structureID->typeInfo()); 322 366 transition->m_transitionCount = structureID->m_transitionCount + 1; 323 transition->m_propertyMap = structureID->m_propertyMap; 367 transition->m_propertyTable = structureID->copyPropertyTable(); 368 transition->m_deletedOffsets = structureID->m_deletedOffsets; 324 369 transition->m_propertyStorageCapacity = structureID->m_propertyStorageCapacity; 325 370 transition->m_hasGetterSetterProperties = structureID->m_hasGetterSetterProperties; … … 331 376 RefPtr<StructureID> transition = create(structureID->storedPrototype(), structureID->typeInfo()); 332 377 transition->m_transitionCount = structureID->m_transitionCount + 1; 333 transition->m_propertyMap = structureID->m_propertyMap; 378 transition->m_propertyTable = structureID->copyPropertyTable(); 379 transition->m_deletedOffsets = structureID->m_deletedOffsets; 334 380 transition->m_propertyStorageCapacity = structureID->m_propertyStorageCapacity; 335 381 transition->m_hasGetterSetterProperties = transition->m_hasGetterSetterProperties; … … 339 385 size_t StructureID::addPropertyWithoutTransition(const Identifier& propertyName, unsigned attributes) 340 386 { 341 size_t offset = m_propertyMap.put(propertyName, attributes);342 if ( m_propertyMap.storageSize() > propertyStorageCapacity())387 size_t offset = put(propertyName, attributes); 388 if (propertyStorageSize() > propertyStorageCapacity()) 343 389 growPropertyStorageCapacity(); 390 clearEnumerationCache(); 391 return offset; 392 } 393 394 size_t StructureID::removePropertyWithoutTransition(const Identifier& propertyName) 395 { 396 size_t offset = remove(propertyName); 397 clearEnumerationCache(); 344 398 return offset; 345 399 } … … 358 412 return cachedPrototypeChain(); 359 413 } 414 415 #if DUMP_PROPERTYMAP_STATS 416 417 static int numProbes; 418 static int numCollisions; 419 static int numRehashes; 420 static int numRemoves; 421 422 struct PropertyMapStatisticsExitLogger { 423 ~PropertyMapStatisticsExitLogger(); 424 }; 425 426 static PropertyMapStatisticsExitLogger logger; 427 428 PropertyMapStatisticsExitLogger::~PropertyMapStatisticsExitLogger() 429 { 430 printf("\nJSC::PropertyMap statistics\n\n"); 431 printf("%d probes\n", numProbes); 432 printf("%d collisions (%.1f%%)\n", numCollisions, 100.0 * numCollisions / numProbes); 433 printf("%d rehashes\n", numRehashes); 434 printf("%d removes\n", numRemoves); 435 } 436 437 #endif 438 439 static const unsigned deletedSentinelIndex = 1; 440 441 #if !DO_PROPERTYMAP_CONSTENCY_CHECK 442 443 inline void StructureID::checkConsistency() 444 { 445 } 446 447 #endif 448 449 PropertyMapHashTable* StructureID::copyPropertyTable() 450 { 451 if (!m_propertyTable) 452 return 0; 453 454 size_t tableSize = PropertyMapHashTable::allocationSize(m_propertyTable->size); 455 PropertyMapHashTable* newTable = static_cast<PropertyMapHashTable*>(fastMalloc(tableSize)); 456 memcpy(newTable, m_propertyTable, tableSize); 457 458 unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount; 459 for (unsigned i = 1; i <= entryCount; ++i) { 460 if (UString::Rep* key = newTable->entries()[i].key) 461 key->ref(); 462 } 463 464 return newTable; 465 } 466 467 size_t StructureID::get(const Identifier& propertyName, unsigned& attributes) const 468 { 469 ASSERT(!propertyName.isNull()); 470 471 if (!m_propertyTable) 472 return WTF::notFound; 473 474 UString::Rep* rep = propertyName._ustring.rep(); 475 476 unsigned i = rep->computedHash(); 477 478 #if DUMP_PROPERTYMAP_STATS 479 ++numProbes; 480 #endif 481 482 unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask]; 483 if (entryIndex == emptyEntryIndex) 484 return WTF::notFound; 485 486 if (rep == m_propertyTable->entries()[entryIndex - 1].key) { 487 attributes = m_propertyTable->entries()[entryIndex - 1].attributes; 488 return m_propertyTable->entries()[entryIndex - 1].offset; 489 } 490 491 #if DUMP_PROPERTYMAP_STATS 492 ++numCollisions; 493 #endif 494 495 unsigned k = 1 | doubleHash(rep->computedHash()); 496 497 while (1) { 498 i += k; 499 500 #if DUMP_PROPERTYMAP_STATS 501 ++numRehashes; 502 #endif 503 504 entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask]; 505 if (entryIndex == emptyEntryIndex) 506 return WTF::notFound; 507 508 if (rep == m_propertyTable->entries()[entryIndex - 1].key) { 509 attributes = m_propertyTable->entries()[entryIndex - 1].attributes; 510 return m_propertyTable->entries()[entryIndex - 1].offset; 511 } 512 } 513 } 514 515 size_t StructureID::put(const Identifier& propertyName, unsigned attributes) 516 { 517 ASSERT(!propertyName.isNull()); 518 ASSERT(get(propertyName) == WTF::notFound); 519 520 checkConsistency(); 521 522 UString::Rep* rep = propertyName._ustring.rep(); 523 524 if (!m_propertyTable) 525 createPropertyMapHashTable(); 526 527 // FIXME: Consider a fast case for tables with no deleted sentinels. 528 529 unsigned i = rep->computedHash(); 530 unsigned k = 0; 531 bool foundDeletedElement = false; 532 unsigned deletedElementIndex = 0; // initialize to make the compiler happy 533 534 #if DUMP_PROPERTYMAP_STATS 535 ++numProbes; 536 #endif 537 538 while (1) { 539 unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask]; 540 if (entryIndex == emptyEntryIndex) 541 break; 542 543 if (entryIndex == deletedSentinelIndex) { 544 // If we find a deleted-element sentinel, remember it for use later. 545 if (!foundDeletedElement) { 546 foundDeletedElement = true; 547 deletedElementIndex = i; 548 } 549 } 550 551 if (k == 0) { 552 k = 1 | doubleHash(rep->computedHash()); 553 #if DUMP_PROPERTYMAP_STATS 554 ++numCollisions; 555 #endif 556 } 557 558 i += k; 559 560 #if DUMP_PROPERTYMAP_STATS 561 ++numRehashes; 562 #endif 563 } 564 565 // Figure out which entry to use. 566 unsigned entryIndex = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount + 2; 567 if (foundDeletedElement) { 568 i = deletedElementIndex; 569 --m_propertyTable->deletedSentinelCount; 570 571 // Since we're not making the table bigger, we can't use the entry one past 572 // the end that we were planning on using, so search backwards for the empty 573 // slot that we can use. We know it will be there because we did at least one 574 // deletion in the past that left an entry empty. 575 while (m_propertyTable->entries()[--entryIndex - 1].key) { } 576 } 577 578 // Create a new hash table entry. 579 m_propertyTable->entryIndices[i & m_propertyTable->sizeMask] = entryIndex; 580 581 // Create a new hash table entry. 582 rep->ref(); 583 m_propertyTable->entries()[entryIndex - 1].key = rep; 584 m_propertyTable->entries()[entryIndex - 1].attributes = attributes; 585 m_propertyTable->entries()[entryIndex - 1].index = ++m_propertyTable->lastIndexUsed; 586 587 unsigned newOffset; 588 if (!m_deletedOffsets.isEmpty()) { 589 newOffset = m_deletedOffsets.last(); 590 m_deletedOffsets.removeLast(); 591 } else 592 newOffset = m_propertyTable->keyCount; 593 m_propertyTable->entries()[entryIndex - 1].offset = newOffset; 594 595 ++m_propertyTable->keyCount; 596 597 if ((m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount) * 2 >= m_propertyTable->size) 598 expandPropertyMapHashTable(); 599 600 checkConsistency(); 601 return newOffset; 602 } 603 604 size_t StructureID::remove(const Identifier& propertyName) 605 { 606 ASSERT(!propertyName.isNull()); 607 608 checkConsistency(); 609 610 UString::Rep* rep = propertyName._ustring.rep(); 611 612 if (!m_propertyTable) 613 return WTF::notFound; 614 615 #if DUMP_PROPERTYMAP_STATS 616 ++numProbes; 617 ++numRemoves; 618 #endif 619 620 // Find the thing to remove. 621 unsigned i = rep->computedHash(); 622 unsigned k = 0; 623 unsigned entryIndex; 624 UString::Rep* key = 0; 625 while (1) { 626 entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask]; 627 if (entryIndex == emptyEntryIndex) 628 return WTF::notFound; 629 630 key = m_propertyTable->entries()[entryIndex - 1].key; 631 if (rep == key) 632 break; 633 634 if (k == 0) { 635 k = 1 | doubleHash(rep->computedHash()); 636 #if DUMP_PROPERTYMAP_STATS 637 ++numCollisions; 638 #endif 639 } 640 641 i += k; 642 643 #if DUMP_PROPERTYMAP_STATS 644 ++numRehashes; 645 #endif 646 } 647 648 // Replace this one element with the deleted sentinel. Also clear out 649 // the entry so we can iterate all the entries as needed. 650 m_propertyTable->entryIndices[i & m_propertyTable->sizeMask] = deletedSentinelIndex; 651 652 size_t offset = m_propertyTable->entries()[entryIndex - 1].offset; 653 654 key->deref(); 655 m_propertyTable->entries()[entryIndex - 1].key = 0; 656 m_propertyTable->entries()[entryIndex - 1].attributes = 0; 657 m_propertyTable->entries()[entryIndex - 1].offset = 0; 658 m_deletedOffsets.append(offset); 659 660 ASSERT(m_propertyTable->keyCount >= 1); 661 --m_propertyTable->keyCount; 662 ++m_propertyTable->deletedSentinelCount; 663 664 if (m_propertyTable->deletedSentinelCount * 4 >= m_propertyTable->size) 665 rehashPropertyMapHashTable(); 666 667 checkConsistency(); 668 return offset; 669 } 670 671 void StructureID::insertIntoPropertyMapHashTable(const PropertyMapEntry& entry) 672 { 673 ASSERT(m_propertyTable); 674 675 unsigned i = entry.key->computedHash(); 676 unsigned k = 0; 677 678 #if DUMP_PROPERTYMAP_STATS 679 ++numProbes; 680 #endif 681 682 while (1) { 683 unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask]; 684 if (entryIndex == emptyEntryIndex) 685 break; 686 687 if (k == 0) { 688 k = 1 | doubleHash(entry.key->computedHash()); 689 #if DUMP_PROPERTYMAP_STATS 690 ++numCollisions; 691 #endif 692 } 693 694 i += k; 695 696 #if DUMP_PROPERTYMAP_STATS 697 ++numRehashes; 698 #endif 699 } 700 701 unsigned entryIndex = m_propertyTable->keyCount + 2; 702 m_propertyTable->entryIndices[i & m_propertyTable->sizeMask] = entryIndex; 703 m_propertyTable->entries()[entryIndex - 1] = entry; 704 705 ++m_propertyTable->keyCount; 706 } 707 708 void StructureID::expandPropertyMapHashTable() 709 { 710 ASSERT(m_propertyTable); 711 rehashPropertyMapHashTable(m_propertyTable->size * 2); 712 } 713 714 void StructureID::createPropertyMapHashTable() 715 { 716 const unsigned newTableSize = 16; 717 718 ASSERT(!m_propertyTable); 719 720 checkConsistency(); 721 722 m_propertyTable = static_cast<PropertyMapHashTable*>(fastZeroedMalloc(PropertyMapHashTable::allocationSize(newTableSize))); 723 m_propertyTable->size = newTableSize; 724 m_propertyTable->sizeMask = newTableSize - 1; 725 726 checkConsistency(); 727 } 728 729 void StructureID::rehashPropertyMapHashTable() 730 { 731 ASSERT(m_propertyTable); 732 ASSERT(m_propertyTable->size); 733 rehashPropertyMapHashTable(m_propertyTable->size); 734 } 735 736 void StructureID::rehashPropertyMapHashTable(unsigned newTableSize) 737 { 738 ASSERT(m_propertyTable); 739 740 checkConsistency(); 741 742 PropertyMapHashTable* oldTable = m_propertyTable; 743 744 m_propertyTable = static_cast<PropertyMapHashTable*>(fastZeroedMalloc(PropertyMapHashTable::allocationSize(newTableSize))); 745 m_propertyTable->size = newTableSize; 746 m_propertyTable->sizeMask = newTableSize - 1; 747 748 unsigned lastIndexUsed = 0; 749 unsigned entryCount = oldTable->keyCount + oldTable->deletedSentinelCount; 750 for (unsigned i = 1; i <= entryCount; ++i) { 751 if (oldTable->entries()[i].key) { 752 lastIndexUsed = max(oldTable->entries()[i].index, lastIndexUsed); 753 insertIntoPropertyMapHashTable(oldTable->entries()[i]); 754 } 755 } 756 m_propertyTable->lastIndexUsed = lastIndexUsed; 757 758 fastFree(oldTable); 759 760 checkConsistency(); 761 } 762 763 static int comparePropertyMapEntryIndices(const void* a, const void* b) 764 { 765 unsigned ia = static_cast<PropertyMapEntry* const*>(a)[0]->index; 766 unsigned ib = static_cast<PropertyMapEntry* const*>(b)[0]->index; 767 if (ia < ib) 768 return -1; 769 if (ia > ib) 770 return +1; 771 return 0; 772 } 773 774 void StructureID::getEnumerablePropertyNamesInternal(PropertyNameArray& propertyNames) const 775 { 776 if (!m_propertyTable) 777 return; 778 779 if (m_propertyTable->keyCount < tinyMapThreshold) { 780 PropertyMapEntry* a[tinyMapThreshold]; 781 int i = 0; 782 unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount; 783 for (unsigned k = 1; k <= entryCount; k++) { 784 if (m_propertyTable->entries()[k].key && !(m_propertyTable->entries()[k].attributes & DontEnum)) { 785 PropertyMapEntry* value = &m_propertyTable->entries()[k]; 786 int j; 787 for (j = i - 1; j >= 0 && a[j]->index > value->index; --j) 788 a[j + 1] = a[j]; 789 a[j + 1] = value; 790 ++i; 791 } 792 } 793 if (!propertyNames.size()) { 794 for (int k = 0; k < i; ++k) 795 propertyNames.addKnownUnique(a[k]->key); 796 } else { 797 for (int k = 0; k < i; ++k) 798 propertyNames.add(a[k]->key); 799 } 800 801 return; 802 } 803 804 // Allocate a buffer to use to sort the keys. 805 Vector<PropertyMapEntry*, smallMapThreshold> sortedEnumerables(m_propertyTable->keyCount); 806 807 // Get pointers to the enumerable entries in the buffer. 808 PropertyMapEntry** p = sortedEnumerables.data(); 809 unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount; 810 for (unsigned i = 1; i <= entryCount; i++) { 811 if (m_propertyTable->entries()[i].key && !(m_propertyTable->entries()[i].attributes & DontEnum)) 812 *p++ = &m_propertyTable->entries()[i]; 813 } 814 815 size_t enumerableCount = p - sortedEnumerables.data(); 816 // Sort the entries by index. 817 qsort(sortedEnumerables.data(), enumerableCount, sizeof(PropertyMapEntry*), comparePropertyMapEntryIndices); 818 sortedEnumerables.resize(enumerableCount); 819 820 // Put the keys of the sorted entries into the list. 821 if (!propertyNames.size()) { 822 for (size_t i = 0; i < sortedEnumerables.size(); ++i) 823 propertyNames.addKnownUnique(sortedEnumerables[i]->key); 824 } else { 825 for (size_t i = 0; i < sortedEnumerables.size(); ++i) 826 propertyNames.add(sortedEnumerables[i]->key); 827 } 828 } 829 830 #if DO_PROPERTYMAP_CONSTENCY_CHECK 831 832 void StructureID::checkConsistency() 833 { 834 if (!m_propertyTable) 835 return; 836 837 ASSERT(m_propertyTable->size >= 16); 838 ASSERT(m_propertyTable->sizeMask); 839 ASSERT(m_propertyTable->size == m_propertyTable->sizeMask + 1); 840 ASSERT(!(m_propertyTable->size & m_propertyTable->sizeMask)); 841 842 ASSERT(m_propertyTable->keyCount <= m_propertyTable->size / 2); 843 ASSERT(m_propertyTable->deletedSentinelCount <= m_propertyTable->size / 4); 844 845 ASSERT(m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount <= m_propertyTable->size / 2); 846 847 unsigned indexCount = 0; 848 unsigned deletedIndexCount = 0; 849 for (unsigned a = 0; a != m_propertyTable->size; ++a) { 850 unsigned entryIndex = m_propertyTable->entryIndices[a]; 851 if (entryIndex == emptyEntryIndex) 852 continue; 853 if (entryIndex == deletedSentinelIndex) { 854 ++deletedIndexCount; 855 continue; 856 } 857 ASSERT(entryIndex > deletedSentinelIndex); 858 ASSERT(entryIndex - 1 <= m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount); 859 ++indexCount; 860 861 for (unsigned b = a + 1; b != m_propertyTable->size; ++b) 862 ASSERT(m_propertyTable->entryIndices[b] != entryIndex); 863 } 864 ASSERT(indexCount == m_propertyTable->keyCount); 865 ASSERT(deletedIndexCount == m_propertyTable->deletedSentinelCount); 866 867 ASSERT(m_propertyTable->entries()[0].key == 0); 868 869 unsigned nonEmptyEntryCount = 0; 870 for (unsigned c = 1; c <= m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount; ++c) { 871 UString::Rep* rep = m_propertyTable->entries()[c].key; 872 if (!rep) 873 continue; 874 ++nonEmptyEntryCount; 875 unsigned i = rep->computedHash(); 876 unsigned k = 0; 877 unsigned entryIndex; 878 while (1) { 879 entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask]; 880 ASSERT(entryIndex != emptyEntryIndex); 881 if (rep == m_propertyTable->entries()[entryIndex - 1].key) 882 break; 883 if (k == 0) 884 k = 1 | doubleHash(rep->computedHash()); 885 i += k; 886 } 887 ASSERT(entryIndex == c + 1); 888 } 889 890 ASSERT(nonEmptyEntryCount == m_propertyTable->keyCount); 891 } 892 893 #endif // DO_PROPERTYMAP_CONSTENCY_CHECK 894 895 // StructureIDChain 360 896 361 897 StructureIDChain::StructureIDChain(StructureID* structureID) -
trunk/JavaScriptCore/runtime/StructureID.h
r37989 r38016 1 // -*- mode: c++; c-basic-offset: 4 -*-2 1 /* 3 2 * Copyright (C) 2008 Apple Inc. All rights reserved. … … 30 29 #include "JSType.h" 31 30 #include "JSValue.h" 32 #include "PropertyMap .h"31 #include "PropertyMapHashTable.h" 33 32 #include "StructureIDTransitionTable.h" 34 33 #include "TypeInfo.h" 34 #include "identifier.h" 35 35 #include "ustring.h" 36 36 #include <wtf/HashFunctions.h> … … 41 41 42 42 #define DUMP_STRUCTURE_ID_STATISTICS 0 43 44 #ifndef NDEBUG 45 #define DUMP_PROPERTYMAP_STATS 0 46 #else 47 #define DUMP_PROPERTYMAP_STATS 0 48 #endif 43 49 44 50 namespace JSC { … … 65 71 static PassRefPtr<StructureID> changePrototypeTransition(StructureID*, JSValue* prototype); 66 72 static PassRefPtr<StructureID> addPropertyTransition(StructureID*, const Identifier& propertyName, unsigned attributes, size_t& offset); 73 static PassRefPtr<StructureID> removePropertyTransition(StructureID*, const Identifier& propertyName, size_t& offset); 67 74 static PassRefPtr<StructureID> getterSetterTransition(StructureID*); 68 75 static PassRefPtr<StructureID> toDictionaryTransition(StructureID*); … … 79 86 // These should be used with caution. 80 87 size_t addPropertyWithoutTransition(const Identifier& propertyName, unsigned attributes); 88 size_t removePropertyWithoutTransition(const Identifier& propertyName); 81 89 void setPrototypeWithoutTransition(JSValue* prototype) { m_prototype = prototype; } 82 90 … … 102 110 void growPropertyStorageCapacity(); 103 111 size_t propertyStorageCapacity() const { return m_propertyStorageCapacity; } 104 size_t propertyStorageSize() const { return m_propertyMap.storageSize(); } 105 106 size_t get(const Identifier& propertyName) const { return m_propertyMap.get(propertyName); } 107 size_t get(const Identifier& propertyName, unsigned& attributes) const { return m_propertyMap.get(propertyName, attributes); } 108 size_t put(const Identifier& propertyName, unsigned attributes) { return m_propertyMap.put(propertyName, attributes); } 109 size_t remove(const Identifier& propertyName) { return m_propertyMap.remove(propertyName); } 110 112 size_t propertyStorageSize() const { return m_propertyTable ? m_propertyTable->keyCount + m_deletedOffsets.size() : 0; } 113 114 size_t get(const Identifier& propertyName) const; 115 size_t get(const Identifier& propertyName, unsigned& attributes) const; 111 116 void getEnumerablePropertyNames(ExecState*, PropertyNameArray&, JSObject*); 112 void clearEnumerationCache();113 117 114 118 bool hasGetterSetterProperties() const { return m_hasGetterSetterProperties; } 115 119 void setHasGetterSetterProperties(bool hasGetterSetterProperties) { m_hasGetterSetterProperties = hasGetterSetterProperties; } 116 120 117 bool isEmpty() const { return m_propertyMap.isEmpty(); }121 bool isEmpty() const { return !m_propertyTable; } 118 122 119 123 private: 120 124 StructureID(JSValue* prototype, const TypeInfo&); 121 125 126 size_t put(const Identifier& propertyName, unsigned attributes); 127 size_t remove(const Identifier& propertyName); 128 void getEnumerablePropertyNamesInternal(PropertyNameArray&) const; 129 130 void expandPropertyMapHashTable(); 131 void rehashPropertyMapHashTable(); 132 void rehashPropertyMapHashTable(unsigned newTableSize); 133 void createPropertyMapHashTable(); 134 void insertIntoPropertyMapHashTable(const PropertyMapEntry&); 135 void checkConsistency(); 136 137 PropertyMapHashTable* copyPropertyTable(); 138 139 void clearEnumerationCache(); 140 141 static const unsigned emptyEntryIndex = 0; 142 122 143 static const size_t s_maxTransitionLength = 64; 123 144 … … 138 159 RefPtr<PropertyNameArrayData> m_cachedPropertyNameArrayData; 139 160 140 PropertyMap m_propertyMap; 161 PropertyMapHashTable* m_propertyTable; 162 Vector<unsigned> m_deletedOffsets; 163 141 164 size_t m_propertyStorageCapacity; 142 165 … … 149 172 }; 150 173 174 inline size_t StructureID::get(const Identifier& propertyName) const 175 { 176 ASSERT(!propertyName.isNull()); 177 178 if (!m_propertyTable) 179 return WTF::notFound; 180 181 UString::Rep* rep = propertyName._ustring.rep(); 182 183 unsigned i = rep->computedHash(); 184 185 #if DUMP_PROPERTYMAP_STATS 186 ++numProbes; 187 #endif 188 189 unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask]; 190 if (entryIndex == emptyEntryIndex) 191 return WTF::notFound; 192 193 if (rep == m_propertyTable->entries()[entryIndex - 1].key) 194 return m_propertyTable->entries()[entryIndex - 1].offset; 195 196 #if DUMP_PROPERTYMAP_STATS 197 ++numCollisions; 198 #endif 199 200 unsigned k = 1 | WTF::doubleHash(rep->computedHash()); 201 202 while (1) { 203 i += k; 204 205 #if DUMP_PROPERTYMAP_STATS 206 ++numRehashes; 207 #endif 208 209 entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask]; 210 if (entryIndex == emptyEntryIndex) 211 return WTF::notFound; 212 213 if (rep == m_propertyTable->entries()[entryIndex - 1].key) 214 return m_propertyTable->entries()[entryIndex - 1].offset; 215 } 216 } 217 151 218 class StructureIDChain : public RefCounted<StructureIDChain> { 152 219 public:
Note:
See TracChangeset
for help on using the changeset viewer.
