1 /*
2 * Copyright (C) 2008 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 "PropertyNameArray.h"
32 #include "StructureChain.h"
33 #include "Lookup.h"
34 #include <wtf/RefCountedLeakCounter.h>
35 #include <wtf/RefPtr.h>
36
37 #if ENABLE(JSC_MULTIPLE_THREADS)
38 #include <wtf/Threading.h>
39 #endif
40
41 #define DUMP_STRUCTURE_ID_STATISTICS 0
42
43 #ifndef NDEBUG
44 #define DO_PROPERTYMAP_CONSTENCY_CHECK 0
45 #else
46 #define DO_PROPERTYMAP_CONSTENCY_CHECK 0
47 #endif
48
49 using namespace std;
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;
69 #endif
70
71 static bool shouldIgnoreLeaks;
72 static HashSet<Structure*> ignoreSet;
73 #endif
74
75 #if DUMP_STRUCTURE_ID_STATISTICS
76 static HashSet<Structure*> liveStructureSet;
77 #endif
78
dumpStatistics()79 void Structure::dumpStatistics()
80 {
81 #if DUMP_STRUCTURE_ID_STATISTICS
82 unsigned numberLeaf = 0;
83 unsigned numberUsingSingleSlot = 0;
84 unsigned numberSingletons = 0;
85 unsigned numberWithPropertyMaps = 0;
86 unsigned totalPropertyMapsSize = 0;
87
88 HashSet<Structure*>::const_iterator end = liveStructureSet.end();
89 for (HashSet<Structure*>::const_iterator it = liveStructureSet.begin(); it != end; ++it) {
90 Structure* structure = *it;
91 if (structure->m_usingSingleTransitionSlot) {
92 if (!structure->m_transitions.singleTransition)
93 ++numberLeaf;
94 else
95 ++numberUsingSingleSlot;
96
97 if (!structure->m_previous && !structure->m_transitions.singleTransition)
98 ++numberSingletons;
99 }
100
101 if (structure->m_propertyTable) {
102 ++numberWithPropertyMaps;
103 totalPropertyMapsSize += PropertyMapHashTable::allocationSize(structure->m_propertyTable->size);
104 if (structure->m_propertyTable->deletedOffsets)
105 totalPropertyMapsSize += (structure->m_propertyTable->deletedOffsets->capacity() * sizeof(unsigned));
106 }
107 }
108
109 printf("Number of live Structures: %d\n", liveStructureSet.size());
110 printf("Number of Structures using the single item optimization for transition map: %d\n", numberUsingSingleSlot);
111 printf("Number of Structures that are leaf nodes: %d\n", numberLeaf);
112 printf("Number of Structures that singletons: %d\n", numberSingletons);
113 printf("Number of Structures with PropertyMaps: %d\n", numberWithPropertyMaps);
114
115 printf("Size of a single Structures: %d\n", static_cast<unsigned>(sizeof(Structure)));
116 printf("Size of sum of all property maps: %d\n", totalPropertyMapsSize);
117 printf("Size of average of all property maps: %f\n", static_cast<double>(totalPropertyMapsSize) / static_cast<double>(liveStructureSet.size()));
118 #else
119 printf("Dumping Structure statistics is not enabled.\n");
120 #endif
121 }
122
Structure(JSValuePtr prototype,const TypeInfo & typeInfo)123 Structure::Structure(JSValuePtr prototype, const TypeInfo& typeInfo)
124 : m_typeInfo(typeInfo)
125 , m_prototype(prototype)
126 , m_cachedPrototypeChain(0)
127 , m_previous(0)
128 , m_nameInPrevious(0)
129 , m_propertyTable(0)
130 , m_propertyStorageCapacity(JSObject::inlineStorageCapacity)
131 , m_offset(noOffset)
132 , m_isDictionary(false)
133 , m_isPinnedPropertyTable(false)
134 , m_hasGetterSetterProperties(false)
135 , m_usingSingleTransitionSlot(true)
136 , m_attributesInPrevious(0)
137 {
138 ASSERT(m_prototype);
139 ASSERT(m_prototype.isObject() || m_prototype.isNull());
140
141 m_transitions.singleTransition = 0;
142
143 #ifndef NDEBUG
144 #if ENABLE(JSC_MULTIPLE_THREADS)
145 MutexLocker protect(ignoreSetMutex);
146 #endif
147 if (shouldIgnoreLeaks)
148 ignoreSet.add(this);
149 else
150 structureCounter.increment();
151 #endif
152
153 #if DUMP_STRUCTURE_ID_STATISTICS
154 liveStructureSet.add(this);
155 #endif
156 }
157
~Structure()158 Structure::~Structure()
159 {
160 if (m_previous) {
161 if (m_previous->m_usingSingleTransitionSlot) {
162 m_previous->m_transitions.singleTransition = 0;
163 } else {
164 ASSERT(m_previous->m_transitions.table->contains(make_pair(m_nameInPrevious.get(), m_attributesInPrevious)));
165 m_previous->m_transitions.table->remove(make_pair(m_nameInPrevious.get(), m_attributesInPrevious));
166 }
167 }
168
169 if (m_cachedPropertyNameArrayData)
170 m_cachedPropertyNameArrayData->setCachedStructure(0);
171
172 if (!m_usingSingleTransitionSlot)
173 delete m_transitions.table;
174
175 if (m_propertyTable) {
176 unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount;
177 for (unsigned i = 1; i <= entryCount; i++) {
178 if (UString::Rep* key = m_propertyTable->entries()[i].key)
179 key->deref();
180 }
181
182 delete m_propertyTable->deletedOffsets;
183 fastFree(m_propertyTable);
184 }
185
186 #ifndef NDEBUG
187 #if ENABLE(JSC_MULTIPLE_THREADS)
188 MutexLocker protect(ignoreSetMutex);
189 #endif
190 HashSet<Structure*>::iterator it = ignoreSet.find(this);
191 if (it != ignoreSet.end())
192 ignoreSet.remove(it);
193 else
194 structureCounter.decrement();
195 #endif
196
197 #if DUMP_STRUCTURE_ID_STATISTICS
198 liveStructureSet.remove(this);
199 #endif
200 }
201
startIgnoringLeaks()202 void Structure::startIgnoringLeaks()
203 {
204 #ifndef NDEBUG
205 shouldIgnoreLeaks = true;
206 #endif
207 }
208
stopIgnoringLeaks()209 void Structure::stopIgnoringLeaks()
210 {
211 #ifndef NDEBUG
212 shouldIgnoreLeaks = false;
213 #endif
214 }
215
isPowerOf2(unsigned v)216 static bool isPowerOf2(unsigned v)
217 {
218 // Taken from http://www.cs.utk.edu/~vose/c-stuff/bithacks.html
219
220 return !(v & (v - 1)) && v;
221 }
222
nextPowerOf2(unsigned v)223 static unsigned nextPowerOf2(unsigned v)
224 {
225 // Taken from http://www.cs.utk.edu/~vose/c-stuff/bithacks.html
226 // Devised by Sean Anderson, Sepember 14, 2001
227
228 v--;
229 v |= v >> 1;
230 v |= v >> 2;
231 v |= v >> 4;
232 v |= v >> 8;
233 v |= v >> 16;
234 v++;
235
236 return v;
237 }
238
sizeForKeyCount(size_t keyCount)239 static unsigned sizeForKeyCount(size_t keyCount)
240 {
241 if (keyCount == notFound)
242 return newTableSize;
243
244 if (keyCount < 8)
245 return newTableSize;
246
247 if (isPowerOf2(keyCount))
248 return keyCount * 4;
249
250 return nextPowerOf2(keyCount) * 2;
251 }
252
materializePropertyMap()253 void Structure::materializePropertyMap()
254 {
255 ASSERT(!m_propertyTable);
256
257 Vector<Structure*, 8> structures;
258 structures.append(this);
259
260 Structure* structure = this;
261
262 // Search for the last Structure with a property table.
263 while ((structure = structure->previousID())) {
264 if (structure->m_isPinnedPropertyTable) {
265 ASSERT(structure->m_propertyTable);
266 ASSERT(!structure->m_previous);
267
268 m_propertyTable = structure->copyPropertyTable();
269 break;
270 }
271
272 structures.append(structure);
273 }
274
275 if (!m_propertyTable)
276 createPropertyMapHashTable(sizeForKeyCount(m_offset + 1));
277 else {
278 if (sizeForKeyCount(m_offset + 1) > m_propertyTable->size)
279 rehashPropertyMapHashTable(sizeForKeyCount(m_offset + 1)); // This could be made more efficient by combining with the copy above.
280 }
281
282 for (ptrdiff_t i = structures.size() - 2; i >= 0; --i) {
283 structure = structures[i];
284 structure->m_nameInPrevious->ref();
285 PropertyMapEntry entry(structure->m_nameInPrevious.get(), structure->m_offset, structure->m_attributesInPrevious, ++m_propertyTable->lastIndexUsed);
286 insertIntoPropertyMapHashTable(entry);
287 }
288 }
289
getEnumerablePropertyNames(ExecState * exec,PropertyNameArray & propertyNames,JSObject * baseObject)290 void Structure::getEnumerablePropertyNames(ExecState* exec, PropertyNameArray& propertyNames, JSObject* baseObject)
291 {
292 bool shouldCache = propertyNames.cacheable() && !(propertyNames.size() || m_isDictionary);
293
294 if (shouldCache) {
295 if (m_cachedPropertyNameArrayData) {
296 if (structureChainsAreEqual(m_cachedPropertyNameArrayData->cachedPrototypeChain(), cachedPrototypeChain())) {
297 propertyNames.setData(m_cachedPropertyNameArrayData);
298 return;
299 }
300 }
301 propertyNames.setCacheable(false);
302 }
303
304 getEnumerablePropertyNamesInternal(propertyNames);
305
306 // Add properties from the static hashtables of properties
307 for (const ClassInfo* info = baseObject->classInfo(); info; info = info->parentClass) {
308 const HashTable* table = info->propHashTable(exec);
309 if (!table)
310 continue;
311 table->initializeIfNeeded(exec);
312 ASSERT(table->table);
313 #if ENABLE(PERFECT_HASH_SIZE)
314 int hashSizeMask = table->hashSizeMask;
315 #else
316 int hashSizeMask = table->compactSize - 1;
317 #endif
318 const HashEntry* entry = table->table;
319 for (int i = 0; i <= hashSizeMask; ++i, ++entry) {
320 if (entry->key() && !(entry->attributes() & DontEnum))
321 propertyNames.add(entry->key());
322 }
323 }
324
325 if (m_prototype.isObject())
326 asObject(m_prototype)->getPropertyNames(exec, propertyNames);
327
328 if (shouldCache) {
329 if (m_cachedPropertyNameArrayData)
330 m_cachedPropertyNameArrayData->setCachedStructure(0);
331
332 m_cachedPropertyNameArrayData = propertyNames.data();
333
334 StructureChain* chain = cachedPrototypeChain();
335 if (!chain)
336 chain = createCachedPrototypeChain();
337 m_cachedPropertyNameArrayData->setCachedPrototypeChain(chain);
338 m_cachedPropertyNameArrayData->setCachedStructure(this);
339 }
340 }
341
clearEnumerationCache()342 void Structure::clearEnumerationCache()
343 {
344 if (m_cachedPropertyNameArrayData)
345 m_cachedPropertyNameArrayData->setCachedStructure(0);
346 m_cachedPropertyNameArrayData.clear();
347 }
348
growPropertyStorageCapacity()349 void Structure::growPropertyStorageCapacity()
350 {
351 if (m_propertyStorageCapacity == JSObject::inlineStorageCapacity)
352 m_propertyStorageCapacity = JSObject::nonInlineBaseStorageCapacity;
353 else
354 m_propertyStorageCapacity *= 2;
355 }
356
addPropertyTransitionToExistingStructure(Structure * structure,const Identifier & propertyName,unsigned attributes,size_t & offset)357 PassRefPtr<Structure> Structure::addPropertyTransitionToExistingStructure(Structure* structure, const Identifier& propertyName, unsigned attributes, size_t& offset)
358 {
359 ASSERT(!structure->m_isDictionary);
360 ASSERT(structure->typeInfo().type() == ObjectType);
361
362 if (structure->m_usingSingleTransitionSlot) {
363 Structure* existingTransition = structure->m_transitions.singleTransition;
364 if (existingTransition && existingTransition->m_nameInPrevious.get() == propertyName.ustring().rep() && existingTransition->m_attributesInPrevious == attributes) {
365 ASSERT(structure->m_transitions.singleTransition->m_offset != noOffset);
366 offset = structure->m_transitions.singleTransition->m_offset;
367 return existingTransition;
368 }
369 } else {
370 if (Structure* existingTransition = structure->m_transitions.table->get(make_pair(propertyName.ustring().rep(), attributes))) {
371 ASSERT(existingTransition->m_offset != noOffset);
372 offset = existingTransition->m_offset;
373 return existingTransition;
374 }
375 }
376
377 return 0;
378 }
379
addPropertyTransition(Structure * structure,const Identifier & propertyName,unsigned attributes,size_t & offset)380 PassRefPtr<Structure> Structure::addPropertyTransition(Structure* structure, const Identifier& propertyName, unsigned attributes, size_t& offset)
381 {
382 ASSERT(!structure->m_isDictionary);
383 ASSERT(structure->typeInfo().type() == ObjectType);
384 ASSERT(!Structure::addPropertyTransitionToExistingStructure(structure, propertyName, attributes, offset));
385
386 if (structure->transitionCount() > s_maxTransitionLength) {
387 RefPtr<Structure> transition = toDictionaryTransition(structure);
388 offset = transition->put(propertyName, attributes);
389 if (transition->propertyStorageSize() > transition->propertyStorageCapacity())
390 transition->growPropertyStorageCapacity();
391 return transition.release();
392 }
393
394 RefPtr<Structure> transition = create(structure->m_prototype, structure->typeInfo());
395 transition->m_cachedPrototypeChain = structure->m_cachedPrototypeChain;
396 transition->m_previous = structure;
397 transition->m_nameInPrevious = propertyName.ustring().rep();
398 transition->m_attributesInPrevious = attributes;
399 transition->m_propertyStorageCapacity = structure->m_propertyStorageCapacity;
400 transition->m_hasGetterSetterProperties = structure->m_hasGetterSetterProperties;
401
402 if (structure->m_propertyTable) {
403 if (structure->m_isPinnedPropertyTable)
404 transition->m_propertyTable = structure->copyPropertyTable();
405 else {
406 transition->m_propertyTable = structure->m_propertyTable;
407 structure->m_propertyTable = 0;
408 }
409 } else {
410 if (structure->m_previous)
411 transition->materializePropertyMap();
412 else
413 transition->createPropertyMapHashTable();
414 }
415
416 offset = transition->put(propertyName, attributes);
417 if (transition->propertyStorageSize() > transition->propertyStorageCapacity())
418 transition->growPropertyStorageCapacity();
419
420 transition->m_offset = offset;
421
422 if (structure->m_usingSingleTransitionSlot) {
423 if (!structure->m_transitions.singleTransition) {
424 structure->m_transitions.singleTransition = transition.get();
425 return transition.release();
426 }
427
428 Structure* existingTransition = structure->m_transitions.singleTransition;
429 structure->m_usingSingleTransitionSlot = false;
430 StructureTransitionTable* transitionTable = new StructureTransitionTable;
431 structure->m_transitions.table = transitionTable;
432 transitionTable->add(make_pair(existingTransition->m_nameInPrevious.get(), existingTransition->m_attributesInPrevious), existingTransition);
433 }
434 structure->m_transitions.table->add(make_pair(propertyName.ustring().rep(), attributes), transition.get());
435 return transition.release();
436 }
437
removePropertyTransition(Structure * structure,const Identifier & propertyName,size_t & offset)438 PassRefPtr<Structure> Structure::removePropertyTransition(Structure* structure, const Identifier& propertyName, size_t& offset)
439 {
440 ASSERT(!structure->m_isDictionary);
441
442 RefPtr<Structure> transition = toDictionaryTransition(structure);
443
444 offset = transition->remove(propertyName);
445
446 return transition.release();
447 }
448
changePrototypeTransition(Structure * structure,JSValuePtr prototype)449 PassRefPtr<Structure> Structure::changePrototypeTransition(Structure* structure, JSValuePtr prototype)
450 {
451 RefPtr<Structure> transition = create(prototype, structure->typeInfo());
452
453 transition->m_propertyStorageCapacity = structure->m_propertyStorageCapacity;
454 transition->m_hasGetterSetterProperties = structure->m_hasGetterSetterProperties;
455
456 // Don't set m_offset, as one can not transition to this.
457
458 structure->materializePropertyMapIfNecessary();
459 transition->m_propertyTable = structure->copyPropertyTable();
460 transition->m_isPinnedPropertyTable = true;
461
462 return transition.release();
463 }
464
getterSetterTransition(Structure * structure)465 PassRefPtr<Structure> Structure::getterSetterTransition(Structure* structure)
466 {
467 RefPtr<Structure> transition = create(structure->storedPrototype(), structure->typeInfo());
468 transition->m_propertyStorageCapacity = structure->m_propertyStorageCapacity;
469 transition->m_hasGetterSetterProperties = transition->m_hasGetterSetterProperties;
470
471 // Don't set m_offset, as one can not transition to this.
472
473 structure->materializePropertyMapIfNecessary();
474 transition->m_propertyTable = structure->copyPropertyTable();
475 transition->m_isPinnedPropertyTable = true;
476
477 return transition.release();
478 }
479
toDictionaryTransition(Structure * structure)480 PassRefPtr<Structure> Structure::toDictionaryTransition(Structure* structure)
481 {
482 ASSERT(!structure->m_isDictionary);
483
484 RefPtr<Structure> transition = create(structure->m_prototype, structure->typeInfo());
485 transition->m_isDictionary = true;
486 transition->m_propertyStorageCapacity = structure->m_propertyStorageCapacity;
487 transition->m_hasGetterSetterProperties = structure->m_hasGetterSetterProperties;
488
489 structure->materializePropertyMapIfNecessary();
490 transition->m_propertyTable = structure->copyPropertyTable();
491 transition->m_isPinnedPropertyTable = true;
492
493 return transition.release();
494 }
495
fromDictionaryTransition(Structure * structure)496 PassRefPtr<Structure> Structure::fromDictionaryTransition(Structure* structure)
497 {
498 ASSERT(structure->m_isDictionary);
499
500 // Since dictionary Structures are not shared, and no opcodes specialize
501 // for them, we don't need to allocate a new Structure when transitioning
502 // to non-dictionary status.
503
504 // FIMXE: We can make this more efficient by canonicalizing the Structure (draining the
505 // deleted offsets vector) before transitioning from dictionary.
506 if (!structure->m_propertyTable || !structure->m_propertyTable->deletedOffsets || structure->m_propertyTable->deletedOffsets->isEmpty())
507 structure->m_isDictionary = false;
508
509 return structure;
510 }
511
addPropertyWithoutTransition(const Identifier & propertyName,unsigned attributes)512 size_t Structure::addPropertyWithoutTransition(const Identifier& propertyName, unsigned attributes)
513 {
514 ASSERT(!m_transitions.singleTransition);
515
516 materializePropertyMapIfNecessary();
517
518 m_isPinnedPropertyTable = true;
519 size_t offset = put(propertyName, attributes);
520 if (propertyStorageSize() > propertyStorageCapacity())
521 growPropertyStorageCapacity();
522 clearEnumerationCache();
523 return offset;
524 }
525
removePropertyWithoutTransition(const Identifier & propertyName)526 size_t Structure::removePropertyWithoutTransition(const Identifier& propertyName)
527 {
528 ASSERT(!m_transitions.singleTransition);
529 ASSERT(m_isDictionary);
530
531 materializePropertyMapIfNecessary();
532
533 m_isPinnedPropertyTable = true;
534 size_t offset = remove(propertyName);
535 clearEnumerationCache();
536 return offset;
537 }
538
createCachedPrototypeChain()539 StructureChain* Structure::createCachedPrototypeChain()
540 {
541 ASSERT(typeInfo().type() == ObjectType);
542 ASSERT(!m_cachedPrototypeChain);
543
544 JSValuePtr prototype = storedPrototype();
545 if (!prototype.isCell())
546 return 0;
547
548 RefPtr<StructureChain> chain = StructureChain::create(asObject(prototype)->structure());
549 setCachedPrototypeChain(chain.release());
550 return cachedPrototypeChain();
551 }
552
553 #if DUMP_PROPERTYMAP_STATS
554
555 static int numProbes;
556 static int numCollisions;
557 static int numRehashes;
558 static int numRemoves;
559
560 struct PropertyMapStatisticsExitLogger {
561 ~PropertyMapStatisticsExitLogger();
562 };
563
564 static PropertyMapStatisticsExitLogger logger;
565
~PropertyMapStatisticsExitLogger()566 PropertyMapStatisticsExitLogger::~PropertyMapStatisticsExitLogger()
567 {
568 printf("\nJSC::PropertyMap statistics\n\n");
569 printf("%d probes\n", numProbes);
570 printf("%d collisions (%.1f%%)\n", numCollisions, 100.0 * numCollisions / numProbes);
571 printf("%d rehashes\n", numRehashes);
572 printf("%d removes\n", numRemoves);
573 }
574
575 #endif
576
577 static const unsigned deletedSentinelIndex = 1;
578
579 #if !DO_PROPERTYMAP_CONSTENCY_CHECK
580
checkConsistency()581 inline void Structure::checkConsistency()
582 {
583 }
584
585 #endif
586
copyPropertyTable()587 PropertyMapHashTable* Structure::copyPropertyTable()
588 {
589 if (!m_propertyTable)
590 return 0;
591
592 size_t tableSize = PropertyMapHashTable::allocationSize(m_propertyTable->size);
593 PropertyMapHashTable* newTable = static_cast<PropertyMapHashTable*>(fastMalloc(tableSize));
594 memcpy(newTable, m_propertyTable, tableSize);
595
596 unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount;
597 for (unsigned i = 1; i <= entryCount; ++i) {
598 if (UString::Rep* key = newTable->entries()[i].key)
599 key->ref();
600 }
601
602 // Copy the deletedOffsets vector.
603 if (m_propertyTable->deletedOffsets)
604 newTable->deletedOffsets = new Vector<unsigned>(*m_propertyTable->deletedOffsets);
605
606 return newTable;
607 }
608
get(const Identifier & propertyName,unsigned & attributes)609 size_t Structure::get(const Identifier& propertyName, unsigned& attributes)
610 {
611 ASSERT(!propertyName.isNull());
612
613 materializePropertyMapIfNecessary();
614 if (!m_propertyTable)
615 return notFound;
616
617 UString::Rep* rep = propertyName._ustring.rep();
618
619 unsigned i = rep->computedHash();
620
621 #if DUMP_PROPERTYMAP_STATS
622 ++numProbes;
623 #endif
624
625 unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
626 if (entryIndex == emptyEntryIndex)
627 return notFound;
628
629 if (rep == m_propertyTable->entries()[entryIndex - 1].key) {
630 attributes = m_propertyTable->entries()[entryIndex - 1].attributes;
631 return m_propertyTable->entries()[entryIndex - 1].offset;
632 }
633
634 #if DUMP_PROPERTYMAP_STATS
635 ++numCollisions;
636 #endif
637
638 unsigned k = 1 | doubleHash(rep->computedHash());
639
640 while (1) {
641 i += k;
642
643 #if DUMP_PROPERTYMAP_STATS
644 ++numRehashes;
645 #endif
646
647 entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
648 if (entryIndex == emptyEntryIndex)
649 return notFound;
650
651 if (rep == m_propertyTable->entries()[entryIndex - 1].key) {
652 attributes = m_propertyTable->entries()[entryIndex - 1].attributes;
653 return m_propertyTable->entries()[entryIndex - 1].offset;
654 }
655 }
656 }
657
put(const Identifier & propertyName,unsigned attributes)658 size_t Structure::put(const Identifier& propertyName, unsigned attributes)
659 {
660 ASSERT(!propertyName.isNull());
661 ASSERT(get(propertyName) == notFound);
662
663 checkConsistency();
664
665 UString::Rep* rep = propertyName._ustring.rep();
666
667 if (!m_propertyTable)
668 createPropertyMapHashTable();
669
670 // FIXME: Consider a fast case for tables with no deleted sentinels.
671
672 unsigned i = rep->computedHash();
673 unsigned k = 0;
674 bool foundDeletedElement = false;
675 unsigned deletedElementIndex = 0; // initialize to make the compiler happy
676
677 #if DUMP_PROPERTYMAP_STATS
678 ++numProbes;
679 #endif
680
681 while (1) {
682 unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
683 if (entryIndex == emptyEntryIndex)
684 break;
685
686 if (entryIndex == deletedSentinelIndex) {
687 // If we find a deleted-element sentinel, remember it for use later.
688 if (!foundDeletedElement) {
689 foundDeletedElement = true;
690 deletedElementIndex = i;
691 }
692 }
693
694 if (k == 0) {
695 k = 1 | doubleHash(rep->computedHash());
696 #if DUMP_PROPERTYMAP_STATS
697 ++numCollisions;
698 #endif
699 }
700
701 i += k;
702
703 #if DUMP_PROPERTYMAP_STATS
704 ++numRehashes;
705 #endif
706 }
707
708 // Figure out which entry to use.
709 unsigned entryIndex = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount + 2;
710 if (foundDeletedElement) {
711 i = deletedElementIndex;
712 --m_propertyTable->deletedSentinelCount;
713
714 // Since we're not making the table bigger, we can't use the entry one past
715 // the end that we were planning on using, so search backwards for the empty
716 // slot that we can use. We know it will be there because we did at least one
717 // deletion in the past that left an entry empty.
718 while (m_propertyTable->entries()[--entryIndex - 1].key) { }
719 }
720
721 // Create a new hash table entry.
722 m_propertyTable->entryIndices[i & m_propertyTable->sizeMask] = entryIndex;
723
724 // Create a new hash table entry.
725 rep->ref();
726 m_propertyTable->entries()[entryIndex - 1].key = rep;
727 m_propertyTable->entries()[entryIndex - 1].attributes = attributes;
728 m_propertyTable->entries()[entryIndex - 1].index = ++m_propertyTable->lastIndexUsed;
729
730 unsigned newOffset;
731 if (m_propertyTable->deletedOffsets && !m_propertyTable->deletedOffsets->isEmpty()) {
732 newOffset = m_propertyTable->deletedOffsets->last();
733 m_propertyTable->deletedOffsets->removeLast();
734 } else
735 newOffset = m_propertyTable->keyCount;
736 m_propertyTable->entries()[entryIndex - 1].offset = newOffset;
737
738 ++m_propertyTable->keyCount;
739
740 if ((m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount) * 2 >= m_propertyTable->size)
741 expandPropertyMapHashTable();
742
743 checkConsistency();
744 return newOffset;
745 }
746
remove(const Identifier & propertyName)747 size_t Structure::remove(const Identifier& propertyName)
748 {
749 ASSERT(!propertyName.isNull());
750
751 checkConsistency();
752
753 UString::Rep* rep = propertyName._ustring.rep();
754
755 if (!m_propertyTable)
756 return notFound;
757
758 #if DUMP_PROPERTYMAP_STATS
759 ++numProbes;
760 ++numRemoves;
761 #endif
762
763 // Find the thing to remove.
764 unsigned i = rep->computedHash();
765 unsigned k = 0;
766 unsigned entryIndex;
767 UString::Rep* key = 0;
768 while (1) {
769 entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
770 if (entryIndex == emptyEntryIndex)
771 return notFound;
772
773 key = m_propertyTable->entries()[entryIndex - 1].key;
774 if (rep == key)
775 break;
776
777 if (k == 0) {
778 k = 1 | doubleHash(rep->computedHash());
779 #if DUMP_PROPERTYMAP_STATS
780 ++numCollisions;
781 #endif
782 }
783
784 i += k;
785
786 #if DUMP_PROPERTYMAP_STATS
787 ++numRehashes;
788 #endif
789 }
790
791 // Replace this one element with the deleted sentinel. Also clear out
792 // the entry so we can iterate all the entries as needed.
793 m_propertyTable->entryIndices[i & m_propertyTable->sizeMask] = deletedSentinelIndex;
794
795 size_t offset = m_propertyTable->entries()[entryIndex - 1].offset;
796
797 key->deref();
798 m_propertyTable->entries()[entryIndex - 1].key = 0;
799 m_propertyTable->entries()[entryIndex - 1].attributes = 0;
800 m_propertyTable->entries()[entryIndex - 1].offset = 0;
801
802 if (!m_propertyTable->deletedOffsets)
803 m_propertyTable->deletedOffsets = new Vector<unsigned>;
804 m_propertyTable->deletedOffsets->append(offset);
805
806 ASSERT(m_propertyTable->keyCount >= 1);
807 --m_propertyTable->keyCount;
808 ++m_propertyTable->deletedSentinelCount;
809
810 if (m_propertyTable->deletedSentinelCount * 4 >= m_propertyTable->size)
811 rehashPropertyMapHashTable();
812
813 checkConsistency();
814 return offset;
815 }
816
insertIntoPropertyMapHashTable(const PropertyMapEntry & entry)817 void Structure::insertIntoPropertyMapHashTable(const PropertyMapEntry& entry)
818 {
819 ASSERT(m_propertyTable);
820
821 unsigned i = entry.key->computedHash();
822 unsigned k = 0;
823
824 #if DUMP_PROPERTYMAP_STATS
825 ++numProbes;
826 #endif
827
828 while (1) {
829 unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
830 if (entryIndex == emptyEntryIndex)
831 break;
832
833 if (k == 0) {
834 k = 1 | doubleHash(entry.key->computedHash());
835 #if DUMP_PROPERTYMAP_STATS
836 ++numCollisions;
837 #endif
838 }
839
840 i += k;
841
842 #if DUMP_PROPERTYMAP_STATS
843 ++numRehashes;
844 #endif
845 }
846
847 unsigned entryIndex = m_propertyTable->keyCount + 2;
848 m_propertyTable->entryIndices[i & m_propertyTable->sizeMask] = entryIndex;
849 m_propertyTable->entries()[entryIndex - 1] = entry;
850
851 ++m_propertyTable->keyCount;
852 }
853
createPropertyMapHashTable()854 void Structure::createPropertyMapHashTable()
855 {
856 ASSERT(sizeForKeyCount(7) == newTableSize);
857 createPropertyMapHashTable(newTableSize);
858 }
859
createPropertyMapHashTable(unsigned newTableSize)860 void Structure::createPropertyMapHashTable(unsigned newTableSize)
861 {
862 ASSERT(!m_propertyTable);
863 ASSERT(isPowerOf2(newTableSize));
864
865 checkConsistency();
866
867 m_propertyTable = static_cast<PropertyMapHashTable*>(fastZeroedMalloc(PropertyMapHashTable::allocationSize(newTableSize)));
868 m_propertyTable->size = newTableSize;
869 m_propertyTable->sizeMask = newTableSize - 1;
870
871 checkConsistency();
872 }
873
expandPropertyMapHashTable()874 void Structure::expandPropertyMapHashTable()
875 {
876 ASSERT(m_propertyTable);
877 rehashPropertyMapHashTable(m_propertyTable->size * 2);
878 }
879
rehashPropertyMapHashTable()880 void Structure::rehashPropertyMapHashTable()
881 {
882 ASSERT(m_propertyTable);
883 ASSERT(m_propertyTable->size);
884 rehashPropertyMapHashTable(m_propertyTable->size);
885 }
886
rehashPropertyMapHashTable(unsigned newTableSize)887 void Structure::rehashPropertyMapHashTable(unsigned newTableSize)
888 {
889 ASSERT(m_propertyTable);
890 ASSERT(isPowerOf2(newTableSize));
891
892 checkConsistency();
893
894 PropertyMapHashTable* oldTable = m_propertyTable;
895
896 m_propertyTable = static_cast<PropertyMapHashTable*>(fastZeroedMalloc(PropertyMapHashTable::allocationSize(newTableSize)));
897 m_propertyTable->size = newTableSize;
898 m_propertyTable->sizeMask = newTableSize - 1;
899
900 unsigned lastIndexUsed = 0;
901 unsigned entryCount = oldTable->keyCount + oldTable->deletedSentinelCount;
902 for (unsigned i = 1; i <= entryCount; ++i) {
903 if (oldTable->entries()[i].key) {
904 lastIndexUsed = max(oldTable->entries()[i].index, lastIndexUsed);
905 insertIntoPropertyMapHashTable(oldTable->entries()[i]);
906 }
907 }
908 m_propertyTable->lastIndexUsed = lastIndexUsed;
909 m_propertyTable->deletedOffsets = oldTable->deletedOffsets;
910
911 fastFree(oldTable);
912
913 checkConsistency();
914 }
915
comparePropertyMapEntryIndices(const void * a,const void * b)916 static int comparePropertyMapEntryIndices(const void* a, const void* b)
917 {
918 unsigned ia = static_cast<PropertyMapEntry* const*>(a)[0]->index;
919 unsigned ib = static_cast<PropertyMapEntry* const*>(b)[0]->index;
920 if (ia < ib)
921 return -1;
922 if (ia > ib)
923 return +1;
924 return 0;
925 }
926
getEnumerablePropertyNamesInternal(PropertyNameArray & propertyNames)927 void Structure::getEnumerablePropertyNamesInternal(PropertyNameArray& propertyNames)
928 {
929 materializePropertyMapIfNecessary();
930 if (!m_propertyTable)
931 return;
932
933 if (m_propertyTable->keyCount < tinyMapThreshold) {
934 PropertyMapEntry* a[tinyMapThreshold];
935 int i = 0;
936 unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount;
937 for (unsigned k = 1; k <= entryCount; k++) {
938 if (m_propertyTable->entries()[k].key && !(m_propertyTable->entries()[k].attributes & DontEnum)) {
939 PropertyMapEntry* value = &m_propertyTable->entries()[k];
940 int j;
941 for (j = i - 1; j >= 0 && a[j]->index > value->index; --j)
942 a[j + 1] = a[j];
943 a[j + 1] = value;
944 ++i;
945 }
946 }
947 if (!propertyNames.size()) {
948 for (int k = 0; k < i; ++k)
949 propertyNames.addKnownUnique(a[k]->key);
950 } else {
951 for (int k = 0; k < i; ++k)
952 propertyNames.add(a[k]->key);
953 }
954
955 return;
956 }
957
958 // Allocate a buffer to use to sort the keys.
959 Vector<PropertyMapEntry*, smallMapThreshold> sortedEnumerables(m_propertyTable->keyCount);
960
961 // Get pointers to the enumerable entries in the buffer.
962 PropertyMapEntry** p = sortedEnumerables.data();
963 unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount;
964 for (unsigned i = 1; i <= entryCount; i++) {
965 if (m_propertyTable->entries()[i].key && !(m_propertyTable->entries()[i].attributes & DontEnum))
966 *p++ = &m_propertyTable->entries()[i];
967 }
968
969 size_t enumerableCount = p - sortedEnumerables.data();
970 // Sort the entries by index.
971 qsort(sortedEnumerables.data(), enumerableCount, sizeof(PropertyMapEntry*), comparePropertyMapEntryIndices);
972 sortedEnumerables.resize(enumerableCount);
973
974 // Put the keys of the sorted entries into the list.
975 if (!propertyNames.size()) {
976 for (size_t i = 0; i < sortedEnumerables.size(); ++i)
977 propertyNames.addKnownUnique(sortedEnumerables[i]->key);
978 } else {
979 for (size_t i = 0; i < sortedEnumerables.size(); ++i)
980 propertyNames.add(sortedEnumerables[i]->key);
981 }
982 }
983
984 #if DO_PROPERTYMAP_CONSTENCY_CHECK
985
checkConsistency()986 void Structure::checkConsistency()
987 {
988 if (!m_propertyTable)
989 return;
990
991 ASSERT(m_propertyTable->size >= newTableSize);
992 ASSERT(m_propertyTable->sizeMask);
993 ASSERT(m_propertyTable->size == m_propertyTable->sizeMask + 1);
994 ASSERT(!(m_propertyTable->size & m_propertyTable->sizeMask));
995
996 ASSERT(m_propertyTable->keyCount <= m_propertyTable->size / 2);
997 ASSERT(m_propertyTable->deletedSentinelCount <= m_propertyTable->size / 4);
998
999 ASSERT(m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount <= m_propertyTable->size / 2);
1000
1001 unsigned indexCount = 0;
1002 unsigned deletedIndexCount = 0;
1003 for (unsigned a = 0; a != m_propertyTable->size; ++a) {
1004 unsigned entryIndex = m_propertyTable->entryIndices[a];
1005 if (entryIndex == emptyEntryIndex)
1006 continue;
1007 if (entryIndex == deletedSentinelIndex) {
1008 ++deletedIndexCount;
1009 continue;
1010 }
1011 ASSERT(entryIndex > deletedSentinelIndex);
1012 ASSERT(entryIndex - 1 <= m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount);
1013 ++indexCount;
1014
1015 for (unsigned b = a + 1; b != m_propertyTable->size; ++b)
1016 ASSERT(m_propertyTable->entryIndices[b] != entryIndex);
1017 }
1018 ASSERT(indexCount == m_propertyTable->keyCount);
1019 ASSERT(deletedIndexCount == m_propertyTable->deletedSentinelCount);
1020
1021 ASSERT(m_propertyTable->entries()[0].key == 0);
1022
1023 unsigned nonEmptyEntryCount = 0;
1024 for (unsigned c = 1; c <= m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount; ++c) {
1025 UString::Rep* rep = m_propertyTable->entries()[c].key;
1026 if (!rep)
1027 continue;
1028 ++nonEmptyEntryCount;
1029 unsigned i = rep->computedHash();
1030 unsigned k = 0;
1031 unsigned entryIndex;
1032 while (1) {
1033 entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
1034 ASSERT(entryIndex != emptyEntryIndex);
1035 if (rep == m_propertyTable->entries()[entryIndex - 1].key)
1036 break;
1037 if (k == 0)
1038 k = 1 | doubleHash(rep->computedHash());
1039 i += k;
1040 }
1041 ASSERT(entryIndex == c + 1);
1042 }
1043
1044 ASSERT(nonEmptyEntryCount == m_propertyTable->keyCount);
1045 }
1046
1047 #endif // DO_PROPERTYMAP_CONSTENCY_CHECK
1048
1049 } // namespace JSC
1050