// Carlos Alberto Cortez (calberto.cortez@gmail.com)
// David Waite (mass@akuma.org)
//
-// (C) 2004 Novell, Inc.
-// (C) 2005 David Waite
-//
-
-//
-// Copyright (C) 2004 Novell, Inc (http://www.novell.com)
+// Copyright (C) 2004-2005 Novell, Inc (http://www.novell.com)
// Copyright (C) 2005 David Waite
//
// Permission is hereby granted, free of charge, to any person obtaining
//
#if NET_2_0
-using System;
-using System.Collections;
+
using System.Collections.ObjectModel;
using System.Runtime.InteropServices;
namespace System.Collections.Generic {
[Serializable]
public class List <T> : IList <T>, IList, ICollection {
- T [] data;
- int size;
- int version;
+ T [] _items;
+ int _size;
+ int _version;
static readonly T [] EmptyArray = new T [0];
const int DefaultCapacity = 4;
public List ()
{
- data = EmptyArray;
+ _items = EmptyArray;
}
public List (IEnumerable <T> collection)
ICollection <T> c = collection as ICollection <T>;
if (c == null)
{
- data = EmptyArray;
+ _items = EmptyArray;
AddEnumerable (collection);
}
else
{
- data = new T [c.Count];
+ _items = new T [c.Count];
AddCollection (c);
}
}
{
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);
+ _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)
AddCollection (c);
else
AddEnumerable (collection);
+ _version++;
}
public ReadOnlyCollection <T> AsReadOnly ()
public int BinarySearch (T item)
{
- return Array.BinarySearch (data, item);
+ return Array.BinarySearch <T> (_items, 0, _size, item);
}
public int BinarySearch (T item, IComparer <T> comparer)
{
- return Array.BinarySearch (data, 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 (data, index, size, 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)
{
- return IndexOf (item) != -1;
+ 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 (data, item, 0, size);
+ return Array.IndexOf<T> (_items, item, 0, _size);
}
public int IndexOf (T item, int index)
{
CheckIndex (index);
- return Array.IndexOf (data, item, index, size - index);
+ return Array.IndexOf<T> (_items, item, index, _size - index);
}
public int IndexOf (T item, int index, int count)
{
- CheckRange (index, count);
- return Array.IndexOf (data, item, index, count);
+ if (index < 0)
+ throw new ArgumentOutOfRangeException ("index");
+
+ if (count < 0)
+ throw new ArgumentOutOfRangeException ("count");
+
+ if ((uint) index + (uint) count > (uint) _size)
+ throw new ArgumentOutOfRangeException ("index and count exceed length of list");
+
+ 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 ((uint) index >= (uint) size)
+ if (index < 0 || (uint) index > (uint) _size)
throw new ArgumentOutOfRangeException ("index");
}
public void Insert (int index, T item)
{
- if ((uint) index > (uint) size)
- throw new ArgumentOutOfRangeException ("index");
-
- GrowIfNeeded (1);
+ CheckIndex (index);
+ if (_size == _items.Length)
+ GrowIfNeeded (1);
Shift (index, 1);
- this [index] = item;
-
+ _items[index] = item;
+ _version++;
}
void CheckCollection (IEnumerable <T> collection)
{
CheckCollection (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)
{
public int LastIndexOf (T item)
{
- return Array.LastIndexOf (data, item, 0, size);
+ return Array.LastIndexOf<T> (_items, item, _size - 1, _size);
}
public int LastIndexOf (T item, int index)
{
CheckIndex (index);
- return Array.LastIndexOf (data, item, index, size - index);
+ return Array.LastIndexOf<T> (_items, item, index, index + 1);
}
public int LastIndexOf (T item, int index, int count)
{
- CheckRange (index, count);
- return Array.LastIndexOf (data, item, index, count);
+ if (index < 0)
+ throw new ArgumentOutOfRangeException ("index", index, "index is negative");
+
+ if (count < 0)
+ throw new ArgumentOutOfRangeException ("count", count, "count is negative");
+
+ if (index - count + 1 < 0)
+ throw new ArgumentOutOfRangeException ("cound", count, "count is too large");
+
+ 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;
+
+ // Find the first item to remove
+ for (i = 0; i < _size; i++)
+ if (match(_items[i]))
+ break;
+
+ if (i == _size)
+ return 0;
- int index = 0;
- int c = 0;
- while ((index = GetIndex (index, size - index, match)) != -1) {
- RemoveAt (index);
- c ++;
+ _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 (data, 0, size, (IComparer) Comparer <T>.Default);
+ Array.Sort<T> (_items, 0, _size, Comparer <T>.Default);
+ _version++;
}
public void Sort (IComparer <T> comparer)
{
- Array.Sort (data, 0, size, (IComparer) comparer);
+ Array.Sort<T> (_items, 0, _size, comparer);
+ _version++;
}
-
- // Waiting on Array
- [MonoTODO]
+
public void Sort (Comparison <T> comparison)
{
- throw new NotImplementedException ();
+ Array.Sort<T> (_items, _size, comparison);
+ _version++;
}
public void Sort (int index, int count, IComparer <T> comparer)
{
CheckRange (index, count);
- Array.Sort (data, index, count, (IComparer) 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] {
get {
- if ((uint) index >= (uint) size)
+ if ((uint) index >= (uint) _size)
throw new ArgumentOutOfRangeException ("index");
- return data [index];
+ return _items [index];
}
set {
CheckIndex (index);
- data [index] = value;
+ if ((uint) index == (uint) _size)
+ throw new ArgumentOutOfRangeException ("index");
+ _items [index] = value;
}
}
void ICollection.CopyTo (Array array, int arrayIndex)
{
- Array.Copy (data, 0, array, arrayIndex, size);
+ 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);
+ } 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 {
}
#endregion
+ [Serializable]
public struct Enumerator : IEnumerator <T>, IDisposable {
const int NOT_STARTED = -2;
{
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
public bool MoveNext ()
{
- if (ver != l.version)
- throw new InvalidOperationException ();
+ if (ver != l._version)
+ throw new InvalidOperationException ("Collection was modified;"
+ + "enumeration operation may not execute.");
if (idx == NOT_STARTED)
- idx = l.size;
+ idx = l._size;
return idx != FINISHED && -- idx != FINISHED;
}
if (idx < 0)
throw new InvalidOperationException ();
- return l.data [l.size - 1 - idx];
+ return l._items [l._size - 1 - idx];
}
}
void IEnumerator.Reset ()
{
- if (ver != l.version)
- throw new InvalidOperationException ();
+ if (ver != l._version)
+ throw new InvalidOperationException ("Collection was modified;"
+ + "enumeration operation may not execute.");
idx = NOT_STARTED;
}
projects / mono.git / blobdiff