-// -*- Mode: C; tab-width: 8; c-basic-offset: 8 -*-
//
// System.Collections.Stack
//
// (C) 2001 Garrett Rooney
//
-namespace System.Collections {
+//
+// Copyright (C) 2004 Novell, Inc (http://www.novell.com)
+//
+// Permission is hereby granted, free of charge, to any person obtaining
+// a copy of this software and associated documentation files (the
+// "Software"), to deal in the Software without restriction, including
+// without limitation the rights to use, copy, modify, merge, publish,
+// distribute, sublicense, and/or sell copies of the Software, and to
+// permit persons to whom the Software is furnished to do so, subject to
+// the following conditions:
+//
+// The above copyright notice and this permission notice shall be
+// included in all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
+// LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
+// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+//
+namespace System.Collections {
+ [Serializable]
+ [MonoTODO ("Fix serialization compatibility with MS.NET")]
public class Stack : ICollection, IEnumerable, ICloneable {
// properties
private object[] contents;
private int current = -1;
private int count = 0;
- private int capacity = 16;
-
- private bool readOnly = false;
- private bool synchronized = false;
+ private int capacity;
+ private int modCount = 0;
private void Resize(int ncapacity) {
+
+ ncapacity = Math.Max (ncapacity, 16);
object[] ncontents = new object[ncapacity];
- for (int i = 0; i < capacity; i++) {
- ncontents[i] = contents[i];
- }
+ Array.Copy(contents, ncontents, count);
capacity = ncapacity;
contents = ncontents;
}
- public Stack() {
- contents = new object[capacity];
- }
-
- public Stack(ICollection collection) {
- capacity = collection.Count;
- contents = new object[capacity];
- current = capacity - 1;
- count = capacity;
+ public Stack () : this (16) {}
- int i = 0;
- foreach (object o in collection) {
- contents[i++] = o;
- }
+ public Stack(ICollection col) : this (col == null ? 16 : col.Count) {
+ if (col == null)
+ throw new ArgumentNullException("col");
+
+ // We have to do this because msft seems to call the
+ // enumerator rather than CopyTo. This affects classes
+ // like bitarray.
+ foreach (object o in col)
+ Push (o);
}
- public Stack(int c) {
- capacity = c;
+ public Stack (int initialCapacity) {
+ if (initialCapacity < 0)
+ throw new ArgumentOutOfRangeException ("initialCapacity");
+
+ capacity = Math.Max (initialCapacity, 16);
contents = new object[capacity];
}
- // The Synchronized version of Stack uses lock(this) to make
- // it thread safe. This should be ok, even though we wrap an
- // Array, which is a Collection, since there is no way for the
- // outside world to get a reference to the Array. If I'm
- // wrong about this, then we should change lock(this) to
- // lock(contents.SyncRoot).
+ [Serializable]
private class SyncStack : Stack {
- public SyncStack(Stack s) {
- contents = s.contents;
- current = s.current;
- count = s.count;
- capacity = s.capacity;
- readOnly = s.readOnly;
- synchronized = true;
+ Stack stack;
+
+ internal SyncStack(Stack s) {
+ stack = s;
}
public override int Count {
- get { lock(this) { return count; } }
+ get {
+ lock (stack) {
+ return stack.Count;
+ }
+ }
}
+/*
public override bool IsReadOnly {
- get { lock(this) { return readOnly; } }
+ get {
+ lock (stack) {
+ return stack.IsReadOnly;
+ }
+ }
}
-
+*/
+
public override bool IsSynchronized {
- get { lock(this) { return synchronized; } }
+ get { return true; }
}
public override object SyncRoot {
- get { lock(this) { return this; } }
+ get { return stack.SyncRoot; }
}
public override void Clear() {
- lock(this) { base.Clear(); }
+ lock(stack) { stack.Clear(); }
}
public override object Clone() {
- lock (this) { return base.Clone(); }
+ lock (stack) {
+ return Stack.Synchronized((Stack)stack.Clone());
+ }
}
public override bool Contains(object obj) {
- lock (this) { return base.Contains(obj); }
+ lock (stack) { return stack.Contains(obj); }
}
public override void CopyTo(Array array, int index) {
- lock (this) { base.CopyTo(array, index); }
+ lock (stack) { stack.CopyTo(array, index); }
}
- // As noted above, this uses lock(this), and if that
- // turns out to be unsafe, it should be changed to
- // lock(contents.SyncRoot).
- private class SyncEnumerator : Enumerator {
-
- internal SyncEnumerator(Stack s) : base(s) {}
-
- public override object Current {
- get {
- lock (this) {
- return base.Current;
- }
- }
- }
-
- public override bool MoveNext() {
- lock (this) { return base.MoveNext(); }
- }
-
- public override void Reset() {
- lock (this) { base.Reset(); }
- }
- }
-
public override IEnumerator GetEnumerator() {
- lock (this) {
- return new SyncEnumerator(this);
+ lock (stack) {
+ return new Enumerator(stack);
}
}
public override object Peek() {
- lock (this) { return base.Peek(); }
+ lock (stack) { return stack.Peek(); }
}
public override object Pop() {
- lock (this) { return base.Pop(); }
+ lock (stack) { return stack.Pop(); }
}
public override void Push(object obj) {
- lock (this) { base.Push(obj); }
+ lock (stack) { stack.Push(obj); }
}
public override object[] ToArray() {
- lock (this) { return base.ToArray(); }
+ lock (stack) { return stack.ToArray(); }
}
}
- public static Stack Syncronized(Stack s) {
+ public static Stack Synchronized(Stack s) {
if (s == null) {
throw new ArgumentNullException();
}
get { return count; }
}
+/*
public virtual bool IsReadOnly {
- get { return readOnly; }
+ get { return false; }
}
+*/
public virtual bool IsSynchronized {
- get { return synchronized; }
+ get { return false; }
}
- // If using this for the SyncRoot is unsafe, we should use
- // contents.SyncRoot instead. I think this is ok though.
public virtual object SyncRoot {
get { return this; }
}
public virtual void Clear() {
+ modCount++;
+
for (int i = 0; i < count; i++) {
contents[i] = null;
}
}
public virtual object Clone() {
- Stack stack;
-
- if (synchronized == false) {
- stack = new Stack();
-
- stack.current = current;
- stack.contents = contents;
- stack.count = count;
- stack.capacity = capacity;
- stack.readOnly = readOnly;
- stack.synchronized = synchronized;
- } else {
- stack = new SyncStack(this);
- }
-
+ Stack stack = new Stack (contents);
+ stack.current = current;
+ stack.count = count;
return stack;
}
public virtual bool Contains(object obj) {
if (count == 0)
return false;
-
- for (int i = 0; i < count; i++) {
- if (contents[i].Equals(obj))
- return true;
+
+ if (obj == null) {
+ for (int i = 0; i < count; i++) {
+ if (contents[i] == null)
+ return true;
+ }
+ } else {
+ for (int i = 0; i < count; i++) {
+ if (obj.Equals (contents[i]))
+ return true;
+ }
}
return false;
public virtual void CopyTo (Array array, int index) {
if (array == null) {
- throw new ArgumentNullException();
+ throw new ArgumentNullException("array");
}
if (index < 0) {
- throw new ArgumentOutOfRangeException();
+ throw new ArgumentOutOfRangeException("index");
}
if (array.Rank > 1 ||
- index >= array.Length ||
+ array.Length > 0 && index >= array.Length ||
count > array.Length - index) {
throw new ArgumentException();
}
}
}
- // I made several methods of this class virtual, so that they
- // could be overriden by a thread safe version of the
- // Enumerator for use by SyncStack. I don't know if MS does
- // that in their implimentation, but it seemed like one should
- // reasonably be able to expect a thread safe Collection to
- // return a thread safe Enumerator. If this is a problem, it
- // could be ripped out. Realistically speaking, I doubt if
- // many people would ever notice if the Enumerator was thread
- // safe, as I cannot concieve of a situation where an
- // Enumerator would be accessed by more than one thread.
- private class Enumerator : IEnumerator {
-
- private Array contents;
+ private class Enumerator : IEnumerator, ICloneable {
+
+ const int EOF = -1;
+ const int BOF = -2;
+
+ Stack stack;
+ private int modCount;
private int current;
- private int count;
- private int begin;
internal Enumerator(Stack s) {
- // this is odd. it seems that you need to
- // start one further ahead than current, since
- // MoveNext() gets called first when using an
- // Enumeration...
- begin = s.current + 1;
- current = begin;
- count = s.count;
- contents = (Array) s.contents.Clone();
+ stack = s;
+ modCount = s.modCount;
+ current = BOF;
+ }
+
+ public object Clone ()
+ {
+ return MemberwiseClone ();
}
public virtual object Current {
get {
- if (current == -1 || current > count)
+ if (modCount != stack.modCount
+ || current == BOF
+ || current == EOF
+ || current > stack.count)
throw new InvalidOperationException();
- return contents.GetValue(current);
+ return stack.contents[current];
}
}
public virtual bool MoveNext() {
- if (current == -1) {
+ if (modCount != stack.modCount)
throw new InvalidOperationException();
- }
-
- current--;
-
- if (current == -1) {
+
+ switch (current) {
+ case BOF:
+ current = stack.current;
+ return current != -1;
+
+ case EOF:
return false;
- } else {
- return true;
+
+ default:
+ current--;
+ return current != -1;
}
}
public virtual void Reset() {
- // start one ahead of stack.current, so the
- // first MoveNext() will put us at the top
- current = begin;
+ if (modCount != stack.modCount) {
+ throw new InvalidOperationException();
+ }
+
+ current = BOF;
}
}
if (current == -1) {
throw new InvalidOperationException();
} else {
+ modCount++;
+
object ret = contents[current];
+ contents [current] = null;
count--;
current--;
-
+
+ // if we're down to capacity/4, go back to a
+ // lower array size. this should keep us from
+ // sucking down huge amounts of memory when
+ // putting large numbers of items in the Stack.
+ // if we're lower than 16, don't bother, since
+ // it will be more trouble than it's worth.
+ if (count <= (capacity/4) && count > 16) {
+ Resize(capacity/2);
+ }
+
return ret;
}
}
- // FIXME: We should probably be a bit smarter about our
- // resizing. After a certain point, doubling isn't that smart.
- // We just need to find out what that point is...
public virtual void Push(Object o) {
+ modCount++;
+
if (capacity == count) {
Resize(capacity * 2);
}
}
}
}
-
projects / mono.git / blobdiff