}
public void Add (T item)
{
- GrowIfNeeded (1);
+ // 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);
_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 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++;
}
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;
+
+ // Find the first item to remove
+ for (i = 0; i < _size; i++)
+ if (match(_items[i]))
+ break;
- int index = 0;
- int c = 0;
- while ((index = GetIndex (index, _size - index, match)) != -1) {
- RemoveAt (index);
- c ++;
+ 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++;
}
{
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;
}
set {
CheckIndex (index);
+ if ((uint) index == (uint) _size)
+ throw new ArgumentOutOfRangeException ("index");
_items [index] = value;
}
}
int IList.Add (object item)
{
- Add ((T) item);
+ try {
+ Add ((T) item);
+ } catch (InvalidCastException) {
+ throw new ArgumentException("item");
+ }
return _size - 1;
}
bool IList.Contains (object item)
{
- return Contains ((T) item);
+ try {
+ return Contains ((T) item);
+ } catch (InvalidCastException) {
+ return false;
+ }
}
int IList.IndexOf (object item)
{
- return IndexOf ((T) item);
+ try {
+ return IndexOf((T) item);
+ } 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);
+ } catch (InvalidCastException) {
+ throw new ArgumentException("item");
+ }
}
void IList.Remove (object item)
{
- Remove ((T) item);
+ try {
+ Remove ((T) item);
+ } 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 {
projects / mono.git / blobdiff