JavaScriptCore:
authordarin <darin@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 22 Oct 2007 13:35:17 +0000 (13:35 +0000)
committerdarin <darin@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 22 Oct 2007 13:35:17 +0000 (13:35 +0000)
        Reviewed by Maciej.

        - http://bugs.webkit.org/show_bug.cgi?id=15606
          make cut-off for sparse vs. dense arrays smarter for speed with large arrays

        Makes the morph test in SunSpider 26% faster, and the overall
        benchmark 3% faster.

        This also fixes some small problems we had with the distinction
        between nonexistent and undefined values in arrays.

        * kjs/array_instance.h: Tweaked formatting and naming.
        * kjs/array_instance.cpp: Copied from kjs/array_object.cpp.
        (KJS::storageSize): Added. Computes the size of the storage given a vector length.
        (KJS::increasedVectorLength): Added. Implements the rule for resizing the vector.
        (KJS::isDenseEnoughForVector): Added.
        (KJS::ArrayInstance::ArrayInstance): Initialize the new fields.
        (KJS::ArrayInstance::~ArrayInstance): Since m_storage is now never 0, delete it.
        (KJS::ArrayInstance::getItem): Updated for name changes.
        (KJS::ArrayInstance::lengthGetter): Ditto.
        (KJS::ArrayInstance::inlineGetOwnPropertySlot): Added. Allows both versions of
        getOwnPropertySlot to share more code.
        (KJS::ArrayInstance::getOwnPropertySlot): Just refactored, no code change.
        (KJS::ArrayInstance::put): Added logic for extending the vector as long as the
        array is dense enough. Also keep m_numValuesInVector up to date.
        (KJS::ArrayInstance::deleteProperty): Added code to keep m_numValuesInVector
        up to date.
        (KJS::ArrayInstance::getPropertyNames): Fixed bug where this would omit names
        for array indices with undefined values.
        (KJS::ArrayInstance::increaseVectorLength): Renamed from resizeStorage. Also
        simplified to only handle getting larger.
        (KJS::ArrayInstance::setLength): Added code to update m_numValuesInVector, to
        zero out the unused part of the vector and to delete the map if it's no longer
        needed.
        (KJS::ArrayInstance::mark): Tweaked formatting.
        (KJS::compareByStringForQSort): Ditto.
        (KJS::ArrayInstance::sort): Ditto.
        (KJS::CompareWithCompareFunctionArguments::CompareWithCompareFunctionArguments):
        Ditto.
        (KJS::compareWithCompareFunctionForQSort): Ditto.
        (KJS::ArrayInstance::compactForSorting): Fixed bug where this would turn
        undefined values into nonexistent values in some cases.

        * kjs/array_object.h: Removed MAX_ARRAY_INDEX.
        * kjs/array_object.cpp: Removed ArrayInstance. Moved to a separate file.

        * JavaScriptCore.pri: Added array_instance.cpp.
        * JavaScriptCore.xcodeproj/project.pbxproj: Ditto.
        * kjs/AllInOneFile.cpp: Ditto.

LayoutTests:

        * fast/js/kde/resources/Array.js: Added tests to cover missing value behavior
        (not the same as undefined values in arrays). This matches the ECMA JavaScript
        specification, but doesn't exactly match Firefox.
        * fast/js/kde/Array-expected.txt: Updated with results.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@26881 268f45cc-cd09-0410-ab3c-d52691b4dbfc

12 files changed:
JavaScriptCore/ChangeLog
JavaScriptCore/JavaScriptCore.pri
JavaScriptCore/JavaScriptCore.vcproj/JavaScriptCore/JavaScriptCore.vcproj
JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
JavaScriptCore/kjs/AllInOneFile.cpp
JavaScriptCore/kjs/array_instance.cpp [new file with mode: 0644]
JavaScriptCore/kjs/array_instance.h
JavaScriptCore/kjs/array_object.cpp
JavaScriptCore/kjs/array_object.h
LayoutTests/ChangeLog
LayoutTests/fast/js/kde/Array-expected.txt
LayoutTests/fast/js/kde/resources/Array.js

index 8b323b9213e163488dbc51b462016b0509c9916e..890a81a7b37dda1b98d543e2f141ed8da7fe804e 100644 (file)
@@ -1,3 +1,55 @@
+2007-10-22  Darin Adler  <darin@apple.com>
+
+        Reviewed by Maciej.
+
+        - http://bugs.webkit.org/show_bug.cgi?id=15606
+          make cut-off for sparse vs. dense arrays smarter for speed with large arrays
+
+        Makes the morph test in SunSpider 26% faster, and the overall
+        benchmark 3% faster.
+
+        This also fixes some small problems we had with the distinction
+        between nonexistent and undefined values in arrays.
+
+        * kjs/array_instance.h: Tweaked formatting and naming.
+        * kjs/array_instance.cpp: Copied from kjs/array_object.cpp.
+        (KJS::storageSize): Added. Computes the size of the storage given a vector length.
+        (KJS::increasedVectorLength): Added. Implements the rule for resizing the vector.
+        (KJS::isDenseEnoughForVector): Added.
+        (KJS::ArrayInstance::ArrayInstance): Initialize the new fields.
+        (KJS::ArrayInstance::~ArrayInstance): Since m_storage is now never 0, delete it.
+        (KJS::ArrayInstance::getItem): Updated for name changes.
+        (KJS::ArrayInstance::lengthGetter): Ditto.
+        (KJS::ArrayInstance::inlineGetOwnPropertySlot): Added. Allows both versions of
+        getOwnPropertySlot to share more code.
+        (KJS::ArrayInstance::getOwnPropertySlot): Just refactored, no code change.
+        (KJS::ArrayInstance::put): Added logic for extending the vector as long as the
+        array is dense enough. Also keep m_numValuesInVector up to date.
+        (KJS::ArrayInstance::deleteProperty): Added code to keep m_numValuesInVector
+        up to date.
+        (KJS::ArrayInstance::getPropertyNames): Fixed bug where this would omit names
+        for array indices with undefined values.
+        (KJS::ArrayInstance::increaseVectorLength): Renamed from resizeStorage. Also
+        simplified to only handle getting larger.
+        (KJS::ArrayInstance::setLength): Added code to update m_numValuesInVector, to
+        zero out the unused part of the vector and to delete the map if it's no longer
+        needed.
+        (KJS::ArrayInstance::mark): Tweaked formatting.
+        (KJS::compareByStringForQSort): Ditto.
+        (KJS::ArrayInstance::sort): Ditto.
+        (KJS::CompareWithCompareFunctionArguments::CompareWithCompareFunctionArguments):
+        Ditto.
+        (KJS::compareWithCompareFunctionForQSort): Ditto.
+        (KJS::ArrayInstance::compactForSorting): Fixed bug where this would turn
+        undefined values into nonexistent values in some cases.
+
+        * kjs/array_object.h: Removed MAX_ARRAY_INDEX.
+        * kjs/array_object.cpp: Removed ArrayInstance. Moved to a separate file.
+
+        * JavaScriptCore.pri: Added array_instance.cpp.
+        * JavaScriptCore.xcodeproj/project.pbxproj: Ditto.
+        * kjs/AllInOneFile.cpp: Ditto.
+
 2007-10-22  Andrew Wellington  <proton@wiretapped.net>
 
         Reviewed by Mark Rowe.
index fca5b1e92c0d4f5904f704da1d57c9edee15ec92..3389299880055487ea174ba89528632ccd0caace 100644 (file)
@@ -56,6 +56,7 @@ SOURCES += \
     kjs/DateMath.cpp \
     kjs/JSWrapperObject.cpp \
     kjs/PropertyNameArray.cpp \
+    kjs/array_instance.cpp \
     kjs/array_object.cpp \
     kjs/bool_object.cpp \
     kjs/collector.cpp \
index 4c50b30c774b876f00c749a70ec1490d9b9aea6b..d7b6a952d53416a720e55cc1df229d735e884ead 100644 (file)
                <Filter\r
                        Name="KJS"\r
                        >\r
+                       <File\r
+                               RelativePath="..\..\kjs\array_instance.cpp"\r
+                               >\r
+                       </File>\r
                        <File\r
                                RelativePath="..\..\kjs\array_instance.h"\r
                                >\r
index f85113b5a5f7b612afa2d073a482bc106f8dca47..30e1201608cb2a1a04ab7786afda307ba4d77dc2 100644 (file)
                938C4F690CA06BC700D9310A /* ASCIICType.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ASCIICType.h; sourceTree = "<group>"; };
                938C4F6B0CA06BCE00D9310A /* DisallowCType.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = DisallowCType.h; sourceTree = "<group>"; };
                93AA4F770957251F0084B3A7 /* AlwaysInline.h */ = {isa = PBXFileReference; fileEncoding = 4; indentWidth = 4; lastKnownFileType = sourcecode.c.h; path = AlwaysInline.h; sourceTree = "<group>"; tabWidth = 8; };
+               93ADFCE60CCBD7AC00D30B08 /* array_instance.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = array_instance.cpp; sourceTree = "<group>"; };
                93B6A0DE0AA64DA40076DE27 /* GetPtr.h */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.c.h; path = GetPtr.h; sourceTree = "<group>"; };
                93E26BC908B1511900F85226 /* pcre_ord2utf8.c */ = {isa = PBXFileReference; fileEncoding = 30; indentWidth = 4; lastKnownFileType = sourcecode.c.c; name = pcre_ord2utf8.c; path = pcre/pcre_ord2utf8.c; sourceTree = "<group>"; tabWidth = 8; };
                93E26BD308B1514100F85226 /* pcre_xclass.c */ = {isa = PBXFileReference; fileEncoding = 30; indentWidth = 4; lastKnownFileType = sourcecode.c.c; name = pcre_xclass.c; path = pcre/pcre_xclass.c; sourceTree = "<group>"; tabWidth = 8; };
                                65400C0F0A69BAF200509887 /* PropertyNameArray.cpp */,
                                65400C100A69BAF200509887 /* PropertyNameArray.h */,
                                938772E5038BFE19008635CE /* array_instance.h */,
+                               93ADFCE60CCBD7AC00D30B08 /* array_instance.cpp */,
                                659126BC0BDD1728001921FB /* AllInOneFile.cpp */,
                                F692A84D0255597D01FF60F7 /* array_object.cpp */,
                                F692A84E0255597D01FF60F7 /* array_object.h */,
index 527924299dcfa2ee73d9115e7b58f15214cce432..795c790bdb6707dfe983cb770970a3bc2b042dfe 100644 (file)
@@ -28,6 +28,7 @@
 
 #include "function.cpp"
 #include "debugger.cpp"
+#include "array_instance.cpp"
 #include "array_object.cpp"
 #include "bool_object.cpp"
 #include "collector.cpp"
diff --git a/JavaScriptCore/kjs/array_instance.cpp b/JavaScriptCore/kjs/array_instance.cpp
new file mode 100644 (file)
index 0000000..23557f1
--- /dev/null
@@ -0,0 +1,599 @@
+/*
+ *  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 "PropertyNameArray.h"
+#include <wtf/Assertions.h>
+
+namespace KJS {
+
+typedef HashMap<unsigned, JSValue*> 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.
+static const unsigned sparseArrayCutoff = 10000;
+static const unsigned minDensityMultiplier = 8;
+
+static const unsigned mergeSortCutoff = 10000;
+
+const ClassInfo ArrayInstance::info = {"Array", 0, 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<ArrayStorage*>(fastCalloc(storageSize(initialCapacity), 1));
+
+    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<ArrayStorage*>(fastMalloc(storageSize(length)));
+
+    storage->m_numValuesInVector = length;
+    storage->m_sparseValueMap = 0;
+
+    ListIterator it = list.begin();
+    for (unsigned i = 0; i < length; ++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<ArrayInstance*>(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) {
+        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<double>(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;
+    }
+
+    if (i < sparseArrayCutoff) {
+        increaseVectorLength(i + 1);
+        storage = m_storage;
+        ++storage->m_numValuesInVector;
+        storage->m_vector[i] = value;
+        return;
+    }
+
+    SparseArrayValueMap* map = storage->m_sparseValueMap;
+    if (!map || map->isEmpty()) {
+        if (isDenseEnoughForVector(i + 1, storage->m_numValuesInVector + 1)) {
+            increaseVectorLength(i + 1);
+            storage = m_storage;
+            ++storage->m_numValuesInVector;
+            storage->m_vector[i] = value;
+            return;
+        }
+        if (!map) {
+            map = new SparseArrayValueMap;
+            storage->m_sparseValueMap = map;
+        }
+        map->add(i, value);
+        return;
+    }
+
+    unsigned newNumValuesInVector = storage->m_numValuesInVector + 1;
+    if (!isDenseEnoughForVector(i + 1, newNumValuesInVector)) {
+        map->add(i, value);
+        return;
+    }
+
+    unsigned newVectorLength = increasedVectorLength(i + 1);
+    for (unsigned j = m_vectorLength; j < newVectorLength; ++j)
+        newNumValuesInVector += map->contains(j);
+    newNumValuesInVector -= map->contains(i);
+    if (isDenseEnoughForVector(newVectorLength, newNumValuesInVector)) {
+        unsigned proposedNewNumValuesInVector = newNumValuesInVector;
+        while (true) {
+            unsigned proposedNewVectorLength = increasedVectorLength(newVectorLength + 1);
+            for (unsigned j = newVectorLength; j < proposedNewVectorLength; ++j)
+                proposedNewNumValuesInVector += map->contains(j);
+            if (!isDenseEnoughForVector(proposedNewVectorLength, proposedNewNumValuesInVector))
+                break;
+            newVectorLength = proposedNewVectorLength;
+            newNumValuesInVector = proposedNewNumValuesInVector;
+        }
+    }
+
+    storage = static_cast<ArrayStorage*>(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;
+        map->remove(i);
+    } else {
+        for (unsigned j = vectorLength; j < newVectorLength; ++j) {
+            SparseArrayValueMap::iterator it = map->find(j);
+            if (it == map->end())
+                storage->m_vector[j] = 0;
+            else {
+                storage->m_vector[j] = it->second;
+                map->remove(it);
+            }
+        }
+    }
+
+    storage->m_vector[i] = value;
+
+    m_vectorLength = newVectorLength;
+    storage->m_numValuesInVector = newNumValuesInVector;
+}
+
+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) {
+        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)
+{
+    ArrayStorage* storage = m_storage;
+
+    unsigned vectorLength = m_vectorLength;
+    ASSERT(newLength > vectorLength);
+    unsigned newVectorLength = increasedVectorLength(newLength);
+
+    storage = static_cast<ArrayStorage*>(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 copy = *map;
+        SparseArrayValueMap::iterator end = copy.end();
+        for (SparseArrayValueMap::iterator it = copy.begin(); it != end; ++it) {
+            JSValue* value = it->second;
+            if (!value->marked())
+                value->mark();
+        }
+    }
+}
+
+static ExecState* execForCompareByStringForQSort = 0;
+
+static int compareByStringForQSort(const void* a, const void* b)
+{
+    ExecState* exec = execForCompareByStringForQSort;
+
+    JSValue* va = *static_cast<JSValue* const*>(a);
+    JSValue* vb = *static_cast<JSValue* const*>(b);
+    ASSERT(!va->isUndefined());
+    ASSERT(!vb->isUndefined());
+
+    return compare(va->toString(exec), vb->toString(exec));
+}
+
+void ArrayInstance::sort(ExecState* exec)
+{
+    unsigned lengthNotIncludingUndefined = compactForSorting();
+
+    ExecState* oldExec = execForCompareByStringForQSort;
+    execForCompareByStringForQSort = exec;
+
+#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: Since we sort by string value, a fast algorithm might be to convert all the
+    // values to string once up front, and then use a radix sort. That would be O(N) rather
+    // than O(N log N).
+
+    if (lengthNotIncludingUndefined < mergeSortCutoff) {
+        // 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<ArrayStorage*>(fastMalloc(size));
+        memcpy(copy, m_storage, size);
+        mergesort(copy->m_vector, lengthNotIncludingUndefined, sizeof(JSValue*), compareByStringForQSort);
+        fastFree(m_storage);
+        m_storage = copy;
+        execForCompareByStringForQSort = oldExec;
+        return;
+    }
+#endif
+
+    qsort(m_storage->m_vector, lengthNotIncludingUndefined, sizeof(JSValue*), compareByStringForQSort);
+    execForCompareByStringForQSort = oldExec;
+}
+
+struct CompareWithCompareFunctionArguments {
+    CompareWithCompareFunctionArguments(ExecState *e, JSObject *cf)
+        : exec(e)
+        , compareFunction(cf)
+        , globalObject(e->dynamicInterpreter()->globalObject())
+    {
+    }
+
+    ExecState *exec;
+    JSObject *compareFunction;
+    List arguments;
+    JSObject *globalObject;
+};
+
+static CompareWithCompareFunctionArguments* compareWithCompareFunctionArguments = 0;
+
+static int compareWithCompareFunctionForQSort(const void* a, const void* b)
+{
+    CompareWithCompareFunctionArguments *args = compareWithCompareFunctionArguments;
+
+    JSValue* va = *static_cast<JSValue* const*>(a);
+    JSValue* vb = *static_cast<JSValue* const*>(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 < mergeSortCutoff) {
+        // 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<ArrayStorage*>(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;
+}
+
+}
index a0d8ef079f262c5953da4841420c1e95d79ab06b..913d0cdcf1455be07fbeecb861cf3387f2dfaf11 100644 (file)
@@ -1,6 +1,5 @@
 // -*- c-basic-offset: 2 -*-
 /*
- *  This file is part of the KDE libraries
  *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
  *  Copyright (C) 2003, 2007 Apple Inc. All rights reserved.
  *
 
 namespace KJS {
 
+  struct ArrayStorage;
+
   class ArrayInstance : public JSObject {
   public:
-    ArrayInstance(JSObject *proto, unsigned initialLength);
-    ArrayInstance(JSObject *proto, const List &initialValues);
+    ArrayInstance(JSObject* prototype, unsigned initialLength);
+    ArrayInstance(JSObject* prototype, const List& initialValues);
     ~ArrayInstance();
 
-    virtual bool getOwnPropertySlot(ExecState *, const Identifier&, PropertySlot&);
-    virtual bool getOwnPropertySlot(ExecState *, unsigned, PropertySlot&);
-    virtual void put(ExecState *exec, const Identifier &propertyName, JSValue *value, int attr = None);
-    virtual void put(ExecState *exec, unsigned propertyName, JSValue *value, int attr = None);
-    virtual bool deleteProperty(ExecState *exec, const Identifier &propertyName);
-    virtual bool deleteProperty(ExecState *exec, unsigned propertyName);
+    virtual bool getOwnPropertySlot(ExecState*, const Identifier& propertyName, PropertySlot&);
+    virtual bool getOwnPropertySlot(ExecState*, unsigned propertyName, PropertySlot&);
+    virtual void put(ExecState*, const Identifier& propertyName, JSValue*, int attributes = None);
+    virtual void put(ExecState*, unsigned propertyName, JSValue*, int attributes = None);
+    virtual bool deleteProperty(ExecState *, const Identifier& propertyName);
+    virtual bool deleteProperty(ExecState *, unsigned propertyName);
     virtual void getPropertyNames(ExecState*, PropertyNameArray&);
 
     virtual void mark();
 
-    virtual const ClassInfo *classInfo() const { return &info; }
+    virtual const ClassInfoclassInfo() const { return &info; }
     static const ClassInfo info;
-    
-    unsigned getLength() const { return length; }
+
+    unsigned getLength() const { return m_length; }
     JSValue* getItem(unsigned) const;
-    
-    void sort(ExecState *exec);
-    void sort(ExecState *exec, JSObject *compareFunction);
-    
+
+    void sort(ExecState*);
+    void sort(ExecState*, JSObject* compareFunction);
+
   private:
-    static JSValue *lengthGetter(ExecState *, JSObject *, const Identifier&, const PropertySlot&);
+    static JSValue* lengthGetter(ExecState*, JSObject*, const Identifier&, const PropertySlot&);
+    bool inlineGetOwnPropertySlot(ExecState*, unsigned propertyName, PropertySlot&);
 
-    void setLength(unsigned newLength);
+    void setLength(unsigned);
+    void increaseVectorLength(unsigned newLength);
     
-    unsigned compactForSorting();
-    
-    void resizeStorage(unsigned);
-
-    // store capacity in extra space at the beginning of the storage array to save space
-    size_t capacity() { return storage ? reinterpret_cast<size_t>(storage[-1]) : 0; }
+    unsigned compactForSorting();    
 
-    unsigned length;
-    unsigned storageLength;
-    JSValue **storage;
+    unsigned m_length;
+    unsigned m_vectorLength;
+    ArrayStorage* m_storage;
   };
 
 } // namespace KJS
index 156634ab5573112d67d55d18ef988c3a5df88778..811dedac1e7c00f75bf4471bd2a6299f5c17bb83 100644 (file)
@@ -1,6 +1,5 @@
 // -*- c-basic-offset: 2 -*-
 /*
- *  This file is part of the KDE libraries
  *  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)
@@ -26,7 +25,6 @@
 #include "array_object.h"
 #include "array_object.lut.h"
 
-#include "PropertyNameArray.h"
 #include "error_object.h"
 #include "lookup.h"
 #include "operations.h"
 #include <wtf/Assertions.h>
 #include <wtf/HashSet.h>
 
-
 namespace KJS {
 
-typedef HashMap<unsigned, JSValue*> OverflowMap;
-
-static inline OverflowMap* overflowMap(JSValue** storage)
-{
-    return storage ? reinterpret_cast<OverflowMap*>(storage[-2]) : 0;
-}
-
-// ------------------------------ ArrayInstance -----------------------------
-
-const unsigned sparseArrayCutoff = 10000;
-
-const ClassInfo ArrayInstance::info = {"Array", 0, 0, 0};
-
-static inline JSValue** allocateStorage(size_t capacity)
-{
-  if (capacity == 0)
-      return 0;
-
-  // store capacity and overflow map in extra space before the beginning of the storage array to save space
-  JSValue** storage = static_cast<JSValue**>(fastCalloc(capacity + 2, sizeof(JSValue *))) + 2;
-  storage[-1] = reinterpret_cast<JSValue*>(capacity);
-  return storage;
-}
-
-static inline void reallocateStorage(JSValue**& storage, size_t newCapacity)
-{
-  if (!storage) {
-    storage = allocateStorage(newCapacity);
-    return;
-  }
-
-  // store capacity and overflow map in extra space before the beginning of the storage array to save space
-  storage = static_cast<JSValue**>(fastRealloc(storage - 2, (newCapacity + 2) * sizeof (JSValue*))) + 2;
-  storage[-1] = reinterpret_cast<JSValue*>(newCapacity);
-}
-
-static inline void freeStorage(JSValue** storage)
-{
-    if (storage)
-        fastFree(storage - 2);
-}
-
-ArrayInstance::ArrayInstance(JSObject *proto, unsigned initialLength)
-  : JSObject(proto)
-  , length(initialLength)
-  , storageLength(initialLength < sparseArrayCutoff ? initialLength : 0)
-  , storage(allocateStorage(storageLength))
-{
-  Collector::reportExtraMemoryCost(storageLength * sizeof(JSValue*));
-}
-
-ArrayInstance::ArrayInstance(JSObject *proto, const List &list)
-  : JSObject(proto)
-  , length(list.size())
-  , storageLength(length)
-  , storage(allocateStorage(storageLength))
-{
-  ListIterator it = list.begin();
-  unsigned l = length;
-  for (unsigned i = 0; i < l; ++i)
-    storage[i] = it++;
-  // 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()
-{
-  if (storage) {
-    delete reinterpret_cast<OverflowMap*>(storage[-2]);
-    freeStorage(storage);
-  }
-}
-
-JSValue* ArrayInstance::getItem(unsigned i) const
-{
-    if (i < storageLength) {
-        JSValue* value = storage[i];
-        return value ? value : jsUndefined();
-    }
-
-    const OverflowMap* overflow = overflowMap(storage);
-    if (!overflow)
-        return jsUndefined();
-
-    JSValue* value = overflow->get(i);
-    return value ? value : jsUndefined();
-}
-
-JSValue *ArrayInstance::lengthGetter(ExecState*, JSObject*, const Identifier&, const PropertySlot& slot)
-{
-  return jsNumber(static_cast<ArrayInstance *>(slot.slotBase())->length);
-}
-
-bool ArrayInstance::getOwnPropertySlot(ExecState* exec, const Identifier& propertyName, PropertySlot& slot)
-{
-  if (propertyName == exec->propertyNames().length) {
-    slot.setCustom(this, lengthGetter);
-    return true;
-  }
-
-  bool ok;
-  unsigned index = propertyName.toArrayIndex(&ok);
-  if (!ok)
-    return JSObject::getOwnPropertySlot(exec, propertyName, slot);
-
-  if (index < storageLength) {
-    JSValue *v = storage[index];
-    if (!v)
-      return false;      
-    slot.setValueSlot(this, &storage[index]);
-    return true;
-  }
-  if (index > MAX_ARRAY_INDEX)
-    return JSObject::getOwnPropertySlot(exec, propertyName, slot);
-  OverflowMap* overflow = overflowMap(storage);
-  if (!overflow)
-    return false;
-  OverflowMap::iterator it = overflow->find(index);
-  if (it == overflow->end())
-    return false;
-  slot.setValueSlot(this, &it->second);
-  return true;
-}
-
-bool ArrayInstance::getOwnPropertySlot(ExecState *exec, unsigned index, PropertySlot& slot)
-{
-  if (index < storageLength) {
-    JSValue *v = storage[index];
-    if (!v)
-      return false;
-    slot.setValueSlot(this, &storage[index]);
-    return true;
-  }
-  if (index > MAX_ARRAY_INDEX)
-    return getOwnPropertySlot(exec, Identifier::from(index), slot);
-  OverflowMap* overflow = overflowMap(storage);
-  if (!overflow)
-    return false;
-  OverflowMap::iterator it = overflow->find(index);
-  if (it == overflow->end())
-    return false;
-  slot.setValueSlot(this, &it->second);
-  return true;
-}
-
-// Special implementation of [[Put]] - see ECMA 15.4.5.1
-void ArrayInstance::put(ExecState* exec, const Identifier& propertyName, JSValue* value, int attr)
-{
-  if (propertyName == exec->propertyNames().length) {
-    unsigned int newLen = value->toUInt32(exec);
-    if (value->toNumber(exec) != double(newLen)) {
-      throwError(exec, RangeError, "Invalid array length.");
-      return;
-    }
-    setLength(newLen);
-    return;
-  }
-
-  bool ok;
-  unsigned index = propertyName.toArrayIndex(&ok);
-  if (ok) {
-    put(exec, index, value, attr);
-    return;
-  }
-
-  JSObject::put(exec, propertyName, value, attr);
-}
-
-void ArrayInstance::put(ExecState *exec, unsigned index, JSValue *value, int attr)
-{
-  // 0xFFFFFFFF is a bit weird --- it should be treated as a non-array index, even when it's a string 
-  if (index > MAX_ARRAY_INDEX) {
-    put(exec, Identifier::from(index), value, attr);
-    return;
-  }
-
-  if (index < sparseArrayCutoff && index >= storageLength)
-    resizeStorage(index + 1);
-
-  if (index >= length)
-    length = index + 1;
-
-  if (index < storageLength) {
-    storage[index] = value;
-    return;
-  }
-
-  OverflowMap* overflow = overflowMap(storage);
-  if (!overflow) {
-    overflow = new OverflowMap;
-    if (!storage)
-      storage = allocateStorage(1);
-    storage[-2] = reinterpret_cast<JSValue*>(overflow);
-  }
-  overflow->add(index, value);
-}
-
-bool ArrayInstance::deleteProperty(ExecState* exec, const Identifier &propertyName)
-{
-  if (propertyName == exec->propertyNames().length)
-    return false;
-
-  bool ok;
-  uint32_t index = propertyName.toArrayIndex(&ok);
-  if (ok) {
-    if (index >= length)
-      return true;
-    if (index < storageLength) {
-      storage[index] = 0;
-      return true;
-    }
-    if (OverflowMap* overflow = overflowMap(storage)) {
-      OverflowMap::iterator it = overflow->find(index);
-      if (it == overflow->end())
-        return false;
-      overflow->remove(it);
-      return true;
-    }
-    return false;
-  }
-
-  return JSObject::deleteProperty(exec, propertyName);
-}
-
-bool ArrayInstance::deleteProperty(ExecState *exec, unsigned index)
-{
-  if (index > MAX_ARRAY_INDEX)
-    return deleteProperty(exec, Identifier::from(index));
-
-  if (index >= length)
-    return true;
-  if (index < storageLength) {
-    storage[index] = 0;
-    return true;
-  }
-  OverflowMap* overflow = overflowMap(storage);
-  if (!overflow)
-    return false;
-  OverflowMap::iterator it = overflow->find(index);
-  if (it == overflow->end())
-    return false;
-  overflow->remove(it);
-  return true;
-}
-
-void ArrayInstance::getPropertyNames(ExecState* exec, PropertyNameArray& propertyNames)
-{
-  // avoid fetching this every time through the loop
-  JSValue* undefined = jsUndefined();
-  
-  for (unsigned i = 0; i < storageLength; ++i) {
-    JSValue* value = storage[i];
-    if (value && value != undefined)
-      propertyNames.add(Identifier::from(i));
-  }
-
-  OverflowMap* overflow = overflowMap(storage);
-  if (overflow) {
-    OverflowMap::iterator end = overflow->end();
-    for (OverflowMap::iterator it = overflow->begin(); it != end; ++it) {
-      JSValue* value = it->second;
-      if (value && value != undefined)
-        propertyNames.add(Identifier::from(it->first));
-    }
-  }
-  JSObject::getPropertyNames(exec, propertyNames);
-}
-
-void ArrayInstance::resizeStorage(unsigned newLength)
-{
-    if (newLength < storageLength) {
-      memset(storage + newLength, 0, sizeof(JSValue *) * (storageLength - newLength));
-    }
-    size_t cap = capacity();
-    if (newLength > cap) {
-      unsigned newCapacity;
-      if (newLength > sparseArrayCutoff) {
-        newCapacity = newLength;
-      } else {
-        newCapacity = (newLength * 3 + 1) / 2;
-        if (newCapacity > sparseArrayCutoff) {
-          newCapacity = sparseArrayCutoff;
-        }
-      }
-      
-      reallocateStorage(storage, newCapacity);
-      memset(storage + cap, 0, sizeof(JSValue*) * (newCapacity - cap));
-    }
-    storageLength = newLength;
-}
-
-void ArrayInstance::setLength(unsigned newLength)
-{
-  if (newLength <= storageLength)
-    resizeStorage(newLength);
-
-  if (newLength < length) {
-    if (OverflowMap* overflow = overflowMap(storage)) {
-      OverflowMap copy = *overflow;
-      OverflowMap::iterator end = copy.end();
-      for (OverflowMap::iterator it = copy.begin(); it != end; ++it) {
-        if (it->first >= newLength)
-          overflow->remove(it->first);
-      }
-    }
-  }
-  
-  length = newLength;
-}
-
-void ArrayInstance::mark()
-{
-  JSObject::mark();
-  unsigned l = storageLength;
-  for (unsigned i = 0; i < l; ++i) {
-    JSValue* imp = storage[i];
-    if (imp && !imp->marked())
-      imp->mark();
-  }
-  if (OverflowMap* overflow = overflowMap(storage)) {
-    OverflowMap::iterator end = overflow->end();
-    for (OverflowMap::iterator it = overflow->begin(); it != end; ++it) {
-      JSValue* value = it->second;
-      if (value && !value->marked())
-        value->mark();
-    }
-  }
-}
-
-static ExecState* execForCompareByStringForQSort = 0;
-
-static int compareByStringForQSort(const void *a, const void *b)
-{
-    ExecState *exec = execForCompareByStringForQSort;
-    JSValue *va = *(JSValue **)a;
-    JSValue *vb = *(JSValue **)b;
-    ASSERT(!va->isUndefined());
-    ASSERT(!vb->isUndefined());
-    return compare(va->toString(exec), vb->toString(exec));
-}
-
-void ArrayInstance::sort(ExecState* exec)
-{
-    size_t lengthNotIncludingUndefined = compactForSorting();
-      
-    ExecState* oldExec = execForCompareByStringForQSort;
-    execForCompareByStringForQSort = exec;
-#if HAVE(MERGESORT)
-    // mergesort usually does fewer compares, so it is actually faster than qsort for JS sorts.
-    // however, becuase it requires extra copies of the storage buffer, don't use it for very
-    // large arrays
-    // FIXME: for sorting by string value, the fastest thing would actually be to convert all the
-    // values to string once up front, and then use a radix sort. That would be O(N) rather than 
-    // O(N log N).
-    if (lengthNotIncludingUndefined < sparseArrayCutoff) {
-        JSValue** storageCopy = allocateStorage(capacity());
-        memcpy(storageCopy, storage, capacity() * sizeof(JSValue*));
-        mergesort(storageCopy, lengthNotIncludingUndefined, sizeof(JSValue *), compareByStringForQSort);
-        freeStorage(storage);
-        storage = storageCopy;
-        execForCompareByStringForQSort = oldExec;
-        return;
-    }
-#endif
-
-    qsort(storage, lengthNotIncludingUndefined, sizeof(JSValue*), compareByStringForQSort);
-    execForCompareByStringForQSort = oldExec;
-}
-
-struct CompareWithCompareFunctionArguments {
-    CompareWithCompareFunctionArguments(ExecState *e, JSObject *cf)
-        : exec(e)
-        , compareFunction(cf)
-        , globalObject(e->dynamicInterpreter()->globalObject())
-    {
-        arguments.append(jsUndefined());
-        arguments.append(jsUndefined());
-    }
-
-    ExecState *exec;
-    JSObject *compareFunction;
-    List arguments;
-    JSObject *globalObject;
-};
-
-static CompareWithCompareFunctionArguments* compareWithCompareFunctionArguments = 0;
-
-static int compareWithCompareFunctionForQSort(const void *a, const void *b)
-{
-    CompareWithCompareFunctionArguments *args = compareWithCompareFunctionArguments;
-
-    JSValue *va = *(JSValue **)a;
-    JSValue *vb = *(JSValue **)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)
-    // mergesort usually does fewer compares, so it is actually faster than qsort for JS sorts.
-    // however, becuase 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 < sparseArrayCutoff) {
-        JSValue** storageCopy = allocateStorage(capacity());
-        memcpy(storageCopy, storage, capacity() * sizeof(JSValue*));
-        mergesort(storageCopy, lengthNotIncludingUndefined, sizeof(JSValue *), compareWithCompareFunctionForQSort);
-        freeStorage(storage);
-        storage = storageCopy;
-        compareWithCompareFunctionArguments = oldArgs;
-        return;
-    }
-#endif
-    qsort(storage, lengthNotIncludingUndefined, sizeof(JSValue*), compareWithCompareFunctionForQSort);
-    compareWithCompareFunctionArguments = oldArgs;
-}
-
-unsigned ArrayInstance::compactForSorting()
-{
-    JSValue *undefined = jsUndefined();
-
-    unsigned o = 0;
-    
-    for (unsigned i = 0; i != storageLength; ++i) {
-        JSValue *v = storage[i];
-        if (v && v != undefined) {
-            if (o != i)
-                storage[o] = v;
-            o++;
-        }
-    }
-   
-    unsigned newLength = o;
-
-    if (OverflowMap* overflow = overflowMap(storage)) {
-        OverflowMap::iterator end = overflow->end();
-        for (OverflowMap::iterator it = overflow->begin(); it != end; ++it)
-            newLength += it->second != undefined;
-    
-        if (newLength > storageLength)
-            resizeStorage(newLength);
-    
-        for (OverflowMap::iterator it = overflow->begin(); it != end; ++it) {
-            JSValue* v = it->second;
-            if (v != undefined) {
-                storage[o] = v;
-                o++;
-            }
-        }
-        delete overflow;
-        storage[-2] = 0;
-    }
-    
-    if (newLength != storageLength)
-        memset(storage + o, 0, sizeof(JSValue *) * (storageLength - o));
-    
-    return o;
-}
-
 // ------------------------------ ArrayPrototype ----------------------------
 
 const ClassInfo ArrayPrototype::info = {"Array", &ArrayInstance::info, &arrayTable, 0};
index b59c43cc3e527c17682a984178c0558c44a74265..f2ef7818faea10f5e3b4bc86200e5d1f2272b6e1 100644 (file)
@@ -49,8 +49,6 @@ namespace KJS {
     int id;
   };
 
-  const unsigned MAX_ARRAY_INDEX = 0xFFFFFFFEu;
-
   class ArrayObjectImp : public InternalFunctionImp {
   public:
     ArrayObjectImp(ExecState *exec,
index abc626a133f9d73df48f5950b910218c1500d6a8..773ebb422212619ab00440f4f15418fae083b995 100644 (file)
@@ -1,3 +1,10 @@
+2007-10-22  Darin Adler  <darin@apple.com>
+
+        * fast/js/kde/resources/Array.js: Added tests to cover missing value behavior
+        (not the same as undefined values in arrays). This matches the ECMA JavaScript
+        specification, but doesn't exactly match Firefox.
+        * fast/js/kde/Array-expected.txt: Updated with results.
+
 2007-10-21  Mark Rowe  <mrowe@apple.com>
 
         Reviewed by Mitz.
@@ -10,8 +17,6 @@
 
 2007-10-21  Nikolas Zimmermann  <zimmermann@kde.org>
 
-        Not reviewed.
-
         Forgot to land the new computed style results in fast/css - after the addition of glyph-orientation-*.
 
         * fast/css/computed-style-expected.txt:
index 021a76e701f2f68c852c37d9c1dd9923d91b454d..00216aa12c0b34bc0d5eb867ec32040653fc5e24 100644 (file)
@@ -45,14 +45,23 @@ PASS [].length is 0
 PASS ['a'].length is 1
 PASS ['a'][0] is 'a'
 PASS ['a',,'c'][2] is 'c'
+PASS ['a',undefined,'c'][1] is undefined
+PASS ['a',,'c'][1] is undefined
+PASS 1 in ['a',,'c'] is false
+PASS 1 in ['a',undefined,'c'] is true
+PASS 1 in arrayWithDeletion is false
 PASS forInSum([]) is ''
 PASS forInSum(Array()) is ''
 PASS forInSum(Array('a')) is 'a'
+PASS forInSum([,undefined,'x','aa']) is 'undefinedxaa'
 PASS forInSum(a0) is ''
 PASS forInSum(a1) is 'a'
 PASS String([].sort()) is ''
 PASS String([3,1,'2'].sort()) is '1,2,3'
 PASS String([,'x','aa'].sort()) is 'aa,x,'
+PASS String([,undefined,'x','aa'].sort()) is 'aa,x,,'
+PASS 2 in [,undefined,'x','aa'].sort() is true
+PASS 3 in [,undefined,'x','aa'].sort() is false
 PASS var a = ['aa', 'b', 'cccc', 'ddd']; String(a.sort(comp)) is 'b,aa,ddd,cccc'
 PASS [0, Infinity].sort(function(a, b) { return a - b }).toString() is '0,Infinity'
 PASS [].unshift('a') is 1
index 4418019c5efa3a2e09937dbf2131a47e4ed43b12..0b2b40a3f4c34dbced17209976446caa0f5abbcf 100644 (file)
@@ -72,6 +72,14 @@ shouldBe("[].length", "0");
 shouldBe("['a'].length", "1");
 shouldBe("['a'][0]", "'a'");
 shouldBe("['a',,'c'][2]", "'c'");
+shouldBe("['a',undefined,'c'][1]", "undefined");
+shouldBe("['a',,'c'][1]", "undefined");
+shouldBe("1 in ['a',,'c']", "false");
+shouldBe("1 in ['a',undefined,'c']", "true");
+
+var arrayWithDeletion = ['a','b','c'];
+delete arrayWithDeletion[1];
+shouldBe("1 in arrayWithDeletion", "false");
 
 function forInSum(_a) {
   var s = '';
@@ -83,6 +91,7 @@ function forInSum(_a) {
 shouldBe("forInSum([])", "''");
 shouldBe("forInSum(Array())", "''");
 shouldBe("forInSum(Array('a'))", "'a'");
+shouldBe("forInSum([,undefined,'x','aa'])", "'undefinedxaa'");
 
 var a0 = [];
 shouldBe("forInSum(a0)", "''");
@@ -92,7 +101,10 @@ shouldBe("forInSum(a1)", "'a'");
 
 shouldBe("String([].sort())", "''")
 shouldBe("String([3,1,'2'].sort())", "'1,2,3'");
-shouldBe("String([,'x','aa'].sort())", "'aa,x,'"); // don't assume 'x'>undefined !
+shouldBe("String([,'x','aa'].sort())", "'aa,x,'");
+shouldBe("String([,undefined,'x','aa'].sort())", "'aa,x,,'");
+shouldBe("2 in [,undefined,'x','aa'].sort()", "true");
+shouldBe("3 in [,undefined,'x','aa'].sort()", "false");
 
 // sort by length
 function comp(a, b) {