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 | |

27 | namespace 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. |

87 | static const unsigned minDensityMultiplier = 8; |

88 | |

89 | inline bool isDenseEnoughForVector(unsigned length, unsigned numValues) |

90 | { |

91 | return length / minDensityMultiplier <= numValues; |

92 | } |

93 | |

94 | inline bool indexIsSufficientlyBeyondLengthForSparseMap(unsigned i, unsigned length) |

95 | { |

96 | return i >= MIN_BEYOND_LENGTH_SPARSE_INDEX && i > length; |

97 | } |

98 | |

99 | inline IndexingHeader indexingHeaderForArray(unsigned length, unsigned vectorLength) |

100 | { |

101 | IndexingHeader result; |

102 | result.setPublicLength(length); |

103 | result.setVectorLength(vectorLength); |

104 | return result; |

105 | } |

106 | |

107 | inline IndexingHeader baseIndexingHeaderForArray(unsigned length) |

108 | { |

109 | return indexingHeaderForArray(length, BASE_VECTOR_LEN); |

110 | } |

111 | |

112 | } // namespace JSC |

113 | |

114 | #endif // ArrayConventions_h |

115 | |

116 |