Ignore:
Timestamp:
Dec 19, 2005, 2:38:07 AM (19 years ago)
Author:
mjs
Message:

Reviewed by Geoff and Adele

  • replaced custom Identifier hashtable with HashSet
  • kjs/identifier.cpp: (KXMLCore::): (KJS::identifierTable): (KJS::Identifier::equal): (KJS::hash): (KJS::equal): (KJS::convert): (KJS::Identifier::add): (KJS::Identifier::remove):
  • kjs/identifier.h:
  • kjs/internal.cpp: (KJS::InterpreterImp::initGlobalObject):
File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/JavaScriptCore/kjs/identifier.cpp

    r11472 r11661  
    3838
    3939#include <kxmlcore/FastMalloc.h>
     40#include <kxmlcore/HashSet.h>
    4041#include <string.h> // for strlen
    4142#include <new> // for placement new
    4243
    43 #define DUMP_STATISTICS 0
     44namespace KXMLCore {
     45
     46    template<typename T> class DefaultHash;
     47
     48    template<> struct DefaultHash<KJS::UString::Rep *> {
     49        static unsigned hash(const KJS::UString::Rep *key) { return key->hash(); }
     50        static bool equal(const KJS::UString::Rep *a, const KJS::UString::Rep *b) { return KJS::Identifier::equal(a, b); }
     51    };
     52}
    4453
    4554namespace KJS {
    4655
    47 #if DUMP_STATISTICS
    48 
    49 static int numProbes;
    50 static int numCollisions;
    51 
    52 struct IdentifierStatisticsExitLogger { ~IdentifierStatisticsExitLogger(); };
    53 
    54 static IdentifierStatisticsExitLogger logger;
    55 
    56 IdentifierStatisticsExitLogger::~IdentifierStatisticsExitLogger()
    57 {
    58     printf("\nKJS::Identifier statistics\n\n");
    59     printf("%d probes\n", numProbes);
    60     printf("%d collisions (%.1f%%)\n", numCollisions, 100.0 * numCollisions / numProbes);
    61 }
    62 
    63 #endif
    64 
    65 const int _minTableSize = 64;
    66 
    67 UString::Rep **Identifier::_table;
    68 int Identifier::_tableSize;
    69 int Identifier::_tableSizeMask;
    70 int Identifier::_keyCount;
    71 
    72 bool Identifier::equal(UString::Rep *r, const char *s)
     56typedef HashSet<UString::Rep *> IdentifierTable;
     57static IdentifierTable *table;
     58
     59static inline IdentifierTable& identifierTable()
     60{
     61    if (!table)
     62        table = new IdentifierTable;
     63    return *table;
     64}
     65
     66
     67bool Identifier::equal(const UString::Rep *r, const char *s)
    7368{
    7469    int length = r->len;
    … …  
    8075}
    8176
    82 bool Identifier::equal(UString::Rep *r, const UChar *s, int length)
     77bool Identifier::equal(const UString::Rep *r, const UChar *s, int length)
    8378{
    8479    if (r->len != length)
    … …  
    9186}
    9287
    93 bool Identifier::equal(UString::Rep *r, UString::Rep *b)
     88bool Identifier::equal(const UString::Rep *r, const UString::Rep *b)
    9489{
    9590    int length = r->len;
    … …  
    10499}
    105100
     101inline unsigned hash(const char* const& c)
     102{
     103    return UString::Rep::computeHash(c);
     104}
     105
     106inline bool equal(UString::Rep* const& r, const char* const& s)
     107{
     108    return Identifier::equal(r, s);
     109}
     110
     111inline UString::Rep *convert(const char* const& c, unsigned hash)
     112{
     113    int length = strlen(c);
     114    UChar *d = static_cast<UChar *>(fastMalloc(sizeof(UChar) * length));
     115    for (int i = 0; i != length; i++)
     116        d[i] = c[i];
     117   
     118    UString::Rep *r = UString::Rep::create(d, length).release();
     119    r->isIdentifier = 1;
     120    r->rc = 0;
     121    r->_hash = hash;
     122
     123    return r;
     124}
     125
    106126UString::Rep *Identifier::add(const char *c)
    107127{
    … …  
    112132        return &UString::Rep::empty;
    113133   
    114     if (!_table)
    115         expand();
    116    
    117     unsigned hash = UString::Rep::computeHash(c);
    118    
    119     int i = hash & _tableSizeMask;
    120 #if DUMP_STATISTICS
    121     ++numProbes;
    122     numCollisions += _table[i] && !equal(_table[i], c);
    123 #endif
    124     while (UString::Rep *key = _table[i]) {
    125         if (equal(key, c))
    126             return key;
    127         i = (i + 1) & _tableSizeMask;
    128     }
    129    
    130     UChar *d = static_cast<UChar *>(fastMalloc(sizeof(UChar) * length));
    131     for (int j = 0; j != length; j++)
    132         d[j] = c[j];
    133    
    134     UString::Rep *r = UString::Rep::create(d, length).release();
     134    return *identifierTable().insert<const char *, hash, KJS::equal, convert>(c).first;
     135}
     136
     137struct UCharBuffer {
     138    const UChar *s;
     139    uint length;
     140};
     141
     142inline unsigned hash(const UCharBuffer& buf)
     143{
     144    return UString::Rep::computeHash(buf.s, buf.length);
     145}
     146
     147inline bool equal(UString::Rep* const& str, const UCharBuffer& buf)
     148{
     149    return Identifier::equal(str, buf.s, buf.length);
     150}
     151
     152inline UString::Rep *convert(const UCharBuffer& buf, unsigned hash)
     153{
     154    UChar *d = static_cast<UChar *>(fastMalloc(sizeof(UChar) * buf.length));
     155    for (unsigned i = 0; i != buf.length; i++)
     156        d[i] = buf.s[i];
     157
     158    UString::Rep *r = UString::Rep::create(d, buf.length).release();
    135159    r->isIdentifier = 1;
    136160    r->rc = 0;
    137161    r->_hash = hash;
    138    
    139     _table[i] = r;
    140     ++_keyCount;
    141    
    142     if (_keyCount * 2 >= _tableSize)
    143         expand();
    144    
    145     return r;
     162
     163    return r;
    146164}
    147165
    … …  
    151169        return &UString::Rep::empty;
    152170   
    153     if (!_table)
    154         expand();
    155    
    156     unsigned hash = UString::Rep::computeHash(s, length);
    157    
    158     int i = hash & _tableSizeMask;
    159 #if DUMP_STATISTICS
    160     ++numProbes;
    161     numCollisions += _table[i] && !equal(_table[i], s, length);
    162 #endif
    163     while (UString::Rep *key = _table[i]) {
    164         if (equal(key, s, length))
    165             return key;
    166         i = (i + 1) & _tableSizeMask;
    167     }
    168    
    169     UChar *d = static_cast<UChar *>(fastMalloc(sizeof(UChar) * length));
    170     for (int j = 0; j != length; j++)
    171         d[j] = s[j];
    172    
    173     UString::Rep *r = UString::Rep::create(d, length).release();
    174     r->isIdentifier = 1;
    175     r->rc = 0;
    176     r->_hash = hash;
    177    
    178     _table[i] = r;
    179     ++_keyCount;
    180    
    181     if (_keyCount * 2 >= _tableSize)
    182         expand();
    183    
    184     return r;
     171    UCharBuffer buf = {s, length};
     172    return *identifierTable().insert<UCharBuffer, hash, KJS::equal, convert>(buf).first;
    185173}
    186174
    … …  
    189177    if (r->isIdentifier)
    190178        return r;
     179
    191180    if (r->len == 0)
    192181        return &UString::Rep::empty;
    193    
    194     if (!_table)
    195         expand();
    196    
    197     unsigned hash = r->hash();
    198    
    199     int i = hash & _tableSizeMask;
    200 #if DUMP_STATISTICS
    201     ++numProbes;
    202     numCollisions += _table[i] && !equal(_table[i], r);
    203 #endif
    204     while (UString::Rep *key = _table[i]) {
    205         if (equal(key, r))
    206             return key;
    207         i = (i + 1) & _tableSizeMask;
    208     }
    209    
    210     r->isIdentifier = 1;
    211    
    212     _table[i] = r;
    213     ++_keyCount;
    214    
    215     if (_keyCount * 2 >= _tableSize)
    216         expand();
    217    
    218     return r;
    219 }
    220 
    221 inline void Identifier::insert(UString::Rep *key)
    222 {
    223     unsigned hash = key->hash();
    224    
    225     int i = hash & _tableSizeMask;
    226 #if DUMP_STATISTICS
    227     ++numProbes;
    228     numCollisions += _table[i] != 0;
    229 #endif
    230     while (_table[i])
    231         i = (i + 1) & _tableSizeMask;
    232    
    233     _table[i] = key;
     182
     183    UString::Rep *result = *identifierTable().insert(r).first;
     184    if (result == r)
     185        r->isIdentifier = true;
     186    return result;
    234187}
    235188
    236189void Identifier::remove(UString::Rep *r)
    237190{
    238     unsigned hash = r->hash();
    239    
    240     UString::Rep *key;
    241    
    242     int i = hash & _tableSizeMask;
    243 #if DUMP_STATISTICS
    244     ++numProbes;
    245     numCollisions += _table[i] && equal(_table[i], r);
    246 #endif
    247     while ((key = _table[i])) {
    248         if (equal(key, r))
    249             break;
    250         i = (i + 1) & _tableSizeMask;
    251     }
    252     if (!key)
    253         return;
    254    
    255     _table[i] = 0;
    256     --_keyCount;
    257    
    258     if (_keyCount * 6 < _tableSize && _tableSize > _minTableSize) {
    259         shrink();
    260         return;
    261     }
    262    
    263     // Reinsert all the items to the right in the same cluster.
    264     while (1) {
    265         i = (i + 1) & _tableSizeMask;
    266         key = _table[i];
    267         if (!key)
    268             break;
    269         _table[i] = 0;
    270         insert(key);
    271     }
    272 }
    273 
    274 void Identifier::expand()
    275 {
    276     rehash(_tableSize == 0 ? _minTableSize : _tableSize * 2);
    277 }
    278 
    279 void Identifier::shrink()
    280 {
    281     rehash(_tableSize / 2);
    282 }
    283 
    284 void Identifier::rehash(int newTableSize)
    285 {
    286     int oldTableSize = _tableSize;
    287     UString::Rep **oldTable = _table;
    288 
    289     _tableSize = newTableSize;
    290     _tableSizeMask = newTableSize - 1;
    291     _table = (UString::Rep **)fastCalloc(newTableSize, sizeof(UString::Rep *));
    292 
    293     for (int i = 0; i != oldTableSize; ++i)
    294         if (UString::Rep *key = oldTable[i])
    295             insert(key);
    296 
    297     fastFree(oldTable);
     191    identifierTable().remove(r);
    298192}
    299193
Note: See TracChangeset for help on using the changeset viewer.