blob: 876e6df8f2194c18aac2b66815d3991e2c18df9e [file] [log] [blame]
// 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);
}
}