2008-10-07 Cameron Zwarich <zwarich@apple.com>
[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 #else
39 #define DO_PROPERTYMAP_CONSTENCY_CHECK 0
40 #endif
41
42 namespace JSC {
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 static const int smallMapThreshold = 1024;
47
48 // The point at which the function call overhead of the qsort implementation
49 // becomes small compared to the inefficiency of insertion sort.
50 static const unsigned tinyMapThreshold = 20;
51
52 #if DUMP_PROPERTYMAP_STATS
53
54 static int numProbes;
55 static int numCollisions;
56 static int numRehashes;
57 static int numRemoves;
58
59 struct PropertyMapStatisticsExitLogger {
60     ~PropertyMapStatisticsExitLogger();
61 };
62
63 static PropertyMapStatisticsExitLogger logger;
64
65 PropertyMapStatisticsExitLogger::~PropertyMapStatisticsExitLogger()
66 {
67     printf("\nJSC::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 static const unsigned deletedSentinelIndex = 1;
77
78 #if !DO_PROPERTYMAP_CONSTENCY_CHECK
79
80 inline void PropertyMap::checkConsistency(PropertyStorage&)
81 {
82 }
83
84 #endif
85
86 PropertyMap& PropertyMap::operator=(const PropertyMap& other)
87 {
88     if (other.m_table) {
89         size_t tableSize = Table::allocationSize(other.m_table->size);
90         m_table = static_cast<Table*>(fastMalloc(tableSize));
91         memcpy(m_table, other.m_table, tableSize);
92
93         unsigned entryCount = m_table->keyCount + m_table->deletedSentinelCount;
94         for (unsigned i = 1; i <= entryCount; ++i) {
95             if (UString::Rep* key = m_table->entries()[i].key)
96                 key->ref();
97         }
98     }
99
100     m_getterSetterFlag = other.m_getterSetterFlag;
101     return *this;
102 }
103
104 PropertyMap::~PropertyMap()
105 {
106     if (!m_table)
107         return;
108
109     unsigned entryCount = m_table->keyCount + m_table->deletedSentinelCount;
110     for (unsigned i = 1; i <= entryCount; i++) {
111         if (UString::Rep* key = m_table->entries()[i].key)
112             key->deref();
113     }
114     fastFree(m_table);
115 }
116
117 size_t PropertyMap::put(const Identifier& propertyName, JSValue* value, unsigned attributes, bool checkReadOnly, JSObject* slotBase, PutPropertySlot& slot, PropertyStorage& propertyStorage)
118 {
119     ASSERT(!propertyName.isNull());
120     ASSERT(value);
121
122     checkConsistency(propertyStorage);
123
124     UString::Rep* rep = propertyName._ustring.rep();
125
126     if (!m_table)
127         expand(propertyStorage);
128
129     // FIXME: Consider a fast case for tables with no deleted sentinels.
130
131     unsigned i = rep->computedHash();
132     unsigned k = 0;
133     bool foundDeletedElement = false;
134     unsigned deletedElementIndex = 0; // initialize to make the compiler happy
135
136 #if DUMP_PROPERTYMAP_STATS
137     ++numProbes;
138 #endif
139
140     while (1) {
141         unsigned entryIndex = m_table->entryIndices[i & m_table->sizeMask];
142         if (entryIndex == emptyEntryIndex)
143             break;
144
145         if (m_table->entries()[entryIndex - 1].key == rep) {
146             if (checkReadOnly && (m_table->entries()[entryIndex - 1].attributes & ReadOnly))
147                 return WTF::notFound;
148             // Put a new value in an existing hash table entry.
149             propertyStorage[entryIndex - 2] = value;
150             // Attributes are intentionally not updated.
151             slot.setExistingProperty(slotBase, entryIndex - 2);
152             return entryIndex - 2;
153         } else if (entryIndex == deletedSentinelIndex) {
154             // If we find a deleted-element sentinel, remember it for use later.
155             if (!foundDeletedElement) {
156                 foundDeletedElement = true;
157                 deletedElementIndex = i;
158             }
159         }
160
161         if (k == 0) {
162             k = 1 | doubleHash(rep->computedHash());
163 #if DUMP_PROPERTYMAP_STATS
164             ++numCollisions;
165 #endif
166         }
167
168         i += k;
169
170 #if DUMP_PROPERTYMAP_STATS
171         ++numRehashes;
172 #endif
173     }
174
175     // Figure out which entry to use.
176     unsigned entryIndex = m_table->keyCount + m_table->deletedSentinelCount + 2;
177     if (foundDeletedElement) {
178         i = deletedElementIndex;
179         --m_table->deletedSentinelCount;
180
181         // Since we're not making the table bigger, we can't use the entry one past
182         // the end that we were planning on using, so search backwards for the empty
183         // slot that we can use. We know it will be there because we did at least one
184         // deletion in the past that left an entry empty.
185         while (m_table->entries()[--entryIndex - 1].key) { }
186     }
187
188     // Create a new hash table entry.
189     m_table->entryIndices[i & m_table->sizeMask] = entryIndex;
190
191     // Create a new hash table entry.
192     rep->ref();
193     m_table->entries()[entryIndex - 1].key = rep;
194     m_table->entries()[entryIndex - 1].attributes = attributes;
195     m_table->entries()[entryIndex - 1].index = ++m_table->lastIndexUsed;
196     ++m_table->keyCount;
197
198     propertyStorage[entryIndex - 2] = value;
199
200     if ((m_table->keyCount + m_table->deletedSentinelCount) * 2 >= m_table->size)
201         expand(propertyStorage);
202
203     checkConsistency(propertyStorage);
204     slot.setNewProperty(slotBase, entryIndex - 2);
205     return entryIndex - 2;
206 }
207
208 void PropertyMap::remove(const Identifier& propertyName, PropertyStorage& propertyStorage)
209 {
210     ASSERT(!propertyName.isNull());
211
212     checkConsistency(propertyStorage);
213
214     UString::Rep* rep = propertyName._ustring.rep();
215
216     if (!m_table)
217         return;
218
219 #if DUMP_PROPERTYMAP_STATS
220     ++numProbes;
221     ++numRemoves;
222 #endif
223
224     // Find the thing to remove.
225     unsigned i = rep->computedHash();
226     unsigned k = 0;
227     unsigned entryIndex;
228     UString::Rep* key = 0;
229     while (1) {
230         entryIndex = m_table->entryIndices[i & m_table->sizeMask];
231         if (entryIndex == emptyEntryIndex)
232             return;
233
234         key = m_table->entries()[entryIndex - 1].key;
235         if (rep == key)
236             break;
237
238         if (k == 0) {
239             k = 1 | doubleHash(rep->computedHash());
240 #if DUMP_PROPERTYMAP_STATS
241             ++numCollisions;
242 #endif
243         }
244
245         i += k;
246
247 #if DUMP_PROPERTYMAP_STATS
248         ++numRehashes;
249 #endif
250     }
251
252     // Replace this one element with the deleted sentinel. Also clear out
253     // the entry so we can iterate all the entries as needed.
254     m_table->entryIndices[i & m_table->sizeMask] = deletedSentinelIndex;
255     key->deref();
256     m_table->entries()[entryIndex - 1].key = 0;
257     m_table->entries()[entryIndex - 1].attributes = 0;
258
259     propertyStorage[entryIndex - 2] = jsUndefined();
260
261     ASSERT(m_table->keyCount >= 1);
262     --m_table->keyCount;
263     ++m_table->deletedSentinelCount;
264
265     if (m_table->deletedSentinelCount * 4 >= m_table->size)
266         rehash(propertyStorage);
267
268     checkConsistency(propertyStorage);
269 }
270
271 size_t PropertyMap::getOffset(const Identifier& propertyName, unsigned& attributes)
272 {
273     ASSERT(!propertyName.isNull());
274
275     if (!m_table)
276         return WTF::notFound;
277
278     UString::Rep* rep = propertyName._ustring.rep();
279
280     unsigned i = rep->computedHash();
281
282 #if DUMP_PROPERTYMAP_STATS
283     ++numProbes;
284 #endif
285
286     unsigned entryIndex = m_table->entryIndices[i & m_table->sizeMask];
287     if (entryIndex == emptyEntryIndex)
288         return WTF::notFound;
289
290     if (rep == m_table->entries()[entryIndex - 1].key) {
291         attributes = m_table->entries()[entryIndex - 1].attributes;
292         return entryIndex - 2;
293     }
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             attributes = m_table->entries()[entryIndex - 1].attributes;
314             return entryIndex - 2;
315         }
316     }
317 }
318
319 void PropertyMap::insert(const Entry& entry, JSValue* value, PropertyStorage& propertyStorage)
320 {
321     ASSERT(m_table);
322
323     unsigned i = entry.key->computedHash();
324     unsigned k = 0;
325
326 #if DUMP_PROPERTYMAP_STATS
327     ++numProbes;
328 #endif
329
330     while (1) {
331         unsigned entryIndex = m_table->entryIndices[i & m_table->sizeMask];
332         if (entryIndex == emptyEntryIndex)
333             break;
334
335         if (k == 0) {
336             k = 1 | doubleHash(entry.key->computedHash());
337 #if DUMP_PROPERTYMAP_STATS
338             ++numCollisions;
339 #endif
340         }
341
342         i += k;
343
344 #if DUMP_PROPERTYMAP_STATS
345         ++numRehashes;
346 #endif
347     }
348
349     unsigned entryIndex = m_table->keyCount + 2;
350     m_table->entryIndices[i & m_table->sizeMask] = entryIndex;
351     m_table->entries()[entryIndex - 1] = entry;
352
353     propertyStorage[entryIndex - 2] = value;
354
355     ++m_table->keyCount;
356 }
357
358 void PropertyMap::expand(PropertyStorage& propertyStorage)
359 {
360     if (!m_table)
361         createTable(propertyStorage);
362     else
363         rehash(m_table->size * 2, propertyStorage);
364 }
365
366 void PropertyMap::rehash(PropertyStorage& propertyStorage)
367 {
368     ASSERT(m_table);
369     ASSERT(m_table->size);
370     rehash(m_table->size, propertyStorage);
371 }
372
373 void PropertyMap::createTable(PropertyStorage& propertyStorage)
374 {
375     const unsigned newTableSize = 16;
376
377     ASSERT(!m_table);
378
379     checkConsistency(propertyStorage);
380
381     m_table = static_cast<Table*>(fastZeroedMalloc(Table::allocationSize(newTableSize)));
382     m_table->size = newTableSize;
383     m_table->sizeMask = newTableSize - 1;
384
385     checkConsistency(propertyStorage);
386 }
387
388 void PropertyMap::rehash(unsigned newTableSize, PropertyStorage& propertyStorage)
389 {
390     ASSERT(m_table);
391
392     checkConsistency(propertyStorage);
393
394     Table* oldTable = m_table;
395     JSValue** oldPropertStorage = propertyStorage;
396
397     m_table = static_cast<Table*>(fastZeroedMalloc(Table::allocationSize(newTableSize)));
398     m_table->size = newTableSize;
399     m_table->sizeMask = newTableSize - 1;
400
401     propertyStorage = new JSValue*[m_table->size];
402
403     unsigned lastIndexUsed = 0;
404     unsigned entryCount = oldTable->keyCount + oldTable->deletedSentinelCount;
405     for (unsigned i = 1; i <= entryCount; ++i) {
406         if (oldTable->entries()[i].key) {
407             lastIndexUsed = max(oldTable->entries()[i].index, lastIndexUsed);
408             insert(oldTable->entries()[i], oldPropertStorage[i - 1], propertyStorage);
409         }
410     }
411     m_table->lastIndexUsed = lastIndexUsed;
412
413     fastFree(oldTable);
414     delete [] oldPropertStorage;
415
416     checkConsistency(propertyStorage);
417 }
418
419 static int comparePropertyMapEntryIndices(const void* a, const void* b)
420 {
421     unsigned ia = static_cast<PropertyMapEntry* const*>(a)[0]->index;
422     unsigned ib = static_cast<PropertyMapEntry* const*>(b)[0]->index;
423     if (ia < ib)
424         return -1;
425     if (ia > ib)
426         return +1;
427     return 0;
428 }
429
430 void PropertyMap::getEnumerablePropertyNames(PropertyNameArray& propertyNames) const
431 {
432     if (!m_table)
433         return;
434
435     if (m_table->keyCount < tinyMapThreshold) {
436         Entry* a[tinyMapThreshold];
437         int i = 0;
438         unsigned entryCount = m_table->keyCount + m_table->deletedSentinelCount;
439         for (unsigned k = 1; k <= entryCount; k++) {
440             if (m_table->entries()[k].key && !(m_table->entries()[k].attributes & DontEnum)) {
441                 Entry* value = &m_table->entries()[k];
442                 int j;
443                 for (j = i - 1; j >= 0 && a[j]->index > value->index; --j)
444                     a[j + 1] = a[j];
445                 a[j + 1] = value;
446                 ++i;
447             }
448         }
449         if (!propertyNames.size()) {
450             for (int k = 0; k < i; ++k)
451                 propertyNames.addKnownUnique(a[k]->key);
452         } else {
453             for (int k = 0; k < i; ++k)
454                 propertyNames.add(a[k]->key);
455         }
456
457         return;
458     }
459
460     // Allocate a buffer to use to sort the keys.
461     Vector<Entry*, smallMapThreshold> sortedEnumerables(m_table->keyCount);
462
463     // Get pointers to the enumerable entries in the buffer.
464     Entry** p = sortedEnumerables.data();
465     unsigned entryCount = m_table->keyCount + m_table->deletedSentinelCount;
466     for (unsigned i = 1; i <= entryCount; i++) {
467         if (m_table->entries()[i].key && !(m_table->entries()[i].attributes & DontEnum))
468             *p++ = &m_table->entries()[i];
469     }
470
471     size_t enumerableCount = p - sortedEnumerables.data();
472     // Sort the entries by index.
473     qsort(sortedEnumerables.data(), enumerableCount, sizeof(Entry*), comparePropertyMapEntryIndices);
474     sortedEnumerables.resize(enumerableCount);
475
476     // Put the keys of the sorted entries into the list.
477     if (!propertyNames.size()) {
478         for (size_t i = 0; i < sortedEnumerables.size(); ++i)
479             propertyNames.addKnownUnique(sortedEnumerables[i]->key);
480     } else {
481         for (size_t i = 0; i < sortedEnumerables.size(); ++i)
482             propertyNames.add(sortedEnumerables[i]->key);
483     }
484 }
485
486 #if DO_PROPERTYMAP_CONSTENCY_CHECK
487
488 void PropertyMap::checkConsistency(PropertyStorage& propertyStorage)
489 {
490     if (!m_table)
491         return;
492
493     ASSERT(m_table->size >= 16);
494     ASSERT(m_table->sizeMask);
495     ASSERT(m_table->size == m_table->sizeMask + 1);
496     ASSERT(!(m_table->size & m_table->sizeMask));
497
498     ASSERT(m_table->keyCount <= m_table->size / 2);
499     ASSERT(m_table->deletedSentinelCount <= m_table->size / 4);
500
501     ASSERT(m_table->keyCount + m_table->deletedSentinelCount <= m_table->size / 2);
502
503     unsigned indexCount = 0;
504     unsigned deletedIndexCount = 0;
505     for (unsigned a = 0; a != m_table->size; ++a) {
506         unsigned entryIndex = m_table->entryIndices[a];
507         if (entryIndex == emptyEntryIndex)
508             continue;
509         if (entryIndex == deletedSentinelIndex) {
510             ++deletedIndexCount;
511             continue;
512         }
513         ASSERT(entryIndex > deletedSentinelIndex);
514         ASSERT(entryIndex - 1 <= m_table->keyCount + m_table->deletedSentinelCount);
515         ++indexCount;
516
517         for (unsigned b = a + 1; b != m_table->size; ++b)
518             ASSERT(m_table->entryIndices[b] != entryIndex);
519     }
520     ASSERT(indexCount == m_table->keyCount);
521     ASSERT(deletedIndexCount == m_table->deletedSentinelCount);
522
523     ASSERT(m_table->entries()[0].key == 0);
524
525     unsigned nonEmptyEntryCount = 0;
526     for (unsigned c = 1; c <= m_table->keyCount + m_table->deletedSentinelCount; ++c) {
527         UString::Rep* rep = m_table->entries()[c].key;
528         if (!rep) {
529             ASSERT(propertyStorage[c - 1]->isUndefined());
530             continue;
531         }
532         ++nonEmptyEntryCount;
533         unsigned i = rep->computedHash();
534         unsigned k = 0;
535         unsigned entryIndex;
536         while (1) {
537             entryIndex = m_table->entryIndices[i & m_table->sizeMask];
538             ASSERT(entryIndex != emptyEntryIndex);
539             if (rep == m_table->entries()[entryIndex - 1].key)
540                 break;
541             if (k == 0)
542                 k = 1 | doubleHash(rep->computedHash());
543             i += k;
544         }
545         ASSERT(entryIndex == c + 1);
546     }
547
548     ASSERT(nonEmptyEntryCount == m_table->keyCount);
549 }
550
551 #endif // DO_PROPERTYMAP_CONSTENCY_CHECK
552
553 } // namespace JSC