• 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 
41 namespace KJS {
42 
43 #if DUMP_STATISTICS
44 
45 static int numProbes;
46 static int numCollisions;
47 
48 struct PropertyMapStatisticsExitLogger { ~PropertyMapStatisticsExitLogger(); };
49 
50 static PropertyMapStatisticsExitLogger logger;
51 
52 PropertyMapStatisticsExitLogger::~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 
61 struct 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 
76 class SavedProperty {
77 public:
78  Identifier key;
79  Value value;
80  int attributes;
81 };
82 
83 SavedProperties::SavedProperties() : _count(0), _properties(0) { }
84 
85 SavedProperties::~SavedProperties()
86 {
87  delete [] _properties;
88 }
89 
90 // Algorithm concepts from Algorithms in C++, Sedgewick.
91 
92 PropertyMap::PropertyMap() : _table(0)
93 {
94 }
95 
96 PropertyMap::~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 
119 void 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 
142 inline int PropertyMap::hash(const UString::Rep *s) const
143 {
144  return s->hash() & _table->sizeMask;
145 }
146 
147 ValueImp *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 
179 ValueImp *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
208 static 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 
225 void 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 
293 inline 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 
310 void 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 
396 void 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 
473 void 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 
495 void 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 
541 void 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 
571 void 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 
620 void 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 
628 void 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::insert
const TDEShortcut & insert()
TDEStdAccel::name
TQString name(StdAccel id)

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.1
This website is maintained by Timothy Pearson.