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