OLD | NEW |
1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 class _GrowableList<T> extends ListBase<T> { | 5 class _GrowableList<T> extends ListBase<T> { |
6 void insert(int index, T element) { | 6 void insert(int index, T element) { |
7 if ((index < 0) || (index > length)) { | 7 if ((index < 0) || (index > length)) { |
8 throw new RangeError.range(index, 0, length); | 8 throw new RangeError.range(index, 0, length); |
9 } | 9 } |
10 if (index == this.length) { | 10 if (index == this.length) { |
(...skipping 69 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
80 if (length == 0) return <T>[]; | 80 if (length == 0) return <T>[]; |
81 List list = new _List(length); | 81 List list = new _List(length); |
82 for (int i = 0; i < length; i++) { | 82 for (int i = 0; i < length; i++) { |
83 list[i] = this[start + i]; | 83 list[i] = this[start + i]; |
84 } | 84 } |
85 var result = new _GrowableList<T>.withData(list); | 85 var result = new _GrowableList<T>.withData(list); |
86 result._setLength(length); | 86 result._setLength(length); |
87 return result; | 87 return result; |
88 } | 88 } |
89 | 89 |
| 90 static const int _kDefaultCapacity = 2; |
| 91 |
90 factory _GrowableList(int length) { | 92 factory _GrowableList(int length) { |
91 var data = _allocateData(length); | 93 var data = new _List((length == 0) ? _kDefaultCapacity : length); |
92 var result = new _GrowableList<T>.withData(data); | 94 var result = new _GrowableList<T>.withData(data); |
93 if (length > 0) { | 95 if (length > 0) { |
94 result._setLength(length); | 96 result._setLength(length); |
95 } | 97 } |
96 return result; | 98 return result; |
97 } | 99 } |
98 | 100 |
99 factory _GrowableList.withCapacity(int capacity) { | 101 factory _GrowableList.withCapacity(int capacity) { |
100 var data = _allocateData(capacity); | 102 var data = new _List((capacity == 0) ? _kDefaultCapacity : capacity); |
101 return new _GrowableList<T>.withData(data); | 103 return new _GrowableList<T>.withData(data); |
102 } | 104 } |
103 | 105 |
104 factory _GrowableList.withData(_List data) native "GrowableList_allocate"; | 106 factory _GrowableList.withData(_List data) native "GrowableList_allocate"; |
105 | 107 |
106 int get _capacity native "GrowableList_getCapacity"; | 108 int get _capacity native "GrowableList_getCapacity"; |
107 | 109 |
108 int get length native "GrowableList_getLength"; | 110 int get length native "GrowableList_getLength"; |
109 | 111 |
110 void set length(int new_length) { | 112 void set length(int new_length) { |
111 int old_capacity = _capacity; | 113 int old_capacity = _capacity; |
112 int new_capacity = new_length; | 114 int new_capacity = new_length; |
| 115 if (new_length == 0) { |
| 116 // Ensure that we use _kDefaultCapacity only when the old_capacity |
| 117 // is greater than _kDefaultCapacity otherwise we end up growing the |
| 118 // the array. |
| 119 if (old_capacity < _kDefaultCapacity) { |
| 120 new_capacity = old_capacity; |
| 121 } else { |
| 122 new_capacity = _kDefaultCapacity; |
| 123 } |
| 124 } |
113 if (new_capacity > old_capacity) { | 125 if (new_capacity > old_capacity) { |
114 _grow(new_capacity); | 126 _grow(new_capacity); |
115 _setLength(new_length); | 127 _setLength(new_length); |
116 return; | 128 return; |
117 } | 129 } |
118 // We are shrinking. Pick the method which has fewer writes. | 130 // We are shrinking. Pick the method which has fewer writes. |
119 // In the shrink-to-fit path, we write |new_capacity + new_length| words | 131 // In the shrink-to-fit path, we write |new_capacity + new_length| words |
120 // (null init + copy). | 132 // (null init + copy). |
121 // In the non-shrink-to-fit path, we write |length - new_length| words | 133 // In the non-shrink-to-fit path, we write |length - new_length| words |
122 // (null overwrite). | 134 // (null overwrite). |
(...skipping 10 matching lines...) Expand all Loading... |
133 } | 145 } |
134 | 146 |
135 void _setLength(int new_length) native "GrowableList_setLength"; | 147 void _setLength(int new_length) native "GrowableList_setLength"; |
136 | 148 |
137 void _setData(_List array) native "GrowableList_setData"; | 149 void _setData(_List array) native "GrowableList_setData"; |
138 | 150 |
139 T operator [](int index) native "GrowableList_getIndexed"; | 151 T operator [](int index) native "GrowableList_getIndexed"; |
140 | 152 |
141 void operator []=(int index, T value) native "GrowableList_setIndexed"; | 153 void operator []=(int index, T value) native "GrowableList_setIndexed"; |
142 | 154 |
| 155 // The length of this growable array. It is always less than or equal to the |
| 156 // length of the object array, which itself is always greater than 0, so that |
| 157 // grow() does not have to check for a zero length object array before |
| 158 // doubling its size. |
143 void add(T value) { | 159 void add(T value) { |
144 var len = length; | 160 var len = length; |
145 if (len == _capacity) { | 161 if (len == _capacity) { |
146 _grow(_nextCapacity(len)); | 162 _grow(len * 2); |
147 } | 163 } |
148 _setLength(len + 1); | 164 _setLength(len + 1); |
149 this[len] = value; | 165 this[len] = value; |
150 } | 166 } |
151 | 167 |
152 void addAll(Iterable<T> iterable) { | 168 void addAll(Iterable<T> iterable) { |
153 var len = length; | 169 var len = length; |
154 final cid = ClassID.getID(iterable); | 170 final cid = ClassID.getID(iterable); |
155 final isVMList = (cid == ClassID.cidArray) || | 171 final isVMList = (cid == ClassID.cidArray) || |
156 (cid == ClassID.cidGrowableObjectArray) || | 172 (cid == ClassID.cidGrowableObjectArray) || |
157 (cid == ClassID.cidImmutableArray); | 173 (cid == ClassID.cidImmutableArray); |
158 if (isVMList || (iterable is EfficientLengthIterable)) { | 174 if (isVMList || (iterable is EfficientLengthIterable)) { |
159 var cap = _capacity; | 175 var cap = _capacity; |
160 // Pregrow if we know iterable.length. | 176 // Pregrow if we know iterable.length. |
161 var iterLen = iterable.length; | 177 var iterLen = iterable.length; |
162 var newLen = len + iterLen; | 178 var newLen = len + iterLen; |
163 if (newLen > cap) { | 179 if (newLen > cap) { |
164 do { | 180 do { |
165 cap = _nextCapacity(cap); | 181 cap *= 2; |
166 } while (newLen > cap); | 182 } while (newLen > cap); |
167 _grow(cap); | 183 _grow(cap); |
168 } | 184 } |
169 if (isVMList) { | 185 if (isVMList) { |
170 if (identical(iterable, this)) { | 186 if (identical(iterable, this)) { |
171 throw new ConcurrentModificationError(this); | 187 throw new ConcurrentModificationError(this); |
172 } | 188 } |
173 this._setLength(newLen); | 189 this._setLength(newLen); |
174 for (int i = 0; i < iterLen; i++) { | 190 for (int i = 0; i < iterLen; i++) { |
175 this[len++] = iterable[i]; | 191 this[len++] = iterable[i]; |
176 } | 192 } |
177 return; | 193 return; |
178 } | 194 } |
179 } | 195 } |
180 Iterator it = iterable.iterator; | 196 Iterator it = iterable.iterator; |
181 if (!it.moveNext()) return; | 197 if (!it.moveNext()) return; |
182 do { | 198 do { |
183 while (len < _capacity) { | 199 while (len < _capacity) { |
184 int newLen = len + 1; | 200 int newLen = len + 1; |
185 this._setLength(newLen); | 201 this._setLength(newLen); |
186 this[len] = it.current; | 202 this[len] = it.current; |
187 if (!it.moveNext()) return; | 203 if (!it.moveNext()) return; |
188 if (this.length != newLen) throw new ConcurrentModificationError(this); | 204 if (this.length != newLen) throw new ConcurrentModificationError(this); |
189 len = newLen; | 205 len = newLen; |
190 } | 206 } |
191 _grow(_nextCapacity(_capacity)); | 207 _grow(_capacity * 2); |
192 } while (true); | 208 } while (true); |
193 } | 209 } |
194 | 210 |
195 T removeLast() { | 211 T removeLast() { |
196 var len = length - 1; | 212 var len = length - 1; |
197 var elem = this[len]; | 213 var elem = this[len]; |
198 this.length = len; | 214 this.length = len; |
199 return elem; | 215 return elem; |
200 } | 216 } |
201 | 217 |
202 T get first { | 218 T get first { |
203 if (length > 0) return this[0]; | 219 if (length > 0) return this[0]; |
204 throw IterableElementError.noElement(); | 220 throw IterableElementError.noElement(); |
205 } | 221 } |
206 | 222 |
207 T get last { | 223 T get last { |
208 if (length > 0) return this[length - 1]; | 224 if (length > 0) return this[length - 1]; |
209 throw IterableElementError.noElement(); | 225 throw IterableElementError.noElement(); |
210 } | 226 } |
211 | 227 |
212 T get single { | 228 T get single { |
213 if (length == 1) return this[0]; | 229 if (length == 1) return this[0]; |
214 if (length == 0) throw IterableElementError.noElement(); | 230 if (length == 0) throw IterableElementError.noElement(); |
215 throw IterableElementError.tooMany(); | 231 throw IterableElementError.tooMany(); |
216 ; | 232 ; |
217 } | 233 } |
218 | 234 |
219 // Shared array used as backing for new empty growable arrays. | 235 void _grow(int new_capacity) { |
220 static final _List _emptyList = new _List(0); | 236 var new_data = new _List(new_capacity); |
221 | 237 for (int i = 0; i < length; i++) { |
222 static _List _allocateData(int capacity) { | 238 new_data[i] = this[i]; |
223 if (capacity == 0) { | |
224 // Use shared empty list as backing. | |
225 return _emptyList; | |
226 } | 239 } |
227 // Round up size to the next odd number, since this is free | 240 _setData(new_data); |
228 // because of alignment requirements of the GC. | |
229 return new _List(capacity | 1); | |
230 } | |
231 | |
232 // Grow from 0 to 3, and then double + 1. | |
233 int _nextCapacity(int old_capacity) => (old_capacity * 2) | 3; | |
234 | |
235 void _grow(int new_capacity) { | |
236 var newData = _allocateData(new_capacity); | |
237 for (int i = 0; i < length; i++) { | |
238 newData[i] = this[i]; | |
239 } | |
240 _setData(newData); | |
241 } | 241 } |
242 | 242 |
243 void _shrink(int new_capacity, int new_length) { | 243 void _shrink(int new_capacity, int new_length) { |
244 var newData = _allocateData(new_capacity); | 244 var new_data = new _List(new_capacity); |
245 for (int i = 0; i < new_length; i++) { | 245 for (int i = 0; i < new_length; i++) { |
246 newData[i] = this[i]; | 246 new_data[i] = this[i]; |
247 } | 247 } |
248 _setData(newData); | 248 _setData(new_data); |
249 } | 249 } |
250 | 250 |
251 // Iterable interface. | 251 // Iterable interface. |
252 | 252 |
253 void forEach(f(T element)) { | 253 void forEach(f(T element)) { |
254 int initialLength = length; | 254 int initialLength = length; |
255 for (int i = 0; i < length; i++) { | 255 for (int i = 0; i < length; i++) { |
256 f(this[i]); | 256 f(this[i]); |
257 if (length != initialLength) throw new ConcurrentModificationError(this); | 257 if (length != initialLength) throw new ConcurrentModificationError(this); |
258 } | 258 } |
(...skipping 99 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
358 result._setLength(length); | 358 result._setLength(length); |
359 return result; | 359 return result; |
360 } | 360 } |
361 return growable ? <T>[] : new List<T>(0); | 361 return growable ? <T>[] : new List<T>(0); |
362 } | 362 } |
363 | 363 |
364 Set<T> toSet() { | 364 Set<T> toSet() { |
365 return new Set<T>.from(this); | 365 return new Set<T>.from(this); |
366 } | 366 } |
367 } | 367 } |
OLD | NEW |