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