2 * Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
3 * Copyright (C) 2003, 2007, 2008, 2009 Apple Inc. All rights reserved.
4 * Copyright (C) 2003 Peter Kelly (pmk@post.com)
5 * Copyright (C) 2006 Alexey Proskuryakov (ap@nypop.com)
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public
9 * License as published by the Free Software Foundation; either
10 * version 2 of the License, or (at your option) any later version.
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
17 * You should have received a copy of the GNU Lesser General Public
18 * License along with this library; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
26 #include "ArrayPrototype.h"
27 #include "CachedCall.h"
29 #include "Executable.h"
30 #include "PropertyNameArray.h"
31 #include <wtf/AVLTree.h>
32 #include <wtf/Assertions.h>
33 #include <wtf/OwnPtr.h>
34 #include <Operations.h>
36 #define CHECK_ARRAY_CONSISTENCY 0
43 ASSERT_CLASS_FITS_IN_CELL(JSArray
);
45 // Overview of JSArray
47 // Properties of JSArray objects may be stored in one of three locations:
48 // * The regular JSObject property map.
49 // * A storage vector.
50 // * A sparse map of array entries.
52 // Properties with non-numeric identifiers, with identifiers that are not representable
53 // as an unsigned integer, or where the value is greater than MAX_ARRAY_INDEX
54 // (specifically, this is only one property - the value 0xFFFFFFFFU as an unsigned 32-bit
55 // integer) are not considered array indices and will be stored in the JSObject property map.
57 // All properties with a numeric identifer, representable as an unsigned integer i,
58 // where (i <= MAX_ARRAY_INDEX), are an array index and will be stored in either the
59 // storage vector or the sparse map. An array index i will be handled in the following
62 // * Where (i < MIN_SPARSE_ARRAY_INDEX) the value will be stored in the storage vector.
63 // * Where (MIN_SPARSE_ARRAY_INDEX <= i <= MAX_STORAGE_VECTOR_INDEX) the value will either
64 // be stored in the storage vector or in the sparse array, depending on the density of
65 // data that would be stored in the vector (a vector being used where at least
66 // (1 / minDensityMultiplier) of the entries would be populated).
67 // * Where (MAX_STORAGE_VECTOR_INDEX < i <= MAX_ARRAY_INDEX) the value will always be stored
68 // in the sparse array.
70 // The definition of MAX_STORAGE_VECTOR_LENGTH is dependant on the definition storageSize
71 // function below - the MAX_STORAGE_VECTOR_LENGTH limit is defined such that the storage
72 // size calculation cannot overflow. (sizeof(ArrayStorage) - sizeof(JSValue)) +
73 // (vectorLength * sizeof(JSValue)) must be <= 0xFFFFFFFFU (which is maximum value of size_t).
74 #define MAX_STORAGE_VECTOR_LENGTH static_cast<unsigned>((0xFFFFFFFFU - (sizeof(ArrayStorage) - sizeof(JSValue))) / sizeof(JSValue))
76 // These values have to be macros to be used in max() and min() without introducing
77 // a PIC branch in Mach-O binaries, see <rdar://problem/5971391>.
78 #define MIN_SPARSE_ARRAY_INDEX 10000U
79 #define MAX_STORAGE_VECTOR_INDEX (MAX_STORAGE_VECTOR_LENGTH - 1)
80 // 0xFFFFFFFF is a bit weird -- is not an array index even though it's an integer.
81 #define MAX_ARRAY_INDEX 0xFFFFFFFEU
83 // Our policy for when to use a vector and when to use a sparse map.
84 // For all array indices under MIN_SPARSE_ARRAY_INDEX, we always use a vector.
85 // When indices greater than MIN_SPARSE_ARRAY_INDEX are involved, we use a vector
86 // as long as it is 1/8 full. If more sparse than that, we use a map.
87 static const unsigned minDensityMultiplier
= 8;
89 const ClassInfo
JSArray::info
= {"Array", 0, 0, 0};
91 static inline size_t storageSize(unsigned vectorLength
)
93 ASSERT(vectorLength
<= MAX_STORAGE_VECTOR_LENGTH
);
95 // MAX_STORAGE_VECTOR_LENGTH is defined such that provided (vectorLength <= MAX_STORAGE_VECTOR_LENGTH)
96 // - as asserted above - the following calculation cannot overflow.
97 size_t size
= (sizeof(ArrayStorage
) - sizeof(JSValue
)) + (vectorLength
* sizeof(JSValue
));
98 // Assertion to detect integer overflow in previous calculation (should not be possible, provided that
99 // MAX_STORAGE_VECTOR_LENGTH is correctly defined).
100 ASSERT(((size
- (sizeof(ArrayStorage
) - sizeof(JSValue
))) / sizeof(JSValue
) == vectorLength
) && (size
>= (sizeof(ArrayStorage
) - sizeof(JSValue
))));
105 static inline unsigned increasedVectorLength(unsigned newLength
)
107 ASSERT(newLength
<= MAX_STORAGE_VECTOR_LENGTH
);
109 // Mathematically equivalent to:
110 // increasedLength = (newLength * 3 + 1) / 2;
112 // increasedLength = (unsigned)ceil(newLength * 1.5));
113 // This form is not prone to internal overflow.
114 unsigned increasedLength
= newLength
+ (newLength
>> 1) + (newLength
& 1);
115 ASSERT(increasedLength
>= newLength
);
117 return min(increasedLength
, MAX_STORAGE_VECTOR_LENGTH
);
120 static inline bool isDenseEnoughForVector(unsigned length
, unsigned numValues
)
122 return length
/ minDensityMultiplier
<= numValues
;
125 #if !CHECK_ARRAY_CONSISTENCY
127 inline void JSArray::checkConsistency(ConsistencyCheckType
)
133 JSArray::JSArray(NonNullPassRefPtr
<Structure
> structure
)
134 : JSObject(structure
)
136 unsigned initialCapacity
= 0;
138 m_storage
= static_cast<ArrayStorage
*>(fastZeroedMalloc(storageSize(initialCapacity
)));
139 m_vectorLength
= initialCapacity
;
144 JSArray::JSArray(NonNullPassRefPtr
<Structure
> structure
, unsigned initialLength
)
145 : JSObject(structure
)
147 unsigned initialCapacity
= min(initialLength
, MIN_SPARSE_ARRAY_INDEX
);
149 m_storage
= static_cast<ArrayStorage
*>(fastMalloc(storageSize(initialCapacity
)));
150 m_storage
->m_length
= initialLength
;
151 m_vectorLength
= initialCapacity
;
152 m_storage
->m_numValuesInVector
= 0;
153 m_storage
->m_sparseValueMap
= 0;
154 m_storage
->lazyCreationData
= 0;
156 JSValue
* vector
= m_storage
->m_vector
;
157 for (size_t i
= 0; i
< initialCapacity
; ++i
)
158 vector
[i
] = JSValue();
162 Heap::heap(this)->reportExtraMemoryCost(initialCapacity
* sizeof(JSValue
));
165 JSArray::JSArray(NonNullPassRefPtr
<Structure
> structure
, const ArgList
& list
)
166 : JSObject(structure
)
168 unsigned initialCapacity
= list
.size();
170 m_storage
= static_cast<ArrayStorage
*>(fastMalloc(storageSize(initialCapacity
)));
171 m_storage
->m_length
= initialCapacity
;
172 m_vectorLength
= initialCapacity
;
173 m_storage
->m_numValuesInVector
= initialCapacity
;
174 m_storage
->m_sparseValueMap
= 0;
177 ArgList::const_iterator end
= list
.end();
178 for (ArgList::const_iterator it
= list
.begin(); it
!= end
; ++it
, ++i
)
179 m_storage
->m_vector
[i
] = *it
;
183 Heap::heap(this)->reportExtraMemoryCost(storageSize(initialCapacity
));
188 checkConsistency(DestructorConsistencyCheck
);
190 delete m_storage
->m_sparseValueMap
;
194 bool JSArray::getOwnPropertySlot(ExecState
* exec
, unsigned i
, PropertySlot
& slot
)
196 ArrayStorage
* storage
= m_storage
;
198 if (i
>= storage
->m_length
) {
199 if (i
> MAX_ARRAY_INDEX
)
200 return getOwnPropertySlot(exec
, Identifier::from(exec
, i
), slot
);
204 if (i
< m_vectorLength
) {
205 JSValue
& valueSlot
= storage
->m_vector
[i
];
207 slot
.setValueSlot(&valueSlot
);
210 } else if (SparseArrayValueMap
* map
= storage
->m_sparseValueMap
) {
211 if (i
>= MIN_SPARSE_ARRAY_INDEX
) {
212 SparseArrayValueMap::iterator it
= map
->find(i
);
213 if (it
!= map
->end()) {
214 slot
.setValueSlot(&it
->second
);
220 return JSObject::getOwnPropertySlot(exec
, Identifier::from(exec
, i
), slot
);
223 bool JSArray::getOwnPropertySlot(ExecState
* exec
, const Identifier
& propertyName
, PropertySlot
& slot
)
225 if (propertyName
== exec
->propertyNames().length
) {
226 slot
.setValue(jsNumber(exec
, length()));
231 unsigned i
= propertyName
.toArrayIndex(&isArrayIndex
);
233 return JSArray::getOwnPropertySlot(exec
, i
, slot
);
235 return JSObject::getOwnPropertySlot(exec
, propertyName
, slot
);
238 bool JSArray::getOwnPropertyDescriptor(ExecState
* exec
, const Identifier
& propertyName
, PropertyDescriptor
& descriptor
)
240 if (propertyName
== exec
->propertyNames().length
) {
241 descriptor
.setDescriptor(jsNumber(exec
, length()), DontDelete
| DontEnum
);
246 unsigned i
= propertyName
.toArrayIndex(&isArrayIndex
);
248 if (i
>= m_storage
->m_length
)
250 if (i
< m_vectorLength
) {
251 JSValue
& value
= m_storage
->m_vector
[i
];
253 descriptor
.setDescriptor(value
, 0);
256 } else if (SparseArrayValueMap
* map
= m_storage
->m_sparseValueMap
) {
257 if (i
>= MIN_SPARSE_ARRAY_INDEX
) {
258 SparseArrayValueMap::iterator it
= map
->find(i
);
259 if (it
!= map
->end()) {
260 descriptor
.setDescriptor(it
->second
, 0);
266 return JSObject::getOwnPropertyDescriptor(exec
, propertyName
, descriptor
);
270 void JSArray::put(ExecState
* exec
, const Identifier
& propertyName
, JSValue value
, PutPropertySlot
& slot
)
273 unsigned i
= propertyName
.toArrayIndex(&isArrayIndex
);
279 if (propertyName
== exec
->propertyNames().length
) {
280 unsigned newLength
= value
.toUInt32(exec
);
281 if (value
.toNumber(exec
) != static_cast<double>(newLength
)) {
282 throwError(exec
, RangeError
, "Invalid array length.");
285 setLength(newLength
);
289 JSObject::put(exec
, propertyName
, value
, slot
);
292 void JSArray::put(ExecState
* exec
, unsigned i
, JSValue value
)
296 unsigned length
= m_storage
->m_length
;
297 if (i
>= length
&& i
<= MAX_ARRAY_INDEX
) {
299 m_storage
->m_length
= length
;
302 if (i
< m_vectorLength
) {
303 JSValue
& valueSlot
= m_storage
->m_vector
[i
];
310 ++m_storage
->m_numValuesInVector
;
315 putSlowCase(exec
, i
, value
);
318 NEVER_INLINE
void JSArray::putSlowCase(ExecState
* exec
, unsigned i
, JSValue value
)
320 ArrayStorage
* storage
= m_storage
;
321 SparseArrayValueMap
* map
= storage
->m_sparseValueMap
;
323 if (i
>= MIN_SPARSE_ARRAY_INDEX
) {
324 if (i
> MAX_ARRAY_INDEX
) {
325 PutPropertySlot slot
;
326 put(exec
, Identifier::from(exec
, i
), value
, slot
);
330 // We miss some cases where we could compact the storage, such as a large array that is being filled from the end
331 // (which will only be compacted as we reach indices that are less than cutoff) - but this makes the check much faster.
332 if ((i
> MAX_STORAGE_VECTOR_INDEX
) || !isDenseEnoughForVector(i
+ 1, storage
->m_numValuesInVector
+ 1)) {
334 map
= new SparseArrayValueMap
;
335 storage
->m_sparseValueMap
= map
;
342 // We have decided that we'll put the new item into the vector.
343 // Fast case is when there is no sparse map, so we can increase the vector size without moving values from it.
344 if (!map
|| map
->isEmpty()) {
345 if (increaseVectorLength(i
+ 1)) {
347 storage
->m_vector
[i
] = value
;
348 ++storage
->m_numValuesInVector
;
351 throwOutOfMemoryError(exec
);
355 // Decide how many values it would be best to move from the map.
356 unsigned newNumValuesInVector
= storage
->m_numValuesInVector
+ 1;
357 unsigned newVectorLength
= increasedVectorLength(i
+ 1);
358 for (unsigned j
= max(m_vectorLength
, MIN_SPARSE_ARRAY_INDEX
); j
< newVectorLength
; ++j
)
359 newNumValuesInVector
+= map
->contains(j
);
360 if (i
>= MIN_SPARSE_ARRAY_INDEX
)
361 newNumValuesInVector
-= map
->contains(i
);
362 if (isDenseEnoughForVector(newVectorLength
, newNumValuesInVector
)) {
363 unsigned proposedNewNumValuesInVector
= newNumValuesInVector
;
364 // If newVectorLength is already the maximum - MAX_STORAGE_VECTOR_LENGTH - then do not attempt to grow any further.
365 while (newVectorLength
< MAX_STORAGE_VECTOR_LENGTH
) {
366 unsigned proposedNewVectorLength
= increasedVectorLength(newVectorLength
+ 1);
367 for (unsigned j
= max(newVectorLength
, MIN_SPARSE_ARRAY_INDEX
); j
< proposedNewVectorLength
; ++j
)
368 proposedNewNumValuesInVector
+= map
->contains(j
);
369 if (!isDenseEnoughForVector(proposedNewVectorLength
, proposedNewNumValuesInVector
))
371 newVectorLength
= proposedNewVectorLength
;
372 newNumValuesInVector
= proposedNewNumValuesInVector
;
376 if (!tryFastRealloc(storage
, storageSize(newVectorLength
)).getValue(storage
)) {
377 throwOutOfMemoryError(exec
);
381 unsigned vectorLength
= m_vectorLength
;
383 if (newNumValuesInVector
== storage
->m_numValuesInVector
+ 1) {
384 for (unsigned j
= vectorLength
; j
< newVectorLength
; ++j
)
385 storage
->m_vector
[j
] = JSValue();
386 if (i
> MIN_SPARSE_ARRAY_INDEX
)
389 for (unsigned j
= vectorLength
; j
< max(vectorLength
, MIN_SPARSE_ARRAY_INDEX
); ++j
)
390 storage
->m_vector
[j
] = JSValue();
391 for (unsigned j
= max(vectorLength
, MIN_SPARSE_ARRAY_INDEX
); j
< newVectorLength
; ++j
)
392 storage
->m_vector
[j
] = map
->take(j
);
395 storage
->m_vector
[i
] = value
;
397 m_vectorLength
= newVectorLength
;
398 storage
->m_numValuesInVector
= newNumValuesInVector
;
404 Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength
) - storageSize(vectorLength
));
407 bool JSArray::deleteProperty(ExecState
* exec
, const Identifier
& propertyName
)
410 unsigned i
= propertyName
.toArrayIndex(&isArrayIndex
);
412 return deleteProperty(exec
, i
);
414 if (propertyName
== exec
->propertyNames().length
)
417 return JSObject::deleteProperty(exec
, propertyName
);
420 bool JSArray::deleteProperty(ExecState
* exec
, unsigned i
)
424 ArrayStorage
* storage
= m_storage
;
426 if (i
< m_vectorLength
) {
427 JSValue
& valueSlot
= storage
->m_vector
[i
];
432 valueSlot
= JSValue();
433 --storage
->m_numValuesInVector
;
438 if (SparseArrayValueMap
* map
= storage
->m_sparseValueMap
) {
439 if (i
>= MIN_SPARSE_ARRAY_INDEX
) {
440 SparseArrayValueMap::iterator it
= map
->find(i
);
441 if (it
!= map
->end()) {
451 if (i
> MAX_ARRAY_INDEX
)
452 return deleteProperty(exec
, Identifier::from(exec
, i
));
457 void JSArray::getOwnPropertyNames(ExecState
* exec
, PropertyNameArray
& propertyNames
)
459 // FIXME: Filling PropertyNameArray with an identifier for every integer
460 // is incredibly inefficient for large arrays. We need a different approach,
461 // which almost certainly means a different structure for PropertyNameArray.
463 ArrayStorage
* storage
= m_storage
;
465 unsigned usedVectorLength
= min(storage
->m_length
, m_vectorLength
);
466 for (unsigned i
= 0; i
< usedVectorLength
; ++i
) {
467 if (storage
->m_vector
[i
])
468 propertyNames
.add(Identifier::from(exec
, i
));
471 if (SparseArrayValueMap
* map
= storage
->m_sparseValueMap
) {
472 SparseArrayValueMap::iterator end
= map
->end();
473 for (SparseArrayValueMap::iterator it
= map
->begin(); it
!= end
; ++it
)
474 propertyNames
.add(Identifier::from(exec
, it
->first
));
477 JSObject::getOwnPropertyNames(exec
, propertyNames
);
480 bool JSArray::increaseVectorLength(unsigned newLength
)
482 // This function leaves the array in an internally inconsistent state, because it does not move any values from sparse value map
483 // to the vector. Callers have to account for that, because they can do it more efficiently.
485 ArrayStorage
* storage
= m_storage
;
487 unsigned vectorLength
= m_vectorLength
;
488 ASSERT(newLength
> vectorLength
);
489 ASSERT(newLength
<= MAX_STORAGE_VECTOR_INDEX
);
490 unsigned newVectorLength
= increasedVectorLength(newLength
);
492 if (!tryFastRealloc(storage
, storageSize(newVectorLength
)).getValue(storage
))
495 m_vectorLength
= newVectorLength
;
497 for (unsigned i
= vectorLength
; i
< newVectorLength
; ++i
)
498 storage
->m_vector
[i
] = JSValue();
502 Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength
) - storageSize(vectorLength
));
507 void JSArray::setLength(unsigned newLength
)
511 ArrayStorage
* storage
= m_storage
;
513 unsigned length
= m_storage
->m_length
;
515 if (newLength
< length
) {
516 unsigned usedVectorLength
= min(length
, m_vectorLength
);
517 for (unsigned i
= newLength
; i
< usedVectorLength
; ++i
) {
518 JSValue
& valueSlot
= storage
->m_vector
[i
];
519 bool hadValue
= valueSlot
;
520 valueSlot
= JSValue();
521 storage
->m_numValuesInVector
-= hadValue
;
524 if (SparseArrayValueMap
* map
= storage
->m_sparseValueMap
) {
525 SparseArrayValueMap copy
= *map
;
526 SparseArrayValueMap::iterator end
= copy
.end();
527 for (SparseArrayValueMap::iterator it
= copy
.begin(); it
!= end
; ++it
) {
528 if (it
->first
>= newLength
)
529 map
->remove(it
->first
);
531 if (map
->isEmpty()) {
533 storage
->m_sparseValueMap
= 0;
538 m_storage
->m_length
= newLength
;
543 JSValue
JSArray::pop()
547 unsigned length
= m_storage
->m_length
;
549 return jsUndefined();
555 if (length
< m_vectorLength
) {
556 JSValue
& valueSlot
= m_storage
->m_vector
[length
];
558 --m_storage
->m_numValuesInVector
;
560 valueSlot
= JSValue();
562 result
= jsUndefined();
564 result
= jsUndefined();
565 if (SparseArrayValueMap
* map
= m_storage
->m_sparseValueMap
) {
566 SparseArrayValueMap::iterator it
= map
->find(length
);
567 if (it
!= map
->end()) {
570 if (map
->isEmpty()) {
572 m_storage
->m_sparseValueMap
= 0;
578 m_storage
->m_length
= length
;
585 void JSArray::push(ExecState
* exec
, JSValue value
)
589 if (m_storage
->m_length
< m_vectorLength
) {
590 m_storage
->m_vector
[m_storage
->m_length
] = value
;
591 ++m_storage
->m_numValuesInVector
;
592 ++m_storage
->m_length
;
597 if (m_storage
->m_length
< MIN_SPARSE_ARRAY_INDEX
) {
598 SparseArrayValueMap
* map
= m_storage
->m_sparseValueMap
;
599 if (!map
|| map
->isEmpty()) {
600 if (increaseVectorLength(m_storage
->m_length
+ 1)) {
601 m_storage
->m_vector
[m_storage
->m_length
] = value
;
602 ++m_storage
->m_numValuesInVector
;
603 ++m_storage
->m_length
;
608 throwOutOfMemoryError(exec
);
613 putSlowCase(exec
, m_storage
->m_length
++, value
);
616 void JSArray::markChildren(MarkStack
& markStack
)
618 markChildrenDirect(markStack
);
621 static int compareNumbersForQSort(const void* a
, const void* b
)
623 double da
= static_cast<const JSValue
*>(a
)->uncheckedGetNumber();
624 double db
= static_cast<const JSValue
*>(b
)->uncheckedGetNumber();
625 return (da
> db
) - (da
< db
);
628 typedef std::pair
<JSValue
, UString
> ValueStringPair
;
630 static int compareByStringPairForQSort(const void* a
, const void* b
)
632 const ValueStringPair
* va
= static_cast<const ValueStringPair
*>(a
);
633 const ValueStringPair
* vb
= static_cast<const ValueStringPair
*>(b
);
634 return compare(va
->second
, vb
->second
);
637 void JSArray::sortNumeric(ExecState
* exec
, JSValue compareFunction
, CallType callType
, const CallData
& callData
)
639 unsigned lengthNotIncludingUndefined
= compactForSorting();
640 if (m_storage
->m_sparseValueMap
) {
641 throwOutOfMemoryError(exec
);
645 if (!lengthNotIncludingUndefined
)
648 bool allValuesAreNumbers
= true;
649 size_t size
= m_storage
->m_numValuesInVector
;
650 for (size_t i
= 0; i
< size
; ++i
) {
651 if (!m_storage
->m_vector
[i
].isNumber()) {
652 allValuesAreNumbers
= false;
657 if (!allValuesAreNumbers
)
658 return sort(exec
, compareFunction
, callType
, callData
);
660 // For numeric comparison, which is fast, qsort is faster than mergesort. We
661 // also don't require mergesort's stability, since there's no user visible
662 // side-effect from swapping the order of equal primitive values.
663 qsort(m_storage
->m_vector
, size
, sizeof(JSValue
), compareNumbersForQSort
);
665 checkConsistency(SortConsistencyCheck
);
668 void JSArray::sort(ExecState
* exec
)
670 unsigned lengthNotIncludingUndefined
= compactForSorting();
671 if (m_storage
->m_sparseValueMap
) {
672 throwOutOfMemoryError(exec
);
676 if (!lengthNotIncludingUndefined
)
679 // Converting JavaScript values to strings can be expensive, so we do it once up front and sort based on that.
680 // This is a considerable improvement over doing it twice per comparison, though it requires a large temporary
681 // buffer. Besides, this protects us from crashing if some objects have custom toString methods that return
682 // random or otherwise changing results, effectively making compare function inconsistent.
684 Vector
<ValueStringPair
> values(lengthNotIncludingUndefined
);
685 if (!values
.begin()) {
686 throwOutOfMemoryError(exec
);
690 for (size_t i
= 0; i
< lengthNotIncludingUndefined
; i
++) {
691 JSValue value
= m_storage
->m_vector
[i
];
692 ASSERT(!value
.isUndefined());
693 values
[i
].first
= value
;
696 // FIXME: While calling these toString functions, the array could be mutated.
697 // In that case, objects pointed to by values in this vector might get garbage-collected!
699 // FIXME: The following loop continues to call toString on subsequent values even after
700 // a toString call raises an exception.
702 for (size_t i
= 0; i
< lengthNotIncludingUndefined
; i
++)
703 values
[i
].second
= values
[i
].first
.toString(exec
);
705 if (exec
->hadException())
708 // FIXME: Since we sort by string value, a fast algorithm might be to use a radix sort. That would be O(N) rather
712 mergesort(values
.begin(), values
.size(), sizeof(ValueStringPair
), compareByStringPairForQSort
);
714 // FIXME: The qsort library function is likely to not be a stable sort.
715 // ECMAScript-262 does not specify a stable sort, but in practice, browsers perform a stable sort.
716 qsort(values
.begin(), values
.size(), sizeof(ValueStringPair
), compareByStringPairForQSort
);
719 // FIXME: If the toString function changed the length of the array, this might be
720 // modifying the vector incorrectly.
722 for (size_t i
= 0; i
< lengthNotIncludingUndefined
; i
++)
723 m_storage
->m_vector
[i
] = values
[i
].first
;
725 checkConsistency(SortConsistencyCheck
);
728 struct AVLTreeNodeForArrayCompare
{
731 // Child pointers. The high bit of gt is robbed and used as the
732 // balance factor sign. The high bit of lt is robbed and used as
733 // the magnitude of the balance factor.
738 struct AVLTreeAbstractorForArrayCompare
{
739 typedef int32_t handle
; // Handle is an index into m_nodes vector.
741 typedef int32_t size
;
743 Vector
<AVLTreeNodeForArrayCompare
> m_nodes
;
745 JSValue m_compareFunction
;
746 CallType m_compareCallType
;
747 const CallData
* m_compareCallData
;
748 JSValue m_globalThisValue
;
749 OwnPtr
<CachedCall
> m_cachedCall
;
751 handle
get_less(handle h
) { return m_nodes
[h
].lt
& 0x7FFFFFFF; }
752 void set_less(handle h
, handle lh
) { m_nodes
[h
].lt
&= 0x80000000; m_nodes
[h
].lt
|= lh
; }
753 handle
get_greater(handle h
) { return m_nodes
[h
].gt
& 0x7FFFFFFF; }
754 void set_greater(handle h
, handle gh
) { m_nodes
[h
].gt
&= 0x80000000; m_nodes
[h
].gt
|= gh
; }
756 int get_balance_factor(handle h
)
758 if (m_nodes
[h
].gt
& 0x80000000)
760 return static_cast<unsigned>(m_nodes
[h
].lt
) >> 31;
763 void set_balance_factor(handle h
, int bf
)
766 m_nodes
[h
].lt
&= 0x7FFFFFFF;
767 m_nodes
[h
].gt
&= 0x7FFFFFFF;
769 m_nodes
[h
].lt
|= 0x80000000;
771 m_nodes
[h
].gt
|= 0x80000000;
773 m_nodes
[h
].gt
&= 0x7FFFFFFF;
777 int compare_key_key(key va
, key vb
)
779 ASSERT(!va
.isUndefined());
780 ASSERT(!vb
.isUndefined());
782 if (m_exec
->hadException())
785 double compareResult
;
787 m_cachedCall
->setThis(m_globalThisValue
);
788 m_cachedCall
->setArgument(0, va
);
789 m_cachedCall
->setArgument(1, vb
);
790 compareResult
= m_cachedCall
->call().toNumber(m_cachedCall
->newCallFrame(m_exec
));
792 MarkedArgumentBuffer arguments
;
793 arguments
.append(va
);
794 arguments
.append(vb
);
795 compareResult
= call(m_exec
, m_compareFunction
, m_compareCallType
, *m_compareCallData
, m_globalThisValue
, arguments
).toNumber(m_exec
);
797 return (compareResult
< 0) ? -1 : 1; // Not passing equality through, because we need to store all values, even if equivalent.
800 int compare_key_node(key k
, handle h
) { return compare_key_key(k
, m_nodes
[h
].value
); }
801 int compare_node_node(handle h1
, handle h2
) { return compare_key_key(m_nodes
[h1
].value
, m_nodes
[h2
].value
); }
803 static handle
null() { return 0x7FFFFFFF; }
806 void JSArray::sort(ExecState
* exec
, JSValue compareFunction
, CallType callType
, const CallData
& callData
)
810 // FIXME: This ignores exceptions raised in the compare function or in toNumber.
812 // The maximum tree depth is compiled in - but the caller is clearly up to no good
813 // if a larger array is passed.
814 ASSERT(m_storage
->m_length
<= static_cast<unsigned>(std::numeric_limits
<int>::max()));
815 if (m_storage
->m_length
> static_cast<unsigned>(std::numeric_limits
<int>::max()))
818 if (!m_storage
->m_length
)
821 unsigned usedVectorLength
= min(m_storage
->m_length
, m_vectorLength
);
823 AVLTree
<AVLTreeAbstractorForArrayCompare
, 44> tree
; // Depth 44 is enough for 2^31 items
824 tree
.abstractor().m_exec
= exec
;
825 tree
.abstractor().m_compareFunction
= compareFunction
;
826 tree
.abstractor().m_compareCallType
= callType
;
827 tree
.abstractor().m_compareCallData
= &callData
;
828 tree
.abstractor().m_globalThisValue
= exec
->globalThisValue();
829 tree
.abstractor().m_nodes
.resize(usedVectorLength
+ (m_storage
->m_sparseValueMap
? m_storage
->m_sparseValueMap
->size() : 0));
831 if (callType
== CallTypeJS
)
832 tree
.abstractor().m_cachedCall
.set(new CachedCall(exec
, asFunction(compareFunction
), 2, exec
->exceptionSlot()));
834 if (!tree
.abstractor().m_nodes
.begin()) {
835 throwOutOfMemoryError(exec
);
839 // FIXME: If the compare function modifies the array, the vector, map, etc. could be modified
840 // right out from under us while we're building the tree here.
842 unsigned numDefined
= 0;
843 unsigned numUndefined
= 0;
845 // Iterate over the array, ignoring missing values, counting undefined ones, and inserting all other ones into the tree.
846 for (; numDefined
< usedVectorLength
; ++numDefined
) {
847 JSValue v
= m_storage
->m_vector
[numDefined
];
848 if (!v
|| v
.isUndefined())
850 tree
.abstractor().m_nodes
[numDefined
].value
= v
;
851 tree
.insert(numDefined
);
853 for (unsigned i
= numDefined
; i
< usedVectorLength
; ++i
) {
854 JSValue v
= m_storage
->m_vector
[i
];
859 tree
.abstractor().m_nodes
[numDefined
].value
= v
;
860 tree
.insert(numDefined
);
866 unsigned newUsedVectorLength
= numDefined
+ numUndefined
;
868 if (SparseArrayValueMap
* map
= m_storage
->m_sparseValueMap
) {
869 newUsedVectorLength
+= map
->size();
870 if (newUsedVectorLength
> m_vectorLength
) {
871 // Check that it is possible to allocate an array large enough to hold all the entries.
872 if ((newUsedVectorLength
> MAX_STORAGE_VECTOR_LENGTH
) || !increaseVectorLength(newUsedVectorLength
)) {
873 throwOutOfMemoryError(exec
);
878 SparseArrayValueMap::iterator end
= map
->end();
879 for (SparseArrayValueMap::iterator it
= map
->begin(); it
!= end
; ++it
) {
880 tree
.abstractor().m_nodes
[numDefined
].value
= it
->second
;
881 tree
.insert(numDefined
);
886 m_storage
->m_sparseValueMap
= 0;
889 ASSERT(tree
.abstractor().m_nodes
.size() >= numDefined
);
891 // FIXME: If the compare function changed the length of the array, the following might be
892 // modifying the vector incorrectly.
894 // Copy the values back into m_storage.
895 AVLTree
<AVLTreeAbstractorForArrayCompare
, 44>::Iterator iter
;
896 iter
.start_iter_least(tree
);
897 for (unsigned i
= 0; i
< numDefined
; ++i
) {
898 m_storage
->m_vector
[i
] = tree
.abstractor().m_nodes
[*iter
].value
;
902 // Put undefined values back in.
903 for (unsigned i
= numDefined
; i
< newUsedVectorLength
; ++i
)
904 m_storage
->m_vector
[i
] = jsUndefined();
906 // Ensure that unused values in the vector are zeroed out.
907 for (unsigned i
= newUsedVectorLength
; i
< usedVectorLength
; ++i
)
908 m_storage
->m_vector
[i
] = JSValue();
910 m_storage
->m_numValuesInVector
= newUsedVectorLength
;
912 checkConsistency(SortConsistencyCheck
);
915 void JSArray::fillArgList(ExecState
* exec
, MarkedArgumentBuffer
& args
)
917 JSValue
* vector
= m_storage
->m_vector
;
918 unsigned vectorEnd
= min(m_storage
->m_length
, m_vectorLength
);
920 for (; i
< vectorEnd
; ++i
) {
921 JSValue
& v
= vector
[i
];
927 for (; i
< m_storage
->m_length
; ++i
)
928 args
.append(get(exec
, i
));
931 void JSArray::copyToRegisters(ExecState
* exec
, Register
* buffer
, uint32_t maxSize
)
933 ASSERT(m_storage
->m_length
== maxSize
);
934 UNUSED_PARAM(maxSize
);
935 JSValue
* vector
= m_storage
->m_vector
;
936 unsigned vectorEnd
= min(m_storage
->m_length
, m_vectorLength
);
938 for (; i
< vectorEnd
; ++i
) {
939 JSValue
& v
= vector
[i
];
945 for (; i
< m_storage
->m_length
; ++i
)
946 buffer
[i
] = get(exec
, i
);
949 unsigned JSArray::compactForSorting()
953 ArrayStorage
* storage
= m_storage
;
955 unsigned usedVectorLength
= min(m_storage
->m_length
, m_vectorLength
);
957 unsigned numDefined
= 0;
958 unsigned numUndefined
= 0;
960 for (; numDefined
< usedVectorLength
; ++numDefined
) {
961 JSValue v
= storage
->m_vector
[numDefined
];
962 if (!v
|| v
.isUndefined())
965 for (unsigned i
= numDefined
; i
< usedVectorLength
; ++i
) {
966 JSValue v
= storage
->m_vector
[i
];
971 storage
->m_vector
[numDefined
++] = v
;
975 unsigned newUsedVectorLength
= numDefined
+ numUndefined
;
977 if (SparseArrayValueMap
* map
= storage
->m_sparseValueMap
) {
978 newUsedVectorLength
+= map
->size();
979 if (newUsedVectorLength
> m_vectorLength
) {
980 // Check that it is possible to allocate an array large enough to hold all the entries - if not,
981 // exception is thrown by caller.
982 if ((newUsedVectorLength
> MAX_STORAGE_VECTOR_LENGTH
) || !increaseVectorLength(newUsedVectorLength
))
987 SparseArrayValueMap::iterator end
= map
->end();
988 for (SparseArrayValueMap::iterator it
= map
->begin(); it
!= end
; ++it
)
989 storage
->m_vector
[numDefined
++] = it
->second
;
992 storage
->m_sparseValueMap
= 0;
995 for (unsigned i
= numDefined
; i
< newUsedVectorLength
; ++i
)
996 storage
->m_vector
[i
] = jsUndefined();
997 for (unsigned i
= newUsedVectorLength
; i
< usedVectorLength
; ++i
)
998 storage
->m_vector
[i
] = JSValue();
1000 storage
->m_numValuesInVector
= newUsedVectorLength
;
1002 checkConsistency(SortConsistencyCheck
);
1007 void* JSArray::lazyCreationData()
1009 return m_storage
->lazyCreationData
;
1012 void JSArray::setLazyCreationData(void* d
)
1014 m_storage
->lazyCreationData
= d
;
1017 #if CHECK_ARRAY_CONSISTENCY
1019 void JSArray::checkConsistency(ConsistencyCheckType type
)
1022 if (type
== SortConsistencyCheck
)
1023 ASSERT(!m_storage
->m_sparseValueMap
);
1025 unsigned numValuesInVector
= 0;
1026 for (unsigned i
= 0; i
< m_vectorLength
; ++i
) {
1027 if (JSValue value
= m_storage
->m_vector
[i
]) {
1028 ASSERT(i
< m_storage
->m_length
);
1029 if (type
!= DestructorConsistencyCheck
)
1030 value
->type(); // Likely to crash if the object was deallocated.
1031 ++numValuesInVector
;
1033 if (type
== SortConsistencyCheck
)
1034 ASSERT(i
>= m_storage
->m_numValuesInVector
);
1037 ASSERT(numValuesInVector
== m_storage
->m_numValuesInVector
);
1038 ASSERT(numValuesInVector
<= m_storage
->m_length
);
1040 if (m_storage
->m_sparseValueMap
) {
1041 SparseArrayValueMap::iterator end
= m_storage
->m_sparseValueMap
->end();
1042 for (SparseArrayValueMap::iterator it
= m_storage
->m_sparseValueMap
->begin(); it
!= end
; ++it
) {
1043 unsigned index
= it
->first
;
1044 ASSERT(index
< m_storage
->m_length
);
1045 ASSERT(index
>= m_vectorLength
);
1046 ASSERT(index
<= MAX_ARRAY_INDEX
);
1048 if (type
!= DestructorConsistencyCheck
)
1049 it
->second
->type(); // Likely to crash if the object was deallocated.