kjs Library API Documentation

property_map.cpp

00001 /*
00002  *  This file is part of the KDE libraries
00003  *  Copyright (C) 2003 Apple Computer, Inc.
00004  *
00005  *  This library is free software; you can redistribute it and/or
00006  *  modify it under the terms of the GNU Library General Public
00007  *  License as published by the Free Software Foundation; either
00008  *  version 2 of the License, or (at your option) any later version.
00009  *
00010  *  This library is distributed in the hope that it will be useful,
00011  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
00012  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00013  *  Library General Public License for more details.
00014  *
00015  *  You should have received a copy of the GNU Library General Public License
00016  *  along with this library; see the file COPYING.LIB.  If not, write to
00017  *  the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
00018  *  Boston, MA 02111-1307, USA.
00019  *
00020  */
00021 
00022 #include "property_map.h"
00023 
00024 #include "object.h"
00025 #include "reference_list.h"
00026 
00027 #include <assert.h>
00028 
00029 #define DEBUG_PROPERTIES 0
00030 #define DO_CONSISTENCY_CHECK 0
00031 #define DUMP_STATISTICS 0
00032 #define USE_SINGLE_ENTRY 1
00033 
00034 // At the time I added USE_SINGLE_ENTRY, the optimization still gave a 1.5%
00035 // performance boost to the iBench JavaScript benchmark so I didn't remove it.
00036 
00037 #if !DO_CONSISTENCY_CHECK
00038 #define checkConsistency() ((void)0)
00039 #endif
00040 
00041 namespace KJS {
00042 
00043 #if DUMP_STATISTICS
00044 
00045 static int numProbes;
00046 static int numCollisions;
00047 
00048 struct PropertyMapStatisticsExitLogger { ~PropertyMapStatisticsExitLogger(); };
00049 
00050 static PropertyMapStatisticsExitLogger logger;
00051 
00052 PropertyMapStatisticsExitLogger::~PropertyMapStatisticsExitLogger()
00053 {
00054     printf("\nKJS::PropertyMap statistics\n\n");
00055     printf("%d probes\n", numProbes);
00056     printf("%d collisions (%.1f%%)\n", numCollisions, 100.0 * numCollisions / numProbes);
00057 }
00058 
00059 #endif
00060 
00061 struct PropertyMapHashTable
00062 {
00063     int sizeMask;
00064     int size;
00065     int keyCount;
00066     PropertyMapHashTableEntry entries[1];
00067 };
00068 
00069 class SavedProperty {
00070 public:
00071     Identifier key;
00072     Value value;
00073     int attributes;
00074 };
00075 
00076 SavedProperties::SavedProperties() : _count(0), _properties(0) { }
00077 
00078 SavedProperties::~SavedProperties()
00079 {
00080     delete [] _properties;
00081 }
00082 
00083 // Algorithm concepts from Algorithms in C++, Sedgewick.
00084 
00085 PropertyMap::PropertyMap() : _table(0)
00086 {
00087 }
00088 
00089 PropertyMap::~PropertyMap()
00090 {
00091     if (!_table) {
00092 #if USE_SINGLE_ENTRY
00093         UString::Rep *key = _singleEntry.key;
00094         if (key)
00095             key->deref();
00096 #endif
00097         return;
00098     }
00099 
00100     for (int i = 0; i < _table->size; i++) {
00101         UString::Rep *key = _table->entries[i].key;
00102         if (key)
00103       key->deref();
00104     }
00105     free(_table);
00106 }
00107 
00108 void PropertyMap::clear()
00109 {
00110     if (!_table) {
00111 #if USE_SINGLE_ENTRY
00112         UString::Rep *key = _singleEntry.key;
00113         if (key) {
00114             key->deref();
00115             _singleEntry.key = 0;
00116         }
00117 #endif
00118         return;
00119     }
00120 
00121     for (int i = 0; i < _table->size; i++) {
00122         UString::Rep *key = _table->entries[i].key;
00123         if (key) {
00124             key->deref();
00125             _table->entries[i].key = 0;
00126         }
00127     }
00128     _table->keyCount = 0;
00129 }
00130 
00131 inline int PropertyMap::hash(const UString::Rep *s) const
00132 {
00133     return s->hash() & _table->sizeMask;
00134 }
00135 
00136 ValueImp *PropertyMap::get(const Identifier &name, int &attributes) const
00137 {
00138     assert(!name.isNull());
00139 
00140     UString::Rep *rep = name._ustring.rep;
00141 
00142     if (!_table) {
00143 #if USE_SINGLE_ENTRY
00144         UString::Rep *key = _singleEntry.key;
00145         if (rep == key) {
00146             attributes = _singleEntry.attributes;
00147             return _singleEntry.value;
00148         }
00149 #endif
00150         return 0;
00151     }
00152 
00153     int i = hash(rep);
00154 #if DUMP_STATISTICS
00155     ++numProbes;
00156     numCollisions += _table->entries[i].key && _table->entries[i].key != rep;
00157 #endif
00158     while (UString::Rep *key = _table->entries[i].key) {
00159         if (rep == key) {
00160             attributes = _table->entries[i].attributes;
00161             return _table->entries[i].value;
00162         }
00163         i = (i + 1) & _table->sizeMask;
00164     }
00165     return 0;
00166 }
00167 
00168 ValueImp *PropertyMap::get(const Identifier &name) const
00169 {
00170     assert(!name.isNull());
00171 
00172     UString::Rep *rep = name._ustring.rep;
00173 
00174     if (!_table) {
00175 #if USE_SINGLE_ENTRY
00176         UString::Rep *key = _singleEntry.key;
00177         if (rep == key)
00178             return _singleEntry.value;
00179 #endif
00180         return 0;
00181     }
00182 
00183     int i = hash(rep);
00184 #if DUMP_STATISTICS
00185     ++numProbes;
00186     numCollisions += _table->entries[i].key && _table->entries[i].key != rep;
00187 #endif
00188     while (UString::Rep *key = _table->entries[i].key) {
00189         if (rep == key)
00190             return _table->entries[i].value;
00191         i = (i + 1) & _table->sizeMask;
00192     }
00193     return 0;
00194 }
00195 
00196 #if DEBUG_PROPERTIES
00197 static void printAttributes(int attributes)
00198 {
00199     if (attributes == 0)
00200         printf ("None ");
00201     if (attributes & ReadOnly)
00202         printf ("ReadOnly ");
00203     if (attributes & DontEnum)
00204         printf ("DontEnum ");
00205     if (attributes & DontDelete)
00206         printf ("DontDelete ");
00207     if (attributes & Internal)
00208         printf ("Internal ");
00209     if (attributes & Function)
00210         printf ("Function ");
00211 }
00212 #endif
00213 
00214 void PropertyMap::put(const Identifier &name, ValueImp *value, int attributes)
00215 {
00216     assert(!name.isNull());
00217     assert(value != 0);
00218 
00219     checkConsistency();
00220 
00221     UString::Rep *rep = name._ustring.rep;
00222 
00223 #if DEBUG_PROPERTIES
00224     printf("adding property %s, attributes = 0x%08x (", name.ascii(), attributes);
00225     printAttributes(attributes);
00226     printf(")\n");
00227 #endif
00228 
00229 #if USE_SINGLE_ENTRY
00230     if (!_table) {
00231         UString::Rep *key = _singleEntry.key;
00232         if (key) {
00233             if (rep == key) {
00234                 _singleEntry.value = value;
00235                 return;
00236             }
00237         } else {
00238             rep->ref();
00239             _singleEntry.key = rep;
00240             _singleEntry.value = value;
00241             _singleEntry.attributes = attributes;
00242             checkConsistency();
00243             return;
00244         }
00245     }
00246 #endif
00247 
00248     if (!_table || _table->keyCount * 2 >= _table->size)
00249         expand();
00250 
00251     int i = hash(rep);
00252 #if DUMP_STATISTICS
00253     ++numProbes;
00254     numCollisions += _table->entries[i].key && _table->entries[i].key != rep;
00255 #endif
00256     while (UString::Rep *key = _table->entries[i].key) {
00257         if (rep == key) {
00258             // Put a new value in an existing hash table entry.
00259             _table->entries[i].value = value;
00260             // Attributes are intentionally not updated.
00261             return;
00262         }
00263         i = (i + 1) & _table->sizeMask;
00264     }
00265 
00266     // Create a new hash table entry.
00267     rep->ref();
00268     _table->entries[i].key = rep;
00269     _table->entries[i].value = value;
00270     _table->entries[i].attributes = attributes;
00271     ++_table->keyCount;
00272 
00273     checkConsistency();
00274 }
00275 
00276 inline void PropertyMap::insert(UString::Rep *key, ValueImp *value, int attributes)
00277 {
00278     assert(_table);
00279 
00280     int i = hash(key);
00281 #if DUMP_STATISTICS
00282     ++numProbes;
00283     numCollisions += _table->entries[i].key && _table->entries[i].key != key;
00284 #endif
00285     while (_table->entries[i].key)
00286         i = (i + 1) & _table->sizeMask;
00287 
00288     _table->entries[i].key = key;
00289     _table->entries[i].value = value;
00290     _table->entries[i].attributes = attributes;
00291 }
00292 
00293 void PropertyMap::expand()
00294 {
00295     checkConsistency();
00296 
00297     Table *oldTable = _table;
00298     int oldTableSize = oldTable ? oldTable->size : 0;
00299 
00300     int newTableSize = oldTableSize ? oldTableSize * 2 : 16;
00301     _table = (Table *)calloc(1, sizeof(Table) + (newTableSize - 1) * sizeof(Entry) );
00302     _table->size = newTableSize;
00303     _table->sizeMask = newTableSize - 1;
00304     _table->keyCount = oldTable ? oldTable->keyCount : 0;
00305 
00306 #if USE_SINGLE_ENTRY
00307     UString::Rep *key = _singleEntry.key;
00308     if (key) {
00309         insert(key, _singleEntry.value, _singleEntry.attributes);
00310     _table->keyCount++;
00311         _singleEntry.key = 0;
00312     }
00313 #endif
00314 
00315     for (int i = 0; i != oldTableSize; ++i) {
00316         UString::Rep *key = oldTable->entries[i].key;
00317         if (key)
00318             insert(key, oldTable->entries[i].value, oldTable->entries[i].attributes);
00319     }
00320 
00321     free(oldTable);
00322 
00323     checkConsistency();
00324 }
00325 
00326 void PropertyMap::remove(const Identifier &name)
00327 {
00328     assert(!name.isNull());
00329 
00330     checkConsistency();
00331 
00332     UString::Rep *rep = name._ustring.rep;
00333 
00334     UString::Rep *key;
00335 
00336     if (!_table) {
00337 #if USE_SINGLE_ENTRY
00338         key = _singleEntry.key;
00339         if (rep == key) {
00340             key->deref();
00341             _singleEntry.key = 0;
00342             checkConsistency();
00343         }
00344 #endif
00345         return;
00346     }
00347 
00348     // Find the thing to remove.
00349     int i = hash(rep);
00350 #if DUMP_STATISTICS
00351     ++numProbes;
00352     numCollisions += _table->entries[i].key && _table->entries[i].key != rep;
00353 #endif
00354     while ((key = _table->entries[i].key)) {
00355         if (rep == key)
00356             break;
00357         i = (i + 1) & _table->sizeMask;
00358     }
00359     if (!key)
00360         return;
00361 
00362     // Remove the one key.
00363     key->deref();
00364     _table->entries[i].key = 0;
00365     assert(_table->keyCount >= 1);
00366     --_table->keyCount;
00367 
00368     // Reinsert all the items to the right in the same cluster.
00369     while (1) {
00370         i = (i + 1) & _table->sizeMask;
00371         key = _table->entries[i].key;
00372         if (!key)
00373             break;
00374         _table->entries[i].key = 0;
00375         insert(key, _table->entries[i].value, _table->entries[i].attributes);
00376     }
00377 
00378     checkConsistency();
00379 }
00380 
00381 void PropertyMap::mark() const
00382 {
00383     if (!_table) {
00384 #if USE_SINGLE_ENTRY
00385         if (_singleEntry.key) {
00386             ValueImp *v = _singleEntry.value;
00387             if (!v->marked())
00388                 v->mark();
00389         }
00390 #endif
00391         return;
00392     }
00393 
00394     for (int i = 0; i != _table->size; ++i) {
00395         if (_table->entries[i].key) {
00396             ValueImp *v = _table->entries[i].value;
00397             if (!v->marked())
00398                 v->mark();
00399         }
00400     }
00401 }
00402 
00403 void PropertyMap::addEnumerablesToReferenceList(ReferenceList &list, const Object &base) const
00404 {
00405     if (!_table) {
00406 #if USE_SINGLE_ENTRY
00407         UString::Rep *key = _singleEntry.key;
00408         if (key && !(_singleEntry.attributes & DontEnum))
00409             list.append(Reference(base, Identifier(key)));
00410 #endif
00411         return;
00412     }
00413 
00414     for (int i = 0; i != _table->size; ++i) {
00415         UString::Rep *key = _table->entries[i].key;
00416         if (key && !(_table->entries[i].attributes & DontEnum))
00417             list.append(Reference(base, Identifier(key)));
00418     }
00419 }
00420 
00421 void PropertyMap::addSparseArrayPropertiesToReferenceList(ReferenceList &list, const Object &base) const
00422 {
00423     if (!_table) {
00424 #if USE_SINGLE_ENTRY
00425         UString::Rep *key = _singleEntry.key;
00426         if (key) {
00427             UString k(key);
00428             bool fitsInULong;
00429             unsigned long i = k.toULong(&fitsInULong);
00430             if (fitsInULong && i <= 0xFFFFFFFFU)
00431                 list.append(Reference(base, Identifier(key)));
00432         }
00433 #endif
00434         return;
00435     }
00436 
00437     for (int i = 0; i != _table->size; ++i) {
00438         UString::Rep *key = _table->entries[i].key;
00439         if (key) {
00440             UString k(key);
00441             bool fitsInULong;
00442             unsigned long i = k.toULong(&fitsInULong);
00443             if (fitsInULong && i <= 0xFFFFFFFFU)
00444                 list.append(Reference(base, Identifier(key)));
00445         }
00446     }
00447 }
00448 
00449 void PropertyMap::save(SavedProperties &p) const
00450 {
00451     int count = 0;
00452 
00453     if (!_table) {
00454 #if USE_SINGLE_ENTRY
00455         if (_singleEntry.key && !(_singleEntry.attributes & (ReadOnly | DontEnum | Function)))
00456             ++count;
00457 #endif
00458     } else {
00459         for (int i = 0; i != _table->size; ++i)
00460             if (_table->entries[i].key && !(_table->entries[i].attributes & (ReadOnly | DontEnum | Function)))
00461                 ++count;
00462     }
00463 
00464     delete [] p._properties;
00465 
00466     p._count = count;
00467 
00468     if (count == 0) {
00469         p._properties = 0;
00470         return;
00471     }
00472 
00473     p._properties = new SavedProperty [count];
00474 
00475     SavedProperty *prop = p._properties;
00476 
00477     if (!_table) {
00478 #if USE_SINGLE_ENTRY
00479         if (_singleEntry.key && !(_singleEntry.attributes & (ReadOnly | DontEnum | Function))) {
00480             prop->key = Identifier(_singleEntry.key);
00481             prop->value = Value(_singleEntry.value);
00482             prop->attributes = _singleEntry.attributes;
00483             ++prop;
00484         }
00485 #endif
00486     } else {
00487         for (int i = 0; i != _table->size; ++i) {
00488             if (_table->entries[i].key && !(_table->entries[i].attributes & (ReadOnly | DontEnum | Function))) {
00489                 prop->key = Identifier(_table->entries[i].key);
00490                 prop->value = Value(_table->entries[i].value);
00491                 prop->attributes = _table->entries[i].attributes;
00492                 ++prop;
00493             }
00494         }
00495     }
00496 }
00497 
00498 void PropertyMap::restore(const SavedProperties &p)
00499 {
00500     for (int i = 0; i != p._count; ++i)
00501         put(p._properties[i].key, p._properties[i].value.imp(), p._properties[i].attributes);
00502 }
00503 
00504 #if DO_CONSISTENCY_CHECK
00505 
00506 void PropertyMap::checkConsistency()
00507 {
00508     if (!_table)
00509         return;
00510 
00511     int count = 0;
00512     for (int j = 0; j != _table->size; ++j) {
00513         UString::Rep *rep = _table->entries[j].key;
00514         if (!rep)
00515             continue;
00516         int i = hash(rep);
00517         while (UString::Rep *key = _table->entries[i].key) {
00518             if (rep == key)
00519                 break;
00520             i = (i + 1) & _table->sizeMask;
00521         }
00522         assert(i == j);
00523         count++;
00524     }
00525     assert(count == _table->keyCount);
00526     assert(_table->size >= 16);
00527     assert(_table->sizeMask);
00528     assert(_table->size == _table->sizeMask + 1);
00529 }
00530 
00531 #endif // DO_CONSISTENCY_CHECK
00532 
00533 } // namespace KJS
KDE Logo
This file is part of the documentation for kjs Library Version 3.2.2.
Documentation copyright © 1996-2004 the KDE developers.
Generated on Wed Apr 21 18:43:31 2004 by doxygen 1.3.6-20040222 written by Dimitri van Heesch, © 1997-2003