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
50using namespace WTF;
51
52namespace 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.
56static 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.
60static const unsigned tinyMapThreshold = 20;
61
62static const unsigned newTableSize = 16;
63
64#ifndef NDEBUG
65static WTF::RefCountedLeakCounter structureCounter("Structure");
66
67#if ENABLE(JSC_MULTIPLE_THREADS)
68static Mutex& ignoreSetMutex = *(new Mutex);
69#endif
70
71static bool shouldIgnoreLeaks;
72static HashSet<Structure*>& ignoreSet = *(new HashSet<Structure*>);
73#endif
74
75#if DUMP_STRUCTURE_ID_STATISTICS
76static HashSet<Structure*>& liveStructureSet = *(new HashSet<Structure*>);
77#endif
78
79static int comparePropertyMapEntryIndices(const void* a, const void* b);
80
81void 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
125Structure::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
156Structure::~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
197void Structure::startIgnoringLeaks()
198{
199#ifndef NDEBUG
200 shouldIgnoreLeaks = true;
201#endif
202}
203
204void Structure::stopIgnoringLeaks()
205{
206#ifndef NDEBUG
207 shouldIgnoreLeaks = false;
208#endif
209}
210
211static 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
218static 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
234static 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
248void 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
289void Structure::growPropertyStorageCapacity()
290{
291 if (m_propertyStorageCapacity == JSObject::inlineStorageCapacity)
292 m_propertyStorageCapacity = JSObject::nonInlineBaseStorageCapacity;
293 else
294 m_propertyStorageCapacity *= 2;
295}
296
297void 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
343PassRefPtr<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
357PassRefPtr<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
411PassRefPtr<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
422PassRefPtr<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
440PassRefPtr<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
466PassRefPtr<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
509PassRefPtr<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
526PassRefPtr<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
544PassRefPtr<Structure> Structure::toCacheableDictionaryTransition(Structure* structure)
545{
546 return toDictionaryTransition(structure, kind: CachedDictionaryKind);
547}
548
549PassRefPtr<Structure> Structure::toUncacheableDictionaryTransition(Structure* structure)
550{
551 return toDictionaryTransition(structure, kind: UncachedDictionaryKind);
552}
553
554PassRefPtr<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
597size_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
614size_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
628static int numProbes;
629static int numCollisions;
630static int numRehashes;
631static int numRemoves;
632
633struct PropertyMapStatisticsExitLogger {
634 ~PropertyMapStatisticsExitLogger();
635};
636
637static PropertyMapStatisticsExitLogger logger;
638
639PropertyMapStatisticsExitLogger::~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
650static const unsigned deletedSentinelIndex = 1;
651
652#if !DO_PROPERTYMAP_CONSTENCY_CHECK
653
654inline void Structure::checkConsistency()
655{
656}
657
658#endif
659
660PropertyMapHashTable* 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
683size_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
730bool 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
781void 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
792size_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
885void Structure::addAnonymousSlots(unsigned count)
886{
887 m_propertyTable->anonymousSlotCount += count;
888}
889
890bool Structure::hasTransition(UString::Rep* rep, unsigned attributes)
891{
892 return table.hasTransition(key: StructureTransitionTableHash::Key(RefPtr<UString::Rep>(rep), attributes));
893}
894
895size_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
966void 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
1003void Structure::createPropertyMapHashTable()
1004{
1005 ASSERT(sizeForKeyCount(7) == newTableSize);
1006 createPropertyMapHashTable(newTableSize);
1007}
1008
1009void 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
1023void Structure::expandPropertyMapHashTable()
1024{
1025 ASSERT(m_propertyTable);
1026 rehashPropertyMapHashTable(newTableSize: m_propertyTable->size * 2);
1027}
1028
1029void Structure::rehashPropertyMapHashTable()
1030{
1031 ASSERT(m_propertyTable);
1032 ASSERT(m_propertyTable->size);
1033 rehashPropertyMapHashTable(newTableSize: m_propertyTable->size);
1034}
1035
1036void 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
1066int 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
1077void 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
1137void 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

source code of qtscript/src/3rdparty/javascriptcore/JavaScriptCore/runtime/Structure.cpp