JavaScriptCore/kjs/property_map.cpp

   1 /*
   2  *  This file is part of the KDE libraries
   3  *  Copyright (C) 2004 Apple Computer, Inc.
   4  *
   5  *  This library is free software; you can redistribute it and/or
   6  *  modify it under the terms of the GNU Library General Public
   7  *  License as published by the Free Software Foundation; either
   8  *  version 2 of the License, or (at your option) any later version.
   9  *
  10  *  This library is distributed in the hope that it will be useful,
  11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  *  Library General Public License for more details.
  14  *
  15  *  You should have received a copy of the GNU Library General Public License
  16  *  along with this library; see the file COPYING.LIB.  If not, write to
  17  *  the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18  *  Boston, MA 02111-1307, USA.
  19  *
  20  */
  21
  22 #include "property_map.h"
  23
  24 #include "object.h"
  25 #include "protect.h"
  26 #include "reference_list.h"
  27
  28 #define DEBUG_PROPERTIES 0
  29 #define DO_CONSISTENCY_CHECK 0
  30 #define DUMP_STATISTICS 0
  31 #define USE_SINGLE_ENTRY 1
  32
  33 // At the time I added USE_SINGLE_ENTRY, the optimization still gave a 1.5%
  34 // performance boost to the iBench JavaScript benchmark so I didn't remove it.
  35
  36 // FIXME: _singleEntry.index is unused.
  37
  38 #if !DO_CONSISTENCY_CHECK
  39 #define checkConsistency() ((void)0)
  40 #endif
  41
  42 namespace KJS {
  43
  44 // Choose a number for the following so that most property maps are smaller,
  45 // but it's not going to blow out the stack to allocate this number of pointers.
  46 const int smallMapThreshold = 1024;
  47
  48 #if DUMP_STATISTICS
  49
  50 static int numProbes;
  51 static int numCollisions;
  52 static int numRehashes;
  53 static int numRemoves;
  54
  55 struct PropertyMapStatisticsExitLogger { ~PropertyMapStatisticsExitLogger(); };
  56
  57 static PropertyMapStatisticsExitLogger logger;
  58
  59 PropertyMapStatisticsExitLogger::~PropertyMapStatisticsExitLogger()
  60 {
  61     printf("\nKJS::PropertyMap statistics\n\n");
  62     printf("%d probes\n", numProbes);
  63     printf("%d collisions (%.1f%%)\n", numCollisions, 100.0 * numCollisions / numProbes);
  64     printf("%d rehashes\n", numRehashes);
  65     printf("%d removes\n", numRemoves);
  66 }
  67
  68 #endif
  69
  70 // lastIndexUsed is an ever-increasing index used to identify the order items
  71 // were inserted into the property map. It's vital that addEnumerablesToReferenceList
  72 // return the properties in the order they were added for compatibility with other
  73 // browsers' JavaScript implementations.
  74 struct PropertyMapHashTable
  75 {
  76     int sizeMask;
  77     int size;
  78     int keyCount;
  79     int sentinelCount;
  80     int lastIndexUsed;
  81     PropertyMapHashTableEntry entries[1];
  82 };
  83
  84 class SavedProperty {
  85 public:
  86     Identifier key;
  87     ProtectedValue value;
  88     int attributes;
  89 };
  90
  91 SavedProperties::SavedProperties() : _count(0), _properties(0) { }
  92
  93 SavedProperties::~SavedProperties()
  94 {
  95     delete [] _properties;
  96 }
  97
  98 // Algorithm concepts from Algorithms in C++, Sedgewick.
  99
 100 PropertyMap::PropertyMap() : _table(0)
 101 {
 102 }
 103
 104 PropertyMap::~PropertyMap()
 105 {
 106     if (!_table) {
 107 #if USE_SINGLE_ENTRY
 108         UString::Rep *key = _singleEntry.key;
 109         if (key)
 110             key->deref();
 111 #endif
 112         return;
 113     }
 114
 115     for (int i = 0; i < _table->size; i++) {
 116         UString::Rep *key = _table->entries[i].key;
 117         if (key)
 118             key->deref();
 119     }
 120     free(_table);
 121 }
 122
 123 void PropertyMap::clear()
 124 {
 125     if (!_table) {
 126 #if USE_SINGLE_ENTRY
 127         UString::Rep *key = _singleEntry.key;
 128         if (key) {
 129             key->deref();
 130             _singleEntry.key = 0;
 131         }
 132 #endif
 133         return;
 134     }
 135
 136     for (int i = 0; i < _table->size; i++) {
 137         UString::Rep *key = _table->entries[i].key;
 138         if (key) {
 139             key->deref();
 140             _table->entries[i].key = 0;
 141         }
 142     }
 143     _table->keyCount = 0;
 144     _table->sentinelCount = 0;
 145 }
 146
 147 ValueImp *PropertyMap::get(const Identifier &name, int &attributes) const
 148 {
 149     assert(!name.isNull());
 150
 151     UString::Rep *rep = name._ustring.rep;
 152
 153     if (!_table) {
 154 #if USE_SINGLE_ENTRY
 155         UString::Rep *key = _singleEntry.key;
 156         if (rep == key) {
 157             attributes = _singleEntry.attributes;
 158             return _singleEntry.value;
 159         }
 160 #endif
 161         return 0;
 162     }
 163
 164     unsigned h = rep->hash();
 165     int i = h & _table->sizeMask;
 166     int k = 0;
 167 #if DUMP_STATISTICS
 168     ++numProbes;
 169     numCollisions += _table->entries[i].key && _table->entries[i].key != rep;
 170 #endif
 171     while (UString::Rep *key = _table->entries[i].key) {
 172         if (rep == key) {
 173             attributes = _table->entries[i].attributes;
 174             return _table->entries[i].value;
 175         }
 176         if (k == 0)
 177             k = 1 | (h % _table->sizeMask);
 178         i = (i + k) & _table->sizeMask;
 179 #if DUMP_STATISTICS
 180         ++numRehashes;
 181 #endif
 182     }
 183     return 0;
 184 }
 185
 186 ValueImp *PropertyMap::get(const Identifier &name) const
 187 {
 188     assert(!name.isNull());
 189
 190     UString::Rep *rep = name._ustring.rep;
 191
 192     if (!_table) {
 193 #if USE_SINGLE_ENTRY
 194         UString::Rep *key = _singleEntry.key;
 195         if (rep == key)
 196             return _singleEntry.value;
 197 #endif
 198         return 0;
 199     }
 200
 201     unsigned h = rep->hash();
 202     int i = h & _table->sizeMask;
 203     int k = 0;
 204 #if DUMP_STATISTICS
 205     ++numProbes;
 206     numCollisions += _table->entries[i].key && _table->entries[i].key != rep;
 207 #endif
 208     while (UString::Rep *key = _table->entries[i].key) {
 209         if (rep == key)
 210             return _table->entries[i].value;
 211         if (k == 0)
 212             k = 1 | (h % _table->sizeMask);
 213         i = (i + k) & _table->sizeMask;
 214 #if DUMP_STATISTICS
 215         ++numRehashes;
 216 #endif
 217     }
 218     return 0;
 219 }
 220
 221 #if DEBUG_PROPERTIES
 222 static void printAttributes(int attributes)
 223 {
 224     if (attributes == 0)
 225         printf("None");
 226     else {
 227         if (attributes & ReadOnly)
 228             printf("ReadOnly ");
 229         if (attributes & DontEnum)
 230             printf("DontEnum ");
 231         if (attributes & DontDelete)
 232             printf("DontDelete ");
 233         if (attributes & Internal)
 234             printf("Internal ");
 235         if (attributes & Function)
 236             printf("Function ");
 237     }
 238 }
 239 #endif
 240
 241 void PropertyMap::put(const Identifier &name, ValueImp *value, int attributes)
 242 {
 243     assert(!name.isNull());
 244     assert(value != 0);
 245
 246     checkConsistency();
 247
 248     UString::Rep *rep = name._ustring.rep;
 249
 250 #if DEBUG_PROPERTIES
 251     printf("adding property %s, attributes = 0x%08x (", name.ascii(), attributes);
 252     printAttributes(attributes);
 253     printf(")\n");
 254 #endif
 255
 256 #if USE_SINGLE_ENTRY
 257     if (!_table) {
 258         UString::Rep *key = _singleEntry.key;
 259         if (key) {
 260             if (rep == key) {
 261                 _singleEntry.value = value;
 262                 return;
 263             }
 264         } else {
 265             rep->ref();
 266             _singleEntry.key = rep;
 267             _singleEntry.value = value;
 268             _singleEntry.attributes = attributes;
 269             checkConsistency();
 270             return;
 271         }
 272     }
 273 #endif
 274
 275     if (!_table || _table->keyCount * 2 >= _table->size)
 276         expand();
 277
 278     unsigned h = rep->hash();
 279     int i = h & _table->sizeMask;
 280     int k = 0;
 281     bool foundDeletedElement = false;
 282     int deletedElementIndex = 0;    /* initialize to make the compiler happy */
 283 #if DUMP_STATISTICS
 284     ++numProbes;
 285     numCollisions += _table->entries[i].key && _table->entries[i].key != rep;
 286 #endif
 287     while (UString::Rep *key = _table->entries[i].key) {
 288         if (rep == key) {
 289             // Put a new value in an existing hash table entry.
 290             _table->entries[i].value = value;
 291             // Attributes are intentionally not updated.
 292             return;
 293         }
 294         // If we find the deleted-element sentinel, remember it for use later.
 295         if (key == &UString::Rep::null && !foundDeletedElement) {
 296             foundDeletedElement = true;
 297             deletedElementIndex = i;
 298         }
 299         if (k == 0)
 300             k = 1 | (h % _table->sizeMask);
 301         i = (i + k) & _table->sizeMask;
 302 #if DUMP_STATISTICS
 303         ++numRehashes;
 304 #endif
 305     }
 306
 307     // Use either the deleted element or the 0 at the end of the chain.
 308     if (foundDeletedElement) {
 309         i = deletedElementIndex;
 310         _table->entries[i].key->deref();
 311         --_table->sentinelCount;
 312     }
 313
 314     // Create a new hash table entry.
 315     rep->ref();
 316     _table->entries[i].key = rep;
 317     _table->entries[i].value = value;
 318     _table->entries[i].attributes = attributes;
 319     _table->entries[i].index = ++_table->lastIndexUsed;
 320     ++_table->keyCount;
 321
 322     checkConsistency();
 323 }
 324
 325 void PropertyMap::insert(UString::Rep *key, ValueImp *value, int attributes, int index)
 326 {
 327     assert(_table);
 328
 329     unsigned h = key->hash();
 330     int i = h & _table->sizeMask;
 331     int k = 0;
 332 #if DUMP_STATISTICS
 333     ++numProbes;
 334     numCollisions += _table->entries[i].key && _table->entries[i].key != key;
 335 #endif
 336     while (_table->entries[i].key) {
 337         assert(_table->entries[i].key != &UString::Rep::null);
 338         if (k == 0)
 339             k = 1 | (h % _table->sizeMask);
 340         i = (i + k) & _table->sizeMask;
 341 #if DUMP_STATISTICS
 342         ++numRehashes;
 343 #endif
 344     }
 345
 346     _table->entries[i].key = key;
 347     _table->entries[i].value = value;
 348     _table->entries[i].attributes = attributes;
 349     _table->entries[i].index = index;
 350 }
 351
 352 void PropertyMap::expand()
 353 {
 354     Table *oldTable = _table;
 355     int oldTableSize = oldTable ? oldTable->size : 0;
 356     rehash(oldTableSize ? oldTableSize * 2 : 16);
 357 }
 358
 359 void PropertyMap::rehash()
 360 {
 361     assert(_table);
 362     assert(_table->size);
 363     rehash(_table->size);
 364 }
 365
 366 void PropertyMap::rehash(int newTableSize)
 367 {
 368     checkConsistency();
 369
 370     Table *oldTable = _table;
 371     int oldTableSize = oldTable ? oldTable->size : 0;
 372     int oldTableKeyCount = oldTable ? oldTable->keyCount : 0;
 373
 374     _table = (Table *)calloc(1, sizeof(Table) + (newTableSize - 1) * sizeof(Entry) );
 375     _table->size = newTableSize;
 376     _table->sizeMask = newTableSize - 1;
 377     _table->keyCount = oldTableKeyCount;
 378
 379 #if USE_SINGLE_ENTRY
 380     UString::Rep *key = _singleEntry.key;
 381     if (key) {
 382         insert(key, _singleEntry.value, _singleEntry.attributes, 0);
 383         _singleEntry.key = 0;
 384         // update the count, because single entries don't count towards
 385         // the table key count
 386         ++_table->keyCount;
 387         assert(_table->keyCount == 1);
 388     }
 389 #endif
 390
 391     int lastIndexUsed = 0;
 392     for (int i = 0; i != oldTableSize; ++i) {
 393         Entry &entry = oldTable->entries[i];
 394         UString::Rep *key = entry.key;
 395         if (key) {
 396             // Don't copy deleted-element sentinels.
 397             if (key == &UString::Rep::null)
 398                 key->deref();
 399             else {
 400                 int index = entry.index;
 401                 lastIndexUsed = MAX(index, lastIndexUsed);
 402                 insert(key, entry.value, entry.attributes, index);
 403             }
 404         }
 405     }
 406     _table->lastIndexUsed = lastIndexUsed;
 407
 408     free(oldTable);
 409
 410     checkConsistency();
 411 }
 412
 413 void PropertyMap::remove(const Identifier &name)
 414 {
 415     assert(!name.isNull());
 416
 417     checkConsistency();
 418
 419     UString::Rep *rep = name._ustring.rep;
 420
 421     UString::Rep *key;
 422
 423     if (!_table) {
 424 #if USE_SINGLE_ENTRY
 425         key = _singleEntry.key;
 426         if (rep == key) {
 427             key->deref();
 428             _singleEntry.key = 0;
 429             checkConsistency();
 430         }
 431 #endif
 432         return;
 433     }
 434
 435     // Find the thing to remove.
 436     unsigned h = rep->hash();
 437     int i = h & _table->sizeMask;
 438     int k = 0;
 439 #if DUMP_STATISTICS
 440     ++numProbes;
 441     ++numRemoves;
 442     numCollisions += _table->entries[i].key && _table->entries[i].key != rep;
 443 #endif
 444     while ((key = _table->entries[i].key)) {
 445         if (rep == key)
 446             break;
 447         if (k == 0)
 448             k = 1 | (h % _table->sizeMask);
 449         i = (i + k) & _table->sizeMask;
 450 #if DUMP_STATISTICS
 451         ++numRehashes;
 452 #endif
 453     }
 454     if (!key)
 455         return;
 456
 457     // Replace this one element with the deleted sentinel,
 458     // &UString::Rep::null; also set value to 0 and attributes to DontEnum
 459     // to help callers that iterate all keys not have to check for the sentinel.
 460     key->deref();
 461     key = &UString::Rep::null;
 462     key->ref();
 463     _table->entries[i].key = key;
 464     _table->entries[i].value = 0;
 465     _table->entries[i].attributes = DontEnum;
 466     assert(_table->keyCount >= 1);
 467     --_table->keyCount;
 468     ++_table->sentinelCount;
 469
 470     if (_table->sentinelCount * 4 >= _table->size)
 471         rehash();
 472
 473     checkConsistency();
 474 }
 475
 476 void PropertyMap::mark() const
 477 {
 478     if (!_table) {
 479 #if USE_SINGLE_ENTRY
 480         if (_singleEntry.key) {
 481             ValueImp *v = _singleEntry.value;
 482             if (!v->marked())
 483                 v->mark();
 484         }
 485 #endif
 486         return;
 487     }
 488
 489     for (int i = 0; i != _table->size; ++i) {
 490         UString::Rep *key = _table->entries[i].key;
 491         if (key) {
 492             ValueImp *v = _table->entries[i].value;
 493             // Check v against 0 to handle deleted elements
 494             // without comparing key to UString::Rep::null.
 495             if (v && !v->marked())
 496                 v->mark();
 497         }
 498     }
 499 }
 500
 501 static int comparePropertyMapEntryIndices(const void *a, const void *b)
 502 {
 503     int ia = static_cast<PropertyMapHashTableEntry * const *>(a)[0]->index;
 504     int ib = static_cast<PropertyMapHashTableEntry * const *>(b)[0]->index;
 505     if (ia < ib)
 506         return -1;
 507     if (ia > ib)
 508         return +1;
 509     return 0;
 510 }
 511
 512 void PropertyMap::addEnumerablesToReferenceList(ReferenceList &list, const Object &base) const
 513 {
 514     if (!_table) {
 515 #if USE_SINGLE_ENTRY
 516         UString::Rep *key = _singleEntry.key;
 517         if (key && !(_singleEntry.attributes & DontEnum))
 518             list.append(Reference(base, Identifier(key)));
 519 #endif
 520         return;
 521     }
 522
 523     // Allocate a buffer to use to sort the keys.
 524     Entry *fixedSizeBuffer[smallMapThreshold];
 525     Entry **sortedEnumerables;
 526     if (_table->keyCount <= smallMapThreshold)
 527         sortedEnumerables = fixedSizeBuffer;
 528     else
 529         sortedEnumerables = new Entry *[_table->keyCount];
 530
 531     // Get pointers to the enumerable entries in the buffer.
 532     Entry **p = sortedEnumerables;
 533     for (int i = 0; i != _table->size; ++i) {
 534         Entry *e = &_table->entries[i];
 535         if (e->key && !(e->attributes & DontEnum))
 536             *p++ = e;
 537     }
 538
 539     // Sort the entries by index.
 540     qsort(sortedEnumerables, p - sortedEnumerables, sizeof(sortedEnumerables[0]), comparePropertyMapEntryIndices);
 541
 542     // Put the keys of the sorted entries into the reference list.
 543     Entry **q = sortedEnumerables;
 544     while (q != p)
 545         list.append(Reference(base, Identifier((*q++)->key)));
 546
 547     // Deallocate the buffer.
 548     if (sortedEnumerables != fixedSizeBuffer)
 549         delete [] sortedEnumerables;
 550 }
 551
 552 void PropertyMap::addSparseArrayPropertiesToReferenceList(ReferenceList &list, const Object &base) const
 553 {
 554     if (!_table) {
 555 #if USE_SINGLE_ENTRY
 556         UString::Rep *key = _singleEntry.key;
 557         if (key) {
 558             UString k(key);
 559             bool fitsInUInt32;
 560             k.toUInt32(&fitsInUInt32);
 561             if (fitsInUInt32)
 562                 list.append(Reference(base, Identifier(key)));
 563         }
 564 #endif
 565         return;
 566     }
 567
 568     for (int i = 0; i != _table->size; ++i) {
 569         UString::Rep *key = _table->entries[i].key;
 570         if (key && key != &UString::Rep::null)
 571         {
 572             UString k(key);
 573             bool fitsInUInt32;
 574             k.toUInt32(&fitsInUInt32);
 575             if (fitsInUInt32)
 576                 list.append(Reference(base, Identifier(key)));
 577         }
 578     }
 579 }
 580
 581 void PropertyMap::save(SavedProperties &p) const
 582 {
 583     int count = 0;
 584
 585     if (!_table) {
 586 #if USE_SINGLE_ENTRY
 587         if (_singleEntry.key && !(_singleEntry.attributes & (ReadOnly | Function)))
 588             ++count;
 589 #endif
 590     } else {
 591         for (int i = 0; i != _table->size; ++i)
 592             if (_table->entries[i].key && !(_table->entries[i].attributes & (ReadOnly | Function)))
 593                 ++count;
 594     }
 595
 596     delete [] p._properties;
 597
 598     p._count = count;
 599
 600     if (count == 0) {
 601         p._properties = 0;
 602         return;
 603     }
 604
 605     p._properties = new SavedProperty [count];
 606
 607     SavedProperty *prop = p._properties;
 608
 609     if (!_table) {
 610 #if USE_SINGLE_ENTRY
 611         if (_singleEntry.key && !(_singleEntry.attributes & (ReadOnly | Function))) {
 612             prop->key = Identifier(_singleEntry.key);
 613             prop->value = Value(_singleEntry.value);
 614             prop->attributes = _singleEntry.attributes;
 615             ++prop;
 616         }
 617 #endif
 618     } else {
 619         // Save in the right order so we don't lose the order.
 620         // Another possibility would be to save the indices.
 621
 622         // Allocate a buffer to use to sort the keys.
 623         Entry *fixedSizeBuffer[smallMapThreshold];
 624         Entry **sortedEntries;
 625         if (count <= smallMapThreshold)
 626             sortedEntries = fixedSizeBuffer;
 627         else
 628             sortedEntries = new Entry *[count];
 629
 630         // Get pointers to the entries in the buffer.
 631         Entry **p = sortedEntries;
 632         for (int i = 0; i != _table->size; ++i) {
 633             Entry *e = &_table->entries[i];
 634             if (e->key && !(e->attributes & (ReadOnly | Function)))
 635                 *p++ = e;
 636         }
 637         assert(p - sortedEntries == count);
 638
 639         // Sort the entries by index.
 640         qsort(sortedEntries, p - sortedEntries, sizeof(sortedEntries[0]), comparePropertyMapEntryIndices);
 641
 642         // Put the sorted entries into the saved properties list.
 643         Entry **q = sortedEntries;
 644         while (q != p) {
 645             Entry *e = *q++;
 646             prop->key = Identifier(e->key);
 647             prop->value = Value(e->value);
 648             prop->attributes = e->attributes;
 649             ++prop;
 650         }
 651
 652         // Deallocate the buffer.
 653         if (sortedEntries != fixedSizeBuffer)
 654             delete [] sortedEntries;
 655     }
 656 }
 657
 658 void PropertyMap::restore(const SavedProperties &p)
 659 {
 660     for (int i = 0; i != p._count; ++i)
 661         put(p._properties[i].key, p._properties[i].value.imp(), p._properties[i].attributes);
 662 }
 663
 664 #if DO_CONSISTENCY_CHECK
 665
 666 void PropertyMap::checkConsistency()
 667 {
 668     if (!_table)
 669         return;
 670
 671     int count = 0;
 672     int sentinelCount = 0;
 673     for (int j = 0; j != _table->size; ++j) {
 674         UString::Rep *rep = _table->entries[j].key;
 675         if (!rep)
 676             continue;
 677         if (rep == &UString::Rep::null) {
 678             ++sentinelCount;
 679             continue;
 680         }
 681         unsigned h = rep->hash();
 682         int i = h & _table->sizeMask;
 683         int k = 0;
 684         while (UString::Rep *key = _table->entries[i].key) {
 685             if (rep == key)
 686                 break;
 687             if (k == 0)
 688                 k = 1 | (h % _table->sizeMask);
 689             i = (i + k) & _table->sizeMask;
 690         }
 691         assert(i == j);
 692         ++count;
 693     }
 694     assert(count == _table->keyCount);
 695     assert(sentinelCount == _table->sentinelCount);
 696     assert(_table->size >= 16);
 697     assert(_table->sizeMask);
 698     assert(_table->size == _table->sizeMask + 1);
 699 }
 700
 701 #endif // DO_CONSISTENCY_CHECK
 702
 703 } // namespace KJS