X-Git-Url: https://git.saurik.com/apple/javascriptcore.git/blobdiff_plain/b5422865f473faf3977f31b96a635c4c8c4ede09..9dae56ea45a0f5f8136a5c93d6f3a7f99399ca73:/kjs/array_instance.cpp diff --git a/kjs/array_instance.cpp b/kjs/array_instance.cpp deleted file mode 100644 index fec5c09..0000000 --- a/kjs/array_instance.cpp +++ /dev/null @@ -1,612 +0,0 @@ -/* - * Copyright (C) 1999-2000 Harri Porten (porten@kde.org) - * Copyright (C) 2003, 2007 Apple Inc. All rights reserved. - * Copyright (C) 2003 Peter Kelly (pmk@post.com) - * Copyright (C) 2006 Alexey Proskuryakov (ap@nypop.com) - * - * This library is free software; you can redistribute it and/or - * modify it under the terms of the GNU Lesser General Public - * License as published by the Free Software Foundation; either - * version 2 of the License, or (at your option) any later version. - * - * This library is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - * Lesser General Public License for more details. - * - * You should have received a copy of the GNU Lesser General Public - * License along with this library; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA - * - */ - -#include "config.h" -#include "array_instance.h" - -#include "JSGlobalObject.h" -#include "PropertyNameArray.h" -#include - -using namespace std; - -namespace KJS { - -typedef HashMap SparseArrayValueMap; - -struct ArrayStorage { - unsigned m_numValuesInVector; - SparseArrayValueMap* m_sparseValueMap; - JSValue* m_vector[1]; -}; - -// 0xFFFFFFFF is a bit weird -- is not an array index even though it's an integer -static const unsigned maxArrayIndex = 0xFFFFFFFEU; - -// Our policy for when to use a vector and when to use a sparse map. -// For all array indices under sparseArrayCutoff, we always use a vector. -// When indices greater than sparseArrayCutoff are involved, we use a vector -// as long as it is 1/8 full. If more sparse than that, we use a map. -// This value has to be a macro to be used in max() and min() without introducing -// a PIC branch in Mach-O binaries, see . -#define sparseArrayCutoff 10000U -static const unsigned minDensityMultiplier = 8; - -static const unsigned copyingSortCutoff = 50000; - -const ClassInfo ArrayInstance::info = {"Array", 0, 0}; - -static inline size_t storageSize(unsigned vectorLength) -{ - return sizeof(ArrayStorage) - sizeof(JSValue*) + vectorLength * sizeof(JSValue*); -} - -static inline unsigned increasedVectorLength(unsigned newLength) -{ - return (newLength * 3 + 1) / 2; -} - -static inline bool isDenseEnoughForVector(unsigned length, unsigned numValues) -{ - return length / minDensityMultiplier <= numValues; -} - -ArrayInstance::ArrayInstance(JSObject* prototype, unsigned initialLength) - : JSObject(prototype) -{ - unsigned initialCapacity = min(initialLength, sparseArrayCutoff); - - m_length = initialLength; - m_vectorLength = initialCapacity; - m_storage = static_cast(fastZeroedMalloc(storageSize(initialCapacity))); - - Collector::reportExtraMemoryCost(initialCapacity * sizeof(JSValue*)); -} - -ArrayInstance::ArrayInstance(JSObject* prototype, const List& list) - : JSObject(prototype) -{ - unsigned length = list.size(); - - m_length = length; - m_vectorLength = length; - - ArrayStorage* storage = static_cast(fastMalloc(storageSize(length))); - - storage->m_numValuesInVector = length; - storage->m_sparseValueMap = 0; - - size_t i = 0; - List::const_iterator end = list.end(); - for (List::const_iterator it = list.begin(); it != end; ++it, ++i) - 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. -} - -ArrayInstance::~ArrayInstance() -{ - delete m_storage->m_sparseValueMap; - fastFree(m_storage); -} - -JSValue* ArrayInstance::getItem(unsigned i) const -{ - ASSERT(i <= maxArrayIndex); - - ArrayStorage* storage = m_storage; - - if (i < m_vectorLength) { - JSValue* value = storage->m_vector[i]; - return value ? value : jsUndefined(); - } - - SparseArrayValueMap* map = storage->m_sparseValueMap; - if (!map) - return jsUndefined(); - - JSValue* value = map->get(i); - return value ? value : jsUndefined(); -} - -JSValue* ArrayInstance::lengthGetter(ExecState*, JSObject*, const Identifier&, const PropertySlot& slot) -{ - return jsNumber(static_cast(slot.slotBase())->m_length); -} - -ALWAYS_INLINE bool ArrayInstance::inlineGetOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot) -{ - ArrayStorage* storage = m_storage; - - if (i >= m_length) { - if (i > maxArrayIndex) - return getOwnPropertySlot(exec, Identifier::from(i), slot); - return false; - } - - if (i < m_vectorLength) { - JSValue*& valueSlot = storage->m_vector[i]; - if (valueSlot) { - slot.setValueSlot(this, &valueSlot); - return true; - } - } else if (SparseArrayValueMap* map = storage->m_sparseValueMap) { - if (i >= sparseArrayCutoff) { - SparseArrayValueMap::iterator it = map->find(i); - if (it != map->end()) { - slot.setValueSlot(this, &it->second); - return true; - } - } - } - - return false; -} - -bool ArrayInstance::getOwnPropertySlot(ExecState* exec, const Identifier& propertyName, PropertySlot& slot) -{ - if (propertyName == exec->propertyNames().length) { - slot.setCustom(this, lengthGetter); - return true; - } - - bool isArrayIndex; - unsigned i = propertyName.toArrayIndex(&isArrayIndex); - if (isArrayIndex) - return inlineGetOwnPropertySlot(exec, i, slot); - - return JSObject::getOwnPropertySlot(exec, propertyName, slot); -} - -bool ArrayInstance::getOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot) -{ - return inlineGetOwnPropertySlot(exec, i, slot); -} - -// ECMA 15.4.5.1 -void ArrayInstance::put(ExecState* exec, const Identifier& propertyName, JSValue* value, int attributes) -{ - bool isArrayIndex; - unsigned i = propertyName.toArrayIndex(&isArrayIndex); - if (isArrayIndex) { - put(exec, i, value, attributes); - return; - } - - if (propertyName == exec->propertyNames().length) { - unsigned newLength = value->toUInt32(exec); - if (value->toNumber(exec) != static_cast(newLength)) { - throwError(exec, RangeError, "Invalid array length."); - return; - } - setLength(newLength); - return; - } - - JSObject::put(exec, propertyName, value, attributes); -} - -void ArrayInstance::put(ExecState* exec, unsigned i, JSValue* value, int attributes) -{ - if (i > maxArrayIndex) { - put(exec, Identifier::from(i), value, attributes); - return; - } - - ArrayStorage* storage = m_storage; - - unsigned length = m_length; - if (i >= length) { - length = i + 1; - m_length = length; - } - - if (i < m_vectorLength) { - JSValue*& valueSlot = storage->m_vector[i]; - storage->m_numValuesInVector += !valueSlot; - valueSlot = value; - return; - } - - SparseArrayValueMap* map = storage->m_sparseValueMap; - - if (i >= sparseArrayCutoff) { - // We miss some cases where we could compact the storage, such as a large array that is being filled from the end - // (which will only be compacted as we reach indices that are less than cutoff) - but this makes the check much faster. - if (!isDenseEnoughForVector(i + 1, storage->m_numValuesInVector + 1)) { - if (!map) { - map = new SparseArrayValueMap; - storage->m_sparseValueMap = map; - } - map->set(i, value); - return; - } - } - - // We have decided that we'll put the new item into the vector. - // Fast case is when there is no sparse map, so we can increase the vector size without moving values from it. - if (!map || map->isEmpty()) { - increaseVectorLength(i + 1); - storage = m_storage; - ++storage->m_numValuesInVector; - storage->m_vector[i] = value; - return; - } - - // Decide how many values it would be best to move from the map. - unsigned newNumValuesInVector = storage->m_numValuesInVector + 1; - unsigned newVectorLength = increasedVectorLength(i + 1); - for (unsigned j = max(m_vectorLength, sparseArrayCutoff); j < newVectorLength; ++j) - newNumValuesInVector += map->contains(j); - if (i >= sparseArrayCutoff) - newNumValuesInVector -= map->contains(i); - if (isDenseEnoughForVector(newVectorLength, newNumValuesInVector)) { - unsigned proposedNewNumValuesInVector = newNumValuesInVector; - while (true) { - unsigned proposedNewVectorLength = increasedVectorLength(newVectorLength + 1); - for (unsigned j = max(newVectorLength, sparseArrayCutoff); j < proposedNewVectorLength; ++j) - proposedNewNumValuesInVector += map->contains(j); - if (!isDenseEnoughForVector(proposedNewVectorLength, proposedNewNumValuesInVector)) - break; - newVectorLength = proposedNewVectorLength; - newNumValuesInVector = proposedNewNumValuesInVector; - } - } - - storage = static_cast(fastRealloc(storage, storageSize(newVectorLength))); - - unsigned vectorLength = m_vectorLength; - if (newNumValuesInVector == storage->m_numValuesInVector + 1) { - for (unsigned j = vectorLength; j < newVectorLength; ++j) - storage->m_vector[j] = 0; - if (i > sparseArrayCutoff) - map->remove(i); - } else { - for (unsigned j = vectorLength; j < max(vectorLength, sparseArrayCutoff); ++j) - storage->m_vector[j] = 0; - for (unsigned j = max(vectorLength, sparseArrayCutoff); j < newVectorLength; ++j) - storage->m_vector[j] = map->take(j); - } - - storage->m_vector[i] = value; - - m_vectorLength = newVectorLength; - storage->m_numValuesInVector = newNumValuesInVector; - - m_storage = storage; -} - -bool ArrayInstance::deleteProperty(ExecState* exec, const Identifier& propertyName) -{ - bool isArrayIndex; - unsigned i = propertyName.toArrayIndex(&isArrayIndex); - if (isArrayIndex) - return deleteProperty(exec, i); - - if (propertyName == exec->propertyNames().length) - return false; - - return JSObject::deleteProperty(exec, propertyName); -} - -bool ArrayInstance::deleteProperty(ExecState* exec, unsigned i) -{ - ArrayStorage* storage = m_storage; - - if (i < m_vectorLength) { - JSValue*& valueSlot = storage->m_vector[i]; - bool hadValue = valueSlot; - valueSlot = 0; - storage->m_numValuesInVector -= hadValue; - return hadValue; - } - - if (SparseArrayValueMap* map = storage->m_sparseValueMap) { - if (i >= sparseArrayCutoff) { - SparseArrayValueMap::iterator it = map->find(i); - if (it != map->end()) { - map->remove(it); - return true; - } - } - } - - if (i > maxArrayIndex) - return deleteProperty(exec, Identifier::from(i)); - - return false; -} - -void ArrayInstance::getPropertyNames(ExecState* exec, PropertyNameArray& propertyNames) -{ - // FIXME: Filling PropertyNameArray with an identifier for every integer - // is incredibly inefficient for large arrays. We need a different approach. - - ArrayStorage* storage = m_storage; - - unsigned usedVectorLength = min(m_length, m_vectorLength); - for (unsigned i = 0; i < usedVectorLength; ++i) { - if (storage->m_vector[i]) - propertyNames.add(Identifier::from(i)); - } - - if (SparseArrayValueMap* map = storage->m_sparseValueMap) { - SparseArrayValueMap::iterator end = map->end(); - for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) - propertyNames.add(Identifier::from(it->first)); - } - - JSObject::getPropertyNames(exec, propertyNames); -} - -void ArrayInstance::increaseVectorLength(unsigned newLength) -{ - // This function leaves the array in an internally inconsistent state, because it does not move any values from sparse value map - // to the vector. Callers have to account for that, because they can do it more efficiently. - - ArrayStorage* storage = m_storage; - - unsigned vectorLength = m_vectorLength; - ASSERT(newLength > vectorLength); - unsigned newVectorLength = increasedVectorLength(newLength); - - storage = static_cast(fastRealloc(storage, storageSize(newVectorLength))); - m_vectorLength = newVectorLength; - - for (unsigned i = vectorLength; i < newVectorLength; ++i) - storage->m_vector[i] = 0; - - m_storage = storage; -} - -void ArrayInstance::setLength(unsigned newLength) -{ - ArrayStorage* storage = m_storage; - - unsigned length = m_length; - - if (newLength < length) { - unsigned usedVectorLength = min(length, m_vectorLength); - for (unsigned i = newLength; i < usedVectorLength; ++i) { - JSValue*& valueSlot = storage->m_vector[i]; - bool hadValue = valueSlot; - valueSlot = 0; - storage->m_numValuesInVector -= hadValue; - } - - if (SparseArrayValueMap* map = storage->m_sparseValueMap) { - SparseArrayValueMap copy = *map; - SparseArrayValueMap::iterator end = copy.end(); - for (SparseArrayValueMap::iterator it = copy.begin(); it != end; ++it) { - if (it->first >= newLength) - map->remove(it->first); - } - if (map->isEmpty()) { - delete map; - storage->m_sparseValueMap = 0; - } - } - } - - m_length = newLength; -} - -void ArrayInstance::mark() -{ - JSObject::mark(); - - ArrayStorage* storage = m_storage; - - unsigned usedVectorLength = min(m_length, m_vectorLength); - for (unsigned i = 0; i < usedVectorLength; ++i) { - 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) { - JSValue* value = it->second; - if (!value->marked()) - value->mark(); - } - } -} - -static int compareByStringPairForQSort(const void* a, const void* b) -{ - const std::pair* va = static_cast*>(a); - const std::pair* vb = static_cast*>(b); - return compare(va->second, vb->second); -} - -static ExecState* execForCompareByStringForQSort = 0; -static int compareByStringForQSort(const void* a, const void* b) -{ - ExecState* exec = execForCompareByStringForQSort; - - JSValue* va = *static_cast(a); - JSValue* vb = *static_cast(b); - ASSERT(!va->isUndefined()); - ASSERT(!vb->isUndefined()); - - return compare(va->toString(exec), vb->toString(exec)); -} - -void ArrayInstance::sort(ExecState* exec) -{ - unsigned lengthNotIncludingUndefined = compactForSorting(); - - if (lengthNotIncludingUndefined < copyingSortCutoff) { - // Converting JavaScript values to strings can be expensive, so we do it once up front and sort based on that. - // This is a considerable improvement over doing it twice per comparison, though it requires a large temporary - // buffer. For large arrays, we fall back to a qsort on the JavaScriptValues to avoid creating copies. - - Vector > values(lengthNotIncludingUndefined); - for (size_t i = 0; i < lengthNotIncludingUndefined; i++) { - JSValue* value = m_storage->m_vector[i]; - ASSERT(!value->isUndefined()); - values[i].first = value; - values[i].second = value->toString(exec); - } - - // FIXME: Since we sort by string value, a fast algorithm might be to use a radix sort. That would be O(N) rather - // than O(N log N). - -#if HAVE(MERGESORT) - mergesort(values.begin(), values.size(), sizeof(std::pair), compareByStringPairForQSort); -#else - qsort(values.begin(), values.size(), sizeof(std::pair), compareByStringPairForQSort); -#endif - for (size_t i = 0; i < lengthNotIncludingUndefined; i++) - m_storage->m_vector[i] = values[i].first; - return; - } - - ExecState* oldExec = execForCompareByStringForQSort; - execForCompareByStringForQSort = exec; - qsort(m_storage->m_vector, lengthNotIncludingUndefined, sizeof(JSValue*), compareByStringForQSort); - execForCompareByStringForQSort = oldExec; -} - -struct CompareWithCompareFunctionArguments { - CompareWithCompareFunctionArguments(ExecState *e, JSObject *cf) - : exec(e) - , compareFunction(cf) - , globalObject(e->dynamicGlobalObject()) - { - } - - ExecState *exec; - JSObject *compareFunction; - List arguments; - JSGlobalObject* globalObject; -}; - -static CompareWithCompareFunctionArguments* compareWithCompareFunctionArguments = 0; - -static int compareWithCompareFunctionForQSort(const void* a, const void* b) -{ - CompareWithCompareFunctionArguments *args = compareWithCompareFunctionArguments; - - JSValue* va = *static_cast(a); - JSValue* vb = *static_cast(b); - ASSERT(!va->isUndefined()); - ASSERT(!vb->isUndefined()); - - args->arguments.clear(); - args->arguments.append(va); - args->arguments.append(vb); - double compareResult = args->compareFunction->call - (args->exec, args->globalObject, args->arguments)->toNumber(args->exec); - return compareResult < 0 ? -1 : compareResult > 0 ? 1 : 0; -} - -void ArrayInstance::sort(ExecState* exec, JSObject* compareFunction) -{ - size_t lengthNotIncludingUndefined = compactForSorting(); - - CompareWithCompareFunctionArguments* oldArgs = compareWithCompareFunctionArguments; - CompareWithCompareFunctionArguments args(exec, compareFunction); - compareWithCompareFunctionArguments = &args; - -#if HAVE(MERGESORT) - // Because mergesort usually does fewer compares, it is faster than qsort here. - // However, because it requires extra copies of the storage buffer, don't use it for very - // large arrays. - - // FIXME: A tree sort using a perfectly balanced tree (e.g. an AVL tree) could do an even - // better job of minimizing compares. - - if (lengthNotIncludingUndefined < copyingSortCutoff) { - // During the sort, we could do a garbage collect, and it's important to still - // have references to every object in the array for ArrayInstance::mark. - // The mergesort algorithm does not guarantee this, so we sort a copy rather - // than the original. - size_t size = storageSize(m_vectorLength); - ArrayStorage* copy = static_cast(fastMalloc(size)); - memcpy(copy, m_storage, size); - mergesort(copy->m_vector, lengthNotIncludingUndefined, sizeof(JSValue*), compareWithCompareFunctionForQSort); - fastFree(m_storage); - m_storage = copy; - compareWithCompareFunctionArguments = oldArgs; - return; - } -#endif - - qsort(m_storage->m_vector, lengthNotIncludingUndefined, sizeof(JSValue*), compareWithCompareFunctionForQSort); - compareWithCompareFunctionArguments = oldArgs; -} - -unsigned ArrayInstance::compactForSorting() -{ - ArrayStorage* storage = m_storage; - - unsigned usedVectorLength = min(m_length, m_vectorLength); - - unsigned numDefined = 0; - unsigned numUndefined = 0; - - for (; numDefined < usedVectorLength; ++numDefined) { - JSValue* v = storage->m_vector[numDefined]; - if (!v || v->isUndefined()) - break; - } - for (unsigned i = numDefined; i < usedVectorLength; ++i) { - if (JSValue* v = storage->m_vector[i]) { - if (v->isUndefined()) - ++numUndefined; - else - storage->m_vector[numDefined++] = v; - } - } - - unsigned newUsedVectorLength = numDefined + numUndefined; - - if (SparseArrayValueMap* map = storage->m_sparseValueMap) { - newUsedVectorLength += map->size(); - if (newUsedVectorLength > m_vectorLength) { - increaseVectorLength(newUsedVectorLength); - storage = m_storage; - } - - SparseArrayValueMap::iterator end = map->end(); - for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) - storage->m_vector[numDefined++] = it->second; - - delete map; - storage->m_sparseValueMap = 0; - } - - for (unsigned i = numDefined; i < newUsedVectorLength; ++i) - storage->m_vector[i] = jsUndefined(); - for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i) - storage->m_vector[i] = 0; - - return numDefined; -} - -}