284cdfff8dfe422cd17a8486b4ea91f225426e91
[WebKit-https.git] / JavaScriptCore / kjs / property_map.cpp
1 /*
2  *  Copyright (C) 2004, 2005, 2006, 2007 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     : m_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 &p) 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     p.m_properties.clear();
736     p.m_count = count;
737
738     if (count == 0)
739         return;
740     
741     p.m_properties.set(new SavedProperty [count]);
742     
743     SavedProperty* prop = p.m_properties.get();
744     
745     if (!m_usingTable) {
746 #if USE_SINGLE_ENTRY
747         if (m_singleEntryKey && !(m_singleEntryAttributes & (ReadOnly | Function))) {
748             prop->key = Identifier(m_singleEntryKey);
749             prop->value = m_u.singleEntryValue;
750             prop->attributes = m_singleEntryAttributes;
751             ++prop;
752         }
753 #endif
754     } else {
755         // Save in the right order so we don't lose the order.
756         // Another possibility would be to save the indices.
757
758         // Allocate a buffer to use to sort the keys.
759         Vector<Entry*, smallMapThreshold> sortedEntries(count);
760
761         // Get pointers to the entries in the buffer.
762         Entry** p = sortedEntries.data();
763         unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
764         for (unsigned i = 1; i <= entryCount; ++i) {
765             if (m_u.table->entries()[i].key && !(m_u.table->entries()[i].attributes & (ReadOnly | Function)))
766                 *p++ = &m_u.table->entries()[i];
767         }
768         ASSERT(p == sortedEntries.data() + count);
769
770         // Sort the entries by index.
771         qsort(sortedEntries.data(), p - sortedEntries.data(), sizeof(Entry*), comparePropertyMapEntryIndices);
772
773         // Put the sorted entries into the saved properties list.
774         for (Entry** q = sortedEntries.data(); q != p; ++q, ++prop) {
775             Entry* e = *q;
776             prop->key = Identifier(e->key);
777             prop->value = e->value;
778             prop->attributes = e->attributes;
779         }
780     }
781 }
782
783 void PropertyMap::restore(const SavedProperties &p)
784 {
785     for (unsigned i = 0; i != p.m_count; ++i)
786         put(p.m_properties[i].key, p.m_properties[i].value, p.m_properties[i].attributes);
787 }
788
789 #if DO_PROPERTYMAP_CONSTENCY_CHECK
790
791 void PropertyMap::checkConsistency()
792 {
793     if (!m_usingTable)
794         return;
795
796     ASSERT(m_u.table->size >= 16);
797     ASSERT(m_u.table->sizeMask);
798     ASSERT(m_u.table->size == m_u.table->sizeMask + 1);
799     ASSERT(!(m_u.table->size & m_u.table->sizeMask));
800
801     ASSERT(m_u.table->keyCount <= m_u.table->size / 2);
802     ASSERT(m_u.table->deletedSentinelCount <= m_u.table->size / 4);
803
804     ASSERT(m_u.table->keyCount + m_u.table->deletedSentinelCount <= m_u.table->size / 2);
805
806     unsigned indexCount = 0;
807     unsigned deletedIndexCount = 0;
808     for (unsigned a = 0; a != m_u.table->size; ++a) {
809         unsigned entryIndex = m_u.table->entryIndicies[a];
810         if (entryIndex == emptyEntryIndex)
811             continue;
812         if (entryIndex == deletedSentinelIndex) {
813             ++deletedIndexCount;
814             continue;
815         }
816         ASSERT(entryIndex > deletedSentinelIndex);
817         ASSERT(entryIndex - 1 <= m_u.table->keyCount + m_u.table->deletedSentinelCount);
818         ++indexCount;
819
820         for (unsigned b = a + 1; b != m_u.table->size; ++b)
821             ASSERT(m_u.table->entryIndicies[b] != entryIndex);
822     }
823     ASSERT(indexCount == m_u.table->keyCount);
824     ASSERT(deletedIndexCount == m_u.table->deletedSentinelCount);
825
826     ASSERT(m_u.table->entries()[0].key == 0);
827
828     unsigned nonEmptyEntryCount = 0;
829     for (unsigned c = 1; c <= m_u.table->keyCount + m_u.table->deletedSentinelCount; ++c) {
830         UString::Rep* rep = m_u.table->entries()[c].key;
831         if (!rep) {
832             ASSERT(m_u.table->entries()[c].value->isUndefined());
833             continue;
834         }
835         ++nonEmptyEntryCount;
836         unsigned i = rep->computedHash();
837         unsigned k = 0;
838         unsigned entryIndex;
839         while (1) {
840             entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
841             ASSERT(entryIndex != emptyEntryIndex);
842             if (rep == m_u.table->entries()[entryIndex - 1].key)
843                 break;
844             if (k == 0)
845                 k = 1 | doubleHash(rep->computedHash());
846             i += k;
847         }
848         ASSERT(entryIndex == c + 1);
849     }
850
851     ASSERT(nonEmptyEntryCount == m_u.table->keyCount);
852 }
853
854 #endif // DO_PROPERTYMAP_CONSTENCY_CHECK
855
856 } // namespace KJS