| // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file | |
| // for details. All rights reserved. Use of this source code is governed by a | |
| // BSD-style license that can be found in the LICENSE file. | |
| // part of "core_patch.dart"; | |
| @pragma("vm:entry-point") | |
| class _GrowableList<T> extends ListBase<T> { | |
| void insert(int index, T element) { | |
| if ((index < 0) || (index > length)) { | |
| throw new RangeError.range(index, 0, length); | |
| } | |
| if (index == this.length) { | |
| add(element); | |
| return; | |
| } | |
| int oldLength = this.length; | |
| // We are modifying the length just below the is-check. Without the check | |
| // Array.copy could throw an exception, leaving the list in a bad state | |
| // (with a length that has been increased, but without a new element). | |
| if (index is! int) throw new ArgumentError(index); | |
| this.length++; | |
| Lists.copy(this, index, this, index + 1, oldLength - index); | |
| this[index] = element; | |
| } | |
| T removeAt(int index) { | |
| var result = this[index]; | |
| int newLength = this.length - 1; | |
| if (index < newLength) { | |
| Lists.copy(this, index + 1, this, index, newLength - index); | |
| } | |
| this.length = newLength; | |
| return result; | |
| } | |
| bool remove(Object element) { | |
| for (int i = 0; i < this.length; i++) { | |
| if (this[i] == element) { | |
| removeAt(i); | |
| return true; | |
| } | |
| } | |
| return false; | |
| } | |
| void insertAll(int index, Iterable<T> iterable) { | |
| if (index < 0 || index > length) { | |
| throw new RangeError.range(index, 0, length); | |
| } | |
| // TODO(floitsch): we can probably detect more cases. | |
| if (iterable is! List && iterable is! Set && iterable is! SubListIterable) { | |
| iterable = iterable.toList(); | |
| } | |
| int insertionLength = iterable.length; | |
| // There might be errors after the length change, in which case the list | |
| // will end up being modified but the operation not complete. Unless we | |
| // always go through a "toList" we can't really avoid that. | |
| this.length += insertionLength; | |
| setRange(index + insertionLength, this.length, this, index); | |
| setAll(index, iterable); | |
| } | |
| void setAll(int index, Iterable<T> iterable) { | |
| if (iterable is List) { | |
| setRange(index, index + iterable.length, iterable); | |
| } else { | |
| for (T element in iterable) { | |
| this[index++] = element; | |
| } | |
| } | |
| } | |
| void removeRange(int start, int end) { | |
| RangeError.checkValidRange(start, end, this.length); | |
| Lists.copy(this, end, this, start, this.length - end); | |
| this.length = this.length - (end - start); | |
| } | |
| List<T> sublist(int start, [int end]) { | |
| end = RangeError.checkValidRange(start, end, this.length); | |
| int length = end - start; | |
| if (length == 0) return <T>[]; | |
| List list = new _List(length); | |
| for (int i = 0; i < length; i++) { | |
| list[i] = this[start + i]; | |
| } | |
| var result = new _GrowableList<T>.withData(list); | |
| result._setLength(length); | |
| return result; | |
| } | |
| factory _GrowableList(int length) { | |
| var data = _allocateData(length); | |
| var result = new _GrowableList<T>.withData(data); | |
| if (length > 0) { | |
| result._setLength(length); | |
| } | |
| return result; | |
| } | |
| factory _GrowableList.withCapacity(int capacity) { | |
| var data = _allocateData(capacity); | |
| return new _GrowableList<T>.withData(data); | |
| } | |
| @pragma("vm:exact-result-type", _GrowableList) | |
| factory _GrowableList.withData(_List data) native "GrowableList_allocate"; | |
| @pragma("vm:exact-result-type", "dart:core#_Smi") | |
| int get _capacity native "GrowableList_getCapacity"; | |
| @pragma("vm:exact-result-type", "dart:core#_Smi") | |
| int get length native "GrowableList_getLength"; | |
| void set length(int new_length) { | |
| int old_capacity = _capacity; | |
| int new_capacity = new_length; | |
| if (new_capacity > old_capacity) { | |
| _grow(new_capacity); | |
| _setLength(new_length); | |
| return; | |
| } | |
| // We are shrinking. Pick the method which has fewer writes. | |
| // In the shrink-to-fit path, we write |new_capacity + new_length| words | |
| // (null init + copy). | |
| // In the non-shrink-to-fit path, we write |length - new_length| words | |
| // (null overwrite). | |
| final bool shouldShrinkToFit = | |
| (new_capacity + new_length) < (length - new_length); | |
| if (shouldShrinkToFit) { | |
| _shrink(new_capacity, new_length); | |
| } else { | |
| for (int i = new_length; i < length; i++) { | |
| this[i] = null; | |
| } | |
| } | |
| _setLength(new_length); | |
| } | |
| void _setLength(int new_length) native "GrowableList_setLength"; | |
| void _setData(_List array) native "GrowableList_setData"; | |
| T operator [](int index) native "GrowableList_getIndexed"; | |
| void operator []=(int index, T value) { | |
| _setIndexed(index, value); | |
| } | |
| void _setIndexed(int index, T value) native "GrowableList_setIndexed"; | |
| @pragma("vm:entry-point", "call") | |
| void add(T value) { | |
| var len = length; | |
| if (len == _capacity) { | |
| _grow(_nextCapacity(len)); | |
| } | |
| _setLength(len + 1); | |
| this[len] = value; | |
| } | |
| void addAll(Iterable<T> iterable) { | |
| var len = length; | |
| final cid = ClassID.getID(iterable); | |
| final isVMList = (cid == ClassID.cidArray) || | |
| (cid == ClassID.cidGrowableObjectArray) || | |
| (cid == ClassID.cidImmutableArray); | |
| if (isVMList || (iterable is EfficientLengthIterable)) { | |
| var cap = _capacity; | |
| // Pregrow if we know iterable.length. | |
| var iterLen = iterable.length; | |
| var newLen = len + iterLen; | |
| if (newLen > cap) { | |
| do { | |
| cap = _nextCapacity(cap); | |
| } while (newLen > cap); | |
| _grow(cap); | |
| } | |
| if (isVMList) { | |
| if (identical(iterable, this)) { | |
| throw new ConcurrentModificationError(this); | |
| } | |
| this._setLength(newLen); | |
| final ListBase<T> iterableAsList = iterable; | |
| for (int i = 0; i < iterLen; i++) { | |
| this[len++] = iterableAsList[i]; | |
| } | |
| return; | |
| } | |
| } | |
| Iterator it = iterable.iterator; | |
| if (!it.moveNext()) return; | |
| do { | |
| while (len < _capacity) { | |
| int newLen = len + 1; | |
| this._setLength(newLen); | |
| this[len] = it.current; | |
| if (!it.moveNext()) return; | |
| if (this.length != newLen) throw new ConcurrentModificationError(this); | |
| len = newLen; | |
| } | |
| _grow(_nextCapacity(_capacity)); | |
| } while (true); | |
| } | |
| T removeLast() { | |
| var len = length - 1; | |
| var elem = this[len]; | |
| this.length = len; | |
| return elem; | |
| } | |
| T get first { | |
| if (length > 0) return this[0]; | |
| throw IterableElementError.noElement(); | |
| } | |
| T get last { | |
| if (length > 0) return this[length - 1]; | |
| throw IterableElementError.noElement(); | |
| } | |
| T get single { | |
| if (length == 1) return this[0]; | |
| if (length == 0) throw IterableElementError.noElement(); | |
| throw IterableElementError.tooMany(); | |
| } | |
| // Shared array used as backing for new empty growable arrays. | |
| static final _List _emptyList = new _List(0); | |
| static _List _allocateData(int capacity) { | |
| if (capacity == 0) { | |
| // Use shared empty list as backing. | |
| return _emptyList; | |
| } | |
| // Round up size to the next odd number, since this is free | |
| // because of alignment requirements of the GC. | |
| return new _List(capacity | 1); | |
| } | |
| // Grow from 0 to 3, and then double + 1. | |
| int _nextCapacity(int old_capacity) => (old_capacity * 2) | 3; | |
| void _grow(int new_capacity) { | |
| var newData = _allocateData(new_capacity); | |
| // This is a work-around for dartbug.com/30090: array-bound-check | |
| // generalization causes excessive deoptimizations because it | |
| // hoists CheckArrayBound(i, ...) out of the loop below and turns it | |
| // into CheckArrayBound(length - 1, ...). Which deoptimizes | |
| // if length == 0. However the loop itself does not execute | |
| // if length == 0. | |
| if (length > 0) { | |
| for (int i = 0; i < length; i++) { | |
| newData[i] = this[i]; | |
| } | |
| } | |
| _setData(newData); | |
| } | |
| void _shrink(int new_capacity, int new_length) { | |
| var newData = _allocateData(new_capacity); | |
| // This is a work-around for dartbug.com/30090. See the comment in _grow. | |
| if (new_length > 0) { | |
| for (int i = 0; i < new_length; i++) { | |
| newData[i] = this[i]; | |
| } | |
| } | |
| _setData(newData); | |
| } | |
| // Iterable interface. | |
| void forEach(f(T element)) { | |
| int initialLength = length; | |
| for (int i = 0; i < length; i++) { | |
| f(this[i]); | |
| if (length != initialLength) throw new ConcurrentModificationError(this); | |
| } | |
| } | |
| String join([String separator = ""]) { | |
| final int length = this.length; | |
| if (length == 0) return ""; | |
| if (length == 1) return "${this[0]}"; | |
| if (separator.isNotEmpty) return _joinWithSeparator(separator); | |
| var i = 0; | |
| var codeUnitCount = 0; | |
| while (i < length) { | |
| final element = this[i]; | |
| // While list contains one-byte strings. | |
| if (element is _OneByteString) { | |
| codeUnitCount += element.length; | |
| i++; | |
| // Loop back while strings are one-byte strings. | |
| continue; | |
| } | |
| // Otherwise, never loop back to the outer loop, and | |
| // handle the remaining strings below. | |
| // Loop while elements are strings, | |
| final int firstNonOneByteStringLimit = i; | |
| var nextElement = element; | |
| while (nextElement is String) { | |
| i++; | |
| if (i == length) { | |
| return _StringBase._concatRangeNative(this, 0, length); | |
| } | |
| nextElement = this[i]; | |
| } | |
| // Not all elements are strings, so allocate a new backing array. | |
| final list = new _List(length); | |
| for (int copyIndex = 0; copyIndex < i; copyIndex++) { | |
| list[copyIndex] = this[copyIndex]; | |
| } | |
| // Is non-zero if list contains a non-onebyte string. | |
| var onebyteCanary = i - firstNonOneByteStringLimit; | |
| while (true) { | |
| final String elementString = "$nextElement"; | |
| onebyteCanary |= | |
| (ClassID.getID(elementString) ^ ClassID.cidOneByteString); | |
| list[i] = elementString; | |
| codeUnitCount += elementString.length; | |
| i++; | |
| if (i == length) break; | |
| nextElement = this[i]; | |
| } | |
| if (onebyteCanary == 0) { | |
| // All elements returned a one-byte string from toString. | |
| return _OneByteString._concatAll(list, codeUnitCount); | |
| } | |
| return _StringBase._concatRangeNative(list, 0, length); | |
| } | |
| // All elements were one-byte strings. | |
| return _OneByteString._concatAll(this, codeUnitCount); | |
| } | |
| String _joinWithSeparator(String separator) { | |
| StringBuffer buffer = new StringBuffer(); | |
| buffer.write(this[0]); | |
| for (int i = 1; i < this.length; i++) { | |
| buffer.write(separator); | |
| buffer.write(this[i]); | |
| } | |
| return buffer.toString(); | |
| } | |
| T elementAt(int index) { | |
| return this[index]; | |
| } | |
| bool get isEmpty { | |
| return this.length == 0; | |
| } | |
| bool get isNotEmpty => !isEmpty; | |
| void clear() { | |
| this.length = 0; | |
| } | |
| String toString() => ListBase.listToString(this); | |
| Iterator<T> get iterator { | |
| return new ListIterator<T>(this); | |
| } | |
| List<T> toList({bool growable: true}) { | |
| var length = this.length; | |
| if (length > 0) { | |
| List list = growable ? new _List(length) : new _List<T>(length); | |
| for (int i = 0; i < length; i++) { | |
| list[i] = this[i]; | |
| } | |
| if (!growable) return list; | |
| var result = new _GrowableList<T>.withData(list); | |
| result._setLength(length); | |
| return result; | |
| } | |
| return growable ? <T>[] : new List<T>(0); | |
| } | |
| Set<T> toSet() { | |
| return new Set<T>.from(this); | |
| } | |
| } |