JavaScriptCore:
[WebKit-https.git] / JavaScriptCore / kjs / property_map.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 "property_map.h"
23
24 #include "object.h"
25 #include "protect.h"
26 #include "PropertyNameArray.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 #define USE_SINGLE_ENTRY 1
45
46 // 2/28/2006 ggaren: command-line JS iBench says that USE_SINGLE_ENTRY is a
47 // 3.2% performance boost.
48
49 namespace KJS {
50
51 // Choose a number for the following so that most property maps are smaller,
52 // but it's not going to blow out the stack to allocate this number of pointers.
53 static const int smallMapThreshold = 1024;
54
55 // The point at which the function call overhead of the qsort implementation
56 // becomes small compared to the inefficiency of insertion sort.
57 static const unsigned tinyMapThreshold = 20;
58
59 #if DUMP_PROPERTYMAP_STATS
60
61 static int numProbes;
62 static int numCollisions;
63 static int numRehashes;
64 static int numRemoves;
65
66 struct PropertyMapStatisticsExitLogger { ~PropertyMapStatisticsExitLogger(); };
67
68 static PropertyMapStatisticsExitLogger logger;
69
70 PropertyMapStatisticsExitLogger::~PropertyMapStatisticsExitLogger()
71 {
72     printf("\nKJS::PropertyMap statistics\n\n");
73     printf("%d probes\n", numProbes);
74     printf("%d collisions (%.1f%%)\n", numCollisions, 100.0 * numCollisions / numProbes);
75     printf("%d rehashes\n", numRehashes);
76     printf("%d removes\n", numRemoves);
77 }
78
79 #endif
80
81 struct PropertyMapEntry {
82     UString::Rep* key;
83     JSValue* value;
84     unsigned attributes;
85     unsigned index;
86
87     PropertyMapEntry(UString::Rep* k, JSValue* v, int a)
88         : key(k), value(v), attributes(a), index(0)
89     {
90     }
91 };
92
93 // lastIndexUsed is an ever-increasing index used to identify the order items
94 // were inserted into the property map. It's required that getEnumerablePropertyNames
95 // return the properties in the order they were added for compatibility with other
96 // browsers' JavaScript implementations.
97 struct PropertyMapHashTable {
98     unsigned sizeMask;
99     unsigned size;
100     unsigned keyCount;
101     unsigned deletedSentinelCount;
102     unsigned lastIndexUsed;
103     unsigned entryIndicies[1];
104
105     PropertyMapEntry* entries()
106     {
107         // The entries vector comes after the indices vector.
108         // The 0th item in the entries vector is not really used; it has to
109         // have a 0 in its key to allow the hash table lookup to handle deleted
110         // sentinels without any special-case code, but the other fields are unused.
111         return reinterpret_cast<PropertyMapEntry*>(&entryIndicies[size]);
112     }
113
114     static size_t allocationSize(unsigned size)
115     {
116         // We never let a hash table get more than half full,
117         // So the number of indices we need is the size of the hash table.
118         // But the number of entries is half that (plus one for the deleted sentinel).
119         return sizeof(PropertyMapHashTable)
120             + (size - 1) * sizeof(unsigned)
121             + (1 + size / 2) * sizeof(PropertyMapEntry);
122     }
123 };
124
125 static const unsigned emptyEntryIndex = 0;
126 static const unsigned deletedSentinelIndex = 1;
127
128 SavedProperties::SavedProperties()
129     : count(0)
130 {
131 }
132
133 SavedProperties::~SavedProperties()
134 {
135 }
136
137 #if !DO_PROPERTYMAP_CONSTENCY_CHECK
138
139 inline void PropertyMap::checkConsistency()
140 {
141 }
142
143 #endif
144
145 PropertyMap::~PropertyMap()
146 {
147     if (!m_usingTable) {
148 #if USE_SINGLE_ENTRY
149         if (m_singleEntryKey)
150             m_singleEntryKey->deref();
151 #endif
152         return;
153     }
154     
155     unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
156     for (unsigned i = 1; i <= entryCount; i++) {
157         if (UString::Rep* key = m_u.table->entries()[i].key)
158             key->deref();
159     }
160     fastFree(m_u.table);
161 }
162
163 void PropertyMap::clear()
164 {
165     if (!m_usingTable) {
166 #if USE_SINGLE_ENTRY
167         if (m_singleEntryKey) {
168             m_singleEntryKey->deref();
169             m_singleEntryKey = 0;
170         }
171 #endif
172         return;
173     }
174
175     unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
176     for (unsigned i = 1; i <= entryCount; i++) {
177         if (UString::Rep* key = m_u.table->entries()[i].key)
178             key->deref();
179     }
180     for (unsigned i = 0; i < m_u.table->size; i++)
181         m_u.table->entryIndicies[i] = emptyEntryIndex;
182     m_u.table->keyCount = 0;
183     m_u.table->deletedSentinelCount = 0;
184 }
185
186 JSValue* PropertyMap::get(const Identifier& name, unsigned& attributes) const
187 {
188     ASSERT(!name.isNull());
189     
190     UString::Rep* rep = name._ustring.rep();
191     
192     if (!m_usingTable) {
193 #if USE_SINGLE_ENTRY
194         if (rep == m_singleEntryKey) {
195             attributes = m_singleEntryAttributes;
196             return m_u.singleEntryValue;
197         }
198 #endif
199         return 0;
200     }
201     
202     unsigned i = rep->computedHash();
203
204 #if DUMP_PROPERTYMAP_STATS
205     ++numProbes;
206 #endif
207
208     unsigned entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
209     if (entryIndex == emptyEntryIndex)
210         return 0;
211
212     if (rep == m_u.table->entries()[entryIndex - 1].key) {
213         attributes = m_u.table->entries()[entryIndex - 1].attributes;
214         return m_u.table->entries()[entryIndex - 1].value;
215     }
216
217 #if DUMP_PROPERTYMAP_STATS
218     ++numCollisions;
219 #endif
220
221     unsigned k = 1 | doubleHash(rep->computedHash());
222
223     while (1) {
224         i += k;
225
226 #if DUMP_PROPERTYMAP_STATS
227         ++numRehashes;
228 #endif
229
230         entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
231         if (entryIndex == emptyEntryIndex)
232             return 0;
233
234         if (rep == m_u.table->entries()[entryIndex - 1].key) {
235             attributes = m_u.table->entries()[entryIndex - 1].attributes;
236             return m_u.table->entries()[entryIndex - 1].value;
237         }
238     }
239 }
240
241 JSValue* PropertyMap::get(const Identifier& name) const
242 {
243     ASSERT(!name.isNull());
244     
245     UString::Rep* rep = name._ustring.rep();
246     
247     if (!m_usingTable) {
248 #if USE_SINGLE_ENTRY
249         if (rep == m_singleEntryKey)
250             return m_u.singleEntryValue;
251 #endif
252         return 0;
253     }
254     
255     unsigned i = rep->computedHash();
256
257 #if DUMP_PROPERTYMAP_STATS
258     ++numProbes;
259 #endif
260
261     unsigned entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
262     if (entryIndex == emptyEntryIndex)
263         return 0;
264
265     if (rep == m_u.table->entries()[entryIndex - 1].key)
266         return m_u.table->entries()[entryIndex - 1].value;
267
268 #if DUMP_PROPERTYMAP_STATS
269     ++numCollisions;
270 #endif
271
272     unsigned k = 1 | doubleHash(rep->computedHash());
273
274     while (1) {
275         i += k;
276
277 #if DUMP_PROPERTYMAP_STATS
278         ++numRehashes;
279 #endif
280
281         entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
282         if (entryIndex == emptyEntryIndex)
283             return 0;
284
285         if (rep == m_u.table->entries()[entryIndex - 1].key)
286             return m_u.table->entries()[entryIndex - 1].value;
287     }
288 }
289
290 JSValue** PropertyMap::getLocation(const Identifier& name)
291 {
292     ASSERT(!name.isNull());
293     
294     UString::Rep* rep = name._ustring.rep();
295     
296     if (!m_usingTable) {
297 #if USE_SINGLE_ENTRY
298         if (rep == m_singleEntryKey)
299             return &m_u.singleEntryValue;
300 #endif
301         return 0;
302     }
303     
304     unsigned i = rep->computedHash();
305
306 #if DUMP_PROPERTYMAP_STATS
307     ++numProbes;
308 #endif
309
310     unsigned entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
311     if (entryIndex == emptyEntryIndex)
312         return 0;
313
314     if (rep == m_u.table->entries()[entryIndex - 1].key)
315         return &m_u.table->entries()[entryIndex - 1].value;
316
317 #if DUMP_PROPERTYMAP_STATS
318     ++numCollisions;
319 #endif
320
321     unsigned k = 1 | doubleHash(rep->computedHash());
322
323     while (1) {
324         i += k;
325
326 #if DUMP_PROPERTYMAP_STATS
327         ++numRehashes;
328 #endif
329
330         entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
331         if (entryIndex == emptyEntryIndex)
332             return 0;
333
334         if (rep == m_u.table->entries()[entryIndex - 1].key)
335             return &m_u.table->entries()[entryIndex - 1].value;
336     }
337 }
338
339 void PropertyMap::put(const Identifier& name, JSValue* value, unsigned attributes, bool checkReadOnly)
340 {
341     ASSERT(!name.isNull());
342     ASSERT(value);
343     
344     checkConsistency();
345
346     UString::Rep* rep = name._ustring.rep();
347     
348 #if USE_SINGLE_ENTRY
349     if (!m_usingTable) {
350         if (!m_singleEntryKey) {
351             rep->ref();
352             m_singleEntryKey = rep;
353             m_u.singleEntryValue = value;
354             m_singleEntryAttributes = static_cast<short>(attributes);
355             checkConsistency();
356             return;
357         }
358         if (rep == m_singleEntryKey && !(checkReadOnly && (m_singleEntryAttributes & ReadOnly))) {
359             m_u.singleEntryValue = value;
360             return;
361         }
362     }
363 #endif
364
365     if (!m_usingTable || (m_u.table->keyCount + m_u.table->deletedSentinelCount) * 2 >= m_u.table->size)
366         expand();
367
368     // FIXME: Consider a fast case for tables with no deleted sentinels.
369
370     unsigned i = rep->computedHash();
371     unsigned k = 0;
372     bool foundDeletedElement = false;
373     unsigned deletedElementIndex = 0; // initialize to make the compiler happy
374
375 #if DUMP_PROPERTYMAP_STATS
376     ++numProbes;
377 #endif
378
379     while (1) {
380         unsigned entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
381         if (entryIndex == emptyEntryIndex)
382             break;
383
384         if (m_u.table->entries()[entryIndex - 1].key == rep) {
385             if (checkReadOnly && (m_u.table->entries()[entryIndex - 1].attributes & ReadOnly)) 
386                 return;
387             // Put a new value in an existing hash table entry.
388             m_u.table->entries()[entryIndex - 1].value = value;
389             // Attributes are intentionally not updated.
390             return;
391         } else if (entryIndex == deletedSentinelIndex) {
392             // If we find a deleted-element sentinel, remember it for use later.
393             if (!foundDeletedElement) {
394                 foundDeletedElement = true;
395                 deletedElementIndex = i;
396             }
397         }
398
399         if (k == 0) {
400             k = 1 | doubleHash(rep->computedHash());
401 #if DUMP_PROPERTYMAP_STATS
402             ++numCollisions;
403 #endif
404         }
405
406         i += k;
407
408 #if DUMP_PROPERTYMAP_STATS
409         ++numRehashes;
410 #endif
411     }
412
413     // Figure out which entry to use.
414     unsigned entryIndex = m_u.table->keyCount + m_u.table->deletedSentinelCount + 2;
415     if (foundDeletedElement) {
416         i = deletedElementIndex;
417         --m_u.table->deletedSentinelCount;
418
419         // Since we're not making the table bigger, we can't use the entry one past
420         // the end that we were planning on using, so search backwards for the empty
421         // slot that we can use. We know it will be there because we did at least one
422         // deletion in the past that left an entry empty.
423         while (m_u.table->entries()[--entryIndex - 1].key)
424             ;
425     }
426
427
428     // Create a new hash table entry.
429     m_u.table->entryIndicies[i & m_u.table->sizeMask] = entryIndex;
430
431     // Create a new hash table entry.
432     rep->ref();
433     m_u.table->entries()[entryIndex - 1].key = rep;
434     m_u.table->entries()[entryIndex - 1].value = value;
435     m_u.table->entries()[entryIndex - 1].attributes = attributes;
436     m_u.table->entries()[entryIndex - 1].index = ++m_u.table->lastIndexUsed;
437     ++m_u.table->keyCount;
438
439     checkConsistency();
440 }
441
442 void PropertyMap::insert(const Entry& entry)
443 {
444     ASSERT(m_u.table);
445
446     unsigned i = entry.key->computedHash();
447     unsigned k = 0;
448
449 #if DUMP_PROPERTYMAP_STATS
450     ++numProbes;
451 #endif
452
453     while (1) {
454         unsigned entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
455         if (entryIndex == emptyEntryIndex)
456             break;
457
458         if (k == 0) {
459             k = 1 | doubleHash(entry.key->computedHash());
460 #if DUMP_PROPERTYMAP_STATS
461             ++numCollisions;
462 #endif
463         }
464
465         i += k;
466
467 #if DUMP_PROPERTYMAP_STATS
468         ++numRehashes;
469 #endif
470     }
471
472     unsigned entryIndex = m_u.table->keyCount + 2;
473     m_u.table->entryIndicies[i & m_u.table->sizeMask] = entryIndex;
474     m_u.table->entries()[entryIndex - 1] = entry;
475     ++m_u.table->keyCount;
476 }
477
478 void PropertyMap::expand()
479 {
480     if (!m_usingTable)
481         createTable();
482     else
483         rehash(m_u.table->size * 2);
484 }
485
486 void PropertyMap::rehash()
487 {
488     ASSERT(m_usingTable);
489     ASSERT(m_u.table);
490     ASSERT(m_u.table->size);
491     rehash(m_u.table->size);
492 }
493
494 void PropertyMap::createTable()
495 {
496     const unsigned newTableSize = 16;
497
498     ASSERT(!m_usingTable);
499
500     checkConsistency();
501
502 #if USE_SINGLE_ENTRY
503     JSValue* oldSingleEntryValue = m_u.singleEntryValue;
504 #endif
505
506     m_u.table = static_cast<Table*>(fastZeroedMalloc(Table::allocationSize(newTableSize)));
507     m_u.table->size = newTableSize;
508     m_u.table->sizeMask = newTableSize - 1;
509     m_usingTable = true;
510
511 #if USE_SINGLE_ENTRY
512     if (m_singleEntryKey) {
513         insert(Entry(m_singleEntryKey, oldSingleEntryValue, m_singleEntryAttributes));
514         m_singleEntryKey = 0;
515     }
516 #endif
517
518     checkConsistency();
519 }
520
521 void PropertyMap::rehash(unsigned newTableSize)
522 {
523     ASSERT(!m_singleEntryKey);
524     ASSERT(m_u.table);
525     ASSERT(m_usingTable);
526
527     checkConsistency();
528
529     Table* oldTable = m_u.table;
530     
531     m_u.table = static_cast<Table*>(fastZeroedMalloc(Table::allocationSize(newTableSize)));
532     m_u.table->size = newTableSize;
533     m_u.table->sizeMask = newTableSize - 1;
534
535     unsigned lastIndexUsed = 0;
536     unsigned entryCount = oldTable->keyCount + oldTable->deletedSentinelCount;
537     for (unsigned i = 1; i <= entryCount; ++i) {
538         if (oldTable->entries()[i].key) {
539             lastIndexUsed = max(oldTable->entries()[i].index, lastIndexUsed);
540             insert(oldTable->entries()[i]);
541         }
542     }
543     m_u.table->lastIndexUsed = lastIndexUsed;
544
545     fastFree(oldTable);
546
547     checkConsistency();
548 }
549
550 void PropertyMap::remove(const Identifier& name)
551 {
552     ASSERT(!name.isNull());
553     
554     checkConsistency();
555
556     UString::Rep* rep = name._ustring.rep();
557
558     if (!m_usingTable) {
559 #if USE_SINGLE_ENTRY
560         if (rep == m_singleEntryKey) {
561             m_singleEntryKey->deref();
562             m_singleEntryKey = 0;
563             checkConsistency();
564         }
565 #endif
566         return;
567     }
568
569 #if DUMP_PROPERTYMAP_STATS
570     ++numProbes;
571     ++numRemoves;
572 #endif
573
574     // Find the thing to remove.
575     unsigned i = rep->computedHash();
576     unsigned k = 0;
577     unsigned entryIndex;
578     UString::Rep* key = 0;
579     while (1) {
580         entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
581         if (entryIndex == emptyEntryIndex)
582             return;
583
584         key = m_u.table->entries()[entryIndex - 1].key;
585         if (rep == key)
586             break;
587
588         if (k == 0) {
589             k = 1 | doubleHash(rep->computedHash());
590 #if DUMP_PROPERTYMAP_STATS
591             ++numCollisions;
592 #endif
593         }
594
595         i += k;
596
597 #if DUMP_PROPERTYMAP_STATS
598         ++numRehashes;
599 #endif
600     }
601
602     // Replace this one element with the deleted sentinel. Also clear out
603     // the entry so we can iterate all the entries as needed.
604     m_u.table->entryIndicies[i & m_u.table->sizeMask] = deletedSentinelIndex;
605     key->deref();
606     m_u.table->entries()[entryIndex - 1].key = 0;
607     m_u.table->entries()[entryIndex - 1].value = jsUndefined();
608     m_u.table->entries()[entryIndex - 1].attributes = 0;
609     ASSERT(m_u.table->keyCount >= 1);
610     --m_u.table->keyCount;
611     ++m_u.table->deletedSentinelCount;
612
613     if (m_u.table->deletedSentinelCount * 4 >= m_u.table->size)
614         rehash();
615
616     checkConsistency();
617 }
618
619 void PropertyMap::mark() const
620 {
621     if (!m_usingTable) {
622 #if USE_SINGLE_ENTRY
623         if (m_singleEntryKey) {
624             JSValue* v = m_u.singleEntryValue;
625             if (!v->marked())
626                 v->mark();
627         }
628 #endif
629         return;
630     }
631
632     unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
633     for (unsigned i = 1; i <= entryCount; i++) {
634         JSValue* v = m_u.table->entries()[i].value;
635         if (!v->marked())
636             v->mark();
637     }
638 }
639
640 static int comparePropertyMapEntryIndices(const void* a, const void* b)
641 {
642     unsigned ia = static_cast<PropertyMapEntry* const*>(a)[0]->index;
643     unsigned ib = static_cast<PropertyMapEntry* const*>(b)[0]->index;
644     if (ia < ib)
645         return -1;
646     if (ia > ib)
647         return +1;
648     return 0;
649 }
650
651 bool PropertyMap::containsGettersOrSetters() const
652 {
653     if (!m_usingTable) {
654 #if USE_SINGLE_ENTRY
655         return !!(m_singleEntryAttributes & GetterSetter);
656 #else
657         return false;
658 #endif
659     }
660
661     unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
662     for (unsigned i = 1; i <= entryCount; i++) {
663         if (m_u.table->entries()[i].attributes & GetterSetter)
664             return true;
665     }
666
667     return false;
668 }
669
670 void PropertyMap::getEnumerablePropertyNames(PropertyNameArray& propertyNames) const
671 {
672     if (!m_usingTable) {
673 #if USE_SINGLE_ENTRY
674         UString::Rep* key = m_singleEntryKey;
675         if (key && !(m_singleEntryAttributes & DontEnum))
676             propertyNames.add(Identifier(key));
677 #endif
678         return;
679     }
680
681     if (m_u.table->keyCount < tinyMapThreshold) {
682         Entry* a[tinyMapThreshold];
683         int i = 0;
684         unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
685         for (unsigned k = 1; k <= entryCount; k++) {
686             if (m_u.table->entries()[k].key && !(m_u.table->entries()[k].attributes & DontEnum)) {
687                 Entry* value = &m_u.table->entries()[k];
688                 int j;
689                 for (j = i - 1; j >= 0 && a[j]->index > value->index; --j)
690                     a[j + 1] = a[j];
691                 a[j + 1] = value;
692                 ++i;
693             }
694         }
695         for (int k = 0; k < i; ++k)
696             propertyNames.add(Identifier(a[k]->key));
697         return;
698     }
699
700     // Allocate a buffer to use to sort the keys.
701     Vector<Entry*, smallMapThreshold> sortedEnumerables(m_u.table->keyCount);
702
703     // Get pointers to the enumerable entries in the buffer.
704     Entry** p = sortedEnumerables.data();
705     unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
706     for (unsigned i = 1; i <= entryCount; i++) {
707         if (m_u.table->entries()[i].key && !(m_u.table->entries()[i].attributes & DontEnum))
708             *p++ = &m_u.table->entries()[i];
709     }
710
711     // Sort the entries by index.
712     qsort(sortedEnumerables.data(), p - sortedEnumerables.data(), sizeof(Entry*), comparePropertyMapEntryIndices);
713
714     // Put the keys of the sorted entries into the list.
715     for (Entry** q = sortedEnumerables.data(); q != p; ++q)
716         propertyNames.add(Identifier(q[0]->key));
717 }
718
719 void PropertyMap::save(SavedProperties& s) const
720 {
721     unsigned count = 0;
722
723     if (!m_usingTable) {
724 #if USE_SINGLE_ENTRY
725         if (m_singleEntryKey && !(m_singleEntryAttributes & (ReadOnly | Function)))
726             ++count;
727 #endif
728     } else {
729         unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
730         for (unsigned i = 1; i <= entryCount; ++i)
731             if (m_u.table->entries()[i].key && !(m_u.table->entries()[i].attributes & (ReadOnly | Function)))
732                 ++count;
733     }
734
735     s.properties.clear();
736     s.count = count;
737
738     if (count == 0)
739         return;
740     
741     s.properties.set(new SavedProperty[count]);
742     
743     SavedProperty* prop = s.properties.get();
744     
745 #if USE_SINGLE_ENTRY
746     if (!m_usingTable) {
747         prop->init(m_singleEntryKey, m_u.singleEntryValue, m_singleEntryAttributes);
748         return;
749     }
750 #endif
751
752     // Save in the right order so we don't lose the order.
753     // Another possibility would be to save the indices.
754
755     // Allocate a buffer to use to sort the keys.
756     Vector<Entry*, smallMapThreshold> sortedEntries(count);
757
758     // Get pointers to the entries in the buffer.
759     Entry** p = sortedEntries.data();
760     unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
761     for (unsigned i = 1; i <= entryCount; ++i) {
762         if (m_u.table->entries()[i].key && !(m_u.table->entries()[i].attributes & (ReadOnly | Function)))
763             *p++ = &m_u.table->entries()[i];
764     }
765     ASSERT(p == sortedEntries.data() + count);
766
767     // Sort the entries by index.
768     qsort(sortedEntries.data(), p - sortedEntries.data(), sizeof(Entry*), comparePropertyMapEntryIndices);
769
770     // Put the sorted entries into the saved properties list.
771     for (Entry** q = sortedEntries.data(); q != p; ++q, ++prop) {
772         Entry* e = *q;
773         prop->init(e->key, e->value, e->attributes);
774     }
775 }
776
777 void PropertyMap::restore(const SavedProperties& p)
778 {
779     for (unsigned i = 0; i != p.count; ++i)
780         put(Identifier(p.properties[i].name()), p.properties[i].value(), p.properties[i].attributes());
781 }
782
783 #if DO_PROPERTYMAP_CONSTENCY_CHECK
784
785 void PropertyMap::checkConsistency()
786 {
787     if (!m_usingTable)
788         return;
789
790     ASSERT(m_u.table->size >= 16);
791     ASSERT(m_u.table->sizeMask);
792     ASSERT(m_u.table->size == m_u.table->sizeMask + 1);
793     ASSERT(!(m_u.table->size & m_u.table->sizeMask));
794
795     ASSERT(m_u.table->keyCount <= m_u.table->size / 2);
796     ASSERT(m_u.table->deletedSentinelCount <= m_u.table->size / 4);
797
798     ASSERT(m_u.table->keyCount + m_u.table->deletedSentinelCount <= m_u.table->size / 2);
799
800     unsigned indexCount = 0;
801     unsigned deletedIndexCount = 0;
802     for (unsigned a = 0; a != m_u.table->size; ++a) {
803         unsigned entryIndex = m_u.table->entryIndicies[a];
804         if (entryIndex == emptyEntryIndex)
805             continue;
806         if (entryIndex == deletedSentinelIndex) {
807             ++deletedIndexCount;
808             continue;
809         }
810         ASSERT(entryIndex > deletedSentinelIndex);
811         ASSERT(entryIndex - 1 <= m_u.table->keyCount + m_u.table->deletedSentinelCount);
812         ++indexCount;
813
814         for (unsigned b = a + 1; b != m_u.table->size; ++b)
815             ASSERT(m_u.table->entryIndicies[b] != entryIndex);
816     }
817     ASSERT(indexCount == m_u.table->keyCount);
818     ASSERT(deletedIndexCount == m_u.table->deletedSentinelCount);
819
820     ASSERT(m_u.table->entries()[0].key == 0);
821
822     unsigned nonEmptyEntryCount = 0;
823     for (unsigned c = 1; c <= m_u.table->keyCount + m_u.table->deletedSentinelCount; ++c) {
824         UString::Rep* rep = m_u.table->entries()[c].key;
825         if (!rep) {
826             ASSERT(m_u.table->entries()[c].value->isUndefined());
827             continue;
828         }
829         ++nonEmptyEntryCount;
830         unsigned i = rep->computedHash();
831         unsigned k = 0;
832         unsigned entryIndex;
833         while (1) {
834             entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
835             ASSERT(entryIndex != emptyEntryIndex);
836             if (rep == m_u.table->entries()[entryIndex - 1].key)
837                 break;
838             if (k == 0)
839                 k = 1 | doubleHash(rep->computedHash());
840             i += k;
841         }
842         ASSERT(entryIndex == c + 1);
843     }
844
845     ASSERT(nonEmptyEntryCount == m_u.table->keyCount);
846 }
847
848 #endif // DO_PROPERTYMAP_CONSTENCY_CHECK
849
850 } // namespace KJS