runtime/Structure.cpp

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