diff options
author | Bradley T. Hughes <bradley.hughes@nokia.com> | 2009-06-15 09:57:36 (GMT) |
---|---|---|
committer | Bradley T. Hughes <bradley.hughes@nokia.com> | 2009-06-15 09:57:36 (GMT) |
commit | 336dfcef05cb63df0a6d550b59a4badc7a0f01c1 (patch) | |
tree | a218ec97413e0c8ebc9600ac5db9b2adea485b32 /src/3rdparty/webkit/JavaScriptCore/runtime/JSArray.cpp | |
parent | e44d64510e019e5d3b379b704cfb824e0d7ccc9d (diff) | |
download | Qt-336dfcef05cb63df0a6d550b59a4badc7a0f01c1.zip Qt-336dfcef05cb63df0a6d550b59a4badc7a0f01c1.tar.gz Qt-336dfcef05cb63df0a6d550b59a4badc7a0f01c1.tar.bz2 |
Merge of master
Diffstat (limited to 'src/3rdparty/webkit/JavaScriptCore/runtime/JSArray.cpp')
-rw-r--r-- | src/3rdparty/webkit/JavaScriptCore/runtime/JSArray.cpp | 214 |
1 files changed, 141 insertions, 73 deletions
diff --git a/src/3rdparty/webkit/JavaScriptCore/runtime/JSArray.cpp b/src/3rdparty/webkit/JavaScriptCore/runtime/JSArray.cpp index 35d0dec..296ac9d 100644 --- a/src/3rdparty/webkit/JavaScriptCore/runtime/JSArray.cpp +++ b/src/3rdparty/webkit/JavaScriptCore/runtime/JSArray.cpp @@ -24,9 +24,11 @@ #include "JSArray.h" #include "ArrayPrototype.h" +#include "CachedCall.h" #include "PropertyNameArray.h" #include <wtf/AVLTree.h> #include <wtf/Assertions.h> +#include <wtf/OwnPtr.h> #include <Operations.h> #define CHECK_ARRAY_CONSISTENCY 0 @@ -65,9 +67,9 @@ ASSERT_CLASS_FITS_IN_CELL(JSArray); // The definition of MAX_STORAGE_VECTOR_LENGTH is dependant on the definition storageSize // function below - the MAX_STORAGE_VECTOR_LENGTH limit is defined such that the storage -// size calculation cannot overflow. (sizeof(ArrayStorage) - sizeof(JSValuePtr)) + -// (vectorLength * sizeof(JSValuePtr)) must be <= 0xFFFFFFFFU (which is maximum value of size_t). -#define MAX_STORAGE_VECTOR_LENGTH static_cast<unsigned>((0xFFFFFFFFU - (sizeof(ArrayStorage) - sizeof(JSValuePtr))) / sizeof(JSValuePtr)) +// size calculation cannot overflow. (sizeof(ArrayStorage) - sizeof(JSValue)) + +// (vectorLength * sizeof(JSValue)) must be <= 0xFFFFFFFFU (which is maximum value of size_t). +#define MAX_STORAGE_VECTOR_LENGTH static_cast<unsigned>((0xFFFFFFFFU - (sizeof(ArrayStorage) - sizeof(JSValue))) / sizeof(JSValue)) // These values have to be macros to be used in max() and min() without introducing // a PIC branch in Mach-O binaries, see <rdar://problem/5971391>. @@ -90,10 +92,10 @@ static inline size_t storageSize(unsigned vectorLength) // MAX_STORAGE_VECTOR_LENGTH is defined such that provided (vectorLength <= MAX_STORAGE_VECTOR_LENGTH) // - as asserted above - the following calculation cannot overflow. - size_t size = (sizeof(ArrayStorage) - sizeof(JSValuePtr)) + (vectorLength * sizeof(JSValuePtr)); + size_t size = (sizeof(ArrayStorage) - sizeof(JSValue)) + (vectorLength * sizeof(JSValue)); // Assertion to detect integer overflow in previous calculation (should not be possible, provided that // MAX_STORAGE_VECTOR_LENGTH is correctly defined). - ASSERT(((size - (sizeof(ArrayStorage) - sizeof(JSValuePtr))) / sizeof(JSValuePtr) == vectorLength) && (size >= (sizeof(ArrayStorage) - sizeof(JSValuePtr)))); + ASSERT(((size - (sizeof(ArrayStorage) - sizeof(JSValue))) / sizeof(JSValue) == vectorLength) && (size >= (sizeof(ArrayStorage) - sizeof(JSValue)))); return size; } @@ -149,12 +151,12 @@ JSArray::JSArray(PassRefPtr<Structure> structure, unsigned initialLength) m_storage->m_vectorLength = initialCapacity; m_storage->m_length = initialLength; - Heap::heap(this)->reportExtraMemoryCost(initialCapacity * sizeof(JSValuePtr)); + Heap::heap(this)->reportExtraMemoryCost(initialCapacity * sizeof(JSValue)); checkConsistency(); } -JSArray::JSArray(ExecState* exec, PassRefPtr<Structure> structure, const ArgList& list) +JSArray::JSArray(PassRefPtr<Structure> structure, const ArgList& list) : JSObject(structure) { unsigned length = list.size(); @@ -171,12 +173,11 @@ JSArray::JSArray(ExecState* exec, PassRefPtr<Structure> structure, const ArgList size_t i = 0; ArgList::const_iterator end = list.end(); for (ArgList::const_iterator it = list.begin(); it != end; ++it, ++i) - storage->m_vector[i] = (*it).jsValue(exec); + storage->m_vector[i] = *it; m_storage = storage; - // When the array is created non-empty, its cells are filled, so it's really no worse than - // a property map. Therefore don't report extra memory cost. + Heap::heap(this)->reportExtraMemoryCost(storageSize(length)); checkConsistency(); } @@ -200,7 +201,7 @@ bool JSArray::getOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot } if (i < storage->m_vectorLength) { - JSValuePtr& valueSlot = storage->m_vector[i]; + JSValue& valueSlot = storage->m_vector[i]; if (valueSlot) { slot.setValueSlot(&valueSlot); return true; @@ -234,7 +235,7 @@ bool JSArray::getOwnPropertySlot(ExecState* exec, const Identifier& propertyName } // ECMA 15.4.5.1 -void JSArray::put(ExecState* exec, const Identifier& propertyName, JSValuePtr value, PutPropertySlot& slot) +void JSArray::put(ExecState* exec, const Identifier& propertyName, JSValue value, PutPropertySlot& slot) { bool isArrayIndex; unsigned i = propertyName.toArrayIndex(&isArrayIndex); @@ -244,8 +245,8 @@ void JSArray::put(ExecState* exec, const Identifier& propertyName, JSValuePtr va } if (propertyName == exec->propertyNames().length) { - unsigned newLength = value->toUInt32(exec); - if (value->toNumber(exec) != static_cast<double>(newLength)) { + unsigned newLength = value.toUInt32(exec); + if (value.toNumber(exec) != static_cast<double>(newLength)) { throwError(exec, RangeError, "Invalid array length."); return; } @@ -256,7 +257,7 @@ void JSArray::put(ExecState* exec, const Identifier& propertyName, JSValuePtr va JSObject::put(exec, propertyName, value, slot); } -void JSArray::put(ExecState* exec, unsigned i, JSValuePtr value) +void JSArray::put(ExecState* exec, unsigned i, JSValue value) { checkConsistency(); @@ -267,7 +268,7 @@ void JSArray::put(ExecState* exec, unsigned i, JSValuePtr value) } if (i < m_storage->m_vectorLength) { - JSValuePtr& valueSlot = m_storage->m_vector[i]; + JSValue& valueSlot = m_storage->m_vector[i]; if (valueSlot) { valueSlot = value; checkConsistency(); @@ -283,7 +284,7 @@ void JSArray::put(ExecState* exec, unsigned i, JSValuePtr value) putSlowCase(exec, i, value); } -NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValuePtr value) +NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue value) { ArrayStorage* storage = m_storage; SparseArrayValueMap* map = storage->m_sparseValueMap; @@ -349,14 +350,17 @@ NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValuePtr v } unsigned vectorLength = storage->m_vectorLength; + + Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength)); + if (newNumValuesInVector == storage->m_numValuesInVector + 1) { for (unsigned j = vectorLength; j < newVectorLength; ++j) - storage->m_vector[j] = noValue(); + storage->m_vector[j] = JSValue(); if (i > MIN_SPARSE_ARRAY_INDEX) map->remove(i); } else { for (unsigned j = vectorLength; j < max(vectorLength, MIN_SPARSE_ARRAY_INDEX); ++j) - storage->m_vector[j] = noValue(); + storage->m_vector[j] = JSValue(); for (unsigned j = max(vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j) storage->m_vector[j] = map->take(j); } @@ -391,12 +395,12 @@ bool JSArray::deleteProperty(ExecState* exec, unsigned i) ArrayStorage* storage = m_storage; if (i < storage->m_vectorLength) { - JSValuePtr& valueSlot = storage->m_vector[i]; + JSValue& valueSlot = storage->m_vector[i]; if (!valueSlot) { checkConsistency(); return false; } - valueSlot = noValue(); + valueSlot = JSValue(); --storage->m_numValuesInVector; if (m_fastAccessCutoff > i) m_fastAccessCutoff = i; @@ -462,10 +466,11 @@ bool JSArray::increaseVectorLength(unsigned newLength) if (!storage) return false; + Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength)); storage->m_vectorLength = newVectorLength; for (unsigned i = vectorLength; i < newVectorLength; ++i) - storage->m_vector[i] = noValue(); + storage->m_vector[i] = JSValue(); m_storage = storage; return true; @@ -485,9 +490,9 @@ void JSArray::setLength(unsigned newLength) unsigned usedVectorLength = min(length, storage->m_vectorLength); for (unsigned i = newLength; i < usedVectorLength; ++i) { - JSValuePtr& valueSlot = storage->m_vector[i]; + JSValue& valueSlot = storage->m_vector[i]; bool hadValue = valueSlot; - valueSlot = noValue(); + valueSlot = JSValue(); storage->m_numValuesInVector -= hadValue; } @@ -510,7 +515,7 @@ void JSArray::setLength(unsigned newLength) checkConsistency(); } -JSValuePtr JSArray::pop() +JSValue JSArray::pop() { checkConsistency(); @@ -520,19 +525,19 @@ JSValuePtr JSArray::pop() --length; - JSValuePtr result; + JSValue result; if (m_fastAccessCutoff > length) { - JSValuePtr& valueSlot = m_storage->m_vector[length]; + JSValue& valueSlot = m_storage->m_vector[length]; result = valueSlot; ASSERT(result); - valueSlot = noValue(); + valueSlot = JSValue(); --m_storage->m_numValuesInVector; m_fastAccessCutoff = length; } else if (length < m_storage->m_vectorLength) { - JSValuePtr& valueSlot = m_storage->m_vector[length]; + JSValue& valueSlot = m_storage->m_vector[length]; result = valueSlot; - valueSlot = noValue(); + valueSlot = JSValue(); if (result) --m_storage->m_numValuesInVector; else @@ -559,7 +564,7 @@ JSValuePtr JSArray::pop() return result; } -void JSArray::push(ExecState* exec, JSValuePtr value) +void JSArray::push(ExecState* exec, JSValue value) { checkConsistency(); @@ -599,30 +604,68 @@ void JSArray::mark() unsigned usedVectorLength = min(storage->m_length, storage->m_vectorLength); for (unsigned i = 0; i < usedVectorLength; ++i) { - JSValuePtr value = storage->m_vector[i]; - if (value && !value->marked()) - value->mark(); + JSValue value = storage->m_vector[i]; + if (value && !value.marked()) + value.mark(); } if (SparseArrayValueMap* map = storage->m_sparseValueMap) { SparseArrayValueMap::iterator end = map->end(); for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) { - JSValuePtr value = it->second; - if (!value->marked()) - value->mark(); + JSValue value = it->second; + if (!value.marked()) + value.mark(); } } } -typedef std::pair<JSValuePtr, UString> ArrayQSortPair; +static int compareNumbersForQSort(const void* a, const void* b) +{ + double da = static_cast<const JSValue*>(a)->uncheckedGetNumber(); + double db = static_cast<const JSValue*>(b)->uncheckedGetNumber(); + return (da > db) - (da < db); +} + +typedef std::pair<JSValue, UString> ValueStringPair; static int compareByStringPairForQSort(const void* a, const void* b) { - const ArrayQSortPair* va = static_cast<const ArrayQSortPair*>(a); - const ArrayQSortPair* vb = static_cast<const ArrayQSortPair*>(b); + const ValueStringPair* va = static_cast<const ValueStringPair*>(a); + const ValueStringPair* vb = static_cast<const ValueStringPair*>(b); return compare(va->second, vb->second); } +void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData) +{ + unsigned lengthNotIncludingUndefined = compactForSorting(); + if (m_storage->m_sparseValueMap) { + throwOutOfMemoryError(exec); + return; + } + + if (!lengthNotIncludingUndefined) + return; + + bool allValuesAreNumbers = true; + size_t size = m_storage->m_numValuesInVector; + for (size_t i = 0; i < size; ++i) { + if (!m_storage->m_vector[i].isNumber()) { + allValuesAreNumbers = false; + break; + } + } + + if (!allValuesAreNumbers) + return sort(exec, compareFunction, callType, callData); + + // For numeric comparison, which is fast, qsort is faster than mergesort. We + // also don't require mergesort's stability, since there's no user visible + // side-effect from swapping the order of equal primitive values. + qsort(m_storage->m_vector, size, sizeof(JSValue), compareNumbersForQSort); + + checkConsistency(SortConsistencyCheck); +} + void JSArray::sort(ExecState* exec) { unsigned lengthNotIncludingUndefined = compactForSorting(); @@ -639,15 +682,15 @@ void JSArray::sort(ExecState* exec) // buffer. Besides, this protects us from crashing if some objects have custom toString methods that return // random or otherwise changing results, effectively making compare function inconsistent. - Vector<ArrayQSortPair> values(lengthNotIncludingUndefined); + Vector<ValueStringPair> values(lengthNotIncludingUndefined); if (!values.begin()) { throwOutOfMemoryError(exec); return; } for (size_t i = 0; i < lengthNotIncludingUndefined; i++) { - JSValuePtr value = m_storage->m_vector[i]; - ASSERT(!value->isUndefined()); + JSValue value = m_storage->m_vector[i]; + ASSERT(!value.isUndefined()); values[i].first = value; } @@ -658,7 +701,7 @@ void JSArray::sort(ExecState* exec) // a toString call raises an exception. for (size_t i = 0; i < lengthNotIncludingUndefined; i++) - values[i].second = values[i].first->toString(exec); + values[i].second = values[i].first.toString(exec); if (exec->hadException()) return; @@ -667,11 +710,11 @@ void JSArray::sort(ExecState* exec) // than O(N log N). #if HAVE(MERGESORT) - mergesort(values.begin(), values.size(), sizeof(ArrayQSortPair), compareByStringPairForQSort); + mergesort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort); #else // FIXME: The qsort library function is likely to not be a stable sort. // ECMAScript-262 does not specify a stable sort, but in practice, browsers perform a stable sort. - qsort(values.begin(), values.size(), sizeof(ArrayQSortPair), compareByStringPairForQSort); + qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort); #endif // FIXME: If the toString function changed the length of the array, this might be @@ -684,7 +727,7 @@ void JSArray::sort(ExecState* exec) } struct AVLTreeNodeForArrayCompare { - JSValuePtr value; + JSValue value; // Child pointers. The high bit of gt is robbed and used as the // balance factor sign. The high bit of lt is robbed and used as @@ -695,15 +738,16 @@ struct AVLTreeNodeForArrayCompare { struct AVLTreeAbstractorForArrayCompare { typedef int32_t handle; // Handle is an index into m_nodes vector. - typedef JSValuePtr key; + typedef JSValue key; typedef int32_t size; Vector<AVLTreeNodeForArrayCompare> m_nodes; ExecState* m_exec; - JSValuePtr m_compareFunction; + JSValue m_compareFunction; CallType m_compareCallType; const CallData* m_compareCallData; - JSValuePtr m_globalThisValue; + JSValue m_globalThisValue; + OwnPtr<CachedCall> m_cachedCall; handle get_less(handle h) { return m_nodes[h].lt & 0x7FFFFFFF; } void set_less(handle h, handle lh) { m_nodes[h].lt &= 0x80000000; m_nodes[h].lt |= lh; } @@ -733,16 +777,24 @@ struct AVLTreeAbstractorForArrayCompare { int compare_key_key(key va, key vb) { - ASSERT(!va->isUndefined()); - ASSERT(!vb->isUndefined()); + ASSERT(!va.isUndefined()); + ASSERT(!vb.isUndefined()); if (m_exec->hadException()) return 1; - ArgList arguments; - arguments.append(va); - arguments.append(vb); - double compareResult = call(m_exec, m_compareFunction, m_compareCallType, *m_compareCallData, m_globalThisValue, arguments)->toNumber(m_exec); + double compareResult; + if (m_cachedCall) { + m_cachedCall->setThis(m_globalThisValue); + m_cachedCall->setArgument(0, va); + m_cachedCall->setArgument(1, vb); + compareResult = m_cachedCall->call().toNumber(m_cachedCall->newCallFrame()); + } else { + MarkedArgumentBuffer arguments; + arguments.append(va); + arguments.append(vb); + compareResult = call(m_exec, m_compareFunction, m_compareCallType, *m_compareCallData, m_globalThisValue, arguments).toNumber(m_exec); + } return (compareResult < 0) ? -1 : 1; // Not passing equality through, because we need to store all values, even if equivalent. } @@ -752,7 +804,7 @@ struct AVLTreeAbstractorForArrayCompare { static handle null() { return 0x7FFFFFFF; } }; -void JSArray::sort(ExecState* exec, JSValuePtr compareFunction, CallType callType, const CallData& callData) +void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData) { checkConsistency(); @@ -777,6 +829,9 @@ void JSArray::sort(ExecState* exec, JSValuePtr compareFunction, CallType callTyp tree.abstractor().m_globalThisValue = exec->globalThisValue(); tree.abstractor().m_nodes.resize(usedVectorLength + (m_storage->m_sparseValueMap ? m_storage->m_sparseValueMap->size() : 0)); + if (callType == CallTypeJS) + tree.abstractor().m_cachedCall.set(new CachedCall(exec, asFunction(compareFunction), 2, exec->exceptionSlot())); + if (!tree.abstractor().m_nodes.begin()) { throwOutOfMemoryError(exec); return; @@ -790,16 +845,16 @@ void JSArray::sort(ExecState* exec, JSValuePtr compareFunction, CallType callTyp // Iterate over the array, ignoring missing values, counting undefined ones, and inserting all other ones into the tree. for (; numDefined < usedVectorLength; ++numDefined) { - JSValuePtr v = m_storage->m_vector[numDefined]; - if (!v || v->isUndefined()) + JSValue v = m_storage->m_vector[numDefined]; + if (!v || v.isUndefined()) break; tree.abstractor().m_nodes[numDefined].value = v; tree.insert(numDefined); } for (unsigned i = numDefined; i < usedVectorLength; ++i) { - JSValuePtr v = m_storage->m_vector[i]; + JSValue v = m_storage->m_vector[i]; if (v) { - if (v->isUndefined()) + if (v.isUndefined()) ++numUndefined; else { tree.abstractor().m_nodes[numDefined].value = v; @@ -851,7 +906,7 @@ void JSArray::sort(ExecState* exec, JSValuePtr compareFunction, CallType callTyp // Ensure that unused values in the vector are zeroed out. for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i) - m_storage->m_vector[i] = noValue(); + m_storage->m_vector[i] = JSValue(); m_fastAccessCutoff = newUsedVectorLength; m_storage->m_numValuesInVector = newUsedVectorLength; @@ -859,7 +914,7 @@ void JSArray::sort(ExecState* exec, JSValuePtr compareFunction, CallType callTyp checkConsistency(SortConsistencyCheck); } -void JSArray::fillArgList(ExecState* exec, ArgList& args) +void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args) { unsigned fastAccessLength = min(m_storage->m_length, m_fastAccessCutoff); unsigned i = 0; @@ -869,6 +924,19 @@ void JSArray::fillArgList(ExecState* exec, ArgList& args) args.append(get(exec, i)); } +void JSArray::copyToRegisters(ExecState* exec, Register* buffer, uint32_t maxSize) +{ + ASSERT(m_storage->m_length == maxSize); + UNUSED_PARAM(maxSize); + unsigned fastAccessLength = min(m_storage->m_length, m_fastAccessCutoff); + unsigned i = 0; + for (; i < fastAccessLength; ++i) + buffer[i] = getIndex(i); + uint32_t size = m_storage->m_length; + for (; i < size; ++i) + buffer[i] = get(exec, i); +} + unsigned JSArray::compactForSorting() { checkConsistency(); @@ -881,14 +949,14 @@ unsigned JSArray::compactForSorting() unsigned numUndefined = 0; for (; numDefined < usedVectorLength; ++numDefined) { - JSValuePtr v = storage->m_vector[numDefined]; - if (!v || v->isUndefined()) + JSValue v = storage->m_vector[numDefined]; + if (!v || v.isUndefined()) break; } for (unsigned i = numDefined; i < usedVectorLength; ++i) { - JSValuePtr v = storage->m_vector[i]; + JSValue v = storage->m_vector[i]; if (v) { - if (v->isUndefined()) + if (v.isUndefined()) ++numUndefined; else storage->m_vector[numDefined++] = v; @@ -918,7 +986,7 @@ unsigned JSArray::compactForSorting() for (unsigned i = numDefined; i < newUsedVectorLength; ++i) storage->m_vector[i] = jsUndefined(); for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i) - storage->m_vector[i] = noValue(); + storage->m_vector[i] = JSValue(); m_fastAccessCutoff = newUsedVectorLength; storage->m_numValuesInVector = newUsedVectorLength; @@ -951,7 +1019,7 @@ void JSArray::checkConsistency(ConsistencyCheckType type) unsigned numValuesInVector = 0; for (unsigned i = 0; i < m_storage->m_vectorLength; ++i) { - if (JSValuePtr value = m_storage->m_vector[i]) { + if (JSValue value = m_storage->m_vector[i]) { ASSERT(i < m_storage->m_length); if (type != DestructorConsistencyCheck) value->type(); // Likely to crash if the object was deallocated. @@ -990,16 +1058,16 @@ JSArray* constructEmptyArray(ExecState* exec, unsigned initialLength) return new (exec) JSArray(exec->lexicalGlobalObject()->arrayStructure(), initialLength); } -JSArray* constructArray(ExecState* exec, JSValuePtr singleItemValue) +JSArray* constructArray(ExecState* exec, JSValue singleItemValue) { - ArgList values; + MarkedArgumentBuffer values; values.append(singleItemValue); - return new (exec) JSArray(exec, exec->lexicalGlobalObject()->arrayStructure(), values); + return new (exec) JSArray(exec->lexicalGlobalObject()->arrayStructure(), values); } JSArray* constructArray(ExecState* exec, const ArgList& values) { - return new (exec) JSArray(exec, exec->lexicalGlobalObject()->arrayStructure(), values); + return new (exec) JSArray(exec->lexicalGlobalObject()->arrayStructure(), values); } } // namespace JSC |