- ArrayStorage* storage = m_storage;
- SparseArrayValueMap* map = m_sparseValueMap;
-
- // First, handle cases where we don't currently have a sparse map.
- if (LIKELY(!map)) {
- // If the array is not extensible, we should have entered dictionary mode, and created the spare map.
- ASSERT(isExtensible());
-
- // Update m_length if necessary.
- if (i >= storage->m_length)
- storage->m_length = i + 1;
-
- // Check that it is sensible to still be using a vector, and then try to grow the vector.
- if (LIKELY((isDenseEnoughForVector(i, storage->m_numValuesInVector)) && increaseVectorLength(globalData, i + 1))) {
- // success! - reread m_storage since it has likely been reallocated, and store to the vector.
- storage = m_storage;
- storage->m_vector[i].set(globalData, this, value);
- ++storage->m_numValuesInVector;
- return true;
- }
- // We don't want to, or can't use a vector to hold this property - allocate a sparse map & add the value.
- allocateSparseMap(exec->globalData());
- map = m_sparseValueMap;
- return map->putDirect(exec, this, i, value, shouldThrow);
- }
-
- // Update m_length if necessary.
- unsigned length = storage->m_length;
- if (i >= length) {
- // Prohibit growing the array if length is not writable.
- if (map->lengthIsReadOnly())
- return reject(exec, shouldThrow, StrictModeReadonlyPropertyWriteError);
- if (!isExtensible())
- return reject(exec, shouldThrow, "Attempting to define property on object that is not extensible.");
- length = i + 1;
- storage->m_length = length;
- }
-
- // We are currently using a map - check whether we still want to be doing so.
- // We will continue to use a sparse map if SparseMode is set, a vector would be too sparse, or if allocation fails.
- unsigned numValuesInArray = storage->m_numValuesInVector + map->size();
- if (map->sparseMode() || !isDenseEnoughForVector(length, numValuesInArray) || !increaseVectorLength(exec->globalData(), length))
- return map->putDirect(exec, this, i, value, shouldThrow);
-
- // Reread m_storage afterincreaseVectorLength, update m_numValuesInVector.
- storage = m_storage;
- storage->m_numValuesInVector = numValuesInArray;
-
- // Copy all values from the map into the vector, and delete the map.
- WriteBarrier<Unknown>* vector = storage->m_vector;
- SparseArrayValueMap::const_iterator end = map->end();
- for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it)
- vector[it->first].set(globalData, this, it->second.getNonSparseMode());
- deallocateSparseMap();
-
- // Store the new property into the vector.
- WriteBarrier<Unknown>& valueSlot = vector[i];
- if (!valueSlot)
- ++storage->m_numValuesInVector;
- valueSlot.set(globalData, this, value);
- return true;
-}
-
-bool JSArray::deleteProperty(JSCell* cell, ExecState* exec, const Identifier& propertyName)
-{
- JSArray* thisObject = jsCast<JSArray*>(cell);
- bool isArrayIndex;
- unsigned i = propertyName.toArrayIndex(isArrayIndex);
- if (isArrayIndex)
- return thisObject->methodTable()->deletePropertyByIndex(thisObject, exec, i);
-
- if (propertyName == exec->propertyNames().length)
- return false;
-
- return JSObject::deleteProperty(thisObject, exec, propertyName);
-}
-
-bool JSArray::deletePropertyByIndex(JSCell* cell, ExecState* exec, unsigned i)
-{
- JSArray* thisObject = jsCast<JSArray*>(cell);
- thisObject->checkConsistency();
-
- if (i > MAX_ARRAY_INDEX)
- return thisObject->methodTable()->deleteProperty(thisObject, exec, Identifier::from(exec, i));
-
- ArrayStorage* storage = thisObject->m_storage;
-
- if (i < thisObject->m_vectorLength) {
- WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
- if (valueSlot) {
- valueSlot.clear();
- --storage->m_numValuesInVector;
- }
- } else if (SparseArrayValueMap* map = thisObject->m_sparseValueMap) {
- SparseArrayValueMap::iterator it = map->find(i);
- if (it != map->notFound()) {
- if (it->second.attributes & DontDelete)
- return false;
- map->remove(it);
- }
- }
-
- thisObject->checkConsistency();
- return true;
-}
-
-static int compareKeysForQSort(const void* a, const void* b)
-{
- unsigned da = *static_cast<const unsigned*>(a);
- unsigned db = *static_cast<const unsigned*>(b);
- return (da > db) - (da < db);
-}
-
-void JSArray::getOwnPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
-{
- JSArray* thisObject = jsCast<JSArray*>(object);
- // FIXME: Filling PropertyNameArray with an identifier for every integer
- // is incredibly inefficient for large arrays. We need a different approach,
- // which almost certainly means a different structure for PropertyNameArray.
-
- ArrayStorage* storage = thisObject->m_storage;
-
- unsigned usedVectorLength = min(storage->m_length, thisObject->m_vectorLength);
- for (unsigned i = 0; i < usedVectorLength; ++i) {
- if (storage->m_vector[i])
- propertyNames.add(Identifier::from(exec, i));
- }
-
- if (SparseArrayValueMap* map = thisObject->m_sparseValueMap) {
- Vector<unsigned> keys;
- keys.reserveCapacity(map->size());
-
- SparseArrayValueMap::const_iterator end = map->end();
- for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it) {
- if (mode == IncludeDontEnumProperties || !(it->second.attributes & DontEnum))
- keys.append(static_cast<unsigned>(it->first));
- }
-
- qsort(keys.begin(), keys.size(), sizeof(unsigned), compareKeysForQSort);
- for (unsigned i = 0; i < keys.size(); ++i)
- propertyNames.add(Identifier::from(exec, keys[i]));
- }
-
- if (mode == IncludeDontEnumProperties)
- propertyNames.add(exec->propertyNames().length);
-
- JSObject::getOwnPropertyNames(thisObject, exec, propertyNames, mode);
-}
-
-ALWAYS_INLINE unsigned JSArray::getNewVectorLength(unsigned desiredLength)
-{
- ASSERT(desiredLength <= MAX_STORAGE_VECTOR_LENGTH);
-
- unsigned increasedLength;
- unsigned maxInitLength = min(m_storage->m_length, 100000U);
-
- if (desiredLength < maxInitLength)
- increasedLength = maxInitLength;
- else if (!m_vectorLength)
- increasedLength = max(desiredLength, lastArraySize);
- else {
- // Mathematically equivalent to:
- // increasedLength = (newLength * 3 + 1) / 2;
- // or:
- // increasedLength = (unsigned)ceil(newLength * 1.5));
- // This form is not prone to internal overflow.
- increasedLength = desiredLength + (desiredLength >> 1) + (desiredLength & 1);
- }
-
- ASSERT(increasedLength >= desiredLength);
-
- lastArraySize = min(increasedLength, FIRST_VECTOR_GROW);
-
- return min(increasedLength, MAX_STORAGE_VECTOR_LENGTH);
-}
-
-bool JSArray::increaseVectorLength(JSGlobalData& globalData, 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.
- if (newLength > MAX_STORAGE_VECTOR_LENGTH)
- return false;
-
- ArrayStorage* storage = m_storage;
-
- unsigned vectorLength = m_vectorLength;
- ASSERT(newLength > vectorLength);
- unsigned newVectorLength = getNewVectorLength(newLength);
-
- // Fast case - there is no precapacity. In these cases a realloc makes sense.
- if (LIKELY(!m_indexBias)) {
- void* newStorage = storage->m_allocBase;
- if (!globalData.heap.tryReallocateStorage(&newStorage, storageSize(vectorLength), storageSize(newVectorLength)))
- return false;
-
- storage = m_storage = reinterpret_cast_ptr<ArrayStorage*>(static_cast<char*>(newStorage));
- m_storage->m_allocBase = newStorage;
- ASSERT(m_storage->m_allocBase);
-
- m_vectorLength = newVectorLength;
-
- return true;
- }
-
- // Remove some, but not all of the precapacity. Atomic decay, & capped to not overflow array length.
- unsigned newIndexBias = min(m_indexBias >> 1, MAX_STORAGE_VECTOR_LENGTH - newVectorLength);
- // Calculate new stoarge capcity, allowing room for the pre-capacity.
- unsigned newStorageCapacity = newVectorLength + newIndexBias;
- void* newAllocBase = 0;
- if (!globalData.heap.tryAllocateStorage(storageSize(newStorageCapacity), &newAllocBase))
- return false;
- // The sum of m_vectorLength and m_indexBias will never exceed MAX_STORAGE_VECTOR_LENGTH.
- ASSERT(m_vectorLength <= MAX_STORAGE_VECTOR_LENGTH && (MAX_STORAGE_VECTOR_LENGTH - m_vectorLength) >= m_indexBias);
-
- m_vectorLength = newVectorLength;
- m_indexBias = newIndexBias;
- m_storage = reinterpret_cast_ptr<ArrayStorage*>(reinterpret_cast<WriteBarrier<Unknown>*>(newAllocBase) + m_indexBias);
-
- // Copy the ArrayStorage header & current contents of the vector.
- memmove(m_storage, storage, storageSize(vectorLength));
-
- // Free the old allocation, update m_allocBase.
- m_storage->m_allocBase = newAllocBase;
-
- return true;
-}
-
-// This method makes room in the vector, but leaves the new space uncleared.
-bool JSArray::unshiftCountSlowCase(JSGlobalData& globalData, unsigned count)
-{
- // If not, we should have handled this on the fast path.
- ASSERT(count > m_indexBias);
-
- ArrayStorage* storage = m_storage;
-
- // Step 1:
- // Gather 4 key metrics:
- // * usedVectorLength - how many entries are currently in the vector (conservative estimate - fewer may be in use in sparse vectors).
- // * requiredVectorLength - how many entries are will there be in the vector, after allocating space for 'count' more.
- // * currentCapacity - what is the current size of the vector, including any pre-capacity.
- // * desiredCapacity - how large should we like to grow the vector to - based on 2x requiredVectorLength.
-
- unsigned length = storage->m_length;
- unsigned usedVectorLength = min(m_vectorLength, length);
- ASSERT(usedVectorLength <= MAX_STORAGE_VECTOR_LENGTH);
- // Check that required vector length is possible, in an overflow-safe fashion.
- if (count > MAX_STORAGE_VECTOR_LENGTH - usedVectorLength)
- return false;
- unsigned requiredVectorLength = usedVectorLength + count;
- ASSERT(requiredVectorLength <= MAX_STORAGE_VECTOR_LENGTH);
- // The sum of m_vectorLength and m_indexBias will never exceed MAX_STORAGE_VECTOR_LENGTH.
- ASSERT(m_vectorLength <= MAX_STORAGE_VECTOR_LENGTH && (MAX_STORAGE_VECTOR_LENGTH - m_vectorLength) >= m_indexBias);
- unsigned currentCapacity = m_vectorLength + m_indexBias;
- // The calculation of desiredCapacity won't overflow, due to the range of MAX_STORAGE_VECTOR_LENGTH.
- unsigned desiredCapacity = min(MAX_STORAGE_VECTOR_LENGTH, max(BASE_VECTOR_LEN, requiredVectorLength) << 1);
-
- // Step 2:
- // We're either going to choose to allocate a new ArrayStorage, or we're going to reuse the existing on.
-
- void* newAllocBase = 0;
- unsigned newStorageCapacity;
- // If the current storage array is sufficiently large (but not too large!) then just keep using it.
- if (currentCapacity > desiredCapacity && isDenseEnoughForVector(currentCapacity, requiredVectorLength)) {
- newAllocBase = storage->m_allocBase;
- newStorageCapacity = currentCapacity;
- } else {
- if (!globalData.heap.tryAllocateStorage(storageSize(desiredCapacity), &newAllocBase))
- return false;
- newStorageCapacity = desiredCapacity;
- }
-
- // Step 3:
- // Work out where we're going to move things to.
-
- // Determine how much of the vector to use as pre-capacity, and how much as post-capacity.
- // If the vector had no free post-capacity (length >= m_vectorLength), don't give it any.
- // If it did, we calculate the amount that will remain based on an atomic decay - leave the
- // vector with half the post-capacity it had previously.
- unsigned postCapacity = 0;
- if (length < m_vectorLength) {
- // Atomic decay, + the post-capacity cannot be greater than what is available.
- postCapacity = min((m_vectorLength - length) >> 1, newStorageCapacity - requiredVectorLength);
- // If we're moving contents within the same allocation, the post-capacity is being reduced.
- ASSERT(newAllocBase != storage->m_allocBase || postCapacity < m_vectorLength - length);
- }
-
- m_vectorLength = requiredVectorLength + postCapacity;
- m_indexBias = newStorageCapacity - m_vectorLength;
- m_storage = reinterpret_cast_ptr<ArrayStorage*>(reinterpret_cast<WriteBarrier<Unknown>*>(newAllocBase) + m_indexBias);
-
- // Step 4:
- // Copy array data / header into their new locations, clear post-capacity & free any old allocation.
-
- // If this is being moved within the existing buffer of memory, we are always shifting data
- // to the right (since count > m_indexBias). As such this memmove cannot trample the header.
- memmove(m_storage->m_vector + count, storage->m_vector, sizeof(WriteBarrier<Unknown>) * usedVectorLength);
- memmove(m_storage, storage, storageSize(0));
-
- // Are we copying into a new allocation?
- if (newAllocBase != m_storage->m_allocBase) {
- // Free the old allocation, update m_allocBase.
- m_storage->m_allocBase = newAllocBase;
- }
-
- return true;
-}
-
-bool JSArray::setLength(ExecState* exec, unsigned newLength, bool throwException)
-{
- checkConsistency();
-
- ArrayStorage* storage = m_storage;
- unsigned length = storage->m_length;
-
- // If the length is read only then we enter sparse mode, so should enter the following 'if'.
- ASSERT(isLengthWritable() || m_sparseValueMap);
-
- if (SparseArrayValueMap* map = m_sparseValueMap) {
- // Fail if the length is not writable.
- if (map->lengthIsReadOnly())
- return reject(exec, throwException, StrictModeReadonlyPropertyWriteError);
projects / apple / javascriptcore.git / blobdiff