fa0f15261b7fc80e5f32499e23e1923a36a4ec57
[WebKit.git] / JavaScriptCore / kjs / PropertyMap.cpp
1 /*
2  *  Copyright (C) 2004, 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
3  *
4  *  This library is free software; you can redistribute it and/or
5  *  modify it under the terms of the GNU Library General Public
6  *  License as published by the Free Software Foundation; either
7  *  version 2 of the License, or (at your option) any later version.
8  *
9  *  This library is distributed in the hope that it will be useful,
10  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
11  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12  *  Library General Public License for more details.
13  *
14  *  You should have received a copy of the GNU Library General Public License
15  *  along with this library; see the file COPYING.LIB.  If not, write to
16  *  the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
17  *  Boston, MA 02110-1301, USA.
18  *
19  */
20
21 #include "config.h"
22 #include "PropertyMap.h"
23
24 #include "JSObject.h"
25 #include "PropertyNameArray.h"
26 #include "protect.h"
27 #include <algorithm>
28 #include <wtf/Assertions.h>
29 #include <wtf/FastMalloc.h>
30 #include <wtf/HashTable.h>
31 #include <wtf/Vector.h>
32
33 using std::max;
34 using WTF::doubleHash;
35
36 #ifndef NDEBUG
37 #define DO_PROPERTYMAP_CONSTENCY_CHECK 0
38 #define DUMP_PROPERTYMAP_STATS 0
39 #else
40 #define DO_PROPERTYMAP_CONSTENCY_CHECK 0
41 #define DUMP_PROPERTYMAP_STATS 0
42 #endif
43
44 namespace JSC {
45
46 // Choose a number for the following so that most property maps are smaller,
47 // but it's not going to blow out the stack to allocate this number of pointers.
48 static const int smallMapThreshold = 1024;
49
50 // The point at which the function call overhead of the qsort implementation
51 // becomes small compared to the inefficiency of insertion sort.
52 static const unsigned tinyMapThreshold = 20;
53
54 #if DUMP_PROPERTYMAP_STATS
55
56 static int numProbes;
57 static int numCollisions;
58 static int numRehashes;
59 static int numRemoves;
60
61 struct PropertyMapStatisticsExitLogger {
62     ~PropertyMapStatisticsExitLogger();
63 };
64
65 static PropertyMapStatisticsExitLogger logger;
66
67 PropertyMapStatisticsExitLogger::~PropertyMapStatisticsExitLogger()
68 {
69     printf("\nJSC::PropertyMap statistics\n\n");
70     printf("%d probes\n", numProbes);
71     printf("%d collisions (%.1f%%)\n", numCollisions, 100.0 * numCollisions / numProbes);
72     printf("%d rehashes\n", numRehashes);
73     printf("%d removes\n", numRemoves);
74 }
75
76 #endif
77
78 static const unsigned emptyEntryIndex = 0;
79 static const unsigned deletedSentinelIndex = 1;
80
81 #if !DO_PROPERTYMAP_CONSTENCY_CHECK
82
83 inline void PropertyMap::checkConsistency(PropertyStorage&)
84 {
85 }
86
87 #endif
88
89 PropertyMap& PropertyMap::operator=(const PropertyMap& other)
90 {
91     if (other.m_table) {
92         size_t tableSize = Table::allocationSize(other.m_table->size);
93         m_table = static_cast<Table*>(fastMalloc(tableSize));
94         memcpy(m_table, other.m_table, tableSize);
95
96         unsigned entryCount = m_table->keyCount + m_table->deletedSentinelCount;
97         for (unsigned i = 1; i <= entryCount; ++i) {
98             if (UString::Rep* key = m_table->entries()[i].key)
99                 key->ref();
100         }
101     }
102
103     m_getterSetterFlag = other.m_getterSetterFlag;
104     return *this;
105 }
106
107 PropertyMap::~PropertyMap()
108 {
109     if (!m_table)
110         return;
111
112     unsigned entryCount = m_table->keyCount + m_table->deletedSentinelCount;
113     for (unsigned i = 1; i <= entryCount; i++) {
114         if (UString::Rep* key = m_table->entries()[i].key)
115             key->deref();
116     }
117     fastFree(m_table);
118 }
119
120 void PropertyMap::put(const Identifier& propertyName, JSValue* value, unsigned attributes, bool checkReadOnly, JSObject* slotBase, PutPropertySlot& slot, PropertyStorage& propertyStorage)
121 {
122     ASSERT(!propertyName.isNull());
123     ASSERT(value);
124
125     checkConsistency(propertyStorage);
126
127     UString::Rep* rep = propertyName._ustring.rep();
128
129     if (!m_table)
130         expand(propertyStorage);
131
132     // FIXME: Consider a fast case for tables with no deleted sentinels.
133
134     unsigned i = rep->computedHash();
135     unsigned k = 0;
136     bool foundDeletedElement = false;
137     unsigned deletedElementIndex = 0; // initialize to make the compiler happy
138
139 #if DUMP_PROPERTYMAP_STATS
140     ++numProbes;
141 #endif
142
143     while (1) {
144         unsigned entryIndex = m_table->entryIndices[i & m_table->sizeMask];
145         if (entryIndex == emptyEntryIndex)
146             break;
147
148         if (m_table->entries()[entryIndex - 1].key == rep) {
149             if (checkReadOnly && (m_table->entries()[entryIndex - 1].attributes & ReadOnly))
150                 return;
151             // Put a new value in an existing hash table entry.
152             propertyStorage[entryIndex - 2] = value;
153             // Attributes are intentionally not updated.
154             slot.setExistingProperty(slotBase, entryIndex - 2);
155             return;
156         } else if (entryIndex == deletedSentinelIndex) {
157             // If we find a deleted-element sentinel, remember it for use later.
158             if (!foundDeletedElement) {
159                 foundDeletedElement = true;
160                 deletedElementIndex = i;
161             }
162         }
163
164         if (k == 0) {
165             k = 1 | doubleHash(rep->computedHash());
166 #if DUMP_PROPERTYMAP_STATS
167             ++numCollisions;
168 #endif
169         }
170
171         i += k;
172
173 #if DUMP_PROPERTYMAP_STATS
174         ++numRehashes;
175 #endif
176     }
177
178     // Figure out which entry to use.
179     unsigned entryIndex = m_table->keyCount + m_table->deletedSentinelCount + 2;
180     if (foundDeletedElement) {
181         i = deletedElementIndex;
182         --m_table->deletedSentinelCount;
183
184         // Since we're not making the table bigger, we can't use the entry one past
185         // the end that we were planning on using, so search backwards for the empty
186         // slot that we can use. We know it will be there because we did at least one
187         // deletion in the past that left an entry empty.
188         while (m_table->entries()[--entryIndex - 1].key) { }
189     }
190
191     // Create a new hash table entry.
192     m_table->entryIndices[i & m_table->sizeMask] = entryIndex;
193
194     // Create a new hash table entry.
195     rep->ref();
196     m_table->entries()[entryIndex - 1].key = rep;
197     m_table->entries()[entryIndex - 1].attributes = attributes;
198     m_table->entries()[entryIndex - 1].index = ++m_table->lastIndexUsed;
199     ++m_table->keyCount;
200
201     propertyStorage[entryIndex - 2] = value;
202
203     if ((m_table->keyCount + m_table->deletedSentinelCount) * 2 >= m_table->size)
204         expand(propertyStorage);
205
206     checkConsistency(propertyStorage);
207     slot.setNewProperty(slotBase, entryIndex - 2);
208 }
209
210 void PropertyMap::remove(const Identifier& propertyName, PropertyStorage& propertyStorage)
211 {
212     ASSERT(!propertyName.isNull());
213
214     checkConsistency(propertyStorage);
215
216     UString::Rep* rep = propertyName._ustring.rep();
217
218     if (!m_table)
219         return;
220
221 #if DUMP_PROPERTYMAP_STATS
222     ++numProbes;
223     ++numRemoves;
224 #endif
225
226     // Find the thing to remove.
227     unsigned i = rep->computedHash();
228     unsigned k = 0;
229     unsigned entryIndex;
230     UString::Rep* key = 0;
231     while (1) {
232         entryIndex = m_table->entryIndices[i & m_table->sizeMask];
233         if (entryIndex == emptyEntryIndex)
234             return;
235
236         key = m_table->entries()[entryIndex - 1].key;
237         if (rep == key)
238             break;
239
240         if (k == 0) {
241             k = 1 | doubleHash(rep->computedHash());
242 #if DUMP_PROPERTYMAP_STATS
243             ++numCollisions;
244 #endif
245         }
246
247         i += k;
248
249 #if DUMP_PROPERTYMAP_STATS
250         ++numRehashes;
251 #endif
252     }
253
254     // Replace this one element with the deleted sentinel. Also clear out
255     // the entry so we can iterate all the entries as needed.
256     m_table->entryIndices[i & m_table->sizeMask] = deletedSentinelIndex;
257     key->deref();
258     m_table->entries()[entryIndex - 1].key = 0;
259     m_table->entries()[entryIndex - 1].attributes = 0;
260
261     propertyStorage[entryIndex - 2] = jsUndefined();
262
263     ASSERT(m_table->keyCount >= 1);
264     --m_table->keyCount;
265     ++m_table->deletedSentinelCount;
266
267     if (m_table->deletedSentinelCount * 4 >= m_table->size)
268         rehash(propertyStorage);
269
270     checkConsistency(propertyStorage);
271 }
272
273 size_t PropertyMap::getOffset(const Identifier& propertyName)
274 {
275     ASSERT(!propertyName.isNull());
276
277     if (!m_table)
278         return WTF::notFound;
279
280     UString::Rep* rep = propertyName._ustring.rep();
281
282     unsigned i = rep->computedHash();
283
284 #if DUMP_PROPERTYMAP_STATS
285     ++numProbes;
286 #endif
287
288     unsigned entryIndex = m_table->entryIndices[i & m_table->sizeMask];
289     if (entryIndex == emptyEntryIndex)
290         return WTF::notFound;
291
292     if (rep == m_table->entries()[entryIndex - 1].key)
293         return entryIndex - 2;
294
295 #if DUMP_PROPERTYMAP_STATS
296     ++numCollisions;
297 #endif
298
299     unsigned k = 1 | doubleHash(rep->computedHash());
300
301     while (1) {
302         i += k;
303
304 #if DUMP_PROPERTYMAP_STATS
305         ++numRehashes;
306 #endif
307
308         entryIndex = m_table->entryIndices[i & m_table->sizeMask];
309         if (entryIndex == emptyEntryIndex)
310             return WTF::notFound;
311
312         if (rep == m_table->entries()[entryIndex - 1].key)
313             return entryIndex - 2;
314     }
315 }
316
317 size_t PropertyMap::getOffset(const Identifier& propertyName, unsigned& attributes)
318 {
319     ASSERT(!propertyName.isNull());
320
321     if (!m_table)
322         return WTF::notFound;
323
324     UString::Rep* rep = propertyName._ustring.rep();
325
326     unsigned i = rep->computedHash();
327
328 #if DUMP_PROPERTYMAP_STATS
329     ++numProbes;
330 #endif
331
332     unsigned entryIndex = m_table->entryIndices[i & m_table->sizeMask];
333     if (entryIndex == emptyEntryIndex)
334         return WTF::notFound;
335
336     if (rep == m_table->entries()[entryIndex - 1].key) {
337         attributes = m_table->entries()[entryIndex - 1].attributes;
338         return entryIndex - 2;
339     }
340
341 #if DUMP_PROPERTYMAP_STATS
342     ++numCollisions;
343 #endif
344
345     unsigned k = 1 | doubleHash(rep->computedHash());
346
347     while (1) {
348         i += k;
349
350 #if DUMP_PROPERTYMAP_STATS
351         ++numRehashes;
352 #endif
353
354         entryIndex = m_table->entryIndices[i & m_table->sizeMask];
355         if (entryIndex == emptyEntryIndex)
356             return WTF::notFound;
357
358         if (rep == m_table->entries()[entryIndex - 1].key) {
359             attributes = m_table->entries()[entryIndex - 1].attributes;
360             return entryIndex - 2;
361         }
362     }
363 }
364
365 void PropertyMap::insert(const Entry& entry, JSValue* value, PropertyStorage& propertyStorage)
366 {
367     ASSERT(m_table);
368
369     unsigned i = entry.key->computedHash();
370     unsigned k = 0;
371
372 #if DUMP_PROPERTYMAP_STATS
373     ++numProbes;
374 #endif
375
376     while (1) {
377         unsigned entryIndex = m_table->entryIndices[i & m_table->sizeMask];
378         if (entryIndex == emptyEntryIndex)
379             break;
380
381         if (k == 0) {
382             k = 1 | doubleHash(entry.key->computedHash());
383 #if DUMP_PROPERTYMAP_STATS
384             ++numCollisions;
385 #endif
386         }
387
388         i += k;
389
390 #if DUMP_PROPERTYMAP_STATS
391         ++numRehashes;
392 #endif
393     }
394
395     unsigned entryIndex = m_table->keyCount + 2;
396     m_table->entryIndices[i & m_table->sizeMask] = entryIndex;
397     m_table->entries()[entryIndex - 1] = entry;
398
399     propertyStorage[entryIndex - 2] = value;
400
401     ++m_table->keyCount;
402 }
403
404 void PropertyMap::expand(PropertyStorage& propertyStorage)
405 {
406     if (!m_table)
407         createTable(propertyStorage);
408     else
409         rehash(m_table->size * 2, propertyStorage);
410 }
411
412 void PropertyMap::rehash(PropertyStorage& propertyStorage)
413 {
414     ASSERT(m_table);
415     ASSERT(m_table->size);
416     rehash(m_table->size, propertyStorage);
417 }
418
419 void PropertyMap::createTable(PropertyStorage& propertyStorage)
420 {
421     const unsigned newTableSize = 16;
422
423     ASSERT(!m_table);
424
425     checkConsistency(propertyStorage);
426
427     m_table = static_cast<Table*>(fastZeroedMalloc(Table::allocationSize(newTableSize)));
428     m_table->size = newTableSize;
429     m_table->sizeMask = newTableSize - 1;
430
431     checkConsistency(propertyStorage);
432 }
433
434 void PropertyMap::rehash(unsigned newTableSize, PropertyStorage& propertyStorage)
435 {
436     ASSERT(m_table);
437
438     checkConsistency(propertyStorage);
439
440     Table* oldTable = m_table;
441     JSValue** oldPropertStorage = propertyStorage;
442
443     m_table = static_cast<Table*>(fastZeroedMalloc(Table::allocationSize(newTableSize)));
444     m_table->size = newTableSize;
445     m_table->sizeMask = newTableSize - 1;
446
447     propertyStorage = new JSValue*[m_table->size];
448
449     unsigned lastIndexUsed = 0;
450     unsigned entryCount = oldTable->keyCount + oldTable->deletedSentinelCount;
451     for (unsigned i = 1; i <= entryCount; ++i) {
452         if (oldTable->entries()[i].key) {
453             lastIndexUsed = max(oldTable->entries()[i].index, lastIndexUsed);
454             insert(oldTable->entries()[i], oldPropertStorage[i - 1], propertyStorage);
455         }
456     }
457     m_table->lastIndexUsed = lastIndexUsed;
458
459     fastFree(oldTable);
460     delete [] oldPropertStorage;
461
462     checkConsistency(propertyStorage);
463 }
464
465 static int comparePropertyMapEntryIndices(const void* a, const void* b)
466 {
467     unsigned ia = static_cast<PropertyMapEntry* const*>(a)[0]->index;
468     unsigned ib = static_cast<PropertyMapEntry* const*>(b)[0]->index;
469     if (ia < ib)
470         return -1;
471     if (ia > ib)
472         return +1;
473     return 0;
474 }
475
476 void PropertyMap::getEnumerablePropertyNames(PropertyNameArray& propertyNames) const
477 {
478     if (!m_table)
479         return;
480
481     if (m_table->keyCount < tinyMapThreshold) {
482         Entry* a[tinyMapThreshold];
483         int i = 0;
484         unsigned entryCount = m_table->keyCount + m_table->deletedSentinelCount;
485         for (unsigned k = 1; k <= entryCount; k++) {
486             if (m_table->entries()[k].key && !(m_table->entries()[k].attributes & DontEnum)) {
487                 Entry* value = &m_table->entries()[k];
488                 int j;
489                 for (j = i - 1; j >= 0 && a[j]->index > value->index; --j)
490                     a[j + 1] = a[j];
491                 a[j + 1] = value;
492                 ++i;
493             }
494         }
495         if (!propertyNames.size()) {
496             for (int k = 0; k < i; ++k)
497                 propertyNames.addKnownUnique(a[k]->key);
498         } else {
499             for (int k = 0; k < i; ++k)
500                 propertyNames.add(a[k]->key);
501         }
502
503         return;
504     }
505
506     // Allocate a buffer to use to sort the keys.
507     Vector<Entry*, smallMapThreshold> sortedEnumerables(m_table->keyCount);
508
509     // Get pointers to the enumerable entries in the buffer.
510     Entry** p = sortedEnumerables.data();
511     unsigned entryCount = m_table->keyCount + m_table->deletedSentinelCount;
512     for (unsigned i = 1; i <= entryCount; i++) {
513         if (m_table->entries()[i].key && !(m_table->entries()[i].attributes & DontEnum))
514             *p++ = &m_table->entries()[i];
515     }
516
517     size_t enumerableCount = p - sortedEnumerables.data();
518     // Sort the entries by index.
519     qsort(sortedEnumerables.data(), enumerableCount, sizeof(Entry*), comparePropertyMapEntryIndices);
520     sortedEnumerables.resize(enumerableCount);
521
522     // Put the keys of the sorted entries into the list.
523     if (!propertyNames.size()) {
524         for (size_t i = 0; i < sortedEnumerables.size(); ++i)
525             propertyNames.addKnownUnique(sortedEnumerables[i]->key);
526     } else {
527         for (size_t i = 0; i < sortedEnumerables.size(); ++i)
528             propertyNames.add(sortedEnumerables[i]->key);
529     }
530 }
531
532 #if DO_PROPERTYMAP_CONSTENCY_CHECK
533
534 void PropertyMap::checkConsistency(PropertyStorage& propertyStorage)
535 {
536     if (!m_table)
537         return;
538
539     ASSERT(m_table->size >= 16);
540     ASSERT(m_table->sizeMask);
541     ASSERT(m_table->size == m_table->sizeMask + 1);
542     ASSERT(!(m_table->size & m_table->sizeMask));
543
544     ASSERT(m_table->keyCount <= m_table->size / 2);
545     ASSERT(m_table->deletedSentinelCount <= m_table->size / 4);
546
547     ASSERT(m_table->keyCount + m_table->deletedSentinelCount <= m_table->size / 2);
548
549     unsigned indexCount = 0;
550     unsigned deletedIndexCount = 0;
551     for (unsigned a = 0; a != m_table->size; ++a) {
552         unsigned entryIndex = m_table->entryIndices[a];
553         if (entryIndex == emptyEntryIndex)
554             continue;
555         if (entryIndex == deletedSentinelIndex) {
556             ++deletedIndexCount;
557             continue;
558         }
559         ASSERT(entryIndex > deletedSentinelIndex);
560         ASSERT(entryIndex - 1 <= m_table->keyCount + m_table->deletedSentinelCount);
561         ++indexCount;
562
563         for (unsigned b = a + 1; b != m_table->size; ++b)
564             ASSERT(m_table->entryIndices[b] != entryIndex);
565     }
566     ASSERT(indexCount == m_table->keyCount);
567     ASSERT(deletedIndexCount == m_table->deletedSentinelCount);
568
569     ASSERT(m_table->entries()[0].key == 0);
570
571     unsigned nonEmptyEntryCount = 0;
572     for (unsigned c = 1; c <= m_table->keyCount + m_table->deletedSentinelCount; ++c) {
573         UString::Rep* rep = m_table->entries()[c].key;
574         if (!rep) {
575             ASSERT(propertyStorage[c - 1]->isUndefined());
576             continue;
577         }
578         ++nonEmptyEntryCount;
579         unsigned i = rep->computedHash();
580         unsigned k = 0;
581         unsigned entryIndex;
582         while (1) {
583             entryIndex = m_table->entryIndices[i & m_table->sizeMask];
584             ASSERT(entryIndex != emptyEntryIndex);
585             if (rep == m_table->entries()[entryIndex - 1].key)
586                 break;
587             if (k == 0)
588                 k = 1 | doubleHash(rep->computedHash());
589             i += k;
590         }
591         ASSERT(entryIndex == c + 1);
592     }
593
594     ASSERT(nonEmptyEntryCount == m_table->keyCount);
595 }
596
597 #endif // DO_PROPERTYMAP_CONSTENCY_CHECK
598
599 } // namespace JSC