- initialize deletedElementIndex to make the compiler happy
[WebKit-https.git] / JavaScriptCore / kjs / property_map.cpp
1 /*
2  *  This file is part of the KDE libraries
3  *  Copyright (C) 2004 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., 59 Temple Place - Suite 330,
18  *  Boston, MA 02111-1307, USA.
19  *
20  */
21
22 #include "property_map.h"
23
24 #include "object.h"
25 #include "protect.h"
26 #include "reference_list.h"
27
28 #define DEBUG_PROPERTIES 0
29 #define DO_CONSISTENCY_CHECK 0
30 #define DUMP_STATISTICS 0
31 #define USE_SINGLE_ENTRY 1
32
33 // At the time I added USE_SINGLE_ENTRY, the optimization still gave a 1.5%
34 // performance boost to the iBench JavaScript benchmark so I didn't remove it.
35
36 // FIXME: _singleEntry.index is unused.
37
38 #if !DO_CONSISTENCY_CHECK
39 #define checkConsistency() ((void)0)
40 #endif
41
42 namespace KJS {
43
44 // Choose a number for the following so that most property maps are smaller,
45 // but it's not going to blow out the stack to allocate this number of pointers.
46 const int smallMapThreshold = 1024;
47
48 #if DUMP_STATISTICS
49
50 static int numProbes;
51 static int numCollisions;
52 static int numRehashes;
53 static int numRemoves;
54
55 struct PropertyMapStatisticsExitLogger { ~PropertyMapStatisticsExitLogger(); };
56
57 static PropertyMapStatisticsExitLogger logger;
58
59 PropertyMapStatisticsExitLogger::~PropertyMapStatisticsExitLogger()
60 {
61     printf("\nKJS::PropertyMap statistics\n\n");
62     printf("%d probes\n", numProbes);
63     printf("%d collisions (%.1f%%)\n", numCollisions, 100.0 * numCollisions / numProbes);
64     printf("%d rehashes\n", numRehashes);
65     printf("%d removes\n", numRemoves);
66 }
67
68 #endif
69
70 // lastIndexUsed is an ever-increasing index used to identify the order items
71 // were inserted into the property map. It's vital that addEnumerablesToReferenceList
72 // return the properties in the order they were added for compatibility with other
73 // browsers' JavaScript implementations.
74 struct PropertyMapHashTable
75 {
76     int sizeMask;
77     int size;
78     int keyCount;
79     int sentinelCount;
80     int lastIndexUsed;
81     PropertyMapHashTableEntry entries[1];
82 };
83
84 class SavedProperty {
85 public:
86     Identifier key;
87     ProtectedValue value;
88     int attributes;
89 };
90
91 SavedProperties::SavedProperties() : _count(0), _properties(0) { }
92
93 SavedProperties::~SavedProperties()
94 {
95     delete [] _properties;
96 }
97
98 // Algorithm concepts from Algorithms in C++, Sedgewick.
99
100 PropertyMap::PropertyMap() : _table(0)
101 {
102 }
103
104 PropertyMap::~PropertyMap()
105 {
106     if (!_table) {
107 #if USE_SINGLE_ENTRY
108         UString::Rep *key = _singleEntry.key;
109         if (key)
110             key->deref();
111 #endif
112         return;
113     }
114     
115     for (int i = 0; i < _table->size; i++) {
116         UString::Rep *key = _table->entries[i].key;
117         if (key)
118             key->deref();
119     }
120     free(_table);
121 }
122
123 void PropertyMap::clear()
124 {
125     if (!_table) {
126 #if USE_SINGLE_ENTRY
127         UString::Rep *key = _singleEntry.key;
128         if (key) {
129             key->deref();
130             _singleEntry.key = 0;
131         }
132 #endif
133         return;
134     }
135
136     for (int i = 0; i < _table->size; i++) {
137         UString::Rep *key = _table->entries[i].key;
138         if (key) {
139             key->deref();
140             _table->entries[i].key = 0;
141         }
142     }
143     _table->keyCount = 0;
144     _table->sentinelCount = 0;
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     unsigned h = rep->hash();
165     int i = h & _table->sizeMask;
166     int k = 0;
167 #if DUMP_STATISTICS
168     ++numProbes;
169     numCollisions += _table->entries[i].key && _table->entries[i].key != rep;
170 #endif
171     while (UString::Rep *key = _table->entries[i].key) {
172         if (rep == key) {
173             attributes = _table->entries[i].attributes;
174             return _table->entries[i].value;
175         }
176         if (k == 0)
177             k = 1 | (h % _table->sizeMask);
178         i = (i + k) & _table->sizeMask;
179 #if DUMP_STATISTICS
180         ++numRehashes;
181 #endif
182     }
183     return 0;
184 }
185
186 ValueImp *PropertyMap::get(const Identifier &name) const
187 {
188     assert(!name.isNull());
189     
190     UString::Rep *rep = name._ustring.rep;
191
192     if (!_table) {
193 #if USE_SINGLE_ENTRY
194         UString::Rep *key = _singleEntry.key;
195         if (rep == key)
196             return _singleEntry.value;
197 #endif
198         return 0;
199     }
200     
201     unsigned h = rep->hash();
202     int i = h & _table->sizeMask;
203     int k = 0;
204 #if DUMP_STATISTICS
205     ++numProbes;
206     numCollisions += _table->entries[i].key && _table->entries[i].key != rep;
207 #endif
208     while (UString::Rep *key = _table->entries[i].key) {
209         if (rep == key)
210             return _table->entries[i].value;
211         if (k == 0)
212             k = 1 | (h % _table->sizeMask);
213         i = (i + k) & _table->sizeMask;
214 #if DUMP_STATISTICS
215         ++numRehashes;
216 #endif
217     }
218     return 0;
219 }
220
221 #if DEBUG_PROPERTIES
222 static void printAttributes(int attributes)
223 {
224     if (attributes == 0)
225         printf("None");
226     else {
227         if (attributes & ReadOnly)
228             printf("ReadOnly ");
229         if (attributes & DontEnum)
230             printf("DontEnum ");
231         if (attributes & DontDelete)
232             printf("DontDelete ");
233         if (attributes & Internal)
234             printf("Internal ");
235         if (attributes & Function)
236             printf("Function ");
237     }
238 }
239 #endif
240
241 void PropertyMap::put(const Identifier &name, ValueImp *value, int attributes)
242 {
243     assert(!name.isNull());
244     assert(value != 0);
245     
246     checkConsistency();
247
248     UString::Rep *rep = name._ustring.rep;
249     
250 #if DEBUG_PROPERTIES
251     printf("adding property %s, attributes = 0x%08x (", name.ascii(), attributes);
252     printAttributes(attributes);
253     printf(")\n");
254 #endif
255     
256 #if USE_SINGLE_ENTRY
257     if (!_table) {
258         UString::Rep *key = _singleEntry.key;
259         if (key) {
260             if (rep == key) {
261                 _singleEntry.value = value;
262                 return;
263             }
264         } else {
265             rep->ref();
266             _singleEntry.key = rep;
267             _singleEntry.value = value;
268             _singleEntry.attributes = attributes;
269             checkConsistency();
270             return;
271         }
272     }
273 #endif
274
275     if (!_table || _table->keyCount * 2 >= _table->size)
276         expand();
277     
278     unsigned h = rep->hash();
279     int i = h & _table->sizeMask;
280     int k = 0;
281     bool foundDeletedElement = false;
282     int deletedElementIndex = 0;    /* initialize to make the compiler happy */
283 #if DUMP_STATISTICS
284     ++numProbes;
285     numCollisions += _table->entries[i].key && _table->entries[i].key != rep;
286 #endif
287     while (UString::Rep *key = _table->entries[i].key) {
288         if (rep == key) {
289             // Put a new value in an existing hash table entry.
290             _table->entries[i].value = value;
291             // Attributes are intentionally not updated.
292             return;
293         }
294         // If we find the deleted-element sentinel, remember it for use later.
295         if (key == &UString::Rep::null && !foundDeletedElement) {
296             foundDeletedElement = true;
297             deletedElementIndex = i;
298         }
299         if (k == 0)
300             k = 1 | (h % _table->sizeMask);
301         i = (i + k) & _table->sizeMask;
302 #if DUMP_STATISTICS
303         ++numRehashes;
304 #endif
305     }
306
307     // Use either the deleted element or the 0 at the end of the chain.
308     if (foundDeletedElement) {
309         i = deletedElementIndex;
310         _table->entries[i].key->deref();
311         --_table->sentinelCount;
312     }
313
314     // Create a new hash table entry.
315     rep->ref();
316     _table->entries[i].key = rep;
317     _table->entries[i].value = value;
318     _table->entries[i].attributes = attributes;
319     _table->entries[i].index = ++_table->lastIndexUsed;
320     ++_table->keyCount;
321
322     checkConsistency();
323 }
324
325 void PropertyMap::insert(UString::Rep *key, ValueImp *value, int attributes, int index)
326 {
327     assert(_table);
328
329     unsigned h = key->hash();
330     int i = h & _table->sizeMask;
331     int k = 0;
332 #if DUMP_STATISTICS
333     ++numProbes;
334     numCollisions += _table->entries[i].key && _table->entries[i].key != key;
335 #endif
336     while (_table->entries[i].key) {
337         assert(_table->entries[i].key != &UString::Rep::null);
338         if (k == 0)
339             k = 1 | (h % _table->sizeMask);
340         i = (i + k) & _table->sizeMask;
341 #if DUMP_STATISTICS
342         ++numRehashes;
343 #endif
344     }
345     
346     _table->entries[i].key = key;
347     _table->entries[i].value = value;
348     _table->entries[i].attributes = attributes;
349     _table->entries[i].index = index;
350 }
351
352 void PropertyMap::expand()
353 {
354     Table *oldTable = _table;
355     int oldTableSize = oldTable ? oldTable->size : 0;    
356     rehash(oldTableSize ? oldTableSize * 2 : 16);
357 }
358
359 void PropertyMap::rehash()
360 {
361     assert(_table);
362     assert(_table->size);
363     rehash(_table->size);
364 }
365
366 void PropertyMap::rehash(int newTableSize)
367 {
368     checkConsistency();
369     
370     Table *oldTable = _table;
371     int oldTableSize = oldTable ? oldTable->size : 0;
372     int oldTableKeyCount = oldTable ? oldTable->keyCount : 0;
373     
374     _table = (Table *)calloc(1, sizeof(Table) + (newTableSize - 1) * sizeof(Entry) );
375     _table->size = newTableSize;
376     _table->sizeMask = newTableSize - 1;
377     _table->keyCount = oldTableKeyCount;
378
379 #if USE_SINGLE_ENTRY
380     UString::Rep *key = _singleEntry.key;
381     if (key) {
382         insert(key, _singleEntry.value, _singleEntry.attributes, 0);
383         _singleEntry.key = 0;
384         // update the count, because single entries don't count towards
385         // the table key count
386         ++_table->keyCount;
387         assert(_table->keyCount == 1);
388     }
389 #endif
390     
391     int lastIndexUsed = 0;
392     for (int i = 0; i != oldTableSize; ++i) {
393         Entry &entry = oldTable->entries[i];
394         UString::Rep *key = entry.key;
395         if (key) {
396             // Don't copy deleted-element sentinels.
397             if (key == &UString::Rep::null)
398                 key->deref();
399             else {
400                 int index = entry.index;
401                 lastIndexUsed = MAX(index, lastIndexUsed);
402                 insert(key, entry.value, entry.attributes, index);
403             }
404         }
405     }
406     _table->lastIndexUsed = lastIndexUsed;
407
408     free(oldTable);
409
410     checkConsistency();
411 }
412
413 void PropertyMap::remove(const Identifier &name)
414 {
415     assert(!name.isNull());
416     
417     checkConsistency();
418
419     UString::Rep *rep = name._ustring.rep;
420
421     UString::Rep *key;
422
423     if (!_table) {
424 #if USE_SINGLE_ENTRY
425         key = _singleEntry.key;
426         if (rep == key) {
427             key->deref();
428             _singleEntry.key = 0;
429             checkConsistency();
430         }
431 #endif
432         return;
433     }
434
435     // Find the thing to remove.
436     unsigned h = rep->hash();
437     int i = h & _table->sizeMask;
438     int k = 0;
439 #if DUMP_STATISTICS
440     ++numProbes;
441     ++numRemoves;
442     numCollisions += _table->entries[i].key && _table->entries[i].key != rep;
443 #endif
444     while ((key = _table->entries[i].key)) {
445         if (rep == key)
446             break;
447         if (k == 0)
448             k = 1 | (h % _table->sizeMask);
449         i = (i + k) & _table->sizeMask;
450 #if DUMP_STATISTICS
451         ++numRehashes;
452 #endif
453     }
454     if (!key)
455         return;
456     
457     // Replace this one element with the deleted sentinel,
458     // &UString::Rep::null; also set value to 0 and attributes to DontEnum
459     // to help callers that iterate all keys not have to check for the sentinel.
460     key->deref();
461     key = &UString::Rep::null;
462     key->ref();
463     _table->entries[i].key = key;
464     _table->entries[i].value = 0;
465     _table->entries[i].attributes = DontEnum;
466     assert(_table->keyCount >= 1);
467     --_table->keyCount;
468     ++_table->sentinelCount;
469     
470     if (_table->sentinelCount * 4 >= _table->size)
471         rehash();
472
473     checkConsistency();
474 }
475
476 void PropertyMap::mark() const
477 {
478     if (!_table) {
479 #if USE_SINGLE_ENTRY
480         if (_singleEntry.key) {
481             ValueImp *v = _singleEntry.value;
482             if (!v->marked())
483                 v->mark();
484         }
485 #endif
486         return;
487     }
488
489     for (int i = 0; i != _table->size; ++i) {
490         UString::Rep *key = _table->entries[i].key;
491         if (key) {
492             ValueImp *v = _table->entries[i].value;
493             // Check v against 0 to handle deleted elements
494             // without comparing key to UString::Rep::null.
495             if (v && !v->marked())
496                 v->mark();
497         }
498     }
499 }
500
501 static int comparePropertyMapEntryIndices(const void *a, const void *b)
502 {
503     int ia = static_cast<PropertyMapHashTableEntry * const *>(a)[0]->index;
504     int ib = static_cast<PropertyMapHashTableEntry * const *>(b)[0]->index;
505     if (ia < ib)
506         return -1;
507     if (ia > ib)
508         return +1;
509     return 0;
510 }
511
512 void PropertyMap::addEnumerablesToReferenceList(ReferenceList &list, const Object &base) const
513 {
514     if (!_table) {
515 #if USE_SINGLE_ENTRY
516         UString::Rep *key = _singleEntry.key;
517         if (key && !(_singleEntry.attributes & DontEnum))
518             list.append(Reference(base, Identifier(key)));
519 #endif
520         return;
521     }
522
523     // Allocate a buffer to use to sort the keys.
524     Entry *fixedSizeBuffer[smallMapThreshold];
525     Entry **sortedEnumerables;
526     if (_table->keyCount <= smallMapThreshold)
527         sortedEnumerables = fixedSizeBuffer;
528     else
529         sortedEnumerables = new Entry *[_table->keyCount];
530
531     // Get pointers to the enumerable entries in the buffer.
532     Entry **p = sortedEnumerables;
533     for (int i = 0; i != _table->size; ++i) {
534         Entry *e = &_table->entries[i];
535         if (e->key && !(e->attributes & DontEnum))
536             *p++ = e;
537     }
538
539     // Sort the entries by index.
540     qsort(sortedEnumerables, p - sortedEnumerables, sizeof(sortedEnumerables[0]), comparePropertyMapEntryIndices);
541
542     // Put the keys of the sorted entries into the reference list.
543     Entry **q = sortedEnumerables;
544     while (q != p)
545         list.append(Reference(base, Identifier((*q++)->key)));
546
547     // Deallocate the buffer.
548     if (sortedEnumerables != fixedSizeBuffer)
549         delete [] sortedEnumerables;
550 }
551
552 void PropertyMap::addSparseArrayPropertiesToReferenceList(ReferenceList &list, const Object &base) const
553 {
554     if (!_table) {
555 #if USE_SINGLE_ENTRY
556         UString::Rep *key = _singleEntry.key;
557         if (key) {
558             UString k(key);
559             bool fitsInUInt32;
560             k.toUInt32(&fitsInUInt32);
561             if (fitsInUInt32)
562                 list.append(Reference(base, Identifier(key)));
563         }
564 #endif
565         return;
566     }
567
568     for (int i = 0; i != _table->size; ++i) {
569         UString::Rep *key = _table->entries[i].key;
570         if (key && key != &UString::Rep::null)
571         {
572             UString k(key);
573             bool fitsInUInt32;
574             k.toUInt32(&fitsInUInt32);
575             if (fitsInUInt32)
576                 list.append(Reference(base, Identifier(key)));
577         }
578     }
579 }
580
581 void PropertyMap::save(SavedProperties &p) const
582 {
583     int count = 0;
584
585     if (!_table) {
586 #if USE_SINGLE_ENTRY
587         if (_singleEntry.key && !(_singleEntry.attributes & (ReadOnly | Function)))
588             ++count;
589 #endif
590     } else {
591         for (int i = 0; i != _table->size; ++i)
592             if (_table->entries[i].key && !(_table->entries[i].attributes & (ReadOnly | Function)))
593                 ++count;
594     }
595
596     delete [] p._properties;
597
598     p._count = count;
599
600     if (count == 0) {
601         p._properties = 0;
602         return;
603     }
604     
605     p._properties = new SavedProperty [count];
606     
607     SavedProperty *prop = p._properties;
608     
609     if (!_table) {
610 #if USE_SINGLE_ENTRY
611         if (_singleEntry.key && !(_singleEntry.attributes & (ReadOnly | Function))) {
612             prop->key = Identifier(_singleEntry.key);
613             prop->value = Value(_singleEntry.value);
614             prop->attributes = _singleEntry.attributes;
615             ++prop;
616         }
617 #endif
618     } else {
619         // Save in the right order so we don't lose the order.
620         // Another possibility would be to save the indices.
621
622         // Allocate a buffer to use to sort the keys.
623         Entry *fixedSizeBuffer[smallMapThreshold];
624         Entry **sortedEntries;
625         if (count <= smallMapThreshold)
626             sortedEntries = fixedSizeBuffer;
627         else
628             sortedEntries = new Entry *[count];
629
630         // Get pointers to the entries in the buffer.
631         Entry **p = sortedEntries;
632         for (int i = 0; i != _table->size; ++i) {
633             Entry *e = &_table->entries[i];
634             if (e->key && !(e->attributes & (ReadOnly | Function)))
635                 *p++ = e;
636         }
637         assert(p - sortedEntries == count);
638
639         // Sort the entries by index.
640         qsort(sortedEntries, p - sortedEntries, sizeof(sortedEntries[0]), comparePropertyMapEntryIndices);
641
642         // Put the sorted entries into the saved properties list.
643         Entry **q = sortedEntries;
644         while (q != p) {
645             Entry *e = *q++;
646             prop->key = Identifier(e->key);
647             prop->value = Value(e->value);
648             prop->attributes = e->attributes;
649             ++prop;
650         }
651
652         // Deallocate the buffer.
653         if (sortedEntries != fixedSizeBuffer)
654             delete [] sortedEntries;
655     }
656 }
657
658 void PropertyMap::restore(const SavedProperties &p)
659 {
660     for (int i = 0; i != p._count; ++i)
661         put(p._properties[i].key, p._properties[i].value.imp(), p._properties[i].attributes);
662 }
663
664 #if DO_CONSISTENCY_CHECK
665
666 void PropertyMap::checkConsistency()
667 {
668     if (!_table)
669         return;
670
671     int count = 0;
672     int sentinelCount = 0;
673     for (int j = 0; j != _table->size; ++j) {
674         UString::Rep *rep = _table->entries[j].key;
675         if (!rep)
676             continue;
677         if (rep == &UString::Rep::null) {
678             ++sentinelCount;
679             continue;
680         }
681         unsigned h = rep->hash();
682         int i = h & _table->sizeMask;
683         int k = 0;
684         while (UString::Rep *key = _table->entries[i].key) {
685             if (rep == key)
686                 break;
687             if (k == 0)
688                 k = 1 | (h % _table->sizeMask);
689             i = (i + k) & _table->sizeMask;
690         }
691         assert(i == j);
692         ++count;
693     }
694     assert(count == _table->keyCount);
695     assert(sentinelCount == _table->sentinelCount);
696     assert(_table->size >= 16);
697     assert(_table->sizeMask);
698     assert(_table->size == _table->sizeMask + 1);
699 }
700
701 #endif // DO_CONSISTENCY_CHECK
702
703 } // namespace KJS