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 identifier, 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
62// If you grow an ArrayStorage array by more than this, then the array will go sparse. Note that we
63// could probably make this smaller (it's large because it used to be conflated with
64// MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH).
65#define MIN_SPARSE_ARRAY_INDEX 100000U
66// If you try to allocate a contiguous array larger than this, then we will allocate an ArrayStorage
67// array instead. We allow for an array that occupies 1GB of VM.
68#define MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH 1024 * 1024 * 1024 / 8
69#define MAX_STORAGE_VECTOR_INDEX (MAX_STORAGE_VECTOR_LENGTH - 1)
70// 0xFFFFFFFF is a bit weird -- is not an array index even though it's an integer.
71#define MAX_ARRAY_INDEX 0xFFFFFFFEU
72
73// The value BASE_VECTOR_LEN is the maximum number of vector elements we'll allocate
74// for an array that was created with a sepcified length (e.g. a = new Array(123))
75#define BASE_VECTOR_LEN 4U
76
77// The upper bound to the size we'll grow a zero length array when the first element
78// is added.
79#define FIRST_VECTOR_GROW 4U
80
81#define MIN_BEYOND_LENGTH_SPARSE_INDEX 1000
82
83// Our policy for when to use a vector and when to use a sparse map.
84// For all array indices under MIN_SPARSE_ARRAY_INDEX, we always use a vector.
85// When indices greater than MIN_SPARSE_ARRAY_INDEX are involved, we use a vector
86// as long as it is 1/8 full. If more sparse than that, we use a map.
87static const unsigned minDensityMultiplier = 8;
88
89inline bool isDenseEnoughForVector(unsigned length, unsigned numValues)
90{
91 return length / minDensityMultiplier <= numValues;
92}
93
94inline bool indexIsSufficientlyBeyondLengthForSparseMap(unsigned i, unsigned length)
95{
96 return i >= MIN_BEYOND_LENGTH_SPARSE_INDEX && i > length;
97}
98
99inline IndexingHeader indexingHeaderForArray(unsigned length, unsigned vectorLength)
100{
101 IndexingHeader result;
102 result.setPublicLength(length);
103 result.setVectorLength(vectorLength);
104 return result;
105}
106
107inline IndexingHeader baseIndexingHeaderForArray(unsigned length)
108{
109 return indexingHeaderForArray(length, BASE_VECTOR_LEN);
110}
111
112} // namespace JSC
113
114#endif // ArrayConventions_h
115
116