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