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