Changeset 27387 in webkit


Ignore:
Timestamp:
Nov 2, 2007, 5:46:32 PM (17 years ago)
Author:
Darin Adler
Message:

Reviewed by Maciej.

The property map now has an array of indices and a separate array of
property map entries. This slightly slows down lookup because of a second
memory acess, but makes property maps smaller and faster to iterate in
functions like mark().

SunSpider says this is 1.2% faster, although it makes the bitwise-end test
more than 10% slower. To fix that we'll need to optimize global variable lookup.

  • kjs/property_map.cpp: (KJS::PropertyMapEntry::PropertyMapEntry): (KJS::PropertyMapHashTable::entries): (KJS::PropertyMapHashTable::allocationSize): (KJS::SavedProperties::SavedProperties): (KJS::SavedProperties::~SavedProperties): (KJS::PropertyMap::checkConsistency): (KJS::PropertyMap::~PropertyMap): (KJS::PropertyMap::clear): (KJS::PropertyMap::get): (KJS::PropertyMap::getLocation): (KJS::PropertyMap::put): (KJS::PropertyMap::insert): (KJS::PropertyMap::createTable): (KJS::PropertyMap::rehash): (KJS::PropertyMap::remove): (KJS::PropertyMap::mark): (KJS::comparePropertyMapEntryIndices): (KJS::PropertyMap::containsGettersOrSetters): (KJS::PropertyMap::getEnumerablePropertyNames): (KJS::PropertyMap::save): (KJS::PropertyMap::restore):
  • kjs/property_map.h:
Location:
trunk/JavaScriptCore
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • trunk/JavaScriptCore/ChangeLog

    r27385 r27387  
     12007-11-02  Darin Adler  <darin@apple.com>
     2
     3        Reviewed by Maciej.
     4
     5        - http://bugs.webkit.org/show_bug.cgi?id=15791
     6          change property map data structure for less memory use, better speed
     7
     8        The property map now has an array of indices and a separate array of
     9        property map entries. This slightly slows down lookup because of a second
     10        memory acess, but makes property maps smaller and faster to iterate in
     11        functions like mark().
     12
     13        SunSpider says this is 1.2% faster, although it makes the bitwise-end test
     14        more than 10% slower. To fix that we'll need to optimize global variable lookup.
     15
     16        * kjs/property_map.cpp:
     17        (KJS::PropertyMapEntry::PropertyMapEntry):
     18        (KJS::PropertyMapHashTable::entries):
     19        (KJS::PropertyMapHashTable::allocationSize):
     20        (KJS::SavedProperties::SavedProperties):
     21        (KJS::SavedProperties::~SavedProperties):
     22        (KJS::PropertyMap::checkConsistency):
     23        (KJS::PropertyMap::~PropertyMap):
     24        (KJS::PropertyMap::clear):
     25        (KJS::PropertyMap::get):
     26        (KJS::PropertyMap::getLocation):
     27        (KJS::PropertyMap::put):
     28        (KJS::PropertyMap::insert):
     29        (KJS::PropertyMap::createTable):
     30        (KJS::PropertyMap::rehash):
     31        (KJS::PropertyMap::remove):
     32        (KJS::PropertyMap::mark):
     33        (KJS::comparePropertyMapEntryIndices):
     34        (KJS::PropertyMap::containsGettersOrSetters):
     35        (KJS::PropertyMap::getEnumerablePropertyNames):
     36        (KJS::PropertyMap::save):
     37        (KJS::PropertyMap::restore):
     38        * kjs/property_map.h:
     39
    1402007-11-02  Darin Adler  <darin@apple.com>
    241

  • trunk/JavaScriptCore/kjs/property_map.cpp

    r27305 r27387  
    11/*
    2  *  This file is part of the KDE libraries
    3  *  Copyright (C) 2004, 2005, 2006 Apple Computer, Inc.
     2 *  Copyright (C) 2004, 2005, 2006, 2007 Apple Inc. All rights reserved.
    43 *
    54 *  This library is free software; you can redistribute it and/or
    … …  
    3534using WTF::doubleHash;
    3635
    37 #define DEBUG_PROPERTIES 0
    38 #define DO_CONSISTENCY_CHECK 0
     36#ifndef NDEBUG
     37#define DO_PROPERTYMAP_CONSTENCY_CHECK 0
    3938#define DUMP_PROPERTYMAP_STATS 0
     39#else
     40#define DO_PROPERTYMAP_CONSTENCY_CHECK 0
     41#define DUMP_PROPERTYMAP_STATS 0
     42#endif
     43
    4044#define USE_SINGLE_ENTRY 1
    4145
    4246// 2/28/2006 ggaren: command-line JS iBench says that USE_SINGLE_ENTRY is a
    4347// 3.2% performance boost.
    44 
    45 #if !DO_CONSISTENCY_CHECK
    46 #define checkConsistency() ((void)0)
    47 #endif
    4848
    4949namespace KJS {
    … …  
    7575#endif
    7676
     77struct PropertyMapEntry {
     78    UString::Rep* key;
     79    JSValue* value;
     80    unsigned attributes;
     81    unsigned index;
     82
     83    PropertyMapEntry(UString::Rep* k, JSValue* v, int a)
     84        : key(k), value(v), attributes(a), index(0)
     85    {
     86    }
     87};
     88
    7789// lastIndexUsed is an ever-increasing index used to identify the order items
    78 // were inserted into the property map. It's vital that getEnumerablePropertyNames
     90// were inserted into the property map. It's required that getEnumerablePropertyNames
    7991// return the properties in the order they were added for compatibility with other
    8092// browsers' JavaScript implementations.
    81 struct PropertyMapHashTable
    82 {
    83     int sizeMask;
    84     int size;
    85     int keyCount;
    86     int sentinelCount;
    87     int lastIndexUsed;
    88     PropertyMapHashTableEntry entries[1];
     93struct PropertyMapHashTable {
     94    unsigned sizeMask;
     95    unsigned size;
     96    unsigned keyCount;
     97    unsigned deletedSentinelCount;
     98    unsigned lastIndexUsed;
     99    unsigned entryIndicies[1];
     100
     101    PropertyMapEntry* entries()
     102    {
     103        // The entries vector comes after the indices vector.
     104        // The 0th item in the entries vector is not really used; it has to
     105        // have a 0 in its key to allow the hash table lookup to handle deleted
     106        // sentinels without any special-case code, but the other fields are unused.
     107        return reinterpret_cast<PropertyMapEntry*>(&entryIndicies[size]);
     108    }
     109
     110    static size_t allocationSize(unsigned size)
     111    {
     112        // We never let a hash table get more than half full,
     113        // So the number of indices we need is the size of the hash table.
     114        // But the number of entries is half that (plus one for the deleted sentinel).
     115        return sizeof(PropertyMapHashTable)
     116            + (size - 1) * sizeof(unsigned)
     117            + (1 + size / 2) * sizeof(PropertyMapEntry);
     118    }
    89119};
    90120
    91 class SavedProperty {
    92 public:
     121struct SavedProperty {
    93122    Identifier key;
    94123    ProtectedPtr<JSValue> value;
    95     int attributes;
     124    unsigned attributes;
    96125};
    97126
    98 SavedProperties::SavedProperties() : _count(0) { }
    99 SavedProperties::~SavedProperties() { }
    100 
    101 // Algorithm concepts from Algorithms in C++, Sedgewick.
    102 
    103 // This is a method rather than a variable to work around <rdar://problem/4462053>
    104 static inline UString::Rep* deletedSentinel() { return reinterpret_cast<UString::Rep*>(0x1); }
    105 
    106 // Returns true if the key is not null or the deleted sentinel, false otherwise
    107 static inline bool isValid(UString::Rep* key)
    108 {
    109     return !!(reinterpret_cast<uintptr_t>(key) & ~0x1);
    110 }
     127static const unsigned emptyEntryIndex = 0;
     128static const unsigned deletedSentinelIndex = 1;
     129
     130SavedProperties::SavedProperties()
     131    : m_count(0)
     132{
     133}
     134
     135SavedProperties::~SavedProperties()
     136{
     137}
     138
     139#if !DO_PROPERTYMAP_CONSTENCY_CHECK
     140
     141inline void PropertyMap::checkConsistency()
     142{
     143}
     144
     145#endif
    111146
    112147PropertyMap::~PropertyMap()
    … …  
    114149    if (!m_usingTable) {
    115150#if USE_SINGLE_ENTRY
    116         UString::Rep* key = m_singleEntryKey;
    117         if (key)
     151        if (m_singleEntryKey)
     152            m_singleEntryKey->deref();
     153#endif
     154        return;
     155    }
     156   
     157    unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
     158    for (unsigned i = 1; i <= entryCount; i++) {
     159        if (UString::Rep* key = m_u.table->entries()[i].key)
    118160            key->deref();
     161    }
     162    fastFree(m_u.table);
     163}
     164
     165void PropertyMap::clear()
     166{
     167    if (!m_usingTable) {
     168#if USE_SINGLE_ENTRY
     169        if (m_singleEntryKey) {
     170            m_singleEntryKey->deref();
     171            m_singleEntryKey = 0;
     172        }
    119173#endif
    120174        return;
    121175    }
    122    
    123     int minimumKeysToProcess = m_u.table->keyCount + m_u.table->sentinelCount;
    124     Entry *entries = m_u.table->entries;
    125     for (int i = 0; i < minimumKeysToProcess; i++) {
    126         UString::Rep *key = entries[i].key;
    127         if (key) {
    128             if (key != deletedSentinel())
    129                 key->deref();
    130         } else
    131             ++minimumKeysToProcess;
    132     }
    133     fastFree(m_u.table);
    134 }
    135 
    136 void PropertyMap::clear()
    137 {
    138     if (!m_usingTable) {
    139 #if USE_SINGLE_ENTRY
    140         UString::Rep* key = m_singleEntryKey;
    141         if (key) {
     176
     177    unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
     178    for (unsigned i = 1; i <= entryCount; i++) {
     179        if (UString::Rep* key = m_u.table->entries()[i].key)
    142180            key->deref();
    143             m_singleEntryKey = 0;
    144         }
    145 #endif
    146         return;
    147     }
    148 
    149     int size = m_u.table->size;
    150     Entry *entries = m_u.table->entries;
    151     for (int i = 0; i < size; i++) {
    152         UString::Rep *key = entries[i].key;
    153         if (isValid(key)) {
    154             key->deref();
    155             entries[i].key = 0;
    156             entries[i].value = 0;
    157         }
    158     }
     181    }
     182    for (unsigned i = 0; i < m_u.table->size; i++)
     183        m_u.table->entryIndicies[i] = emptyEntryIndex;
    159184    m_u.table->keyCount = 0;
    160     m_u.table->sentinelCount = 0;
    161 }
    162 
    163 JSValue *PropertyMap::get(const Identifier &name, unsigned &attributes) const
     185    m_u.table->deletedSentinelCount = 0;
     186}
     187
     188JSValue* PropertyMap::get(const Identifier& name, unsigned& attributes) const
    164189{
    165190    ASSERT(!name.isNull());
    166191   
    167     UString::Rep *rep = name._ustring.rep();
    168    
    169     if (!m_usingTable) {
    170 #if USE_SINGLE_ENTRY
    171         UString::Rep* key = m_singleEntryKey;
    172         if (rep == key) {
     192    UString::Rep* rep = name._ustring.rep();
     193   
     194    if (!m_usingTable) {
     195#if USE_SINGLE_ENTRY
     196        if (rep == m_singleEntryKey) {
    173197            attributes = m_singleEntryAttributes;
    174198            return m_u.singleEntryValue;
    … …  
    178202    }
    179203   
    180     unsigned h = rep->computedHash();
    181     int sizeMask = m_u.table->sizeMask;
    182     Entry *entries = m_u.table->entries;
    183     int i = h & sizeMask;
    184     int k = 0;
     204    unsigned i = rep->computedHash();
     205
    185206#if DUMP_PROPERTYMAP_STATS
    186207    ++numProbes;
    187     numCollisions += entries[i].key && entries[i].key != rep;
    188 #endif
     208#endif
     209
     210    unsigned entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
     211    if (entryIndex == emptyEntryIndex)
     212        return 0;
     213
     214    if (rep == m_u.table->entries()[entryIndex - 1].key) {
     215        attributes = m_u.table->entries()[entryIndex - 1].attributes;
     216        return m_u.table->entries()[entryIndex - 1].value;
     217    }
     218
     219#if DUMP_PROPERTYMAP_STATS
     220    ++numCollisions;
     221#endif
     222
     223    unsigned k = 1 | doubleHash(rep->computedHash());
     224
    189225    while (1) {
    190         UString::Rep* key = entries[i].key;
    191 
    192         if (!key)
     226        i += k;
     227
     228#if DUMP_PROPERTYMAP_STATS
     229        ++numRehashes;
     230#endif
     231
     232        entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
     233        if (entryIndex == emptyEntryIndex)
    193234            return 0;
    194235
    195         if (rep == key) {
    196             attributes = entries[i].attributes;
    197             return entries[i].value;
    198         }
    199        
    200         if (k == 0)
    201             k = 1 | doubleHash(h);
    202         i = (i + k) & sizeMask;
     236        if (rep == m_u.table->entries()[entryIndex - 1].key) {
     237            attributes = m_u.table->entries()[entryIndex - 1].attributes;
     238            return m_u.table->entries()[entryIndex - 1].value;
     239        }
     240    }
     241}
     242
     243JSValue* PropertyMap::get(const Identifier& name) const
     244{
     245    ASSERT(!name.isNull());
     246   
     247    UString::Rep* rep = name._ustring.rep();
     248   
     249    if (!m_usingTable) {
     250#if USE_SINGLE_ENTRY
     251        if (rep == m_singleEntryKey)
     252            return m_u.singleEntryValue;
     253#endif
     254        return 0;
     255    }
     256   
     257    unsigned i = rep->computedHash();
     258
     259#if DUMP_PROPERTYMAP_STATS
     260    ++numProbes;
     261#endif
     262
     263    unsigned entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
     264    if (entryIndex == emptyEntryIndex)
     265        return 0;
     266
     267    if (rep == m_u.table->entries()[entryIndex - 1].key)
     268        return m_u.table->entries()[entryIndex - 1].value;
     269
     270#if DUMP_PROPERTYMAP_STATS
     271    ++numCollisions;
     272#endif
     273
     274    unsigned k = 1 | doubleHash(rep->computedHash());
     275
     276    while (1) {
     277        i += k;
     278
    203279#if DUMP_PROPERTYMAP_STATS
    204280        ++numRehashes;
    205281#endif
    206     }
    207 }
    208 
    209 JSValue *PropertyMap::get(const Identifier &name) const
     282
     283        entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
     284        if (entryIndex == emptyEntryIndex)
     285            return 0;
     286
     287        if (rep == m_u.table->entries()[entryIndex - 1].key)
     288            return m_u.table->entries()[entryIndex - 1].value;
     289    }
     290}
     291
     292JSValue** PropertyMap::getLocation(const Identifier& name)
    210293{
    211294    ASSERT(!name.isNull());
    212295   
    213     UString::Rep *rep = name._ustring.rep();
    214 
    215     if (!m_usingTable) {
    216 #if USE_SINGLE_ENTRY
    217         UString::Rep *key = m_singleEntryKey;
    218         if (rep == key)
    219             return m_u.singleEntryValue;
     296    UString::Rep* rep = name._ustring.rep();
     297   
     298    if (!m_usingTable) {
     299#if USE_SINGLE_ENTRY
     300        if (rep == m_singleEntryKey)
     301            return &m_u.singleEntryValue;
    220302#endif
    221303        return 0;
    222304    }
    223305   
    224     unsigned h = rep->computedHash();
    225     int sizeMask = m_u.table->sizeMask;
    226     Entry *entries = m_u.table->entries;
    227     int i = h & sizeMask;
    228     int k = 0;
     306    unsigned i = rep->computedHash();
     307
    229308#if DUMP_PROPERTYMAP_STATS
    230309    ++numProbes;
    231     numCollisions += entries[i].key && entries[i].key != rep;
    232 #endif
     310#endif
     311
     312    unsigned entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
     313    if (entryIndex == emptyEntryIndex)
     314        return 0;
     315
     316    if (rep == m_u.table->entries()[entryIndex - 1].key)
     317        return &m_u.table->entries()[entryIndex - 1].value;
     318
     319#if DUMP_PROPERTYMAP_STATS
     320    ++numCollisions;
     321#endif
     322
     323    unsigned k = 1 | doubleHash(rep->computedHash());
     324
    233325    while (1) {
    234         UString::Rep* key = entries[i].key;
    235 
    236         if (!key)
     326        i += k;
     327
     328#if DUMP_PROPERTYMAP_STATS
     329        ++numRehashes;
     330#endif
     331
     332        entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
     333        if (entryIndex == emptyEntryIndex)
    237334            return 0;
    238335
    239         if (rep == key)
    240             return entries[i].value;
    241        
    242         if (k == 0)
    243             k = 1 | doubleHash(h);
    244         i = (i + k) & sizeMask;
    245 #if DUMP_PROPERTYMAP_STATS
    246         ++numRehashes;
    247 #endif
    248     }
    249 }
    250 
    251 JSValue **PropertyMap::getLocation(const Identifier &name)
     336        if (rep == m_u.table->entries()[entryIndex - 1].key)
     337            return &m_u.table->entries()[entryIndex - 1].value;
     338    }
     339}
     340
     341void PropertyMap::put(const Identifier& name, JSValue* value, unsigned attributes, bool checkReadOnly)
    252342{
    253343    ASSERT(!name.isNull());
    254    
    255     UString::Rep *rep = name._ustring.rep();
    256 
    257     if (!m_usingTable) {
    258 #if USE_SINGLE_ENTRY
    259         UString::Rep *key = m_singleEntryKey;
    260         if (rep == key)
    261             return &m_u.singleEntryValue;
    262 #endif
    263         return 0;
    264     }
    265    
    266     unsigned h = rep->computedHash();
    267     int sizeMask = m_u.table->sizeMask;
    268     Entry *entries = m_u.table->entries;
    269     int i = h & sizeMask;
    270     int k = 0;
    271 #if DUMP_PROPERTYMAP_STATS
    272     ++numProbes;
    273     numCollisions += entries[i].key && entries[i].key != rep;
    274 #endif
    275     while (1) {
    276         UString::Rep* key = entries[i].key;
    277 
    278         if (!key)
    279             return 0;
    280 
    281         if (rep == key)
    282             return &entries[i].value;
    283        
    284         if (k == 0)
    285             k = 1 | doubleHash(h);
    286         i = (i + k) & sizeMask;
    287 #if DUMP_PROPERTYMAP_STATS
    288         ++numRehashes;
    289 #endif
    290     }
    291 }
    292 
    293 #if DEBUG_PROPERTIES
    294 static void printAttributes(int attributes)
    295 {
    296     if (attributes == 0)
    297         printf("None");
    298     else {
    299         if (attributes & ReadOnly)
    300             printf("ReadOnly ");
    301         if (attributes & DontEnum)
    302             printf("DontEnum ");
    303         if (attributes & DontDelete)
    304             printf("DontDelete ");
    305         if (attributes & Internal)
    306             printf("Internal ");
    307         if (attributes & Function)
    308             printf("Function ");
    309     }
    310 }
    311 #endif
    312 
    313 void PropertyMap::put(const Identifier &name, JSValue *value, int attributes, bool roCheck)
    314 {
    315     ASSERT(!name.isNull());
    316     ASSERT(value != 0);
     344    ASSERT(value);
    317345   
    318346    checkConsistency();
    319347
    320     UString::Rep *rep = name._ustring.rep();
    321    
    322 #if DEBUG_PROPERTIES
    323     printf("adding property %s, attributes = 0x%08x (", name.ascii(), attributes);
    324     printAttributes(attributes);
    325     printf(")\n");
    326 #endif
    327    
    328 #if USE_SINGLE_ENTRY
    329     if (!m_usingTable) {
    330         UString::Rep *key = m_singleEntryKey;
    331         if (key) {
    332             if (rep == key && !(roCheck && (m_singleEntryAttributes & ReadOnly))) {
    333                 m_u.singleEntryValue = value;
    334                 return;
    335             }
    336         } else {
     348    UString::Rep* rep = name._ustring.rep();
     349   
     350#if USE_SINGLE_ENTRY
     351    if (!m_usingTable) {
     352        if (!m_singleEntryKey) {
    337353            rep->ref();
    338354            m_singleEntryKey = rep;
    … …  
    342358            return;
    343359        }
    344     }
    345 #endif
    346 
    347     if (!m_usingTable || m_u.table->keyCount * 2 >= m_u.table->size)
     360        if (rep == m_singleEntryKey && !(checkReadOnly && (m_singleEntryAttributes & ReadOnly))) {
     361            m_u.singleEntryValue = value;
     362            return;
     363        }
     364    }
     365#endif
     366
     367    if (!m_usingTable || (m_u.table->keyCount + m_u.table->deletedSentinelCount) * 2 >= m_u.table->size)
    348368        expand();
    349    
    350     unsigned h = rep->computedHash();
    351     int sizeMask = m_u.table->sizeMask;
    352     Entry *entries = m_u.table->entries;
    353     int i = h & sizeMask;
    354     int k = 0;
     369
     370    // FIXME: Consider a fast case for tables with no deleted sentinels.
     371
     372    unsigned i = rep->computedHash();
     373    unsigned k = 0;
    355374    bool foundDeletedElement = false;
    356     int deletedElementIndex = 0;    /* initialize to make the compiler happy */
     375    unsigned deletedElementIndex = 0; // initialize to make the compiler happy
     376
    357377#if DUMP_PROPERTYMAP_STATS
    358378    ++numProbes;
    359     numCollisions += entries[i].key && entries[i].key != rep;
    360 #endif
    361     while (UString::Rep *key = entries[i].key) {
    362         if (rep == key) {
    363             if (roCheck && (m_u.table->entries[i].attributes & ReadOnly))
     379#endif
     380
     381    while (1) {
     382        unsigned entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
     383        if (entryIndex == emptyEntryIndex)
     384            break;
     385
     386        if (m_u.table->entries()[entryIndex - 1].key == rep) {
     387            if (checkReadOnly && (m_u.table->entries()[entryIndex - 1].attributes & ReadOnly))
    364388                return;
    365389            // Put a new value in an existing hash table entry.
    366             entries[i].value = value;
     390            m_u.table->entries()[entryIndex - 1].value = value;
    367391            // Attributes are intentionally not updated.
    368392            return;
    369         }
    370         // If we find the deleted-element sentinel, remember it for use later.
    371         if (key == deletedSentinel() && !foundDeletedElement) {
    372             foundDeletedElement = true;
    373             deletedElementIndex = i;
    374         }
    375         if (k == 0)
    376             k = 1 | doubleHash(h);
    377         i = (i + k) & sizeMask;
     393        } else if (entryIndex == deletedSentinelIndex) {
     394            // If we find a deleted-element sentinel, remember it for use later.
     395            if (!foundDeletedElement) {
     396                foundDeletedElement = true;
     397                deletedElementIndex = i;
     398            }
     399        }
     400
     401        if (k == 0) {
     402            k = 1 | doubleHash(rep->computedHash());
     403#if DUMP_PROPERTYMAP_STATS
     404            ++numCollisions;
     405#endif
     406        }
     407
     408        i += k;
     409
    378410#if DUMP_PROPERTYMAP_STATS
    379411        ++numRehashes;
    … …  
    381413    }
    382414
    383     // Use either the deleted element or the 0 at the end of the chain.
    384     if (foundDeletedElement) {
    385         i = deletedElementIndex;
    386         --m_u.table->sentinelCount;
    387     }
     415    // Figure out which entry to use.
     416    unsigned entryIndex;
     417    if (!m_u.table->deletedSentinelCount)
     418        entryIndex = m_u.table->keyCount + 2;
     419    else {
     420        if (foundDeletedElement) {
     421            i = deletedElementIndex;
     422            --m_u.table->deletedSentinelCount;
     423        }
     424        for (entryIndex = m_u.table->keyCount + m_u.table->deletedSentinelCount + 2;
     425                m_u.table->entries()[entryIndex - 1].key; --entryIndex)
     426            ;
     427    }
     428
     429
     430    // Create a new hash table entry.
     431    m_u.table->entryIndicies[i & m_u.table->sizeMask] = entryIndex;
    388432
    389433    // Create a new hash table entry.
    390434    rep->ref();
    391     entries[i].key = rep;
    392     entries[i].value = value;
    393     entries[i].attributes = static_cast<short>(attributes);
    394     entries[i].index = ++m_u.table->lastIndexUsed;
     435    m_u.table->entries()[entryIndex - 1].key = rep;
     436    m_u.table->entries()[entryIndex - 1].value = value;
     437    m_u.table->entries()[entryIndex - 1].attributes = attributes;
     438    m_u.table->entries()[entryIndex - 1].index = ++m_u.table->lastIndexUsed;
    395439    ++m_u.table->keyCount;
    396440
    … …  
    398442}
    399443
    400 void PropertyMap::insert(UString::Rep *key, JSValue *value, int attributes, int index)
     444void PropertyMap::insert(const Entry& entry)
    401445{
    402446    ASSERT(m_u.table);
    403447
    404     unsigned h = key->computedHash();
    405     int sizeMask = m_u.table->sizeMask;
    406     Entry *entries = m_u.table->entries;
    407     int i = h & sizeMask;
    408     int k = 0;
     448    unsigned i = entry.key->computedHash();
     449    unsigned k = 0;
     450
    409451#if DUMP_PROPERTYMAP_STATS
    410452    ++numProbes;
    411     numCollisions += entries[i].key && entries[i].key != key;
    412 #endif
    413     while (entries[i].key) {
    414         ASSERT(entries[i].key != deletedSentinel());
    415         if (k == 0)
    416             k = 1 | doubleHash(h);
    417         i = (i + k) & sizeMask;
     453#endif
     454
     455    while (1) {
     456        unsigned entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
     457        if (entryIndex == emptyEntryIndex)
     458            break;
     459
     460        if (k == 0) {
     461            k = 1 | doubleHash(entry.key->computedHash());
     462#if DUMP_PROPERTYMAP_STATS
     463            ++numCollisions;
     464#endif
     465        }
     466
     467        i += k;
     468
    418469#if DUMP_PROPERTYMAP_STATS
    419470        ++numRehashes;
    420471#endif
    421472    }
    422    
    423     entries[i].key = key;
    424     entries[i].value = value;
    425     entries[i].attributes = static_cast<short>(attributes);
    426     entries[i].index = index;
     473
     474    unsigned entryIndex = m_u.table->keyCount + 2;
     475    m_u.table->entryIndicies[i & m_u.table->sizeMask] = entryIndex;
     476    m_u.table->entries()[entryIndex - 1] = entry;
     477    ++m_u.table->keyCount;
    427478}
    428479
    … …  
    445496void PropertyMap::createTable()
    446497{
    447     const int newTableSize = 16;
     498    const unsigned newTableSize = 16;
    448499
    449500    ASSERT(!m_usingTable);
    … …  
    455506#endif
    456507
    457     m_u.table = (Table *)fastCalloc(1, sizeof(Table) + (newTableSize - 1) * sizeof(Entry));
     508    m_u.table = static_cast<Table*>(fastCalloc(1, Table::allocationSize(newTableSize)));
    458509    m_u.table->size = newTableSize;
    459510    m_u.table->sizeMask = newTableSize - 1;
    … …  
    461512
    462513#if USE_SINGLE_ENTRY
    463     UString::Rep* key = m_singleEntryKey;
    464     if (key) {
    465         insert(key, oldSingleEntryValue, m_singleEntryAttributes, 0);
     514    if (m_singleEntryKey) {
     515        insert(Entry(m_singleEntryKey, oldSingleEntryValue, m_singleEntryAttributes));
    466516        m_singleEntryKey = 0;
    467         m_u.table->keyCount = 1;
    468517    }
    469518#endif
    … …  
    472521}
    473522
    474 void PropertyMap::rehash(int newTableSize)
     523void PropertyMap::rehash(unsigned newTableSize)
    475524{
    476525    ASSERT(!m_singleEntryKey);
    … …  
    481530
    482531    Table* oldTable = m_u.table;
    483     int oldTableSize = oldTable->size;
    484     int oldTableKeyCount = oldTable->keyCount;
    485    
    486     m_u.table = (Table *)fastCalloc(1, sizeof(Table) + (newTableSize - 1) * sizeof(Entry));
     532   
     533    m_u.table = static_cast<Table*>(fastCalloc(1, Table::allocationSize(newTableSize)));
    487534    m_u.table->size = newTableSize;
    488535    m_u.table->sizeMask = newTableSize - 1;
    489     m_u.table->keyCount = oldTableKeyCount;
    490    
    491     int lastIndexUsed = 0;
    492     for (int i = 0; i != oldTableSize; ++i) {
    493         Entry &entry = oldTable->entries[i];
    494         UString::Rep *key = entry.key;
    495         if (isValid(key)) {
    496             int index = entry.index;
    497             lastIndexUsed = max(index, lastIndexUsed);
    498             insert(key, entry.value, entry.attributes, index);
     536
     537    unsigned lastIndexUsed = 0;
     538    unsigned entryCount = oldTable->keyCount + oldTable->deletedSentinelCount;
     539    for (unsigned i = 1; i <= entryCount; ++i) {
     540        if (oldTable->entries()[i].key) {
     541            lastIndexUsed = max(oldTable->entries()[i].index, lastIndexUsed);
     542            insert(oldTable->entries()[i]);
    499543        }
    500544    }
    … …  
    506550}
    507551
    508 void PropertyMap::remove(const Identifier &name)
     552void PropertyMap::remove(const Identifier& name)
    509553{
    510554    ASSERT(!name.isNull());
    … …  
    512556    checkConsistency();
    513557
    514     UString::Rep *rep = name._ustring.rep();
    515 
    516     UString::Rep *key;
    517 
    518     if (!m_usingTable) {
    519 #if USE_SINGLE_ENTRY
    520         key = m_singleEntryKey;
    521         if (rep == key) {
    522             key->deref();
     558    UString::Rep* rep = name._ustring.rep();
     559
     560    if (!m_usingTable) {
     561#if USE_SINGLE_ENTRY
     562        if (rep == m_singleEntryKey) {
     563            m_singleEntryKey->deref();
    523564            m_singleEntryKey = 0;
    524565            checkConsistency();
    … …  
    528569    }
    529570
    530     // Find the thing to remove.
    531     unsigned h = rep->computedHash();
    532     int sizeMask = m_u.table->sizeMask;
    533     Entry *entries = m_u.table->entries;
    534     int i = h & sizeMask;
    535     int k = 0;
    536571#if DUMP_PROPERTYMAP_STATS
    537572    ++numProbes;
    538573    ++numRemoves;
    539     numCollisions += entries[i].key && entries[i].key != rep;
    540 #endif
    541     while ((key = entries[i].key)) {
     574#endif
     575
     576    // Find the thing to remove.
     577    unsigned i = rep->computedHash();
     578    unsigned k = 0;
     579    unsigned entryIndex;
     580    UString::Rep* key = 0;
     581    while (1) {
     582        entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
     583        if (entryIndex == emptyEntryIndex)
     584            return;
     585
     586        key = m_u.table->entries()[entryIndex - 1].key;
    542587        if (rep == key)
    543588            break;
    544         if (k == 0)
    545             k = 1 | doubleHash(h);
    546         i = (i + k) & sizeMask;
     589
     590        if (k == 0) {
     591            k = 1 | doubleHash(rep->computedHash());
     592#if DUMP_PROPERTYMAP_STATS
     593            ++numCollisions;
     594#endif
     595        }
     596
     597        i += k;
     598
    547599#if DUMP_PROPERTYMAP_STATS
    548600        ++numRehashes;
    549601#endif
    550602    }
    551     if (!key)
    552         return;
    553    
    554     // Replace this one element with the deleted sentinel. Also set value to 0 and attributes to DontEnum
    555     // to help callers that iterate all keys not have to check for the sentinel.
     603
     604    // Replace this one element with the deleted sentinel. Also clear out
     605    // the entry so we can iterate all the entries as needed.
     606    m_u.table->entryIndicies[i & m_u.table->sizeMask] = deletedSentinelIndex;
    556607    key->deref();
    557     key = deletedSentinel();
    558     entries[i].key = key;
    559     entries[i].value = 0;
    560     entries[i].attributes = DontEnum;
     608    m_u.table->entries()[entryIndex - 1].key = 0;
     609    m_u.table->entries()[entryIndex - 1].value = jsUndefined();
     610    m_u.table->entries()[entryIndex - 1].attributes = 0;
    561611    ASSERT(m_u.table->keyCount >= 1);
    562612    --m_u.table->keyCount;
    563     ++m_u.table->sentinelCount;
    564    
    565     if (m_u.table->sentinelCount * 4 >= m_u.table->size)
     613    ++m_u.table->deletedSentinelCount;
     614
     615    if (m_u.table->deletedSentinelCount * 4 >= m_u.table->size)
    566616        rehash();
    567617
    … …  
    582632    }
    583633
    584     int minimumKeysToProcess = m_u.table->keyCount;
    585     Entry *entries = m_u.table->entries;
    586     for (int i = 0; i < minimumKeysToProcess; i++) {
    587         JSValue *v = entries[i].value;
    588         if (v) {
    589             if (!v->marked())
    590                 v->mark();
    591         } else {
    592             ++minimumKeysToProcess;
    593         }
    594     }
    595 }
    596 
    597 static int comparePropertyMapEntryIndices(const void *a, const void *b)
    598 {
    599     int ia = static_cast<PropertyMapHashTableEntry * const *>(a)[0]->index;
    600     int ib = static_cast<PropertyMapHashTableEntry * const *>(b)[0]->index;
     634    unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
     635    for (unsigned i = 1; i <= entryCount; i++) {
     636        JSValue* v = m_u.table->entries()[i].value;
     637        if (!v->marked())
     638            v->mark();
     639    }
     640}
     641
     642static int comparePropertyMapEntryIndices(const void* a, const void* b)
     643{
     644    unsigned ia = static_cast<PropertyMapEntry* const*>(a)[0]->index;
     645    unsigned ib = static_cast<PropertyMapEntry* const*>(b)[0]->index;
    601646    if (ia < ib)
    602647        return -1;
    … …  
    616661    }
    617662
    618     for (int i = 0; i != m_u.table->size; ++i) {
    619         if (m_u.table->entries[i].attributes & GetterSetter)
     663    unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
     664    for (unsigned i = 1; i <= entryCount; i++) {
     665        if (m_u.table->entries()[i].attributes & GetterSetter)
    620666            return true;
    621667    }
    622    
     668
    623669    return false;
    624670}
    … …  
    640686    // Get pointers to the enumerable entries in the buffer.
    641687    Entry** p = sortedEnumerables.data();
    642     int size = m_u.table->size;
    643     Entry* entries = m_u.table->entries;
    644     for (int i = 0; i != size; ++i) {
    645         Entry* e = &entries[i];
    646         if (e->key && !(e->attributes & DontEnum))
    647             *p++ = e;
     688    unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
     689    for (unsigned i = 1; i <= entryCount; i++) {
     690        if (m_u.table->entries()[i].key && !(m_u.table->entries()[i].attributes & DontEnum))
     691            *p++ = &m_u.table->entries()[i];
    648692    }
    649693
    … …  
    658702void PropertyMap::save(SavedProperties &p) const
    659703{
    660     int count = 0;
     704    unsigned count = 0;
    661705
    662706    if (!m_usingTable) {
    … …  
    666710#endif
    667711    } else {
    668         int size = m_u.table->size;
    669         Entry *entries = m_u.table->entries;
    670         for (int i = 0; i != size; ++i)
    671             if (isValid(entries[i].key) && !(entries[i].attributes & (ReadOnly | Function)))
     712        unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
     713        for (unsigned i = 1; i <= entryCount; ++i)
     714            if (m_u.table->entries()[i].key && !(m_u.table->entries()[i].attributes & (ReadOnly | Function)))
    672715                ++count;
    673716    }
    674717
    675     p._properties.clear();
    676     p._count = count;
     718    p.m_properties.clear();
     719    p.m_count = count;
    677720
    678721    if (count == 0)
    679722        return;
    680723   
    681     p._properties.set(new SavedProperty [count]);
    682    
    683     SavedProperty *prop = p._properties.get();
     724    p.m_properties.set(new SavedProperty [count]);
     725   
     726    SavedProperty* prop = p.m_properties.get();
    684727   
    685728    if (!m_usingTable) {
    … …  
    701744        // Get pointers to the entries in the buffer.
    702745        Entry** p = sortedEntries.data();
    703         int size = m_u.table->size;
    704         Entry* entries = m_u.table->entries;
    705         for (int i = 0; i != size; ++i) {
    706             Entry *e = &entries[i];
    707             if (isValid(e->key) && !(e->attributes & (ReadOnly | Function)))
    708                 *p++ = e;
    709         }
    710         ASSERT(p - sortedEntries.data() == count);
     746        unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
     747        for (unsigned i = 1; i <= entryCount; ++i) {
     748            if (m_u.table->entries()[i].key && !(m_u.table->entries()[i].attributes & (ReadOnly | Function)))
     749                *p++ = &m_u.table->entries()[i];
     750        }
     751        ASSERT(p == sortedEntries.data() + count);
    711752
    712753        // Sort the entries by index.
    … …  
    725766void PropertyMap::restore(const SavedProperties &p)
    726767{
    727     for (int i = 0; i != p._count; ++i)
    728         put(p._properties[i].key, p._properties[i].value, p._properties[i].attributes);
    729 }
    730 
    731 #if DO_CONSISTENCY_CHECK
     768    for (unsigned i = 0; i != p.m_count; ++i)
     769        put(p.m_properties[i].key, p.m_properties[i].value, p.m_properties[i].attributes);
     770}
     771
     772#if DO_PROPERTYMAP_CONSTENCY_CHECK
    732773
    733774void PropertyMap::checkConsistency()
    … …  
    736777        return;
    737778
    738     int count = 0;
    739     int sentinelCount = 0;
    740     for (int j = 0; j != m_u.table->size; ++j) {
    741         UString::Rep *rep = m_u.table->entries[j].key;
    742         if (!rep)
    743             continue;
    744         if (rep == deletedSentinel()) {
    745             ++sentinelCount;
    746             continue;
    747         }
    748         unsigned h = rep->computedHash();
    749         int i = h & m_u.table->sizeMask;
    750         int k = 0;
    751         while (UString::Rep *key = m_u.table->entries[i].key) {
    752             if (rep == key)
    753                 break;
    754             if (k == 0)
    755                 k = 1 | doubleHash(h);
    756             i = (i + k) & m_u.table->sizeMask;
    757         }
    758         ASSERT(i == j);
    759         ++count;
    760     }
    761     ASSERT(count == m_u.table->keyCount);
    762     ASSERT(sentinelCount == m_u.table->sentinelCount);
    763779    ASSERT(m_u.table->size >= 16);
    764780    ASSERT(m_u.table->sizeMask);
    765781    ASSERT(m_u.table->size == m_u.table->sizeMask + 1);
    766 }
    767 
    768 #endif // DO_CONSISTENCY_CHECK
     782    ASSERT(!(m_u.table->size & m_u.table->sizeMask));
     783
     784    ASSERT(m_u.table->keyCount <= m_u.table->size / 2);
     785    ASSERT(m_u.table->deletedSentinelCount <= m_u.table->size / 4);
     786
     787    ASSERT(m_u.table->keyCount + m_u.table->deletedSentinelCount <= m_u.table->size / 2);
     788
     789    unsigned indexCount = 0;
     790    unsigned deletedIndexCount = 0;
     791    for (unsigned a = 0; a != m_u.table->size; ++a) {
     792        unsigned entryIndex = m_u.table->entryIndicies[a];
     793        if (entryIndex == emptyEntryIndex)
     794            continue;
     795        if (entryIndex == deletedSentinelIndex) {
     796            ++deletedIndexCount;
     797            continue;
     798        }
     799        ++indexCount;
     800
     801        for (unsigned b = a + 1; b != m_u.table->size; ++b)
     802            ASSERT(m_u.table->entryIndicies[b] != entryIndex);
     803
     804    }
     805    ASSERT(indexCount == m_u.table->keyCount);
     806    ASSERT(deletedIndexCount == m_u.table->deletedSentinelCount);
     807
     808    ASSERT(m_u.table->entries()[0].key == 0);
     809
     810    unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
     811    unsigned nonEmptyEntryCount = 0;
     812    for (unsigned c = 1; c <= entryCount; ++c) {
     813        UString::Rep* rep = m_u.table->entries()[c].key;
     814        if (!rep) {
     815            ASSERT(m_u.table->entries()[c].value->isUndefined());
     816            continue;
     817        }
     818        ++nonEmptyEntryCount;
     819        unsigned i = rep->computedHash();
     820        unsigned k = 0;
     821        unsigned entryIndex;
     822        while (1) {
     823            entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
     824            ASSERT(entryIndex != emptyEntryIndex);
     825            if (rep == m_u.table->entries()[entryIndex - 1].key)
     826                break;
     827            if (k == 0)
     828                k = 1 | doubleHash(rep->computedHash());
     829            i += k;
     830        }
     831        ASSERT(entryIndex == c + 1);
     832    }
     833
     834    ASSERT(nonEmptyEntryCount == m_u.table->keyCount);
     835}
     836
     837#endif // DO_PROPERTYMAP_CONSTENCY_CHECK
    769838
    770839} // namespace KJS

  • trunk/JavaScriptCore/kjs/property_map.h

    r26958 r27387  
    11// -*- mode: c++; c-basic-offset: 4 -*-
    22/*
    3  *  This file is part of the KDE libraries
    4  *  Copyright (C) 2004, 2005, 2006 Apple Computer, Inc.
     3 *  Copyright (C) 2004, 2005, 2006, 2007 Apple Inc. All rights reserved.
    54 *
    65 *  This library is free software; you can redistribute it and/or
    … …  
    2928namespace KJS {
    3029
    31     class PropertyNameArray;
    3230    class JSObject;
    3331    class JSValue;
     32    class PropertyNameArray;
    3433   
    35     class SavedProperty;
     34    struct PropertyMapEntry;
     35    struct PropertyMapHashTable;
     36    struct SavedProperty;
    3637   
    37     struct PropertyMapHashTable;
    38    
    39 /**
    40 * Saved Properties
    41 */
    4238    class SavedProperties {
    43     friend class PropertyMap;
     39        friend class PropertyMap;
    4440    public:
    4541        SavedProperties();
    … …  
    4743       
    4844    private:
    49         int _count;
    50         OwnArrayPtr<SavedProperty> _properties;
    51     };
    52    
    53 /**
    54 * A hashtable entry for the @ref PropertyMap.
    55 */
    56     struct PropertyMapHashTableEntry
    57     {
    58         PropertyMapHashTableEntry() : key(0) { }
    59         UString::Rep *key;
    60         JSValue *value;
    61         int attributes;
    62         int index;
     45        unsigned m_count;
     46        OwnArrayPtr<SavedProperty> m_properties;
    6347    };
    6448
    65 /**
    66 * Javascript Property Map.
    67 */
    68     class PropertyMap {
     49    class PropertyMap : Noncopyable {
    6950    public:
    7051        PropertyMap();
    … …  
    7354        void clear();
    7455       
    75         void put(const Identifier &name, JSValue *value, int attributes, bool roCheck = false);
    76         void remove(const Identifier &name);
    77         JSValue *get(const Identifier &name) const;
    78         JSValue *get(const Identifier &name, unsigned &attributes) const;
    79         JSValue **getLocation(const Identifier &name);
     56        void put(const Identifier&, JSValue*, unsigned attributes, bool checkReadOnly = false);
     57        void remove(const Identifier&);
     58        JSValue* get(const Identifier&) const;
     59        JSValue* get(const Identifier&, unsigned& attributes) const;
     60        JSValue** getLocation(const Identifier& name);
    8061
    8162        void mark() const;
    8263        void getEnumerablePropertyNames(PropertyNameArray&) const;
    8364
    84         void save(SavedProperties &) const;
    85         void restore(const SavedProperties &p);
     65        void save(SavedProperties&) const;
     66        void restore(const SavedProperties&);
    8667
    8768        bool hasGetterSetterProperties() const { return m_getterSetterFlag; }
    … …  
    8970
    9071        bool containsGettersOrSetters() const;
     72
    9173    private:
    92         static bool keysMatch(const UString::Rep *, const UString::Rep *);
     74        typedef PropertyMapEntry Entry;
     75        typedef PropertyMapHashTable Table;
     76
     77        static bool keysMatch(const UString::Rep*, const UString::Rep*);
    9378        void expand();
    9479        void rehash();
    95         void rehash(int newTableSize);
     80        void rehash(unsigned newTableSize);
    9681        void createTable();
    9782       
    98         void insert(UString::Rep *, JSValue *value, int attributes, int index);
     83        void insert(const Entry&);
    9984       
    10085        void checkConsistency();
    10186       
    102         typedef PropertyMapHashTableEntry Entry;
    103         typedef PropertyMapHashTable Table;
    104 
    10587        UString::Rep* m_singleEntryKey;
    10688        union {
    107           JSValue* singleEntryValue;
    108           Table* table;
     89            JSValue* singleEntryValue;
     90            Table* table;
    10991        } m_u;
    11092
Note: See TracChangeset for help on using the changeset viewer.