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