1 | /* |
2 | * Copyright (C) 2008, 2009 Apple Inc. All rights reserved. |
3 | * |
4 | * Redistribution and use in source and binary forms, with or without |
5 | * modification, are permitted provided that the following conditions |
6 | * are met: |
7 | * 1. Redistributions of source code must retain the above copyright |
8 | * notice, this list of conditions and the following disclaimer. |
9 | * 2. Redistributions in binary form must reproduce the above copyright |
10 | * notice, this list of conditions and the following disclaimer in the |
11 | * documentation and/or other materials provided with the distribution. |
12 | * |
13 | * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY |
14 | * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
15 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
16 | * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE COMPUTER, INC. OR |
17 | * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, |
18 | * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, |
19 | * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
20 | * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY |
21 | * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
22 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
23 | * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
24 | */ |
25 | |
26 | #include "config.h" |
27 | #include "Structure.h" |
28 | |
29 | #include "Identifier.h" |
30 | #include "JSObject.h" |
31 | #include "JSPropertyNameIterator.h" |
32 | #include "Lookup.h" |
33 | #include "PropertyNameArray.h" |
34 | #include "StructureChain.h" |
35 | #include <wtf/RefCountedLeakCounter.h> |
36 | #include <wtf/RefPtr.h> |
37 | |
38 | #if ENABLE(JSC_MULTIPLE_THREADS) |
39 | #include <wtf/Threading.h> |
40 | #endif |
41 | |
42 | #define DUMP_STRUCTURE_ID_STATISTICS 0 |
43 | |
44 | #ifndef NDEBUG |
45 | #define DO_PROPERTYMAP_CONSTENCY_CHECK 0 |
46 | #else |
47 | #define DO_PROPERTYMAP_CONSTENCY_CHECK 0 |
48 | #endif |
49 | |
50 | using namespace WTF; |
51 | |
52 | namespace JSC { |
53 | |
54 | // Choose a number for the following so that most property maps are smaller, |
55 | // but it's not going to blow out the stack to allocate this number of pointers. |
56 | static const int smallMapThreshold = 1024; |
57 | |
58 | // The point at which the function call overhead of the qsort implementation |
59 | // becomes small compared to the inefficiency of insertion sort. |
60 | static const unsigned tinyMapThreshold = 20; |
61 | |
62 | static const unsigned newTableSize = 16; |
63 | |
64 | #ifndef NDEBUG |
65 | static WTF::RefCountedLeakCounter structureCounter("Structure" ); |
66 | |
67 | #if ENABLE(JSC_MULTIPLE_THREADS) |
68 | static Mutex& ignoreSetMutex = *(new Mutex); |
69 | #endif |
70 | |
71 | static bool shouldIgnoreLeaks; |
72 | static HashSet<Structure*>& ignoreSet = *(new HashSet<Structure*>); |
73 | #endif |
74 | |
75 | #if DUMP_STRUCTURE_ID_STATISTICS |
76 | static HashSet<Structure*>& liveStructureSet = *(new HashSet<Structure*>); |
77 | #endif |
78 | |
79 | static int comparePropertyMapEntryIndices(const void* a, const void* b); |
80 | |
81 | void Structure::dumpStatistics() |
82 | { |
83 | #if DUMP_STRUCTURE_ID_STATISTICS |
84 | unsigned numberLeaf = 0; |
85 | unsigned numberUsingSingleSlot = 0; |
86 | unsigned numberSingletons = 0; |
87 | unsigned numberWithPropertyMaps = 0; |
88 | unsigned totalPropertyMapsSize = 0; |
89 | |
90 | HashSet<Structure*>::const_iterator end = liveStructureSet.end(); |
91 | for (HashSet<Structure*>::const_iterator it = liveStructureSet.begin(); it != end; ++it) { |
92 | Structure* structure = *it; |
93 | if (structure->m_usingSingleTransitionSlot) { |
94 | if (!structure->m_transitions.singleTransition) |
95 | ++numberLeaf; |
96 | else |
97 | ++numberUsingSingleSlot; |
98 | |
99 | if (!structure->m_previous && !structure->m_transitions.singleTransition) |
100 | ++numberSingletons; |
101 | } |
102 | |
103 | if (structure->m_propertyTable) { |
104 | ++numberWithPropertyMaps; |
105 | totalPropertyMapsSize += PropertyMapHashTable::allocationSize(structure->m_propertyTable->size); |
106 | if (structure->m_propertyTable->deletedOffsets) |
107 | totalPropertyMapsSize += (structure->m_propertyTable->deletedOffsets->capacity() * sizeof(unsigned)); |
108 | } |
109 | } |
110 | |
111 | printf("Number of live Structures: %d\n" , liveStructureSet.size()); |
112 | printf("Number of Structures using the single item optimization for transition map: %d\n" , numberUsingSingleSlot); |
113 | printf("Number of Structures that are leaf nodes: %d\n" , numberLeaf); |
114 | printf("Number of Structures that singletons: %d\n" , numberSingletons); |
115 | printf("Number of Structures with PropertyMaps: %d\n" , numberWithPropertyMaps); |
116 | |
117 | printf("Size of a single Structures: %d\n" , static_cast<unsigned>(sizeof(Structure))); |
118 | printf("Size of sum of all property maps: %d\n" , totalPropertyMapsSize); |
119 | printf("Size of average of all property maps: %f\n" , static_cast<double>(totalPropertyMapsSize) / static_cast<double>(liveStructureSet.size())); |
120 | #else |
121 | printf(format: "Dumping Structure statistics is not enabled.\n" ); |
122 | #endif |
123 | } |
124 | |
125 | Structure::Structure(JSValue prototype, const TypeInfo& typeInfo) |
126 | : m_typeInfo(typeInfo) |
127 | , m_prototype(prototype) |
128 | , m_specificValueInPrevious(0) |
129 | , m_propertyTable(0) |
130 | , m_propertyStorageCapacity(JSObject::inlineStorageCapacity) |
131 | , m_offset(noOffset) |
132 | , m_dictionaryKind(NoneDictionaryKind) |
133 | , m_isPinnedPropertyTable(false) |
134 | , m_hasGetterSetterProperties(false) |
135 | , m_attributesInPrevious(0) |
136 | , m_specificFunctionThrashCount(0) |
137 | { |
138 | ASSERT(m_prototype); |
139 | ASSERT(m_prototype.isObject() || m_prototype.isNull()); |
140 | |
141 | #ifndef NDEBUG |
142 | #if ENABLE(JSC_MULTIPLE_THREADS) |
143 | MutexLocker protect(ignoreSetMutex); |
144 | #endif |
145 | if (shouldIgnoreLeaks) |
146 | ignoreSet.add(value: this); |
147 | else |
148 | structureCounter.increment(); |
149 | #endif |
150 | |
151 | #if DUMP_STRUCTURE_ID_STATISTICS |
152 | liveStructureSet.add(this); |
153 | #endif |
154 | } |
155 | |
156 | Structure::~Structure() |
157 | { |
158 | if (m_previous) { |
159 | if (m_nameInPrevious) { |
160 | unsigned attrInPrev = m_attributesInPrevious; |
161 | m_previous->table.remove(key: StructureTransitionTableHash::Key(RefPtr<UString::Rep>(m_nameInPrevious.get()), attrInPrev), specificValue: m_specificValueInPrevious); |
162 | } else |
163 | m_previous->table.removeAnonymousSlotTransition(count: m_anonymousSlotsInPrevious); |
164 | |
165 | } |
166 | |
167 | if (m_enumerationCache) |
168 | m_enumerationCache->setCachedStructure(0); |
169 | |
170 | if (m_propertyTable) { |
171 | unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount; |
172 | for (unsigned i = 1; i <= entryCount; i++) { |
173 | if (UString::Rep* key = m_propertyTable->entries()[i].key) |
174 | key->deref(); |
175 | } |
176 | |
177 | delete m_propertyTable->deletedOffsets; |
178 | fastFree(m_propertyTable); |
179 | } |
180 | |
181 | #ifndef NDEBUG |
182 | #if ENABLE(JSC_MULTIPLE_THREADS) |
183 | MutexLocker protect(ignoreSetMutex); |
184 | #endif |
185 | HashSet<Structure*>::iterator it = ignoreSet.find(value: this); |
186 | if (it != ignoreSet.end()) |
187 | ignoreSet.remove(it); |
188 | else |
189 | structureCounter.decrement(); |
190 | #endif |
191 | |
192 | #if DUMP_STRUCTURE_ID_STATISTICS |
193 | liveStructureSet.remove(this); |
194 | #endif |
195 | } |
196 | |
197 | void Structure::startIgnoringLeaks() |
198 | { |
199 | #ifndef NDEBUG |
200 | shouldIgnoreLeaks = true; |
201 | #endif |
202 | } |
203 | |
204 | void Structure::stopIgnoringLeaks() |
205 | { |
206 | #ifndef NDEBUG |
207 | shouldIgnoreLeaks = false; |
208 | #endif |
209 | } |
210 | |
211 | static bool isPowerOf2(unsigned v) |
212 | { |
213 | // Taken from http://www.cs.utk.edu/~vose/c-stuff/bithacks.html |
214 | |
215 | return !(v & (v - 1)) && v; |
216 | } |
217 | |
218 | static unsigned nextPowerOf2(unsigned v) |
219 | { |
220 | // Taken from http://www.cs.utk.edu/~vose/c-stuff/bithacks.html |
221 | // Devised by Sean Anderson, Sepember 14, 2001 |
222 | |
223 | v--; |
224 | v |= v >> 1; |
225 | v |= v >> 2; |
226 | v |= v >> 4; |
227 | v |= v >> 8; |
228 | v |= v >> 16; |
229 | v++; |
230 | |
231 | return v; |
232 | } |
233 | |
234 | static unsigned sizeForKeyCount(size_t keyCount) |
235 | { |
236 | if (keyCount == notFound) |
237 | return newTableSize; |
238 | |
239 | if (keyCount < 8) |
240 | return newTableSize; |
241 | |
242 | if (isPowerOf2(v: keyCount)) |
243 | return keyCount * 4; |
244 | |
245 | return nextPowerOf2(v: keyCount) * 2; |
246 | } |
247 | |
248 | void Structure::materializePropertyMap() |
249 | { |
250 | ASSERT(!m_propertyTable); |
251 | |
252 | Vector<Structure*, 8> structures; |
253 | structures.append(val: this); |
254 | |
255 | Structure* structure = this; |
256 | |
257 | // Search for the last Structure with a property table. |
258 | while ((structure = structure->previousID())) { |
259 | if (structure->m_isPinnedPropertyTable) { |
260 | ASSERT(structure->m_propertyTable); |
261 | ASSERT(!structure->m_previous); |
262 | |
263 | m_propertyTable = structure->copyPropertyTable(); |
264 | break; |
265 | } |
266 | |
267 | structures.append(val: structure); |
268 | } |
269 | |
270 | if (!m_propertyTable) |
271 | createPropertyMapHashTable(newTableSize: sizeForKeyCount(keyCount: m_offset + 1)); |
272 | else { |
273 | if (sizeForKeyCount(keyCount: m_offset + 1) > m_propertyTable->size) |
274 | rehashPropertyMapHashTable(newTableSize: sizeForKeyCount(keyCount: m_offset + 1)); // This could be made more efficient by combining with the copy above. |
275 | } |
276 | |
277 | for (ptrdiff_t i = structures.size() - 2; i >= 0; --i) { |
278 | structure = structures[i]; |
279 | if (!structure->m_nameInPrevious) { |
280 | m_propertyTable->anonymousSlotCount += structure->m_anonymousSlotsInPrevious; |
281 | continue; |
282 | } |
283 | structure->m_nameInPrevious->ref(); |
284 | PropertyMapEntry entry(structure->m_nameInPrevious.get(), structure->m_offset, structure->m_attributesInPrevious, structure->m_specificValueInPrevious, ++m_propertyTable->lastIndexUsed); |
285 | insertIntoPropertyMapHashTable(entry); |
286 | } |
287 | } |
288 | |
289 | void Structure::growPropertyStorageCapacity() |
290 | { |
291 | if (m_propertyStorageCapacity == JSObject::inlineStorageCapacity) |
292 | m_propertyStorageCapacity = JSObject::nonInlineBaseStorageCapacity; |
293 | else |
294 | m_propertyStorageCapacity *= 2; |
295 | } |
296 | |
297 | void Structure::despecifyDictionaryFunction(const Identifier& propertyName) |
298 | { |
299 | const UString::Rep* rep = propertyName._ustring.rep(); |
300 | |
301 | materializePropertyMapIfNecessary(); |
302 | |
303 | ASSERT(isDictionary()); |
304 | ASSERT(m_propertyTable); |
305 | |
306 | unsigned i = rep->existingHash(); |
307 | |
308 | #if DUMP_PROPERTYMAP_STATS |
309 | ++numProbes; |
310 | #endif |
311 | |
312 | unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask]; |
313 | ASSERT(entryIndex != emptyEntryIndex); |
314 | |
315 | if (rep == m_propertyTable->entries()[entryIndex - 1].key) { |
316 | m_propertyTable->entries()[entryIndex - 1].specificValue = 0; |
317 | return; |
318 | } |
319 | |
320 | #if DUMP_PROPERTYMAP_STATS |
321 | ++numCollisions; |
322 | #endif |
323 | |
324 | unsigned k = 1 | doubleHash(key: rep->existingHash()); |
325 | |
326 | while (1) { |
327 | i += k; |
328 | |
329 | #if DUMP_PROPERTYMAP_STATS |
330 | ++numRehashes; |
331 | #endif |
332 | |
333 | entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask]; |
334 | ASSERT(entryIndex != emptyEntryIndex); |
335 | |
336 | if (rep == m_propertyTable->entries()[entryIndex - 1].key) { |
337 | m_propertyTable->entries()[entryIndex - 1].specificValue = 0; |
338 | return; |
339 | } |
340 | } |
341 | } |
342 | |
343 | PassRefPtr<Structure> Structure::addPropertyTransitionToExistingStructure(Structure* structure, const Identifier& propertyName, unsigned attributes, JSCell* specificValue, size_t& offset) |
344 | { |
345 | ASSERT(!structure->isDictionary()); |
346 | ASSERT(structure->typeInfo().type() == ObjectType); |
347 | |
348 | if (Structure* existingTransition = structure->table.get(key: StructureTransitionTableHash::Key(RefPtr<UString::Rep>(propertyName.ustring().rep()), attributes), specificValue)) { |
349 | ASSERT(existingTransition->m_offset != noOffset); |
350 | offset = existingTransition->m_offset; |
351 | return existingTransition; |
352 | } |
353 | |
354 | return 0; |
355 | } |
356 | |
357 | PassRefPtr<Structure> Structure::addPropertyTransition(Structure* structure, const Identifier& propertyName, unsigned attributes, JSCell* specificValue, size_t& offset) |
358 | { |
359 | ASSERT(!structure->isDictionary()); |
360 | ASSERT(structure->typeInfo().type() == ObjectType); |
361 | ASSERT(!Structure::addPropertyTransitionToExistingStructure(structure, propertyName, attributes, specificValue, offset)); |
362 | |
363 | if (structure->m_specificFunctionThrashCount == maxSpecificFunctionThrashCount) |
364 | specificValue = 0; |
365 | |
366 | if (structure->transitionCount() > s_maxTransitionLength) { |
367 | RefPtr<Structure> transition = toCacheableDictionaryTransition(structure); |
368 | ASSERT(structure != transition); |
369 | offset = transition->put(propertyName, attributes, specificValue); |
370 | if (transition->propertyStorageSize() > transition->propertyStorageCapacity()) |
371 | transition->growPropertyStorageCapacity(); |
372 | return transition.release(); |
373 | } |
374 | |
375 | RefPtr<Structure> transition = create(prototype: structure->m_prototype, typeInfo: structure->typeInfo()); |
376 | |
377 | transition->m_cachedPrototypeChain = structure->m_cachedPrototypeChain; |
378 | transition->m_previous = structure; |
379 | transition->m_nameInPrevious = propertyName.ustring().rep(); |
380 | transition->m_attributesInPrevious = attributes; |
381 | transition->m_specificValueInPrevious = specificValue; |
382 | transition->m_propertyStorageCapacity = structure->m_propertyStorageCapacity; |
383 | transition->m_hasGetterSetterProperties = structure->m_hasGetterSetterProperties; |
384 | transition->m_hasNonEnumerableProperties = structure->m_hasNonEnumerableProperties; |
385 | transition->m_specificFunctionThrashCount = structure->m_specificFunctionThrashCount; |
386 | |
387 | if (structure->m_propertyTable) { |
388 | if (structure->m_isPinnedPropertyTable) |
389 | transition->m_propertyTable = structure->copyPropertyTable(); |
390 | else { |
391 | transition->m_propertyTable = structure->m_propertyTable; |
392 | structure->m_propertyTable = 0; |
393 | } |
394 | } else { |
395 | if (structure->m_previous) |
396 | transition->materializePropertyMap(); |
397 | else |
398 | transition->createPropertyMapHashTable(); |
399 | } |
400 | |
401 | offset = transition->put(propertyName, attributes, specificValue); |
402 | if (transition->propertyStorageSize() > transition->propertyStorageCapacity()) |
403 | transition->growPropertyStorageCapacity(); |
404 | |
405 | transition->m_offset = offset; |
406 | |
407 | structure->table.add(key: StructureTransitionTableHash::Key(RefPtr<UString::Rep>(propertyName.ustring().rep()), attributes), structure: transition.get(), specificValue); |
408 | return transition.release(); |
409 | } |
410 | |
411 | PassRefPtr<Structure> Structure::removePropertyTransition(Structure* structure, const Identifier& propertyName, size_t& offset) |
412 | { |
413 | ASSERT(!structure->isUncacheableDictionary()); |
414 | |
415 | RefPtr<Structure> transition = toUncacheableDictionaryTransition(structure); |
416 | |
417 | offset = transition->remove(propertyName); |
418 | |
419 | return transition.release(); |
420 | } |
421 | |
422 | PassRefPtr<Structure> Structure::changePrototypeTransition(Structure* structure, JSValue prototype) |
423 | { |
424 | RefPtr<Structure> transition = create(prototype, typeInfo: structure->typeInfo()); |
425 | |
426 | transition->m_propertyStorageCapacity = structure->m_propertyStorageCapacity; |
427 | transition->m_hasGetterSetterProperties = structure->m_hasGetterSetterProperties; |
428 | transition->m_hasNonEnumerableProperties = structure->m_hasNonEnumerableProperties; |
429 | transition->m_specificFunctionThrashCount = structure->m_specificFunctionThrashCount; |
430 | |
431 | // Don't set m_offset, as one can not transition to this. |
432 | |
433 | structure->materializePropertyMapIfNecessary(); |
434 | transition->m_propertyTable = structure->copyPropertyTable(); |
435 | transition->m_isPinnedPropertyTable = true; |
436 | |
437 | return transition.release(); |
438 | } |
439 | |
440 | PassRefPtr<Structure> Structure::despecifyFunctionTransition(Structure* structure, const Identifier& replaceFunction) |
441 | { |
442 | ASSERT(structure->m_specificFunctionThrashCount < maxSpecificFunctionThrashCount); |
443 | RefPtr<Structure> transition = create(prototype: structure->storedPrototype(), typeInfo: structure->typeInfo()); |
444 | |
445 | transition->m_propertyStorageCapacity = structure->m_propertyStorageCapacity; |
446 | transition->m_hasGetterSetterProperties = structure->m_hasGetterSetterProperties; |
447 | transition->m_hasNonEnumerableProperties = structure->m_hasNonEnumerableProperties; |
448 | transition->m_specificFunctionThrashCount = structure->m_specificFunctionThrashCount + 1; |
449 | |
450 | // Don't set m_offset, as one can not transition to this. |
451 | |
452 | structure->materializePropertyMapIfNecessary(); |
453 | transition->m_propertyTable = structure->copyPropertyTable(); |
454 | transition->m_isPinnedPropertyTable = true; |
455 | |
456 | if (transition->m_specificFunctionThrashCount == maxSpecificFunctionThrashCount) |
457 | transition->despecifyAllFunctions(); |
458 | else { |
459 | bool removed = transition->despecifyFunction(replaceFunction); |
460 | ASSERT_UNUSED(removed, removed); |
461 | } |
462 | |
463 | return transition.release(); |
464 | } |
465 | |
466 | PassRefPtr<Structure> Structure::addAnonymousSlotsTransition(Structure* structure, unsigned count) |
467 | { |
468 | if (Structure* transition = structure->table.getAnonymousSlotTransition(count)) { |
469 | ASSERT(transition->storedPrototype() == structure->storedPrototype()); |
470 | return transition; |
471 | } |
472 | ASSERT(count); |
473 | ASSERT(count < ((1<<6) - 2)); |
474 | RefPtr<Structure> transition = create(prototype: structure->m_prototype, typeInfo: structure->typeInfo()); |
475 | |
476 | transition->m_cachedPrototypeChain = structure->m_cachedPrototypeChain; |
477 | transition->m_previous = structure; |
478 | transition->m_nameInPrevious = 0; |
479 | transition->m_attributesInPrevious = 0; |
480 | transition->m_anonymousSlotsInPrevious = count; |
481 | transition->m_specificValueInPrevious = 0; |
482 | transition->m_propertyStorageCapacity = structure->m_propertyStorageCapacity; |
483 | transition->m_hasGetterSetterProperties = structure->m_hasGetterSetterProperties; |
484 | transition->m_hasNonEnumerableProperties = structure->m_hasNonEnumerableProperties; |
485 | transition->m_specificFunctionThrashCount = structure->m_specificFunctionThrashCount; |
486 | |
487 | if (structure->m_propertyTable) { |
488 | if (structure->m_isPinnedPropertyTable) |
489 | transition->m_propertyTable = structure->copyPropertyTable(); |
490 | else { |
491 | transition->m_propertyTable = structure->m_propertyTable; |
492 | structure->m_propertyTable = 0; |
493 | } |
494 | } else { |
495 | if (structure->m_previous) |
496 | transition->materializePropertyMap(); |
497 | else |
498 | transition->createPropertyMapHashTable(); |
499 | } |
500 | |
501 | transition->addAnonymousSlots(slotCount: count); |
502 | if (transition->propertyStorageSize() > transition->propertyStorageCapacity()) |
503 | transition->growPropertyStorageCapacity(); |
504 | |
505 | structure->table.addAnonymousSlotTransition(count, structure: transition.get()); |
506 | return transition.release(); |
507 | } |
508 | |
509 | PassRefPtr<Structure> Structure::getterSetterTransition(Structure* structure) |
510 | { |
511 | RefPtr<Structure> transition = create(prototype: structure->storedPrototype(), typeInfo: structure->typeInfo()); |
512 | transition->m_propertyStorageCapacity = structure->m_propertyStorageCapacity; |
513 | transition->m_hasGetterSetterProperties = structure->m_hasGetterSetterProperties; |
514 | transition->m_hasNonEnumerableProperties = structure->m_hasNonEnumerableProperties; |
515 | transition->m_specificFunctionThrashCount = structure->m_specificFunctionThrashCount; |
516 | |
517 | // Don't set m_offset, as one can not transition to this. |
518 | |
519 | structure->materializePropertyMapIfNecessary(); |
520 | transition->m_propertyTable = structure->copyPropertyTable(); |
521 | transition->m_isPinnedPropertyTable = true; |
522 | |
523 | return transition.release(); |
524 | } |
525 | |
526 | PassRefPtr<Structure> Structure::toDictionaryTransition(Structure* structure, DictionaryKind kind) |
527 | { |
528 | ASSERT(!structure->isUncacheableDictionary()); |
529 | |
530 | RefPtr<Structure> transition = create(prototype: structure->m_prototype, typeInfo: structure->typeInfo()); |
531 | transition->m_dictionaryKind = kind; |
532 | transition->m_propertyStorageCapacity = structure->m_propertyStorageCapacity; |
533 | transition->m_hasGetterSetterProperties = structure->m_hasGetterSetterProperties; |
534 | transition->m_hasNonEnumerableProperties = structure->m_hasNonEnumerableProperties; |
535 | transition->m_specificFunctionThrashCount = structure->m_specificFunctionThrashCount; |
536 | |
537 | structure->materializePropertyMapIfNecessary(); |
538 | transition->m_propertyTable = structure->copyPropertyTable(); |
539 | transition->m_isPinnedPropertyTable = true; |
540 | |
541 | return transition.release(); |
542 | } |
543 | |
544 | PassRefPtr<Structure> Structure::toCacheableDictionaryTransition(Structure* structure) |
545 | { |
546 | return toDictionaryTransition(structure, kind: CachedDictionaryKind); |
547 | } |
548 | |
549 | PassRefPtr<Structure> Structure::toUncacheableDictionaryTransition(Structure* structure) |
550 | { |
551 | return toDictionaryTransition(structure, kind: UncachedDictionaryKind); |
552 | } |
553 | |
554 | PassRefPtr<Structure> Structure::flattenDictionaryStructure(JSObject* object) |
555 | { |
556 | ASSERT(isDictionary()); |
557 | if (isUncacheableDictionary()) { |
558 | ASSERT(m_propertyTable); |
559 | Vector<PropertyMapEntry*> sortedPropertyEntries(m_propertyTable->keyCount); |
560 | PropertyMapEntry** p = sortedPropertyEntries.data(); |
561 | unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount; |
562 | for (unsigned i = 1; i <= entryCount; i++) { |
563 | if (m_propertyTable->entries()[i].key) |
564 | *p++ = &m_propertyTable->entries()[i]; |
565 | } |
566 | size_t propertyCount = p - sortedPropertyEntries.data(); |
567 | qsort(base: sortedPropertyEntries.data(), nmemb: propertyCount, size: sizeof(PropertyMapEntry*), compar: comparePropertyMapEntryIndices); |
568 | sortedPropertyEntries.resize(size: propertyCount); |
569 | |
570 | // We now have the properties currently defined on this object |
571 | // in the order that they are expected to be in, but we need to |
572 | // reorder the storage, so we have to copy the current values out |
573 | Vector<JSValue> values(propertyCount); |
574 | unsigned anonymousSlotCount = m_propertyTable->anonymousSlotCount; |
575 | for (unsigned i = 0; i < propertyCount; i++) { |
576 | PropertyMapEntry* entry = sortedPropertyEntries[i]; |
577 | values[i] = object->getDirectOffset(offset: entry->offset); |
578 | // Update property table to have the new property offsets |
579 | entry->offset = anonymousSlotCount + i; |
580 | entry->index = i; |
581 | } |
582 | |
583 | // Copy the original property values into their final locations |
584 | for (unsigned i = 0; i < propertyCount; i++) |
585 | object->putDirectOffset(offset: anonymousSlotCount + i, value: values[i]); |
586 | |
587 | if (m_propertyTable->deletedOffsets) { |
588 | delete m_propertyTable->deletedOffsets; |
589 | m_propertyTable->deletedOffsets = 0; |
590 | } |
591 | } |
592 | |
593 | m_dictionaryKind = NoneDictionaryKind; |
594 | return this; |
595 | } |
596 | |
597 | size_t Structure::addPropertyWithoutTransition(const Identifier& propertyName, unsigned attributes, JSCell* specificValue) |
598 | { |
599 | ASSERT(!m_enumerationCache); |
600 | |
601 | if (m_specificFunctionThrashCount == maxSpecificFunctionThrashCount) |
602 | specificValue = 0; |
603 | |
604 | materializePropertyMapIfNecessary(); |
605 | |
606 | m_isPinnedPropertyTable = true; |
607 | |
608 | size_t offset = put(propertyName, attributes, specificValue); |
609 | if (propertyStorageSize() > propertyStorageCapacity()) |
610 | growPropertyStorageCapacity(); |
611 | return offset; |
612 | } |
613 | |
614 | size_t Structure::removePropertyWithoutTransition(const Identifier& propertyName) |
615 | { |
616 | ASSERT(isUncacheableDictionary()); |
617 | ASSERT(!m_enumerationCache); |
618 | |
619 | materializePropertyMapIfNecessary(); |
620 | |
621 | m_isPinnedPropertyTable = true; |
622 | size_t offset = remove(propertyName); |
623 | return offset; |
624 | } |
625 | |
626 | #if DUMP_PROPERTYMAP_STATS |
627 | |
628 | static int numProbes; |
629 | static int numCollisions; |
630 | static int numRehashes; |
631 | static int numRemoves; |
632 | |
633 | struct PropertyMapStatisticsExitLogger { |
634 | ~PropertyMapStatisticsExitLogger(); |
635 | }; |
636 | |
637 | static PropertyMapStatisticsExitLogger logger; |
638 | |
639 | PropertyMapStatisticsExitLogger::~PropertyMapStatisticsExitLogger() |
640 | { |
641 | printf("\nJSC::PropertyMap statistics\n\n" ); |
642 | printf("%d probes\n" , numProbes); |
643 | printf("%d collisions (%.1f%%)\n" , numCollisions, 100.0 * numCollisions / numProbes); |
644 | printf("%d rehashes\n" , numRehashes); |
645 | printf("%d removes\n" , numRemoves); |
646 | } |
647 | |
648 | #endif |
649 | |
650 | static const unsigned deletedSentinelIndex = 1; |
651 | |
652 | #if !DO_PROPERTYMAP_CONSTENCY_CHECK |
653 | |
654 | inline void Structure::checkConsistency() |
655 | { |
656 | } |
657 | |
658 | #endif |
659 | |
660 | PropertyMapHashTable* Structure::copyPropertyTable() |
661 | { |
662 | if (!m_propertyTable) |
663 | return 0; |
664 | |
665 | size_t tableSize = PropertyMapHashTable::allocationSize(size: m_propertyTable->size); |
666 | PropertyMapHashTable* newTable = static_cast<PropertyMapHashTable*>(fastMalloc(tableSize)); |
667 | memcpy(dest: newTable, src: m_propertyTable, n: tableSize); |
668 | |
669 | unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount; |
670 | for (unsigned i = 1; i <= entryCount; ++i) { |
671 | if (UString::Rep* key = newTable->entries()[i].key) |
672 | key->ref(); |
673 | } |
674 | |
675 | // Copy the deletedOffsets vector. |
676 | if (m_propertyTable->deletedOffsets) |
677 | newTable->deletedOffsets = new Vector<unsigned>(*m_propertyTable->deletedOffsets); |
678 | |
679 | newTable->anonymousSlotCount = m_propertyTable->anonymousSlotCount; |
680 | return newTable; |
681 | } |
682 | |
683 | size_t Structure::get(const UString::Rep* rep, unsigned& attributes, JSCell*& specificValue) |
684 | { |
685 | materializePropertyMapIfNecessary(); |
686 | if (!m_propertyTable) |
687 | return notFound; |
688 | |
689 | unsigned i = rep->existingHash(); |
690 | |
691 | #if DUMP_PROPERTYMAP_STATS |
692 | ++numProbes; |
693 | #endif |
694 | |
695 | unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask]; |
696 | if (entryIndex == emptyEntryIndex) |
697 | return notFound; |
698 | |
699 | if (rep == m_propertyTable->entries()[entryIndex - 1].key) { |
700 | attributes = m_propertyTable->entries()[entryIndex - 1].attributes; |
701 | specificValue = m_propertyTable->entries()[entryIndex - 1].specificValue; |
702 | return m_propertyTable->entries()[entryIndex - 1].offset; |
703 | } |
704 | |
705 | #if DUMP_PROPERTYMAP_STATS |
706 | ++numCollisions; |
707 | #endif |
708 | |
709 | unsigned k = 1 | doubleHash(key: rep->existingHash()); |
710 | |
711 | while (1) { |
712 | i += k; |
713 | |
714 | #if DUMP_PROPERTYMAP_STATS |
715 | ++numRehashes; |
716 | #endif |
717 | |
718 | entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask]; |
719 | if (entryIndex == emptyEntryIndex) |
720 | return notFound; |
721 | |
722 | if (rep == m_propertyTable->entries()[entryIndex - 1].key) { |
723 | attributes = m_propertyTable->entries()[entryIndex - 1].attributes; |
724 | specificValue = m_propertyTable->entries()[entryIndex - 1].specificValue; |
725 | return m_propertyTable->entries()[entryIndex - 1].offset; |
726 | } |
727 | } |
728 | } |
729 | |
730 | bool Structure::despecifyFunction(const Identifier& propertyName) |
731 | { |
732 | ASSERT(!propertyName.isNull()); |
733 | |
734 | materializePropertyMapIfNecessary(); |
735 | if (!m_propertyTable) |
736 | return false; |
737 | |
738 | UString::Rep* rep = propertyName._ustring.rep(); |
739 | |
740 | unsigned i = rep->existingHash(); |
741 | |
742 | #if DUMP_PROPERTYMAP_STATS |
743 | ++numProbes; |
744 | #endif |
745 | |
746 | unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask]; |
747 | if (entryIndex == emptyEntryIndex) |
748 | return false; |
749 | |
750 | if (rep == m_propertyTable->entries()[entryIndex - 1].key) { |
751 | ASSERT(m_propertyTable->entries()[entryIndex - 1].specificValue); |
752 | m_propertyTable->entries()[entryIndex - 1].specificValue = 0; |
753 | return true; |
754 | } |
755 | |
756 | #if DUMP_PROPERTYMAP_STATS |
757 | ++numCollisions; |
758 | #endif |
759 | |
760 | unsigned k = 1 | doubleHash(key: rep->existingHash()); |
761 | |
762 | while (1) { |
763 | i += k; |
764 | |
765 | #if DUMP_PROPERTYMAP_STATS |
766 | ++numRehashes; |
767 | #endif |
768 | |
769 | entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask]; |
770 | if (entryIndex == emptyEntryIndex) |
771 | return false; |
772 | |
773 | if (rep == m_propertyTable->entries()[entryIndex - 1].key) { |
774 | ASSERT(m_propertyTable->entries()[entryIndex - 1].specificValue); |
775 | m_propertyTable->entries()[entryIndex - 1].specificValue = 0; |
776 | return true; |
777 | } |
778 | } |
779 | } |
780 | |
781 | void Structure::despecifyAllFunctions() |
782 | { |
783 | materializePropertyMapIfNecessary(); |
784 | if (!m_propertyTable) |
785 | return; |
786 | |
787 | unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount; |
788 | for (unsigned i = 1; i <= entryCount; ++i) |
789 | m_propertyTable->entries()[i].specificValue = 0; |
790 | } |
791 | |
792 | size_t Structure::put(const Identifier& propertyName, unsigned attributes, JSCell* specificValue) |
793 | { |
794 | ASSERT(!propertyName.isNull()); |
795 | ASSERT(get(propertyName) == notFound); |
796 | |
797 | checkConsistency(); |
798 | |
799 | if (attributes & DontEnum) |
800 | m_hasNonEnumerableProperties = true; |
801 | |
802 | UString::Rep* rep = propertyName._ustring.rep(); |
803 | |
804 | if (!m_propertyTable) |
805 | createPropertyMapHashTable(); |
806 | |
807 | // FIXME: Consider a fast case for tables with no deleted sentinels. |
808 | |
809 | unsigned i = rep->existingHash(); |
810 | unsigned k = 0; |
811 | bool foundDeletedElement = false; |
812 | unsigned deletedElementIndex = 0; // initialize to make the compiler happy |
813 | |
814 | #if DUMP_PROPERTYMAP_STATS |
815 | ++numProbes; |
816 | #endif |
817 | |
818 | while (1) { |
819 | unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask]; |
820 | if (entryIndex == emptyEntryIndex) |
821 | break; |
822 | |
823 | if (entryIndex == deletedSentinelIndex) { |
824 | // If we find a deleted-element sentinel, remember it for use later. |
825 | if (!foundDeletedElement) { |
826 | foundDeletedElement = true; |
827 | deletedElementIndex = i; |
828 | } |
829 | } |
830 | |
831 | if (k == 0) { |
832 | k = 1 | doubleHash(key: rep->existingHash()); |
833 | #if DUMP_PROPERTYMAP_STATS |
834 | ++numCollisions; |
835 | #endif |
836 | } |
837 | |
838 | i += k; |
839 | |
840 | #if DUMP_PROPERTYMAP_STATS |
841 | ++numRehashes; |
842 | #endif |
843 | } |
844 | |
845 | // Figure out which entry to use. |
846 | unsigned entryIndex = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount + 2; |
847 | if (foundDeletedElement) { |
848 | i = deletedElementIndex; |
849 | --m_propertyTable->deletedSentinelCount; |
850 | |
851 | // Since we're not making the table bigger, we can't use the entry one past |
852 | // the end that we were planning on using, so search backwards for the empty |
853 | // slot that we can use. We know it will be there because we did at least one |
854 | // deletion in the past that left an entry empty. |
855 | while (m_propertyTable->entries()[--entryIndex - 1].key) { } |
856 | } |
857 | |
858 | // Create a new hash table entry. |
859 | m_propertyTable->entryIndices[i & m_propertyTable->sizeMask] = entryIndex; |
860 | |
861 | // Create a new hash table entry. |
862 | rep->ref(); |
863 | m_propertyTable->entries()[entryIndex - 1].key = rep; |
864 | m_propertyTable->entries()[entryIndex - 1].attributes = attributes; |
865 | m_propertyTable->entries()[entryIndex - 1].specificValue = specificValue; |
866 | m_propertyTable->entries()[entryIndex - 1].index = ++m_propertyTable->lastIndexUsed; |
867 | |
868 | unsigned newOffset; |
869 | if (m_propertyTable->deletedOffsets && !m_propertyTable->deletedOffsets->isEmpty()) { |
870 | newOffset = m_propertyTable->deletedOffsets->last(); |
871 | m_propertyTable->deletedOffsets->removeLast(); |
872 | } else |
873 | newOffset = m_propertyTable->keyCount + m_propertyTable->anonymousSlotCount; |
874 | m_propertyTable->entries()[entryIndex - 1].offset = newOffset; |
875 | |
876 | ++m_propertyTable->keyCount; |
877 | |
878 | if ((m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount) * 2 >= m_propertyTable->size) |
879 | expandPropertyMapHashTable(); |
880 | |
881 | checkConsistency(); |
882 | return newOffset; |
883 | } |
884 | |
885 | void Structure::addAnonymousSlots(unsigned count) |
886 | { |
887 | m_propertyTable->anonymousSlotCount += count; |
888 | } |
889 | |
890 | bool Structure::hasTransition(UString::Rep* rep, unsigned attributes) |
891 | { |
892 | return table.hasTransition(key: StructureTransitionTableHash::Key(RefPtr<UString::Rep>(rep), attributes)); |
893 | } |
894 | |
895 | size_t Structure::remove(const Identifier& propertyName) |
896 | { |
897 | ASSERT(!propertyName.isNull()); |
898 | |
899 | checkConsistency(); |
900 | |
901 | UString::Rep* rep = propertyName._ustring.rep(); |
902 | |
903 | if (!m_propertyTable) |
904 | return notFound; |
905 | |
906 | #if DUMP_PROPERTYMAP_STATS |
907 | ++numProbes; |
908 | ++numRemoves; |
909 | #endif |
910 | |
911 | // Find the thing to remove. |
912 | unsigned i = rep->existingHash(); |
913 | unsigned k = 0; |
914 | unsigned entryIndex; |
915 | UString::Rep* key = 0; |
916 | while (1) { |
917 | entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask]; |
918 | if (entryIndex == emptyEntryIndex) |
919 | return notFound; |
920 | |
921 | key = m_propertyTable->entries()[entryIndex - 1].key; |
922 | if (rep == key) |
923 | break; |
924 | |
925 | if (k == 0) { |
926 | k = 1 | doubleHash(key: rep->existingHash()); |
927 | #if DUMP_PROPERTYMAP_STATS |
928 | ++numCollisions; |
929 | #endif |
930 | } |
931 | |
932 | i += k; |
933 | |
934 | #if DUMP_PROPERTYMAP_STATS |
935 | ++numRehashes; |
936 | #endif |
937 | } |
938 | |
939 | // Replace this one element with the deleted sentinel. Also clear out |
940 | // the entry so we can iterate all the entries as needed. |
941 | m_propertyTable->entryIndices[i & m_propertyTable->sizeMask] = deletedSentinelIndex; |
942 | |
943 | size_t offset = m_propertyTable->entries()[entryIndex - 1].offset; |
944 | |
945 | key->deref(); |
946 | m_propertyTable->entries()[entryIndex - 1].key = 0; |
947 | m_propertyTable->entries()[entryIndex - 1].attributes = 0; |
948 | m_propertyTable->entries()[entryIndex - 1].specificValue = 0; |
949 | m_propertyTable->entries()[entryIndex - 1].offset = 0; |
950 | |
951 | if (!m_propertyTable->deletedOffsets) |
952 | m_propertyTable->deletedOffsets = new Vector<unsigned>; |
953 | m_propertyTable->deletedOffsets->append(val: offset); |
954 | |
955 | ASSERT(m_propertyTable->keyCount >= 1); |
956 | --m_propertyTable->keyCount; |
957 | ++m_propertyTable->deletedSentinelCount; |
958 | |
959 | if (m_propertyTable->deletedSentinelCount * 4 >= m_propertyTable->size) |
960 | rehashPropertyMapHashTable(); |
961 | |
962 | checkConsistency(); |
963 | return offset; |
964 | } |
965 | |
966 | void Structure::insertIntoPropertyMapHashTable(const PropertyMapEntry& entry) |
967 | { |
968 | ASSERT(m_propertyTable); |
969 | |
970 | unsigned i = entry.key->existingHash(); |
971 | unsigned k = 0; |
972 | |
973 | #if DUMP_PROPERTYMAP_STATS |
974 | ++numProbes; |
975 | #endif |
976 | |
977 | while (1) { |
978 | unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask]; |
979 | if (entryIndex == emptyEntryIndex) |
980 | break; |
981 | |
982 | if (k == 0) { |
983 | k = 1 | doubleHash(key: entry.key->existingHash()); |
984 | #if DUMP_PROPERTYMAP_STATS |
985 | ++numCollisions; |
986 | #endif |
987 | } |
988 | |
989 | i += k; |
990 | |
991 | #if DUMP_PROPERTYMAP_STATS |
992 | ++numRehashes; |
993 | #endif |
994 | } |
995 | |
996 | unsigned entryIndex = m_propertyTable->keyCount + 2; |
997 | m_propertyTable->entryIndices[i & m_propertyTable->sizeMask] = entryIndex; |
998 | m_propertyTable->entries()[entryIndex - 1] = entry; |
999 | |
1000 | ++m_propertyTable->keyCount; |
1001 | } |
1002 | |
1003 | void Structure::createPropertyMapHashTable() |
1004 | { |
1005 | ASSERT(sizeForKeyCount(7) == newTableSize); |
1006 | createPropertyMapHashTable(newTableSize); |
1007 | } |
1008 | |
1009 | void Structure::createPropertyMapHashTable(unsigned newTableSize) |
1010 | { |
1011 | ASSERT(!m_propertyTable); |
1012 | ASSERT(isPowerOf2(newTableSize)); |
1013 | |
1014 | checkConsistency(); |
1015 | |
1016 | m_propertyTable = static_cast<PropertyMapHashTable*>(fastZeroedMalloc(PropertyMapHashTable::allocationSize(size: newTableSize))); |
1017 | m_propertyTable->size = newTableSize; |
1018 | m_propertyTable->sizeMask = newTableSize - 1; |
1019 | |
1020 | checkConsistency(); |
1021 | } |
1022 | |
1023 | void Structure::expandPropertyMapHashTable() |
1024 | { |
1025 | ASSERT(m_propertyTable); |
1026 | rehashPropertyMapHashTable(newTableSize: m_propertyTable->size * 2); |
1027 | } |
1028 | |
1029 | void Structure::rehashPropertyMapHashTable() |
1030 | { |
1031 | ASSERT(m_propertyTable); |
1032 | ASSERT(m_propertyTable->size); |
1033 | rehashPropertyMapHashTable(newTableSize: m_propertyTable->size); |
1034 | } |
1035 | |
1036 | void Structure::rehashPropertyMapHashTable(unsigned newTableSize) |
1037 | { |
1038 | ASSERT(m_propertyTable); |
1039 | ASSERT(isPowerOf2(newTableSize)); |
1040 | |
1041 | checkConsistency(); |
1042 | |
1043 | PropertyMapHashTable* oldTable = m_propertyTable; |
1044 | |
1045 | m_propertyTable = static_cast<PropertyMapHashTable*>(fastZeroedMalloc(PropertyMapHashTable::allocationSize(size: newTableSize))); |
1046 | m_propertyTable->size = newTableSize; |
1047 | m_propertyTable->sizeMask = newTableSize - 1; |
1048 | m_propertyTable->anonymousSlotCount = oldTable->anonymousSlotCount; |
1049 | |
1050 | unsigned lastIndexUsed = 0; |
1051 | unsigned entryCount = oldTable->keyCount + oldTable->deletedSentinelCount; |
1052 | for (unsigned i = 1; i <= entryCount; ++i) { |
1053 | if (oldTable->entries()[i].key) { |
1054 | lastIndexUsed = max(a: oldTable->entries()[i].index, b: lastIndexUsed); |
1055 | insertIntoPropertyMapHashTable(entry: oldTable->entries()[i]); |
1056 | } |
1057 | } |
1058 | m_propertyTable->lastIndexUsed = lastIndexUsed; |
1059 | m_propertyTable->deletedOffsets = oldTable->deletedOffsets; |
1060 | |
1061 | fastFree(oldTable); |
1062 | |
1063 | checkConsistency(); |
1064 | } |
1065 | |
1066 | int comparePropertyMapEntryIndices(const void* a, const void* b) |
1067 | { |
1068 | unsigned ia = static_cast<PropertyMapEntry* const*>(a)[0]->index; |
1069 | unsigned ib = static_cast<PropertyMapEntry* const*>(b)[0]->index; |
1070 | if (ia < ib) |
1071 | return -1; |
1072 | if (ia > ib) |
1073 | return +1; |
1074 | return 0; |
1075 | } |
1076 | |
1077 | void Structure::getPropertyNames(PropertyNameArray& propertyNames, EnumerationMode mode) |
1078 | { |
1079 | materializePropertyMapIfNecessary(); |
1080 | if (!m_propertyTable) |
1081 | return; |
1082 | |
1083 | if (m_propertyTable->keyCount < tinyMapThreshold) { |
1084 | PropertyMapEntry* a[tinyMapThreshold]; |
1085 | int i = 0; |
1086 | unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount; |
1087 | for (unsigned k = 1; k <= entryCount; k++) { |
1088 | ASSERT(m_hasNonEnumerableProperties || !(m_propertyTable->entries()[k].attributes & DontEnum)); |
1089 | if (m_propertyTable->entries()[k].key && (!(m_propertyTable->entries()[k].attributes & DontEnum) || (mode == IncludeDontEnumProperties))) { |
1090 | PropertyMapEntry* value = &m_propertyTable->entries()[k]; |
1091 | int j; |
1092 | for (j = i - 1; j >= 0 && a[j]->index > value->index; --j) |
1093 | a[j + 1] = a[j]; |
1094 | a[j + 1] = value; |
1095 | ++i; |
1096 | } |
1097 | } |
1098 | if (!propertyNames.size()) { |
1099 | for (int k = 0; k < i; ++k) |
1100 | propertyNames.addKnownUnique(identifier: a[k]->key); |
1101 | } else { |
1102 | for (int k = 0; k < i; ++k) |
1103 | propertyNames.add(a[k]->key); |
1104 | } |
1105 | |
1106 | return; |
1107 | } |
1108 | |
1109 | // Allocate a buffer to use to sort the keys. |
1110 | Vector<PropertyMapEntry*, smallMapThreshold> sortedEnumerables(m_propertyTable->keyCount); |
1111 | |
1112 | // Get pointers to the enumerable entries in the buffer. |
1113 | PropertyMapEntry** p = sortedEnumerables.data(); |
1114 | unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount; |
1115 | for (unsigned i = 1; i <= entryCount; i++) { |
1116 | if (m_propertyTable->entries()[i].key && (!(m_propertyTable->entries()[i].attributes & DontEnum) || (mode == IncludeDontEnumProperties))) |
1117 | *p++ = &m_propertyTable->entries()[i]; |
1118 | } |
1119 | |
1120 | size_t enumerableCount = p - sortedEnumerables.data(); |
1121 | // Sort the entries by index. |
1122 | qsort(base: sortedEnumerables.data(), nmemb: enumerableCount, size: sizeof(PropertyMapEntry*), compar: comparePropertyMapEntryIndices); |
1123 | sortedEnumerables.resize(size: enumerableCount); |
1124 | |
1125 | // Put the keys of the sorted entries into the list. |
1126 | if (!propertyNames.size()) { |
1127 | for (size_t i = 0; i < sortedEnumerables.size(); ++i) |
1128 | propertyNames.addKnownUnique(identifier: sortedEnumerables[i]->key); |
1129 | } else { |
1130 | for (size_t i = 0; i < sortedEnumerables.size(); ++i) |
1131 | propertyNames.add(sortedEnumerables[i]->key); |
1132 | } |
1133 | } |
1134 | |
1135 | #if DO_PROPERTYMAP_CONSTENCY_CHECK |
1136 | |
1137 | void Structure::checkConsistency() |
1138 | { |
1139 | if (!m_propertyTable) |
1140 | return; |
1141 | |
1142 | ASSERT(m_propertyTable->size >= newTableSize); |
1143 | ASSERT(m_propertyTable->sizeMask); |
1144 | ASSERT(m_propertyTable->size == m_propertyTable->sizeMask + 1); |
1145 | ASSERT(!(m_propertyTable->size & m_propertyTable->sizeMask)); |
1146 | |
1147 | ASSERT(m_propertyTable->keyCount <= m_propertyTable->size / 2); |
1148 | ASSERT(m_propertyTable->deletedSentinelCount <= m_propertyTable->size / 4); |
1149 | |
1150 | ASSERT(m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount <= m_propertyTable->size / 2); |
1151 | |
1152 | unsigned indexCount = 0; |
1153 | unsigned deletedIndexCount = 0; |
1154 | for (unsigned a = 0; a != m_propertyTable->size; ++a) { |
1155 | unsigned entryIndex = m_propertyTable->entryIndices[a]; |
1156 | if (entryIndex == emptyEntryIndex) |
1157 | continue; |
1158 | if (entryIndex == deletedSentinelIndex) { |
1159 | ++deletedIndexCount; |
1160 | continue; |
1161 | } |
1162 | ASSERT(entryIndex > deletedSentinelIndex); |
1163 | ASSERT(entryIndex - 1 <= m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount); |
1164 | ++indexCount; |
1165 | |
1166 | for (unsigned b = a + 1; b != m_propertyTable->size; ++b) |
1167 | ASSERT(m_propertyTable->entryIndices[b] != entryIndex); |
1168 | } |
1169 | ASSERT(indexCount == m_propertyTable->keyCount); |
1170 | ASSERT(deletedIndexCount == m_propertyTable->deletedSentinelCount); |
1171 | |
1172 | ASSERT(m_propertyTable->entries()[0].key == 0); |
1173 | |
1174 | unsigned nonEmptyEntryCount = 0; |
1175 | for (unsigned c = 1; c <= m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount; ++c) { |
1176 | ASSERT(m_hasNonEnumerableProperties || !(m_propertyTable->entries()[c].attributes & DontEnum)); |
1177 | UString::Rep* rep = m_propertyTable->entries()[c].key; |
1178 | if (!rep) |
1179 | continue; |
1180 | ++nonEmptyEntryCount; |
1181 | unsigned i = rep->existingHash(); |
1182 | unsigned k = 0; |
1183 | unsigned entryIndex; |
1184 | while (1) { |
1185 | entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask]; |
1186 | ASSERT(entryIndex != emptyEntryIndex); |
1187 | if (rep == m_propertyTable->entries()[entryIndex - 1].key) |
1188 | break; |
1189 | if (k == 0) |
1190 | k = 1 | doubleHash(rep->existingHash()); |
1191 | i += k; |
1192 | } |
1193 | ASSERT(entryIndex == c + 1); |
1194 | } |
1195 | |
1196 | ASSERT(nonEmptyEntryCount == m_propertyTable->keyCount); |
1197 | } |
1198 | |
1199 | #endif // DO_PROPERTYMAP_CONSTENCY_CHECK |
1200 | |
1201 | } // namespace JSC |
1202 | |