JavaScriptCore/kjs/array_instance.cpp - external/Webkit - Git at Google

 /*
  *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
  *  Copyright (C) 2003, 2007 Apple Inc. All rights reserved.
  *  Copyright (C) 2003 Peter Kelly (pmk@post.com)
  *  Copyright (C) 2006 Alexey Proskuryakov (ap@nypop.com)
  *
  *  This library is free software; you can redistribute it and/or
  *  modify it under the terms of the GNU Lesser General Public
  *  License as published by the Free Software Foundation; either
  *  version 2 of the License, or (at your option) any later version.
  *
  *  This library is distributed in the hope that it will be useful,
  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  *  Lesser General Public License for more details.
  *
  *  You should have received a copy of the GNU Lesser General Public
  *  License along with this library; if not, write to the Free Software
  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  *
  */

 #include "config.h"
 #include "array_instance.h"

 #include "JSGlobalObject.h"
 #include "PropertyNameArray.h"
 #include <wtf/Assertions.h>

 using namespace std;

 namespace KJS {

 typedef HashMap<unsigned, JSValue*> SparseArrayValueMap;

 struct ArrayStorage {
     unsigned m_numValuesInVector;
     SparseArrayValueMap* m_sparseValueMap;
     JSValue* m_vector[1];
 };

 // 0xFFFFFFFF is a bit weird -- is not an array index even though it's an integer
 static const unsigned maxArrayIndex = 0xFFFFFFFEU;

 // Our policy for when to use a vector and when to use a sparse map.
 // For all array indices under sparseArrayCutoff, we always use a vector.
 // When indices greater than sparseArrayCutoff are involved, we use a vector
 // as long as it is 1/8 full. If more sparse than that, we use a map.
 // This value has to be a macro to be used in max() and min() without introducing
 // a PIC branch in Mach-O binaries, see <rdar://problem/5971391>.
 #define sparseArrayCutoff 10000U
 static const unsigned minDensityMultiplier = 8;

 static const unsigned copyingSortCutoff = 50000;

 const ClassInfo ArrayInstance::info = {"Array", 0, 0};

 static inline size_t storageSize(unsigned vectorLength)
 {
     return sizeof(ArrayStorage) - sizeof(JSValue*) + vectorLength * sizeof(JSValue*);
 }

 static inline unsigned increasedVectorLength(unsigned newLength)
 {
     return (newLength * 3 + 1) / 2;
 }

 static inline bool isDenseEnoughForVector(unsigned length, unsigned numValues)
 {
     return length / minDensityMultiplier <= numValues;
 }

 ArrayInstance::ArrayInstance(JSObject* prototype, unsigned initialLength)
     : JSObject(prototype)
 {
     unsigned initialCapacity = min(initialLength, sparseArrayCutoff);

     m_length = initialLength;
     m_vectorLength = initialCapacity;
     m_storage = static_cast<ArrayStorage*>(fastZeroedMalloc(storageSize(initialCapacity)));

     Collector::reportExtraMemoryCost(initialCapacity * sizeof(JSValue*));
 }

 ArrayInstance::ArrayInstance(JSObject* prototype, const List& list)
     : JSObject(prototype)
 {
     unsigned length = list.size();

     m_length = length;
     m_vectorLength = length;

     ArrayStorage* storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(length)));

     storage->m_numValuesInVector = length;
     storage->m_sparseValueMap = 0;

     size_t i = 0;
     List::const_iterator end = list.end();
     for (List::const_iterator it = list.begin(); it != end; ++it, ++i)
         storage->m_vector[i] = *it;

     m_storage = storage;

     // When the array is created non-empty, its cells are filled, so it's really no worse than
     // a property map. Therefore don't report extra memory cost.
 }

 ArrayInstance::~ArrayInstance()
 {
     delete m_storage->m_sparseValueMap;
     fastFree(m_storage);
 }

 JSValue* ArrayInstance::getItem(unsigned i) const
 {
     ASSERT(i <= maxArrayIndex);

     ArrayStorage* storage = m_storage;

     if (i < m_vectorLength) {
         JSValue* value = storage->m_vector[i];
         return value ? value : jsUndefined();
     }

     SparseArrayValueMap* map = storage->m_sparseValueMap;
     if (!map)
         return jsUndefined();

     JSValue* value = map->get(i);
     return value ? value : jsUndefined();
 }

 JSValue* ArrayInstance::lengthGetter(ExecState*, JSObject*, const Identifier&, const PropertySlot& slot)
 {
     return jsNumber(static_cast<ArrayInstance*>(slot.slotBase())->m_length);
 }

 ALWAYS_INLINE bool ArrayInstance::inlineGetOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot)
 {
     ArrayStorage* storage = m_storage;

     if (i >= m_length) {
         if (i > maxArrayIndex)
             return getOwnPropertySlot(exec, Identifier::from(i), slot);
         return false;
     }

     if (i < m_vectorLength) {
         JSValue*& valueSlot = storage->m_vector[i];
         if (valueSlot) {
             slot.setValueSlot(this, &valueSlot);
             return true;
         }
     } else if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
         if (i >= sparseArrayCutoff) {
             SparseArrayValueMap::iterator it = map->find(i);
             if (it != map->end()) {
                 slot.setValueSlot(this, &it->second);
                 return true;
             }
         }
     }

     return false;
 }

 bool ArrayInstance::getOwnPropertySlot(ExecState* exec, const Identifier& propertyName, PropertySlot& slot)
 {
     if (propertyName == exec->propertyNames().length) {
         slot.setCustom(this, lengthGetter);
         return true;
     }

     bool isArrayIndex;
     unsigned i = propertyName.toArrayIndex(&isArrayIndex);
     if (isArrayIndex)
         return inlineGetOwnPropertySlot(exec, i, slot);

     return JSObject::getOwnPropertySlot(exec, propertyName, slot);
 }

 bool ArrayInstance::getOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot)
 {
     return inlineGetOwnPropertySlot(exec, i, slot);
 }

 // ECMA 15.4.5.1
 void ArrayInstance::put(ExecState* exec, const Identifier& propertyName, JSValue* value, int attributes)
 {
     bool isArrayIndex;
     unsigned i = propertyName.toArrayIndex(&isArrayIndex);
     if (isArrayIndex) {
         put(exec, i, value, attributes);
         return;
     }

     if (propertyName == exec->propertyNames().length) {
         unsigned newLength = value->toUInt32(exec);
         if (value->toNumber(exec) != static_cast<double>(newLength)) {
             throwError(exec, RangeError, "Invalid array length.");
             return;
         }
         setLength(newLength);
         return;
     }

     JSObject::put(exec, propertyName, value, attributes);
 }

 void ArrayInstance::put(ExecState* exec, unsigned i, JSValue* value, int attributes)
 {
     if (i > maxArrayIndex) {
         put(exec, Identifier::from(i), value, attributes);
         return;
     }

     ArrayStorage* storage = m_storage;

     unsigned length = m_length;
     if (i >= length) {
         length = i + 1;
         m_length = length;
     }

     if (i < m_vectorLength) {
         JSValue*& valueSlot = storage->m_vector[i];
         storage->m_numValuesInVector += !valueSlot;
         valueSlot = value;
         return;
     }

     SparseArrayValueMap* map = storage->m_sparseValueMap;

     if (i >= sparseArrayCutoff) {
         // We miss some cases where we could compact the storage, such as a large array that is being filled from the end
         // (which will only be compacted as we reach indices that are less than cutoff) - but this makes the check much faster.
         if (!isDenseEnoughForVector(i + 1, storage->m_numValuesInVector + 1)) {
             if (!map) {
                 map = new SparseArrayValueMap;
                 storage->m_sparseValueMap = map;
             }
             map->set(i, value);
             return;
         }
     }

     // We have decided that we'll put the new item into the vector.
     // Fast case is when there is no sparse map, so we can increase the vector size without moving values from it.
     if (!map || map->isEmpty()) {
         increaseVectorLength(i + 1);
         storage = m_storage;
         ++storage->m_numValuesInVector;
         storage->m_vector[i] = value;
         return;
     }

     // Decide how many values it would be best to move from the map.
     unsigned newNumValuesInVector = storage->m_numValuesInVector + 1;
     unsigned newVectorLength = increasedVectorLength(i + 1);
     for (unsigned j = max(m_vectorLength, sparseArrayCutoff); j < newVectorLength; ++j)
         newNumValuesInVector += map->contains(j);
     if (i >= sparseArrayCutoff)
         newNumValuesInVector -= map->contains(i);
     if (isDenseEnoughForVector(newVectorLength, newNumValuesInVector)) {
         unsigned proposedNewNumValuesInVector = newNumValuesInVector;
         while (true) {
             unsigned proposedNewVectorLength = increasedVectorLength(newVectorLength + 1);
             for (unsigned j = max(newVectorLength, sparseArrayCutoff); j < proposedNewVectorLength; ++j)
                 proposedNewNumValuesInVector += map->contains(j);
             if (!isDenseEnoughForVector(proposedNewVectorLength, proposedNewNumValuesInVector))
                 break;
             newVectorLength = proposedNewVectorLength;
             newNumValuesInVector = proposedNewNumValuesInVector;
         }
     }

     storage = static_cast<ArrayStorage*>(fastRealloc(storage, storageSize(newVectorLength)));

     unsigned vectorLength = m_vectorLength;
     if (newNumValuesInVector == storage->m_numValuesInVector + 1) {
         for (unsigned j = vectorLength; j < newVectorLength; ++j)
             storage->m_vector[j] = 0;
         if (i > sparseArrayCutoff)
             map->remove(i);
     } else {
         for (unsigned j = vectorLength; j < max(vectorLength, sparseArrayCutoff); ++j)
             storage->m_vector[j] = 0;
         for (unsigned j = max(vectorLength, sparseArrayCutoff); j < newVectorLength; ++j)
             storage->m_vector[j] = map->take(j);
     }

     storage->m_vector[i] = value;

     m_vectorLength = newVectorLength;
     storage->m_numValuesInVector = newNumValuesInVector;

     m_storage = storage;
 }

 bool ArrayInstance::deleteProperty(ExecState* exec, const Identifier& propertyName)
 {
     bool isArrayIndex;
     unsigned i = propertyName.toArrayIndex(&isArrayIndex);
     if (isArrayIndex)
         return deleteProperty(exec, i);

     if (propertyName == exec->propertyNames().length)
         return false;

     return JSObject::deleteProperty(exec, propertyName);
 }

 bool ArrayInstance::deleteProperty(ExecState* exec, unsigned i)
 {
     ArrayStorage* storage = m_storage;

     if (i < m_vectorLength) {
         JSValue*& valueSlot = storage->m_vector[i];
         bool hadValue = valueSlot;
         valueSlot = 0;
         storage->m_numValuesInVector -= hadValue;
         return hadValue;
     }

     if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
         if (i >= sparseArrayCutoff) {
             SparseArrayValueMap::iterator it = map->find(i);
             if (it != map->end()) {
                 map->remove(it);
                 return true;
             }
         }
     }

     if (i > maxArrayIndex)
         return deleteProperty(exec, Identifier::from(i));

     return false;
 }

 void ArrayInstance::getPropertyNames(ExecState* exec, PropertyNameArray& propertyNames)
 {
     // FIXME: Filling PropertyNameArray with an identifier for every integer
     // is incredibly inefficient for large arrays. We need a different approach.

     ArrayStorage* storage = m_storage;

     unsigned usedVectorLength = min(m_length, m_vectorLength);
     for (unsigned i = 0; i < usedVectorLength; ++i) {
         if (storage->m_vector[i])
             propertyNames.add(Identifier::from(i));
     }

     if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
         SparseArrayValueMap::iterator end = map->end();
         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
             propertyNames.add(Identifier::from(it->first));
     }

     JSObject::getPropertyNames(exec, propertyNames);
 }

 void ArrayInstance::increaseVectorLength(unsigned newLength)
 {
     // This function leaves the array in an internally inconsistent state, because it does not move any values from sparse value map
     // to the vector. Callers have to account for that, because they can do it more efficiently.

     ArrayStorage* storage = m_storage;

     unsigned vectorLength = m_vectorLength;
     ASSERT(newLength > vectorLength);
     unsigned newVectorLength = increasedVectorLength(newLength);

     storage = static_cast<ArrayStorage*>(fastRealloc(storage, storageSize(newVectorLength)));
     m_vectorLength = newVectorLength;

     for (unsigned i = vectorLength; i < newVectorLength; ++i)
         storage->m_vector[i] = 0;

     m_storage = storage;
 }

 void ArrayInstance::setLength(unsigned newLength)
 {
     ArrayStorage* storage = m_storage;

     unsigned length = m_length;

     if (newLength < length) {
         unsigned usedVectorLength = min(length, m_vectorLength);
         for (unsigned i = newLength; i < usedVectorLength; ++i) {
             JSValue*& valueSlot = storage->m_vector[i];
             bool hadValue = valueSlot;
             valueSlot = 0;
             storage->m_numValuesInVector -= hadValue;
         }

         if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
             SparseArrayValueMap copy = *map;
             SparseArrayValueMap::iterator end = copy.end();
             for (SparseArrayValueMap::iterator it = copy.begin(); it != end; ++it) {
                 if (it->first >= newLength)
                     map->remove(it->first);
             }
             if (map->isEmpty()) {
                 delete map;
                 storage->m_sparseValueMap = 0;
             }
         }
     }

     m_length = newLength;
 }

 void ArrayInstance::mark()
 {
     JSObject::mark();

     ArrayStorage* storage = m_storage;

     unsigned usedVectorLength = min(m_length, m_vectorLength);
     for (unsigned i = 0; i < usedVectorLength; ++i) {
         JSValue* value = storage->m_vector[i];
         if (value && !value->marked())
             value->mark();
     }

     if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
         SparseArrayValueMap::iterator end = map->end();
         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) {
             JSValue* value = it->second;
             if (!value->marked())
                 value->mark();
         }
     }
 }

 static int compareByStringPairForQSort(const void* a, const void* b)
 {
     const std::pair<JSValue*, UString>* va = static_cast<const std::pair<JSValue*, UString>*>(a);
     const std::pair<JSValue*, UString>* vb = static_cast<const std::pair<JSValue*, UString>*>(b);
     return compare(va->second, vb->second);
 }

 static ExecState* execForCompareByStringForQSort = 0;
 static int compareByStringForQSort(const void* a, const void* b)
 {
     ExecState* exec = execForCompareByStringForQSort;

     JSValue* va = *static_cast<JSValue* const*>(a);
     JSValue* vb = *static_cast<JSValue* const*>(b);
     ASSERT(!va->isUndefined());
     ASSERT(!vb->isUndefined());

     return compare(va->toString(exec), vb->toString(exec));
 }

 void ArrayInstance::sort(ExecState* exec)
 {
     unsigned lengthNotIncludingUndefined = compactForSorting();

     if (lengthNotIncludingUndefined < copyingSortCutoff) {
         // Converting JavaScript values to strings can be expensive, so we do it once up front and sort based on that.
         // This is a considerable improvement over doing it twice per comparison, though it requires a large temporary
         // buffer.  For large arrays, we fall back to a qsort on the JavaScriptValues to avoid creating copies.

         Vector<std::pair<JSValue*, UString> > values(lengthNotIncludingUndefined);
         for (size_t i = 0; i < lengthNotIncludingUndefined; i++) {
             JSValue* value = m_storage->m_vector[i];
             ASSERT(!value->isUndefined());
             values[i].first = value;
             values[i].second = value->toString(exec);
         }

         // FIXME: Since we sort by string value, a fast algorithm might be to use a radix sort. That would be O(N) rather
         // than O(N log N).

 #if HAVE(MERGESORT)
         mergesort(values.begin(), values.size(), sizeof(std::pair<JSValue*, UString>), compareByStringPairForQSort);
 #else
         qsort(values.begin(), values.size(), sizeof(std::pair<JSValue*, UString>), compareByStringPairForQSort);
 #endif
         for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
             m_storage->m_vector[i] = values[i].first;
         return;
     }

     ExecState* oldExec = execForCompareByStringForQSort;
     execForCompareByStringForQSort = exec;
     qsort(m_storage->m_vector, lengthNotIncludingUndefined, sizeof(JSValue*), compareByStringForQSort);
     execForCompareByStringForQSort = oldExec;
 }

 struct CompareWithCompareFunctionArguments {
     CompareWithCompareFunctionArguments(ExecState *e, JSObject *cf)
         : exec(e)
         , compareFunction(cf)
         , globalObject(e->dynamicGlobalObject())
     {
     }

     ExecState *exec;
     JSObject *compareFunction;
     List arguments;
     JSGlobalObject* globalObject;
 };

 static CompareWithCompareFunctionArguments* compareWithCompareFunctionArguments = 0;

 static int compareWithCompareFunctionForQSort(const void* a, const void* b)
 {
     CompareWithCompareFunctionArguments *args = compareWithCompareFunctionArguments;

     JSValue* va = *static_cast<JSValue* const*>(a);
     JSValue* vb = *static_cast<JSValue* const*>(b);
     ASSERT(!va->isUndefined());
     ASSERT(!vb->isUndefined());

     args->arguments.clear();
     args->arguments.append(va);
     args->arguments.append(vb);
     double compareResult = args->compareFunction->call
         (args->exec, args->globalObject, args->arguments)->toNumber(args->exec);
     return compareResult < 0 ? -1 : compareResult > 0 ? 1 : 0;
 }

 void ArrayInstance::sort(ExecState* exec, JSObject* compareFunction)
 {
     size_t lengthNotIncludingUndefined = compactForSorting();

     CompareWithCompareFunctionArguments* oldArgs = compareWithCompareFunctionArguments;
     CompareWithCompareFunctionArguments args(exec, compareFunction);
     compareWithCompareFunctionArguments = &args;

 #if HAVE(MERGESORT)
     // Because mergesort usually does fewer compares, it is faster than qsort here.
     // However, because it requires extra copies of the storage buffer, don't use it for very
     // large arrays.

     // FIXME: A tree sort using a perfectly balanced tree (e.g. an AVL tree) could do an even
     // better job of minimizing compares.

     if (lengthNotIncludingUndefined < copyingSortCutoff) {
         // During the sort, we could do a garbage collect, and it's important to still
         // have references to every object in the array for ArrayInstance::mark.
         // The mergesort algorithm does not guarantee this, so we sort a copy rather
         // than the original.
         size_t size = storageSize(m_vectorLength);
         ArrayStorage* copy = static_cast<ArrayStorage*>(fastMalloc(size));
         memcpy(copy, m_storage, size);
         mergesort(copy->m_vector, lengthNotIncludingUndefined, sizeof(JSValue*), compareWithCompareFunctionForQSort);
         fastFree(m_storage);
         m_storage = copy;
         compareWithCompareFunctionArguments = oldArgs;
         return;
     }
 #endif

     qsort(m_storage->m_vector, lengthNotIncludingUndefined, sizeof(JSValue*), compareWithCompareFunctionForQSort);
     compareWithCompareFunctionArguments = oldArgs;
 }

 unsigned ArrayInstance::compactForSorting()
 {
     ArrayStorage* storage = m_storage;

     unsigned usedVectorLength = min(m_length, m_vectorLength);

     unsigned numDefined = 0;
     unsigned numUndefined = 0;

     for (; numDefined < usedVectorLength; ++numDefined) {
         JSValue* v = storage->m_vector[numDefined];
         if (!v || v->isUndefined())
             break;
     }
     for (unsigned i = numDefined; i < usedVectorLength; ++i) {
         if (JSValue* v = storage->m_vector[i]) {
             if (v->isUndefined())
                 ++numUndefined;
             else
                 storage->m_vector[numDefined++] = v;
         }
     }

     unsigned newUsedVectorLength = numDefined + numUndefined;

     if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
         newUsedVectorLength += map->size();
         if (newUsedVectorLength > m_vectorLength) {
             increaseVectorLength(newUsedVectorLength);
             storage = m_storage;
         }

         SparseArrayValueMap::iterator end = map->end();
         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
             storage->m_vector[numDefined++] = it->second;

         delete map;
         storage->m_sparseValueMap = 0;
     }

     for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
         storage->m_vector[i] = jsUndefined();
     for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
         storage->m_vector[i] = 0;

     return numDefined;
 }

 }
	/*
	* Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
	* Copyright (C) 2003, 2007 Apple Inc. All rights reserved.
	* Copyright (C) 2003 Peter Kelly (pmk@post.com)
	* Copyright (C) 2006 Alexey Proskuryakov (ap@nypop.com)
	*
	* This library is free software; you can redistribute it and/or
	* modify it under the terms of the GNU Lesser General Public
	* License as published by the Free Software Foundation; either
	* version 2 of the License, or (at your option) any later version.
	*
	* This library is distributed in the hope that it will be useful,
	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	* Lesser General Public License for more details.
	*
	* You should have received a copy of the GNU Lesser General Public
	* License along with this library; if not, write to the Free Software
	* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
	*
	*/

	#include "config.h"
	#include "array_instance.h"

	#include "JSGlobalObject.h"
	#include "PropertyNameArray.h"
	#include <wtf/Assertions.h>

	using namespace std;

	namespace KJS {

	typedef HashMap<unsigned, JSValue*> SparseArrayValueMap;

	struct ArrayStorage {
	unsigned m_numValuesInVector;
	SparseArrayValueMap* m_sparseValueMap;
	JSValue* m_vector[1];
	};

	// 0xFFFFFFFF is a bit weird -- is not an array index even though it's an integer
	static const unsigned maxArrayIndex = 0xFFFFFFFEU;

	// Our policy for when to use a vector and when to use a sparse map.
	// For all array indices under sparseArrayCutoff, we always use a vector.
	// When indices greater than sparseArrayCutoff are involved, we use a vector
	// as long as it is 1/8 full. If more sparse than that, we use a map.
	// This value has to be a macro to be used in max() and min() without introducing
	// a PIC branch in Mach-O binaries, see <rdar://problem/5971391>.
	#define sparseArrayCutoff 10000U
	static const unsigned minDensityMultiplier = 8;

	static const unsigned copyingSortCutoff = 50000;

	const ClassInfo ArrayInstance::info = {"Array", 0, 0};

	static inline size_t storageSize(unsigned vectorLength)
	{
	return sizeof(ArrayStorage) - sizeof(JSValue) + vectorLength sizeof(JSValue*);
	}

	static inline unsigned increasedVectorLength(unsigned newLength)
	{
	return (newLength * 3 + 1) / 2;
	}

	static inline bool isDenseEnoughForVector(unsigned length, unsigned numValues)
	{
	return length / minDensityMultiplier <= numValues;
	}

	ArrayInstance::ArrayInstance(JSObject* prototype, unsigned initialLength)
	: JSObject(prototype)
	{
	unsigned initialCapacity = min(initialLength, sparseArrayCutoff);

	m_length = initialLength;
	m_vectorLength = initialCapacity;
	m_storage = static_cast<ArrayStorage*>(fastZeroedMalloc(storageSize(initialCapacity)));

	Collector::reportExtraMemoryCost(initialCapacity * sizeof(JSValue*));
	}

	ArrayInstance::ArrayInstance(JSObject* prototype, const List& list)
	: JSObject(prototype)
	{
	unsigned length = list.size();

	m_length = length;
	m_vectorLength = length;

	ArrayStorage* storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(length)));

	storage->m_numValuesInVector = length;
	storage->m_sparseValueMap = 0;

	size_t i = 0;
	List::const_iterator end = list.end();
	for (List::const_iterator it = list.begin(); it != end; ++it, ++i)
	storage->m_vector[i] = *it;

	m_storage = storage;

	// When the array is created non-empty, its cells are filled, so it's really no worse than
	// a property map. Therefore don't report extra memory cost.
	}

	ArrayInstance::~ArrayInstance()
	{
	delete m_storage->m_sparseValueMap;
	fastFree(m_storage);
	}

	JSValue* ArrayInstance::getItem(unsigned i) const
	{
	ASSERT(i <= maxArrayIndex);

	ArrayStorage* storage = m_storage;

	if (i < m_vectorLength) {
	JSValue* value = storage->m_vector[i];
	return value ? value : jsUndefined();
	}

	SparseArrayValueMap* map = storage->m_sparseValueMap;
	if (!map)
	return jsUndefined();

	JSValue* value = map->get(i);
	return value ? value : jsUndefined();
	}

	JSValue* ArrayInstance::lengthGetter(ExecState, JSObject, const Identifier&, const PropertySlot& slot)
	{
	return jsNumber(static_cast<ArrayInstance*>(slot.slotBase())->m_length);
	}

	ALWAYS_INLINE bool ArrayInstance::inlineGetOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot)
	{
	ArrayStorage* storage = m_storage;

	if (i >= m_length) {
	if (i > maxArrayIndex)
	return getOwnPropertySlot(exec, Identifier::from(i), slot);
	return false;
	}

	if (i < m_vectorLength) {
	JSValue*& valueSlot = storage->m_vector[i];
	if (valueSlot) {
	slot.setValueSlot(this, &valueSlot);
	return true;
	}
	} else if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
	if (i >= sparseArrayCutoff) {
	SparseArrayValueMap::iterator it = map->find(i);
	if (it != map->end()) {
	slot.setValueSlot(this, &it->second);
	return true;
	}
	}
	}

	return false;
	}

	bool ArrayInstance::getOwnPropertySlot(ExecState* exec, const Identifier& propertyName, PropertySlot& slot)
	{
	if (propertyName == exec->propertyNames().length) {
	slot.setCustom(this, lengthGetter);
	return true;
	}

	bool isArrayIndex;
	unsigned i = propertyName.toArrayIndex(&isArrayIndex);
	if (isArrayIndex)
	return inlineGetOwnPropertySlot(exec, i, slot);

	return JSObject::getOwnPropertySlot(exec, propertyName, slot);
	}

	bool ArrayInstance::getOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot)
	{
	return inlineGetOwnPropertySlot(exec, i, slot);
	}

	// ECMA 15.4.5.1
	void ArrayInstance::put(ExecState* exec, const Identifier& propertyName, JSValue* value, int attributes)
	{
	bool isArrayIndex;
	unsigned i = propertyName.toArrayIndex(&isArrayIndex);
	if (isArrayIndex) {
	put(exec, i, value, attributes);
	return;
	}

	if (propertyName == exec->propertyNames().length) {
	unsigned newLength = value->toUInt32(exec);
	if (value->toNumber(exec) != static_cast<double>(newLength)) {
	throwError(exec, RangeError, "Invalid array length.");
	return;
	}
	setLength(newLength);
	return;
	}

	JSObject::put(exec, propertyName, value, attributes);
	}

	void ArrayInstance::put(ExecState* exec, unsigned i, JSValue* value, int attributes)
	{
	if (i > maxArrayIndex) {
	put(exec, Identifier::from(i), value, attributes);
	return;
	}

	ArrayStorage* storage = m_storage;

	unsigned length = m_length;
	if (i >= length) {
	length = i + 1;
	m_length = length;
	}

	if (i < m_vectorLength) {
	JSValue*& valueSlot = storage->m_vector[i];
	storage->m_numValuesInVector += !valueSlot;
	valueSlot = value;
	return;
	}

	SparseArrayValueMap* map = storage->m_sparseValueMap;

	if (i >= sparseArrayCutoff) {
	// We miss some cases where we could compact the storage, such as a large array that is being filled from the end
	// (which will only be compacted as we reach indices that are less than cutoff) - but this makes the check much faster.
	if (!isDenseEnoughForVector(i + 1, storage->m_numValuesInVector + 1)) {
	if (!map) {
	map = new SparseArrayValueMap;
	storage->m_sparseValueMap = map;
	}
	map->set(i, value);
	return;
	}
	}

	// We have decided that we'll put the new item into the vector.
	// Fast case is when there is no sparse map, so we can increase the vector size without moving values from it.
	if (!map \|\| map->isEmpty()) {
	increaseVectorLength(i + 1);
	storage = m_storage;
	++storage->m_numValuesInVector;
	storage->m_vector[i] = value;
	return;
	}

	// Decide how many values it would be best to move from the map.
	unsigned newNumValuesInVector = storage->m_numValuesInVector + 1;
	unsigned newVectorLength = increasedVectorLength(i + 1);
	for (unsigned j = max(m_vectorLength, sparseArrayCutoff); j < newVectorLength; ++j)
	newNumValuesInVector += map->contains(j);
	if (i >= sparseArrayCutoff)
	newNumValuesInVector -= map->contains(i);
	if (isDenseEnoughForVector(newVectorLength, newNumValuesInVector)) {
	unsigned proposedNewNumValuesInVector = newNumValuesInVector;
	while (true) {
	unsigned proposedNewVectorLength = increasedVectorLength(newVectorLength + 1);
	for (unsigned j = max(newVectorLength, sparseArrayCutoff); j < proposedNewVectorLength; ++j)
	proposedNewNumValuesInVector += map->contains(j);
	if (!isDenseEnoughForVector(proposedNewVectorLength, proposedNewNumValuesInVector))
	break;
	newVectorLength = proposedNewVectorLength;
	newNumValuesInVector = proposedNewNumValuesInVector;
	}
	}

	storage = static_cast<ArrayStorage*>(fastRealloc(storage, storageSize(newVectorLength)));

	unsigned vectorLength = m_vectorLength;
	if (newNumValuesInVector == storage->m_numValuesInVector + 1) {
	for (unsigned j = vectorLength; j < newVectorLength; ++j)
	storage->m_vector[j] = 0;
	if (i > sparseArrayCutoff)
	map->remove(i);
	} else {
	for (unsigned j = vectorLength; j < max(vectorLength, sparseArrayCutoff); ++j)
	storage->m_vector[j] = 0;
	for (unsigned j = max(vectorLength, sparseArrayCutoff); j < newVectorLength; ++j)
	storage->m_vector[j] = map->take(j);
	}

	storage->m_vector[i] = value;

	m_vectorLength = newVectorLength;
	storage->m_numValuesInVector = newNumValuesInVector;

	m_storage = storage;
	}

	bool ArrayInstance::deleteProperty(ExecState* exec, const Identifier& propertyName)
	{
	bool isArrayIndex;
	unsigned i = propertyName.toArrayIndex(&isArrayIndex);
	if (isArrayIndex)
	return deleteProperty(exec, i);

	if (propertyName == exec->propertyNames().length)
	return false;

	return JSObject::deleteProperty(exec, propertyName);
	}

	bool ArrayInstance::deleteProperty(ExecState* exec, unsigned i)
	{
	ArrayStorage* storage = m_storage;

	if (i < m_vectorLength) {
	JSValue*& valueSlot = storage->m_vector[i];
	bool hadValue = valueSlot;
	valueSlot = 0;
	storage->m_numValuesInVector -= hadValue;
	return hadValue;
	}

	if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
	if (i >= sparseArrayCutoff) {
	SparseArrayValueMap::iterator it = map->find(i);
	if (it != map->end()) {
	map->remove(it);
	return true;
	}
	}
	}

	if (i > maxArrayIndex)
	return deleteProperty(exec, Identifier::from(i));

	return false;
	}

	void ArrayInstance::getPropertyNames(ExecState* exec, PropertyNameArray& propertyNames)
	{
	// FIXME: Filling PropertyNameArray with an identifier for every integer
	// is incredibly inefficient for large arrays. We need a different approach.

	ArrayStorage* storage = m_storage;

	unsigned usedVectorLength = min(m_length, m_vectorLength);
	for (unsigned i = 0; i < usedVectorLength; ++i) {
	if (storage->m_vector[i])
	propertyNames.add(Identifier::from(i));
	}

	if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
	SparseArrayValueMap::iterator end = map->end();
	for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
	propertyNames.add(Identifier::from(it->first));
	}

	JSObject::getPropertyNames(exec, propertyNames);
	}

	void ArrayInstance::increaseVectorLength(unsigned newLength)
	{
	// This function leaves the array in an internally inconsistent state, because it does not move any values from sparse value map
	// to the vector. Callers have to account for that, because they can do it more efficiently.

	ArrayStorage* storage = m_storage;

	unsigned vectorLength = m_vectorLength;
	ASSERT(newLength > vectorLength);
	unsigned newVectorLength = increasedVectorLength(newLength);

	storage = static_cast<ArrayStorage*>(fastRealloc(storage, storageSize(newVectorLength)));
	m_vectorLength = newVectorLength;

	for (unsigned i = vectorLength; i < newVectorLength; ++i)
	storage->m_vector[i] = 0;

	m_storage = storage;
	}

	void ArrayInstance::setLength(unsigned newLength)
	{
	ArrayStorage* storage = m_storage;

	unsigned length = m_length;

	if (newLength < length) {
	unsigned usedVectorLength = min(length, m_vectorLength);
	for (unsigned i = newLength; i < usedVectorLength; ++i) {
	JSValue*& valueSlot = storage->m_vector[i];
	bool hadValue = valueSlot;
	valueSlot = 0;
	storage->m_numValuesInVector -= hadValue;
	}

	if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
	SparseArrayValueMap copy = *map;
	SparseArrayValueMap::iterator end = copy.end();
	for (SparseArrayValueMap::iterator it = copy.begin(); it != end; ++it) {
	if (it->first >= newLength)
	map->remove(it->first);
	}
	if (map->isEmpty()) {
	delete map;
	storage->m_sparseValueMap = 0;
	}
	}
	}

	m_length = newLength;
	}

	void ArrayInstance::mark()
	{
	JSObject::mark();

	ArrayStorage* storage = m_storage;

	unsigned usedVectorLength = min(m_length, m_vectorLength);
	for (unsigned i = 0; i < usedVectorLength; ++i) {
	JSValue* value = storage->m_vector[i];
	if (value && !value->marked())
	value->mark();
	}

	if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
	SparseArrayValueMap::iterator end = map->end();
	for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) {
	JSValue* value = it->second;
	if (!value->marked())
	value->mark();
	}
	}
	}

	static int compareByStringPairForQSort(const void* a, const void* b)
	{
	const std::pair<JSValue, UString> va = static_cast<const std::pair<JSValue, UString>>(a);
	const std::pair<JSValue, UString> vb = static_cast<const std::pair<JSValue, UString>>(b);
	return compare(va->second, vb->second);
	}

	static ExecState* execForCompareByStringForQSort = 0;
	static int compareByStringForQSort(const void* a, const void* b)
	{
	ExecState* exec = execForCompareByStringForQSort;

	JSValue* va = static_cast<JSValue const*>(a);
	JSValue* vb = static_cast<JSValue const*>(b);
	ASSERT(!va->isUndefined());
	ASSERT(!vb->isUndefined());

	return compare(va->toString(exec), vb->toString(exec));
	}

	void ArrayInstance::sort(ExecState* exec)
	{
	unsigned lengthNotIncludingUndefined = compactForSorting();

	if (lengthNotIncludingUndefined < copyingSortCutoff) {
	// Converting JavaScript values to strings can be expensive, so we do it once up front and sort based on that.
	// This is a considerable improvement over doing it twice per comparison, though it requires a large temporary
	// buffer. For large arrays, we fall back to a qsort on the JavaScriptValues to avoid creating copies.

	Vector<std::pair<JSValue*, UString> > values(lengthNotIncludingUndefined);
	for (size_t i = 0; i < lengthNotIncludingUndefined; i++) {
	JSValue* value = m_storage->m_vector[i];
	ASSERT(!value->isUndefined());
	values[i].first = value;
	values[i].second = value->toString(exec);
	}

	// FIXME: Since we sort by string value, a fast algorithm might be to use a radix sort. That would be O(N) rather
	// than O(N log N).

	#if HAVE(MERGESORT)
	mergesort(values.begin(), values.size(), sizeof(std::pair<JSValue*, UString>), compareByStringPairForQSort);
	#else
	qsort(values.begin(), values.size(), sizeof(std::pair<JSValue*, UString>), compareByStringPairForQSort);
	#endif
	for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
	m_storage->m_vector[i] = values[i].first;
	return;
	}

	ExecState* oldExec = execForCompareByStringForQSort;
	execForCompareByStringForQSort = exec;
	qsort(m_storage->m_vector, lengthNotIncludingUndefined, sizeof(JSValue*), compareByStringForQSort);
	execForCompareByStringForQSort = oldExec;
	}

	struct CompareWithCompareFunctionArguments {
	CompareWithCompareFunctionArguments(ExecState e, JSObject cf)
	: exec(e)
	, compareFunction(cf)
	, globalObject(e->dynamicGlobalObject())
	{
	}

	ExecState *exec;
	JSObject *compareFunction;
	List arguments;
	JSGlobalObject* globalObject;
	};

	static CompareWithCompareFunctionArguments* compareWithCompareFunctionArguments = 0;

	static int compareWithCompareFunctionForQSort(const void* a, const void* b)
	{
	CompareWithCompareFunctionArguments *args = compareWithCompareFunctionArguments;

	JSValue* va = static_cast<JSValue const*>(a);
	JSValue* vb = static_cast<JSValue const*>(b);
	ASSERT(!va->isUndefined());
	ASSERT(!vb->isUndefined());

	args->arguments.clear();
	args->arguments.append(va);
	args->arguments.append(vb);
	double compareResult = args->compareFunction->call
	(args->exec, args->globalObject, args->arguments)->toNumber(args->exec);
	return compareResult < 0 ? -1 : compareResult > 0 ? 1 : 0;
	}

	void ArrayInstance::sort(ExecState* exec, JSObject* compareFunction)
	{
	size_t lengthNotIncludingUndefined = compactForSorting();

	CompareWithCompareFunctionArguments* oldArgs = compareWithCompareFunctionArguments;
	CompareWithCompareFunctionArguments args(exec, compareFunction);
	compareWithCompareFunctionArguments = &args;

	#if HAVE(MERGESORT)
	// Because mergesort usually does fewer compares, it is faster than qsort here.
	// However, because it requires extra copies of the storage buffer, don't use it for very
	// large arrays.

	// FIXME: A tree sort using a perfectly balanced tree (e.g. an AVL tree) could do an even
	// better job of minimizing compares.

	if (lengthNotIncludingUndefined < copyingSortCutoff) {
	// During the sort, we could do a garbage collect, and it's important to still
	// have references to every object in the array for ArrayInstance::mark.
	// The mergesort algorithm does not guarantee this, so we sort a copy rather
	// than the original.
	size_t size = storageSize(m_vectorLength);
	ArrayStorage* copy = static_cast<ArrayStorage*>(fastMalloc(size));
	memcpy(copy, m_storage, size);
	mergesort(copy->m_vector, lengthNotIncludingUndefined, sizeof(JSValue*), compareWithCompareFunctionForQSort);
	fastFree(m_storage);
	m_storage = copy;
	compareWithCompareFunctionArguments = oldArgs;
	return;
	}
	#endif

	qsort(m_storage->m_vector, lengthNotIncludingUndefined, sizeof(JSValue*), compareWithCompareFunctionForQSort);
	compareWithCompareFunctionArguments = oldArgs;
	}

	unsigned ArrayInstance::compactForSorting()
	{
	ArrayStorage* storage = m_storage;

	unsigned usedVectorLength = min(m_length, m_vectorLength);

	unsigned numDefined = 0;
	unsigned numUndefined = 0;

	for (; numDefined < usedVectorLength; ++numDefined) {
	JSValue* v = storage->m_vector[numDefined];
	if (!v \|\| v->isUndefined())
	break;
	}
	for (unsigned i = numDefined; i < usedVectorLength; ++i) {
	if (JSValue* v = storage->m_vector[i]) {
	if (v->isUndefined())
	++numUndefined;
	else
	storage->m_vector[numDefined++] = v;
	}
	}

	unsigned newUsedVectorLength = numDefined + numUndefined;

	if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
	newUsedVectorLength += map->size();
	if (newUsedVectorLength > m_vectorLength) {
	increaseVectorLength(newUsedVectorLength);
	storage = m_storage;
	}

	SparseArrayValueMap::iterator end = map->end();
	for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
	storage->m_vector[numDefined++] = it->second;

	delete map;
	storage->m_sparseValueMap = 0;
	}

	for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
	storage->m_vector[i] = jsUndefined();
	for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
	storage->m_vector[i] = 0;

	return numDefined;
	}

	}