1/* 2 * Copyright (C) 1999-2000 Harri Porten (porten@kde.org) 3 * Copyright (C) 2003, 2007, 2008, 2009, 2012 Apple Inc. All rights reserved. 4 * 5 * This library is free software; you can redistribute it and/or 6 * modify it under the terms of the GNU Lesser General Public 7 * License as published by the Free Software Foundation; either 8 * version 2 of the License, or (at your option) any later version. 9 * 10 * This library is distributed in the hope that it will be useful, 11 * but WITHOUT ANY WARRANTY; without even the implied warranty of 12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 13 * Lesser General Public License for more details. 14 * 15 * You should have received a copy of the GNU Lesser General Public 16 * License along with this library; if not, write to the Free Software 17 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 18 * 19 */ 20 21#ifndef ArrayConventions_h 22#define ArrayConventions_h 23 24#include "IndexingHeader.h" 25#include "WriteBarrier.h" 26 27namespace JSC { 28 29// Overview of JSArray 30// 31// Properties of JSArray objects may be stored in one of three locations: 32// * The regular JSObject property map. 33// * A storage vector. 34// * A sparse map of array entries. 35// 36// Properties with non-numeric identifiers, with identifiers that are not representable 37// as an unsigned integer, or where the value is greater than MAX_ARRAY_INDEX 38// (specifically, this is only one property - the value 0xFFFFFFFFU as an unsigned 32-bit 39// integer) are not considered array indices and will be stored in the JSObject property map. 40// 41// All properties with a numeric identifer, representable as an unsigned integer i, 42// where (i <= MAX_ARRAY_INDEX), are an array index and will be stored in either the 43// storage vector or the sparse map. An array index i will be handled in the following 44// fashion: 45// 46// * Where (i < MIN_SPARSE_ARRAY_INDEX) the value will be stored in the storage vector, 47// unless the array is in SparseMode in which case all properties go into the map. 48// * Where (MIN_SPARSE_ARRAY_INDEX <= i <= MAX_STORAGE_VECTOR_INDEX) the value will either 49// be stored in the storage vector or in the sparse array, depending on the density of 50// data that would be stored in the vector (a vector being used where at least 51// (1 / minDensityMultiplier) of the entries would be populated). 52// * Where (MAX_STORAGE_VECTOR_INDEX < i <= MAX_ARRAY_INDEX) the value will always be stored 53// in the sparse array. 54 55// Define the maximum storage vector length to be 2^32 / sizeof(JSValue) / 2 to ensure that 56// there is no risk of overflow. 57#define MAX_STORAGE_VECTOR_LENGTH (static_cast<unsigned>(IndexingHeader::maximumLength)) 58 59// These values have to be macros to be used in max() and min() without introducing 60// a PIC branch in Mach-O binaries, see <rdar://problem/5971391>. 61#define MIN_SPARSE_ARRAY_INDEX 100000U 62#define MAX_STORAGE_VECTOR_INDEX (MAX_STORAGE_VECTOR_LENGTH - 1) 63// 0xFFFFFFFF is a bit weird -- is not an array index even though it's an integer. 64#define MAX_ARRAY_INDEX 0xFFFFFFFEU 65 66// The value BASE_VECTOR_LEN is the maximum number of vector elements we'll allocate 67// for an array that was created with a sepcified length (e.g. a = new Array(123)) 68#define BASE_VECTOR_LEN 4U 69 70// The upper bound to the size we'll grow a zero length array when the first element 71// is added. 72#define FIRST_VECTOR_GROW 4U 73 74#define MIN_BEYOND_LENGTH_SPARSE_INDEX 1000 75 76// Our policy for when to use a vector and when to use a sparse map. 77// For all array indices under MIN_SPARSE_ARRAY_INDEX, we always use a vector. 78// When indices greater than MIN_SPARSE_ARRAY_INDEX are involved, we use a vector 79// as long as it is 1/8 full. If more sparse than that, we use a map. 80static const unsigned minDensityMultiplier = 8; 81 82inline bool isDenseEnoughForVector(unsigned length, unsigned numValues) 83{ 84 return length / minDensityMultiplier <= numValues; 85} 86 87inline bool indexIsSufficientlyBeyondLengthForSparseMap(unsigned i, unsigned length) 88{ 89 return i >= MIN_BEYOND_LENGTH_SPARSE_INDEX && i > length; 90} 91 92inline IndexingHeader indexingHeaderForArray(unsigned length, unsigned vectorLength) 93{ 94 IndexingHeader result; 95 result.setPublicLength(length); 96 result.setVectorLength(vectorLength); 97 return result; 98} 99 100inline IndexingHeader baseIndexingHeaderForArray(unsigned length) 101{ 102 return indexingHeaderForArray(length, BASE_VECTOR_LEN); 103} 104 105} // namespace JSC 106 107#endif // ArrayConventions_h 108 109