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
32using 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
46namespace 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.
50const int smallMapThreshold = 1024;
51
52#if DUMP_STATISTICS
53
54static int numProbes;
55static int numCollisions;
56static int numRehashes;
57static int numRemoves;
58
59struct PropertyMapStatisticsExitLogger { ~PropertyMapStatisticsExitLogger(); };
60
61static PropertyMapStatisticsExitLogger logger;
62
63PropertyMapStatisticsExitLogger::~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.
78struct PropertyMapHashTable
79{
80 int sizeMask;
81 int size;
82 int keyCount;
83 int sentinelCount;
84 int lastIndexUsed;
85 PropertyMapHashTableEntry entries[1];
86};
87
88class SavedProperty {
89public:
90 Identifier key;
91 ProtectedPtr<JSValue> value;
92 int attributes;
93};
94
95SavedProperties::SavedProperties() : _count(0) { }
96SavedProperties::~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>
101static 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
104static inline bool isValid(UString::Rep* key)
105{
106 return !!(reinterpret_cast<uintptr_t>(key) & ~0x1);
107}
108
109PropertyMap::~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
133void 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
160bool PropertyMap::isEmpty() const
161{
162 if (!m_usingTable)
163 return !m_singleEntryKey;
164 else
165 return !m_u.table->keyCount;
166}
167
168JSValue *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
209JSValue *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
246JSValue **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
283JSValue **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
323static 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
342void 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
429void 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
458void PropertyMap::expand()
459{
460 if (!m_usingTable)
461 createTable();
462 else
463 rehash(m_u.table->size * 2);
464}
465
466void 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
474void 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
503void 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
537void 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
600void 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
626static 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
637bool 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
655void 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
687void 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
754void 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
762void 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