Changeset 26881 in webkit for trunk/JavaScriptCore


Ignore:
Timestamp:
Oct 22, 2007, 6:35:17 AM (18 years ago)
Author:
darin
Message:

JavaScriptCore:

Reviewed by Maciej.

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.

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.
Location:
trunk/JavaScriptCore
Files:
8 edited
1 copied

Legend:

Unmodified
Added
Removed

  • trunk/JavaScriptCore/ChangeLog

    r26880 r26881  
     12007-10-22  Darin Adler  <[email protected]>
     2
     3        Reviewed by Maciej.
     4
     5        - http://bugs.webkit.org/show_bug.cgi?id=15606
     6          make cut-off for sparse vs. dense arrays smarter for speed with large arrays
     7
     8        Makes the morph test in SunSpider 26% faster, and the overall
     9        benchmark 3% faster.
     10
     11        This also fixes some small problems we had with the distinction
     12        between nonexistent and undefined values in arrays.
     13
     14        * kjs/array_instance.h: Tweaked formatting and naming.
     15        * kjs/array_instance.cpp: Copied from kjs/array_object.cpp.
     16        (KJS::storageSize): Added. Computes the size of the storage given a vector length.
     17        (KJS::increasedVectorLength): Added. Implements the rule for resizing the vector.
     18        (KJS::isDenseEnoughForVector): Added.
     19        (KJS::ArrayInstance::ArrayInstance): Initialize the new fields.
     20        (KJS::ArrayInstance::~ArrayInstance): Since m_storage is now never 0, delete it.
     21        (KJS::ArrayInstance::getItem): Updated for name changes.
     22        (KJS::ArrayInstance::lengthGetter): Ditto.
     23        (KJS::ArrayInstance::inlineGetOwnPropertySlot): Added. Allows both versions of
     24        getOwnPropertySlot to share more code.
     25        (KJS::ArrayInstance::getOwnPropertySlot): Just refactored, no code change.
     26        (KJS::ArrayInstance::put): Added logic for extending the vector as long as the
     27        array is dense enough. Also keep m_numValuesInVector up to date.
     28        (KJS::ArrayInstance::deleteProperty): Added code to keep m_numValuesInVector
     29        up to date.
     30        (KJS::ArrayInstance::getPropertyNames): Fixed bug where this would omit names
     31        for array indices with undefined values.
     32        (KJS::ArrayInstance::increaseVectorLength): Renamed from resizeStorage. Also
     33        simplified to only handle getting larger.
     34        (KJS::ArrayInstance::setLength): Added code to update m_numValuesInVector, to
     35        zero out the unused part of the vector and to delete the map if it's no longer
     36        needed.
     37        (KJS::ArrayInstance::mark): Tweaked formatting.
     38        (KJS::compareByStringForQSort): Ditto.
     39        (KJS::ArrayInstance::sort): Ditto.
     40        (KJS::CompareWithCompareFunctionArguments::CompareWithCompareFunctionArguments):
     41        Ditto.
     42        (KJS::compareWithCompareFunctionForQSort): Ditto.
     43        (KJS::ArrayInstance::compactForSorting): Fixed bug where this would turn
     44        undefined values into nonexistent values in some cases.
     45
     46        * kjs/array_object.h: Removed MAX_ARRAY_INDEX.
     47        * kjs/array_object.cpp: Removed ArrayInstance. Moved to a separate file.
     48
     49        * JavaScriptCore.pri: Added array_instance.cpp.
     50        * JavaScriptCore.xcodeproj/project.pbxproj: Ditto.
     51        * kjs/AllInOneFile.cpp: Ditto.
     52
    1532007-10-22  Andrew Wellington  <[email protected]>
    254

  • trunk/JavaScriptCore/JavaScriptCore.pri

    r26699 r26881  
    5757    kjs/JSWrapperObject.cpp \
    5858    kjs/PropertyNameArray.cpp \
     59    kjs/array_instance.cpp \
    5960    kjs/array_object.cpp \
    6061    kjs/bool_object.cpp \

  • trunk/JavaScriptCore/JavaScriptCore.vcproj/JavaScriptCore/JavaScriptCore.vcproj

    r26704 r26881  
    176176                        >
    177177                        <File
     178                                RelativePath="..\..\kjs\array_instance.cpp"
     179                                >
     180                        </File>
     181                        <File
    178182                                RelativePath="..\..\kjs\array_instance.h"
    179183                                >

  • trunk/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj

    r26787 r26881  
    575575                938C4F6B0CA06BCE00D9310A /* DisallowCType.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = DisallowCType.h; sourceTree = "<group>"; };
    576576                93AA4F770957251F0084B3A7 /* AlwaysInline.h */ = {isa = PBXFileReference; fileEncoding = 4; indentWidth = 4; lastKnownFileType = sourcecode.c.h; path = AlwaysInline.h; sourceTree = "<group>"; tabWidth = 8; };
     577                93ADFCE60CCBD7AC00D30B08 /* array_instance.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = array_instance.cpp; sourceTree = "<group>"; };
    577578                93B6A0DE0AA64DA40076DE27 /* GetPtr.h */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.c.h; path = GetPtr.h; sourceTree = "<group>"; };
    578579                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; };
    … …  
    952953                                65400C100A69BAF200509887 /* PropertyNameArray.h */,
    953954                                938772E5038BFE19008635CE /* array_instance.h */,
     955                                93ADFCE60CCBD7AC00D30B08 /* array_instance.cpp */,
    954956                                659126BC0BDD1728001921FB /* AllInOneFile.cpp */,
    955957                                F692A84D0255597D01FF60F7 /* array_object.cpp */,

  • trunk/JavaScriptCore/kjs/AllInOneFile.cpp

    r25754 r26881  
    2929#include "function.cpp"
    3030#include "debugger.cpp"
     31#include "array_instance.cpp"
    3132#include "array_object.cpp"
    3233#include "bool_object.cpp"

  • trunk/JavaScriptCore/kjs/array_instance.cpp

    r26859 r26881  
    1 // -*- c-basic-offset: 2 -*-
    21/*
    3  *  This file is part of the KDE libraries
    42 *  Copyright (C) 1999-2000 Harri Porten ([email protected])
    53 *  Copyright (C) 2003, 2007 Apple Inc. All rights reserved.
    … …  
    2422
    2523#include "config.h"
    26 #include "array_object.h"
    27 #include "array_object.lut.h"
     24#include "array_instance.h"
    2825
    2926#include "PropertyNameArray.h"
    30 #include "error_object.h"
    31 #include "lookup.h"
    32 #include "operations.h"
    33 #include <stdio.h>
    3427#include <wtf/Assertions.h>
    35 #include <wtf/HashSet.h>
    36 
    3728
    3829namespace KJS {
    3930
    40 typedef HashMap<unsigned, JSValue*> OverflowMap;
    41 
    42 static inline OverflowMap* overflowMap(JSValue** storage)
    43 {
    44     return storage ? reinterpret_cast<OverflowMap*>(storage[-2]) : 0;
    45 }
    46 
    47 // ------------------------------ ArrayInstance -----------------------------
    48 
    49 const unsigned sparseArrayCutoff = 10000;
     31typedef HashMap<unsigned, JSValue*> SparseArrayValueMap;
     32
     33struct ArrayStorage {
     34    unsigned m_numValuesInVector;
     35    SparseArrayValueMap* m_sparseValueMap;
     36    JSValue* m_vector[1];
     37};
     38
     39// 0xFFFFFFFF is a bit weird -- is not an array index even though it's an integer
     40static const unsigned maxArrayIndex = 0xFFFFFFFEU;
     41
     42// Our policy for when to use a vector and when to use a sparse map.
     43// For all array indices under sparseArrayCutoff, we always use a vector.
     44// When indices greater than sparseArrayCutoff are involved, we use a vector
     45// as long as it is 1/8 full. If more sparse than that, we use a map.
     46static const unsigned sparseArrayCutoff = 10000;
     47static const unsigned minDensityMultiplier = 8;
     48
     49static const unsigned mergeSortCutoff = 10000;
    5050
    5151const ClassInfo ArrayInstance::info = {"Array", 0, 0, 0};
    5252
    53 static inline JSValue** allocateStorage(size_t capacity)
    54 {
    55   if (capacity == 0)
    56       return 0;
    57 
    58   // store capacity and overflow map in extra space before the beginning of the storage array to save space
    59   JSValue** storage = static_cast<JSValue**>(fastCalloc(capacity + 2, sizeof(JSValue *))) + 2;
    60   storage[-1] = reinterpret_cast<JSValue*>(capacity);
    61   return storage;
    62 }
    63 
    64 static inline void reallocateStorage(JSValue**& storage, size_t newCapacity)
    65 {
    66   if (!storage) {
    67     storage = allocateStorage(newCapacity);
    68     return;
    69   }
    70 
    71   // store capacity and overflow map in extra space before the beginning of the storage array to save space
    72   storage = static_cast<JSValue**>(fastRealloc(storage - 2, (newCapacity + 2) * sizeof (JSValue*))) + 2;
    73   storage[-1] = reinterpret_cast<JSValue*>(newCapacity);
    74 }
    75 
    76 static inline void freeStorage(JSValue** storage)
    77 {
    78   fastFree(storage - 2);
    79 }
    80 
    81 ArrayInstance::ArrayInstance(JSObject *proto, unsigned initialLength)
    82   : JSObject(proto)
    83   , length(initialLength)
    84   , storageLength(initialLength < sparseArrayCutoff ? initialLength : 0)
    85   , storage(allocateStorage(storageLength))
    86 {
    87   Collector::reportExtraMemoryCost(storageLength * sizeof(JSValue*));
    88 }
    89 
    90 ArrayInstance::ArrayInstance(JSObject *proto, const List &list)
    91   : JSObject(proto)
    92   , length(list.size())
    93   , storageLength(length)
    94   , storage(allocateStorage(storageLength))
    95 {
    96   ListIterator it = list.begin();
    97   unsigned l = length;
    98   for (unsigned i = 0; i < l; ++i)
    99     storage[i] = it++;
    100   // When the array is created non-empty, its cells are filled so it's really no worse than
    101   // a property map. Therefore don't report extra memory cost.
     53static inline size_t storageSize(unsigned vectorLength)
     54{
     55    return sizeof(ArrayStorage) - sizeof(JSValue*) + vectorLength * sizeof(JSValue*);
     56}
     57
     58static inline unsigned increasedVectorLength(unsigned newLength)
     59{
     60    return (newLength * 3 + 1) / 2;
     61}
     62
     63static inline bool isDenseEnoughForVector(unsigned length, unsigned numValues)
     64{
     65    return length / minDensityMultiplier <= numValues;
     66}
     67
     68ArrayInstance::ArrayInstance(JSObject* prototype, unsigned initialLength)
     69    : JSObject(prototype)
     70{
     71    unsigned initialCapacity = min(initialLength, sparseArrayCutoff);
     72
     73    m_length = initialLength;
     74    m_vectorLength = initialCapacity;
     75    m_storage = static_cast<ArrayStorage*>(fastCalloc(storageSize(initialCapacity), 1));
     76
     77    Collector::reportExtraMemoryCost(initialCapacity * sizeof(JSValue*));
     78}
     79
     80ArrayInstance::ArrayInstance(JSObject* prototype, const List& list)
     81    : JSObject(prototype)
     82{
     83    unsigned length = list.size();
     84
     85    m_length = length;
     86    m_vectorLength = length;
     87
     88    ArrayStorage* storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(length)));
     89
     90    storage->m_numValuesInVector = length;
     91    storage->m_sparseValueMap = 0;
     92
     93    ListIterator it = list.begin();
     94    for (unsigned i = 0; i < length; ++i)
     95        storage->m_vector[i] = it++;
     96
     97    m_storage = storage;
     98
     99    // When the array is created non-empty, its cells are filled, so it's really no worse than
     100    // a property map. Therefore don't report extra memory cost.
    102101}
    103102
    104103ArrayInstance::~ArrayInstance()
    105104{
    106   if (storage) {
    107     delete reinterpret_cast<OverflowMap*>(storage[-2]);
    108     freeStorage(storage);
    109   }
     105    delete m_storage->m_sparseValueMap;
     106    fastFree(m_storage);
    110107}
    111108
    112109JSValue* ArrayInstance::getItem(unsigned i) const
    113110{
    114     if (i < storageLength) {
    115         JSValue* value = storage[i];
     111    ASSERT(i <= maxArrayIndex);
     112
     113    ArrayStorage* storage = m_storage;
     114
     115    if (i < m_vectorLength) {
     116        JSValue* value = storage->m_vector[i];
    116117        return value ? value : jsUndefined();
    117118    }
    118119
    119     const OverflowMap* overflow = overflowMap(storage);
    120     if (!overflow)
     120    SparseArrayValueMap* map = storage->m_sparseValueMap;
     121    if (!map)
    121122        return jsUndefined();
    122123
    123     JSValue* value = overflow->get(i);
     124    JSValue* value = map->get(i);
    124125    return value ? value : jsUndefined();
    125126}
    126127
    127 JSValue *ArrayInstance::lengthGetter(ExecState*, JSObject*, const Identifier&, const PropertySlot& slot)
    128 {
    129   return jsNumber(static_cast<ArrayInstance *>(slot.slotBase())->length);
     128JSValue* ArrayInstance::lengthGetter(ExecState*, JSObject*, const Identifier&, const PropertySlot& slot)
     129{
     130    return jsNumber(static_cast<ArrayInstance*>(slot.slotBase())->m_length);
     131}
     132
     133ALWAYS_INLINE bool ArrayInstance::inlineGetOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot)
     134{
     135    ArrayStorage* storage = m_storage;
     136
     137    if (i >= m_length) {
     138        if (i > maxArrayIndex)
     139            return getOwnPropertySlot(exec, Identifier::from(i), slot);
     140        return false;
     141    }
     142
     143    if (i < m_vectorLength) {
     144        JSValue*& valueSlot = storage->m_vector[i];
     145        if (valueSlot) {
     146            slot.setValueSlot(this, &valueSlot);
     147            return true;
     148        }
     149    } else if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
     150        SparseArrayValueMap::iterator it = map->find(i);
     151        if (it != map->end()) {
     152            slot.setValueSlot(this, &it->second);
     153            return true;
     154        }
     155    }
     156
     157    return false;
    130158}
    131159
    132160bool ArrayInstance::getOwnPropertySlot(ExecState* exec, const Identifier& propertyName, PropertySlot& slot)
    133161{
    134   if (propertyName == exec->propertyNames().length) {
    135     slot.setCustom(this, lengthGetter);
    136     return true;
    137   }
    138 
    139   bool ok;
    140   unsigned index = propertyName.toArrayIndex(&ok);
    141   if (!ok)
     162    if (propertyName == exec->propertyNames().length) {
     163        slot.setCustom(this, lengthGetter);
     164        return true;
     165    }
     166
     167    bool isArrayIndex;
     168    unsigned i = propertyName.toArrayIndex(&isArrayIndex);
     169    if (isArrayIndex)
     170        return inlineGetOwnPropertySlot(exec, i, slot);
     171
    142172    return JSObject::getOwnPropertySlot(exec, propertyName, slot);
    143 
    144   if (index < storageLength) {
    145     JSValue *v = storage[index];
    146     if (!v)
    147       return false;     
    148     slot.setValueSlot(this, &storage[index]);
    149     return true;
    150   }
    151   if (index > MAX_ARRAY_INDEX)
    152     return JSObject::getOwnPropertySlot(exec, propertyName, slot);
    153   OverflowMap* overflow = overflowMap(storage);
    154   if (!overflow)
     173}
     174
     175bool ArrayInstance::getOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot)
     176{
     177    return inlineGetOwnPropertySlot(exec, i, slot);
     178}
     179
     180// ECMA 15.4.5.1
     181void ArrayInstance::put(ExecState* exec, const Identifier& propertyName, JSValue* value, int attributes)
     182{
     183    bool isArrayIndex;
     184    unsigned i = propertyName.toArrayIndex(&isArrayIndex);
     185    if (isArrayIndex) {
     186        put(exec, i, value, attributes);
     187        return;
     188    }
     189
     190    if (propertyName == exec->propertyNames().length) {
     191        unsigned newLength = value->toUInt32(exec);
     192        if (value->toNumber(exec) != static_cast<double>(newLength)) {
     193            throwError(exec, RangeError, "Invalid array length.");
     194            return;
     195        }
     196        setLength(newLength);
     197        return;
     198    }
     199
     200    JSObject::put(exec, propertyName, value, attributes);
     201}
     202
     203void ArrayInstance::put(ExecState* exec, unsigned i, JSValue* value, int attributes)
     204{
     205    if (i > maxArrayIndex) {
     206        put(exec, Identifier::from(i), value, attributes);
     207        return;
     208    }
     209
     210    ArrayStorage* storage = m_storage;
     211
     212    unsigned length = m_length;
     213    if (i >= length) {
     214        length = i + 1;
     215        m_length = length;
     216    }
     217
     218    if (i < m_vectorLength) {
     219        JSValue*& valueSlot = storage->m_vector[i];
     220        storage->m_numValuesInVector += !valueSlot;
     221        valueSlot = value;
     222        return;
     223    }
     224
     225    if (i < sparseArrayCutoff) {
     226        increaseVectorLength(i + 1);
     227        storage = m_storage;
     228        ++storage->m_numValuesInVector;
     229        storage->m_vector[i] = value;
     230        return;
     231    }
     232
     233    SparseArrayValueMap* map = storage->m_sparseValueMap;
     234    if (!map || map->isEmpty()) {
     235        if (isDenseEnoughForVector(i + 1, storage->m_numValuesInVector + 1)) {
     236            increaseVectorLength(i + 1);
     237            storage = m_storage;
     238            ++storage->m_numValuesInVector;
     239            storage->m_vector[i] = value;
     240            return;
     241        }
     242        if (!map) {
     243            map = new SparseArrayValueMap;
     244            storage->m_sparseValueMap = map;
     245        }
     246        map->add(i, value);
     247        return;
     248    }
     249
     250    unsigned newNumValuesInVector = storage->m_numValuesInVector + 1;
     251    if (!isDenseEnoughForVector(i + 1, newNumValuesInVector)) {
     252        map->add(i, value);
     253        return;
     254    }
     255
     256    unsigned newVectorLength = increasedVectorLength(i + 1);
     257    for (unsigned j = m_vectorLength; j < newVectorLength; ++j)
     258        newNumValuesInVector += map->contains(j);
     259    newNumValuesInVector -= map->contains(i);
     260    if (isDenseEnoughForVector(newVectorLength, newNumValuesInVector)) {
     261        unsigned proposedNewNumValuesInVector = newNumValuesInVector;
     262        while (true) {
     263            unsigned proposedNewVectorLength = increasedVectorLength(newVectorLength + 1);
     264            for (unsigned j = newVectorLength; j < proposedNewVectorLength; ++j)
     265                proposedNewNumValuesInVector += map->contains(j);
     266            if (!isDenseEnoughForVector(proposedNewVectorLength, proposedNewNumValuesInVector))
     267                break;
     268            newVectorLength = proposedNewVectorLength;
     269            newNumValuesInVector = proposedNewNumValuesInVector;
     270        }
     271    }
     272
     273    storage = static_cast<ArrayStorage*>(fastRealloc(storage, storageSize(newVectorLength)));
     274
     275    unsigned vectorLength = m_vectorLength;
     276    if (newNumValuesInVector == storage->m_numValuesInVector + 1) {
     277        for (unsigned j = vectorLength; j < newVectorLength; ++j)
     278            storage->m_vector[j] = 0;
     279        map->remove(i);
     280    } else {
     281        for (unsigned j = vectorLength; j < newVectorLength; ++j) {
     282            SparseArrayValueMap::iterator it = map->find(j);
     283            if (it == map->end())
     284                storage->m_vector[j] = 0;
     285            else {
     286                storage->m_vector[j] = it->second;
     287                map->remove(it);
     288            }
     289        }
     290    }
     291
     292    storage->m_vector[i] = value;
     293
     294    m_vectorLength = newVectorLength;
     295    storage->m_numValuesInVector = newNumValuesInVector;
     296}
     297
     298bool ArrayInstance::deleteProperty(ExecState* exec, const Identifier& propertyName)
     299{
     300    bool isArrayIndex;
     301    unsigned i = propertyName.toArrayIndex(&isArrayIndex);
     302    if (isArrayIndex)
     303        return deleteProperty(exec, i);
     304
     305    if (propertyName == exec->propertyNames().length)
     306        return false;
     307
     308    return JSObject::deleteProperty(exec, propertyName);
     309}
     310
     311bool ArrayInstance::deleteProperty(ExecState* exec, unsigned i)
     312{
     313    ArrayStorage* storage = m_storage;
     314
     315    if (i < m_vectorLength) {
     316        JSValue*& valueSlot = storage->m_vector[i];
     317        bool hadValue = valueSlot;
     318        valueSlot = 0;
     319        storage->m_numValuesInVector -= hadValue;
     320        return hadValue;
     321    }
     322
     323    if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
     324        SparseArrayValueMap::iterator it = map->find(i);
     325        if (it != map->end()) {
     326            map->remove(it);
     327            return true;
     328        }
     329    }
     330
     331    if (i > maxArrayIndex)
     332        return deleteProperty(exec, Identifier::from(i));
     333
    155334    return false;
    156   OverflowMap::iterator it = overflow->find(index);
    157   if (it == overflow->end())
    158     return false;
    159   slot.setValueSlot(this, &it->second);
    160   return true;
    161 }
    162 
    163 bool ArrayInstance::getOwnPropertySlot(ExecState *exec, unsigned index, PropertySlot& slot)
    164 {
    165   if (index < storageLength) {
    166     JSValue *v = storage[index];
    167     if (!v)
    168       return false;
    169     slot.setValueSlot(this, &storage[index]);
    170     return true;
    171   }
    172   if (index > MAX_ARRAY_INDEX)
    173     return getOwnPropertySlot(exec, Identifier::from(index), slot);
    174   OverflowMap* overflow = overflowMap(storage);
    175   if (!overflow)
    176     return false;
    177   OverflowMap::iterator it = overflow->find(index);
    178   if (it == overflow->end())
    179     return false;
    180   slot.setValueSlot(this, &it->second);
    181   return true;
    182 }
    183 
    184 // Special implementation of [[Put]] - see ECMA 15.4.5.1
    185 void ArrayInstance::put(ExecState* exec, const Identifier& propertyName, JSValue* value, int attr)
    186 {
    187   if (propertyName == exec->propertyNames().length) {
    188     unsigned int newLen = value->toUInt32(exec);
    189     if (value->toNumber(exec) != double(newLen)) {
    190       throwError(exec, RangeError, "Invalid array length.");
    191       return;
    192     }
    193     setLength(newLen);
    194     return;
    195   }
    196 
    197   bool ok;
    198   unsigned index = propertyName.toArrayIndex(&ok);
    199   if (ok) {
    200     put(exec, index, value, attr);
    201     return;
    202   }
    203 
    204   JSObject::put(exec, propertyName, value, attr);
    205 }
    206 
    207 void ArrayInstance::put(ExecState *exec, unsigned index, JSValue *value, int attr)
    208 {
    209   // 0xFFFFFFFF is a bit weird --- it should be treated as a non-array index, even when it's a string
    210   if (index > MAX_ARRAY_INDEX) {
    211     put(exec, Identifier::from(index), value, attr);
    212     return;
    213   }
    214 
    215   if (index < sparseArrayCutoff && index >= storageLength)
    216     resizeStorage(index + 1);
    217 
    218   if (index >= length)
    219     length = index + 1;
    220 
    221   if (index < storageLength) {
    222     storage[index] = value;
    223     return;
    224   }
    225 
    226   OverflowMap* overflow = overflowMap(storage);
    227   if (!overflow) {
    228     overflow = new OverflowMap;
    229     if (!storage)
    230       storage = allocateStorage(1);
    231     storage[-2] = reinterpret_cast<JSValue*>(overflow);
    232   }
    233   overflow->add(index, value);
    234 }
    235 
    236 bool ArrayInstance::deleteProperty(ExecState* exec, const Identifier &propertyName)
    237 {
    238   if (propertyName == exec->propertyNames().length)
    239     return false;
    240 
    241   bool ok;
    242   uint32_t index = propertyName.toArrayIndex(&ok);
    243   if (ok) {
    244     if (index >= length)
    245       return true;
    246     if (index < storageLength) {
    247       storage[index] = 0;
    248       return true;
    249     }
    250     if (OverflowMap* overflow = overflowMap(storage)) {
    251       OverflowMap::iterator it = overflow->find(index);
    252       if (it == overflow->end())
    253         return false;
    254       overflow->remove(it);
    255       return true;
    256     }
    257     return false;
    258   }
    259 
    260   return JSObject::deleteProperty(exec, propertyName);
    261 }
    262 
    263 bool ArrayInstance::deleteProperty(ExecState *exec, unsigned index)
    264 {
    265   if (index > MAX_ARRAY_INDEX)
    266     return deleteProperty(exec, Identifier::from(index));
    267 
    268   if (index >= length)
    269     return true;
    270   if (index < storageLength) {
    271     storage[index] = 0;
    272     return true;
    273   }
    274   OverflowMap* overflow = overflowMap(storage);
    275   if (!overflow)
    276     return false;
    277   OverflowMap::iterator it = overflow->find(index);
    278   if (it == overflow->end())
    279     return false;
    280   overflow->remove(it);
    281   return true;
    282335}
    283336
    284337void ArrayInstance::getPropertyNames(ExecState* exec, PropertyNameArray& propertyNames)
    285338{
    286   // avoid fetching this every time through the loop
    287   JSValue* undefined = jsUndefined();
     339    // FIXME: Filling PropertyNameArray with an identifier for every integer
     340    // is incredibly inefficient for large arrays. We need a different approach.
     341
     342    ArrayStorage* storage = m_storage;
     343
     344    unsigned usedVectorLength = min(m_length, m_vectorLength);
     345    for (unsigned i = 0; i < usedVectorLength; ++i) {
     346        if (storage->m_vector[i])
     347            propertyNames.add(Identifier::from(i));
     348    }
     349
     350    if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
     351        SparseArrayValueMap::iterator end = map->end();
     352        for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
     353            propertyNames.add(Identifier::from(it->first));
     354    }
     355 
     356    JSObject::getPropertyNames(exec, propertyNames);
     357}
     358
     359void ArrayInstance::increaseVectorLength(unsigned newLength)
     360{
     361    ArrayStorage* storage = m_storage;
     362
     363    unsigned vectorLength = m_vectorLength;
     364    ASSERT(newLength > vectorLength);
     365    unsigned newVectorLength = increasedVectorLength(newLength);
     366
     367    storage = static_cast<ArrayStorage*>(fastRealloc(storage, storageSize(newVectorLength)));
     368    m_vectorLength = newVectorLength;
     369
     370    for (unsigned i = vectorLength; i < newVectorLength; ++i)
     371        storage->m_vector[i] = 0;
     372
     373    m_storage = storage;
     374}
     375
     376void ArrayInstance::setLength(unsigned newLength)
     377{
     378    ArrayStorage* storage = m_storage;
     379
     380    unsigned length = m_length;
     381
     382    if (newLength < length) {
     383        unsigned usedVectorLength = min(length, m_vectorLength);
     384        for (unsigned i = newLength; i < usedVectorLength; ++i) {
     385            JSValue*& valueSlot = storage->m_vector[i];
     386            bool hadValue = valueSlot;
     387            valueSlot = 0;
     388            storage->m_numValuesInVector -= hadValue;
     389        }
     390
     391        if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
     392            SparseArrayValueMap copy = *map;
     393            SparseArrayValueMap::iterator end = copy.end();
     394            for (SparseArrayValueMap::iterator it = copy.begin(); it != end; ++it) {
     395                if (it->first >= newLength)
     396                    map->remove(it->first);
     397            }
     398            if (map->isEmpty()) {
     399                delete map;
     400                storage->m_sparseValueMap = 0;
     401            }
     402        }
     403    }
    288404 
    289   for (unsigned i = 0; i < storageLength; ++i) {
    290     JSValue* value = storage[i];
    291     if (value && value != undefined)
    292       propertyNames.add(Identifier::from(i));
    293   }
    294 
    295   OverflowMap* overflow = overflowMap(storage);
    296   if (overflow) {
    297     OverflowMap::iterator end = overflow->end();
    298     for (OverflowMap::iterator it = overflow->begin(); it != end; ++it) {
    299       JSValue* value = it->second;
    300       if (value && value != undefined)
    301         propertyNames.add(Identifier::from(it->first));
    302     }
    303   }
    304  
    305   JSObject::getPropertyNames(exec, propertyNames);
    306 }
    307 
    308 void ArrayInstance::resizeStorage(unsigned newLength)
    309 {
    310     if (newLength < storageLength) {
    311       memset(storage + newLength, 0, sizeof(JSValue *) * (storageLength - newLength));
    312     }
    313     size_t cap = capacity();
    314     if (newLength > cap) {
    315       unsigned newCapacity;
    316       if (newLength > sparseArrayCutoff) {
    317         newCapacity = newLength;
    318       } else {
    319         newCapacity = (newLength * 3 + 1) / 2;
    320         if (newCapacity > sparseArrayCutoff) {
    321           newCapacity = sparseArrayCutoff;
    322         }
    323       }
    324      
    325       reallocateStorage(storage, newCapacity);
    326       memset(storage + cap, 0, sizeof(JSValue*) * (newCapacity - cap));
    327     }
    328     storageLength = newLength;
    329 }
    330 
    331 void ArrayInstance::setLength(unsigned newLength)
    332 {
    333   if (newLength <= storageLength)
    334     resizeStorage(newLength);
    335 
    336   if (newLength < length) {
    337     if (OverflowMap* overflow = overflowMap(storage)) {
    338       OverflowMap copy = *overflow;
    339       OverflowMap::iterator end = copy.end();
    340       for (OverflowMap::iterator it = copy.begin(); it != end; ++it) {
    341         if (it->first >= newLength)
    342           overflow->remove(it->first);
    343       }
    344     }
    345   }
    346  
    347   length = newLength;
     405    m_length = newLength;
    348406}
    349407
    350408void ArrayInstance::mark()
    351409{
    352   JSObject::mark();
    353   unsigned l = storageLength;
    354   for (unsigned i = 0; i < l; ++i) {
    355     JSValue* imp = storage[i];
    356     if (imp && !imp->marked())
    357       imp->mark();
    358   }
    359   if (OverflowMap* overflow = overflowMap(storage)) {
    360     OverflowMap::iterator end = overflow->end();
    361     for (OverflowMap::iterator it = overflow->begin(); it != end; ++it) {
    362       JSValue* value = it->second;
    363       if (value && !value->marked())
    364         value->mark();
    365     }
    366   }
     410    JSObject::mark();
     411
     412    ArrayStorage* storage = m_storage;
     413
     414    unsigned usedVectorLength = min(m_length, m_vectorLength);
     415    for (unsigned i = 0; i < usedVectorLength; ++i) {
     416        JSValue* value = storage->m_vector[i];
     417        if (value && !value->marked())
     418            value->mark();
     419    }
     420
     421    if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
     422        SparseArrayValueMap copy = *map;
     423        SparseArrayValueMap::iterator end = copy.end();
     424        for (SparseArrayValueMap::iterator it = copy.begin(); it != end; ++it) {
     425            JSValue* value = it->second;
     426            if (!value->marked())
     427                value->mark();
     428        }
     429    }
    367430}
    368431
    369432static ExecState* execForCompareByStringForQSort = 0;
    370433
    371 static int compareByStringForQSort(const void *a, const void *b)
    372 {
    373     ExecState *exec = execForCompareByStringForQSort;
    374     JSValue *va = *(JSValue **)a;
    375     JSValue *vb = *(JSValue **)b;
     434static int compareByStringForQSort(const void* a, const void* b)
     435{
     436    ExecState* exec = execForCompareByStringForQSort;
     437
     438    JSValue* va = *static_cast<JSValue* const*>(a);
     439    JSValue* vb = *static_cast<JSValue* const*>(b);
    376440    ASSERT(!va->isUndefined());
    377441    ASSERT(!vb->isUndefined());
     442
    378443    return compare(va->toString(exec), vb->toString(exec));
    379444}
    … …  
    381446void ArrayInstance::sort(ExecState* exec)
    382447{
    383     size_t lengthNotIncludingUndefined = compactForSorting();
    384      
     448    unsigned lengthNotIncludingUndefined = compactForSorting();
     449
    385450    ExecState* oldExec = execForCompareByStringForQSort;
    386451    execForCompareByStringForQSort = exec;
     452
    387453#if HAVE(MERGESORT)
    388     // mergesort usually does fewer compares, so it is actually faster than qsort for JS sorts.
    389     // however, becuase it requires extra copies of the storage buffer, don't use it for very
    390     // large arrays
    391     // FIXME: for sorting by string value, the fastest thing would actually be to convert all the
    392     // values to string once up front, and then use a radix sort. That would be O(N) rather than
    393     // O(N log N).
    394     if (lengthNotIncludingUndefined < sparseArrayCutoff) {
    395         JSValue** storageCopy = allocateStorage(capacity());
    396         memcpy(storageCopy, storage, capacity() * sizeof(JSValue*));
    397         mergesort(storageCopy, lengthNotIncludingUndefined, sizeof(JSValue *), compareByStringForQSort);
    398         freeStorage(storage);
    399         storage = storageCopy;
     454    // Because mergesort usually does fewer compares, it is faster than qsort here.
     455    // However, because it requires extra copies of the storage buffer, don't use it for very
     456    // large arrays.
     457
     458    // FIXME: Since we sort by string value, a fast algorithm might be to convert all the
     459    // values to string once up front, and then use a radix sort. That would be O(N) rather
     460    // than O(N log N).
     461
     462    if (lengthNotIncludingUndefined < mergeSortCutoff) {
     463        // During the sort, we could do a garbage collect, and it's important to still
     464        // have references to every object in the array for ArrayInstance::mark.
     465        // The mergesort algorithm does not guarantee this, so we sort a copy rather
     466        // than the original.
     467        size_t size = storageSize(m_vectorLength);
     468        ArrayStorage* copy = static_cast<ArrayStorage*>(fastMalloc(size));
     469        memcpy(copy, m_storage, size);
     470        mergesort(copy->m_vector, lengthNotIncludingUndefined, sizeof(JSValue*), compareByStringForQSort);
     471        fastFree(m_storage);
     472        m_storage = copy;
    400473        execForCompareByStringForQSort = oldExec;
    401474        return;
    … …  
    403476#endif
    404477
    405     qsort(storage, lengthNotIncludingUndefined, sizeof(JSValue*), compareByStringForQSort);
     478    qsort(m_storage->m_vector, lengthNotIncludingUndefined, sizeof(JSValue*), compareByStringForQSort);
    406479    execForCompareByStringForQSort = oldExec;
    407480}
    … …  
    413486        , globalObject(e->dynamicInterpreter()->globalObject())
    414487    {
    415         arguments.append(jsUndefined());
    416         arguments.append(jsUndefined());
    417488    }
    418489
    … …  
    425496static CompareWithCompareFunctionArguments* compareWithCompareFunctionArguments = 0;
    426497
    427 static int compareWithCompareFunctionForQSort(const void *a, const void *b)
     498static int compareWithCompareFunctionForQSort(const void* a, const void* b)
    428499{
    429500    CompareWithCompareFunctionArguments *args = compareWithCompareFunctionArguments;
    430501
    431     JSValue *va = *(JSValue **)a;
    432     JSValue *vb = *(JSValue **)b;
     502    JSValue* va = *static_cast<JSValue* const*>(a);
     503    JSValue* vb = *static_cast<JSValue* const*>(b);
    433504    ASSERT(!va->isUndefined());
    434505    ASSERT(!vb->isUndefined());
    … …  
    449520    CompareWithCompareFunctionArguments args(exec, compareFunction);
    450521    compareWithCompareFunctionArguments = &args;
     522
    451523#if HAVE(MERGESORT)
    452     // mergesort usually does fewer compares, so it is actually faster than qsort for JS sorts.
    453     // however, becuase it requires extra copies of the storage buffer, don't use it for very
    454     // large arrays
    455     // FIXME: a tree sort using a perfectly balanced tree (e.g. an AVL tree) could do an even
    456     // better job of minimizing compares
    457     if (lengthNotIncludingUndefined < sparseArrayCutoff) {
    458         JSValue** storageCopy = allocateStorage(capacity());
    459         memcpy(storageCopy, storage, capacity() * sizeof(JSValue*));
    460         mergesort(storageCopy, lengthNotIncludingUndefined, sizeof(JSValue *), compareWithCompareFunctionForQSort);
    461         freeStorage(storage);
    462         storage = storageCopy;
     524    // Because mergesort usually does fewer compares, it is faster than qsort here.
     525    // However, because it requires extra copies of the storage buffer, don't use it for very
     526    // large arrays.
     527
     528    // FIXME: A tree sort using a perfectly balanced tree (e.g. an AVL tree) could do an even
     529    // better job of minimizing compares.
     530
     531    if (lengthNotIncludingUndefined < mergeSortCutoff) {
     532        // During the sort, we could do a garbage collect, and it's important to still
     533        // have references to every object in the array for ArrayInstance::mark.
     534        // The mergesort algorithm does not guarantee this, so we sort a copy rather
     535        // than the original.
     536        size_t size = storageSize(m_vectorLength);
     537        ArrayStorage* copy = static_cast<ArrayStorage*>(fastMalloc(size));
     538        memcpy(copy, m_storage, size);
     539        mergesort(copy->m_vector, lengthNotIncludingUndefined, sizeof(JSValue*), compareWithCompareFunctionForQSort);
     540        fastFree(m_storage);
     541        m_storage = copy;
    463542        compareWithCompareFunctionArguments = oldArgs;
    464543        return;
    465544    }
    466545#endif
    467     qsort(storage, lengthNotIncludingUndefined, sizeof(JSValue*), compareWithCompareFunctionForQSort);
     546
     547    qsort(m_storage->m_vector, lengthNotIncludingUndefined, sizeof(JSValue*), compareWithCompareFunctionForQSort);
    468548    compareWithCompareFunctionArguments = oldArgs;
    469549}
    … …  
    471551unsigned ArrayInstance::compactForSorting()
    472552{
    473     JSValue *undefined = jsUndefined();
    474 
    475     unsigned o = 0;
    476    
    477     for (unsigned i = 0; i != storageLength; ++i) {
    478         JSValue *v = storage[i];
    479         if (v && v != undefined) {
    480             if (o != i)
    481                 storage[o] = v;
    482             o++;
    483         }
    484     }
    485    
    486     unsigned newLength = o;
    487 
    488     if (OverflowMap* overflow = overflowMap(storage)) {
    489         OverflowMap::iterator end = overflow->end();
    490         for (OverflowMap::iterator it = overflow->begin(); it != end; ++it)
    491             newLength += it->second != undefined;
    492    
    493         if (newLength > storageLength)
    494             resizeStorage(newLength);
    495    
    496         for (OverflowMap::iterator it = overflow->begin(); it != end; ++it) {
    497             JSValue* v = it->second;
    498             if (v != undefined) {
    499                 storage[o] = v;
    500                 o++;
    501             }
    502         }
    503         delete overflow;
    504         storage[-2] = 0;
    505     }
    506    
    507     if (newLength != storageLength)
    508         memset(storage + o, 0, sizeof(JSValue *) * (storageLength - o));
    509    
    510     return o;
    511 }
    512 
    513 // ------------------------------ ArrayPrototype ----------------------------
    514 
    515 const ClassInfo ArrayPrototype::info = {"Array", &ArrayInstance::info, &arrayTable, 0};
    516 
    517 /* Source for array_object.lut.h
    518 @begin arrayTable 16
    519   toString       ArrayProtoFunc::ToString       DontEnum|Function 0
    520   toLocaleString ArrayProtoFunc::ToLocaleString DontEnum|Function 0
    521   concat         ArrayProtoFunc::Concat         DontEnum|Function 1
    522   join           ArrayProtoFunc::Join           DontEnum|Function 1
    523   pop            ArrayProtoFunc::Pop            DontEnum|Function 0
    524   push           ArrayProtoFunc::Push           DontEnum|Function 1
    525   reverse        ArrayProtoFunc::Reverse        DontEnum|Function 0
    526   shift          ArrayProtoFunc::Shift          DontEnum|Function 0
    527   slice          ArrayProtoFunc::Slice          DontEnum|Function 2
    528   sort           ArrayProtoFunc::Sort           DontEnum|Function 1
    529   splice         ArrayProtoFunc::Splice         DontEnum|Function 2
    530   unshift        ArrayProtoFunc::UnShift        DontEnum|Function 1
    531   every          ArrayProtoFunc::Every          DontEnum|Function 1
    532   forEach        ArrayProtoFunc::ForEach        DontEnum|Function 1
    533   some           ArrayProtoFunc::Some           DontEnum|Function 1
    534   indexOf        ArrayProtoFunc::IndexOf        DontEnum|Function 1
    535   lastIndexOf    ArrayProtoFunc::LastIndexOf    DontEnum|Function 1
    536   filter         ArrayProtoFunc::Filter         DontEnum|Function 1
    537   map            ArrayProtoFunc::Map            DontEnum|Function 1
    538 @end
    539 */
    540 
    541 // ECMA 15.4.4
    542 ArrayPrototype::ArrayPrototype(ExecState*, ObjectPrototype* objProto)
    543   : ArrayInstance(objProto, 0)
    544 {
    545 }
    546 
    547 bool ArrayPrototype::getOwnPropertySlot(ExecState* exec, const Identifier& propertyName, PropertySlot& slot)
    548 {
    549   return getStaticFunctionSlot<ArrayProtoFunc, ArrayInstance>(exec, &arrayTable, this, propertyName, slot);
    550 }
    551 
    552 // ------------------------------ ArrayProtoFunc ----------------------------
    553 
    554 ArrayProtoFunc::ArrayProtoFunc(ExecState* exec, int i, int len, const Identifier& name)
    555   : InternalFunctionImp(static_cast<FunctionPrototype*>
    556                         (exec->lexicalInterpreter()->builtinFunctionPrototype()), name)
    557   , id(i)
    558 {
    559   put(exec, exec->propertyNames().length, jsNumber(len), DontDelete | ReadOnly | DontEnum);
    560 }
    561 
    562 static JSValue *getProperty(ExecState *exec, JSObject *obj, unsigned index)
    563 {
    564     PropertySlot slot;
    565     if (!obj->getPropertySlot(exec, index, slot))
    566         return NULL;
    567     return slot.getValue(exec, obj, index);
    568 }
    569 
    570 // ECMA 15.4.4
    571 JSValue* ArrayProtoFunc::callAsFunction(ExecState* exec, JSObject* thisObj, const List& args)
    572 {
    573   unsigned length = thisObj->get(exec, exec->propertyNames().length)->toUInt32(exec);
    574 
    575   JSValue *result = 0; // work around gcc 4.0 bug in uninitialized variable warning
    576  
    577   switch (id) {
    578   case ToLocaleString:
    579   case ToString:
    580 
    581     if (!thisObj->inherits(&ArrayInstance::info))
    582       return throwError(exec, TypeError);
    583 
    584     // fall through
    585   case Join: {
    586     static HashSet<JSObject*> visitedElems;
    587     static const UString* empty = new UString("");
    588     static const UString* comma = new UString(",");
    589     bool alreadyVisited = !visitedElems.add(thisObj).second;
    590     if (alreadyVisited)
    591         return jsString(*empty);
    592     UString separator = *comma;
    593     UString str = *empty;
    594 
    595     if (id == Join && !args[0]->isUndefined())
    596         separator = args[0]->toString(exec);
    597     for (unsigned int k = 0; k < length; k++) {
    598         if (k >= 1)
    599             str += separator;
    600         if (str.isNull()) {
    601             JSObject *error = Error::create(exec, GeneralError, "Out of memory");
    602             exec->setException(error);
     553    ArrayStorage* storage = m_storage;
     554
     555    unsigned usedVectorLength = min(m_length, m_vectorLength);
     556
     557    unsigned numDefined = 0;
     558    unsigned numUndefined = 0;
     559
     560    for (; numDefined < usedVectorLength; ++numDefined) {
     561        JSValue* v = storage->m_vector[numDefined];
     562        if (!v || v->isUndefined())
    603563            break;
    604         }
    605 
    606         JSValue* element = thisObj->get(exec, k);
    607         if (element->isUndefinedOrNull())
    608             continue;
    609 
    610         bool fallback = false;
    611         if (id == ToLocaleString) {
    612             JSObject* o = element->toObject(exec);
    613             JSValue* conversionFunction = o->get(exec, exec->propertyNames().toLocaleString);
    614             if (conversionFunction->isObject() && static_cast<JSObject*>(conversionFunction)->implementsCall())
    615                 str += static_cast<JSObject*>(conversionFunction)->call(exec, o, List())->toString(exec);
     564    }
     565    for (unsigned i = numDefined; i < usedVectorLength; ++i) {
     566        if (JSValue* v = storage->m_vector[i]) {
     567            if (v->isUndefined())
     568                ++numUndefined;
    616569            else
    617                 // try toString() fallback
    618                 fallback = true;
    619         }
    620 
    621         if (id == ToString || id == Join || fallback)
    622             str += element->toString(exec);
    623 
    624         if (str.isNull()) {
    625             JSObject *error = Error::create(exec, GeneralError, "Out of memory");
    626             exec->setException(error);
    627         }
    628 
    629         if (exec->hadException())
    630             break;
    631     }
    632     visitedElems.remove(thisObj);
    633     result = jsString(str);
    634     break;
    635   }
    636   case Concat: {
    637     JSObject *arr = static_cast<JSObject *>(exec->lexicalInterpreter()->builtinArray()->construct(exec,List::empty()));
    638     int n = 0;
    639     JSValue *curArg = thisObj;
    640     JSObject *curObj = static_cast<JSObject *>(thisObj);
    641     ListIterator it = args.begin();
    642     for (;;) {
    643       if (curArg->isObject() &&
    644           curObj->inherits(&ArrayInstance::info)) {
    645         unsigned int k = 0;
    646         // Older versions tried to optimize out getting the length of thisObj
    647         // by checking for n != 0, but that doesn't work if thisObj is an empty array.
    648         length = curObj->get(exec, exec->propertyNames().length)->toUInt32(exec);
    649         while (k < length) {
    650           if (JSValue *v = getProperty(exec, curObj, k))
    651             arr->put(exec, n, v);
    652           n++;
    653           k++;
    654         }
    655       } else {
    656         arr->put(exec, n, curArg);
    657         n++;
    658       }
    659       if (it == args.end())
    660         break;
    661       curArg = *it;
    662       curObj = static_cast<JSObject *>(it++); // may be 0
    663     }
    664     arr->put(exec, exec->propertyNames().length, jsNumber(n), DontEnum | DontDelete);
    665 
    666     result = arr;
    667     break;
    668   }
    669   case Pop:{
    670     if (length == 0) {
    671       thisObj->put(exec, exec->propertyNames().length, jsNumber(length), DontEnum | DontDelete);
    672       result = jsUndefined();
    673     } else {
    674       result = thisObj->get(exec, length - 1);
    675       thisObj->put(exec, exec->propertyNames().length, jsNumber(length - 1), DontEnum | DontDelete);
    676     }
    677     break;
    678   }
    679   case Push: {
    680     for (int n = 0; n < args.size(); n++)
    681       thisObj->put(exec, length + n, args[n]);
    682     length += args.size();
    683     thisObj->put(exec, exec->propertyNames().length, jsNumber(length), DontEnum | DontDelete);
    684     result = jsNumber(length);
    685     break;
    686   }
    687   case Reverse: {
    688 
    689     unsigned int middle = length / 2;
    690 
    691     for (unsigned int k = 0; k < middle; k++) {
    692       unsigned lk1 = length - k - 1;
    693       JSValue *obj2 = getProperty(exec, thisObj, lk1);
    694       JSValue *obj = getProperty(exec, thisObj, k);
    695 
    696       if (obj2)
    697         thisObj->put(exec, k, obj2);
    698       else
    699         thisObj->deleteProperty(exec, k);
    700 
    701       if (obj)
    702         thisObj->put(exec, lk1, obj);
    703       else
    704         thisObj->deleteProperty(exec, lk1);
    705     }
    706     result = thisObj;
    707     break;
    708   }
    709   case Shift: {
    710     if (length == 0) {
    711       thisObj->put(exec, exec->propertyNames().length, jsNumber(length), DontEnum | DontDelete);
    712       result = jsUndefined();
    713     } else {
    714       result = thisObj->get(exec, 0);
    715       for(unsigned int k = 1; k < length; k++) {
    716         if (JSValue *obj = getProperty(exec, thisObj, k))
    717           thisObj->put(exec, k-1, obj);
    718         else
    719           thisObj->deleteProperty(exec, k-1);
    720       }
    721       thisObj->deleteProperty(exec, length - 1);
    722       thisObj->put(exec, exec->propertyNames().length, jsNumber(length - 1), DontEnum | DontDelete);
    723     }
    724     break;
    725   }
    726   case Slice: {
    727     // http://developer.netscape.com/docs/manuals/js/client/jsref/array.htm#1193713 or 15.4.4.10
    728 
    729     // We return a new array
    730     JSObject *resObj = static_cast<JSObject *>(exec->lexicalInterpreter()->builtinArray()->construct(exec,List::empty()));
    731     result = resObj;
    732     double begin = 0;
    733     if (!args[0]->isUndefined()) {
    734         begin = args[0]->toInteger(exec);
    735         if (begin >= 0) { // false for NaN
    736             if (begin > length)
    737                 begin = length;
    738         } else {
    739             begin += length;
    740             if (!(begin >= 0)) // true for NaN
    741                 begin = 0;
    742         }
    743     }
    744     double end = length;
    745     if (!args[1]->isUndefined()) {
    746       end = args[1]->toInteger(exec);
    747       if (end < 0) { // false for NaN
    748         end += length;
    749         if (end < 0)
    750           end = 0;
    751       } else {
    752         if (!(end <= length)) // true for NaN
    753           end = length;
    754       }
    755     }
    756 
    757     //printf( "Slicing from %d to %d \n", begin, end );
    758     int n = 0;
    759     int b = static_cast<int>(begin);
    760     int e = static_cast<int>(end);
    761     for(int k = b; k < e; k++, n++) {
    762       if (JSValue *v = getProperty(exec, thisObj, k))
    763         resObj->put(exec, n, v);
    764     }
    765     resObj->put(exec, exec->propertyNames().length, jsNumber(n), DontEnum | DontDelete);
    766     break;
    767   }
    768   case Sort:{
    769 #if 0
    770     printf("KJS Array::Sort length=%d\n", length);
    771     for ( unsigned int i = 0 ; i<length ; ++i )
    772       printf("KJS Array::Sort: %d: %s\n", i, thisObj->get(exec, i)->toString(exec).ascii() );
    773 #endif
    774     JSObject *sortFunction = NULL;
    775     if (!args[0]->isUndefined())
    776       {
    777         sortFunction = args[0]->toObject(exec);
    778         if (!sortFunction->implementsCall())
    779           sortFunction = NULL;
    780       }
    781    
    782     if (thisObj->classInfo() == &ArrayInstance::info) {
    783       if (sortFunction)
    784         ((ArrayInstance *)thisObj)->sort(exec, sortFunction);
    785       else
    786         ((ArrayInstance *)thisObj)->sort(exec);
    787       result = thisObj;
    788       break;
    789     }
    790 
    791     if (length == 0) {
    792       thisObj->put(exec, exec->propertyNames().length, jsNumber(0), DontEnum | DontDelete);
    793       result = thisObj;
    794       break;
    795     }
    796 
    797     // "Min" sort. Not the fastest, but definitely less code than heapsort
    798     // or quicksort, and much less swapping than bubblesort/insertionsort.
    799     for ( unsigned int i = 0 ; i<length-1 ; ++i )
    800       {
    801         JSValue *iObj = thisObj->get(exec,i);
    802         unsigned int themin = i;
    803         JSValue *minObj = iObj;
    804         for ( unsigned int j = i+1 ; j<length ; ++j )
    805           {
    806             JSValue *jObj = thisObj->get(exec,j);
    807             double cmp;
    808             if (jObj->isUndefined()) {
    809               cmp = 1; // don't check minObj because there's no need to differentiate == (0) from > (1)
    810             } else if (minObj->isUndefined()) {
    811               cmp = -1;
    812             } else if (sortFunction) {
    813                 List l;
    814                 l.append(jObj);
    815                 l.append(minObj);
    816                 cmp = sortFunction->call(exec, exec->dynamicInterpreter()->globalObject(), l)->toNumber(exec);
    817             } else {
    818               cmp = (jObj->toString(exec) < minObj->toString(exec)) ? -1 : 1;
    819             }
    820             if ( cmp < 0 )
    821               {
    822                 themin = j;
    823                 minObj = jObj;
    824               }
    825           }
    826         // Swap themin and i
    827         if ( themin > i )
    828           {
    829             //printf("KJS Array::Sort: swapping %d and %d\n", i, themin );
    830             thisObj->put( exec, i, minObj );
    831             thisObj->put( exec, themin, iObj );
    832           }
    833       }
    834 #if 0
    835     printf("KJS Array::Sort -- Resulting array:\n");
    836     for ( unsigned int i = 0 ; i<length ; ++i )
    837       printf("KJS Array::Sort: %d: %s\n", i, thisObj->get(exec, i)->toString(exec).ascii() );
    838 #endif
    839     result = thisObj;
    840     break;
    841   }
    842   case Splice: {
    843     // 15.4.4.12 - oh boy this is huge
    844     JSObject *resObj = static_cast<JSObject *>(exec->lexicalInterpreter()->builtinArray()->construct(exec,List::empty()));
    845     result = resObj;
    846     int begin = args[0]->toUInt32(exec);
    847     if ( begin < 0 )
    848       begin = maxInt( begin + length, 0 );
    849     else
    850       begin = minInt( begin, length );
    851     unsigned int deleteCount = minInt( maxInt( args[1]->toUInt32(exec), 0 ), length - begin );
    852 
    853     //printf( "Splicing from %d, deleteCount=%d \n", begin, deleteCount );
    854     for(unsigned int k = 0; k < deleteCount; k++) {
    855       if (JSValue *v = getProperty(exec, thisObj, k+begin))
    856         resObj->put(exec, k, v);
    857     }
    858     resObj->put(exec, exec->propertyNames().length, jsNumber(deleteCount), DontEnum | DontDelete);
    859 
    860     unsigned int additionalArgs = maxInt( args.size() - 2, 0 );
    861     if ( additionalArgs != deleteCount )
    862     {
    863       if ( additionalArgs < deleteCount )
    864       {
    865         for ( unsigned int k = begin; k < length - deleteCount; ++k )
    866         {
    867           if (JSValue *v = getProperty(exec, thisObj, k+deleteCount))
    868             thisObj->put(exec, k+additionalArgs, v);
    869           else
    870             thisObj->deleteProperty(exec, k+additionalArgs);
    871         }
    872         for ( unsigned int k = length ; k > length - deleteCount + additionalArgs; --k )
    873           thisObj->deleteProperty(exec, k-1);
    874       }
    875       else
    876       {
    877         for ( unsigned int k = length - deleteCount; (int)k > begin; --k )
    878         {
    879           if (JSValue *obj = getProperty(exec, thisObj, k + deleteCount - 1))
    880             thisObj->put(exec, k + additionalArgs - 1, obj);
    881           else
    882             thisObj->deleteProperty(exec, k+additionalArgs-1);
    883         }
    884       }
    885     }
    886     for ( unsigned int k = 0; k < additionalArgs; ++k )
    887     {
    888       thisObj->put(exec, k+begin, args[k+2]);
    889     }
    890     thisObj->put(exec, exec->propertyNames().length, jsNumber(length - deleteCount + additionalArgs), DontEnum | DontDelete);
    891     break;
    892   }
    893   case UnShift: { // 15.4.4.13
    894     unsigned int nrArgs = args.size();
    895     for ( unsigned int k = length; k > 0; --k )
    896     {
    897       if (JSValue *v = getProperty(exec, thisObj, k - 1))
    898         thisObj->put(exec, k+nrArgs-1, v);
    899       else
    900         thisObj->deleteProperty(exec, k+nrArgs-1);
    901     }
    902     for ( unsigned int k = 0; k < nrArgs; ++k )
    903       thisObj->put(exec, k, args[k]);
    904     result = jsNumber(length + nrArgs);
    905     thisObj->put(exec, exec->propertyNames().length, result, DontEnum | DontDelete);
    906     break;
    907   }
    908   case Filter:
    909   case Map: {
    910     JSObject *eachFunction = args[0]->toObject(exec);
    911    
    912     if (!eachFunction->implementsCall())
    913       return throwError(exec, TypeError);
    914    
    915     JSObject *applyThis = args[1]->isUndefinedOrNull() ? exec->dynamicInterpreter()->globalObject() :  args[1]->toObject(exec);
    916     JSObject *resultArray;
    917    
    918     if (id == Filter)
    919       resultArray = static_cast<JSObject *>(exec->lexicalInterpreter()->builtinArray()->construct(exec, List::empty()));
    920     else {
    921       List args;
    922       args.append(jsNumber(length));
    923       resultArray = static_cast<JSObject *>(exec->lexicalInterpreter()->builtinArray()->construct(exec, args));
    924     }
    925    
    926     unsigned filterIndex = 0;
    927     for (unsigned k = 0; k < length && !exec->hadException(); ++k) {
    928       PropertySlot slot;
    929 
    930       if (!thisObj->getPropertySlot(exec, k, slot))
    931          continue;
    932        
    933       JSValue *v = slot.getValue(exec, thisObj, k);
    934      
    935       List eachArguments;
    936      
    937       eachArguments.append(v);
    938       eachArguments.append(jsNumber(k));
    939       eachArguments.append(thisObj);
    940      
    941       JSValue *result = eachFunction->call(exec, applyThis, eachArguments);
    942      
    943       if (id == Map)
    944         resultArray->put(exec, k, result);
    945       else if (result->toBoolean(exec))
    946         resultArray->put(exec, filterIndex++, v);
    947     }
    948    
    949     return resultArray;
    950   }
    951   case Every:
    952   case ForEach:
    953   case Some: {
    954     //Documentation for these three is available at:
    955     //http://developer-test.mozilla.org/en/docs/Core_JavaScript_1.5_Reference:Objects:Array:every
    956     //http://developer-test.mozilla.org/en/docs/Core_JavaScript_1.5_Reference:Objects:Array:forEach
    957     //http://developer-test.mozilla.org/en/docs/Core_JavaScript_1.5_Reference:Objects:Array:some
    958    
    959     JSObject *eachFunction = args[0]->toObject(exec);
    960    
    961     if (!eachFunction->implementsCall())
    962       return throwError(exec, TypeError);
    963    
    964     JSObject *applyThis = args[1]->isUndefinedOrNull() ? exec->dynamicInterpreter()->globalObject() :  args[1]->toObject(exec);
    965    
    966     if (id == Some || id == Every)
    967       result = jsBoolean(id == Every);
    968     else
    969       result = jsUndefined();
    970    
    971     for (unsigned k = 0; k < length && !exec->hadException(); ++k) {
    972       PropertySlot slot;
    973        
    974       if (!thisObj->getPropertySlot(exec, k, slot))
    975         continue;
    976      
    977       List eachArguments;
    978      
    979       eachArguments.append(slot.getValue(exec, thisObj, k));
    980       eachArguments.append(jsNumber(k));
    981       eachArguments.append(thisObj);
    982      
    983       bool predicateResult = eachFunction->call(exec, applyThis, eachArguments)->toBoolean(exec);
    984      
    985       if (id == Every && !predicateResult) {
    986         result = jsBoolean(false);
    987         break;
    988       }
    989       if (id == Some && predicateResult) {
    990         result = jsBoolean(true);
    991         break;
    992       }
    993     }
    994     break;
    995   }
    996 
    997   case IndexOf: {
    998     // JavaScript 1.5 Extension by Mozilla
    999     // Documentation: http://developer.mozilla.org/en/docs/Core_JavaScript_1.5_Reference:Global_Objects:Array:indexOf
    1000 
    1001     unsigned index = 0;
    1002     double d = args[1]->toInteger(exec);
    1003     if (d < 0)
    1004         d += length;
    1005     if (d > 0) {
    1006         if (d > length)
    1007             index = length;
    1008         else
    1009             index = static_cast<unsigned>(d);
    1010     }
    1011 
    1012     JSValue* searchElement = args[0];
    1013     for (; index < length; ++index) {
    1014         JSValue* e = getProperty(exec, thisObj, index);
    1015         if (!e)
    1016             continue;
    1017         if (strictEqual(exec, searchElement, e))
    1018             return jsNumber(index);
    1019     }
    1020 
    1021     return jsNumber(-1);
    1022   }
    1023   case LastIndexOf: {
    1024        // JavaScript 1.6 Extension by Mozilla
    1025       // Documentation: http://developer.mozilla.org/en/docs/Core_JavaScript_1.5_Reference:Global_Objects:Array:lastIndexOf
    1026 
    1027     int index = length - 1;
    1028     double d = args[1]->toInteger(exec);
    1029 
    1030     if (d < 0) {
    1031         d += length;
    1032         if (d < 0)
    1033             return jsNumber(-1);
    1034     }
    1035     if (d < length)
    1036         index = static_cast<int>(d);
    1037          
    1038     JSValue* searchElement = args[0];
    1039     for (; index >= 0; --index) {
    1040         JSValue* e = getProperty(exec, thisObj, index);
    1041         if (!e)
    1042             continue;
    1043         if (strictEqual(exec, searchElement, e))
    1044             return jsNumber(index);
    1045     }
    1046          
    1047     return jsNumber(-1);
    1048 }
    1049   default:
    1050     ASSERT(0);
    1051     result = 0;
    1052     break;
    1053   }
    1054   return result;
    1055 }
    1056 
    1057 // ------------------------------ ArrayObjectImp -------------------------------
    1058 
    1059 ArrayObjectImp::ArrayObjectImp(ExecState *exec,
    1060                                FunctionPrototype *funcProto,
    1061                                ArrayPrototype *arrayProto)
    1062   : InternalFunctionImp(funcProto)
    1063 {
    1064   // ECMA 15.4.3.1 Array.prototype
    1065   put(exec, exec->propertyNames().prototype, arrayProto, DontEnum|DontDelete|ReadOnly);
    1066 
    1067   // no. of arguments for constructor
    1068   put(exec, exec->propertyNames().length, jsNumber(1), ReadOnly|DontDelete|DontEnum);
    1069 }
    1070 
    1071 bool ArrayObjectImp::implementsConstruct() const
    1072 {
    1073   return true;
    1074 }
    1075 
    1076 // ECMA 15.4.2
    1077 JSObject *ArrayObjectImp::construct(ExecState *exec, const List &args)
    1078 {
    1079   // a single numeric argument denotes the array size (!)
    1080   if (args.size() == 1 && args[0]->isNumber()) {
    1081     uint32_t n = args[0]->toUInt32(exec);
    1082     if (n != args[0]->toNumber(exec))
    1083       return throwError(exec, RangeError, "Array size is not a small enough positive integer.");
    1084     return new ArrayInstance(exec->lexicalInterpreter()->builtinArrayPrototype(), n);
    1085   }
    1086 
    1087   // otherwise the array is constructed with the arguments in it
    1088   return new ArrayInstance(exec->lexicalInterpreter()->builtinArrayPrototype(), args);
    1089 }
    1090 
    1091 // ECMA 15.6.1
    1092 JSValue *ArrayObjectImp::callAsFunction(ExecState *exec, JSObject *, const List &args)
    1093 {
    1094   // equivalent to 'new Array(....)'
    1095   return construct(exec,args);
    1096 }
    1097 
    1098 }
     570                storage->m_vector[numDefined++] = v;
     571        }
     572    }
     573
     574    unsigned newUsedVectorLength = numDefined + numUndefined;
     575
     576    if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
     577        newUsedVectorLength += map->size();
     578        if (newUsedVectorLength > m_vectorLength) {
     579            increaseVectorLength(newUsedVectorLength);
     580            storage = m_storage;
     581        }
     582
     583        SparseArrayValueMap::iterator end = map->end();
     584        for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
     585            storage->m_vector[numDefined++] = it->second;
     586
     587        delete map;
     588        storage->m_sparseValueMap = 0;
     589    }
     590
     591    for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
     592        storage->m_vector[i] = jsUndefined();
     593    for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
     594        storage->m_vector[i] = 0;
     595
     596    return numDefined;
     597}
     598
     599}

  • trunk/JavaScriptCore/kjs/array_instance.h

    r26850 r26881  
    11// -*- c-basic-offset: 2 -*-
    22/*
    3  *  This file is part of the KDE libraries
    43 *  Copyright (C) 1999-2000 Harri Porten ([email protected])
    54 *  Copyright (C) 2003, 2007 Apple Inc. All rights reserved.
    … …  
    2827namespace KJS {
    2928
     29  struct ArrayStorage;
     30
    3031  class ArrayInstance : public JSObject {
    3132  public:
    32     ArrayInstance(JSObject *proto, unsigned initialLength);
    33     ArrayInstance(JSObject *proto, const List &initialValues);
     33    ArrayInstance(JSObject* prototype, unsigned initialLength);
     34    ArrayInstance(JSObject* prototype, const List& initialValues);
    3435    ~ArrayInstance();
    3536
    36     virtual bool getOwnPropertySlot(ExecState *, const Identifier&, PropertySlot&);
    37     virtual bool getOwnPropertySlot(ExecState *, unsigned, PropertySlot&);
    38     virtual void put(ExecState *exec, const Identifier &propertyName, JSValue *value, int attr = None);
    39     virtual void put(ExecState *exec, unsigned propertyName, JSValue *value, int attr = None);
    40     virtual bool deleteProperty(ExecState *exec, const Identifier &propertyName);
    41     virtual bool deleteProperty(ExecState *exec, unsigned propertyName);
     37    virtual bool getOwnPropertySlot(ExecState*, const Identifier& propertyName, PropertySlot&);
     38    virtual bool getOwnPropertySlot(ExecState*, unsigned propertyName, PropertySlot&);
     39    virtual void put(ExecState*, const Identifier& propertyName, JSValue*, int attributes = None);
     40    virtual void put(ExecState*, unsigned propertyName, JSValue*, int attributes = None);
     41    virtual bool deleteProperty(ExecState *, const Identifier& propertyName);
     42    virtual bool deleteProperty(ExecState *, unsigned propertyName);
    4243    virtual void getPropertyNames(ExecState*, PropertyNameArray&);
    4344
    4445    virtual void mark();
    4546
    46     virtual const ClassInfo *classInfo() const { return &info; }
     47    virtual const ClassInfo* classInfo() const { return &info; }
    4748    static const ClassInfo info;
     49
     50    unsigned getLength() const { return m_length; }
     51    JSValue* getItem(unsigned) const;
     52
     53    void sort(ExecState*);
     54    void sort(ExecState*, JSObject* compareFunction);
     55
     56  private:
     57    static JSValue* lengthGetter(ExecState*, JSObject*, const Identifier&, const PropertySlot&);
     58    bool inlineGetOwnPropertySlot(ExecState*, unsigned propertyName, PropertySlot&);
     59
     60    void setLength(unsigned);
     61    void increaseVectorLength(unsigned newLength);
    4862   
    49     unsigned getLength() const { return length; }
    50     JSValue* getItem(unsigned) const;
    51    
    52     void sort(ExecState *exec);
    53     void sort(ExecState *exec, JSObject *compareFunction);
    54    
    55   private:
    56     static JSValue *lengthGetter(ExecState *, JSObject *, const Identifier&, const PropertySlot&);
     63    unsigned compactForSorting();   
    5764
    58     void setLength(unsigned newLength);
    59    
    60     unsigned compactForSorting();
    61    
    62     void resizeStorage(unsigned);
    63 
    64     // store capacity in extra space at the beginning of the storage array to save space
    65     size_t capacity() { return storage ? reinterpret_cast<size_t>(storage[-1]) : 0; }
    66 
    67     unsigned length;
    68     unsigned storageLength;
    69     JSValue **storage;
     65    unsigned m_length;
     66    unsigned m_vectorLength;
     67    ArrayStorage* m_storage;
    7068  };
    7169

  • trunk/JavaScriptCore/kjs/array_object.cpp

    r26862 r26881  
    11// -*- c-basic-offset: 2 -*-
    22/*
    3  *  This file is part of the KDE libraries
    43 *  Copyright (C) 1999-2000 Harri Porten ([email protected])
    54 *  Copyright (C) 2003, 2007 Apple Inc. All rights reserved.
    … …  
    2726#include "array_object.lut.h"
    2827
    29 #include "PropertyNameArray.h"
    3028#include "error_object.h"
    3129#include "lookup.h"
    … …  
    3533#include <wtf/HashSet.h>
    3634
    37 
    3835namespace KJS {
    39 
    40 typedef HashMap<unsigned, JSValue*> OverflowMap;
    41 
    42 static inline OverflowMap* overflowMap(JSValue** storage)
    43 {
    44     return storage ? reinterpret_cast<OverflowMap*>(storage[-2]) : 0;
    45 }
    46 
    47 // ------------------------------ ArrayInstance -----------------------------
    48 
    49 const unsigned sparseArrayCutoff = 10000;
    50 
    51 const ClassInfo ArrayInstance::info = {"Array", 0, 0, 0};
    52 
    53 static inline JSValue** allocateStorage(size_t capacity)
    54 {
    55   if (capacity == 0)
    56       return 0;
    57 
    58   // store capacity and overflow map in extra space before the beginning of the storage array to save space
    59   JSValue** storage = static_cast<JSValue**>(fastCalloc(capacity + 2, sizeof(JSValue *))) + 2;
    60   storage[-1] = reinterpret_cast<JSValue*>(capacity);
    61   return storage;
    62 }
    63 
    64 static inline void reallocateStorage(JSValue**& storage, size_t newCapacity)
    65 {
    66   if (!storage) {
    67     storage = allocateStorage(newCapacity);
    68     return;
    69   }
    70 
    71   // store capacity and overflow map in extra space before the beginning of the storage array to save space
    72   storage = static_cast<JSValue**>(fastRealloc(storage - 2, (newCapacity + 2) * sizeof (JSValue*))) + 2;
    73   storage[-1] = reinterpret_cast<JSValue*>(newCapacity);
    74 }
    75 
    76 static inline void freeStorage(JSValue** storage)
    77 {
    78     if (storage)
    79         fastFree(storage - 2);
    80 }
    81 
    82 ArrayInstance::ArrayInstance(JSObject *proto, unsigned initialLength)
    83   : JSObject(proto)
    84   , length(initialLength)
    85   , storageLength(initialLength < sparseArrayCutoff ? initialLength : 0)
    86   , storage(allocateStorage(storageLength))
    87 {
    88   Collector::reportExtraMemoryCost(storageLength * sizeof(JSValue*));
    89 }
    90 
    91 ArrayInstance::ArrayInstance(JSObject *proto, const List &list)
    92   : JSObject(proto)
    93   , length(list.size())
    94   , storageLength(length)
    95   , storage(allocateStorage(storageLength))
    96 {
    97   ListIterator it = list.begin();
    98   unsigned l = length;
    99   for (unsigned i = 0; i < l; ++i)
    100     storage[i] = it++;
    101   // When the array is created non-empty, its cells are filled so it's really no worse than
    102   // a property map. Therefore don't report extra memory cost.
    103 }
    104 
    105 ArrayInstance::~ArrayInstance()
    106 {
    107   if (storage) {
    108     delete reinterpret_cast<OverflowMap*>(storage[-2]);
    109     freeStorage(storage);
    110   }
    111 }
    112 
    113 JSValue* ArrayInstance::getItem(unsigned i) const
    114 {
    115     if (i < storageLength) {
    116         JSValue* value = storage[i];
    117         return value ? value : jsUndefined();
    118     }
    119 
    120     const OverflowMap* overflow = overflowMap(storage);
    121     if (!overflow)
    122         return jsUndefined();
    123 
    124     JSValue* value = overflow->get(i);
    125     return value ? value : jsUndefined();
    126 }
    127 
    128 JSValue *ArrayInstance::lengthGetter(ExecState*, JSObject*, const Identifier&, const PropertySlot& slot)
    129 {
    130   return jsNumber(static_cast<ArrayInstance *>(slot.slotBase())->length);
    131 }
    132 
    133 bool ArrayInstance::getOwnPropertySlot(ExecState* exec, const Identifier& propertyName, PropertySlot& slot)
    134 {
    135   if (propertyName == exec->propertyNames().length) {
    136     slot.setCustom(this, lengthGetter);
    137     return true;
    138   }
    139 
    140   bool ok;
    141   unsigned index = propertyName.toArrayIndex(&ok);
    142   if (!ok)
    143     return JSObject::getOwnPropertySlot(exec, propertyName, slot);
    144 
    145   if (index < storageLength) {
    146     JSValue *v = storage[index];
    147     if (!v)
    148       return false;     
    149     slot.setValueSlot(this, &storage[index]);
    150     return true;
    151   }
    152   if (index > MAX_ARRAY_INDEX)
    153     return JSObject::getOwnPropertySlot(exec, propertyName, slot);
    154   OverflowMap* overflow = overflowMap(storage);
    155   if (!overflow)
    156     return false;
    157   OverflowMap::iterator it = overflow->find(index);
    158   if (it == overflow->end())
    159     return false;
    160   slot.setValueSlot(this, &it->second);
    161   return true;
    162 }
    163 
    164 bool ArrayInstance::getOwnPropertySlot(ExecState *exec, unsigned index, PropertySlot& slot)
    165 {
    166   if (index < storageLength) {
    167     JSValue *v = storage[index];
    168     if (!v)
    169       return false;
    170     slot.setValueSlot(this, &storage[index]);
    171     return true;
    172   }
    173   if (index > MAX_ARRAY_INDEX)
    174     return getOwnPropertySlot(exec, Identifier::from(index), slot);
    175   OverflowMap* overflow = overflowMap(storage);
    176   if (!overflow)
    177     return false;
    178   OverflowMap::iterator it = overflow->find(index);
    179   if (it == overflow->end())
    180     return false;
    181   slot.setValueSlot(this, &it->second);
    182   return true;
    183 }
    184 
    185 // Special implementation of [[Put]] - see ECMA 15.4.5.1
    186 void ArrayInstance::put(ExecState* exec, const Identifier& propertyName, JSValue* value, int attr)
    187 {
    188   if (propertyName == exec->propertyNames().length) {
    189     unsigned int newLen = value->toUInt32(exec);
    190     if (value->toNumber(exec) != double(newLen)) {
    191       throwError(exec, RangeError, "Invalid array length.");
    192       return;
    193     }
    194     setLength(newLen);
    195     return;
    196   }
    197 
    198   bool ok;
    199   unsigned index = propertyName.toArrayIndex(&ok);
    200   if (ok) {
    201     put(exec, index, value, attr);
    202     return;
    203   }
    204 
    205   JSObject::put(exec, propertyName, value, attr);
    206 }
    207 
    208 void ArrayInstance::put(ExecState *exec, unsigned index, JSValue *value, int attr)
    209 {
    210   // 0xFFFFFFFF is a bit weird --- it should be treated as a non-array index, even when it's a string
    211   if (index > MAX_ARRAY_INDEX) {
    212     put(exec, Identifier::from(index), value, attr);
    213     return;
    214   }
    215 
    216   if (index < sparseArrayCutoff && index >= storageLength)
    217     resizeStorage(index + 1);
    218 
    219   if (index >= length)
    220     length = index + 1;
    221 
    222   if (index < storageLength) {
    223     storage[index] = value;
    224     return;
    225   }
    226 
    227   OverflowMap* overflow = overflowMap(storage);
    228   if (!overflow) {
    229     overflow = new OverflowMap;
    230     if (!storage)
    231       storage = allocateStorage(1);
    232     storage[-2] = reinterpret_cast<JSValue*>(overflow);
    233   }
    234   overflow->add(index, value);
    235 }
    236 
    237 bool ArrayInstance::deleteProperty(ExecState* exec, const Identifier &propertyName)
    238 {
    239   if (propertyName == exec->propertyNames().length)
    240     return false;
    241 
    242   bool ok;
    243   uint32_t index = propertyName.toArrayIndex(&ok);
    244   if (ok) {
    245     if (index >= length)
    246       return true;
    247     if (index < storageLength) {
    248       storage[index] = 0;
    249       return true;
    250     }
    251     if (OverflowMap* overflow = overflowMap(storage)) {
    252       OverflowMap::iterator it = overflow->find(index);
    253       if (it == overflow->end())
    254         return false;
    255       overflow->remove(it);
    256       return true;
    257     }
    258     return false;
    259   }
    260 
    261   return JSObject::deleteProperty(exec, propertyName);
    262 }
    263 
    264 bool ArrayInstance::deleteProperty(ExecState *exec, unsigned index)
    265 {
    266   if (index > MAX_ARRAY_INDEX)
    267     return deleteProperty(exec, Identifier::from(index));
    268 
    269   if (index >= length)
    270     return true;
    271   if (index < storageLength) {
    272     storage[index] = 0;
    273     return true;
    274   }
    275   OverflowMap* overflow = overflowMap(storage);
    276   if (!overflow)
    277     return false;
    278   OverflowMap::iterator it = overflow->find(index);
    279   if (it == overflow->end())
    280     return false;
    281   overflow->remove(it);
    282   return true;
    283 }
    284 
    285 void ArrayInstance::getPropertyNames(ExecState* exec, PropertyNameArray& propertyNames)
    286 {
    287   // avoid fetching this every time through the loop
    288   JSValue* undefined = jsUndefined();
    289  
    290   for (unsigned i = 0; i < storageLength; ++i) {
    291     JSValue* value = storage[i];
    292     if (value && value != undefined)
    293       propertyNames.add(Identifier::from(i));
    294   }
    295 
    296   OverflowMap* overflow = overflowMap(storage);
    297   if (overflow) {
    298     OverflowMap::iterator end = overflow->end();
    299     for (OverflowMap::iterator it = overflow->begin(); it != end; ++it) {
    300       JSValue* value = it->second;
    301       if (value && value != undefined)
    302         propertyNames.add(Identifier::from(it->first));
    303     }
    304   }
    305  
    306   JSObject::getPropertyNames(exec, propertyNames);
    307 }
    308 
    309 void ArrayInstance::resizeStorage(unsigned newLength)
    310 {
    311     if (newLength < storageLength) {
    312       memset(storage + newLength, 0, sizeof(JSValue *) * (storageLength - newLength));
    313     }
    314     size_t cap = capacity();
    315     if (newLength > cap) {
    316       unsigned newCapacity;
    317       if (newLength > sparseArrayCutoff) {
    318         newCapacity = newLength;
    319       } else {
    320         newCapacity = (newLength * 3 + 1) / 2;
    321         if (newCapacity > sparseArrayCutoff) {
    322           newCapacity = sparseArrayCutoff;
    323         }
    324       }
    325      
    326       reallocateStorage(storage, newCapacity);
    327       memset(storage + cap, 0, sizeof(JSValue*) * (newCapacity - cap));
    328     }
    329     storageLength = newLength;
    330 }
    331 
    332 void ArrayInstance::setLength(unsigned newLength)
    333 {
    334   if (newLength <= storageLength)
    335     resizeStorage(newLength);
    336 
    337   if (newLength < length) {
    338     if (OverflowMap* overflow = overflowMap(storage)) {
    339       OverflowMap copy = *overflow;
    340       OverflowMap::iterator end = copy.end();
    341       for (OverflowMap::iterator it = copy.begin(); it != end; ++it) {
    342         if (it->first >= newLength)
    343           overflow->remove(it->first);
    344       }
    345     }
    346   }
    347  
    348   length = newLength;
    349 }
    350 
    351 void ArrayInstance::mark()
    352 {
    353   JSObject::mark();
    354   unsigned l = storageLength;
    355   for (unsigned i = 0; i < l; ++i) {
    356     JSValue* imp = storage[i];
    357     if (imp && !imp->marked())
    358       imp->mark();
    359   }
    360   if (OverflowMap* overflow = overflowMap(storage)) {
    361     OverflowMap::iterator end = overflow->end();
    362     for (OverflowMap::iterator it = overflow->begin(); it != end; ++it) {
    363       JSValue* value = it->second;
    364       if (value && !value->marked())
    365         value->mark();
    366     }
    367   }
    368 }
    369 
    370 static ExecState* execForCompareByStringForQSort = 0;
    371 
    372 static int compareByStringForQSort(const void *a, const void *b)
    373 {
    374     ExecState *exec = execForCompareByStringForQSort;
    375     JSValue *va = *(JSValue **)a;
    376     JSValue *vb = *(JSValue **)b;
    377     ASSERT(!va->isUndefined());
    378     ASSERT(!vb->isUndefined());
    379     return compare(va->toString(exec), vb->toString(exec));
    380 }
    381 
    382 void ArrayInstance::sort(ExecState* exec)
    383 {
    384     size_t lengthNotIncludingUndefined = compactForSorting();
    385      
    386     ExecState* oldExec = execForCompareByStringForQSort;
    387     execForCompareByStringForQSort = exec;
    388 #if HAVE(MERGESORT)
    389     // mergesort usually does fewer compares, so it is actually faster than qsort for JS sorts.
    390     // however, becuase it requires extra copies of the storage buffer, don't use it for very
    391     // large arrays
    392     // FIXME: for sorting by string value, the fastest thing would actually be to convert all the
    393     // values to string once up front, and then use a radix sort. That would be O(N) rather than
    394     // O(N log N).
    395     if (lengthNotIncludingUndefined < sparseArrayCutoff) {
    396         JSValue** storageCopy = allocateStorage(capacity());
    397         memcpy(storageCopy, storage, capacity() * sizeof(JSValue*));
    398         mergesort(storageCopy, lengthNotIncludingUndefined, sizeof(JSValue *), compareByStringForQSort);
    399         freeStorage(storage);
    400         storage = storageCopy;
    401         execForCompareByStringForQSort = oldExec;
    402         return;
    403     }
    404 #endif
    405 
    406     qsort(storage, lengthNotIncludingUndefined, sizeof(JSValue*), compareByStringForQSort);
    407     execForCompareByStringForQSort = oldExec;
    408 }
    409 
    410 struct CompareWithCompareFunctionArguments {
    411     CompareWithCompareFunctionArguments(ExecState *e, JSObject *cf)
    412         : exec(e)
    413         , compareFunction(cf)
    414         , globalObject(e->dynamicInterpreter()->globalObject())
    415     {
    416         arguments.append(jsUndefined());
    417         arguments.append(jsUndefined());
    418     }
    419 
    420     ExecState *exec;
    421     JSObject *compareFunction;
    422     List arguments;
    423     JSObject *globalObject;
    424 };
    425 
    426 static CompareWithCompareFunctionArguments* compareWithCompareFunctionArguments = 0;
    427 
    428 static int compareWithCompareFunctionForQSort(const void *a, const void *b)
    429 {
    430     CompareWithCompareFunctionArguments *args = compareWithCompareFunctionArguments;
    431 
    432     JSValue *va = *(JSValue **)a;
    433     JSValue *vb = *(JSValue **)b;
    434     ASSERT(!va->isUndefined());
    435     ASSERT(!vb->isUndefined());
    436 
    437     args->arguments.clear();
    438     args->arguments.append(va);
    439     args->arguments.append(vb);
    440     double compareResult = args->compareFunction->call
    441         (args->exec, args->globalObject, args->arguments)->toNumber(args->exec);
    442     return compareResult < 0 ? -1 : compareResult > 0 ? 1 : 0;
    443 }
    444 
    445 void ArrayInstance::sort(ExecState* exec, JSObject* compareFunction)
    446 {
    447     size_t lengthNotIncludingUndefined = compactForSorting();
    448 
    449     CompareWithCompareFunctionArguments* oldArgs = compareWithCompareFunctionArguments;
    450     CompareWithCompareFunctionArguments args(exec, compareFunction);
    451     compareWithCompareFunctionArguments = &args;
    452 #if HAVE(MERGESORT)
    453     // mergesort usually does fewer compares, so it is actually faster than qsort for JS sorts.
    454     // however, becuase it requires extra copies of the storage buffer, don't use it for very
    455     // large arrays
    456     // FIXME: a tree sort using a perfectly balanced tree (e.g. an AVL tree) could do an even
    457     // better job of minimizing compares
    458     if (lengthNotIncludingUndefined < sparseArrayCutoff) {
    459         JSValue** storageCopy = allocateStorage(capacity());
    460         memcpy(storageCopy, storage, capacity() * sizeof(JSValue*));
    461         mergesort(storageCopy, lengthNotIncludingUndefined, sizeof(JSValue *), compareWithCompareFunctionForQSort);
    462         freeStorage(storage);
    463         storage = storageCopy;
    464         compareWithCompareFunctionArguments = oldArgs;
    465         return;
    466     }
    467 #endif
    468     qsort(storage, lengthNotIncludingUndefined, sizeof(JSValue*), compareWithCompareFunctionForQSort);
    469     compareWithCompareFunctionArguments = oldArgs;
    470 }
    471 
    472 unsigned ArrayInstance::compactForSorting()
    473 {
    474     JSValue *undefined = jsUndefined();
    475 
    476     unsigned o = 0;
    477    
    478     for (unsigned i = 0; i != storageLength; ++i) {
    479         JSValue *v = storage[i];
    480         if (v && v != undefined) {
    481             if (o != i)
    482                 storage[o] = v;
    483             o++;
    484         }
    485     }
    486    
    487     unsigned newLength = o;
    488 
    489     if (OverflowMap* overflow = overflowMap(storage)) {
    490         OverflowMap::iterator end = overflow->end();
    491         for (OverflowMap::iterator it = overflow->begin(); it != end; ++it)
    492             newLength += it->second != undefined;
    493    
    494         if (newLength > storageLength)
    495             resizeStorage(newLength);
    496    
    497         for (OverflowMap::iterator it = overflow->begin(); it != end; ++it) {
    498             JSValue* v = it->second;
    499             if (v != undefined) {
    500                 storage[o] = v;
    501                 o++;
    502             }
    503         }
    504         delete overflow;
    505         storage[-2] = 0;
    506     }
    507    
    508     if (newLength != storageLength)
    509         memset(storage + o, 0, sizeof(JSValue *) * (storageLength - o));
    510    
    511     return o;
    512 }
    51336
    51437// ------------------------------ ArrayPrototype ----------------------------

  • trunk/JavaScriptCore/kjs/array_object.h

    r15952 r26881  
    5050  };
    5151
    52   const unsigned MAX_ARRAY_INDEX = 0xFFFFFFFEu;
    53 
    5452  class ArrayObjectImp : public InternalFunctionImp {
    5553  public:
Note: See TracChangeset for help on using the changeset viewer.