2008-09-24 Maciej Stachowiak <mjs@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 void 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;
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;
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 }
206
207 void PropertyMap::remove(const Identifier& propertyName, PropertyStorage& propertyStorage)
208 {
209     ASSERT(!propertyName.isNull());
210
211     checkConsistency(propertyStorage);
212
213     UString::Rep* rep = propertyName._ustring.rep();
214
215     if (!m_table)
216         return;
217
218 #if DUMP_PROPERTYMAP_STATS
219     ++numProbes;
220     ++numRemoves;
221 #endif
222
223     // Find the thing to remove.
224     unsigned i = rep->computedHash();
225     unsigned k = 0;
226     unsigned entryIndex;
227     UString::Rep* key = 0;
228     while (1) {
229         entryIndex = m_table->entryIndices[i & m_table->sizeMask];
230         if (entryIndex == emptyEntryIndex)
231             return;
232
233         key = m_table->entries()[entryIndex - 1].key;
234         if (rep == key)
235             break;
236
237         if (k == 0) {
238             k = 1 | doubleHash(rep->computedHash());
239 #if DUMP_PROPERTYMAP_STATS
240             ++numCollisions;
241 #endif
242         }
243
244         i += k;
245
246 #if DUMP_PROPERTYMAP_STATS
247         ++numRehashes;
248 #endif
249     }
250
251     // Replace this one element with the deleted sentinel. Also clear out
252     // the entry so we can iterate all the entries as needed.
253     m_table->entryIndices[i & m_table->sizeMask] = deletedSentinelIndex;
254     key->deref();
255     m_table->entries()[entryIndex - 1].key = 0;
256     m_table->entries()[entryIndex - 1].attributes = 0;
257
258     propertyStorage[entryIndex - 2] = jsUndefined();
259
260     ASSERT(m_table->keyCount >= 1);
261     --m_table->keyCount;
262     ++m_table->deletedSentinelCount;
263
264     if (m_table->deletedSentinelCount * 4 >= m_table->size)
265         rehash(propertyStorage);
266
267     checkConsistency(propertyStorage);
268 }
269
270 size_t PropertyMap::getOffset(const Identifier& propertyName, unsigned& attributes)
271 {
272     ASSERT(!propertyName.isNull());
273
274     if (!m_table)
275         return WTF::notFound;
276
277     UString::Rep* rep = propertyName._ustring.rep();
278
279     unsigned i = rep->computedHash();
280
281 #if DUMP_PROPERTYMAP_STATS
282     ++numProbes;
283 #endif
284
285     unsigned entryIndex = m_table->entryIndices[i & m_table->sizeMask];
286     if (entryIndex == emptyEntryIndex)
287         return WTF::notFound;
288
289     if (rep == m_table->entries()[entryIndex - 1].key) {
290         attributes = m_table->entries()[entryIndex - 1].attributes;
291         return entryIndex - 2;
292     }
293
294 #if DUMP_PROPERTYMAP_STATS
295     ++numCollisions;
296 #endif
297
298     unsigned k = 1 | doubleHash(rep->computedHash());
299
300     while (1) {
301         i += k;
302
303 #if DUMP_PROPERTYMAP_STATS
304         ++numRehashes;
305 #endif
306
307         entryIndex = m_table->entryIndices[i & m_table->sizeMask];
308         if (entryIndex == emptyEntryIndex)
309             return WTF::notFound;
310
311         if (rep == m_table->entries()[entryIndex - 1].key) {
312             attributes = m_table->entries()[entryIndex - 1].attributes;
313             return entryIndex - 2;
314         }
315     }
316 }
317
318 void PropertyMap::insert(const Entry& entry, JSValue* value, PropertyStorage& propertyStorage)
319 {
320     ASSERT(m_table);
321
322     unsigned i = entry.key->computedHash();
323     unsigned k = 0;
324
325 #if DUMP_PROPERTYMAP_STATS
326     ++numProbes;
327 #endif
328
329     while (1) {
330         unsigned entryIndex = m_table->entryIndices[i & m_table->sizeMask];
331         if (entryIndex == emptyEntryIndex)
332             break;
333
334         if (k == 0) {
335             k = 1 | doubleHash(entry.key->computedHash());
336 #if DUMP_PROPERTYMAP_STATS
337             ++numCollisions;
338 #endif
339         }
340
341         i += k;
342
343 #if DUMP_PROPERTYMAP_STATS
344         ++numRehashes;
345 #endif
346     }
347
348     unsigned entryIndex = m_table->keyCount + 2;
349     m_table->entryIndices[i & m_table->sizeMask] = entryIndex;
350     m_table->entries()[entryIndex - 1] = entry;
351
352     propertyStorage[entryIndex - 2] = value;
353
354     ++m_table->keyCount;
355 }
356
357 void PropertyMap::expand(PropertyStorage& propertyStorage)
358 {
359     if (!m_table)
360         createTable(propertyStorage);
361     else
362         rehash(m_table->size * 2, propertyStorage);
363 }
364
365 void PropertyMap::rehash(PropertyStorage& propertyStorage)
366 {
367     ASSERT(m_table);
368     ASSERT(m_table->size);
369     rehash(m_table->size, propertyStorage);
370 }
371
372 void PropertyMap::createTable(PropertyStorage& propertyStorage)
373 {
374     const unsigned newTableSize = 16;
375
376     ASSERT(!m_table);
377
378     checkConsistency(propertyStorage);
379
380     m_table = static_cast<Table*>(fastZeroedMalloc(Table::allocationSize(newTableSize)));
381     m_table->size = newTableSize;
382     m_table->sizeMask = newTableSize - 1;
383
384     checkConsistency(propertyStorage);
385 }
386
387 void PropertyMap::rehash(unsigned newTableSize, PropertyStorage& propertyStorage)
388 {
389     ASSERT(m_table);
390
391     checkConsistency(propertyStorage);
392
393     Table* oldTable = m_table;
394     JSValue** oldPropertStorage = propertyStorage;
395
396     m_table = static_cast<Table*>(fastZeroedMalloc(Table::allocationSize(newTableSize)));
397     m_table->size = newTableSize;
398     m_table->sizeMask = newTableSize - 1;
399
400     propertyStorage = new JSValue*[m_table->size];
401
402     unsigned lastIndexUsed = 0;
403     unsigned entryCount = oldTable->keyCount + oldTable->deletedSentinelCount;
404     for (unsigned i = 1; i <= entryCount; ++i) {
405         if (oldTable->entries()[i].key) {
406             lastIndexUsed = max(oldTable->entries()[i].index, lastIndexUsed);
407             insert(oldTable->entries()[i], oldPropertStorage[i - 1], propertyStorage);
408         }
409     }
410     m_table->lastIndexUsed = lastIndexUsed;
411
412     fastFree(oldTable);
413     delete [] oldPropertStorage;
414
415     checkConsistency(propertyStorage);
416 }
417
418 static int comparePropertyMapEntryIndices(const void* a, const void* b)
419 {
420     unsigned ia = static_cast<PropertyMapEntry* const*>(a)[0]->index;
421     unsigned ib = static_cast<PropertyMapEntry* const*>(b)[0]->index;
422     if (ia < ib)
423         return -1;
424     if (ia > ib)
425         return +1;
426     return 0;
427 }
428
429 void PropertyMap::getEnumerablePropertyNames(PropertyNameArray& propertyNames) const
430 {
431     if (!m_table)
432         return;
433
434     if (m_table->keyCount < tinyMapThreshold) {
435         Entry* a[tinyMapThreshold];
436         int i = 0;
437         unsigned entryCount = m_table->keyCount + m_table->deletedSentinelCount;
438         for (unsigned k = 1; k <= entryCount; k++) {
439             if (m_table->entries()[k].key && !(m_table->entries()[k].attributes & DontEnum)) {
440                 Entry* value = &m_table->entries()[k];
441                 int j;
442                 for (j = i - 1; j >= 0 && a[j]->index > value->index; --j)
443                     a[j + 1] = a[j];
444                 a[j + 1] = value;
445                 ++i;
446             }
447         }
448         if (!propertyNames.size()) {
449             for (int k = 0; k < i; ++k)
450                 propertyNames.addKnownUnique(a[k]->key);
451         } else {
452             for (int k = 0; k < i; ++k)
453                 propertyNames.add(a[k]->key);
454         }
455
456         return;
457     }
458
459     // Allocate a buffer to use to sort the keys.
460     Vector<Entry*, smallMapThreshold> sortedEnumerables(m_table->keyCount);
461
462     // Get pointers to the enumerable entries in the buffer.
463     Entry** p = sortedEnumerables.data();
464     unsigned entryCount = m_table->keyCount + m_table->deletedSentinelCount;
465     for (unsigned i = 1; i <= entryCount; i++) {
466         if (m_table->entries()[i].key && !(m_table->entries()[i].attributes & DontEnum))
467             *p++ = &m_table->entries()[i];
468     }
469
470     size_t enumerableCount = p - sortedEnumerables.data();
471     // Sort the entries by index.
472     qsort(sortedEnumerables.data(), enumerableCount, sizeof(Entry*), comparePropertyMapEntryIndices);
473     sortedEnumerables.resize(enumerableCount);
474
475     // Put the keys of the sorted entries into the list.
476     if (!propertyNames.size()) {
477         for (size_t i = 0; i < sortedEnumerables.size(); ++i)
478             propertyNames.addKnownUnique(sortedEnumerables[i]->key);
479     } else {
480         for (size_t i = 0; i < sortedEnumerables.size(); ++i)
481             propertyNames.add(sortedEnumerables[i]->key);
482     }
483 }
484
485 #if DO_PROPERTYMAP_CONSTENCY_CHECK
486
487 void PropertyMap::checkConsistency(PropertyStorage& propertyStorage)
488 {
489     if (!m_table)
490         return;
491
492     ASSERT(m_table->size >= 16);
493     ASSERT(m_table->sizeMask);
494     ASSERT(m_table->size == m_table->sizeMask + 1);
495     ASSERT(!(m_table->size & m_table->sizeMask));
496
497     ASSERT(m_table->keyCount <= m_table->size / 2);
498     ASSERT(m_table->deletedSentinelCount <= m_table->size / 4);
499
500     ASSERT(m_table->keyCount + m_table->deletedSentinelCount <= m_table->size / 2);
501
502     unsigned indexCount = 0;
503     unsigned deletedIndexCount = 0;
504     for (unsigned a = 0; a != m_table->size; ++a) {
505         unsigned entryIndex = m_table->entryIndices[a];
506         if (entryIndex == emptyEntryIndex)
507             continue;
508         if (entryIndex == deletedSentinelIndex) {
509             ++deletedIndexCount;
510             continue;
511         }
512         ASSERT(entryIndex > deletedSentinelIndex);
513         ASSERT(entryIndex - 1 <= m_table->keyCount + m_table->deletedSentinelCount);
514         ++indexCount;
515
516         for (unsigned b = a + 1; b != m_table->size; ++b)
517             ASSERT(m_table->entryIndices[b] != entryIndex);
518     }
519     ASSERT(indexCount == m_table->keyCount);
520     ASSERT(deletedIndexCount == m_table->deletedSentinelCount);
521
522     ASSERT(m_table->entries()[0].key == 0);
523
524     unsigned nonEmptyEntryCount = 0;
525     for (unsigned c = 1; c <= m_table->keyCount + m_table->deletedSentinelCount; ++c) {
526         UString::Rep* rep = m_table->entries()[c].key;
527         if (!rep) {
528             ASSERT(propertyStorage[c - 1]->isUndefined());
529             continue;
530         }
531         ++nonEmptyEntryCount;
532         unsigned i = rep->computedHash();
533         unsigned k = 0;
534         unsigned entryIndex;
535         while (1) {
536             entryIndex = m_table->entryIndices[i & m_table->sizeMask];
537             ASSERT(entryIndex != emptyEntryIndex);
538             if (rep == m_table->entries()[entryIndex - 1].key)
539                 break;
540             if (k == 0)
541                 k = 1 | doubleHash(rep->computedHash());
542             i += k;
543         }
544         ASSERT(entryIndex == c + 1);
545     }
546
547     ASSERT(nonEmptyEntryCount == m_table->keyCount);
548 }
549
550 #endif // DO_PROPERTYMAP_CONSTENCY_CHECK
551
552 } // namespace JSC