1 | /* |
2 | * This file is part of the KDE libraries |
3 | * Copyright (C) 2004, 2005, 2006 Apple Computer, Inc. |
4 | * |
5 | * This library is free software; you can redistribute it and/or |
6 | * modify it under the terms of the GNU Library General Public |
7 | * License as published by the Free Software Foundation; either |
8 | * version 2 of the License, or (at your option) any later version. |
9 | * |
10 | * This library is distributed in the hope that it will be useful, |
11 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
12 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
13 | * Library General Public License for more details. |
14 | * |
15 | * You should have received a copy of the GNU Library General Public License |
16 | * along with this library; see the file COPYING.LIB. If not, write to |
17 | * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, |
18 | * Boston, MA 02110-1301, USA. |
19 | * |
20 | */ |
21 | |
22 | #include "property_map.h" |
23 | #include <config-kjs.h> |
24 | |
25 | #include "object.h" |
26 | #include "protect.h" |
27 | #include "PropertyNameArray.h" |
28 | #include <algorithm> |
29 | #include <wtf/FastMalloc.h> |
30 | #include <wtf/Vector.h> |
31 | |
32 | using std::max; |
33 | |
34 | #define DEBUG_PROPERTIES 0 |
35 | #define DO_CONSISTENCY_CHECK 0 |
36 | #define DUMP_STATISTICS 0 |
37 | #define USE_SINGLE_ENTRY 1 |
38 | |
39 | // 2/28/2006 ggaren: super accurate JS iBench says that USE_SINGLE_ENTRY is a |
40 | // 3.2% performance boost. |
41 | |
42 | #if !DO_CONSISTENCY_CHECK |
43 | #define checkConsistency() ((void)0) |
44 | #endif |
45 | |
46 | namespace KJS { |
47 | |
48 | // Choose a number for the following so that most property maps are smaller, |
49 | // but it's not going to blow out the stack to allocate this number of pointers. |
50 | const int smallMapThreshold = 1024; |
51 | |
52 | #if DUMP_STATISTICS |
53 | |
54 | static int numProbes; |
55 | static int numCollisions; |
56 | static int numRehashes; |
57 | static int numRemoves; |
58 | |
59 | struct PropertyMapStatisticsExitLogger { ~PropertyMapStatisticsExitLogger(); }; |
60 | |
61 | static PropertyMapStatisticsExitLogger logger; |
62 | |
63 | PropertyMapStatisticsExitLogger::~PropertyMapStatisticsExitLogger() |
64 | { |
65 | printf("\nKJS::PropertyMap statistics\n\n" ); |
66 | printf("%d probes\n" , numProbes); |
67 | printf("%d collisions (%.1f%%)\n" , numCollisions, 100.0 * numCollisions / numProbes); |
68 | printf("%d rehashes\n" , numRehashes); |
69 | printf("%d removes\n" , numRemoves); |
70 | } |
71 | |
72 | #endif |
73 | |
74 | // lastIndexUsed is an ever-increasing index used to identify the order items |
75 | // were inserted into the property map. It's vital that getEnumerablePropertyNames |
76 | // return the properties in the order they were added for compatibility with other |
77 | // browsers' JavaScript implementations. |
78 | struct PropertyMapHashTable |
79 | { |
80 | int sizeMask; |
81 | int size; |
82 | int keyCount; |
83 | int sentinelCount; |
84 | int lastIndexUsed; |
85 | PropertyMapHashTableEntry entries[1]; |
86 | }; |
87 | |
88 | class SavedProperty { |
89 | public: |
90 | Identifier key; |
91 | ProtectedPtr<JSValue> value; |
92 | int attributes; |
93 | }; |
94 | |
95 | SavedProperties::SavedProperties() : _count(0) { } |
96 | SavedProperties::~SavedProperties() { } |
97 | |
98 | // Algorithm concepts from Algorithms in C++, Sedgewick. |
99 | |
100 | // This is a method rather than a variable to work around <rdar://problem/4462053> |
101 | static inline UString::Rep* deletedSentinel() { return reinterpret_cast<UString::Rep*>(0x1); } |
102 | |
103 | // Returns true if the key is not null or the deleted sentinel, false otherwise |
104 | static inline bool isValid(UString::Rep* key) |
105 | { |
106 | return !!(reinterpret_cast<uintptr_t>(key) & ~0x1); |
107 | } |
108 | |
109 | PropertyMap::~PropertyMap() |
110 | { |
111 | if (!m_usingTable) { |
112 | #if USE_SINGLE_ENTRY |
113 | UString::Rep *key = m_singleEntryKey; |
114 | if (key) |
115 | key->deref(); |
116 | #endif |
117 | return; |
118 | } |
119 | |
120 | int minimumKeysToProcess = m_u.table->keyCount + m_u.table->sentinelCount; |
121 | Entry *entries = m_u.table->entries; |
122 | for (int i = 0; i < minimumKeysToProcess; i++) { |
123 | UString::Rep *key = entries[i].key; |
124 | if (key) { |
125 | if (key != deletedSentinel()) |
126 | key->deref(); |
127 | } else |
128 | ++minimumKeysToProcess; |
129 | } |
130 | fastFree(m_u.table); |
131 | } |
132 | |
133 | void PropertyMap::clear() |
134 | { |
135 | if (!m_usingTable) { |
136 | #if USE_SINGLE_ENTRY |
137 | UString::Rep *key = m_singleEntryKey; |
138 | if (key) { |
139 | key->deref(); |
140 | m_singleEntryKey = 0; |
141 | } |
142 | #endif |
143 | return; |
144 | } |
145 | |
146 | int size = m_u.table->size; |
147 | Entry *entries = m_u.table->entries; |
148 | for (int i = 0; i < size; i++) { |
149 | UString::Rep *key = entries[i].key; |
150 | if (isValid(key)) { |
151 | key->deref(); |
152 | entries[i].key = 0; |
153 | entries[i].value = 0; |
154 | } |
155 | } |
156 | m_u.table->keyCount = 0; |
157 | m_u.table->sentinelCount = 0; |
158 | } |
159 | |
160 | bool PropertyMap::isEmpty() const |
161 | { |
162 | if (!m_usingTable) |
163 | return !m_singleEntryKey; |
164 | else |
165 | return !m_u.table->keyCount; |
166 | } |
167 | |
168 | JSValue *PropertyMap::get(const Identifier &name, unsigned &attributes) const |
169 | { |
170 | assert(!name.isNull()); |
171 | |
172 | UString::Rep *rep = name._ustring.rep(); |
173 | |
174 | if (!m_usingTable) { |
175 | #if USE_SINGLE_ENTRY |
176 | UString::Rep *key = m_singleEntryKey; |
177 | if (rep == key) { |
178 | attributes = m_singleEntryAttributes; |
179 | return m_u.singleEntryValue; |
180 | } |
181 | #endif |
182 | return 0; |
183 | } |
184 | |
185 | unsigned h = rep->hash(); |
186 | int sizeMask = m_u.table->sizeMask; |
187 | Entry *entries = m_u.table->entries; |
188 | int i = h & sizeMask; |
189 | int k = 0; |
190 | #if DUMP_STATISTICS |
191 | ++numProbes; |
192 | numCollisions += entries[i].key && entries[i].key != rep; |
193 | #endif |
194 | while (UString::Rep *key = entries[i].key) { |
195 | if (rep == key) { |
196 | attributes = entries[i].attributes; |
197 | return entries[i].value; |
198 | } |
199 | if (k == 0) |
200 | k = 1 | (h % sizeMask); |
201 | i = (i + k) & sizeMask; |
202 | #if DUMP_STATISTICS |
203 | ++numRehashes; |
204 | #endif |
205 | } |
206 | return 0; |
207 | } |
208 | |
209 | JSValue *PropertyMap::get(const Identifier &name) const |
210 | { |
211 | assert(!name.isNull()); |
212 | |
213 | UString::Rep *rep = name._ustring.rep(); |
214 | |
215 | if (!m_usingTable) { |
216 | #if USE_SINGLE_ENTRY |
217 | UString::Rep *key = m_singleEntryKey; |
218 | if (rep == key) |
219 | return m_u.singleEntryValue; |
220 | #endif |
221 | return 0; |
222 | } |
223 | |
224 | unsigned h = rep->hash(); |
225 | int sizeMask = m_u.table->sizeMask; |
226 | Entry *entries = m_u.table->entries; |
227 | int i = h & sizeMask; |
228 | int k = 0; |
229 | #if DUMP_STATISTICS |
230 | ++numProbes; |
231 | numCollisions += entries[i].key && entries[i].key != rep; |
232 | #endif |
233 | while (UString::Rep *key = entries[i].key) { |
234 | if (rep == key) |
235 | return entries[i].value; |
236 | if (k == 0) |
237 | k = 1 | (h % sizeMask); |
238 | i = (i + k) & sizeMask; |
239 | #if DUMP_STATISTICS |
240 | ++numRehashes; |
241 | #endif |
242 | } |
243 | return 0; |
244 | } |
245 | |
246 | JSValue **PropertyMap::getLocation(const Identifier &name) |
247 | { |
248 | assert(!name.isNull()); |
249 | |
250 | UString::Rep *rep = name._ustring.rep(); |
251 | |
252 | if (!m_usingTable) { |
253 | #if USE_SINGLE_ENTRY |
254 | UString::Rep *key = m_singleEntryKey; |
255 | if (rep == key) |
256 | return &m_u.singleEntryValue; |
257 | #endif |
258 | return 0; |
259 | } |
260 | |
261 | unsigned h = rep->hash(); |
262 | int sizeMask = m_u.table->sizeMask; |
263 | Entry *entries = m_u.table->entries; |
264 | int i = h & sizeMask; |
265 | int k = 0; |
266 | #if DUMP_STATISTICS |
267 | ++numProbes; |
268 | numCollisions += entries[i].key && entries[i].key != rep; |
269 | #endif |
270 | while (UString::Rep *key = entries[i].key) { |
271 | if (rep == key) |
272 | return &entries[i].value; |
273 | if (k == 0) |
274 | k = 1 | (h % sizeMask); |
275 | i = (i + k) & sizeMask; |
276 | #if DUMP_STATISTICS |
277 | ++numRehashes; |
278 | #endif |
279 | } |
280 | return 0; |
281 | } |
282 | |
283 | JSValue **PropertyMap::getWriteLocation(const Identifier &name) |
284 | { |
285 | assert(!name.isNull()); |
286 | |
287 | UString::Rep *rep = name._ustring.rep(); |
288 | |
289 | if (!m_usingTable) { |
290 | UString::Rep *key = m_singleEntryKey; |
291 | if (rep == key && !(m_singleEntryAttributes & (ReadOnly | GetterSetter))) |
292 | return &m_u.singleEntryValue; |
293 | return 0; |
294 | } |
295 | |
296 | unsigned h = rep->hash(); |
297 | int sizeMask = m_u.table->sizeMask; |
298 | Entry *entries = m_u.table->entries; |
299 | int i = h & sizeMask; |
300 | int k = 0; |
301 | #if DUMP_STATISTICS |
302 | ++numProbes; |
303 | numCollisions += entries[i].key && entries[i].key != rep; |
304 | #endif |
305 | while (UString::Rep *key = entries[i].key) { |
306 | if (rep == key) { |
307 | if (entries[i].attributes & (ReadOnly | GetterSetter)) |
308 | return 0; |
309 | else |
310 | return &entries[i].value; |
311 | } |
312 | if (k == 0) |
313 | k = 1 | (h % sizeMask); |
314 | i = (i + k) & sizeMask; |
315 | #if DUMP_STATISTICS |
316 | ++numRehashes; |
317 | #endif |
318 | } |
319 | return 0; |
320 | } |
321 | |
322 | #if DEBUG_PROPERTIES |
323 | static void printAttributes(int attributes) |
324 | { |
325 | if (attributes == 0) |
326 | printf("None" ); |
327 | else { |
328 | if (attributes & ReadOnly) |
329 | printf("ReadOnly " ); |
330 | if (attributes & DontEnum) |
331 | printf("DontEnum " ); |
332 | if (attributes & DontDelete) |
333 | printf("DontDelete " ); |
334 | if (attributes & Internal) |
335 | printf("Internal " ); |
336 | if (attributes & Function) |
337 | printf("Function " ); |
338 | } |
339 | } |
340 | #endif |
341 | |
342 | void PropertyMap::put(const Identifier &name, JSValue *value, int attributes, bool roCheck) |
343 | { |
344 | assert(!name.isNull()); |
345 | assert(value != 0); |
346 | |
347 | checkConsistency(); |
348 | |
349 | UString::Rep *rep = name._ustring.rep(); |
350 | |
351 | #if DEBUG_PROPERTIES |
352 | printf("adding property %s, attributes = 0x%08x (" , name.ascii(), attributes); |
353 | printAttributes(attributes); |
354 | printf(")\n" ); |
355 | #endif |
356 | |
357 | #if USE_SINGLE_ENTRY |
358 | if (!m_usingTable) { |
359 | UString::Rep *key = m_singleEntryKey; |
360 | if (key) { |
361 | if (rep == key && !(roCheck && (m_singleEntryAttributes & ReadOnly))) { |
362 | m_u.singleEntryValue = value; |
363 | return; |
364 | } |
365 | } else { |
366 | rep->ref(); |
367 | m_singleEntryKey = rep; |
368 | m_u.singleEntryValue = value; |
369 | m_singleEntryAttributes = static_cast<short>(attributes); |
370 | checkConsistency(); |
371 | return; |
372 | } |
373 | } |
374 | #endif |
375 | |
376 | if (!m_usingTable || m_u.table->keyCount * 2 >= m_u.table->size) |
377 | expand(); |
378 | |
379 | unsigned h = rep->hash(); |
380 | int sizeMask = m_u.table->sizeMask; |
381 | Entry *entries = m_u.table->entries; |
382 | int i = h & sizeMask; |
383 | int k = 0; |
384 | bool foundDeletedElement = false; |
385 | int deletedElementIndex = 0; /* initialize to make the compiler happy */ |
386 | #if DUMP_STATISTICS |
387 | ++numProbes; |
388 | numCollisions += entries[i].key && entries[i].key != rep; |
389 | #endif |
390 | while (UString::Rep *key = entries[i].key) { |
391 | if (rep == key) { |
392 | if (roCheck && (entries[i].attributes & ReadOnly)) |
393 | return; |
394 | // Put a new value in an existing hash table entry. |
395 | entries[i].value = value; |
396 | // Attributes are intentionally not updated. |
397 | return; |
398 | } |
399 | // If we find the deleted-element sentinel, remember it for use later. |
400 | if (key == deletedSentinel() && !foundDeletedElement) { |
401 | foundDeletedElement = true; |
402 | deletedElementIndex = i; |
403 | } |
404 | if (k == 0) |
405 | k = 1 | (h % sizeMask); |
406 | i = (i + k) & sizeMask; |
407 | #if DUMP_STATISTICS |
408 | ++numRehashes; |
409 | #endif |
410 | } |
411 | |
412 | // Use either the deleted element or the 0 at the end of the chain. |
413 | if (foundDeletedElement) { |
414 | i = deletedElementIndex; |
415 | --m_u.table->sentinelCount; |
416 | } |
417 | |
418 | // Create a new hash table entry. |
419 | rep->ref(); |
420 | entries[i].key = rep; |
421 | entries[i].value = value; |
422 | entries[i].attributes = attributes; |
423 | entries[i].index = ++m_u.table->lastIndexUsed; |
424 | ++m_u.table->keyCount; |
425 | |
426 | checkConsistency(); |
427 | } |
428 | |
429 | void PropertyMap::insert(UString::Rep *key, JSValue *value, int attributes, int index) |
430 | { |
431 | assert(m_u.table); |
432 | |
433 | unsigned h = key->hash(); |
434 | int sizeMask = m_u.table->sizeMask; |
435 | Entry *entries = m_u.table->entries; |
436 | int i = h & sizeMask; |
437 | int k = 0; |
438 | #if DUMP_STATISTICS |
439 | ++numProbes; |
440 | numCollisions += entries[i].key && entries[i].key != key; |
441 | #endif |
442 | while (entries[i].key) { |
443 | assert(entries[i].key != deletedSentinel()); |
444 | if (k == 0) |
445 | k = 1 | (h % sizeMask); |
446 | i = (i + k) & sizeMask; |
447 | #if DUMP_STATISTICS |
448 | ++numRehashes; |
449 | #endif |
450 | } |
451 | |
452 | entries[i].key = key; |
453 | entries[i].value = value; |
454 | entries[i].attributes = attributes; |
455 | entries[i].index = index; |
456 | } |
457 | |
458 | void PropertyMap::expand() |
459 | { |
460 | if (!m_usingTable) |
461 | createTable(); |
462 | else |
463 | rehash(m_u.table->size * 2); |
464 | } |
465 | |
466 | void PropertyMap::rehash() |
467 | { |
468 | ASSERT(m_usingTable); |
469 | ASSERT(m_u.table); |
470 | ASSERT(m_u.table->size); |
471 | rehash(m_u.table->size); |
472 | } |
473 | |
474 | void PropertyMap::createTable() |
475 | { |
476 | const int newTableSize = 16; |
477 | |
478 | ASSERT(!m_usingTable); |
479 | |
480 | checkConsistency(); |
481 | |
482 | #if USE_SINGLE_ENTRY |
483 | JSValue* oldSingleEntryValue = m_u.singleEntryValue; |
484 | #endif |
485 | |
486 | m_u.table = (Table *)fastCalloc(1, sizeof(Table) + (newTableSize - 1) * sizeof(Entry)); |
487 | m_u.table->size = newTableSize; |
488 | m_u.table->sizeMask = newTableSize - 1; |
489 | m_usingTable = true; |
490 | |
491 | #if USE_SINGLE_ENTRY |
492 | UString::Rep *key = m_singleEntryKey; |
493 | if (key) { |
494 | insert(key, oldSingleEntryValue, m_singleEntryAttributes, 0); |
495 | m_singleEntryKey = 0; |
496 | m_u.table->keyCount = 1; |
497 | } |
498 | #endif |
499 | |
500 | checkConsistency(); |
501 | } |
502 | |
503 | void PropertyMap::rehash(int newTableSize) |
504 | { |
505 | ASSERT(!m_singleEntryKey); |
506 | ASSERT(m_u.table); |
507 | ASSERT(m_usingTable); |
508 | |
509 | checkConsistency(); |
510 | |
511 | Table* oldTable = m_u.table; |
512 | int oldTableSize = oldTable->size; |
513 | int oldTableKeyCount = oldTable->keyCount; |
514 | |
515 | m_u.table = (Table *)fastCalloc(1, sizeof(Table) + (newTableSize - 1) * sizeof(Entry)); |
516 | m_u.table->size = newTableSize; |
517 | m_u.table->sizeMask = newTableSize - 1; |
518 | m_u.table->keyCount = oldTableKeyCount; |
519 | |
520 | int lastIndexUsed = 0; |
521 | for (int i = 0; i != oldTableSize; ++i) { |
522 | Entry &entry = oldTable->entries[i]; |
523 | UString::Rep *key = entry.key; |
524 | if (isValid(key)) { |
525 | int index = entry.index; |
526 | lastIndexUsed = max(index, lastIndexUsed); |
527 | insert(key, entry.value, entry.attributes, index); |
528 | } |
529 | } |
530 | m_u.table->lastIndexUsed = lastIndexUsed; |
531 | |
532 | fastFree(oldTable); |
533 | |
534 | checkConsistency(); |
535 | } |
536 | |
537 | void PropertyMap::remove(const Identifier &name) |
538 | { |
539 | assert(!name.isNull()); |
540 | |
541 | checkConsistency(); |
542 | |
543 | UString::Rep *rep = name._ustring.rep(); |
544 | |
545 | UString::Rep *key; |
546 | |
547 | if (!m_usingTable) { |
548 | #if USE_SINGLE_ENTRY |
549 | key = m_singleEntryKey; |
550 | if (rep == key) { |
551 | key->deref(); |
552 | m_singleEntryKey = 0; |
553 | checkConsistency(); |
554 | } |
555 | #endif |
556 | return; |
557 | } |
558 | |
559 | // Find the thing to remove. |
560 | unsigned h = rep->hash(); |
561 | int sizeMask = m_u.table->sizeMask; |
562 | Entry *entries = m_u.table->entries; |
563 | int i = h & sizeMask; |
564 | int k = 0; |
565 | #if DUMP_STATISTICS |
566 | ++numProbes; |
567 | ++numRemoves; |
568 | numCollisions += entries[i].key && entries[i].key != rep; |
569 | #endif |
570 | while ((key = entries[i].key)) { |
571 | if (rep == key) |
572 | break; |
573 | if (k == 0) |
574 | k = 1 | (h % sizeMask); |
575 | i = (i + k) & sizeMask; |
576 | #if DUMP_STATISTICS |
577 | ++numRehashes; |
578 | #endif |
579 | } |
580 | if (!key) |
581 | return; |
582 | |
583 | // Replace this one element with the deleted sentinel. Also set value to 0 and attributes to DontEnum |
584 | // to help callers that iterate all keys not have to check for the sentinel. |
585 | key->deref(); |
586 | key = deletedSentinel(); |
587 | entries[i].key = key; |
588 | entries[i].value = 0; |
589 | entries[i].attributes = DontEnum; |
590 | assert(m_u.table->keyCount >= 1); |
591 | --m_u.table->keyCount; |
592 | ++m_u.table->sentinelCount; |
593 | |
594 | if (m_u.table->sentinelCount * 4 >= m_u.table->size) |
595 | rehash(); |
596 | |
597 | checkConsistency(); |
598 | } |
599 | |
600 | void PropertyMap::mark() const |
601 | { |
602 | if (!m_usingTable) { |
603 | #if USE_SINGLE_ENTRY |
604 | if (m_singleEntryKey) { |
605 | JSValue *v = m_u.singleEntryValue; |
606 | if (!v->marked()) |
607 | v->mark(); |
608 | } |
609 | #endif |
610 | return; |
611 | } |
612 | |
613 | int minimumKeysToProcess = m_u.table->keyCount; |
614 | Entry *entries = m_u.table->entries; |
615 | for (int i = 0; i < minimumKeysToProcess; i++) { |
616 | JSValue *v = entries[i].value; |
617 | if (v) { |
618 | if (!v->marked()) |
619 | v->mark(); |
620 | } else { |
621 | ++minimumKeysToProcess; |
622 | } |
623 | } |
624 | } |
625 | |
626 | static int comparePropertyMapEntryIndices(const void *a, const void *b) |
627 | { |
628 | int ia = static_cast<PropertyMapHashTableEntry * const *>(a)[0]->index; |
629 | int ib = static_cast<PropertyMapHashTableEntry * const *>(b)[0]->index; |
630 | if (ia < ib) |
631 | return -1; |
632 | if (ia > ib) |
633 | return +1; |
634 | return 0; |
635 | } |
636 | |
637 | bool PropertyMap::containsGettersOrSetters() const |
638 | { |
639 | if (!m_usingTable) { |
640 | #if USE_SINGLE_ENTRY |
641 | return !!(m_singleEntryAttributes & GetterSetter); |
642 | #else |
643 | return false; |
644 | #endif |
645 | } |
646 | |
647 | for (int i = 0; i != m_u.table->size; ++i) { |
648 | if (m_u.table->entries[i].attributes & GetterSetter) |
649 | return true; |
650 | } |
651 | |
652 | return false; |
653 | } |
654 | |
655 | void PropertyMap::getPropertyNames(PropertyNameArray& propertyNames, PropertyMode mode) const |
656 | { |
657 | if (!m_usingTable) { |
658 | #if USE_SINGLE_ENTRY |
659 | UString::Rep *key = m_singleEntryKey; |
660 | if (key && checkEnumerable(m_singleEntryAttributes, mode)) |
661 | propertyNames.add(Identifier(key)); |
662 | #endif |
663 | return; |
664 | } |
665 | |
666 | // Allocate a buffer to use to sort the keys. |
667 | Vector<Entry*, smallMapThreshold> sortedEnumerables(m_u.table->keyCount); |
668 | |
669 | // Get pointers to the enumerable entries in the buffer. |
670 | Entry** p = sortedEnumerables.data(); |
671 | int size = m_u.table->size; |
672 | Entry* entries = m_u.table->entries; |
673 | for (int i = 0; i != size; ++i) { |
674 | Entry* e = &entries[i]; |
675 | if (e->key && checkEnumerable(e->attributes, mode)) |
676 | *p++ = e; |
677 | } |
678 | |
679 | // Sort the entries by index. |
680 | qsort(sortedEnumerables.data(), p - sortedEnumerables.data(), sizeof(Entry*), comparePropertyMapEntryIndices); |
681 | |
682 | // Put the keys of the sorted entries into the list. |
683 | for (Entry** q = sortedEnumerables.data(); q != p; ++q) |
684 | propertyNames.add(Identifier(q[0]->key)); |
685 | } |
686 | |
687 | void PropertyMap::save(SavedProperties &p) const |
688 | { |
689 | int count = 0; |
690 | |
691 | if (!m_usingTable) { |
692 | #if USE_SINGLE_ENTRY |
693 | if (m_singleEntryKey && !(m_singleEntryAttributes & (ReadOnly | Function))) |
694 | ++count; |
695 | #endif |
696 | } else { |
697 | int size = m_u.table->size; |
698 | Entry *entries = m_u.table->entries; |
699 | for (int i = 0; i != size; ++i) |
700 | if (isValid(entries[i].key) && !(entries[i].attributes & (ReadOnly | Function))) |
701 | ++count; |
702 | } |
703 | |
704 | p._properties.clear(); |
705 | p._count = count; |
706 | |
707 | if (count == 0) |
708 | return; |
709 | |
710 | p._properties.set(new SavedProperty [count]); |
711 | |
712 | SavedProperty *prop = p._properties.get(); |
713 | |
714 | if (!m_usingTable) { |
715 | #if USE_SINGLE_ENTRY |
716 | if (m_singleEntryKey && !(m_singleEntryAttributes & (ReadOnly | Function))) { |
717 | prop->key = Identifier(m_singleEntryKey); |
718 | prop->value = m_u.singleEntryValue; |
719 | prop->attributes = m_singleEntryAttributes; |
720 | ++prop; |
721 | } |
722 | #endif |
723 | } else { |
724 | // Save in the right order so we don't lose the order. |
725 | // Another possibility would be to save the indices. |
726 | |
727 | // Allocate a buffer to use to sort the keys. |
728 | Vector<Entry*, smallMapThreshold> sortedEntries(count); |
729 | |
730 | // Get pointers to the entries in the buffer. |
731 | Entry** p = sortedEntries.data(); |
732 | int size = m_u.table->size; |
733 | Entry* entries = m_u.table->entries; |
734 | for (int i = 0; i != size; ++i) { |
735 | Entry *e = &entries[i]; |
736 | if (isValid(e->key) && !(e->attributes & (ReadOnly | Function))) |
737 | *p++ = e; |
738 | } |
739 | assert(p - sortedEntries.data() == count); |
740 | |
741 | // Sort the entries by index. |
742 | qsort(sortedEntries.data(), p - sortedEntries.data(), sizeof(Entry*), comparePropertyMapEntryIndices); |
743 | |
744 | // Put the sorted entries into the saved properties list. |
745 | for (Entry** q = sortedEntries.data(); q != p; ++q, ++prop) { |
746 | Entry* e = *q; |
747 | prop->key = Identifier(e->key); |
748 | prop->value = e->value; |
749 | prop->attributes = e->attributes; |
750 | } |
751 | } |
752 | } |
753 | |
754 | void PropertyMap::restore(const SavedProperties &p) |
755 | { |
756 | for (int i = 0; i != p._count; ++i) |
757 | put(p._properties[i].key, p._properties[i].value, p._properties[i].attributes); |
758 | } |
759 | |
760 | #if DO_CONSISTENCY_CHECK |
761 | |
762 | void PropertyMap::checkConsistency() |
763 | { |
764 | if (!m_usingTable) |
765 | return; |
766 | |
767 | int count = 0; |
768 | int sentinelCount = 0; |
769 | for (int j = 0; j != m_u.table->size; ++j) { |
770 | UString::Rep *rep = m_u.table->entries[j].key; |
771 | if (!rep) |
772 | continue; |
773 | if (rep == deletedSentinel()) { |
774 | ++sentinelCount; |
775 | continue; |
776 | } |
777 | unsigned h = rep->hash(); |
778 | int i = h & m_u.table->sizeMask; |
779 | int k = 0; |
780 | while (UString::Rep *key = m_u.table->entries[i].key) { |
781 | if (rep == key) |
782 | break; |
783 | if (k == 0) |
784 | k = 1 | (h % m_u.table->sizeMask); |
785 | i = (i + k) & m_u.table->sizeMask; |
786 | } |
787 | assert(i == j); |
788 | ++count; |
789 | } |
790 | assert(count == m_u.table->keyCount); |
791 | assert(sentinelCount == m_u.table->sentinelCount); |
792 | assert(m_u.table->size >= 16); |
793 | assert(m_u.table->sizeMask); |
794 | assert(m_u.table->size == m_u.table->sizeMask + 1); |
795 | } |
796 | |
797 | #endif // DO_CONSISTENCY_CHECK |
798 | |
799 | } // namespace KJS |
800 | |