kjs/property_map.cpp

   1 /*
   2  *  Copyright (C) 2004, 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
   3  *
   4  *  This library is free software; you can redistribute it and/or
   5  *  modify it under the terms of the GNU Library General Public
   6  *  License as published by the Free Software Foundation; either
   7  *  version 2 of the License, or (at your option) any later version.
   8  *
   9  *  This library is distributed in the hope that it will be useful,
  10  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  *  Library General Public License for more details.
  13  *
  14  *  You should have received a copy of the GNU Library General Public License
  15  *  along with this library; see the file COPYING.LIB.  If not, write to
  16  *  the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  17  *  Boston, MA 02110-1301, USA.
  18  *
  19  */
  20
  21 #include "config.h"
  22 #include "property_map.h"
  23
  24 #include "object.h"
  25 #include "protect.h"
  26 #include "PropertyNameArray.h"
  27 #include <algorithm>
  28 #include <wtf/Assertions.h>
  29 #include <wtf/FastMalloc.h>
  30 #include <wtf/HashTable.h>
  31 #include <wtf/Vector.h>
  32
  33 using std::max;
  34 using WTF::doubleHash;
  35
  36 #ifndef NDEBUG
  37 #define DO_PROPERTYMAP_CONSTENCY_CHECK 0
  38 #define DUMP_PROPERTYMAP_STATS 0
  39 #else
  40 #define DO_PROPERTYMAP_CONSTENCY_CHECK 0
  41 #define DUMP_PROPERTYMAP_STATS 0
  42 #endif
  43
  44 #define USE_SINGLE_ENTRY 1
  45
  46 // 2/28/2006 ggaren: command-line JS iBench says that USE_SINGLE_ENTRY is a
  47 // 3.2% performance boost.
  48
  49 namespace KJS {
  50
  51 // Choose a number for the following so that most property maps are smaller,
  52 // but it's not going to blow out the stack to allocate this number of pointers.
  53 static const int smallMapThreshold = 1024;
  54
  55 // The point at which the function call overhead of the qsort implementation
  56 // becomes small compared to the inefficiency of insertion sort.
  57 static const unsigned tinyMapThreshold = 20;
  58
  59 #if DUMP_PROPERTYMAP_STATS
  60
  61 static int numProbes;
  62 static int numCollisions;
  63 static int numRehashes;
  64 static int numRemoves;
  65
  66 struct PropertyMapStatisticsExitLogger { ~PropertyMapStatisticsExitLogger(); };
  67
  68 static PropertyMapStatisticsExitLogger logger;
  69
  70 PropertyMapStatisticsExitLogger::~PropertyMapStatisticsExitLogger()
  71 {
  72     printf("\nKJS::PropertyMap statistics\n\n");
  73     printf("%d probes\n", numProbes);
  74     printf("%d collisions (%.1f%%)\n", numCollisions, 100.0 * numCollisions / numProbes);
  75     printf("%d rehashes\n", numRehashes);
  76     printf("%d removes\n", numRemoves);
  77 }
  78
  79 #endif
  80
  81 struct PropertyMapEntry {
  82     UString::Rep* key;
  83     JSValue* value;
  84     unsigned attributes;
  85     unsigned index;
  86
  87     PropertyMapEntry(UString::Rep* k, JSValue* v, int a)
  88         : key(k), value(v), attributes(a), index(0)
  89     {
  90     }
  91 };
  92
  93 // lastIndexUsed is an ever-increasing index used to identify the order items
  94 // were inserted into the property map. It's required that getEnumerablePropertyNames
  95 // return the properties in the order they were added for compatibility with other
  96 // browsers' JavaScript implementations.
  97 struct PropertyMapHashTable {
  98     unsigned sizeMask;
  99     unsigned size;
 100     unsigned keyCount;
 101     unsigned deletedSentinelCount;
 102     unsigned lastIndexUsed;
 103     unsigned entryIndicies[1];
 104
 105     PropertyMapEntry* entries()
 106     {
 107         // The entries vector comes after the indices vector.
 108         // The 0th item in the entries vector is not really used; it has to
 109         // have a 0 in its key to allow the hash table lookup to handle deleted
 110         // sentinels without any special-case code, but the other fields are unused.
 111         return reinterpret_cast<PropertyMapEntry*>(&entryIndicies[size]);
 112     }
 113
 114     static size_t allocationSize(unsigned size)
 115     {
 116         // We never let a hash table get more than half full,
 117         // So the number of indices we need is the size of the hash table.
 118         // But the number of entries is half that (plus one for the deleted sentinel).
 119         return sizeof(PropertyMapHashTable)
 120             + (size - 1) * sizeof(unsigned)
 121             + (1 + size / 2) * sizeof(PropertyMapEntry);
 122     }
 123 };
 124
 125 static const unsigned emptyEntryIndex = 0;
 126 static const unsigned deletedSentinelIndex = 1;
 127
 128 SavedProperties::SavedProperties()
 129     : count(0)
 130 {
 131 }
 132
 133 SavedProperties::~SavedProperties()
 134 {
 135 }
 136
 137 #if !DO_PROPERTYMAP_CONSTENCY_CHECK
 138
 139 inline void PropertyMap::checkConsistency()
 140 {
 141 }
 142
 143 #endif
 144
 145 PropertyMap::~PropertyMap()
 146 {
 147     if (!m_usingTable) {
 148 #if USE_SINGLE_ENTRY
 149         if (m_singleEntryKey)
 150             m_singleEntryKey->deref();
 151 #endif
 152         return;
 153     }
 154
 155     unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
 156     for (unsigned i = 1; i <= entryCount; i++) {
 157         if (UString::Rep* key = m_u.table->entries()[i].key)
 158             key->deref();
 159     }
 160     fastFree(m_u.table);
 161 }
 162
 163 void PropertyMap::clear()
 164 {
 165     if (!m_usingTable) {
 166 #if USE_SINGLE_ENTRY
 167         if (m_singleEntryKey) {
 168             m_singleEntryKey->deref();
 169             m_singleEntryKey = 0;
 170         }
 171 #endif
 172         return;
 173     }
 174
 175     unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
 176     for (unsigned i = 1; i <= entryCount; i++) {
 177         if (UString::Rep* key = m_u.table->entries()[i].key)
 178             key->deref();
 179     }
 180     for (unsigned i = 0; i < m_u.table->size; i++)
 181         m_u.table->entryIndicies[i] = emptyEntryIndex;
 182     m_u.table->keyCount = 0;
 183     m_u.table->deletedSentinelCount = 0;
 184 }
 185
 186 JSValue* PropertyMap::get(const Identifier& name, unsigned& attributes) const
 187 {
 188     ASSERT(!name.isNull());
 189
 190     UString::Rep* rep = name._ustring.rep();
 191
 192     if (!m_usingTable) {
 193 #if USE_SINGLE_ENTRY
 194         if (rep == m_singleEntryKey) {
 195             attributes = m_singleEntryAttributes;
 196             return m_u.singleEntryValue;
 197         }
 198 #endif
 199         return 0;
 200     }
 201
 202     unsigned i = rep->computedHash();
 203
 204 #if DUMP_PROPERTYMAP_STATS
 205     ++numProbes;
 206 #endif
 207
 208     unsigned entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
 209     if (entryIndex == emptyEntryIndex)
 210         return 0;
 211
 212     if (rep == m_u.table->entries()[entryIndex - 1].key) {
 213         attributes = m_u.table->entries()[entryIndex - 1].attributes;
 214         return m_u.table->entries()[entryIndex - 1].value;
 215     }
 216
 217 #if DUMP_PROPERTYMAP_STATS
 218     ++numCollisions;
 219 #endif
 220
 221     unsigned k = 1 | doubleHash(rep->computedHash());
 222
 223     while (1) {
 224         i += k;
 225
 226 #if DUMP_PROPERTYMAP_STATS
 227         ++numRehashes;
 228 #endif
 229
 230         entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
 231         if (entryIndex == emptyEntryIndex)
 232             return 0;
 233
 234         if (rep == m_u.table->entries()[entryIndex - 1].key) {
 235             attributes = m_u.table->entries()[entryIndex - 1].attributes;
 236             return m_u.table->entries()[entryIndex - 1].value;
 237         }
 238     }
 239 }
 240
 241 JSValue* PropertyMap::get(const Identifier& name) const
 242 {
 243     ASSERT(!name.isNull());
 244
 245     UString::Rep* rep = name._ustring.rep();
 246
 247     if (!m_usingTable) {
 248 #if USE_SINGLE_ENTRY
 249         if (rep == m_singleEntryKey)
 250             return m_u.singleEntryValue;
 251 #endif
 252         return 0;
 253     }
 254
 255     unsigned i = rep->computedHash();
 256
 257 #if DUMP_PROPERTYMAP_STATS
 258     ++numProbes;
 259 #endif
 260
 261     unsigned entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
 262     if (entryIndex == emptyEntryIndex)
 263         return 0;
 264
 265     if (rep == m_u.table->entries()[entryIndex - 1].key)
 266         return m_u.table->entries()[entryIndex - 1].value;
 267
 268 #if DUMP_PROPERTYMAP_STATS
 269     ++numCollisions;
 270 #endif
 271
 272     unsigned k = 1 | doubleHash(rep->computedHash());
 273
 274     while (1) {
 275         i += k;
 276
 277 #if DUMP_PROPERTYMAP_STATS
 278         ++numRehashes;
 279 #endif
 280
 281         entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
 282         if (entryIndex == emptyEntryIndex)
 283             return 0;
 284
 285         if (rep == m_u.table->entries()[entryIndex - 1].key)
 286             return m_u.table->entries()[entryIndex - 1].value;
 287     }
 288 }
 289
 290 JSValue** PropertyMap::getLocation(const Identifier& name)
 291 {
 292     ASSERT(!name.isNull());
 293
 294     UString::Rep* rep = name._ustring.rep();
 295
 296     if (!m_usingTable) {
 297 #if USE_SINGLE_ENTRY
 298         if (rep == m_singleEntryKey)
 299             return &m_u.singleEntryValue;
 300 #endif
 301         return 0;
 302     }
 303
 304     unsigned i = rep->computedHash();
 305
 306 #if DUMP_PROPERTYMAP_STATS
 307     ++numProbes;
 308 #endif
 309
 310     unsigned entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
 311     if (entryIndex == emptyEntryIndex)
 312         return 0;
 313
 314     if (rep == m_u.table->entries()[entryIndex - 1].key)
 315         return &m_u.table->entries()[entryIndex - 1].value;
 316
 317 #if DUMP_PROPERTYMAP_STATS
 318     ++numCollisions;
 319 #endif
 320
 321     unsigned k = 1 | doubleHash(rep->computedHash());
 322
 323     while (1) {
 324         i += k;
 325
 326 #if DUMP_PROPERTYMAP_STATS
 327         ++numRehashes;
 328 #endif
 329
 330         entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
 331         if (entryIndex == emptyEntryIndex)
 332             return 0;
 333
 334         if (rep == m_u.table->entries()[entryIndex - 1].key)
 335             return &m_u.table->entries()[entryIndex - 1].value;
 336     }
 337 }
 338
 339 void PropertyMap::put(const Identifier& name, JSValue* value, unsigned attributes, bool checkReadOnly)
 340 {
 341     ASSERT(!name.isNull());
 342     ASSERT(value);
 343
 344     checkConsistency();
 345
 346     UString::Rep* rep = name._ustring.rep();
 347
 348 #if USE_SINGLE_ENTRY
 349     if (!m_usingTable) {
 350         if (!m_singleEntryKey) {
 351             rep->ref();
 352             m_singleEntryKey = rep;
 353             m_u.singleEntryValue = value;
 354             m_singleEntryAttributes = static_cast<short>(attributes);
 355             checkConsistency();
 356             return;
 357         }
 358         if (rep == m_singleEntryKey && !(checkReadOnly && (m_singleEntryAttributes & ReadOnly))) {
 359             m_u.singleEntryValue = value;
 360             return;
 361         }
 362     }
 363 #endif
 364
 365     if (!m_usingTable || (m_u.table->keyCount + m_u.table->deletedSentinelCount) * 2 >= m_u.table->size)
 366         expand();
 367
 368     // FIXME: Consider a fast case for tables with no deleted sentinels.
 369
 370     unsigned i = rep->computedHash();
 371     unsigned k = 0;
 372     bool foundDeletedElement = false;
 373     unsigned deletedElementIndex = 0; // initialize to make the compiler happy
 374
 375 #if DUMP_PROPERTYMAP_STATS
 376     ++numProbes;
 377 #endif
 378
 379     while (1) {
 380         unsigned entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
 381         if (entryIndex == emptyEntryIndex)
 382             break;
 383
 384         if (m_u.table->entries()[entryIndex - 1].key == rep) {
 385             if (checkReadOnly && (m_u.table->entries()[entryIndex - 1].attributes & ReadOnly))
 386                 return;
 387             // Put a new value in an existing hash table entry.
 388             m_u.table->entries()[entryIndex - 1].value = value;
 389             // Attributes are intentionally not updated.
 390             return;
 391         } else if (entryIndex == deletedSentinelIndex) {
 392             // If we find a deleted-element sentinel, remember it for use later.
 393             if (!foundDeletedElement) {
 394                 foundDeletedElement = true;
 395                 deletedElementIndex = i;
 396             }
 397         }
 398
 399         if (k == 0) {
 400             k = 1 | doubleHash(rep->computedHash());
 401 #if DUMP_PROPERTYMAP_STATS
 402             ++numCollisions;
 403 #endif
 404         }
 405
 406         i += k;
 407
 408 #if DUMP_PROPERTYMAP_STATS
 409         ++numRehashes;
 410 #endif
 411     }
 412
 413     // Figure out which entry to use.
 414     unsigned entryIndex = m_u.table->keyCount + m_u.table->deletedSentinelCount + 2;
 415     if (foundDeletedElement) {
 416         i = deletedElementIndex;
 417         --m_u.table->deletedSentinelCount;
 418
 419         // Since we're not making the table bigger, we can't use the entry one past
 420         // the end that we were planning on using, so search backwards for the empty
 421         // slot that we can use. We know it will be there because we did at least one
 422         // deletion in the past that left an entry empty.
 423         while (m_u.table->entries()[--entryIndex - 1].key)
 424             ;
 425     }
 426
 427
 428     // Create a new hash table entry.
 429     m_u.table->entryIndicies[i & m_u.table->sizeMask] = entryIndex;
 430
 431     // Create a new hash table entry.
 432     rep->ref();
 433     m_u.table->entries()[entryIndex - 1].key = rep;
 434     m_u.table->entries()[entryIndex - 1].value = value;
 435     m_u.table->entries()[entryIndex - 1].attributes = attributes;
 436     m_u.table->entries()[entryIndex - 1].index = ++m_u.table->lastIndexUsed;
 437     ++m_u.table->keyCount;
 438
 439     checkConsistency();
 440 }
 441
 442 void PropertyMap::insert(const Entry& entry)
 443 {
 444     ASSERT(m_u.table);
 445
 446     unsigned i = entry.key->computedHash();
 447     unsigned k = 0;
 448
 449 #if DUMP_PROPERTYMAP_STATS
 450     ++numProbes;
 451 #endif
 452
 453     while (1) {
 454         unsigned entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
 455         if (entryIndex == emptyEntryIndex)
 456             break;
 457
 458         if (k == 0) {
 459             k = 1 | doubleHash(entry.key->computedHash());
 460 #if DUMP_PROPERTYMAP_STATS
 461             ++numCollisions;
 462 #endif
 463         }
 464
 465         i += k;
 466
 467 #if DUMP_PROPERTYMAP_STATS
 468         ++numRehashes;
 469 #endif
 470     }
 471
 472     unsigned entryIndex = m_u.table->keyCount + 2;
 473     m_u.table->entryIndicies[i & m_u.table->sizeMask] = entryIndex;
 474     m_u.table->entries()[entryIndex - 1] = entry;
 475     ++m_u.table->keyCount;
 476 }
 477
 478 void PropertyMap::expand()
 479 {
 480     if (!m_usingTable)
 481         createTable();
 482     else
 483         rehash(m_u.table->size * 2);
 484 }
 485
 486 void PropertyMap::rehash()
 487 {
 488     ASSERT(m_usingTable);
 489     ASSERT(m_u.table);
 490     ASSERT(m_u.table->size);
 491     rehash(m_u.table->size);
 492 }
 493
 494 void PropertyMap::createTable()
 495 {
 496     const unsigned newTableSize = 16;
 497
 498     ASSERT(!m_usingTable);
 499
 500     checkConsistency();
 501
 502 #if USE_SINGLE_ENTRY
 503     JSValue* oldSingleEntryValue = m_u.singleEntryValue;
 504 #endif
 505
 506     m_u.table = static_cast<Table*>(fastZeroedMalloc(Table::allocationSize(newTableSize)));
 507     m_u.table->size = newTableSize;
 508     m_u.table->sizeMask = newTableSize - 1;
 509     m_usingTable = true;
 510
 511 #if USE_SINGLE_ENTRY
 512     if (m_singleEntryKey) {
 513         insert(Entry(m_singleEntryKey, oldSingleEntryValue, m_singleEntryAttributes));
 514         m_singleEntryKey = 0;
 515     }
 516 #endif
 517
 518     checkConsistency();
 519 }
 520
 521 void PropertyMap::rehash(unsigned newTableSize)
 522 {
 523     ASSERT(!m_singleEntryKey);
 524     ASSERT(m_u.table);
 525     ASSERT(m_usingTable);
 526
 527     checkConsistency();
 528
 529     Table* oldTable = m_u.table;
 530
 531     m_u.table = static_cast<Table*>(fastZeroedMalloc(Table::allocationSize(newTableSize)));
 532     m_u.table->size = newTableSize;
 533     m_u.table->sizeMask = newTableSize - 1;
 534
 535     unsigned lastIndexUsed = 0;
 536     unsigned entryCount = oldTable->keyCount + oldTable->deletedSentinelCount;
 537     for (unsigned i = 1; i <= entryCount; ++i) {
 538         if (oldTable->entries()[i].key) {
 539             lastIndexUsed = max(oldTable->entries()[i].index, lastIndexUsed);
 540             insert(oldTable->entries()[i]);
 541         }
 542     }
 543     m_u.table->lastIndexUsed = lastIndexUsed;
 544
 545     fastFree(oldTable);
 546
 547     checkConsistency();
 548 }
 549
 550 void PropertyMap::remove(const Identifier& name)
 551 {
 552     ASSERT(!name.isNull());
 553
 554     checkConsistency();
 555
 556     UString::Rep* rep = name._ustring.rep();
 557
 558     if (!m_usingTable) {
 559 #if USE_SINGLE_ENTRY
 560         if (rep == m_singleEntryKey) {
 561             m_singleEntryKey->deref();
 562             m_singleEntryKey = 0;
 563             checkConsistency();
 564         }
 565 #endif
 566         return;
 567     }
 568
 569 #if DUMP_PROPERTYMAP_STATS
 570     ++numProbes;
 571     ++numRemoves;
 572 #endif
 573
 574     // Find the thing to remove.
 575     unsigned i = rep->computedHash();
 576     unsigned k = 0;
 577     unsigned entryIndex;
 578     UString::Rep* key = 0;
 579     while (1) {
 580         entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
 581         if (entryIndex == emptyEntryIndex)
 582             return;
 583
 584         key = m_u.table->entries()[entryIndex - 1].key;
 585         if (rep == key)
 586             break;
 587
 588         if (k == 0) {
 589             k = 1 | doubleHash(rep->computedHash());
 590 #if DUMP_PROPERTYMAP_STATS
 591             ++numCollisions;
 592 #endif
 593         }
 594
 595         i += k;
 596
 597 #if DUMP_PROPERTYMAP_STATS
 598         ++numRehashes;
 599 #endif
 600     }
 601
 602     // Replace this one element with the deleted sentinel. Also clear out
 603     // the entry so we can iterate all the entries as needed.
 604     m_u.table->entryIndicies[i & m_u.table->sizeMask] = deletedSentinelIndex;
 605     key->deref();
 606     m_u.table->entries()[entryIndex - 1].key = 0;
 607     m_u.table->entries()[entryIndex - 1].value = jsUndefined();
 608     m_u.table->entries()[entryIndex - 1].attributes = 0;
 609     ASSERT(m_u.table->keyCount >= 1);
 610     --m_u.table->keyCount;
 611     ++m_u.table->deletedSentinelCount;
 612
 613     if (m_u.table->deletedSentinelCount * 4 >= m_u.table->size)
 614         rehash();
 615
 616     checkConsistency();
 617 }
 618
 619 void PropertyMap::mark() const
 620 {
 621     if (!m_usingTable) {
 622 #if USE_SINGLE_ENTRY
 623         if (m_singleEntryKey) {
 624             JSValue* v = m_u.singleEntryValue;
 625             if (!v->marked())
 626                 v->mark();
 627         }
 628 #endif
 629         return;
 630     }
 631
 632     unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
 633     for (unsigned i = 1; i <= entryCount; i++) {
 634         JSValue* v = m_u.table->entries()[i].value;
 635         if (!v->marked())
 636             v->mark();
 637     }
 638 }
 639
 640 static int comparePropertyMapEntryIndices(const void* a, const void* b)
 641 {
 642     unsigned ia = static_cast<PropertyMapEntry* const*>(a)[0]->index;
 643     unsigned ib = static_cast<PropertyMapEntry* const*>(b)[0]->index;
 644     if (ia < ib)
 645         return -1;
 646     if (ia > ib)
 647         return +1;
 648     return 0;
 649 }
 650
 651 bool PropertyMap::containsGettersOrSetters() const
 652 {
 653     if (!m_usingTable) {
 654 #if USE_SINGLE_ENTRY
 655         return !!(m_singleEntryAttributes & GetterSetter);
 656 #else
 657         return false;
 658 #endif
 659     }
 660
 661     unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
 662     for (unsigned i = 1; i <= entryCount; i++) {
 663         if (m_u.table->entries()[i].attributes & GetterSetter)
 664             return true;
 665     }
 666
 667     return false;
 668 }
 669
 670 void PropertyMap::getEnumerablePropertyNames(PropertyNameArray& propertyNames) const
 671 {
 672     if (!m_usingTable) {
 673 #if USE_SINGLE_ENTRY
 674         UString::Rep* key = m_singleEntryKey;
 675         if (key && !(m_singleEntryAttributes & DontEnum))
 676             propertyNames.add(Identifier(key));
 677 #endif
 678         return;
 679     }
 680
 681     if (m_u.table->keyCount < tinyMapThreshold) {
 682         Entry* a[tinyMapThreshold];
 683         int i = 0;
 684         unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
 685         for (unsigned k = 1; k <= entryCount; k++) {
 686             if (m_u.table->entries()[k].key && !(m_u.table->entries()[k].attributes & DontEnum)) {
 687                 Entry* value = &m_u.table->entries()[k];
 688                 int j;
 689                 for (j = i - 1; j >= 0 && a[j]->index > value->index; --j)
 690                     a[j + 1] = a[j];
 691                 a[j + 1] = value;
 692                 ++i;
 693             }
 694         }
 695         for (int k = 0; k < i; ++k)
 696             propertyNames.add(Identifier(a[k]->key));
 697         return;
 698     }
 699
 700     // Allocate a buffer to use to sort the keys.
 701     Vector<Entry*, smallMapThreshold> sortedEnumerables(m_u.table->keyCount);
 702
 703     // Get pointers to the enumerable entries in the buffer.
 704     Entry** p = sortedEnumerables.data();
 705     unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
 706     for (unsigned i = 1; i <= entryCount; i++) {
 707         if (m_u.table->entries()[i].key && !(m_u.table->entries()[i].attributes & DontEnum))
 708             *p++ = &m_u.table->entries()[i];
 709     }
 710
 711     // Sort the entries by index.
 712     qsort(sortedEnumerables.data(), p - sortedEnumerables.data(), sizeof(Entry*), comparePropertyMapEntryIndices);
 713
 714     // Put the keys of the sorted entries into the list.
 715     for (Entry** q = sortedEnumerables.data(); q != p; ++q)
 716         propertyNames.add(Identifier(q[0]->key));
 717 }
 718
 719 void PropertyMap::save(SavedProperties& s) const
 720 {
 721     unsigned count = 0;
 722
 723     if (!m_usingTable) {
 724 #if USE_SINGLE_ENTRY
 725         if (m_singleEntryKey && !(m_singleEntryAttributes & (ReadOnly | Function)))
 726             ++count;
 727 #endif
 728     } else {
 729         unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
 730         for (unsigned i = 1; i <= entryCount; ++i)
 731             if (m_u.table->entries()[i].key && !(m_u.table->entries()[i].attributes & (ReadOnly | Function)))
 732                 ++count;
 733     }
 734
 735     s.properties.clear();
 736     s.count = count;
 737
 738     if (count == 0)
 739         return;
 740
 741     s.properties.set(new SavedProperty[count]);
 742
 743     SavedProperty* prop = s.properties.get();
 744
 745 #if USE_SINGLE_ENTRY
 746     if (!m_usingTable) {
 747         prop->init(m_singleEntryKey, m_u.singleEntryValue, m_singleEntryAttributes);
 748         return;
 749     }
 750 #endif
 751
 752     // Save in the right order so we don't lose the order.
 753     // Another possibility would be to save the indices.
 754
 755     // Allocate a buffer to use to sort the keys.
 756     Vector<Entry*, smallMapThreshold> sortedEntries(count);
 757
 758     // Get pointers to the entries in the buffer.
 759     Entry** p = sortedEntries.data();
 760     unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
 761     for (unsigned i = 1; i <= entryCount; ++i) {
 762         if (m_u.table->entries()[i].key && !(m_u.table->entries()[i].attributes & (ReadOnly | Function)))
 763             *p++ = &m_u.table->entries()[i];
 764     }
 765     ASSERT(p == sortedEntries.data() + count);
 766
 767     // Sort the entries by index.
 768     qsort(sortedEntries.data(), p - sortedEntries.data(), sizeof(Entry*), comparePropertyMapEntryIndices);
 769
 770     // Put the sorted entries into the saved properties list.
 771     for (Entry** q = sortedEntries.data(); q != p; ++q, ++prop) {
 772         Entry* e = *q;
 773         prop->init(e->key, e->value, e->attributes);
 774     }
 775 }
 776
 777 void PropertyMap::restore(const SavedProperties& p)
 778 {
 779     for (unsigned i = 0; i != p.count; ++i)
 780         put(Identifier(p.properties[i].name()), p.properties[i].value(), p.properties[i].attributes());
 781 }
 782
 783 #if DO_PROPERTYMAP_CONSTENCY_CHECK
 784
 785 void PropertyMap::checkConsistency()
 786 {
 787     if (!m_usingTable)
 788         return;
 789
 790     ASSERT(m_u.table->size >= 16);
 791     ASSERT(m_u.table->sizeMask);
 792     ASSERT(m_u.table->size == m_u.table->sizeMask + 1);
 793     ASSERT(!(m_u.table->size & m_u.table->sizeMask));
 794
 795     ASSERT(m_u.table->keyCount <= m_u.table->size / 2);
 796     ASSERT(m_u.table->deletedSentinelCount <= m_u.table->size / 4);
 797
 798     ASSERT(m_u.table->keyCount + m_u.table->deletedSentinelCount <= m_u.table->size / 2);
 799
 800     unsigned indexCount = 0;
 801     unsigned deletedIndexCount = 0;
 802     for (unsigned a = 0; a != m_u.table->size; ++a) {
 803         unsigned entryIndex = m_u.table->entryIndicies[a];
 804         if (entryIndex == emptyEntryIndex)
 805             continue;
 806         if (entryIndex == deletedSentinelIndex) {
 807             ++deletedIndexCount;
 808             continue;
 809         }
 810         ASSERT(entryIndex > deletedSentinelIndex);
 811         ASSERT(entryIndex - 1 <= m_u.table->keyCount + m_u.table->deletedSentinelCount);
 812         ++indexCount;
 813
 814         for (unsigned b = a + 1; b != m_u.table->size; ++b)
 815             ASSERT(m_u.table->entryIndicies[b] != entryIndex);
 816     }
 817     ASSERT(indexCount == m_u.table->keyCount);
 818     ASSERT(deletedIndexCount == m_u.table->deletedSentinelCount);
 819
 820     ASSERT(m_u.table->entries()[0].key == 0);
 821
 822     unsigned nonEmptyEntryCount = 0;
 823     for (unsigned c = 1; c <= m_u.table->keyCount + m_u.table->deletedSentinelCount; ++c) {
 824         UString::Rep* rep = m_u.table->entries()[c].key;
 825         if (!rep) {
 826             ASSERT(m_u.table->entries()[c].value->isUndefined());
 827             continue;
 828         }
 829         ++nonEmptyEntryCount;
 830         unsigned i = rep->computedHash();
 831         unsigned k = 0;
 832         unsigned entryIndex;
 833         while (1) {
 834             entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
 835             ASSERT(entryIndex != emptyEntryIndex);
 836             if (rep == m_u.table->entries()[entryIndex - 1].key)
 837                 break;
 838             if (k == 0)
 839                 k = 1 | doubleHash(rep->computedHash());
 840             i += k;
 841         }
 842         ASSERT(entryIndex == c + 1);
 843     }
 844
 845     ASSERT(nonEmptyEntryCount == m_u.table->keyCount);
 846 }
 847
 848 #endif // DO_PROPERTYMAP_CONSTENCY_CHECK
 849
 850 } // namespace KJS