// Martin Baulig (martin@ximian.com)
// Carlos Alberto Cortez (calberto.cortez@gmail.com)
// David Waite (mass@akuma.org)
+// Marek Safar (marek.safar@gmail.com)
//
// Copyright (C) 2004-2005 Novell, Inc (http://www.novell.com)
// Copyright (C) 2005 David Waite
+// Copyright (C) 2011,2012 Xamarin, Inc (http://www.xamarin.com)
//
// Permission is hereby granted, free of charge, to any person obtaining
// a copy of this software and associated documentation files (the
// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
//
-#if NET_2_0
-
using System.Collections.ObjectModel;
using System.Runtime.InteropServices;
+using System.Diagnostics;
+using System.Runtime.CompilerServices;
namespace System.Collections.Generic {
[Serializable]
- public class List <T> : IList <T>, IList, ICollection {
- T [] data;
- int size;
- int version;
+ [DebuggerDisplay ("Count={Count}")]
+ [DebuggerTypeProxy (typeof (CollectionDebuggerView<>))]
+ public class List<T> : IList<T>, IList
+#if NET_4_5
+ , IReadOnlyList<T>
+#endif
+ {
+ T [] _items;
+ int _size;
+ int _version;
- static readonly T [] EmptyArray = new T [0];
const int DefaultCapacity = 4;
public List ()
{
- data = EmptyArray;
+ _items = EmptyArray<T>.Value;
}
public List (IEnumerable <T> collection)
{
- CheckCollection (collection);
+ if (collection == null)
+ throw new ArgumentNullException ("collection");
// initialize to needed size (if determinable)
ICollection <T> c = collection as ICollection <T>;
- if (c == null)
- {
- data = EmptyArray;
+ if (c == null) {
+ _items = EmptyArray<T>.Value;;
AddEnumerable (collection);
- }
- else
- {
- data = new T [c.Count];
- AddCollection (c);
+ } else {
+ _size = c.Count;
+ _items = new T [Math.Max (_size, DefaultCapacity)];
+ c.CopyTo (_items, 0);
}
}
{
if (capacity < 0)
throw new ArgumentOutOfRangeException ("capacity");
- data = new T [capacity];
+ _items = new T [capacity];
}
internal List (T [] data, int size)
{
- this.data = data;
- this.size = size;
+ _items = data;
+ _size = size;
}
+
public void Add (T item)
{
- GrowIfNeeded (1);
- data [size ++] = item;
+ // If we check to see if we need to grow before trying to grow
+ // we can speed things up by 25%
+ if (_size == _items.Length)
+ GrowIfNeeded (1);
+ Array.UnsafeStore (_items, _size++, item);
+ _version++;
}
void GrowIfNeeded (int newCount)
{
- int minimumSize = size + newCount;
- if (minimumSize > data.Length)
+ int minimumSize = _size + newCount;
+ if (minimumSize > _items.Length)
Capacity = Math.Max (Math.Max (Capacity * 2, DefaultCapacity), minimumSize);
}
if (count < 0)
throw new ArgumentOutOfRangeException ("count");
- if ((uint) idx + (uint) count > (uint) size)
+ if ((uint) idx + (uint) count > (uint) _size)
throw new ArgumentException ("index and count exceed length of list");
}
void AddCollection (ICollection <T> collection)
{
int collectionCount = collection.Count;
+ if (collectionCount == 0)
+ return;
+
GrowIfNeeded (collectionCount);
- collection.CopyTo (data, size);
- size += collectionCount;
+ collection.CopyTo (_items, _size);
+ _size += collectionCount;
}
+
void AddEnumerable (IEnumerable <T> enumerable)
{
foreach (T t in enumerable)
public void AddRange (IEnumerable <T> collection)
{
- CheckCollection (collection);
+ if (collection == null)
+ throw new ArgumentNullException ("collection");
ICollection <T> c = collection as ICollection <T>;
if (c != null)
AddCollection (c);
else
AddEnumerable (collection);
+ _version++;
}
public ReadOnlyCollection <T> AsReadOnly ()
public int BinarySearch (T item)
{
- return Array.BinarySearch <T> (data, 0, size, item);
+ return Array.BinarySearch <T> (_items, 0, _size, item);
}
public int BinarySearch (T item, IComparer <T> comparer)
{
- return Array.BinarySearch <T> (data, 0, size, item, comparer);
+ return Array.BinarySearch <T> (_items, 0, _size, item, comparer);
}
public int BinarySearch (int index, int count, T item, IComparer <T> comparer)
{
CheckRange (index, count);
- return Array.BinarySearch <T> (data, index, count, item, comparer);
+ return Array.BinarySearch <T> (_items, index, count, item, comparer);
}
public void Clear ()
{
- Array.Clear (data, 0, data.Length);
- size = 0;
+ Array.Clear (_items, 0, _items.Length);
+ _size = 0;
+ _version++;
}
public bool Contains (T item)
{
- EqualityComparer<T> equalityComparer = EqualityComparer<T>.Default;
- for (int i = 0; i < size; i++)
- if (equalityComparer.Equals (data[i], item))
- return true;
- return false;
+ return Array.IndexOf<T>(_items, item, 0, _size) != -1;
}
public List <TOutput> ConvertAll <TOutput> (Converter <T, TOutput> converter)
{
if (converter == null)
throw new ArgumentNullException ("converter");
- List <TOutput> u = new List <TOutput> (size);
- foreach (T t in this)
- u.Add (converter (t));
+ List <TOutput> u = new List <TOutput> (_size);
+ for (int i = 0; i < _size; i++)
+ u._items[i] = converter(_items[i]);
+
+ u._size = _size;
return u;
}
public void CopyTo (T [] array)
{
- Array.Copy (data, 0, array, 0, size);
+ Array.Copy (_items, 0, array, 0, _size);
}
public void CopyTo (T [] array, int arrayIndex)
{
- Array.Copy (data, 0, array, arrayIndex, size);
+ Array.Copy (_items, 0, array, arrayIndex, _size);
}
public void CopyTo (int index, T [] array, int arrayIndex, int count)
{
CheckRange (index, count);
- Array.Copy (data, index, array, arrayIndex, count);
+ Array.Copy (_items, index, array, arrayIndex, count);
}
public bool Exists (Predicate <T> match)
{
- return FindIndex (match) != -1;
+ CheckMatch(match);
+ return GetIndex(0, _size, match) != -1;
}
public T Find (Predicate <T> match)
{
- int i = FindIndex (match);
- return (i != -1) ? data [i] : default (T);
+ CheckMatch(match);
+ int i = GetIndex(0, _size, match);
+ return (i != -1) ? _items [i] : default (T);
}
- void CheckMatch (Predicate <T> match)
+
+ static void CheckMatch (Predicate <T> match)
{
if (match == null)
throw new ArgumentNullException ("match");
}
- // Maybe we could make this faster. For example, you could
- // make a bit set with stackalloc for which elements to copy
- // then you could size the array correctly.
public List <T> FindAll (Predicate <T> match)
{
CheckMatch (match);
- List <T> f = new List <T> ();
-
- foreach (T t in this)
- if (match (t))
- f.Add (t);
+ if (this._size <= 0x10000) // <= 8 * 1024 * 8 (8k in stack)
+ return this.FindAllStackBits (match);
+ else
+ return this.FindAllList (match);
+ }
+
+ private List <T> FindAllStackBits (Predicate <T> match)
+ {
+ unsafe
+ {
+ uint *bits = stackalloc uint [(this._size / 32) + 1];
+ uint *ptr = bits;
+ int found = 0;
+ uint bitmask = 0x80000000;
+
+ for (int i = 0; i < this._size; i++)
+ {
+ if (match (this._items [i]))
+ {
+ (*ptr) = (*ptr) | bitmask;
+ found++;
+ }
+
+ bitmask = bitmask >> 1;
+ if (bitmask == 0)
+ {
+ ptr++;
+ bitmask = 0x80000000;
+ }
+ }
+
+ T [] results = new T [found];
+ bitmask = 0x80000000;
+ ptr = bits;
+ int j = 0;
+ for (int i = 0; i < this._size && j < found; i++)
+ {
+ if (((*ptr) & bitmask) == bitmask)
+ results [j++] = this._items [i];
+
+ bitmask = bitmask >> 1;
+ if (bitmask == 0)
+ {
+ ptr++;
+ bitmask = 0x80000000;
+ }
+ }
+
+ return new List <T> (results, found);
+ }
+ }
+
+ private List <T> FindAllList (Predicate <T> match)
+ {
+ List <T> results = new List <T> ();
+ for (int i = 0; i < this._size; i++)
+ if (match (this._items [i]))
+ results.Add (this._items [i]);
- return f;
+ return results;
}
public int FindIndex (Predicate <T> match)
{
CheckMatch (match);
- return GetIndex (0, size, match);
+ return GetIndex (0, _size, match);
}
public int FindIndex (int startIndex, Predicate <T> match)
{
CheckMatch (match);
CheckIndex (startIndex);
- return GetIndex (startIndex, size - startIndex, match);
+ return GetIndex (startIndex, _size - startIndex, match);
}
public int FindIndex (int startIndex, int count, Predicate <T> match)
{
}
int GetIndex (int startIndex, int count, Predicate <T> match)
{
- for (int i = startIndex; i < startIndex + count; i ++)
- if (match (data [i]))
+ int end = startIndex + count;
+ for (int i = startIndex; i < end; i ++)
+ if (match (_items [i]))
return i;
return -1;
public T FindLast (Predicate <T> match)
{
CheckMatch (match);
- int i = GetLastIndex (0, size, match);
+ int i = GetLastIndex (0, _size, match);
return i == -1 ? default (T) : this [i];
}
public int FindLastIndex (Predicate <T> match)
{
CheckMatch (match);
- return GetLastIndex (0, size, match);
+ return GetLastIndex (0, _size, match);
}
public int FindLastIndex (int startIndex, Predicate <T> match)
{
// unlike FindLastIndex, takes regular params for search range
for (int i = startIndex + count; i != startIndex;)
- if (match (data [--i]))
+ if (match (_items [--i]))
return i;
return -1;
}
{
if (action == null)
throw new ArgumentNullException ("action");
- foreach (T t in this)
- action (t);
+ for(int i=0; i < _size; i++)
+ action(_items[i]);
}
public Enumerator GetEnumerator ()
{
CheckRange (index, count);
T [] tmpArray = new T [count];
- Array.Copy (data, index, tmpArray, 0, count);
+ Array.Copy (_items, index, tmpArray, 0, count);
return new List <T> (tmpArray, count);
}
public int IndexOf (T item)
{
- return Array.IndexOf<T> (data, item, 0, size);
+ return Array.IndexOf<T> (_items, item, 0, _size);
}
public int IndexOf (T item, int index)
{
CheckIndex (index);
- return Array.IndexOf<T> (data, item, index, size - index);
+ return Array.IndexOf<T> (_items, item, index, _size - index);
}
public int IndexOf (T item, int index, int count)
if (count < 0)
throw new ArgumentOutOfRangeException ("count");
- if ((uint) index + (uint) count > (uint) size)
+ if ((uint) index + (uint) count > (uint) _size)
throw new ArgumentOutOfRangeException ("index and count exceed length of list");
- return Array.IndexOf<T> (data, item, index, count);
+ return Array.IndexOf<T> (_items, item, index, count);
}
void Shift (int start, int delta)
if (delta < 0)
start -= delta;
- Array.Copy (data, start, data, start + delta, size - start);
+ if (start < _size)
+ Array.Copy (_items, start, _items, start + delta, _size - start);
- size += delta;
+ _size += delta;
+
+ if (delta < 0)
+ Array.Clear (_items, _size, -delta);
}
void CheckIndex (int index)
{
- if (index < 0 || (uint) index > (uint) size)
+ if (index < 0 || (uint) index > (uint) _size)
throw new ArgumentOutOfRangeException ("index");
}
public void Insert (int index, T item)
{
CheckIndex (index);
- GrowIfNeeded (1);
+ if (_size == _items.Length)
+ GrowIfNeeded (1);
Shift (index, 1);
- this [index] = item;
-
- }
-
- void CheckCollection (IEnumerable <T> collection)
- {
- if (collection == null)
- throw new ArgumentNullException ("collection");
+ _items[index] = item;
+ _version++;
}
public void InsertRange (int index, IEnumerable <T> collection)
{
- CheckCollection (collection);
+ if (collection == null)
+ throw new ArgumentNullException ("collection");
+
CheckIndex (index);
- ICollection <T> c = collection as ICollection <T>;
- if (c != null)
- InsertCollection (index, c);
- else
- InsertEnumeration (index, collection);
+ if (collection == this) {
+ T[] buffer = new T[_size];
+ CopyTo (buffer, 0);
+ GrowIfNeeded (_size);
+ Shift (index, buffer.Length);
+ Array.Copy (buffer, 0, _items, index, buffer.Length);
+ } else {
+ ICollection <T> c = collection as ICollection <T>;
+ if (c != null)
+ InsertCollection (index, c);
+ else
+ InsertEnumeration (index, collection);
+ }
+ _version++;
}
void InsertCollection (int index, ICollection <T> collection)
GrowIfNeeded (collectionCount);
Shift (index, collectionCount);
- collection.CopyTo (data, index);
+ collection.CopyTo (_items, index);
}
+
void InsertEnumeration (int index, IEnumerable <T> enumerable)
{
foreach (T t in enumerable)
public int LastIndexOf (T item)
{
- return Array.LastIndexOf<T> (data, item, size - 1, size);
+ if (_size == 0)
+ return -1;
+ return Array.LastIndexOf<T> (_items, item, _size - 1, _size);
}
public int LastIndexOf (T item, int index)
{
CheckIndex (index);
- return Array.LastIndexOf<T> (data, item, index, index + 1);
+ return Array.LastIndexOf<T> (_items, item, index, index + 1);
}
public int LastIndexOf (T item, int index, int count)
if (index - count + 1 < 0)
throw new ArgumentOutOfRangeException ("cound", count, "count is too large");
- return Array.LastIndexOf<T> (data, item, index, count);
+ return Array.LastIndexOf<T> (_items, item, index, count);
}
public bool Remove (T item)
return loc != -1;
}
- [MonoTODO ("I can make it faster than this...")]
public int RemoveAll (Predicate <T> match)
{
- CheckMatch (match);
+ CheckMatch(match);
+ int i = 0;
+ int j = 0;
- int index = 0;
- int c = 0;
- while ((index = GetIndex (index, size - index, match)) != -1) {
- RemoveAt (index);
- c ++;
+ // Find the first item to remove
+ for (i = 0; i < _size; i++)
+ if (match(_items[i]))
+ break;
+
+ if (i == _size)
+ return 0;
+
+ _version++;
+
+ // Remove any additional items
+ for (j = i + 1; j < _size; j++)
+ {
+ if (!match(_items[j]))
+ _items[i++] = _items[j];
}
-
- Array.Clear (data, size, c);
- return c;
+ if (j - i > 0)
+ Array.Clear (_items, i, j - i);
+
+ _size = i;
+ return (j - i);
}
public void RemoveAt (int index)
{
- CheckIndex (index);
+ if (index < 0 || (uint)index >= (uint)_size)
+ throw new ArgumentOutOfRangeException("index");
Shift (index, -1);
- Array.Clear (data, size, 0);
+ Array.Clear (_items, _size, 1);
+ _version++;
}
public void RemoveRange (int index, int count)
{
CheckRange (index, count);
- Shift (index, -count);
- Array.Clear (data, size, count);
+ if (count > 0) {
+ Shift (index, -count);
+ Array.Clear (_items, _size, count);
+ _version++;
+ }
}
public void Reverse ()
{
- Array.Reverse (data, 0, size);
+ Array.Reverse (_items, 0, _size);
+ _version++;
}
public void Reverse (int index, int count)
{
CheckRange (index, count);
- Array.Reverse (data, index, count);
+ Array.Reverse (_items, index, count);
+ _version++;
}
public void Sort ()
{
- Array.Sort<T> (data, 0, size, Comparer <T>.Default);
+ Array.Sort<T> (_items, 0, _size);
+ _version++;
}
public void Sort (IComparer <T> comparer)
{
- Array.Sort<T> (data, 0, size, comparer);
+ Array.Sort<T> (_items, 0, _size, comparer);
+ _version++;
}
public void Sort (Comparison <T> comparison)
{
- Array.Sort<T> (data, size, comparison);
+ if (comparison == null)
+ throw new ArgumentNullException ("comparison");
+
+ Array.SortImpl<T> (_items, _size, comparison);
+ _version++;
}
public void Sort (int index, int count, IComparer <T> comparer)
{
CheckRange (index, count);
- Array.Sort<T> (data, index, count, comparer);
+ Array.Sort<T> (_items, index, count, comparer);
+ _version++;
}
public T [] ToArray ()
{
- T [] t = new T [size];
- Array.Copy (data, t, size);
+ T [] t = new T [_size];
+ Array.Copy (_items, t, _size);
return t;
}
public void TrimExcess ()
{
- Capacity = size;
+ Capacity = _size;
}
public bool TrueForAll (Predicate <T> match)
{
CheckMatch (match);
- foreach (T t in this)
- if (!match (t))
+ for (int i = 0; i < _size; i++)
+ if (!match(_items[i]))
return false;
return true;
public int Capacity {
get {
- return data.Length;
+ return _items.Length;
}
set {
- if ((uint) value < (uint) size)
+ if ((uint) value < (uint) _size)
throw new ArgumentOutOfRangeException ();
- Array.Resize (ref data, value);
+ Array.Resize (ref _items, value);
}
}
public int Count {
- get { return size; }
+ get { return _size; }
}
public T this [int index] {
+ [MethodImpl ((MethodImplOptions)256)]
get {
- if ((uint) index >= (uint) size)
+ if ((uint) index >= (uint) _size)
throw new ArgumentOutOfRangeException ("index");
- return data [index];
+ return Array.UnsafeLoad (_items, index);
}
+
+ [MethodImpl ((MethodImplOptions)256)]
set {
- CheckIndex (index);
- data [index] = value;
+ if ((uint) index >= (uint) _size)
+ throw new ArgumentOutOfRangeException ("index");
+ Array.UnsafeStore (_items, index, value);
+ _version++;
}
}
void ICollection.CopyTo (Array array, int arrayIndex)
{
- Array.Copy (data, 0, array, arrayIndex, size);
+ if (array == null)
+ throw new ArgumentNullException ("array");
+ if (array.Rank > 1 || array.GetLowerBound (0) != 0)
+ throw new ArgumentException ("Array must be zero based and single dimentional", "array");
+ Array.Copy (_items, 0, array, arrayIndex, _size);
}
IEnumerator IEnumerable.GetEnumerator ()
int IList.Add (object item)
{
- Add ((T) item);
- return size - 1;
+ try {
+ Add ((T) item);
+ return _size - 1;
+ } catch (NullReferenceException) {
+ } catch (InvalidCastException) {
+ }
+ throw new ArgumentException ("item");
}
bool IList.Contains (object item)
{
- return Contains ((T) item);
+ try {
+ return Contains ((T) item);
+ } catch (NullReferenceException) {
+ } catch (InvalidCastException) {
+ }
+ return false;
}
int IList.IndexOf (object item)
{
- return IndexOf ((T) item);
+ try {
+ return IndexOf ((T) item);
+ } catch (NullReferenceException) {
+ } catch (InvalidCastException) {
+ }
+ return -1;
}
void IList.Insert (int index, object item)
{
- Insert (index, (T) item);
+ // We need to check this first because, even if the
+ // item is null or not the correct type, we need to
+ // return an ArgumentOutOfRange exception if the
+ // index is out of range
+ CheckIndex (index);
+ try {
+ Insert (index, (T) item);
+ return;
+ } catch (NullReferenceException) {
+ } catch (InvalidCastException) {
+ }
+ throw new ArgumentException ("item");
}
void IList.Remove (object item)
{
- Remove ((T) item);
+ try {
+ Remove ((T) item);
+ return;
+ } catch (NullReferenceException) {
+ } catch (InvalidCastException) {
+ }
+ // Swallow the exception--if we can't cast to the
+ // correct type then we've already "succeeded" in
+ // removing the item from the List.
}
bool ICollection <T>.IsReadOnly {
object IList.this [int index] {
get { return this [index]; }
- set { this [index] = (T) value; }
+ set {
+ try {
+ this [index] = (T) value;
+ return;
+ } catch (NullReferenceException) {
+ // can happen when 'value' is null and T is a valuetype
+ } catch (InvalidCastException) {
+ }
+ throw new ArgumentException ("value");
+ }
}
#endregion
[Serializable]
public struct Enumerator : IEnumerator <T>, IDisposable {
- const int NOT_STARTED = -2;
-
- // this MUST be -1, because we depend on it in move next.
- // we just decr the size, so, 0 - 1 == FINISHED
- const int FINISHED = -1;
-
- List <T> l;
- int idx;
- int ver;
-
+ readonly List<T> l;
+ int next;
+ readonly int ver;
+
+ T current;
+
internal Enumerator (List <T> l)
+ : this ()
{
this.l = l;
- idx = NOT_STARTED;
- ver = l.version;
+ ver = l._version;
}
- // for some fucked up reason, MSFT added a useless dispose to this class
- // It means that in foreach, we must still do a try/finally. Broken, very
- // broken.
public void Dispose ()
{
- idx = NOT_STARTED;
}
-
+
public bool MoveNext ()
{
- if (ver != l.version)
- throw new InvalidOperationException ();
-
- if (idx == NOT_STARTED)
- idx = l.size;
-
- return idx != FINISHED && -- idx != FINISHED;
+ var list = l;
+
+ if ((uint)next < (uint)list._size && ver == list._version) {
+ current = list._items [next++];
+ return true;
+ }
+
+ if (ver != l._version)
+ throw new InvalidOperationException ("Collection was modified; enumeration operation may not execute.");
+
+ next = -1;
+ return false;
}
-
+
public T Current {
- get {
- if (idx < 0)
- throw new InvalidOperationException ();
-
- return l.data [l.size - 1 - idx];
- }
+ get { return current; }
}
void IEnumerator.Reset ()
{
- if (ver != l.version)
- throw new InvalidOperationException ();
-
- idx = NOT_STARTED;
+ if (ver != l._version)
+ throw new InvalidOperationException ("Collection was modified; enumeration operation may not execute.");
+
+ next = 0;
}
object IEnumerator.Current {
- get { return Current; }
+ get {
+ if (ver != l._version)
+ throw new InvalidOperationException ("Collection was modified; enumeration operation may not execute.");
+
+ if (next <= 0)
+ throw new InvalidOperationException ();
+ return current;
+ }
}
}
}
}
-#endif
projects / mono.git / blobdiff