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