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