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.4.0.
Documentation copyright © 1996-2004 the KDE developers.
Generated on Thu Apr 14 00:18:53 2005 by doxygen 1.3.7 written by Dimitri van Heesch, © 1997-2003