// 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 {
+ [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 ()
{
- _items = 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)
- {
- _items = EmptyArray;
+ if (c == null) {
+ _items = EmptyArray<T>.Value;;
AddEnumerable (collection);
- }
- else
- {
- _items = new T [c.Count];
- AddCollection (c);
+ } else {
+ _size = c.Count;
+ _items = new T [Math.Max (_size, DefaultCapacity)];
+ c.CopyTo (_items, 0);
}
}
_items = data;
_size = size;
}
+
public void Add (T item)
{
- GrowIfNeeded (1);
- _items [_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 AddCollection (ICollection <T> collection)
{
int collectionCount = collection.Count;
+ if (collectionCount == 0)
+ return;
+
GrowIfNeeded (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)
public bool Contains (T item)
{
- EqualityComparer<T> equalityComparer = EqualityComparer<T>.Default;
- for (int i = 0; i < _size; i++)
- if (equalityComparer.Equals (_items[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));
+ for (int i = 0; i < _size; i++)
+ u._items[i] = converter(_items[i]);
+
+ u._size = _size;
return u;
}
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);
+ 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)
}
int GetIndex (int startIndex, int count, Predicate <T> match)
{
- for (int i = startIndex; i < startIndex + count; i ++)
+ int end = startIndex + count;
+ for (int i = startIndex; i < end; i ++)
if (match (_items [i]))
return i;
{
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 ()
if (delta < 0)
start -= delta;
- Array.Copy (_items, start, _items, start + delta, _size - start);
+ if (start < _size)
+ Array.Copy (_items, start, _items, start + delta, _size - start);
_size += delta;
+
+ if (delta < 0)
+ Array.Clear (_items, _size, -delta);
}
void CheckIndex (int index)
public void Insert (int index, T item)
{
CheckIndex (index);
- GrowIfNeeded (1);
+ if (_size == _items.Length)
+ GrowIfNeeded (1);
Shift (index, 1);
- this [index] = item;
+ _items[index] = item;
_version++;
}
-
- void CheckCollection (IEnumerable <T> collection)
- {
- if (collection == null)
- throw new ArgumentNullException ("collection");
- }
public void InsertRange (int index, IEnumerable <T> collection)
{
- CheckCollection (collection);
+ if (collection == null)
+ throw new ArgumentNullException ("collection");
+
CheckIndex (index);
if (collection == this) {
T[] buffer = new T[_size];
Shift (index, collectionCount);
collection.CopyTo (_items, index);
}
+
void InsertEnumeration (int index, IEnumerable <T> enumerable)
{
foreach (T t in enumerable)
public int LastIndexOf (T item)
{
+ if (_size == 0)
+ return -1;
return Array.LastIndexOf<T> (_items, item, _size - 1, _size);
}
return loc != -1;
}
- // FIXME: this could probably be made faster.
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 (_items, _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 (_items, _size, 0);
+ Array.Clear (_items, _size, 1);
_version++;
}
public void Sort ()
{
- Array.Sort<T> (_items, 0, _size, Comparer <T>.Default);
+ Array.Sort<T> (_items, 0, _size);
_version++;
}
public void Sort (IComparer <T> comparer)
public void Sort (Comparison <T> comparison)
{
- Array.Sort<T> (_items, _size, comparison);
+ if (comparison == null)
+ throw new ArgumentNullException ("comparison");
+
+ Array.SortImpl<T> (_items, _size, comparison);
_version++;
}
{
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 T this [int index] {
+ [MethodImpl ((MethodImplOptions)256)]
get {
if ((uint) index >= (uint) _size)
throw new ArgumentOutOfRangeException ("index");
- return _items [index];
+ return Array.UnsafeLoad (_items, index);
}
+
+ [MethodImpl ((MethodImplOptions)256)]
set {
- CheckIndex (index);
- if ((uint) index == (uint) _size)
+ if ((uint) index >= (uint) _size)
throw new ArgumentOutOfRangeException ("index");
- _items [index] = value;
+ Array.UnsafeStore (_items, index, value);
+ _version++;
}
}
void ICollection.CopyTo (Array array, int arrayIndex)
{
+ 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);
}
{
try {
Add ((T) item);
+ return _size - 1;
+ } catch (NullReferenceException) {
} catch (InvalidCastException) {
- throw new ArgumentException("item");
}
- return _size - 1;
+ throw new ArgumentException ("item");
}
bool IList.Contains (object item)
{
try {
return Contains ((T) item);
+ } catch (NullReferenceException) {
} catch (InvalidCastException) {
- return false;
}
+ return false;
}
int IList.IndexOf (object item)
{
try {
- return IndexOf((T) item);
+ return IndexOf ((T) item);
+ } catch (NullReferenceException) {
} catch (InvalidCastException) {
- return -1;
}
+ return -1;
}
void IList.Insert (int index, object item)
CheckIndex (index);
try {
Insert (index, (T) item);
+ return;
+ } catch (NullReferenceException) {
} catch (InvalidCastException) {
- throw new ArgumentException("item");
}
+ throw new ArgumentException ("item");
}
void IList.Remove (object 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.
}
+ // 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;
}
- // 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 ()
{
+ 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.");
-
- if (idx == NOT_STARTED)
- idx = l._size;
-
- return idx != FINISHED && -- idx != FINISHED;
+ 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._items [l._size - 1 - idx];
- }
+ get { return current; }
}
void IEnumerator.Reset ()
{
if (ver != l._version)
- throw new InvalidOperationException ("Collection was modified;"
- + "enumeration operation may not execute.");
-
- idx = NOT_STARTED;
+ 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