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 void Structure::dumpStatistics()
  83 {
  84 #if DUMP_STRUCTURE_ID_STATISTICS
  85     unsigned numberLeaf = 0;
  86     unsigned numberUsingSingleSlot = 0;
  87     unsigned numberSingletons = 0;
  88     unsigned numberWithPropertyMaps = 0;
  89     unsigned totalPropertyMapsSize = 0;
  90
  91     HashSet<Structure*>::const_iterator end = liveStructureSet.end();
  92     for (HashSet<Structure*>::const_iterator it = liveStructureSet.begin(); it != end; ++it) {
  93         Structure* structure = *it;
  94         if (structure->m_usingSingleTransitionSlot) {
  95             if (!structure->m_transitions.singleTransition)
  96                 ++numberLeaf;
  97             else
  98                 ++numberUsingSingleSlot;
  99
 100            if (!structure->m_previous && !structure->m_transitions.singleTransition)
 101                 ++numberSingletons;
 102         }
 103
 104         if (structure->m_propertyTable) {
 105             ++numberWithPropertyMaps;
 106             totalPropertyMapsSize += PropertyMapHashTable::allocationSize(structure->m_propertyTable->size);
 107             if (structure->m_propertyTable->deletedOffsets)
 108                 totalPropertyMapsSize += (structure->m_propertyTable->deletedOffsets->capacity() * sizeof(unsigned));
 109         }
 110     }
 111
 112     printf("Number of live Structures: %d\n", liveStructureSet.size());
 113     printf("Number of Structures using the single item optimization for transition map: %d\n", numberUsingSingleSlot);
 114     printf("Number of Structures that are leaf nodes: %d\n", numberLeaf);
 115     printf("Number of Structures that singletons: %d\n", numberSingletons);
 116     printf("Number of Structures with PropertyMaps: %d\n", numberWithPropertyMaps);
 117
 118     printf("Size of a single Structures: %d\n", static_cast<unsigned>(sizeof(Structure)));
 119     printf("Size of sum of all property maps: %d\n", totalPropertyMapsSize);
 120     printf("Size of average of all property maps: %f\n", static_cast<double>(totalPropertyMapsSize) / static_cast<double>(liveStructureSet.size()));
 121 #else
 122     printf("Dumping Structure statistics is not enabled.\n");
 123 #endif
 124 }
 125
 126 Structure::Structure(JSValue prototype, const TypeInfo& typeInfo)
 127     : m_typeInfo(typeInfo)
 128     , m_prototype(prototype)
 129     , m_specificValueInPrevious(0)
 130     , m_propertyTable(0)
 131     , m_propertyStorageCapacity(JSObject::inlineStorageCapacity)
 132     , m_offset(noOffset)
 133     , m_dictionaryKind(NoneDictionaryKind)
 134     , m_isPinnedPropertyTable(false)
 135     , m_hasGetterSetterProperties(false)
 136     , m_attributesInPrevious(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
 156 Structure::~Structure()
 157 {
 158     if (m_previous) {
 159         if (m_nameInPrevious)
 160             m_previous->table.remove(make_pair(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
 196 void Structure::startIgnoringLeaks()
 197 {
 198 #ifndef NDEBUG
 199     shouldIgnoreLeaks = true;
 200 #endif
 201 }
 202
 203 void Structure::stopIgnoringLeaks()
 204 {
 205 #ifndef NDEBUG
 206     shouldIgnoreLeaks = false;
 207 #endif
 208 }
 209
 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
 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
 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
 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
 288 void Structure::growPropertyStorageCapacity()
 289 {
 290     if (m_propertyStorageCapacity == JSObject::inlineStorageCapacity)
 291         m_propertyStorageCapacity = JSObject::nonInlineBaseStorageCapacity;
 292     else
 293         m_propertyStorageCapacity *= 2;
 294 }
 295
 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->computedHash();
 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->computedHash());
 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
 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(make_pair(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
 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->transitionCount() > s_maxTransitionLength) {
 363         RefPtr<Structure> transition = toCacheableDictionaryTransition(structure);
 364         ASSERT(structure != transition);
 365         offset = transition->put(propertyName, attributes, specificValue);
 366         if (transition->propertyStorageSize() > transition->propertyStorageCapacity())
 367             transition->growPropertyStorageCapacity();
 368         return transition.release();
 369     }
 370
 371     RefPtr<Structure> transition = create(structure->m_prototype, structure->typeInfo());
 372
 373     transition->m_cachedPrototypeChain = structure->m_cachedPrototypeChain;
 374     transition->m_previous = structure;
 375     transition->m_nameInPrevious = propertyName.ustring().rep();
 376     transition->m_attributesInPrevious = attributes;
 377     transition->m_specificValueInPrevious = specificValue;
 378     transition->m_propertyStorageCapacity = structure->m_propertyStorageCapacity;
 379     transition->m_hasGetterSetterProperties = structure->m_hasGetterSetterProperties;
 380     transition->m_hasNonEnumerableProperties = structure->m_hasNonEnumerableProperties;
 381
 382     if (structure->m_propertyTable) {
 383         if (structure->m_isPinnedPropertyTable)
 384             transition->m_propertyTable = structure->copyPropertyTable();
 385         else {
 386             transition->m_propertyTable = structure->m_propertyTable;
 387             structure->m_propertyTable = 0;
 388         }
 389     } else {
 390         if (structure->m_previous)
 391             transition->materializePropertyMap();
 392         else
 393             transition->createPropertyMapHashTable();
 394     }
 395
 396     offset = transition->put(propertyName, attributes, specificValue);
 397     if (transition->propertyStorageSize() > transition->propertyStorageCapacity())
 398         transition->growPropertyStorageCapacity();
 399
 400     transition->m_offset = offset;
 401
 402     structure->table.add(make_pair(propertyName.ustring().rep(), attributes), transition.get(), specificValue);
 403     return transition.release();
 404 }
 405
 406 PassRefPtr<Structure> Structure::removePropertyTransition(Structure* structure, const Identifier& propertyName, size_t& offset)
 407 {
 408     ASSERT(!structure->isUncacheableDictionary());
 409
 410     RefPtr<Structure> transition = toUncacheableDictionaryTransition(structure);
 411
 412     offset = transition->remove(propertyName);
 413
 414     return transition.release();
 415 }
 416
 417 PassRefPtr<Structure> Structure::changePrototypeTransition(Structure* structure, JSValue prototype)
 418 {
 419     RefPtr<Structure> transition = create(prototype, structure->typeInfo());
 420
 421     transition->m_propertyStorageCapacity = structure->m_propertyStorageCapacity;
 422     transition->m_hasGetterSetterProperties = structure->m_hasGetterSetterProperties;
 423     transition->m_hasNonEnumerableProperties = structure->m_hasNonEnumerableProperties;
 424
 425     // Don't set m_offset, as one can not transition to this.
 426
 427     structure->materializePropertyMapIfNecessary();
 428     transition->m_propertyTable = structure->copyPropertyTable();
 429     transition->m_isPinnedPropertyTable = true;
 430
 431     return transition.release();
 432 }
 433
 434 PassRefPtr<Structure> Structure::despecifyFunctionTransition(Structure* structure, const Identifier& replaceFunction)
 435 {
 436     RefPtr<Structure> transition = create(structure->storedPrototype(), structure->typeInfo());
 437
 438     transition->m_propertyStorageCapacity = structure->m_propertyStorageCapacity;
 439     transition->m_hasGetterSetterProperties = structure->m_hasGetterSetterProperties;
 440     transition->m_hasNonEnumerableProperties = structure->m_hasNonEnumerableProperties;
 441
 442     // Don't set m_offset, as one can not transition to this.
 443
 444     structure->materializePropertyMapIfNecessary();
 445     transition->m_propertyTable = structure->copyPropertyTable();
 446     transition->m_isPinnedPropertyTable = true;
 447
 448     bool removed = transition->despecifyFunction(replaceFunction);
 449     ASSERT_UNUSED(removed, removed);
 450
 451     return transition.release();
 452 }
 453
 454 PassRefPtr<Structure> Structure::addAnonymousSlotsTransition(Structure* structure, unsigned count)
 455 {
 456     if (Structure* transition = structure->table.getAnonymousSlotTransition(count)) {
 457         ASSERT(transition->storedPrototype() == structure->storedPrototype());
 458         return transition;
 459     }
 460     ASSERT(count);
 461     ASSERT(count < ((1<<6) - 2));
 462     RefPtr<Structure> transition = create(structure->m_prototype, structure->typeInfo());
 463
 464     transition->m_cachedPrototypeChain = structure->m_cachedPrototypeChain;
 465     transition->m_previous = structure;
 466     transition->m_nameInPrevious = 0;
 467     transition->m_attributesInPrevious = 0;
 468     transition->m_anonymousSlotsInPrevious = count;
 469     transition->m_specificValueInPrevious = 0;
 470     transition->m_propertyStorageCapacity = structure->m_propertyStorageCapacity;
 471     transition->m_hasGetterSetterProperties = structure->m_hasGetterSetterProperties;
 472     transition->m_hasNonEnumerableProperties = structure->m_hasNonEnumerableProperties;
 473
 474     if (structure->m_propertyTable) {
 475         if (structure->m_isPinnedPropertyTable)
 476             transition->m_propertyTable = structure->copyPropertyTable();
 477         else {
 478             transition->m_propertyTable = structure->m_propertyTable;
 479             structure->m_propertyTable = 0;
 480         }
 481     } else {
 482         if (structure->m_previous)
 483             transition->materializePropertyMap();
 484         else
 485             transition->createPropertyMapHashTable();
 486     }
 487
 488     transition->addAnonymousSlots(count);
 489     if (transition->propertyStorageSize() > transition->propertyStorageCapacity())
 490         transition->growPropertyStorageCapacity();
 491
 492     structure->table.addAnonymousSlotTransition(count, transition.get());
 493     return transition.release();
 494 }
 495
 496 PassRefPtr<Structure> Structure::getterSetterTransition(Structure* structure)
 497 {
 498     RefPtr<Structure> transition = create(structure->storedPrototype(), structure->typeInfo());
 499     transition->m_propertyStorageCapacity = structure->m_propertyStorageCapacity;
 500     transition->m_hasGetterSetterProperties = transition->m_hasGetterSetterProperties;
 501     transition->m_hasNonEnumerableProperties = structure->m_hasNonEnumerableProperties;
 502
 503     // Don't set m_offset, as one can not transition to this.
 504
 505     structure->materializePropertyMapIfNecessary();
 506     transition->m_propertyTable = structure->copyPropertyTable();
 507     transition->m_isPinnedPropertyTable = true;
 508
 509     return transition.release();
 510 }
 511
 512 PassRefPtr<Structure> Structure::toDictionaryTransition(Structure* structure, DictionaryKind kind)
 513 {
 514     ASSERT(!structure->isUncacheableDictionary());
 515
 516     RefPtr<Structure> transition = create(structure->m_prototype, structure->typeInfo());
 517     transition->m_dictionaryKind = kind;
 518     transition->m_propertyStorageCapacity = structure->m_propertyStorageCapacity;
 519     transition->m_hasGetterSetterProperties = structure->m_hasGetterSetterProperties;
 520     transition->m_hasNonEnumerableProperties = structure->m_hasNonEnumerableProperties;
 521
 522     structure->materializePropertyMapIfNecessary();
 523     transition->m_propertyTable = structure->copyPropertyTable();
 524     transition->m_isPinnedPropertyTable = true;
 525
 526     return transition.release();
 527 }
 528
 529 PassRefPtr<Structure> Structure::toCacheableDictionaryTransition(Structure* structure)
 530 {
 531     return toDictionaryTransition(structure, CachedDictionaryKind);
 532 }
 533
 534 PassRefPtr<Structure> Structure::toUncacheableDictionaryTransition(Structure* structure)
 535 {
 536     return toDictionaryTransition(structure, UncachedDictionaryKind);
 537 }
 538
 539 PassRefPtr<Structure> Structure::flattenDictionaryStructure(JSObject* object)
 540 {
 541     ASSERT(isDictionary());
 542     if (isUncacheableDictionary()) {
 543         ASSERT(m_propertyTable);
 544         Vector<PropertyMapEntry*> sortedPropertyEntries(m_propertyTable->keyCount);
 545         PropertyMapEntry** p = sortedPropertyEntries.data();
 546         unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount;
 547         for (unsigned i = 1; i <= entryCount; i++) {
 548             if (m_propertyTable->entries()[i].key)
 549                 *p++ = &m_propertyTable->entries()[i];
 550         }
 551         size_t propertyCount = p - sortedPropertyEntries.data();
 552         qsort(sortedPropertyEntries.data(), propertyCount, sizeof(PropertyMapEntry*), comparePropertyMapEntryIndices);
 553         sortedPropertyEntries.resize(propertyCount);
 554
 555         // We now have the properties currently defined on this object
 556         // in the order that they are expected to be in, but we need to
 557         // reorder the storage, so we have to copy the current values out
 558         Vector<JSValue> values(propertyCount);
 559         unsigned anonymousSlotCount = m_propertyTable->anonymousSlotCount;
 560         for (unsigned i = 0; i < propertyCount; i++) {
 561             PropertyMapEntry* entry = sortedPropertyEntries[i];
 562             values[i] = object->getDirectOffset(entry->offset);
 563             // Update property table to have the new property offsets
 564             entry->offset = anonymousSlotCount + i;
 565             entry->index = i;
 566         }
 567
 568         // Copy the original property values into their final locations
 569         for (unsigned i = 0; i < propertyCount; i++)
 570             object->putDirectOffset(anonymousSlotCount + i, values[i]);
 571
 572         if (m_propertyTable->deletedOffsets) {
 573             delete m_propertyTable->deletedOffsets;
 574             m_propertyTable->deletedOffsets = 0;
 575         }
 576     }
 577
 578     m_dictionaryKind = NoneDictionaryKind;
 579     return this;
 580 }
 581
 582 size_t Structure::addPropertyWithoutTransition(const Identifier& propertyName, unsigned attributes, JSCell* specificValue)
 583 {
 584     ASSERT(!m_enumerationCache);
 585     materializePropertyMapIfNecessary();
 586
 587     m_isPinnedPropertyTable = true;
 588
 589     size_t offset = put(propertyName, attributes, specificValue);
 590     if (propertyStorageSize() > propertyStorageCapacity())
 591         growPropertyStorageCapacity();
 592     return offset;
 593 }
 594
 595 size_t Structure::removePropertyWithoutTransition(const Identifier& propertyName)
 596 {
 597     ASSERT(isUncacheableDictionary());
 598     ASSERT(!m_enumerationCache);
 599
 600     materializePropertyMapIfNecessary();
 601
 602     m_isPinnedPropertyTable = true;
 603     size_t offset = remove(propertyName);
 604     return offset;
 605 }
 606
 607 #if DUMP_PROPERTYMAP_STATS
 608
 609 static int numProbes;
 610 static int numCollisions;
 611 static int numRehashes;
 612 static int numRemoves;
 613
 614 struct PropertyMapStatisticsExitLogger {
 615     ~PropertyMapStatisticsExitLogger();
 616 };
 617
 618 static PropertyMapStatisticsExitLogger logger;
 619
 620 PropertyMapStatisticsExitLogger::~PropertyMapStatisticsExitLogger()
 621 {
 622     printf("\nJSC::PropertyMap statistics\n\n");
 623     printf("%d probes\n", numProbes);
 624     printf("%d collisions (%.1f%%)\n", numCollisions, 100.0 * numCollisions / numProbes);
 625     printf("%d rehashes\n", numRehashes);
 626     printf("%d removes\n", numRemoves);
 627 }
 628
 629 #endif
 630
 631 static const unsigned deletedSentinelIndex = 1;
 632
 633 #if !DO_PROPERTYMAP_CONSTENCY_CHECK
 634
 635 inline void Structure::checkConsistency()
 636 {
 637 }
 638
 639 #endif
 640
 641 PropertyMapHashTable* Structure::copyPropertyTable()
 642 {
 643     if (!m_propertyTable)
 644         return 0;
 645
 646     size_t tableSize = PropertyMapHashTable::allocationSize(m_propertyTable->size);
 647     PropertyMapHashTable* newTable = static_cast<PropertyMapHashTable*>(fastMalloc(tableSize));
 648     memcpy(newTable, m_propertyTable, tableSize);
 649
 650     unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount;
 651     for (unsigned i = 1; i <= entryCount; ++i) {
 652         if (UString::Rep* key = newTable->entries()[i].key)
 653             key->ref();
 654     }
 655
 656     // Copy the deletedOffsets vector.
 657     if (m_propertyTable->deletedOffsets)
 658         newTable->deletedOffsets = new Vector<unsigned>(*m_propertyTable->deletedOffsets);
 659
 660     newTable->anonymousSlotCount = m_propertyTable->anonymousSlotCount;
 661     return newTable;
 662 }
 663
 664 size_t Structure::get(const UString::Rep* rep, unsigned& attributes, JSCell*& specificValue)
 665 {
 666     materializePropertyMapIfNecessary();
 667     if (!m_propertyTable)
 668         return notFound;
 669
 670     unsigned i = rep->computedHash();
 671
 672 #if DUMP_PROPERTYMAP_STATS
 673     ++numProbes;
 674 #endif
 675
 676     unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
 677     if (entryIndex == emptyEntryIndex)
 678         return notFound;
 679
 680     if (rep == m_propertyTable->entries()[entryIndex - 1].key) {
 681         attributes = m_propertyTable->entries()[entryIndex - 1].attributes;
 682         specificValue = m_propertyTable->entries()[entryIndex - 1].specificValue;
 683         return m_propertyTable->entries()[entryIndex - 1].offset;
 684     }
 685
 686 #if DUMP_PROPERTYMAP_STATS
 687     ++numCollisions;
 688 #endif
 689
 690     unsigned k = 1 | doubleHash(rep->computedHash());
 691
 692     while (1) {
 693         i += k;
 694
 695 #if DUMP_PROPERTYMAP_STATS
 696         ++numRehashes;
 697 #endif
 698
 699         entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
 700         if (entryIndex == emptyEntryIndex)
 701             return notFound;
 702
 703         if (rep == m_propertyTable->entries()[entryIndex - 1].key) {
 704             attributes = m_propertyTable->entries()[entryIndex - 1].attributes;
 705             specificValue = m_propertyTable->entries()[entryIndex - 1].specificValue;
 706             return m_propertyTable->entries()[entryIndex - 1].offset;
 707         }
 708     }
 709 }
 710
 711 bool Structure::despecifyFunction(const Identifier& propertyName)
 712 {
 713     ASSERT(!propertyName.isNull());
 714
 715     materializePropertyMapIfNecessary();
 716     if (!m_propertyTable)
 717         return false;
 718
 719     UString::Rep* rep = propertyName._ustring.rep();
 720
 721     unsigned i = rep->computedHash();
 722
 723 #if DUMP_PROPERTYMAP_STATS
 724     ++numProbes;
 725 #endif
 726
 727     unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
 728     if (entryIndex == emptyEntryIndex)
 729         return false;
 730
 731     if (rep == m_propertyTable->entries()[entryIndex - 1].key) {
 732         ASSERT(m_propertyTable->entries()[entryIndex - 1].specificValue);
 733         m_propertyTable->entries()[entryIndex - 1].specificValue = 0;
 734         return true;
 735     }
 736
 737 #if DUMP_PROPERTYMAP_STATS
 738     ++numCollisions;
 739 #endif
 740
 741     unsigned k = 1 | doubleHash(rep->computedHash());
 742
 743     while (1) {
 744         i += k;
 745
 746 #if DUMP_PROPERTYMAP_STATS
 747         ++numRehashes;
 748 #endif
 749
 750         entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
 751         if (entryIndex == emptyEntryIndex)
 752             return false;
 753
 754         if (rep == m_propertyTable->entries()[entryIndex - 1].key) {
 755             ASSERT(m_propertyTable->entries()[entryIndex - 1].specificValue);
 756             m_propertyTable->entries()[entryIndex - 1].specificValue = 0;
 757             return true;
 758         }
 759     }
 760 }
 761
 762 size_t Structure::put(const Identifier& propertyName, unsigned attributes, JSCell* specificValue)
 763 {
 764     ASSERT(!propertyName.isNull());
 765     ASSERT(get(propertyName) == notFound);
 766
 767     checkConsistency();
 768
 769     if (attributes & DontEnum)
 770         m_hasNonEnumerableProperties = true;
 771
 772     UString::Rep* rep = propertyName._ustring.rep();
 773
 774     if (!m_propertyTable)
 775         createPropertyMapHashTable();
 776
 777     // FIXME: Consider a fast case for tables with no deleted sentinels.
 778
 779     unsigned i = rep->computedHash();
 780     unsigned k = 0;
 781     bool foundDeletedElement = false;
 782     unsigned deletedElementIndex = 0; // initialize to make the compiler happy
 783
 784 #if DUMP_PROPERTYMAP_STATS
 785     ++numProbes;
 786 #endif
 787
 788     while (1) {
 789         unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
 790         if (entryIndex == emptyEntryIndex)
 791             break;
 792
 793         if (entryIndex == deletedSentinelIndex) {
 794             // If we find a deleted-element sentinel, remember it for use later.
 795             if (!foundDeletedElement) {
 796                 foundDeletedElement = true;
 797                 deletedElementIndex = i;
 798             }
 799         }
 800
 801         if (k == 0) {
 802             k = 1 | doubleHash(rep->computedHash());
 803 #if DUMP_PROPERTYMAP_STATS
 804             ++numCollisions;
 805 #endif
 806         }
 807
 808         i += k;
 809
 810 #if DUMP_PROPERTYMAP_STATS
 811         ++numRehashes;
 812 #endif
 813     }
 814
 815     // Figure out which entry to use.
 816     unsigned entryIndex = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount + 2;
 817     if (foundDeletedElement) {
 818         i = deletedElementIndex;
 819         --m_propertyTable->deletedSentinelCount;
 820
 821         // Since we're not making the table bigger, we can't use the entry one past
 822         // the end that we were planning on using, so search backwards for the empty
 823         // slot that we can use. We know it will be there because we did at least one
 824         // deletion in the past that left an entry empty.
 825         while (m_propertyTable->entries()[--entryIndex - 1].key) { }
 826     }
 827
 828     // Create a new hash table entry.
 829     m_propertyTable->entryIndices[i & m_propertyTable->sizeMask] = entryIndex;
 830
 831     // Create a new hash table entry.
 832     rep->ref();
 833     m_propertyTable->entries()[entryIndex - 1].key = rep;
 834     m_propertyTable->entries()[entryIndex - 1].attributes = attributes;
 835     m_propertyTable->entries()[entryIndex - 1].specificValue = specificValue;
 836     m_propertyTable->entries()[entryIndex - 1].index = ++m_propertyTable->lastIndexUsed;
 837
 838     unsigned newOffset;
 839     if (m_propertyTable->deletedOffsets && !m_propertyTable->deletedOffsets->isEmpty()) {
 840         newOffset = m_propertyTable->deletedOffsets->last();
 841         m_propertyTable->deletedOffsets->removeLast();
 842     } else
 843         newOffset = m_propertyTable->keyCount + m_propertyTable->anonymousSlotCount;
 844     m_propertyTable->entries()[entryIndex - 1].offset = newOffset;
 845
 846     ++m_propertyTable->keyCount;
 847
 848     if ((m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount) * 2 >= m_propertyTable->size)
 849         expandPropertyMapHashTable();
 850
 851     checkConsistency();
 852     return newOffset;
 853 }
 854
 855 void Structure::addAnonymousSlots(unsigned count)
 856 {
 857     m_propertyTable->anonymousSlotCount += count;
 858 }
 859
 860 bool Structure::hasTransition(UString::Rep* rep, unsigned attributes)
 861 {
 862     return table.hasTransition(make_pair(rep, attributes));
 863 }
 864
 865 size_t Structure::remove(const Identifier& propertyName)
 866 {
 867     ASSERT(!propertyName.isNull());
 868
 869     checkConsistency();
 870
 871     UString::Rep* rep = propertyName._ustring.rep();
 872
 873     if (!m_propertyTable)
 874         return notFound;
 875
 876 #if DUMP_PROPERTYMAP_STATS
 877     ++numProbes;
 878     ++numRemoves;
 879 #endif
 880
 881     // Find the thing to remove.
 882     unsigned i = rep->computedHash();
 883     unsigned k = 0;
 884     unsigned entryIndex;
 885     UString::Rep* key = 0;
 886     while (1) {
 887         entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
 888         if (entryIndex == emptyEntryIndex)
 889             return notFound;
 890
 891         key = m_propertyTable->entries()[entryIndex - 1].key;
 892         if (rep == key)
 893             break;
 894
 895         if (k == 0) {
 896             k = 1 | doubleHash(rep->computedHash());
 897 #if DUMP_PROPERTYMAP_STATS
 898             ++numCollisions;
 899 #endif
 900         }
 901
 902         i += k;
 903
 904 #if DUMP_PROPERTYMAP_STATS
 905         ++numRehashes;
 906 #endif
 907     }
 908
 909     // Replace this one element with the deleted sentinel. Also clear out
 910     // the entry so we can iterate all the entries as needed.
 911     m_propertyTable->entryIndices[i & m_propertyTable->sizeMask] = deletedSentinelIndex;
 912
 913     size_t offset = m_propertyTable->entries()[entryIndex - 1].offset;
 914
 915     key->deref();
 916     m_propertyTable->entries()[entryIndex - 1].key = 0;
 917     m_propertyTable->entries()[entryIndex - 1].attributes = 0;
 918     m_propertyTable->entries()[entryIndex - 1].specificValue = 0;
 919     m_propertyTable->entries()[entryIndex - 1].offset = 0;
 920
 921     if (!m_propertyTable->deletedOffsets)
 922         m_propertyTable->deletedOffsets = new Vector<unsigned>;
 923     m_propertyTable->deletedOffsets->append(offset);
 924
 925     ASSERT(m_propertyTable->keyCount >= 1);
 926     --m_propertyTable->keyCount;
 927     ++m_propertyTable->deletedSentinelCount;
 928
 929     if (m_propertyTable->deletedSentinelCount * 4 >= m_propertyTable->size)
 930         rehashPropertyMapHashTable();
 931
 932     checkConsistency();
 933     return offset;
 934 }
 935
 936 void Structure::insertIntoPropertyMapHashTable(const PropertyMapEntry& entry)
 937 {
 938     ASSERT(m_propertyTable);
 939
 940     unsigned i = entry.key->computedHash();
 941     unsigned k = 0;
 942
 943 #if DUMP_PROPERTYMAP_STATS
 944     ++numProbes;
 945 #endif
 946
 947     while (1) {
 948         unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
 949         if (entryIndex == emptyEntryIndex)
 950             break;
 951
 952         if (k == 0) {
 953             k = 1 | doubleHash(entry.key->computedHash());
 954 #if DUMP_PROPERTYMAP_STATS
 955             ++numCollisions;
 956 #endif
 957         }
 958
 959         i += k;
 960
 961 #if DUMP_PROPERTYMAP_STATS
 962         ++numRehashes;
 963 #endif
 964     }
 965
 966     unsigned entryIndex = m_propertyTable->keyCount + 2;
 967     m_propertyTable->entryIndices[i & m_propertyTable->sizeMask] = entryIndex;
 968     m_propertyTable->entries()[entryIndex - 1] = entry;
 969
 970     ++m_propertyTable->keyCount;
 971 }
 972
 973 void Structure::createPropertyMapHashTable()
 974 {
 975     ASSERT(sizeForKeyCount(7) == newTableSize);
 976     createPropertyMapHashTable(newTableSize);
 977 }
 978
 979 void Structure::createPropertyMapHashTable(unsigned newTableSize)
 980 {
 981     ASSERT(!m_propertyTable);
 982     ASSERT(isPowerOf2(newTableSize));
 983
 984     checkConsistency();
 985
 986     m_propertyTable = static_cast<PropertyMapHashTable*>(fastZeroedMalloc(PropertyMapHashTable::allocationSize(newTableSize)));
 987     m_propertyTable->size = newTableSize;
 988     m_propertyTable->sizeMask = newTableSize - 1;
 989
 990     checkConsistency();
 991 }
 992
 993 void Structure::expandPropertyMapHashTable()
 994 {
 995     ASSERT(m_propertyTable);
 996     rehashPropertyMapHashTable(m_propertyTable->size * 2);
 997 }
 998
 999 void Structure::rehashPropertyMapHashTable()
1000 {
1001     ASSERT(m_propertyTable);
1002     ASSERT(m_propertyTable->size);
1003     rehashPropertyMapHashTable(m_propertyTable->size);
1004 }
1005
1006 void Structure::rehashPropertyMapHashTable(unsigned newTableSize)
1007 {
1008     ASSERT(m_propertyTable);
1009     ASSERT(isPowerOf2(newTableSize));
1010
1011     checkConsistency();
1012
1013     PropertyMapHashTable* oldTable = m_propertyTable;
1014
1015     m_propertyTable = static_cast<PropertyMapHashTable*>(fastZeroedMalloc(PropertyMapHashTable::allocationSize(newTableSize)));
1016     m_propertyTable->size = newTableSize;
1017     m_propertyTable->sizeMask = newTableSize - 1;
1018     m_propertyTable->anonymousSlotCount = oldTable->anonymousSlotCount;
1019
1020     unsigned lastIndexUsed = 0;
1021     unsigned entryCount = oldTable->keyCount + oldTable->deletedSentinelCount;
1022     for (unsigned i = 1; i <= entryCount; ++i) {
1023         if (oldTable->entries()[i].key) {
1024             lastIndexUsed = max(oldTable->entries()[i].index, lastIndexUsed);
1025             insertIntoPropertyMapHashTable(oldTable->entries()[i]);
1026         }
1027     }
1028     m_propertyTable->lastIndexUsed = lastIndexUsed;
1029     m_propertyTable->deletedOffsets = oldTable->deletedOffsets;
1030
1031     fastFree(oldTable);
1032
1033     checkConsistency();
1034 }
1035
1036 int comparePropertyMapEntryIndices(const void* a, const void* b)
1037 {
1038     unsigned ia = static_cast<PropertyMapEntry* const*>(a)[0]->index;
1039     unsigned ib = static_cast<PropertyMapEntry* const*>(b)[0]->index;
1040     if (ia < ib)
1041         return -1;
1042     if (ia > ib)
1043         return +1;
1044     return 0;
1045 }
1046
1047 void Structure::getEnumerablePropertyNames(PropertyNameArray& propertyNames)
1048 {
1049     materializePropertyMapIfNecessary();
1050     if (!m_propertyTable)
1051         return;
1052
1053     if (m_propertyTable->keyCount < tinyMapThreshold) {
1054         PropertyMapEntry* a[tinyMapThreshold];
1055         int i = 0;
1056         unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount;
1057         for (unsigned k = 1; k <= entryCount; k++) {
1058             ASSERT(m_hasNonEnumerableProperties || !(m_propertyTable->entries()[k].attributes & DontEnum));
1059             if (m_propertyTable->entries()[k].key && !(m_propertyTable->entries()[k].attributes & DontEnum)) {
1060                 PropertyMapEntry* value = &m_propertyTable->entries()[k];
1061                 int j;
1062                 for (j = i - 1; j >= 0 && a[j]->index > value->index; --j)
1063                     a[j + 1] = a[j];
1064                 a[j + 1] = value;
1065                 ++i;
1066             }
1067         }
1068         if (!propertyNames.size()) {
1069             for (int k = 0; k < i; ++k)
1070                 propertyNames.addKnownUnique(a[k]->key);
1071         } else {
1072             for (int k = 0; k < i; ++k)
1073                 propertyNames.add(a[k]->key);
1074         }
1075
1076         return;
1077     }
1078
1079     // Allocate a buffer to use to sort the keys.
1080     Vector<PropertyMapEntry*, smallMapThreshold> sortedEnumerables(m_propertyTable->keyCount);
1081
1082     // Get pointers to the enumerable entries in the buffer.
1083     PropertyMapEntry** p = sortedEnumerables.data();
1084     unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount;
1085     for (unsigned i = 1; i <= entryCount; i++) {
1086         if (m_propertyTable->entries()[i].key && !(m_propertyTable->entries()[i].attributes & DontEnum))
1087             *p++ = &m_propertyTable->entries()[i];
1088     }
1089
1090     size_t enumerableCount = p - sortedEnumerables.data();
1091     // Sort the entries by index.
1092     qsort(sortedEnumerables.data(), enumerableCount, sizeof(PropertyMapEntry*), comparePropertyMapEntryIndices);
1093     sortedEnumerables.resize(enumerableCount);
1094
1095     // Put the keys of the sorted entries into the list.
1096     if (!propertyNames.size()) {
1097         for (size_t i = 0; i < sortedEnumerables.size(); ++i)
1098             propertyNames.addKnownUnique(sortedEnumerables[i]->key);
1099     } else {
1100         for (size_t i = 0; i < sortedEnumerables.size(); ++i)
1101             propertyNames.add(sortedEnumerables[i]->key);
1102     }
1103 }
1104
1105 #if DO_PROPERTYMAP_CONSTENCY_CHECK
1106
1107 void Structure::checkConsistency()
1108 {
1109     if (!m_propertyTable)
1110         return;
1111
1112     ASSERT(m_propertyTable->size >= newTableSize);
1113     ASSERT(m_propertyTable->sizeMask);
1114     ASSERT(m_propertyTable->size == m_propertyTable->sizeMask + 1);
1115     ASSERT(!(m_propertyTable->size & m_propertyTable->sizeMask));
1116
1117     ASSERT(m_propertyTable->keyCount <= m_propertyTable->size / 2);
1118     ASSERT(m_propertyTable->deletedSentinelCount <= m_propertyTable->size / 4);
1119
1120     ASSERT(m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount <= m_propertyTable->size / 2);
1121
1122     unsigned indexCount = 0;
1123     unsigned deletedIndexCount = 0;
1124     for (unsigned a = 0; a != m_propertyTable->size; ++a) {
1125         unsigned entryIndex = m_propertyTable->entryIndices[a];
1126         if (entryIndex == emptyEntryIndex)
1127             continue;
1128         if (entryIndex == deletedSentinelIndex) {
1129             ++deletedIndexCount;
1130             continue;
1131         }
1132         ASSERT(entryIndex > deletedSentinelIndex);
1133         ASSERT(entryIndex - 1 <= m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount);
1134         ++indexCount;
1135
1136         for (unsigned b = a + 1; b != m_propertyTable->size; ++b)
1137             ASSERT(m_propertyTable->entryIndices[b] != entryIndex);
1138     }
1139     ASSERT(indexCount == m_propertyTable->keyCount);
1140     ASSERT(deletedIndexCount == m_propertyTable->deletedSentinelCount);
1141
1142     ASSERT(m_propertyTable->entries()[0].key == 0);
1143
1144     unsigned nonEmptyEntryCount = 0;
1145     for (unsigned c = 1; c <= m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount; ++c) {
1146         ASSERT(m_hasNonEnumerableProperties || !(m_propertyTable->entries()[c].attributes & DontEnum));
1147         UString::Rep* rep = m_propertyTable->entries()[c].key;
1148         if (!rep)
1149             continue;
1150         ++nonEmptyEntryCount;
1151         unsigned i = rep->computedHash();
1152         unsigned k = 0;
1153         unsigned entryIndex;
1154         while (1) {
1155             entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
1156             ASSERT(entryIndex != emptyEntryIndex);
1157             if (rep == m_propertyTable->entries()[entryIndex - 1].key)
1158                 break;
1159             if (k == 0)
1160                 k = 1 | doubleHash(rep->computedHash());
1161             i += k;
1162         }
1163         ASSERT(entryIndex == c + 1);
1164     }
1165
1166     ASSERT(nonEmptyEntryCount == m_propertyTable->keyCount);
1167 }
1168
1169 #endif // DO_PROPERTYMAP_CONSTENCY_CHECK
1170
1171 } // namespace JSC