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