• Skip to content
  • Skip to link menu
Trinity API Reference
  • Trinity API Reference
  • kjs
 

kjs

  • kjs
property_map.cpp
1/*
2 * This file is part of the KDE libraries
3 * Copyright (C) 2003 Apple Computer, Inc.
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Library General Public
7 * License as published by the Free Software Foundation; either
8 * version 2 of the License, or (at your option) any later version.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Library General Public License for more details.
14 *
15 * You should have received a copy of the GNU Library General Public License
16 * along with this library; see the file COPYING.LIB. If not, write to
17 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
18 * Boston, MA 02110-1301, USA.
19 *
20 */
21
22#include "property_map.h"
23
24#include "object.h"
25#include "reference_list.h"
26
27#include <assert.h>
28
29#define DEBUG_PROPERTIES 0
30#define DO_CONSISTENCY_CHECK 0
31#define DUMP_STATISTICS 0
32#define USE_SINGLE_ENTRY 1
33
34// At the time I added USE_SINGLE_ENTRY, the optimization still gave a 1.5%
35// performance boost to the iBench JavaScript benchmark so I didn't remove it.
36
37#if !DO_CONSISTENCY_CHECK
38#define checkConsistency() ((void)0)
39#endif
40
41namespace KJS {
42
43#if DUMP_STATISTICS
44
45static int numProbes;
46static int numCollisions;
47
48struct PropertyMapStatisticsExitLogger { ~PropertyMapStatisticsExitLogger(); };
49
50static PropertyMapStatisticsExitLogger logger;
51
52PropertyMapStatisticsExitLogger::~PropertyMapStatisticsExitLogger()
53{
54 printf("\nKJS::PropertyMap statistics\n\n");
55 printf("%d probes\n", numProbes);
56 printf("%d collisions (%.1f%%)\n", numCollisions, 100.0 * numCollisions / numProbes);
57}
58
59#endif
60
61struct PropertyMapHashTable
62{
63 int sizeMask;
64 int size;
65 int keyCount;
66
67 // gets initialized in expand, an array that stores insert order of a particular hash
68 int *hashToIndex; // NOTE: is one based 1,2,3 etc..
69
70 // keeps trac on how many insertions we have made, cant use keyCount because delete a key in the middle messes things
71 int indexCount;
72
73 PropertyMapHashTableEntry entries[1];
74};
75
76class SavedProperty {
77public:
78 Identifier key;
79 Value value;
80 int attributes;
81};
82
83SavedProperties::SavedProperties() : _count(0), _properties(0) { }
84
85SavedProperties::~SavedProperties()
86{
87 delete [] _properties;
88}
89
90// Algorithm concepts from Algorithms in C++, Sedgewick.
91
92PropertyMap::PropertyMap() : _table(0)
93{
94}
95
96PropertyMap::~PropertyMap()
97{
98 if (!_table) {
99#if USE_SINGLE_ENTRY
100 UString::Rep *key = _singleEntry.key;
101 if (key)
102 key->deref();
103#endif
104 return;
105 }
106
107 for (int i = 0; i < _table->size; i++) {
108 UString::Rep *key = _table->entries[i].key;
109 if (key)
110 key->deref();
111 }
112 // fredrik added to cleanup sortorder
113 if (_table)
114 delete [] _table->hashToIndex;
115
116 free(_table);
117}
118
119void PropertyMap::clear()
120{
121 if (!_table) {
122#if USE_SINGLE_ENTRY
123 UString::Rep *key = _singleEntry.key;
124 if (key) {
125 key->deref();
126 _singleEntry.key = 0;
127 }
128#endif
129 return;
130 }
131
132 for (int i = 0; i < _table->size; i++) {
133 UString::Rep *key = _table->entries[i].key;
134 if (key) {
135 key->deref();
136 _table->entries[i].key = 0;
137 }
138 }
139 _table->keyCount = 0;
140}
141
142inline int PropertyMap::hash(const UString::Rep *s) const
143{
144 return s->hash() & _table->sizeMask;
145}
146
147ValueImp *PropertyMap::get(const Identifier &name, int &attributes) const
148{
149 assert(!name.isNull());
150
151 UString::Rep *rep = name._ustring.rep;
152
153 if (!_table) {
154#if USE_SINGLE_ENTRY
155 UString::Rep *key = _singleEntry.key;
156 if (rep == key) {
157 attributes = _singleEntry.attributes;
158 return _singleEntry.value;
159 }
160#endif
161 return 0;
162 }
163
164 int i = hash(rep);
165#if DUMP_STATISTICS
166 ++numProbes;
167 numCollisions += _table->entries[i].key && _table->entries[i].key != rep;
168#endif
169 while (UString::Rep *key = _table->entries[i].key) {
170 if (rep == key) {
171 attributes = _table->entries[i].attributes;
172 return _table->entries[i].value;
173 }
174 i = (i + 1) & _table->sizeMask;
175 }
176 return 0;
177}
178
179ValueImp *PropertyMap::get(const Identifier &name) const
180{
181 assert(!name.isNull());
182
183 UString::Rep *rep = name._ustring.rep;
184
185 if (!_table) {
186#if USE_SINGLE_ENTRY
187 UString::Rep *key = _singleEntry.key;
188 if (rep == key)
189 return _singleEntry.value;
190#endif
191 return 0;
192 }
193
194 int i = hash(rep);
195#if DUMP_STATISTICS
196 ++numProbes;
197 numCollisions += _table->entries[i].key && _table->entries[i].key != rep;
198#endif
199 while (UString::Rep *key = _table->entries[i].key) {
200 if (rep == key)
201 return _table->entries[i].value;
202 i = (i + 1) & _table->sizeMask;
203 }
204 return 0;
205}
206
207#if DEBUG_PROPERTIES
208static void printAttributes(int attributes)
209{
210 if (attributes == 0)
211 printf ("None ");
212 if (attributes & ReadOnly)
213 printf ("ReadOnly ");
214 if (attributes & DontEnum)
215 printf ("DontEnum ");
216 if (attributes & DontDelete)
217 printf ("DontDelete ");
218 if (attributes & Internal)
219 printf ("Internal ");
220 if (attributes & Function)
221 printf ("Function ");
222}
223#endif
224
225void PropertyMap::put(const Identifier &name, ValueImp *value, int attributes)
226{
227 assert(!name.isNull());
228 assert(value != 0);
229
230#if DO_CONSISTENCY_CHECK // speed, why call a stub if we dont need to??
231 checkConsistency();
232#endif
233
234 UString::Rep *rep = name._ustring.rep;
235
236#if DEBUG_PROPERTIES
237 printf("adding property %s, attributes = 0x%08x (", name.ascii(), attributes);
238 printAttributes(attributes);
239 printf(")\n");
240#endif
241
242#if USE_SINGLE_ENTRY
243 if (!_table) {
244 UString::Rep *key = _singleEntry.key;
245 if (key) {
246 if (rep == key) {
247 _singleEntry.value = value;
248 return;
249 }
250 } else {
251 rep->ref();
252 _singleEntry.key = rep;
253 _singleEntry.value = value;
254 _singleEntry.attributes = attributes;
255 checkConsistency();
256 return;
257 }
258 }
259#endif
260 if (!_table || _table->keyCount * 2 >= _table->size)
261 expand();
262 int i = hash(rep);
263#if DUMP_STATISTICS
264 ++numProbes;
265 numCollisions += _table->entries[i].key && _table->entries[i].key != rep;
266#endif
267 while (UString::Rep *key = _table->entries[i].key) {
268 if (rep == key) {
269 // Put a new value in an existing hash table entry.
270 _table->entries[i].value = value;
271 // Attributes are intentionally not updated.
272 return;
273 }
274 i = (i + 1) & _table->sizeMask;
275 }
276
277 // Create a new hash table entry.
278 rep->ref();
279 _table->entries[i].key = rep;
280 _table->entries[i].value = value;
281 _table->entries[i].attributes = attributes;
282 ++_table->keyCount;
283
284 // store insert order
285 _table->indexCount++;
286 _table->hashToIndex[i] = _table->indexCount;
287
288#if DO_CONSISTENCY_CHECK// speed, why call a stub if we dont need to??
289 checkConsistency();
290#endif
291}
292
293inline void PropertyMap::insert(UString::Rep *key, ValueImp *value, int attributes)
294{
295 assert(_table);
296
297 int i = hash(key);
298#if DUMP_STATISTICS
299 ++numProbes;
300 numCollisions += _table->entries[i].key && _table->entries[i].key != key;
301#endif
302 while (_table->entries[i].key)
303 i = (i + 1) & _table->sizeMask;
304
305 _table->entries[i].key = key;
306 _table->entries[i].value = value;
307 _table->entries[i].attributes = attributes;
308}
309
310void PropertyMap::expand()
311{
312#if DO_CONSISTENCY_CHECK// speed, why call a stub if we dont need to??
313 checkConsistency();
314#endif
315 Table *oldTable = _table;
316
317 int oldTableSize = oldTable ? oldTable->size : 0;
318
319 int newTableSize = oldTableSize ? oldTableSize * 2 : 16;
320
321 // Is this realy the best way? wouldnt it be easier to use new/delete on an array instead
322 // and do a pointer in Table to that array, that way we wouldnt need to delete the whole _table
323 // every time we need to expand
324 _table = (Table *)calloc(1, sizeof(Table) + ((newTableSize - 1) * sizeof(Entry)) );
325
326 int *p = new int[newTableSize];
327 for (int i = 0; i < newTableSize; i++)
328 p[i] = 0;
329
330 _table->hashToIndex = p;
331
332 _table->size = newTableSize;
333
334 _table->sizeMask = newTableSize - 1;
335
336 _table->keyCount = oldTable ? oldTable->keyCount : 0;
337
338 _table->indexCount = oldTable ? oldTable->indexCount : 0;
339
340#if USE_SINGLE_ENTRY
341 UString::Rep *key = _singleEntry.key;
342 if (key) {
343 insert(key, _singleEntry.value, _singleEntry.attributes);
344 _table->keyCount++;
345 _singleEntry.key = 0;
346
347 // store sort order
348 // first get the id of newly inserted key, check for trashed hash, then store it
349 int k = hash(key);
350#if DUMP_STATISTICS
351 ++numProbes;
352 numCollisions += _table->entries[k].key && _table->entries[k].key != key;
353#endif
354 while (UString::Rep *newKey = _table->entries[k].key) {
355 if (key == newKey)
356 break;
357 k = (k + 1) & _table->sizeMask;
358 }
359 _table->indexCount++;
360 _table->hashToIndex[k] = _table->indexCount;
361 }
362#endif
363
364 for (int i = 0; i != oldTableSize; ++i) {
365 UString::Rep *key = oldTable->entries[i].key;
366 if (key) {
367 insert(key, oldTable->entries[i].value, oldTable->entries[i].attributes);
368
369 // store sort order
370 // first get the id of newly inserted key, check for trashed hash, then store it
371 int k = hash(key);
372#if DUMP_STATISTICS
373 ++numProbes;
374 numCollisions += _table->entries[k].key && _table->entries[k].key != key;
375#endif
376 while (UString::Rep *newKey = _table->entries[k].key) {
377 if (key == newKey)
378 break;
379 k = (k + 1) & _table->sizeMask;
380 }
381 // store hashindex on the newly inserted entry
382 _table->hashToIndex[k] = oldTable->hashToIndex[i];
383 }
384 }
385
386 if (oldTable){
387 delete [] oldTable->hashToIndex;
388 }
389 free(oldTable);
390
391#if DO_CONSISTENCY_CHECK// speed, why call a stub if we dont need to??
392 checkConsistency();
393#endif
394}
395
396void PropertyMap::remove(const Identifier &name)
397{
398 assert(!name.isNull());
399
400#if DO_CONSISTENCY_CHECK// speed, why call a stub if we dont need to??
401 checkConsistency();
402#endif
403
404 UString::Rep *rep = name._ustring.rep;
405
406 UString::Rep *key;
407
408 if (!_table) {
409#if USE_SINGLE_ENTRY
410 key = _singleEntry.key;
411 if (rep == key) {
412 key->deref();
413 _singleEntry.key = 0;
414 checkConsistency();
415 }
416#endif
417 return;
418 }
419
420 // Find the thing to remove.
421 int i = hash(rep);
422#if DUMP_STATISTICS
423 ++numProbes;
424 numCollisions += _table->entries[i].key && _table->entries[i].key != rep;
425#endif
426 while ((key = _table->entries[i].key)) {
427 if (rep == key)
428 break;
429 i = (i + 1) & _table->sizeMask;
430 }
431
432 if (!key)
433 return;
434
435 // Remove the one key.
436 key->deref();
437 _table->entries[i].key = 0;
438 assert(_table->keyCount >= 1);
439 --_table->keyCount;
440
441 // Reinsert all the items to the right in the same cluster.
442 while (1) {
443 i = (i + 1) & _table->sizeMask;
444 key = _table->entries[i].key;
445 if (!key)
446 break;
447
448 _table->entries[i].key = 0;
449
450 insert(key, _table->entries[i].value, _table->entries[i].attributes);
451
452 // store the index of the new hash
453 int k = hash(key);
454#if DUMP_STATISTICS
455 ++numProbes;
456 numCollisions += _table->entries[k].key && _table->entries[k].key != key;
457#endif
458 while (UString::Rep *newKey = _table->entries[k].key) {
459 if (key == newKey)
460 break;
461 k = (k + 1) & _table->sizeMask;
462 }
463
464 // store hashindex on the newly moved entry
465 _table->hashToIndex[k] = _table->hashToIndex[i];
466 }
467
468#if DO_CONSISTENCY_CHECK// speed, why call a stub if we dont need to??
469 checkConsistency();
470#endif
471}
472
473void PropertyMap::mark() const
474{
475 if (!_table) {
476#if USE_SINGLE_ENTRY
477 if (_singleEntry.key) {
478 ValueImp *v = _singleEntry.value;
479 if (!v->marked())
480 v->mark();
481 }
482#endif
483 return;
484 }
485
486 for (int i = 0; i != _table->size; ++i) {
487 if (_table->entries[i].key) {
488 ValueImp *v = _table->entries[i].value;
489 if (!v->marked())
490 v->mark();
491 }
492 }
493}
494
495void PropertyMap::addEnumerablesToReferenceList(ReferenceList &list, const Object &base) const
496{
497 if (!_table) {
498#if USE_SINGLE_ENTRY
499 UString::Rep *key = _singleEntry.key;
500 if (key && !(_singleEntry.attributes & DontEnum))
501 list.append(Reference(base, Identifier(key)));
502#endif
503 return;
504 }
505
506 // Allocate a buffer to use to sort the keys.
507 int indexSize = _table->indexCount + 1; // indexes is one based
508 UString::Rep **allKeys = new UString::Rep*[indexSize];
509
510 for (int i = 0; i < indexSize; i++)
511 allKeys[i] = NULL;
512
513 // push valid hashes to the array allKeys, using insert order as index.
514 // we need to pass array hashes instead of pointers to keys, because we got
515 // memory corruption sometimes, seems that Identifier in below call deletes the key
516 int size = _table->size;
517 Entry *entries = _table->entries;
518 for (int i = 0; i != size; ++i) {
519 if (entries[i].key && !(entries[i].attributes & DontEnum)) {
520 int idx = _table->hashToIndex[i];
521 if (idx) {
522 allKeys[idx] = entries[i].key;
523 } else { // nonsorted key, failure
524 //cout<<"Error with in KJS property_map.addEnumerablesToReferenceList \nUnsorted key"<<endl;
525 assert(0==1); // allways throw error if get here
526 }
527 }
528 }
529 // Put the keys of the sorted entries into the reference list.
530 for (int i = 0; i < indexSize; ++i) {
531 if (allKeys[i] != NULL){
532 list.append(Reference(base, Identifier(allKeys[i])));
533 }
534 allKeys[i] = NULL; // dont deallocate key by accident, when we delete allKeys
535 }
536
537 // Deallocate the buffer.
538 delete [] allKeys;
539}
540
541void PropertyMap::addSparseArrayPropertiesToReferenceList(ReferenceList &list, const Object &base) const
542{
543 // NOTE: I did'nt add sort in this method because It seems to be referenced in ArrayInstanceImp
544 // only and arrays are sorted by definition, dont need the extra overhead
545 if (!_table) {
546#if USE_SINGLE_ENTRY
547 UString::Rep *key = _singleEntry.key;
548 if (key) {
549 UString k(key);
550 bool fitsInULong;
551 unsigned long i = k.toULong(&fitsInULong);
552 if (fitsInULong && i <= 0xFFFFFFFFU)
553 list.append(Reference(base, Identifier(key)));
554 }
555#endif
556 return;
557 }
558
559 for (int i = 0; i != _table->size; ++i) {
560 UString::Rep *key = _table->entries[i].key;
561 if (key) {
562 UString k(key);
563 bool fitsInULong;
564 unsigned long i = k.toULong(&fitsInULong);
565 if (fitsInULong && i <= 0xFFFFFFFFU)
566 list.append(Reference(base, Identifier(key)));
567 }
568 }
569}
570
571void PropertyMap::save(SavedProperties &p) const
572{
573 int count = 0;
574
575 if (!_table) {
576#if USE_SINGLE_ENTRY
577 if (_singleEntry.key && !(_singleEntry.attributes & (ReadOnly | DontEnum | Function)))
578 ++count;
579#endif
580 } else {
581 for (int i = 0; i != _table->size; ++i)
582 if (_table->entries[i].key && !(_table->entries[i].attributes & (ReadOnly | DontEnum | Function)))
583 ++count;
584 }
585
586 delete [] p._properties;
587
588 p._count = count;
589
590 if (count == 0) {
591 p._properties = 0;
592 return;
593 }
594
595 p._properties = new SavedProperty [count];
596
597 SavedProperty *prop = p._properties;
598
599 if (!_table) {
600#if USE_SINGLE_ENTRY
601 if (_singleEntry.key && !(_singleEntry.attributes & (ReadOnly | DontEnum | Function))) {
602 prop->key = Identifier(_singleEntry.key);
603 prop->value = Value(_singleEntry.value);
604 prop->attributes = _singleEntry.attributes;
605 ++prop;
606 }
607#endif
608 } else {
609 for (int i = 0; i != _table->size; ++i) {
610 if (_table->entries[i].key && !(_table->entries[i].attributes & (ReadOnly | DontEnum | Function))) {
611 prop->key = Identifier(_table->entries[i].key);
612 prop->value = Value(_table->entries[i].value);
613 prop->attributes = _table->entries[i].attributes;
614 ++prop;
615 }
616 }
617 }
618}
619
620void PropertyMap::restore(const SavedProperties &p)
621{
622 for (int i = 0; i != p._count; ++i)
623 put(p._properties[i].key, p._properties[i].value.imp(), p._properties[i].attributes);
624}
625
626#if DO_CONSISTENCY_CHECK
627
628void PropertyMap::checkConsistency()
629{
630 if (!_table)
631 return;
632
633 int count = 0;
634 for (int j = 0; j != _table->size; ++j) {
635 UString::Rep *rep = _table->entries[j].key;
636 if (!rep)
637 continue;
638 int i = hash(rep);
639 while (UString::Rep *key = _table->entries[i].key) {
640 if (rep == key)
641 break;
642 i = (i + 1) & _table->sizeMask;
643 }
644 assert(i == j);
645 assert(_table->hashToIndex[i] > 0);
646 count++;
647 }
648 assert(count == _table->keyCount);
649 assert(_table->size >= 16);
650 assert(_table->sizeMask);
651 assert(_table->size == _table->sizeMask + 1);
652}
653
654#endif // DO_CONSISTENCY_CHECK
655
656} // namespace KJS
TDEStdAccel::key
int key(StdAccel id)
TDEStdAccel::name
TQString name(StdAccel id)
TDEStdAccel::insert
const TDEShortcut & insert()

kjs

Skip menu "kjs"
  • Main Page
  • Class Hierarchy
  • Alphabetical List
  • Class List
  • File List
  • Class Members
  • Related Pages

kjs

Skip menu "kjs"
  • arts
  • dcop
  • dnssd
  • interfaces
  •   kspeech
  •     interface
  •     library
  •   tdetexteditor
  • kate
  • kded
  • kdoctools
  • kimgio
  • kjs
  • libtdemid
  • libtdescreensaver
  • tdeabc
  • tdecmshell
  • tdecore
  • tdefx
  • tdehtml
  • tdeinit
  • tdeio
  •   bookmarks
  •   httpfilter
  •   kpasswdserver
  •   kssl
  •   tdefile
  •   tdeio
  •   tdeioexec
  • tdeioslave
  •   http
  • tdemdi
  •   tdemdi
  • tdenewstuff
  • tdeparts
  • tdeprint
  • tderandr
  • tderesources
  • tdespell2
  • tdesu
  • tdeui
  • tdeunittest
  • tdeutils
  • tdewallet
Generated for kjs by doxygen 1.9.4
This website is maintained by Timothy Pearson.