diff options
Diffstat (limited to 'src/mscorlib/src/System/Collections/Generic/List.cs')
-rw-r--r-- | src/mscorlib/src/System/Collections/Generic/List.cs | 754 |
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); } - } } } |