Changeset 2749 in webkit for trunk/JavaScriptCore


Ignore:
Timestamp:
Nov 18, 2002, 10:53:35 PM (23 years ago)
Author:
darin
Message:
  • property and string improvements giving a 7% or so improvement in JavaScript iBench
  • kjs/property_map.h: Rewrite to use a hash table.
  • kjs/property_map.cpp: Ditto.
  • kjs/string_object.h:
  • kjs/string_object.cpp: (StringInstanceImp::StringInstanceImp): Construct a string with the right value instead of putting the string in later. (StringInstanceImp::get): Get the length from the string, not a separate property. (StringInstanceImp::put): Ignore attempts to set length, since we don't put it in the property map. (StringInstanceImp::hasProperty): Return true for length. (StringInstanceImp::deleteProperty): Return false for length. (StringObjectImp::construct): Call new StringInstanceImp constructor. Don't try to set a length property.
  • kjs/ustring.h: Make the rep deref know how to deallocate the rep.
  • kjs/ustring.cpp: (UString::release): Move the real work to the rep's deref, since the hash table now uses the rep directly.
  • kjs/object.h: Remove unused field.
Location:
trunk/JavaScriptCore
Files:
10 edited

Legend:

Unmodified
Added
Removed

  • trunk/JavaScriptCore/ChangeLog

    r2748 r2749  
     12002-11-18  Darin Adler  <[email protected]>
     2
     3        - property and string improvements giving a 7% or so improvement in JavaScript iBench
     4
     5        * kjs/property_map.h: Rewrite to use a hash table.
     6        * kjs/property_map.cpp: Ditto.
     7
     8        * kjs/string_object.h:
     9        * kjs/string_object.cpp:
     10        (StringInstanceImp::StringInstanceImp): Construct a string with the right value
     11        instead of putting the string in later.
     12        (StringInstanceImp::get): Get the length from the string, not a separate property.
     13        (StringInstanceImp::put): Ignore attempts to set length, since we don't put it in
     14        the property map.
     15        (StringInstanceImp::hasProperty): Return true for length.
     16        (StringInstanceImp::deleteProperty): Return false for length.
     17        (StringObjectImp::construct): Call new StringInstanceImp constructor. Don't try
     18        to set a length property.
     19
     20        * kjs/ustring.h: Make the rep deref know how to deallocate the rep.
     21        * kjs/ustring.cpp:
     22        (UString::release): Move the real work to the rep's deref, since the hash table
     23        now uses the rep directly.
     24
     25        * kjs/object.h: Remove unused field.
     26
    1272002-11-18  Maciej Stachowiak  <[email protected]>
    228

  • trunk/JavaScriptCore/ChangeLog-2002-12-03

    r2748 r2749  
     12002-11-18  Darin Adler  <[email protected]>
     2
     3        - property and string improvements giving a 7% or so improvement in JavaScript iBench
     4
     5        * kjs/property_map.h: Rewrite to use a hash table.
     6        * kjs/property_map.cpp: Ditto.
     7
     8        * kjs/string_object.h:
     9        * kjs/string_object.cpp:
     10        (StringInstanceImp::StringInstanceImp): Construct a string with the right value
     11        instead of putting the string in later.
     12        (StringInstanceImp::get): Get the length from the string, not a separate property.
     13        (StringInstanceImp::put): Ignore attempts to set length, since we don't put it in
     14        the property map.
     15        (StringInstanceImp::hasProperty): Return true for length.
     16        (StringInstanceImp::deleteProperty): Return false for length.
     17        (StringObjectImp::construct): Call new StringInstanceImp constructor. Don't try
     18        to set a length property.
     19
     20        * kjs/ustring.h: Make the rep deref know how to deallocate the rep.
     21        * kjs/ustring.cpp:
     22        (UString::release): Move the real work to the rep's deref, since the hash table
     23        now uses the rep directly.
     24
     25        * kjs/object.h: Remove unused field.
     26
    1272002-11-18  Maciej Stachowiak  <[email protected]>
    228

  • trunk/JavaScriptCore/ChangeLog-2003-10-25

    r2748 r2749  
     12002-11-18  Darin Adler  <[email protected]>
     2
     3        - property and string improvements giving a 7% or so improvement in JavaScript iBench
     4
     5        * kjs/property_map.h: Rewrite to use a hash table.
     6        * kjs/property_map.cpp: Ditto.
     7
     8        * kjs/string_object.h:
     9        * kjs/string_object.cpp:
     10        (StringInstanceImp::StringInstanceImp): Construct a string with the right value
     11        instead of putting the string in later.
     12        (StringInstanceImp::get): Get the length from the string, not a separate property.
     13        (StringInstanceImp::put): Ignore attempts to set length, since we don't put it in
     14        the property map.
     15        (StringInstanceImp::hasProperty): Return true for length.
     16        (StringInstanceImp::deleteProperty): Return false for length.
     17        (StringObjectImp::construct): Call new StringInstanceImp constructor. Don't try
     18        to set a length property.
     19
     20        * kjs/ustring.h: Make the rep deref know how to deallocate the rep.
     21        * kjs/ustring.cpp:
     22        (UString::release): Move the real work to the rep's deref, since the hash table
     23        now uses the rep directly.
     24
     25        * kjs/object.h: Remove unused field.
     26
    1272002-11-18  Maciej Stachowiak  <[email protected]>
    228

  • trunk/JavaScriptCore/kjs/object.h

    r2741 r2749  
    4444namespace KJS {
    4545
    46   class ObjectImpPrivate;
    4746  class PropertyMap;
    4847  class HashTable;
    … …  
    584583  private:
    585584    const HashEntry* findPropertyHashEntry( const UString& propertyName ) const;
    586     ObjectImpPrivate *_od;
    587585    PropertyMap *_prop;
    588586    ValueImp *_proto;

  • trunk/JavaScriptCore/kjs/property_map.cpp

    r2740 r2749  
    22/*
    33 *  This file is part of the KDE libraries
    4  *  Copyright (C) 2001 Peter Kelly (pmk@post.com)
     4 *  Copyright (C) 2002 Darin Adler (darin@apple.com)
    55 *
    66 *  This library is free software; you can redistribute it and/or
    … …  
    2121 */
    2222
    23 
    2423#include "property_map.h"
    2524
    … …  
    2726#include "reference_list.h"
    2827
    29 #include <string.h>
    30 #include <assert.h>
    31 #include <stdio.h>
    32 
    3328namespace KJS {
    3429
    35 // ------------------------------ PropertyMapNode ------------------------------
    36 
    37   class PropertyMapNode {
    38   public:
    39     PropertyMapNode(const UString &n, ValueImp *v, int att, PropertyMapNode *p)
    40       : name(n), value(v), attr(att), left(0), right(0), parent(p), height(1) {}
    41 
    42     UString name;
    43     ValueImp *value;
    44     int attr;
    45 
    46     void setLeft(PropertyMapNode *newLeft);
    47     void setRight(PropertyMapNode *newRight);
    48     PropertyMapNode *findMax();
    49     PropertyMapNode *findMin();
    50 
    51     PropertyMapNode *next();
    52 
    53     PropertyMapNode *left;
    54     PropertyMapNode *right;
    55     PropertyMapNode *parent;
    56     int height;
    57 
    58   private:
    59     void setParent(PropertyMapNode *newParent);
    60   };
    61 
    62 void PropertyMapNode::setLeft(PropertyMapNode *newLeft)
    63 {
    64   if (left)
    65     left->setParent(0);
    66   left = newLeft;
    67   if (left)
    68     left->setParent(this);
    69 }
    70 
    71 void PropertyMapNode::setRight(PropertyMapNode *newRight)
    72 {
    73   if (right)
    74     right->setParent(0);
    75   right = newRight;
    76   if (right)
    77     right->setParent(this);
    78 }
    79 
    80 void PropertyMapNode::setParent(PropertyMapNode *newParent)
    81 {
    82   if (parent) {
    83     //assert(this == parent->left || this == parent->right);
    84     if (this == parent->left)
    85       parent->left = 0;
    86     else
    87       parent->right = 0;
    88   }
    89   parent = newParent;
    90 }
    91 
    92 PropertyMapNode *PropertyMapNode::findMax()
    93 {
    94   PropertyMapNode *max = this;
    95   while (max->right)
    96     max = max->right;
    97   return max;
    98 }
    99 
    100 PropertyMapNode *PropertyMapNode::findMin()
    101 {
    102   PropertyMapNode *min = this;
    103   while (min->left)
    104     min = min->left;
    105   return min;
    106 }
    107 
    108 PropertyMapNode *PropertyMapNode::next()
    109 {
    110   // find the next node, going from lowest name to highest name
    111 
    112   // We have a right node. Starting from our right node, keep going left as far as we can
    113   if (right) {
    114     PropertyMapNode *n = right;
    115     while (n->left)
    116       n = n->left;
    117     return n;
    118   }
    119 
    120   // We have no right node. Keep going up to the left, until we find a node that has a parent
    121   // to the right. If we find one, go to it. Otherwise, we have reached the end.
    122   PropertyMapNode *n = this;
    123   while (n->parent && n->parent->right == n) {
    124     // parent is to our left
    125     n = n->parent;
    126   }
    127   if (n->parent && n->parent->left == n) {
    128     // parent is to our right
    129     return n->parent;
    130   }
    131 
    132   return 0;
    133 }
    134 
    135 // ------------------------------ PropertyMap ----------------------------------
    136 
    137 int KJS::uscompare(const UString &s1, const UString &s2)
    138 {
    139   int len1 = s1.size();
    140   int len2 = s2.size();
    141   if (len1 < len2)
    142     return -1;
    143   else if (len1 > len2)
    144     return 1;
    145   else
    146     return memcmp(s1.data(), s2.data(), len1*sizeof(UChar));
    147 }
    148 
    149 PropertyMap::PropertyMap()
    150 {
    151   root = 0;
     30// Algorithm concepts from Algorithms in C++, Sedgewick.
     31
     32PropertyMap::PropertyMap() : _tableSize(0), _table(0), _keyCount(0)
     33{
    15234}
    15335
    15436PropertyMap::~PropertyMap()
    15537{
    156   clear();
    157 }
    158 
    159 void PropertyMap::put(const UString &name, ValueImp *value, int attr)
    160 {
    161   // if not root; make the root the new node
    162   if (!root) {
    163     root = new PropertyMapNode(name, value, attr, 0);
    164     return;
    165   }
    166 
    167   // try to find the parent node
    168   PropertyMapNode *parent = root;
    169   int isLeft = false;
    170   while (true) {
    171     int cmp = uscompare(name, parent->name);
    172     if (cmp < 0) {
    173       // traverse to left node (if any)
    174       isLeft = true;
    175       if (!parent->left)
    176         break;
    177       else
    178         parent = parent->left;
    179     }
    180     else if (cmp > 0) {
    181       // traverse to right node (if any)
    182       isLeft = false;
    183       if (!parent->right)
    184         break;
    185       else
    186         parent = parent->right;
    187     }
    188     else {
    189       // a node with this name already exists; just replace the value
    190       parent->value = value;
    191       return;
    192     }
    193   }
    194 
    195   // we found the parent
    196   //assert(parent);
    197 
    198   if (isLeft) {
    199     //assert(!parent->left);
    200     parent->left = new PropertyMapNode(name, value, attr, parent);
    201   }
    202   else {
    203     //assert(!parent->right);
    204     parent->right = new PropertyMapNode(name, value, attr, parent);
    205   }
    206   updateHeight(parent);
    207 
    208 
    209   PropertyMapNode *node = parent;
    210   while (node) {
    211     PropertyMapNode *p = node->parent;
    212     balance(node); // may change node
    213     node = p;
    214   }
     38    //printf("key count is %d\n", _keyCount);
     39    UString::Rep *key = _singleEntry.key;
     40    if (key)
     41        key->deref();
     42    for (int i = 0; i < _tableSize; i++) {
     43        key = _table[i].key;
     44        if (key)
     45            key->deref();
     46    }
     47    free(_table);
     48}
     49
     50void PropertyMap::clear()
     51{
     52    UString::Rep *key = _singleEntry.key;
     53    if (key) {
     54        key->deref();
     55        _singleEntry.key = 0;
     56    }
     57    for (int i = 0; i < _tableSize; i++) {
     58        UString::Rep *key = _table[i].key;
     59        if (key) {
     60            key->deref();
     61            _table[i].key = 0;
     62        }
     63    }
     64    _keyCount = 0;
     65}
     66
     67int PropertyMap::hash(const UString::Rep *s) const
     68{
     69    int h = 0;
     70    int length = s->len;
     71    int prefixLength = length < 8 ? length : 8;
     72    for (int i = 0; i < prefixLength; i++)
     73        h = (127 * h + s->dat[i].unicode()) & _tableSizeHashMask;
     74    int suffixPosition = length < 16 ? 8 : length - 8;
     75    for (int i = suffixPosition; i < length; i++)
     76        h = (127 * h + s->dat[i].unicode()) & _tableSizeHashMask;
     77    return h;
     78}
     79
     80bool PropertyMap::keysMatch(const UString::Rep *a, const UString::Rep *b)
     81{
     82    if (a == b)
     83        return true;
     84   
     85    int len = a->len;
     86    if (len != b->len)
     87        return false;
     88   
     89    for (int i = 0; i != len; ++i)
     90        if (a->dat[i].unicode() != b->dat[i].unicode())
     91            return false;
     92   
     93    return true;
     94}
     95
     96ValueImp *PropertyMap::get(const UString &name, int &attributes) const
     97{
     98    if (!_table) {
     99        UString::Rep *key = _singleEntry.key;
     100        if (key && keysMatch(name.rep, key)) {
     101            attributes = _singleEntry.attributes;
     102            return _singleEntry.value;
     103        }
     104        return 0;
     105    }
     106   
     107    int i = hash(name.rep);
     108    while (UString::Rep *key = _table[i].key) {
     109        if (keysMatch(name.rep, key)) {
     110            attributes = _table[i].attributes;
     111            return _table[i].value;
     112        }
     113        i = (i + 1) % _tableSize;
     114    }
     115    return 0;
     116}
     117
     118ValueImp *PropertyMap::get(const UString &name) const
     119{
     120    if (!_table) {
     121        UString::Rep *key = _singleEntry.key;
     122        if (key && keysMatch(name.rep, key))
     123            return _singleEntry.value;
     124        return 0;
     125    }
     126   
     127    int i = hash(name.rep);
     128    while (UString::Rep *key = _table[i].key) {
     129        if (keysMatch(name.rep, key))
     130            return _table[i].value;
     131        i = (i + 1) % _tableSize;
     132    }
     133    return 0;
     134}
     135
     136void PropertyMap::put(const UString &name, ValueImp *value, int attributes)
     137{
     138    if (!_table) {
     139        UString::Rep *key = _singleEntry.key;
     140        if (key) {
     141            if (keysMatch(name.rep, key)) {
     142                _singleEntry.value = value;
     143                return;
     144            }
     145        } else {
     146            name.rep->ref();
     147            _singleEntry.key = name.rep;
     148            _singleEntry.value = value;
     149            _singleEntry.attributes = attributes;
     150            _keyCount = 1;
     151            return;
     152        }
     153    }
     154
     155    if (_keyCount >= _tableSize / 2)
     156        expand();
     157   
     158    int i = hash(name.rep);
     159    while (UString::Rep *key = _table[i].key) {
     160        if (keysMatch(name.rep, key)) {
     161            // Put a new value in an existing hash table entry.
     162            _table[i].value = value;
     163            // Attributes are intentionally not updated.
     164            return;
     165        }
     166        i = (i + 1) % _tableSize;
     167    }
     168   
     169    // Create a new hash table entry.
     170    name.rep->ref();
     171    _table[i].key = name.rep;
     172    _table[i].value = value;
     173    _table[i].attributes = attributes;
     174    ++_keyCount;
     175}
     176
     177inline void PropertyMap::insert(UString::Rep *key, ValueImp *value, int attributes)
     178{
     179    int i = hash(key);
     180    while (_table[i].key)
     181        i = (i + 1) % _tableSize;
     182   
     183    _table[i].key = key;
     184    _table[i].value = value;
     185    _table[i].attributes = attributes;
     186}
     187
     188void PropertyMap::expand()
     189{
     190    int oldTableSize = _tableSize;
     191    Entry *oldTable = _table;
     192
     193    _tableSize = oldTableSize ? oldTableSize * 2 : 16;
     194    _tableSizeHashMask = _tableSize - 1;
     195    _table = (Entry *)calloc(_tableSize, sizeof(Entry));
     196
     197    UString::Rep *key = _singleEntry.key;
     198    if (key) {
     199        insert(key, _singleEntry.value, _singleEntry.attributes);
     200        _singleEntry.key = 0;
     201    }
     202   
     203    for (int i = 0; i != oldTableSize; ++i) {
     204        key = oldTable[i].key;
     205        if (key)
     206            insert(key, oldTable[i].value, oldTable[i].attributes);
     207    }
     208
     209    free(oldTable);
    215210}
    216211
    217212void PropertyMap::remove(const UString &name)
    218213{
    219   PropertyMapNode *node = getNode(name);
    220   if (!node) // name not in tree
    221     return;
    222 
    223   PropertyMapNode *removed = remove(node);
    224   if (removed)
    225     delete node;
    226 }
    227 
    228 ValueImp *PropertyMap::get(const UString &name) const
    229 {
    230   const PropertyMapNode *n = getNode(name);
    231   return n ? n->value : 0;
    232 }
    233 
    234 ValueImp *PropertyMap::get(const UString &name, int &attributes) const
    235 {
    236   const PropertyMapNode *n = getNode(name);
    237   attributes = n ? n->attr : 0;
    238   return n ? n->value : 0;
    239 }
    240 
    241 void PropertyMap::clear()
    242 {
    243   clear(0);
    244 }
    245 
    246 void PropertyMap::mark()
    247 {
    248   PropertyMapNode *node = first();
    249   while (node) {
    250     if (!node->value->marked())
    251       node->value->mark();
    252     node = node->next();
    253   }
     214    UString::Rep *key;
     215
     216    if (!_table) {
     217        key = _singleEntry.key;
     218        if (key && keysMatch(name.rep, key)) {
     219            key->deref();
     220            _singleEntry.key = 0;
     221            _keyCount = 0;
     222        }
     223        return;
     224    }
     225
     226    // Find the thing to remove.
     227    int i = hash(name.rep);
     228    while ((key = _table[i].key)) {
     229        if (keysMatch(name.rep, key))
     230            break;
     231        i = (i + 1) % _tableSize;
     232    }
     233    if (!key)
     234        return;
     235   
     236    // Remove the one key.
     237    key->deref();
     238    _table[i].key = 0;
     239    --_keyCount;
     240   
     241    // Reinsert all the items to the right in the same cluster.
     242    while (1) {
     243        i = (i + 1) % _tableSize;
     244        key = _table[i].key;
     245        if (!key)
     246            break;
     247        _table[i].key = 0;
     248        insert(key, _table[i].value, _table[i].attributes);
     249    }
     250}
     251
     252void PropertyMap::mark() const
     253{
     254    if (_singleEntry.key) {
     255        ValueImp *v = _singleEntry.value;
     256        if (!v->marked())
     257            v->mark();
     258    }
     259    for (int i = 0; i != _tableSize; ++i) {
     260        if (_table[i].key) {
     261            ValueImp *v = _table[i].value;
     262            if (!v->marked())
     263                v->mark();
     264        }
     265    }
    254266}
    255267
    256268void PropertyMap::addEnumerablesToReferenceList(ReferenceList &list, const Object &base) const
    257269{
    258   PropertyMapNode *node = first();
    259   while (node) {
    260     if (!(node->attr & DontEnum))
    261       list.append(Reference(base, node->name));
    262     node = node->next();
    263   }
    264 }
    265 
    266 void PropertyMap::clear(PropertyMapNode *node)
    267 {
    268   if (node == 0)
    269     node = root;
    270   if (node == 0) // nothing to do
    271     return;
    272 
    273   if (node->left)
    274     clear(node->left);
    275   if (node->right)
    276     clear(node->right);
    277   if (node == root)
    278     root = 0;
    279   delete node;
    280 }
    281 
    282 void PropertyMap::dump(const PropertyMapNode *node, int indent) const
    283 {
    284   if (!node && indent > 0)
    285     return;
    286   if (!node)
    287     node = root;
    288   if (!node)
    289     return;
    290 
    291   assert(!node->right || node->right->parent == node);
    292   dump(node->right, indent+1);
    293   for (int i = 0; i < indent; i++) {
    294     printf("    ");
    295   }
    296   printf("[%d] %s\n", node->height, node->name.ascii());
    297   assert(!node->left || node->left->parent == node);
    298   dump(node->left, indent+1);
    299 }
    300 
    301 void PropertyMap::checkTree(const PropertyMapNode *node) const
    302 {
    303   if (!root)
    304     return;
    305   if (node == 0)
    306     node = root;
    307   if (node == root) {
    308     assert(!node->parent);
    309   }
    310   assert(!node->right || node->right->parent == node);
    311   assert(!node->left || node->left->parent == node);
    312   assert(node->left != node);
    313   assert(node->right != node);
    314   if (node->left && node->right)
    315     assert(node->left != node->right);
    316 
    317   PropertyMapNode *n = node->parent;
    318   while (n) {
    319     assert(n != node);
    320     n = n->parent;
    321   }
    322 
    323   if (node->right)
    324     checkTree(node->right);
    325   if (node->left)
    326     checkTree(node->left);
    327 }
    328 
    329 PropertyMapNode *PropertyMap::getNode(const UString &name) const
    330 {
    331   PropertyMapNode *node = root;
    332 
    333   while (true) {
    334     if (!node)
    335       return 0;
    336 
    337     int cmp = uscompare(name, node->name);
    338     if (cmp < 0)
    339       node = node->left;
    340     else if (cmp > 0)
    341       node = node->right;
    342     else
    343       return node;
    344   }
    345 }
    346 
    347 PropertyMapNode *PropertyMap::first() const
    348 {
    349   if (!root)
    350     return 0;
    351 
    352   PropertyMapNode *node = root;
    353   while (node->left)
    354     node = node->left;
    355   return node;
    356 }
    357 
    358 PropertyMapNode * PropertyMap::remove(PropertyMapNode *node)
    359 {
    360   PropertyMapNode *parent = node->parent;
    361   //assert(!parent || (node == parent->left || node == parent->right));
    362   bool isLeft = (parent && node == parent->left);
    363 
    364   PropertyMapNode *replace = 0;
    365   if (node->left && node->right) {
    366     PropertyMapNode *maxLeft = node->left->findMax();
    367     if (maxLeft == node->left) {
    368       maxLeft->setRight(node->right);
    369       replace = maxLeft;
    370     }
    371     else {
    372       remove(maxLeft);
    373 
    374       maxLeft->setLeft(node->left);
    375       maxLeft->setRight(node->right);
    376       replace = maxLeft;
    377     }
    378     // removing maxLeft could have re-balanced the tree, so recalculate
    379     // parent again
    380     parent = node->parent;
    381     //assert(!parent || (node == parent->left || node == parent->right));
    382     isLeft = (parent && node == parent->left);
    383   }
    384   else if (node->left) {
    385     replace = node->left;
    386   }
    387   else if (node->right) {
    388     replace = node->right;
    389   }
    390   else {
    391     replace = 0;
    392   }
    393 
    394   if (parent) {
    395     if (isLeft)
    396       parent->setLeft(replace);
    397     else
    398       parent->setRight(replace);
    399   }
    400   else {
    401     root = replace;
    402     if (replace)
    403       replace->parent = 0;
    404   }
    405 
    406   if (replace)
    407     updateHeight(replace); // will also update parent's height
    408   else if (parent)
    409     updateHeight(parent);
    410   else if (root)
    411     updateHeight(root);
    412 
    413 
    414   // balance the tree
    415   PropertyMapNode *bal = parent;
    416   while (bal) {
    417     PropertyMapNode *p = bal->parent;
    418     balance(bal); // may change bal
    419     bal = p;
    420   }
    421 
    422   return node;
    423 }
    424 
    425 void PropertyMap::balance(PropertyMapNode* node)
    426 {
    427   int lheight = node->left ? node->left->height : 0;
    428   int rheight = node->right ? node->right->height : 0;
    429 
    430   int bal = rheight-lheight;
    431 
    432   if (bal < -1) {
    433     //assert(node->left);
    434     int llheight = node->left->left ? node->left->left->height : 0;
    435     int lrheight = node->left->right ? node->left->right->height : 0;
    436     int lbal = lrheight - llheight;
    437 
    438     if (lbal < 0) {
    439       rotateLL(node); // LL rotation
    440     }
    441     else {
    442       // lbal >= 0
    443       rotateLR(node);
    444     }
    445   }
    446   else if (bal > 1) {
    447     int rlheight = node->right->left ? node->right->left->height : 0;
    448     int rrheight = node->right->right ? node->right->right->height : 0;
    449     int rbal = rrheight - rlheight;
    450     if (rbal < 0) {
    451       rotateRL(node);
    452     }
    453     else {
    454       // rbal >= 0
    455       rotateRR(node); // RR rotateion
    456     }
    457   }
    458 }
    459 
    460 void PropertyMap::updateHeight(PropertyMapNode* &node)
    461 {
    462   int lheight = node->left ? node->left->height : 0;
    463   int rheight = node->right ? node->right->height : 0;
    464   if (lheight > rheight)
    465     node->height = lheight+1;
    466   else
    467     node->height = rheight+1;
    468   //assert(node->parent != node);
    469   if (node->parent)
    470     updateHeight(node->parent);
    471 }
    472 
    473 void PropertyMap::rotateRR(PropertyMapNode* &node)
    474 {
    475   /*
    476     Perform a RR ("single left") rotation, e.g.
    477 
    478       a                b
    479      / \              / \
    480     X   b     -->    a   Z
    481        / \          / \
    482       Y   Z        X   Y
    483   */
    484 
    485   // Here, node is initially a, will be replaced with b
    486 
    487   PropertyMapNode *a = node;
    488   PropertyMapNode *b = node->right;
    489 
    490   PropertyMapNode *parent = a->parent;
    491   //assert(!parent || (a == parent->left || a == parent->right));
    492   bool isLeft = (parent && a == parent->left);
    493 
    494   // do the rotation
    495   a->setRight(b->left);
    496   b->setLeft(a);
    497 
    498   // now node is b
    499   node = b;
    500   if (parent) {
    501     if (isLeft)
    502       parent->setLeft(b);
    503     else
    504       parent->setRight(b);
    505   }
    506   else {
    507     // a was the root node
    508     root = b;
    509   }
    510 
    511   updateHeight(a);
    512   updateHeight(b);
    513 }
    514 
    515 
    516 void PropertyMap::rotateLL(PropertyMapNode* &node)
    517 {
    518   /*
    519     Perform a LL ("single right") rotation, e.g.
    520 
    521 
    522         a              b
    523        / \            / \
    524       b   Z   -->    X   a
    525      / \                / \
    526     X   Y              Y   Z
    527   */
    528 
    529   // Here, node is initially a, will be replaced with b
    530 
    531   PropertyMapNode *a = node;
    532   PropertyMapNode *b = node->left;
    533 
    534   PropertyMapNode *parent = a->parent;
    535   //assert(!parent || (a == parent->left || a == parent->right));
    536   bool isLeft = (parent && a == parent->left);
    537 
    538   // do the rotation
    539   a->setLeft(b->right);
    540   b->setRight(a);
    541 
    542   // now node is b
    543   node = b;
    544   if (parent) {
    545     if (isLeft)
    546       parent->setLeft(b);
    547     else
    548       parent->setRight(b);
    549   }
    550   else {
    551     // a was the root node
    552     root = b;
    553   }
    554 
    555   updateHeight(a);
    556   updateHeight(b);
    557 }
    558 
    559 void PropertyMap::rotateRL(PropertyMapNode* &node)
    560 {
    561   /*
    562     Perform a RL ("double left") rotation, e.g.
    563 
    564         a                   a                          b
    565       /   \      LL on c  /   \          RR on b     /   \
    566      W      c      -->   W      b          -->     a       c
    567            / \                 / \                / \     / \
    568           b   Z               X   c              W   X   Y   Z
    569          / \                     / \
    570         X   Y                   Y   Z
    571 
    572   */
    573 
    574   PropertyMapNode *a = node;
    575   PropertyMapNode *c = node->right;
    576   PropertyMapNode *b = node->right->left;
    577 
    578   rotateLL(c);
    579   rotateRR(b);
    580 
    581   updateHeight(a);
    582   updateHeight(c);
    583   updateHeight(b);
    584 }
    585 
    586 void PropertyMap::rotateLR(PropertyMapNode* &node)
    587 {
    588   /*
    589     Perform a LR ("double right") rotation, e.g.
    590 
    591           a                         a                      b
    592         /   \    RR on c          /   \     LL on a      /   \
    593       c       Z    -->          b       Z     -->      c       a
    594      / \                       / \                    / \     / \
    595     W   b                     c   Y                  W   X   Y   Z
    596        / \                   / \
    597       X   Y                 W   X
    598   */
    599 
    600   PropertyMapNode *a = node;
    601   PropertyMapNode *c = node->left;
    602   PropertyMapNode *b = node->left->right;
    603 
    604   rotateRR(c);
    605   rotateLL(a);
    606 
    607   updateHeight(c);
    608   updateHeight(a);
    609   updateHeight(b);
     270    UString::Rep *key = _singleEntry.key;
     271    if (key && !(_singleEntry.attributes & DontEnum))
     272        list.append(Reference(base, key));
     273    for (int i = 0; i != _tableSize; ++i) {
     274        UString::Rep *key = _table[i].key;
     275        if (key && !(_table[i].attributes & DontEnum))
     276            list.append(Reference(base, key));
     277    }
    610278}
    611279

  • trunk/JavaScriptCore/kjs/property_map.h

    r2740 r2749  
    22/*
    33 *  This file is part of the KDE libraries
    4  *  Copyright (C) 2001 Peter Kelly (pmk@post.com)
     4 *  Copyright (C) 2002 Darin Adler (darin@apple.com)
    55 *
    66 *  This library is free software; you can redistribute it and/or
    … …  
    2121 */
    2222
    23 
    2423#ifndef _KJS_PROPERTY_MAP_H_
    2524#define _KJS_PROPERTY_MAP_H_
    2625
    2726#include "ustring.h"
    28 #include "value.h"
    2927
    3028namespace KJS {
    3129
    32   class PropertyMapNode;
    33   class ReferenceList;
     30    class Object;
     31    class ReferenceList;
     32    class ValueImp;
     33   
     34    struct PropertyMapHashTableEntry
     35    {
     36        PropertyMapHashTableEntry() : key(0) { }
     37        UString::Rep *key;
     38        ValueImp *value;
     39        int attributes;
     40    };
     41   
     42    class PropertyMap {
     43    public:
     44        PropertyMap();
     45        ~PropertyMap();
    3446
    35   /**
    36    * @internal
    37    *
    38    * Provides a name/value map for storing properties based on UString keys. The
    39    * map is implemented using an AVL tree, which provides O(log2 n) performance
    40    * for insertion and deletion, and retrieval.
    41    *
    42    * For a description of AVL tree operations, see
    43    * http://www.cis.ksu.edu/~howell/300f99/minavl/rotations.html
    44    * http://www.cgc.cs.jhu.edu/~jkloss/htmls/structures/avltree.html
    45    */
    46   class PropertyMap {
    47   public:
    48     PropertyMap();
    49     ~PropertyMap();
     47        void clear();
     48       
     49        void put(const UString &name, ValueImp *value, int attributes);
     50        void remove(const UString &name);
     51        ValueImp *get(const UString &name) const;
     52        ValueImp *get(const UString &name, int &attributes) const;
    5053
    51     void put(const UString &name, ValueImp *value, int attr);
    52     void remove(const UString &name);
    53     ValueImp *get(const UString &name) const;
    54     ValueImp *get(const UString &name, int &attributes) const;
    55    
    56     void clear();
    57     void mark();
    58    
    59     void addEnumerablesToReferenceList(ReferenceList &, const Object &) const;
     54        void mark() const;
     55        void addEnumerablesToReferenceList(ReferenceList &, const Object &) const;
    6056
    61   private:
    62 
    63     void clear(PropertyMapNode *node);
    64     void dump(const PropertyMapNode *node = 0, int indent = 0) const;
    65     void checkTree(const PropertyMapNode *node = 0) const;
    66 
    67     PropertyMapNode *getNode(const UString &name) const;
    68     PropertyMapNode *first() const;
    69 
    70     PropertyMapNode *remove(PropertyMapNode *node);
    71     void balance(PropertyMapNode* node);
    72     void updateHeight(PropertyMapNode* &node);
    73 
    74     void rotateRR(PropertyMapNode* &node);
    75     void rotateLL(PropertyMapNode* &node);
    76     void rotateRL(PropertyMapNode* &node);
    77     void rotateLR(PropertyMapNode* &node);
    78 
    79     PropertyMapNode *root;
    80   };
    81 
    82   int uscompare(const UString &s1, const UString &s2);
     57    private:
     58        int hash(const UString::Rep *) const;
     59        static bool keysMatch(const UString::Rep *, const UString::Rep *);
     60        void expand();
     61       
     62        void insert(UString::Rep *, ValueImp *value, int attributes);
     63       
     64        typedef PropertyMapHashTableEntry Entry;
     65       
     66        int _tableSizeHashMask;
     67        int _tableSize;
     68        Entry *_table;
     69        int _keyCount;
     70       
     71        Entry _singleEntry;
     72    };
    8373
    8474}; // namespace

  • trunk/JavaScriptCore/kjs/string_object.cpp

    r1824 r2749  
    4242{
    4343  setInternalValue(String(""));
     44}
     45
     46StringInstanceImp::StringInstanceImp(const Object &proto, const UString &string)
     47  : ObjectImp(proto)
     48{
     49  setInternalValue(String(string));
     50}
     51
     52Value StringInstanceImp::get(ExecState *exec, const UString &propertyName) const
     53{
     54  if (propertyName == lengthPropertyName)
     55    return Number(internalValue().toString(exec).size());
     56  return ObjectImp::get(exec, propertyName);
     57}
     58
     59void StringInstanceImp::put(ExecState *exec, const UString &propertyName, const Value &value, int attr)
     60{
     61  if (propertyName == lengthPropertyName)
     62    return;
     63  ObjectImp::put(exec, propertyName, value, attr);
     64}
     65
     66bool StringInstanceImp::hasProperty(ExecState *exec, const UString &propertyName) const
     67{
     68  if (propertyName == lengthPropertyName)
     69    return true;
     70  return ObjectImp::hasProperty(exec, propertyName);
     71}
     72
     73bool StringInstanceImp::deleteProperty(ExecState *exec, const UString &propertyName)
     74{
     75  if (propertyName == lengthPropertyName)
     76    return false;
     77  return ObjectImp::deleteProperty(exec, propertyName);
    4478}
    4579
    … …  
    517551{
    518552  Object proto = exec->interpreter()->builtinStringPrototype();
    519   Object obj(new StringInstanceImp(proto ));
    520 
    521   UString s;
    522   if (args.size() > 0)
    523     s = args.begin()->dispatchToString(exec);
    524   else
    525     s = UString("");
    526 
    527   obj.setInternalValue(String(s));
    528   obj.put(exec, lengthPropertyName, Number(s.size()), ReadOnly|DontEnum|DontDelete);
    529 
    530   return obj;
     553  if (args.size() == 0)
     554    return Object(new StringInstanceImp(proto));
     555  return Object(new StringInstanceImp(proto, args.begin()->dispatchToString(exec)));
    531556}
    532557

  • trunk/JavaScriptCore/kjs/string_object.h

    r1024 r2749  
    3131  public:
    3232    StringInstanceImp(const Object &proto);
     33    StringInstanceImp(const Object &proto, const UString &string);
     34
     35    virtual Value get(ExecState *exec, const UString &propertyName) const;
     36    virtual void put(ExecState *exec, const UString &propertyName, const Value &value, int attr = None);
     37    virtual bool hasProperty(ExecState *exec, const UString &propertyName) const;
     38    virtual bool deleteProperty(ExecState *exec, const UString &propertyName);
    3339
    3440    virtual const ClassInfo *classInfo() const { return &info; }

  • trunk/JavaScriptCore/kjs/ustring.cpp

    r2740 r2749  
    592592void UString::release()
    593593{
    594   if (!rep->deref()) {
    595     delete [] rep->dat;
    596     delete rep;
    597   }
     594  rep->deref();
    598595}
    599596
    … …  
    665662  return (l1 < l2) ? 1 : -1;
    666663}
    667 
    668 // Algorithm concept from Algorithms in C++, Sedgewick, Program 14.1.
    669 int KJS::hash(const UString &s, int hashTableSize)
    670 {
    671     int h = 0;
    672     int length = s.size();
    673     int prefix = length < 8 ? length : 8;
    674     for (int i = 0; i != prefix; i++)
    675         h = (127 * h + s[i].unicode()) % hashTableSize;
    676     int suffix = length < 16 ? 8 : length - 8;
    677     for (int i = suffix; i != length; i++)
    678         h = (127 * h + s[i].unicode()) % hashTableSize;
    679     return h;
    680 }

  • trunk/JavaScriptCore/kjs/ustring.h

    r2740 r2749  
    144144     * @return Unicode value.
    145145     */
    146     unsigned short unicode() const { return ref().unicode(); }
     146    unsigned short unicode() const { return ref().uc; }
    147147    /**
    148148     * @return Lower byte.
    149149     */
    150     unsigned char low() const { return ref().uc & 0xFF; }
     150    unsigned char low() const { return ref().uc; }
    151151    /**
    152152     * @return Higher byte.
    … …  
    200200    friend bool operator==(const UString&, const UString&);
    201201    friend class UCharReference;
     202    friend class PropertyMap;
     203    friend class PropertyMapHashTableEntry;
    202204    /**
    203205     * @internal
    … …  
    211213
    212214      inline void ref() { rc++; }
    213       inline int deref() { return --rc; }
     215      inline void deref() {
     216        if (--rc == 0) {
     217          delete [] dat;
     218          delete this;
     219        }
     220      }
    214221
    215222      UChar *dat;
    … …  
    403410#endif
    404411  private:
     412    UString(Rep *r) { attach(r); }
    405413    void attach(Rep *r);
    406414    void detach();
    … …  
    433441 
    434442  int compare(const UString &, const UString &);
    435   int hash(const UString &, int hashTableSize);
    436443
    437444}; // namespace
Note: See TracChangeset for help on using the changeset viewer.