From 3808b042f406c2f5108c064013b04aa41d321418 Mon Sep 17 00:00:00 2001 From: Ben Maurer Date: Sun, 26 Dec 2004 20:31:40 +0000 Subject: [PATCH] 2004-12-26 Ben Maurer * Queue.cs: New, non-linked-list based impl. svn path=/trunk/mcs/; revision=38095 --- .../corlib/System.Collections.Generic/ChangeLog | 4 + .../corlib/System.Collections.Generic/Queue.cs | 351 +++++++++++++-------- 2 files changed, 219 insertions(+), 136 deletions(-) diff --git a/mcs/class/corlib/System.Collections.Generic/ChangeLog b/mcs/class/corlib/System.Collections.Generic/ChangeLog index 3a1a2478bd7..b7f58aab92c 100644 --- a/mcs/class/corlib/System.Collections.Generic/ChangeLog +++ b/mcs/class/corlib/System.Collections.Generic/ChangeLog @@ -1,3 +1,7 @@ +2004-12-26 Ben Maurer + + * Queue.cs: New, non-linked-list based impl. + 2004-11-29 Ben Maurer * Comparer.cs: Update this class. diff --git a/mcs/class/corlib/System.Collections.Generic/Queue.cs b/mcs/class/corlib/System.Collections.Generic/Queue.cs index cddcf8290ba..924582aa671 100644 --- a/mcs/class/corlib/System.Collections.Generic/Queue.cs +++ b/mcs/class/corlib/System.Collections.Generic/Queue.cs @@ -1,11 +1,11 @@ -// -*- Mode: csharp; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- // // System.Collections.Generic.Queue // // Author: // Martin Baulig (martin@ximian.com) +// Ben Maurer (bmaurer@ximian.com) // -// (C) 2003 Novell, Inc. +// (C) 2003, 2004 Novell, Inc. // // @@ -39,193 +39,272 @@ namespace System.Collections.Generic { [CLSCompliant(false)] [ComVisible(false)] - public class Queue : ICollection, IEnumerable, - ICollection, IEnumerable + public class Queue : ICollection, ICollection { - int count; - protected int modified; - protected Node head; - Node tail; - - public void Clear () + T [] data; + int head; + int tail; + int size; + int version; + + public Queue () { - head = tail = null; - count = 0; - modified++; } - - public void Enqueue (T item) + + public Queue (int count) { - tail = new Node (tail, item); - if (head == null) - head = tail; - count++; - modified++; + if (count < 0) + throw new ArgumentOutOfRangeException ("count"); + + data = new T [count]; } - - public T Peek () + + public Queue (IEnumerable collection) { - if (head == null) - throw new ArgumentException (); - - return head.Item; + if (collection == null) + throw new ArgumentNullException ("collection"); + + foreach (T t in collection) + Enqueue (t); } - - public T Dequeue () + + public void Clear () { - if (head == null) - throw new ArgumentException (); - - T retval = head.Item; - head = head.Next; - if (head == null) - tail = null; - count--; - modified++; - return retval; + Array.Clear (data, 0, data.Length); } - + public bool Contains (T item) { - for (Node node = head; node != null; node = node.Next) - if (node.Item == item) - return true; - + if (item == null) { + foreach (T t in this) + if (t == null) + return true; + } else { + foreach (T t in this) + if (item.Equals (t)) + return true; + } + return false; } - - public virtual void CopyTo (T[] array, int start) + + public void CopyTo (T [] array, int idx) { - // re-ordered to avoid possible integer overflow - if (start >= array.Length - count) - throw new ArgumentException (); - - for (Node node = head; node != null; node = node.Next) - array [start++] = node.Item; + if (array == null) + throw new ArgumentNullException (); + + if ((uint) idx < (uint) array.Length) + throw new ArgumentOutOfRangeException (); + + if (array.Length - idx < size) + throw new ArgumentOutOfRangeException (); + + int contents_length = data.Length; + int length_from_head = contents_length - head; + + Array.Copy (data, head, array, idx, Math.Min (size, length_from_head)); + if (size > length_from_head) + Array.Copy (data, 0, array, + idx + length_from_head, + size - length_from_head); + } - - void ICollection.CopyTo (Array array, int start) + + void ICollection.CopyTo (Array array, int idx) { - // re-ordered to avoid possible integer overflow - if (start >= array.Length - count) + if (array == null) + throw new ArgumentNullException (); + + if ((uint) idx < (uint) array.Length) + throw new ArgumentOutOfRangeException (); + + if (array.Length - idx < size) + throw new ArgumentOutOfRangeException (); + + if (size == 0) + return; + + try { + int contents_length = data.Length; + int length_from_head = contents_length - head; + + Array.Copy (data, head, array, idx, Math.Min (size, length_from_head)); + if (size > length_from_head) + Array.Copy (data, 0, array, + idx + length_from_head, + size - length_from_head); + } catch (ArrayTypeMismatchException) { throw new ArgumentException (); - - for (Node node = head; node != null; node = node.Next) - array.SetValue (node.Item, start++); + } } - - public T[] ToArray () + + public T Dequeue () { - int pos = 0; - T[] retval = new T [count]; - for (Node node = head; node != null; node = node.Next) - retval [pos++] = node.Item; - - return retval; + T ret = Peek (); + + // clear stuff out to make the GC happy + data [head] = default (T); + + if (++head == data.Length) + head = 0; + size --; + version ++; + + return ret; } - + + public T Peek () + { + if (size == 0) + throw new InvalidOperationException (); + + return data [head]; + } + + public void Enqueue (T item) + { + if (data == null || size == data.Length) + SetCapacity (Math.Max (size * 2, 4)); + + data [tail] = item; + + if (++tail == data.Length) + tail = 0; + + size ++; + version ++; + } + + public T [] ToArray () + { + T [] t = new T [size]; + CopyTo (t, 0); + return t; + } + public void TrimToSize () - { } - + { + SetCapacity (size); + } + + void SetCapacity (int new_size) + { + if (data != null && new_size == data.Length) + return; + + if (new_size < size) + throw new InvalidOperationException ("shouldnt happen"); + + T [] new_data = new T [new_size]; + if (size > 0) + CopyTo (new_data, 0); + + data = new_data; + tail = head = 0; + version ++; + } + public int Count { - get { return count; } + get { return size; } } - - public bool IsSynchronized { + + + bool ICollection .IsReadOnly { get { return false; } } - - public object SyncRoot { + + bool ICollection.IsSynchronized { + get { return false; } + } + + object ICollection.SyncRoot { get { return this; } } - - public bool IsReadOnly { - get { return false; } + + void ICollection .Add (T t) + { + Enqueue (t); } - - public void Add (T item) + + bool ICollection .Remove (T t) { - Enqueue (item); + throw new InvalidOperationException (""); } + - public bool Remove (T item) + public Enumerator GetEnumerator () { - throw new NotImplementedException (); + return new Enumerator (this); } - public IEnumerator GetEnumerator () + IEnumerator IEnumerable.GetEnumerator () { - return new Enumerator (this); + return GetEnumerator (); } IEnumerator IEnumerable.GetEnumerator () { - return new Enumerator (this); + return GetEnumerator (); } - - protected sealed class Node - { - public readonly T Item; - public readonly Node Next; - - public Node (Node next, T item) + + public struct Enumerator : IEnumerator , IEnumerator, 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; + + Queue q; + int idx; + int ver; + + internal Enumerator (Queue q) { - this.Next = next; - this.Item = item; + this.q = q; + idx = NOT_STARTED; + ver = q.version; } - } - - protected class Enumerator : IEnumerator, IEnumerator - { - Queue queue; - int modified; - Node current; - - public Enumerator (Queue queue) + + // 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 () { - this.queue = queue; - this.modified = queue.modified; - this.current = queue.head; + idx = NOT_STARTED; } - + + public bool MoveNext () + { + if (ver != q.version) + throw new InvalidOperationException (); + + if (idx == NOT_STARTED) + idx = q.size; + + return idx != FINISHED && -- idx != FINISHED; + } + public T Current { get { - if (queue.modified != modified) + if (idx < 0) throw new InvalidOperationException (); - if (current == null) - throw new ArgumentException (); - return current.Item; + + return q.data [(q.size - 1 - idx + q.head) % q.data.Length]; } } - - object IEnumerator.Current { - get { - return Current; - } - } - - public bool MoveNext () + + void IEnumerator.Reset () { - if (queue.modified != modified) + if (ver != q.version) throw new InvalidOperationException (); - if (current == null) - throw new ArgumentException (); - - current = current.Next; - return current != null; - } - - public void Reset () { - if (queue.modified != modified) - throw new InvalidOperationException(); - - current = queue.head; + + idx = NOT_STARTED; } - - public void Dispose () - { - modified = -1; + + object IEnumerator.Current { + get { return Current; } } + } } } -- 2.11.4.GIT