2008-10-06 Sam Weinig <sam@webkit.org>
[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()
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_deletedOffsets = other.m_deletedOffsets;
101     m_getterSetterFlag = other.m_getterSetterFlag;
102     return *this;
103 }
104
105 PropertyMap::~PropertyMap()
106 {
107     if (!m_table)
108         return;
109
110     unsigned entryCount = m_table->keyCount + m_table->deletedSentinelCount;
111     for (unsigned i = 1; i <= entryCount; i++) {
112         if (UString::Rep* key = m_table->entries()[i].key)
113             key->deref();
114     }
115     fastFree(m_table);
116 }
117
118 size_t PropertyMap::put(const Identifier& propertyName, unsigned attributes)
119 {
120     ASSERT(!propertyName.isNull());
121     ASSERT(get(propertyName) == WTF::notFound);
122
123     checkConsistency();
124
125     UString::Rep* rep = propertyName._ustring.rep();
126
127     if (!m_table)
128         createTable();
129
130     // FIXME: Consider a fast case for tables with no deleted sentinels.
131
132     unsigned i = rep->computedHash();
133     unsigned k = 0;
134     bool foundDeletedElement = false;
135     unsigned deletedElementIndex = 0; // initialize to make the compiler happy
136
137 #if DUMP_PROPERTYMAP_STATS
138     ++numProbes;
139 #endif
140
141     while (1) {
142         unsigned entryIndex = m_table->entryIndices[i & m_table->sizeMask];
143         if (entryIndex == emptyEntryIndex)
144             break;
145
146         if (entryIndex == deletedSentinelIndex) {
147             // If we find a deleted-element sentinel, remember it for use later.
148             if (!foundDeletedElement) {
149                 foundDeletedElement = true;
150                 deletedElementIndex = i;
151             }
152         }
153
154         if (k == 0) {
155             k = 1 | doubleHash(rep->computedHash());
156 #if DUMP_PROPERTYMAP_STATS
157             ++numCollisions;
158 #endif
159         }
160
161         i += k;
162
163 #if DUMP_PROPERTYMAP_STATS
164         ++numRehashes;
165 #endif
166     }
167
168     // Figure out which entry to use.
169     unsigned entryIndex = m_table->keyCount + m_table->deletedSentinelCount + 2;
170     if (foundDeletedElement) {
171         i = deletedElementIndex;
172         --m_table->deletedSentinelCount;
173
174         // Since we're not making the table bigger, we can't use the entry one past
175         // the end that we were planning on using, so search backwards for the empty
176         // slot that we can use. We know it will be there because we did at least one
177         // deletion in the past that left an entry empty.
178         while (m_table->entries()[--entryIndex - 1].key) { }
179     }
180
181     // Create a new hash table entry.
182     m_table->entryIndices[i & m_table->sizeMask] = entryIndex;
183
184     // Create a new hash table entry.
185     rep->ref();
186     m_table->entries()[entryIndex - 1].key = rep;
187     m_table->entries()[entryIndex - 1].attributes = attributes;
188     m_table->entries()[entryIndex - 1].index = ++m_table->lastIndexUsed;
189
190     unsigned newOffset;
191     if (!m_deletedOffsets.isEmpty()) {
192         newOffset = m_deletedOffsets.last();
193         m_deletedOffsets.removeLast();
194     } else
195         newOffset = m_table->keyCount + m_table->deletedSentinelCount;
196     m_table->entries()[entryIndex - 1].offset = newOffset;
197
198     ++m_table->keyCount;
199
200     if ((m_table->keyCount + m_table->deletedSentinelCount) * 2 >= m_table->size)
201         expand();
202
203     checkConsistency();
204     return newOffset;
205 }
206
207 size_t PropertyMap::remove(const Identifier& propertyName)
208 {
209     ASSERT(!propertyName.isNull());
210
211     checkConsistency();
212
213     UString::Rep* rep = propertyName._ustring.rep();
214
215     if (!m_table)
216         return WTF::notFound;
217
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 WTF::notFound;
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
256     size_t offset = m_table->entries()[entryIndex - 1].offset;
257
258     key->deref();
259     m_table->entries()[entryIndex - 1].key = 0;
260     m_table->entries()[entryIndex - 1].attributes = 0;
261     m_table->entries()[entryIndex - 1].offset = 0;
262     m_deletedOffsets.append(offset);
263
264     ASSERT(m_table->keyCount >= 1);
265     --m_table->keyCount;
266     ++m_table->deletedSentinelCount;
267
268     if (m_table->deletedSentinelCount * 4 >= m_table->size)
269         rehash();
270
271     checkConsistency();
272     return offset;
273 }
274
275 size_t PropertyMap::get(const Identifier& propertyName, unsigned& attributes)
276 {
277     ASSERT(!propertyName.isNull());
278
279     if (!m_table)
280         return WTF::notFound;
281
282     UString::Rep* rep = propertyName._ustring.rep();
283
284     unsigned i = rep->computedHash();
285
286 #if DUMP_PROPERTYMAP_STATS
287     ++numProbes;
288 #endif
289
290     unsigned entryIndex = m_table->entryIndices[i & m_table->sizeMask];
291     if (entryIndex == emptyEntryIndex)
292         return WTF::notFound;
293
294     if (rep == m_table->entries()[entryIndex - 1].key) {
295         attributes = m_table->entries()[entryIndex - 1].attributes;
296         return m_table->entries()[entryIndex - 1].offset;
297     }
298
299 #if DUMP_PROPERTYMAP_STATS
300     ++numCollisions;
301 #endif
302
303     unsigned k = 1 | doubleHash(rep->computedHash());
304
305     while (1) {
306         i += k;
307
308 #if DUMP_PROPERTYMAP_STATS
309         ++numRehashes;
310 #endif
311
312         entryIndex = m_table->entryIndices[i & m_table->sizeMask];
313         if (entryIndex == emptyEntryIndex)
314             return WTF::notFound;
315
316         if (rep == m_table->entries()[entryIndex - 1].key) {
317             attributes = m_table->entries()[entryIndex - 1].attributes;
318             return m_table->entries()[entryIndex - 1].offset;
319         }
320     }
321 }
322
323 void PropertyMap::insert(const Entry& entry)
324 {
325     ASSERT(m_table);
326
327     unsigned i = entry.key->computedHash();
328     unsigned k = 0;
329
330 #if DUMP_PROPERTYMAP_STATS
331     ++numProbes;
332 #endif
333
334     while (1) {
335         unsigned entryIndex = m_table->entryIndices[i & m_table->sizeMask];
336         if (entryIndex == emptyEntryIndex)
337             break;
338
339         if (k == 0) {
340             k = 1 | doubleHash(entry.key->computedHash());
341 #if DUMP_PROPERTYMAP_STATS
342             ++numCollisions;
343 #endif
344         }
345
346         i += k;
347
348 #if DUMP_PROPERTYMAP_STATS
349         ++numRehashes;
350 #endif
351     }
352
353     unsigned entryIndex = m_table->keyCount + 2;
354     m_table->entryIndices[i & m_table->sizeMask] = entryIndex;
355     m_table->entries()[entryIndex - 1] = entry;
356
357     ++m_table->keyCount;
358 }
359
360 void PropertyMap::expand()
361 {
362     ASSERT(m_table);
363     rehash(m_table->size * 2);
364 }
365
366 void PropertyMap::createTable()
367 {
368     const unsigned newTableSize = 16;
369
370     ASSERT(!m_table);
371
372     checkConsistency();
373
374     m_table = static_cast<Table*>(fastZeroedMalloc(Table::allocationSize(newTableSize)));
375     m_table->size = newTableSize;
376     m_table->sizeMask = newTableSize - 1;
377
378     checkConsistency();
379 }
380
381 void PropertyMap::rehash()
382 {
383     ASSERT(m_table);
384     ASSERT(m_table->size);
385     rehash(m_table->size);
386 }
387
388 void PropertyMap::rehash(unsigned newTableSize)
389 {
390     ASSERT(m_table);
391
392     checkConsistency();
393
394     Table* oldTable = m_table;
395
396     m_table = static_cast<Table*>(fastZeroedMalloc(Table::allocationSize(newTableSize)));
397     m_table->size = newTableSize;
398     m_table->sizeMask = newTableSize - 1;
399
400     unsigned lastIndexUsed = 0;
401     unsigned entryCount = oldTable->keyCount + oldTable->deletedSentinelCount;
402     for (unsigned i = 1; i <= entryCount; ++i) {
403         if (oldTable->entries()[i].key) {
404             lastIndexUsed = max(oldTable->entries()[i].index, lastIndexUsed);
405             insert(oldTable->entries()[i]);
406         }
407     }
408     m_table->lastIndexUsed = lastIndexUsed;
409
410     fastFree(oldTable);
411
412     checkConsistency();
413 }
414
415 static int comparePropertyMapEntryIndices(const void* a, const void* b)
416 {
417     unsigned ia = static_cast<PropertyMapEntry* const*>(a)[0]->index;
418     unsigned ib = static_cast<PropertyMapEntry* const*>(b)[0]->index;
419     if (ia < ib)
420         return -1;
421     if (ia > ib)
422         return +1;
423     return 0;
424 }
425
426 void PropertyMap::getEnumerablePropertyNames(PropertyNameArray& propertyNames) const
427 {
428     if (!m_table)
429         return;
430
431     if (m_table->keyCount < tinyMapThreshold) {
432         Entry* a[tinyMapThreshold];
433         int i = 0;
434         unsigned entryCount = m_table->keyCount + m_table->deletedSentinelCount;
435         for (unsigned k = 1; k <= entryCount; k++) {
436             if (m_table->entries()[k].key && !(m_table->entries()[k].attributes & DontEnum)) {
437                 Entry* value = &m_table->entries()[k];
438                 int j;
439                 for (j = i - 1; j >= 0 && a[j]->index > value->index; --j)
440                     a[j + 1] = a[j];
441                 a[j + 1] = value;
442                 ++i;
443             }
444         }
445         if (!propertyNames.size()) {
446             for (int k = 0; k < i; ++k)
447                 propertyNames.addKnownUnique(a[k]->key);
448         } else {
449             for (int k = 0; k < i; ++k)
450                 propertyNames.add(a[k]->key);
451         }
452
453         return;
454     }
455
456     // Allocate a buffer to use to sort the keys.
457     Vector<Entry*, smallMapThreshold> sortedEnumerables(m_table->keyCount);
458
459     // Get pointers to the enumerable entries in the buffer.
460     Entry** p = sortedEnumerables.data();
461     unsigned entryCount = m_table->keyCount + m_table->deletedSentinelCount;
462     for (unsigned i = 1; i <= entryCount; i++) {
463         if (m_table->entries()[i].key && !(m_table->entries()[i].attributes & DontEnum))
464             *p++ = &m_table->entries()[i];
465     }
466
467     size_t enumerableCount = p - sortedEnumerables.data();
468     // Sort the entries by index.
469     qsort(sortedEnumerables.data(), enumerableCount, sizeof(Entry*), comparePropertyMapEntryIndices);
470     sortedEnumerables.resize(enumerableCount);
471
472     // Put the keys of the sorted entries into the list.
473     if (!propertyNames.size()) {
474         for (size_t i = 0; i < sortedEnumerables.size(); ++i)
475             propertyNames.addKnownUnique(sortedEnumerables[i]->key);
476     } else {
477         for (size_t i = 0; i < sortedEnumerables.size(); ++i)
478             propertyNames.add(sortedEnumerables[i]->key);
479     }
480 }
481
482 #if DO_PROPERTYMAP_CONSTENCY_CHECK
483
484 void PropertyMap::checkConsistency()
485 {
486     if (!m_table)
487         return;
488
489     ASSERT(m_table->size >= 16);
490     ASSERT(m_table->sizeMask);
491     ASSERT(m_table->size == m_table->sizeMask + 1);
492     ASSERT(!(m_table->size & m_table->sizeMask));
493
494     ASSERT(m_table->keyCount <= m_table->size / 2);
495     ASSERT(m_table->deletedSentinelCount <= m_table->size / 4);
496
497     ASSERT(m_table->keyCount + m_table->deletedSentinelCount <= m_table->size / 2);
498
499     unsigned indexCount = 0;
500     unsigned deletedIndexCount = 0;
501     for (unsigned a = 0; a != m_table->size; ++a) {
502         unsigned entryIndex = m_table->entryIndices[a];
503         if (entryIndex == emptyEntryIndex)
504             continue;
505         if (entryIndex == deletedSentinelIndex) {
506             ++deletedIndexCount;
507             continue;
508         }
509         ASSERT(entryIndex > deletedSentinelIndex);
510         ASSERT(entryIndex - 1 <= m_table->keyCount + m_table->deletedSentinelCount);
511         ++indexCount;
512
513         for (unsigned b = a + 1; b != m_table->size; ++b)
514             ASSERT(m_table->entryIndices[b] != entryIndex);
515     }
516     ASSERT(indexCount == m_table->keyCount);
517     ASSERT(deletedIndexCount == m_table->deletedSentinelCount);
518
519     ASSERT(m_table->entries()[0].key == 0);
520
521     unsigned nonEmptyEntryCount = 0;
522     for (unsigned c = 1; c <= m_table->keyCount + m_table->deletedSentinelCount; ++c) {
523         UString::Rep* rep = m_table->entries()[c].key;
524         if (!rep)
525             continue;
526         ++nonEmptyEntryCount;
527         unsigned i = rep->computedHash();
528         unsigned k = 0;
529         unsigned entryIndex;
530         while (1) {
531             entryIndex = m_table->entryIndices[i & m_table->sizeMask];
532             ASSERT(entryIndex != emptyEntryIndex);
533             if (rep == m_table->entries()[entryIndex - 1].key)
534                 break;
535             if (k == 0)
536                 k = 1 | doubleHash(rep->computedHash());
537             i += k;
538         }
539         ASSERT(entryIndex == c + 1);
540     }
541
542     ASSERT(nonEmptyEntryCount == m_table->keyCount);
543 }
544
545 #endif // DO_PROPERTYMAP_CONSTENCY_CHECK
546
547 } // namespace JSC