summaryrefslogtreecommitdiff
path: root/src/mscorlib/src/System/Collections/Generic/List.cs
diff options
context:
space:
mode:
Diffstat (limited to 'src/mscorlib/src/System/Collections/Generic/List.cs')
-rw-r--r--src/mscorlib/src/System/Collections/Generic/List.cs754
1 files changed, 480 insertions, 274 deletions
diff --git a/src/mscorlib/src/System/Collections/Generic/List.cs b/src/mscorlib/src/System/Collections/Generic/List.cs
index 362e26599d..67d1668aad 100644
--- a/src/mscorlib/src/System/Collections/Generic/List.cs
+++ b/src/mscorlib/src/System/Collections/Generic/List.cs
@@ -12,15 +12,15 @@
**
**
===========================================================*/
-namespace System.Collections.Generic {
- using System;
- using System.Runtime;
- using System.Runtime.Versioning;
- using System.Diagnostics;
- using System.Diagnostics.Contracts;
- using System.Collections.ObjectModel;
+using System;
+using System.Diagnostics;
+using System.Diagnostics.Contracts;
+using System.Collections.ObjectModel;
+using System.Runtime.CompilerServices;
+namespace System.Collections.Generic
+{
// Implements a variable-size List that uses an array of objects to store the
// elements. A List has a capacity, which is the allocated length
// of the internal array. As elements are added to a List, the capacity
@@ -40,22 +40,24 @@ namespace System.Collections.Generic {
private int _version;
[NonSerialized]
private Object _syncRoot;
-
- static readonly T[] _emptyArray = new T[0];
-
+
+ private static readonly T[] _emptyArray = new T[0];
+
// Constructs a List. The list is initially empty and has a capacity
// of zero. Upon adding the first element to the list the capacity is
// increased to _defaultCapacity, and then increased in multiples of two
// as required.
- public List() {
+ public List()
+ {
_items = _emptyArray;
}
-
+
// Constructs a List with a given initial capacity. The list is
// initially empty, but will have room for the given number of elements
// before any reallocations are required.
//
- public List(int capacity) {
+ public List(int capacity)
+ {
if (capacity < 0) ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
Contract.EndContractBlock();
@@ -64,116 +66,142 @@ namespace System.Collections.Generic {
else
_items = new T[capacity];
}
-
+
// Constructs a List, copying the contents of the given collection. The
// size and capacity of the new list will both be equal to the size of the
// given collection.
//
- public List(IEnumerable<T> collection) {
- if (collection==null)
+ public List(IEnumerable<T> collection)
+ {
+ if (collection == null)
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);
Contract.EndContractBlock();
ICollection<T> c = collection as ICollection<T>;
- if( c != null) {
+ if (c != null)
+ {
int count = c.Count;
if (count == 0)
{
_items = _emptyArray;
}
- else {
+ else
+ {
_items = new T[count];
c.CopyTo(_items, 0);
_size = count;
}
- }
- else {
+ }
+ else
+ {
_size = 0;
_items = _emptyArray;
AddEnumerable(collection);
}
}
-
+
// Gets and sets the capacity of this list. The capacity is the size of
// the internal array used to hold items. When set, the internal
// array of the list is reallocated to the given capacity.
//
- public int Capacity {
- get {
+ public int Capacity
+ {
+ get
+ {
Contract.Ensures(Contract.Result<int>() >= 0);
return _items.Length;
}
- set {
- if (value < _size) {
+ set
+ {
+ if (value < _size)
+ {
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.value, ExceptionResource.ArgumentOutOfRange_SmallCapacity);
}
Contract.EndContractBlock();
- if (value != _items.Length) {
- if (value > 0) {
+ if (value != _items.Length)
+ {
+ if (value > 0)
+ {
T[] newItems = new T[value];
- if (_size > 0) {
+ if (_size > 0)
+ {
Array.Copy(_items, 0, newItems, 0, _size);
}
_items = newItems;
}
- else {
+ else
+ {
_items = _emptyArray;
}
}
}
}
-
+
// Read-only property describing how many elements are in the List.
- public int Count {
- get {
+ public int Count
+ {
+ get
+ {
Contract.Ensures(Contract.Result<int>() >= 0);
- return _size;
+ return _size;
}
}
- bool System.Collections.IList.IsFixedSize {
+ bool System.Collections.IList.IsFixedSize
+ {
get { return false; }
}
-
+
// Is this List read-only?
- bool ICollection<T>.IsReadOnly {
+ bool ICollection<T>.IsReadOnly
+ {
get { return false; }
}
- bool System.Collections.IList.IsReadOnly {
+ bool System.Collections.IList.IsReadOnly
+ {
get { return false; }
}
// Is this List synchronized (thread-safe)?
- bool System.Collections.ICollection.IsSynchronized {
+ bool System.Collections.ICollection.IsSynchronized
+ {
get { return false; }
}
-
+
// Synchronization root for this object.
- Object System.Collections.ICollection.SyncRoot {
- get {
- if( _syncRoot == null) {
- System.Threading.Interlocked.CompareExchange<Object>(ref _syncRoot, new Object(), null);
+ Object System.Collections.ICollection.SyncRoot
+ {
+ get
+ {
+ if (_syncRoot == null)
+ {
+ System.Threading.Interlocked.CompareExchange<Object>(ref _syncRoot, new Object(), null);
}
return _syncRoot;
}
}
// Sets or Gets the element at the given index.
//
- public T this[int index] {
- get {
+ public T this[int index]
+ {
+ get
+ {
// Following trick can reduce the range check by one
- if ((uint) index >= (uint)_size) {
+ if ((uint)index >= (uint)_size)
+ {
ThrowHelper.ThrowArgumentOutOfRange_IndexException();
}
Contract.EndContractBlock();
- return _items[index];
+ return _items[index];
}
- set {
- if ((uint) index >= (uint)_size) {
+ set
+ {
+ if ((uint)index >= (uint)_size)
+ {
ThrowHelper.ThrowArgumentOutOfRange_IndexException();
}
Contract.EndContractBlock();
@@ -182,24 +210,30 @@ namespace System.Collections.Generic {
}
}
- private static bool IsCompatibleObject(object value) {
+ private static bool IsCompatibleObject(object value)
+ {
// Non-null values are fine. Only accept nulls if T is a class or Nullable<U>.
// Note that default(T) is not equal to null for value types except when T is Nullable<U>.
return ((value is T) || (value == null && default(T) == null));
}
- Object System.Collections.IList.this[int index] {
- get {
+ Object System.Collections.IList.this[int index]
+ {
+ get
+ {
return this[index];
}
- set {
+ set
+ {
ThrowHelper.IfNullAndNullsAreIllegalThenThrow<T>(value, ExceptionArgument.value);
- try {
- this[index] = (T)value;
+ try
+ {
+ this[index] = (T)value;
}
- catch (InvalidCastException) {
- ThrowHelper.ThrowWrongValueTypeArgumentException(value, typeof(T));
+ catch (InvalidCastException)
+ {
+ ThrowHelper.ThrowWrongValueTypeArgumentException(value, typeof(T));
}
}
}
@@ -207,22 +241,44 @@ namespace System.Collections.Generic {
// Adds the given object to the end of this list. The size of the list is
// increased by one. If required, the capacity of the list is doubled
// before adding the new element.
- //
- public void Add(T item) {
- if (_size == _items.Length) EnsureCapacity(_size + 1);
- _items[_size++] = item;
+ [MethodImpl(MethodImplOptions.AggressiveInlining)]
+ public void Add(T item)
+ {
+ var array = _items;
+ var size = _size;
_version++;
+ if ((uint)size < (uint)array.Length)
+ {
+ _size = size + 1;
+ array[size] = item;
+ }
+ else
+ {
+ AddWithResize(item);
+ }
+ }
+
+ // Non-inline from List.Add to improve its code quality as uncommon path
+ [MethodImpl(MethodImplOptions.NoInlining)]
+ private void AddWithResize(T item)
+ {
+ var size = _size;
+ EnsureCapacity(size + 1);
+ _size = size + 1;
+ _items[size] = item;
}
int System.Collections.IList.Add(Object item)
{
ThrowHelper.IfNullAndNullsAreIllegalThenThrow<T>(item, ExceptionArgument.item);
- try {
- Add((T) item);
+ try
+ {
+ Add((T)item);
}
- catch (InvalidCastException) {
- ThrowHelper.ThrowWrongValueTypeArgumentException(item, typeof(T));
+ catch (InvalidCastException)
+ {
+ ThrowHelper.ThrowWrongValueTypeArgumentException(item, typeof(T));
}
return Count - 1;
@@ -233,17 +289,19 @@ namespace System.Collections.Generic {
// required, the capacity of the list is increased to twice the previous
// capacity or the new size, whichever is larger.
//
- public void AddRange(IEnumerable<T> collection) {
+ public void AddRange(IEnumerable<T> collection)
+ {
Contract.Ensures(Count >= Contract.OldValue(Count));
InsertRange(_size, collection);
}
- public ReadOnlyCollection<T> AsReadOnly() {
+ public ReadOnlyCollection<T> AsReadOnly()
+ {
Contract.Ensures(Contract.Result<ReadOnlyCollection<T>>() != null);
return new ReadOnlyCollection<T>(this);
}
-
+
// Searches a section of the list for a given element using a binary search
// algorithm. Elements of the list are compared to the search value using
// the given IComparer interface. If comparer is null, elements of
@@ -264,7 +322,8 @@ namespace System.Collections.Generic {
// The method uses the Array.BinarySearch method to perform the
// search.
//
- public int BinarySearch(int index, int count, T item, IComparer<T> comparer) {
+ public int BinarySearch(int index, int count, T item, IComparer<T> comparer)
+ {
if (index < 0)
ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
if (count < 0)
@@ -276,7 +335,7 @@ namespace System.Collections.Generic {
return Array.BinarySearch<T>(_items, index, count, item, comparer);
}
-
+
public int BinarySearch(T item)
{
Contract.Ensures(Contract.Result<int>() <= Count);
@@ -289,17 +348,27 @@ namespace System.Collections.Generic {
return BinarySearch(0, Count, item, comparer);
}
-
+
// Clears the contents of List.
- public void Clear() {
- if (_size > 0)
+ public void Clear()
+ {
+ if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
{
- Array.Clear(_items, 0, _size); // Don't need to doc this but we clear the elements so that the gc can reclaim the references.
+ int size = _size;
_size = 0;
+ _version++;
+ if (size > 0)
+ {
+ Array.Clear(_items, 0, size); // Clear the elements so that the gc can reclaim the references.
+ }
+ }
+ else
+ {
+ _size = 0;
+ _version++;
}
- _version++;
}
-
+
// Contains returns true if the specified element is in the List.
// It does a linear, O(n) search. Equality is determined by calling
// EqualityComparer<T>.Default.Equals().
@@ -319,21 +388,25 @@ namespace System.Collections.Generic {
bool System.Collections.IList.Contains(Object item)
{
- if(IsCompatibleObject(item)) {
- return Contains((T) item);
+ if (IsCompatibleObject(item))
+ {
+ return Contains((T)item);
}
return false;
}
- public List<TOutput> ConvertAll<TOutput>(Converter<T,TOutput> converter) {
- if( converter == null) {
+ public List<TOutput> ConvertAll<TOutput>(Converter<T, TOutput> converter)
+ {
+ if (converter == null)
+ {
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.converter);
}
Contract.EndContractBlock();
List<TOutput> list = new List<TOutput>(_size);
- for( int i = 0; i< _size; i++) {
+ for (int i = 0; i < _size; i++)
+ {
list._items[i] = converter(_items[i]);
}
list._size = _size;
@@ -343,43 +416,51 @@ namespace System.Collections.Generic {
// Copies this List into array, which must be of a
// compatible array type.
//
- public void CopyTo(T[] array) {
+ public void CopyTo(T[] array)
+ {
CopyTo(array, 0);
}
// Copies this List into array, which must be of a
// compatible array type.
//
- void System.Collections.ICollection.CopyTo(Array array, int arrayIndex) {
- if ((array != null) && (array.Rank != 1)) {
+ void System.Collections.ICollection.CopyTo(Array array, int arrayIndex)
+ {
+ if ((array != null) && (array.Rank != 1))
+ {
ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported);
}
Contract.EndContractBlock();
- try {
+ try
+ {
// Array.Copy will check for NULL.
Array.Copy(_items, 0, array, arrayIndex, _size);
}
- catch(ArrayTypeMismatchException){
+ catch (ArrayTypeMismatchException)
+ {
ThrowHelper.ThrowArgumentException_Argument_InvalidArrayType();
}
}
-
+
// Copies a section of this list to the given array at the given index.
//
// The method uses the Array.Copy method to copy the elements.
//
- public void CopyTo(int index, T[] array, int arrayIndex, int count) {
- if (_size - index < count) {
+ public void CopyTo(int index, T[] array, int arrayIndex, int count)
+ {
+ if (_size - index < count)
+ {
ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
}
Contract.EndContractBlock();
-
+
// Delegate rest of error checking to Array.Copy.
Array.Copy(_items, index, array, arrayIndex, count);
}
- public void CopyTo(T[] array, int arrayIndex) {
+ public void CopyTo(T[] array, int arrayIndex)
+ {
// Delegate rest of error checking to Array.Copy.
Array.Copy(_items, 0, array, arrayIndex, _size);
}
@@ -388,9 +469,11 @@ namespace System.Collections.Generic {
// value. If the current capacity of the list is less than min, the
// capacity is increased to twice the current capacity or to min,
// whichever is larger.
- private void EnsureCapacity(int min) {
- if (_items.Length < min) {
- int newCapacity = _items.Length == 0? _defaultCapacity : _items.Length * 2;
+ private void EnsureCapacity(int min)
+ {
+ if (_items.Length < min)
+ {
+ int newCapacity = _items.Length == 0 ? _defaultCapacity : _items.Length * 2;
// Allow the list to grow to maximum possible capacity (~2G elements) before encountering overflow.
// Note that this check works even when _items.Length overflowed thanks to the (uint) cast
if ((uint)newCapacity > Array.MaxArrayLength) newCapacity = Array.MaxArrayLength;
@@ -398,62 +481,77 @@ namespace System.Collections.Generic {
Capacity = newCapacity;
}
}
-
- public bool Exists(Predicate<T> match) {
+
+ public bool Exists(Predicate<T> match)
+ {
return FindIndex(match) != -1;
}
- public T Find(Predicate<T> match) {
- if( match == null) {
+ public T Find(Predicate<T> match)
+ {
+ if (match == null)
+ {
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
}
Contract.EndContractBlock();
- for(int i = 0 ; i < _size; i++) {
- if(match(_items[i])) {
+ for (int i = 0; i < _size; i++)
+ {
+ if (match(_items[i]))
+ {
return _items[i];
}
}
return default(T);
}
-
- public List<T> FindAll(Predicate<T> match) {
- if( match == null) {
+
+ public List<T> FindAll(Predicate<T> match)
+ {
+ if (match == null)
+ {
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
}
Contract.EndContractBlock();
- List<T> list = new List<T>();
- for(int i = 0 ; i < _size; i++) {
- if(match(_items[i])) {
+ List<T> list = new List<T>();
+ for (int i = 0; i < _size; i++)
+ {
+ if (match(_items[i]))
+ {
list.Add(_items[i]);
}
}
return list;
}
-
- public int FindIndex(Predicate<T> match) {
+
+ public int FindIndex(Predicate<T> match)
+ {
Contract.Ensures(Contract.Result<int>() >= -1);
Contract.Ensures(Contract.Result<int>() < Count);
return FindIndex(0, _size, match);
}
-
- public int FindIndex(int startIndex, Predicate<T> match) {
+
+ public int FindIndex(int startIndex, Predicate<T> match)
+ {
Contract.Ensures(Contract.Result<int>() >= -1);
Contract.Ensures(Contract.Result<int>() < startIndex + Count);
return FindIndex(startIndex, _size - startIndex, match);
}
-
- public int FindIndex(int startIndex, int count, Predicate<T> match) {
- if( (uint)startIndex > (uint)_size ) {
- ThrowHelper.ThrowStartIndexArgumentOutOfRange_ArgumentOutOfRange_Index();
+
+ public int FindIndex(int startIndex, int count, Predicate<T> match)
+ {
+ if ((uint)startIndex > (uint)_size)
+ {
+ ThrowHelper.ThrowStartIndexArgumentOutOfRange_ArgumentOutOfRange_Index();
}
- if (count < 0 || startIndex > _size - count) {
+ if (count < 0 || startIndex > _size - count)
+ {
ThrowHelper.ThrowCountArgumentOutOfRange_ArgumentOutOfRange_Count();
}
- if( match == null) {
+ if (match == null)
+ {
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
}
Contract.Ensures(Contract.Result<int>() >= -1);
@@ -461,83 +559,103 @@ namespace System.Collections.Generic {
Contract.EndContractBlock();
int endIndex = startIndex + count;
- for( int i = startIndex; i < endIndex; i++) {
- if( match(_items[i])) return i;
+ for (int i = startIndex; i < endIndex; i++)
+ {
+ if (match(_items[i])) return i;
}
return -1;
}
-
- public T FindLast(Predicate<T> match) {
- if( match == null) {
+
+ public T FindLast(Predicate<T> match)
+ {
+ if (match == null)
+ {
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
}
Contract.EndContractBlock();
- for(int i = _size - 1 ; i >= 0; i--) {
- if(match(_items[i])) {
+ for (int i = _size - 1; i >= 0; i--)
+ {
+ if (match(_items[i]))
+ {
return _items[i];
}
}
return default(T);
}
- public int FindLastIndex(Predicate<T> match) {
+ public int FindLastIndex(Predicate<T> match)
+ {
Contract.Ensures(Contract.Result<int>() >= -1);
Contract.Ensures(Contract.Result<int>() < Count);
return FindLastIndex(_size - 1, _size, match);
}
-
- public int FindLastIndex(int startIndex, Predicate<T> match) {
+
+ public int FindLastIndex(int startIndex, Predicate<T> match)
+ {
Contract.Ensures(Contract.Result<int>() >= -1);
Contract.Ensures(Contract.Result<int>() <= startIndex);
return FindLastIndex(startIndex, startIndex + 1, match);
}
- public int FindLastIndex(int startIndex, int count, Predicate<T> match) {
- if( match == null) {
+ public int FindLastIndex(int startIndex, int count, Predicate<T> match)
+ {
+ if (match == null)
+ {
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
}
Contract.Ensures(Contract.Result<int>() >= -1);
Contract.Ensures(Contract.Result<int>() <= startIndex);
Contract.EndContractBlock();
- if(_size == 0) {
+ if (_size == 0)
+ {
// Special case for 0 length List
- if( startIndex != -1) {
+ if (startIndex != -1)
+ {
ThrowHelper.ThrowStartIndexArgumentOutOfRange_ArgumentOutOfRange_Index();
}
}
- else {
+ else
+ {
// Make sure we're not out of range
- if ( (uint)startIndex >= (uint)_size) {
+ if ((uint)startIndex >= (uint)_size)
+ {
ThrowHelper.ThrowStartIndexArgumentOutOfRange_ArgumentOutOfRange_Index();
}
}
-
+
// 2nd have of this also catches when startIndex == MAXINT, so MAXINT - 0 + 1 == -1, which is < 0.
- if (count < 0 || startIndex - count + 1 < 0) {
+ if (count < 0 || startIndex - count + 1 < 0)
+ {
ThrowHelper.ThrowCountArgumentOutOfRange_ArgumentOutOfRange_Count();
}
-
+
int endIndex = startIndex - count;
- for( int i = startIndex; i > endIndex; i--) {
- if( match(_items[i])) {
+ for (int i = startIndex; i > endIndex; i--)
+ {
+ if (match(_items[i]))
+ {
return i;
}
}
return -1;
}
- public void ForEach(Action<T> action) {
- if( action == null) {
+ public void ForEach(Action<T> action)
+ {
+ if (action == null)
+ {
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.action);
}
Contract.EndContractBlock();
int version = _version;
- for(int i = 0 ; i < _size; i++) {
- if (version != _version) {
+ for (int i = 0; i < _size; i++)
+ {
+ if (version != _version)
+ {
break;
}
action(_items[i]);
@@ -552,36 +670,42 @@ namespace System.Collections.Generic {
// while an enumeration is in progress, the MoveNext and
// GetObject methods of the enumerator will throw an exception.
//
- public Enumerator GetEnumerator() {
+ public Enumerator GetEnumerator()
+ {
return new Enumerator(this);
}
- /// <internalonly/>
- IEnumerator<T> IEnumerable<T>.GetEnumerator() {
+ IEnumerator<T> IEnumerable<T>.GetEnumerator()
+ {
return new Enumerator(this);
}
- System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
+ System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
+ {
return new Enumerator(this);
}
- public List<T> GetRange(int index, int count) {
- if (index < 0) {
+ public List<T> GetRange(int index, int count)
+ {
+ if (index < 0)
+ {
ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
}
- if (count < 0) {
+ if (count < 0)
+ {
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
}
- if (_size - index < count) {
- ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
+ if (_size - index < count)
+ {
+ ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
}
Contract.Ensures(Contract.Result<List<T>>() != null);
Contract.EndContractBlock();
List<T> list = new List<T>(count);
- Array.Copy(_items, index, list._items, 0, count);
+ Array.Copy(_items, index, list._items, 0, count);
list._size = count;
return list;
}
@@ -595,7 +719,8 @@ namespace System.Collections.Generic {
// This method uses the Array.IndexOf method to perform the
// search.
//
- public int IndexOf(T item) {
+ public int IndexOf(T item)
+ {
Contract.Ensures(Contract.Result<int>() >= -1);
Contract.Ensures(Contract.Result<int>() < Count);
return Array.IndexOf(_items, item, 0, _size);
@@ -603,7 +728,8 @@ namespace System.Collections.Generic {
int System.Collections.IList.IndexOf(Object item)
{
- if(IsCompatibleObject(item)) {
+ if (IsCompatibleObject(item))
+ {
return IndexOf((T)item);
}
return -1;
@@ -618,7 +744,8 @@ namespace System.Collections.Generic {
// This method uses the Array.IndexOf method to perform the
// search.
//
- public int IndexOf(T item, int index) {
+ public int IndexOf(T item, int index)
+ {
if (index > _size)
ThrowHelper.ThrowArgumentOutOfRange_IndexException();
Contract.Ensures(Contract.Result<int>() >= -1);
@@ -636,46 +763,52 @@ namespace System.Collections.Generic {
// This method uses the Array.IndexOf method to perform the
// search.
//
- public int IndexOf(T item, int index, int count) {
+ public int IndexOf(T item, int index, int count)
+ {
if (index > _size)
ThrowHelper.ThrowArgumentOutOfRange_IndexException();
- if (count <0 || index > _size - count) ThrowHelper.ThrowCountArgumentOutOfRange_ArgumentOutOfRange_Count();
+ if (count < 0 || index > _size - count) ThrowHelper.ThrowCountArgumentOutOfRange_ArgumentOutOfRange_Count();
Contract.Ensures(Contract.Result<int>() >= -1);
Contract.Ensures(Contract.Result<int>() < Count);
Contract.EndContractBlock();
return Array.IndexOf(_items, item, index, count);
}
-
+
// Inserts an element into this list at a given index. The size of the list
// is increased by one. If required, the capacity of the list is doubled
// before inserting the new element.
//
- public void Insert(int index, T item) {
+ public void Insert(int index, T item)
+ {
// Note that insertions at the end are legal.
- if ((uint) index > (uint)_size) {
+ if ((uint)index > (uint)_size)
+ {
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_ListInsert);
}
Contract.EndContractBlock();
if (_size == _items.Length) EnsureCapacity(_size + 1);
- if (index < _size) {
+ if (index < _size)
+ {
Array.Copy(_items, index, _items, index + 1, _size - index);
}
_items[index] = item;
- _size++;
+ _size++;
_version++;
}
-
+
void System.Collections.IList.Insert(int index, Object item)
{
ThrowHelper.IfNullAndNullsAreIllegalThenThrow<T>(item, ExceptionArgument.item);
- try {
- Insert(index, (T) item);
+ try
+ {
+ Insert(index, (T)item);
}
- catch (InvalidCastException) {
- ThrowHelper.ThrowWrongValueTypeArgumentException(item, typeof(T));
+ catch (InvalidCastException)
+ {
+ ThrowHelper.ThrowWrongValueTypeArgumentException(item, typeof(T));
}
}
@@ -684,44 +817,55 @@ namespace System.Collections.Generic {
// capacity or the new size, whichever is larger. Ranges may be added
// to the end of the list by setting index to the List's size.
//
- public void InsertRange(int index, IEnumerable<T> collection) {
- if (collection==null) {
+ public void InsertRange(int index, IEnumerable<T> collection)
+ {
+ if (collection == null)
+ {
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);
}
-
- if ((uint)index > (uint)_size) {
+
+ if ((uint)index > (uint)_size)
+ {
ThrowHelper.ThrowArgumentOutOfRange_IndexException();
}
Contract.EndContractBlock();
ICollection<T> c = collection as ICollection<T>;
- if( c != null ) { // if collection is ICollection<T>
+ if (c != null)
+ { // if collection is ICollection<T>
int count = c.Count;
- if (count > 0) {
+ if (count > 0)
+ {
EnsureCapacity(_size + count);
- if (index < _size) {
+ if (index < _size)
+ {
Array.Copy(_items, index, _items, index + count, _size - index);
}
-
+
// If we're inserting a List into itself, we want to be able to deal with that.
- if (this == c) {
+ if (this == c)
+ {
// Copy first part of _items to insert location
Array.Copy(_items, 0, _items, index, index);
// Copy last part of _items back to inserted location
- Array.Copy(_items, index+count, _items, index*2, _size-index);
+ Array.Copy(_items, index + count, _items, index * 2, _size - index);
}
- else {
+ else
+ {
c.CopyTo(_items, index);
}
_size += count;
- }
+ }
}
- else if (index < _size) {
+ else if (index < _size)
+ {
// We're inserting a lazy enumerable. Call Insert on each of the constituent items.
- using(IEnumerator<T> en = collection.GetEnumerator()) {
- while(en.MoveNext()) {
- Insert(index++, en.Current);
- }
+ using (IEnumerator<T> en = collection.GetEnumerator())
+ {
+ while (en.MoveNext())
+ {
+ Insert(index++, en.Current);
+ }
}
}
else
@@ -729,9 +873,9 @@ namespace System.Collections.Generic {
// We're adding a lazy enumerable because the index is at the end of this list.
AddEnumerable(collection);
}
- _version++;
+ _version++;
}
-
+
// Returns the index of the last occurrence of a given value in a range of
// this list. The list is searched backwards, starting at the end
// and ending at the first element in the list. The elements of the list
@@ -744,10 +888,12 @@ namespace System.Collections.Generic {
{
Contract.Ensures(Contract.Result<int>() >= -1);
Contract.Ensures(Contract.Result<int>() < Count);
- if (_size == 0) { // Special case for empty list
+ if (_size == 0)
+ { // Special case for empty list
return -1;
}
- else {
+ else
+ {
return LastIndexOf(item, _size - 1, _size);
}
}
@@ -780,39 +926,47 @@ namespace System.Collections.Generic {
// This method uses the Array.LastIndexOf method to perform the
// search.
//
- public int LastIndexOf(T item, int index, int count) {
- if ((Count != 0) && (index < 0)) {
+ public int LastIndexOf(T item, int index, int count)
+ {
+ if ((Count != 0) && (index < 0))
+ {
ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
}
- if ((Count !=0) && (count < 0)) {
+ if ((Count != 0) && (count < 0))
+ {
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
}
Contract.Ensures(Contract.Result<int>() >= -1);
Contract.Ensures(((Count == 0) && (Contract.Result<int>() == -1)) || ((Count > 0) && (Contract.Result<int>() <= index)));
Contract.EndContractBlock();
- if (_size == 0) { // Special case for empty list
+ if (_size == 0)
+ { // Special case for empty list
return -1;
}
- if (index >= _size) {
+ if (index >= _size)
+ {
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_BiggerThanCollection);
}
- if (count > index + 1) {
+ if (count > index + 1)
+ {
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_BiggerThanCollection);
- }
+ }
return Array.LastIndexOf(_items, item, index, count);
}
-
+
// Removes the element at the given index. The size of the list is
// decreased by one.
//
- public bool Remove(T item) {
+ public bool Remove(T item)
+ {
int index = IndexOf(item);
- if (index >= 0) {
+ if (index >= 0)
+ {
RemoveAt(index);
return true;
}
@@ -822,39 +976,48 @@ namespace System.Collections.Generic {
void System.Collections.IList.Remove(Object item)
{
- if(IsCompatibleObject(item)) {
- Remove((T) item);
+ if (IsCompatibleObject(item))
+ {
+ Remove((T)item);
}
}
// This method removes all items which matches the predicate.
// The complexity is O(n).
- public int RemoveAll(Predicate<T> match) {
- if( match == null) {
+ public int RemoveAll(Predicate<T> match)
+ {
+ if (match == null)
+ {
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
}
Contract.Ensures(Contract.Result<int>() >= 0);
Contract.Ensures(Contract.Result<int>() <= Contract.OldValue(Count));
Contract.EndContractBlock();
-
+
int freeIndex = 0; // the first free slot in items array
// Find the first item which needs to be removed.
- while( freeIndex < _size && !match(_items[freeIndex])) freeIndex++;
- if( freeIndex >= _size) return 0;
-
+ while (freeIndex < _size && !match(_items[freeIndex])) freeIndex++;
+ if (freeIndex >= _size) return 0;
+
int current = freeIndex + 1;
- while( current < _size) {
+ while (current < _size)
+ {
// Find the first item which needs to be kept.
- while( current < _size && match(_items[current])) current++;
+ while (current < _size && match(_items[current])) current++;
- if( current < _size) {
+ if (current < _size)
+ {
// copy item to the free slot.
_items[freeIndex++] = _items[current++];
}
- }
-
- Array.Clear(_items, freeIndex, _size - freeIndex);
+ }
+
+ if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
+ {
+ Array.Clear(_items, freeIndex, _size - freeIndex); // Clear the elements so that the gc can reclaim the references.
+ }
+
int result = _size - freeIndex;
_size = freeIndex;
_version++;
@@ -864,61 +1027,80 @@ namespace System.Collections.Generic {
// Removes the element at the given index. The size of the list is
// decreased by one.
//
- public void RemoveAt(int index) {
- if ((uint)index >= (uint)_size) {
+ public void RemoveAt(int index)
+ {
+ if ((uint)index >= (uint)_size)
+ {
ThrowHelper.ThrowArgumentOutOfRange_IndexException();
}
Contract.EndContractBlock();
_size--;
- if (index < _size) {
+ if (index < _size)
+ {
Array.Copy(_items, index + 1, _items, index, _size - index);
}
- _items[_size] = default(T);
+ if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
+ {
+ _items[_size] = default(T);
+ }
_version++;
}
-
+
// Removes a range of elements from this list.
//
- public void RemoveRange(int index, int count) {
- if (index < 0) {
+ public void RemoveRange(int index, int count)
+ {
+ if (index < 0)
+ {
ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
}
- if (count < 0) {
+ if (count < 0)
+ {
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
}
-
+
if (_size - index < count)
ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
Contract.EndContractBlock();
-
- if (count > 0) {
+
+ if (count > 0)
+ {
int i = _size;
_size -= count;
- if (index < _size) {
+ if (index < _size)
+ {
Array.Copy(_items, index + count, _items, index, _size - index);
}
- Array.Clear(_items, _size, count);
+
_version++;
+ if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
+ {
+ Array.Clear(_items, _size, count);
+ }
}
}
-
+
// Reverses the elements in this list.
- public void Reverse() {
+ public void Reverse()
+ {
Reverse(0, Count);
}
-
+
// Reverses the elements in a range of this list. Following a call to this
// method, an element in the range given by index and count
// which was previously located at index i will now be located at
// index index + (index + count - i - 1).
//
- public void Reverse(int index, int count) {
- if (index < 0) {
+ public void Reverse(int index, int count)
+ {
+ if (index < 0)
+ {
ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
}
-
- if (count < 0) {
+
+ if (count < 0)
+ {
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
}
@@ -926,12 +1108,13 @@ namespace System.Collections.Generic {
ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
Contract.EndContractBlock();
- if (count > 1) {
+ if (count > 1)
+ {
Array.Reverse(_items, index, count);
}
_version++;
}
-
+
// Sorts the elements in this list. Uses the default comparer and
// Array.Sort.
public void Sort()
@@ -954,32 +1137,39 @@ namespace System.Collections.Generic {
//
// This method uses the Array.Sort method to sort the elements.
//
- public void Sort(int index, int count, IComparer<T> comparer) {
- if (index < 0) {
+ public void Sort(int index, int count, IComparer<T> comparer)
+ {
+ if (index < 0)
+ {
ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
}
-
- if (count < 0) {
+
+ if (count < 0)
+ {
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
}
-
+
if (_size - index < count)
ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
Contract.EndContractBlock();
- if (count > 1) {
+ if (count > 1)
+ {
Array.Sort<T>(_items, index, count, comparer);
}
_version++;
}
- public void Sort(Comparison<T> comparison) {
- if( comparison == null) {
+ public void Sort(Comparison<T> comparison)
+ {
+ if (comparison == null)
+ {
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.comparison);
}
Contract.EndContractBlock();
- if (_size > 1) {
+ if (_size > 1)
+ {
ArraySortHelper<T>.Sort(_items, 0, _size, comparison);
}
_version++;
@@ -987,7 +1177,8 @@ namespace System.Collections.Generic {
// ToArray returns an array containing the contents of the List.
// This requires copying the List, which is an O(n) operation.
- public T[] ToArray() {
+ public T[] ToArray()
+ {
Contract.Ensures(Contract.Result<T[]>() != null);
Contract.Ensures(Contract.Result<T[]>().Length == Count);
@@ -1000,7 +1191,7 @@ namespace System.Collections.Generic {
Array.Copy(_items, 0, array, 0, _size);
return array;
}
-
+
// Sets the capacity of this list to the size of the list. This method can
// be used to minimize a list's memory overhead once it is known that no
// new elements will be added to the list. To completely clear a list and
@@ -1010,21 +1201,27 @@ namespace System.Collections.Generic {
// list.Clear();
// list.TrimExcess();
//
- public void TrimExcess() {
- int threshold = (int)(((double)_items.Length) * 0.9);
- if( _size < threshold ) {
- Capacity = _size;
+ public void TrimExcess()
+ {
+ int threshold = (int)(((double)_items.Length) * 0.9);
+ if (_size < threshold)
+ {
+ Capacity = _size;
}
- }
+ }
- public bool TrueForAll(Predicate<T> match) {
- if( match == null) {
+ public bool TrueForAll(Predicate<T> match)
+ {
+ if (match == null)
+ {
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
}
Contract.EndContractBlock();
- for(int i = 0 ; i < _size; i++) {
- if( !match(_items[i])) {
+ for (int i = 0; i < _size; i++)
+ {
+ if (!match(_items[i]))
+ {
return false;
}
}
@@ -1064,23 +1261,25 @@ namespace System.Collections.Generic {
private int version;
private T current;
- internal Enumerator(List<T> list) {
+ internal Enumerator(List<T> list)
+ {
this.list = list;
index = 0;
version = list._version;
current = default(T);
}
- public void Dispose() {
+ public void Dispose()
+ {
}
- public bool MoveNext() {
-
+ public bool MoveNext()
+ {
List<T> localList = list;
- if (version == localList._version && ((uint)index < (uint)localList._size))
- {
- current = localList._items[index];
+ if (version == localList._version && ((uint)index < (uint)localList._size))
+ {
+ current = localList._items[index];
index++;
return true;
}
@@ -1088,40 +1287,47 @@ namespace System.Collections.Generic {
}
private bool MoveNextRare()
- {
- if (version != list._version) {
+ {
+ if (version != list._version)
+ {
ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
}
index = list._size + 1;
current = default(T);
- return false;
+ return false;
}
- public T Current {
- get {
+ public T Current
+ {
+ get
+ {
return current;
}
}
- Object System.Collections.IEnumerator.Current {
- get {
- if( index == 0 || index == list._size + 1) {
- ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen();
+ Object System.Collections.IEnumerator.Current
+ {
+ get
+ {
+ if (index == 0 || index == list._size + 1)
+ {
+ ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen();
}
return Current;
}
}
-
- void System.Collections.IEnumerator.Reset() {
- if (version != list._version) {
+
+ void System.Collections.IEnumerator.Reset()
+ {
+ if (version != list._version)
+ {
ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
}
-
+
index = 0;
current = default(T);
}
-
}
}
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-16 17:40:18 +0000