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., 51 Franklin Street, Fifth Floor, 00018 * Boston, MA 02110-1301, 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 00067 // gets initialized in expand, an array that stores insert order of a particular hash 00068 int *hashToIndex; // NOTE: is one based 1,2,3 etc.. 00069 00070 // keeps trac on how many insertions we have made, cant use keyCount because delete a key in the middle messes things 00071 int indexCount; 00072 00073 PropertyMapHashTableEntry entries[1]; 00074 }; 00075 00076 class SavedProperty { 00077 public: 00078 Identifier key; 00079 Value value; 00080 int attributes; 00081 }; 00082 00083 SavedProperties::SavedProperties() : _count(0), _properties(0) { } 00084 00085 SavedProperties::~SavedProperties() 00086 { 00087 delete [] _properties; 00088 } 00089 00090 // Algorithm concepts from Algorithms in C++, Sedgewick. 00091 00092 PropertyMap::PropertyMap() : _table(0) 00093 { 00094 } 00095 00096 PropertyMap::~PropertyMap() 00097 { 00098 if (!_table) { 00099 #if USE_SINGLE_ENTRY 00100 UString::Rep *key = _singleEntry.key; 00101 if (key) 00102 key->deref(); 00103 #endif 00104 return; 00105 } 00106 00107 for (int i = 0; i < _table->size; i++) { 00108 UString::Rep *key = _table->entries[i].key; 00109 if (key) 00110 key->deref(); 00111 } 00112 // fredrik added to cleanup sortorder 00113 if (_table) 00114 delete [] _table->hashToIndex; 00115 00116 free(_table); 00117 } 00118 00119 void PropertyMap::clear() 00120 { 00121 if (!_table) { 00122 #if USE_SINGLE_ENTRY 00123 UString::Rep *key = _singleEntry.key; 00124 if (key) { 00125 key->deref(); 00126 _singleEntry.key = 0; 00127 } 00128 #endif 00129 return; 00130 } 00131 00132 for (int i = 0; i < _table->size; i++) { 00133 UString::Rep *key = _table->entries[i].key; 00134 if (key) { 00135 key->deref(); 00136 _table->entries[i].key = 0; 00137 } 00138 } 00139 _table->keyCount = 0; 00140 } 00141 00142 inline int PropertyMap::hash(const UString::Rep *s) const 00143 { 00144 return s->hash() & _table->sizeMask; 00145 } 00146 00147 ValueImp *PropertyMap::get(const Identifier &name, int &attributes) const 00148 { 00149 assert(!name.isNull()); 00150 00151 UString::Rep *rep = name._ustring.rep; 00152 00153 if (!_table) { 00154 #if USE_SINGLE_ENTRY 00155 UString::Rep *key = _singleEntry.key; 00156 if (rep == key) { 00157 attributes = _singleEntry.attributes; 00158 return _singleEntry.value; 00159 } 00160 #endif 00161 return 0; 00162 } 00163 00164 int i = hash(rep); 00165 #if DUMP_STATISTICS 00166 ++numProbes; 00167 numCollisions += _table->entries[i].key && _table->entries[i].key != rep; 00168 #endif 00169 while (UString::Rep *key = _table->entries[i].key) { 00170 if (rep == key) { 00171 attributes = _table->entries[i].attributes; 00172 return _table->entries[i].value; 00173 } 00174 i = (i + 1) & _table->sizeMask; 00175 } 00176 return 0; 00177 } 00178 00179 ValueImp *PropertyMap::get(const Identifier &name) const 00180 { 00181 assert(!name.isNull()); 00182 00183 UString::Rep *rep = name._ustring.rep; 00184 00185 if (!_table) { 00186 #if USE_SINGLE_ENTRY 00187 UString::Rep *key = _singleEntry.key; 00188 if (rep == key) 00189 return _singleEntry.value; 00190 #endif 00191 return 0; 00192 } 00193 00194 int i = hash(rep); 00195 #if DUMP_STATISTICS 00196 ++numProbes; 00197 numCollisions += _table->entries[i].key && _table->entries[i].key != rep; 00198 #endif 00199 while (UString::Rep *key = _table->entries[i].key) { 00200 if (rep == key) 00201 return _table->entries[i].value; 00202 i = (i + 1) & _table->sizeMask; 00203 } 00204 return 0; 00205 } 00206 00207 #if DEBUG_PROPERTIES 00208 static void printAttributes(int attributes) 00209 { 00210 if (attributes == 0) 00211 printf ("None "); 00212 if (attributes & ReadOnly) 00213 printf ("ReadOnly "); 00214 if (attributes & DontEnum) 00215 printf ("DontEnum "); 00216 if (attributes & DontDelete) 00217 printf ("DontDelete "); 00218 if (attributes & Internal) 00219 printf ("Internal "); 00220 if (attributes & Function) 00221 printf ("Function "); 00222 } 00223 #endif 00224 00225 void PropertyMap::put(const Identifier &name, ValueImp *value, int attributes) 00226 { 00227 assert(!name.isNull()); 00228 assert(value != 0); 00229 00230 #if DO_CONSISTENCY_CHECK // speed, why call a stub if we dont need to?? 00231 checkConsistency(); 00232 #endif 00233 00234 UString::Rep *rep = name._ustring.rep; 00235 00236 #if DEBUG_PROPERTIES 00237 printf("adding property %s, attributes = 0x%08x (", name.ascii(), attributes); 00238 printAttributes(attributes); 00239 printf(")\n"); 00240 #endif 00241 00242 #if USE_SINGLE_ENTRY 00243 if (!_table) { 00244 UString::Rep *key = _singleEntry.key; 00245 if (key) { 00246 if (rep == key) { 00247 _singleEntry.value = value; 00248 return; 00249 } 00250 } else { 00251 rep->ref(); 00252 _singleEntry.key = rep; 00253 _singleEntry.value = value; 00254 _singleEntry.attributes = attributes; 00255 checkConsistency(); 00256 return; 00257 } 00258 } 00259 #endif 00260 if (!_table || _table->keyCount * 2 >= _table->size) 00261 expand(); 00262 int i = hash(rep); 00263 #if DUMP_STATISTICS 00264 ++numProbes; 00265 numCollisions += _table->entries[i].key && _table->entries[i].key != rep; 00266 #endif 00267 while (UString::Rep *key = _table->entries[i].key) { 00268 if (rep == key) { 00269 // Put a new value in an existing hash table entry. 00270 _table->entries[i].value = value; 00271 // Attributes are intentionally not updated. 00272 return; 00273 } 00274 i = (i + 1) & _table->sizeMask; 00275 } 00276 00277 // Create a new hash table entry. 00278 rep->ref(); 00279 _table->entries[i].key = rep; 00280 _table->entries[i].value = value; 00281 _table->entries[i].attributes = attributes; 00282 ++_table->keyCount; 00283 00284 // store insert order 00285 _table->indexCount++; 00286 _table->hashToIndex[i] = _table->indexCount; 00287 00288 #if DO_CONSISTENCY_CHECK// speed, why call a stub if we dont need to?? 00289 checkConsistency(); 00290 #endif 00291 } 00292 00293 inline void PropertyMap::insert(UString::Rep *key, ValueImp *value, int attributes) 00294 { 00295 assert(_table); 00296 00297 int i = hash(key); 00298 #if DUMP_STATISTICS 00299 ++numProbes; 00300 numCollisions += _table->entries[i].key && _table->entries[i].key != key; 00301 #endif 00302 while (_table->entries[i].key) 00303 i = (i + 1) & _table->sizeMask; 00304 00305 _table->entries[i].key = key; 00306 _table->entries[i].value = value; 00307 _table->entries[i].attributes = attributes; 00308 } 00309 00310 void PropertyMap::expand() 00311 { 00312 #if DO_CONSISTENCY_CHECK// speed, why call a stub if we dont need to?? 00313 checkConsistency(); 00314 #endif 00315 Table *oldTable = _table; 00316 00317 int oldTableSize = oldTable ? oldTable->size : 0; 00318 00319 int newTableSize = oldTableSize ? oldTableSize * 2 : 16; 00320 00321 // Is this realy the best way? wouldnt it be easier to use new/delete on an array instead 00322 // and do a pointer in Table to that array, that way we wouldnt need to delete the whole _table 00323 // every time we need to expand 00324 _table = (Table *)calloc(1, sizeof(Table) + ((newTableSize - 1) * sizeof(Entry)) ); 00325 00326 int *p = new int[newTableSize]; 00327 for (int i = 0; i < newTableSize; i++) 00328 p[i] = 0; 00329 00330 _table->hashToIndex = p; 00331 00332 _table->size = newTableSize; 00333 00334 _table->sizeMask = newTableSize - 1; 00335 00336 _table->keyCount = oldTable ? oldTable->keyCount : 0; 00337 00338 _table->indexCount = oldTable ? oldTable->indexCount : 0; 00339 00340 #if USE_SINGLE_ENTRY 00341 UString::Rep *key = _singleEntry.key; 00342 if (key) { 00343 insert(key, _singleEntry.value, _singleEntry.attributes); 00344 _table->keyCount++; 00345 _singleEntry.key = 0; 00346 00347 // store sort order 00348 // first get the id of newly inserted key, check for trashed hash, then store it 00349 int k = hash(key); 00350 #if DUMP_STATISTICS 00351 ++numProbes; 00352 numCollisions += _table->entries[k].key && _table->entries[k].key != key; 00353 #endif 00354 while (UString::Rep *newKey = _table->entries[k].key) { 00355 if (key == newKey) 00356 break; 00357 k = (k + 1) & _table->sizeMask; 00358 } 00359 _table->indexCount++; 00360 _table->hashToIndex[k] = _table->indexCount; 00361 } 00362 #endif 00363 00364 for (int i = 0; i != oldTableSize; ++i) { 00365 UString::Rep *key = oldTable->entries[i].key; 00366 if (key) { 00367 insert(key, oldTable->entries[i].value, oldTable->entries[i].attributes); 00368 00369 // store sort order 00370 // first get the id of newly inserted key, check for trashed hash, then store it 00371 int k = hash(key); 00372 #if DUMP_STATISTICS 00373 ++numProbes; 00374 numCollisions += _table->entries[k].key && _table->entries[k].key != key; 00375 #endif 00376 while (UString::Rep *newKey = _table->entries[k].key) { 00377 if (key == newKey) 00378 break; 00379 k = (k + 1) & _table->sizeMask; 00380 } 00381 // store hashindex on the newly inserted entry 00382 _table->hashToIndex[k] = oldTable->hashToIndex[i]; 00383 } 00384 } 00385 00386 if (oldTable){ 00387 delete [] oldTable->hashToIndex; 00388 } 00389 free(oldTable); 00390 00391 #if DO_CONSISTENCY_CHECK// speed, why call a stub if we dont need to?? 00392 checkConsistency(); 00393 #endif 00394 } 00395 00396 void PropertyMap::remove(const Identifier &name) 00397 { 00398 assert(!name.isNull()); 00399 00400 #if DO_CONSISTENCY_CHECK// speed, why call a stub if we dont need to?? 00401 checkConsistency(); 00402 #endif 00403 00404 UString::Rep *rep = name._ustring.rep; 00405 00406 UString::Rep *key; 00407 00408 if (!_table) { 00409 #if USE_SINGLE_ENTRY 00410 key = _singleEntry.key; 00411 if (rep == key) { 00412 key->deref(); 00413 _singleEntry.key = 0; 00414 checkConsistency(); 00415 } 00416 #endif 00417 return; 00418 } 00419 00420 // Find the thing to remove. 00421 int i = hash(rep); 00422 #if DUMP_STATISTICS 00423 ++numProbes; 00424 numCollisions += _table->entries[i].key && _table->entries[i].key != rep; 00425 #endif 00426 while ((key = _table->entries[i].key)) { 00427 if (rep == key) 00428 break; 00429 i = (i + 1) & _table->sizeMask; 00430 } 00431 00432 if (!key) 00433 return; 00434 00435 // Remove the one key. 00436 key->deref(); 00437 _table->entries[i].key = 0; 00438 assert(_table->keyCount >= 1); 00439 --_table->keyCount; 00440 00441 // Reinsert all the items to the right in the same cluster. 00442 while (1) { 00443 i = (i + 1) & _table->sizeMask; 00444 key = _table->entries[i].key; 00445 if (!key) 00446 break; 00447 00448 _table->entries[i].key = 0; 00449 00450 insert(key, _table->entries[i].value, _table->entries[i].attributes); 00451 00452 // store the index of the new hash 00453 int k = hash(key); 00454 #if DUMP_STATISTICS 00455 ++numProbes; 00456 numCollisions += _table->entries[k].key && _table->entries[k].key != key; 00457 #endif 00458 while (UString::Rep *newKey = _table->entries[k].key) { 00459 if (key == newKey) 00460 break; 00461 k = (k + 1) & _table->sizeMask; 00462 } 00463 00464 // store hashindex on the newly moved entry 00465 _table->hashToIndex[k] = _table->hashToIndex[i]; 00466 } 00467 00468 #if DO_CONSISTENCY_CHECK// speed, why call a stub if we dont need to?? 00469 checkConsistency(); 00470 #endif 00471 } 00472 00473 void PropertyMap::mark() const 00474 { 00475 if (!_table) { 00476 #if USE_SINGLE_ENTRY 00477 if (_singleEntry.key) { 00478 ValueImp *v = _singleEntry.value; 00479 if (!v->marked()) 00480 v->mark(); 00481 } 00482 #endif 00483 return; 00484 } 00485 00486 for (int i = 0; i != _table->size; ++i) { 00487 if (_table->entries[i].key) { 00488 ValueImp *v = _table->entries[i].value; 00489 if (!v->marked()) 00490 v->mark(); 00491 } 00492 } 00493 } 00494 00495 void PropertyMap::addEnumerablesToReferenceList(ReferenceList &list, const Object &base) const 00496 { 00497 if (!_table) { 00498 #if USE_SINGLE_ENTRY 00499 UString::Rep *key = _singleEntry.key; 00500 if (key && !(_singleEntry.attributes & DontEnum)) 00501 list.append(Reference(base, Identifier(key))); 00502 #endif 00503 return; 00504 } 00505 00506 // Allocate a buffer to use to sort the keys. 00507 int indexSize = _table->indexCount + 1; // indexes is one based 00508 UString::Rep **allKeys = new UString::Rep*[indexSize]; 00509 00510 for (int i = 0; i < indexSize; i++) 00511 allKeys[i] = NULL; 00512 00513 // push valid hashes to the array allKeys, using insert order as index. 00514 // we need to pass array hashes instead of pointers to keys, because we got 00515 // memory corruption sometimes, seems that Identifier in below call deletes the key 00516 int size = _table->size; 00517 Entry *entries = _table->entries; 00518 for (int i = 0; i != size; ++i) { 00519 if (entries[i].key && !(entries[i].attributes & DontEnum)) { 00520 int idx = _table->hashToIndex[i]; 00521 if (idx) { 00522 allKeys[idx] = entries[i].key; 00523 } else { // nonsorted key, failure 00524 //cout<<"Error with in KJS property_map.addEnumerablesToReferenceList \nUnsorted key"<<endl; 00525 assert(0==1); // allways throw error if get here 00526 } 00527 } 00528 } 00529 // Put the keys of the sorted entries into the reference list. 00530 for (int i = 0; i < indexSize; ++i) { 00531 if (allKeys[i] != NULL){ 00532 list.append(Reference(base, Identifier(allKeys[i]))); 00533 } 00534 allKeys[i] = NULL; // dont deallocate key by accident, when we delete allKeys 00535 } 00536 00537 // Deallocate the buffer. 00538 delete [] allKeys; 00539 } 00540 00541 void PropertyMap::addSparseArrayPropertiesToReferenceList(ReferenceList &list, const Object &base) const 00542 { 00543 // NOTE: I did'nt add sort in this method because It seems to be referenced in ArrayInstanceImp 00544 // only and arrays are sorted by definition, dont need the extra overhead 00545 if (!_table) { 00546 #if USE_SINGLE_ENTRY 00547 UString::Rep *key = _singleEntry.key; 00548 if (key) { 00549 UString k(key); 00550 bool fitsInULong; 00551 unsigned long i = k.toULong(&fitsInULong); 00552 if (fitsInULong && i <= 0xFFFFFFFFU) 00553 list.append(Reference(base, Identifier(key))); 00554 } 00555 #endif 00556 return; 00557 } 00558 00559 for (int i = 0; i != _table->size; ++i) { 00560 UString::Rep *key = _table->entries[i].key; 00561 if (key) { 00562 UString k(key); 00563 bool fitsInULong; 00564 unsigned long i = k.toULong(&fitsInULong); 00565 if (fitsInULong && i <= 0xFFFFFFFFU) 00566 list.append(Reference(base, Identifier(key))); 00567 } 00568 } 00569 } 00570 00571 void PropertyMap::save(SavedProperties &p) const 00572 { 00573 int count = 0; 00574 00575 if (!_table) { 00576 #if USE_SINGLE_ENTRY 00577 if (_singleEntry.key && !(_singleEntry.attributes & (ReadOnly | DontEnum | Function))) 00578 ++count; 00579 #endif 00580 } else { 00581 for (int i = 0; i != _table->size; ++i) 00582 if (_table->entries[i].key && !(_table->entries[i].attributes & (ReadOnly | DontEnum | Function))) 00583 ++count; 00584 } 00585 00586 delete [] p._properties; 00587 00588 p._count = count; 00589 00590 if (count == 0) { 00591 p._properties = 0; 00592 return; 00593 } 00594 00595 p._properties = new SavedProperty [count]; 00596 00597 SavedProperty *prop = p._properties; 00598 00599 if (!_table) { 00600 #if USE_SINGLE_ENTRY 00601 if (_singleEntry.key && !(_singleEntry.attributes & (ReadOnly | DontEnum | Function))) { 00602 prop->key = Identifier(_singleEntry.key); 00603 prop->value = Value(_singleEntry.value); 00604 prop->attributes = _singleEntry.attributes; 00605 ++prop; 00606 } 00607 #endif 00608 } else { 00609 for (int i = 0; i != _table->size; ++i) { 00610 if (_table->entries[i].key && !(_table->entries[i].attributes & (ReadOnly | DontEnum | Function))) { 00611 prop->key = Identifier(_table->entries[i].key); 00612 prop->value = Value(_table->entries[i].value); 00613 prop->attributes = _table->entries[i].attributes; 00614 ++prop; 00615 } 00616 } 00617 } 00618 } 00619 00620 void PropertyMap::restore(const SavedProperties &p) 00621 { 00622 for (int i = 0; i != p._count; ++i) 00623 put(p._properties[i].key, p._properties[i].value.imp(), p._properties[i].attributes); 00624 } 00625 00626 #if DO_CONSISTENCY_CHECK 00627 00628 void PropertyMap::checkConsistency() 00629 { 00630 if (!_table) 00631 return; 00632 00633 int count = 0; 00634 for (int j = 0; j != _table->size; ++j) { 00635 UString::Rep *rep = _table->entries[j].key; 00636 if (!rep) 00637 continue; 00638 int i = hash(rep); 00639 while (UString::Rep *key = _table->entries[i].key) { 00640 if (rep == key) 00641 break; 00642 i = (i + 1) & _table->sizeMask; 00643 } 00644 assert(i == j); 00645 assert(_table->hashToIndex[i] > 0); 00646 count++; 00647 } 00648 assert(count == _table->keyCount); 00649 assert(_table->size >= 16); 00650 assert(_table->sizeMask); 00651 assert(_table->size == _table->sizeMask + 1); 00652 } 00653 00654 #endif // DO_CONSISTENCY_CHECK 00655 00656 } // namespace KJS