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
KDE Home | KDE Accessibility Home | Description of Access Keys