The Labs \ Source Viewer \ SSCLI \ System.Collections \ SyncStack

  1. // ==++==
  2. //
  3. //
  4. // Copyright (c) 2006 Microsoft Corporation. All rights reserved.
  5. //
  6. // The use and distribution terms for this software are contained in the file
  7. // named license.txt, which can be found in the root of this distribution.
  8. // By using this software in any fashion, you are agreeing to be bound by the
  9. // terms of this license.
  10. //
  11. // You must not remove this notice, or any other, from this software.
  12. //
  13. //
  14. // ==--==
  15. /*=============================================================================
  16. **
  17. ** Class: Stack
  18. **
  19. ** Purpose: An array implementation of a stack.
  20. **
  21. **
  22. =============================================================================*/
  23. namespace System.Collections
  24. {
  25.     using System;
  26.     using System.Security.Permissions;
  27.     using System.Diagnostics;
  28.    
  29.     // A simple stack of objects. Internally it is implemented as an array,
  30.     // so Push can be O(n). Pop is O(1).
  31.     [DebuggerTypeProxy(typeof(System.Collections.Stack.StackDebugView))]
  32.     [DebuggerDisplay("Count = {Count}")]
  33.     [System.Runtime.InteropServices.ComVisible(true)]
  34.     [Serializable()]
  35.     public class Stack : ICollection, ICloneable
  36.     {
  37.         private object[] _array;
  38.         // Storage for stack elements
  39.         private int _size;
  40.         // Number of items in the stack.
  41.         private int _version;
  42.         // Used to keep enumerator in sync w/ collection.
  43.         [NonSerialized()]
  44.         private object _syncRoot;
  45.        
  46.         private const int _defaultCapacity = 10;
  47.        
  48.         public Stack()
  49.         {
  50.             _array = new object[_defaultCapacity];
  51.             _size = 0;
  52.             _version = 0;
  53.         }
  54.        
  55.         // Create a stack with a specific initial capacity. The initial capacity
  56.         // must be a non-negative number.
  57.         public Stack(int initialCapacity)
  58.         {
  59.             if (initialCapacity < 0)
  60.                 throw new ArgumentOutOfRangeException("initialCapacity", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
  61.             if (initialCapacity < _defaultCapacity)
  62.                 initialCapacity = _defaultCapacity;
  63.             // Simplify doubling logic in Push.
  64.             _array = new object[initialCapacity];
  65.             _size = 0;
  66.             _version = 0;
  67.         }
  68.        
  69.         // Fills a Stack with the contents of a particular collection. The items are
  70.         // pushed onto the stack in the same order they are read by the enumerator.
  71.         //
  72.         public Stack(ICollection col) : this((col == null ? 32 : col.Count))
  73.         {
  74.             if (col == null)
  75.                 throw new ArgumentNullException("col");
  76.             IEnumerator en = col.GetEnumerator();
  77.             while (en.MoveNext())
  78.                 Push(en.Current);
  79.         }
  80.        
  81.         public virtual int Count {
  82.             get { return _size; }
  83.         }
  84.        
  85.         public virtual bool IsSynchronized {
  86.             get { return false; }
  87.         }
  88.        
  89.         public virtual object SyncRoot {
  90.             get {
  91.                 if (_syncRoot == null) {
  92.                     System.Threading.Interlocked.CompareExchange(ref _syncRoot, new object(), null);
  93.                 }
  94.                 return _syncRoot;
  95.             }
  96.         }
  97.        
  98.         // Removes all Objects from the Stack.
  99.         public virtual void Clear()
  100.         {
  101.             Array.Clear(_array, 0, _size);
  102.             // Don't need to doc this but we clear the elements so that the gc can reclaim the references.
  103.             _size = 0;
  104.             _version++;
  105.         }
  106.        
  107.         public virtual object Clone()
  108.         {
  109.             Stack s = new Stack(_size);
  110.             s._size = _size;
  111.             Array.Copy(_array, 0, s._array, 0, _size);
  112.             s._version = _version;
  113.             return s;
  114.         }
  115.        
  116.         public virtual bool Contains(object obj)
  117.         {
  118.             int count = _size;
  119.            
  120.             while (count-- > 0) {
  121.                 if (obj == null) {
  122.                     if (_array[count] == null)
  123.                         return true;
  124.                 }
  125.                 else if (_array[count] != null && _array[count].Equals(obj)) {
  126.                     return true;
  127.                 }
  128.             }
  129.             return false;
  130.         }
  131.        
  132.         // Copies the stack into an array.
  133.         public virtual void CopyTo(Array array, int index)
  134.         {
  135.             if (array == null)
  136.                 throw new ArgumentNullException("array");
  137.             if (array.Rank != 1)
  138.                 throw new ArgumentException(Environment.GetResourceString("Arg_RankMultiDimNotSupported"));
  139.             if (index < 0)
  140.                 throw new ArgumentOutOfRangeException("index", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
  141.             if (array.Length - index < _size)
  142.                 throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen"));
  143.            
  144.             int i = 0;
  145.             if (array is object[]) {
  146.                 object[] objArray = (object[])array;
  147.                 while (i < _size) {
  148.                     objArray[i + index] = _array[_size - i - 1];
  149.                     i++;
  150.                 }
  151.             }
  152.             else {
  153.                 while (i < _size) {
  154.                     array.SetValue(_array[_size - i - 1], i + index);
  155.                     i++;
  156.                 }
  157.             }
  158.         }
  159.        
  160.         // Returns an IEnumerator for this Stack.
  161.         public virtual IEnumerator GetEnumerator()
  162.         {
  163.             return new StackEnumerator(this);
  164.         }
  165.        
  166.         // Returns the top object on the stack without removing it. If the stack
  167.         // is empty, Peek throws an InvalidOperationException.
  168.         public virtual object Peek()
  169.         {
  170.             if (_size == 0)
  171.                 throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EmptyStack"));
  172.             return _array[_size - 1];
  173.         }
  174.        
  175.         // Pops an item from the top of the stack. If the stack is empty, Pop
  176.         // throws an InvalidOperationException.
  177.         public virtual object Pop()
  178.         {
  179.             if (_size == 0)
  180.                 throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EmptyStack"));
  181.             _version++;
  182.             object obj = _array[--_size];
  183.             _array[_size] = null;
  184.             // Free memory quicker.
  185.             return obj;
  186.         }
  187.        
  188.         // Pushes an item to the top of the stack.
  189.         //
  190.         public virtual void Push(object obj)
  191.         {
  192.             if (_size == _array.Length) {
  193.                 object[] newArray = new object[2 * _array.Length];
  194.                 Array.Copy(_array, 0, newArray, 0, _size);
  195.                 _array = newArray;
  196.             }
  197.             _array[_size++] = obj;
  198.             _version++;
  199.         }
  200.        
  201.         // Returns a synchronized Stack.
  202.         //
  203.         [HostProtection(Synchronization = true)]
  204.         public static Stack Synchronized(Stack stack)
  205.         {
  206.             if (stack == null)
  207.                 throw new ArgumentNullException("stack");
  208.             return new SyncStack(stack);
  209.         }
  210.        
  211.        
  212.         // Copies the Stack to an array, in the same order Pop would return the items.
  213.         public virtual object[] ToArray()
  214.         {
  215.             object[] objArray = new object[_size];
  216.             int i = 0;
  217.             while (i < _size) {
  218.                 objArray[i] = _array[_size - i - 1];
  219.                 i++;
  220.             }
  221.             return objArray;
  222.         }
  223.        
  224.         [Serializable()]
  225.         private class SyncStack : Stack
  226.         {
  227.             private Stack _s;
  228.             private object _root;
  229.            
  230.             internal SyncStack(Stack stack)
  231.             {
  232.                 _s = stack;
  233.                 _root = stack.SyncRoot;
  234.             }
  235.            
  236.             public override bool IsSynchronized {
  237.                 get { return true; }
  238.             }
  239.            
  240.             public override object SyncRoot {
  241.                 get { return _root; }
  242.             }
  243.            
  244.             public override int Count {
  245.                 get {
  246.                     lock (_root) {
  247.                         return _s.Count;
  248.                     }
  249.                 }
  250.             }
  251.            
  252.             public override bool Contains(object obj)
  253.             {
  254.                 lock (_root) {
  255.                     return _s.Contains(obj);
  256.                 }
  257.             }
  258.            
  259.             public override object Clone()
  260.             {
  261.                 lock (_root) {
  262.                     return new SyncStack((Stack)_s.Clone());
  263.                 }
  264.             }
  265.            
  266.             public override void Clear()
  267.             {
  268.                 lock (_root) {
  269.                     _s.Clear();
  270.                 }
  271.             }
  272.            
  273.             public override void CopyTo(Array array, int arrayIndex)
  274.             {
  275.                 lock (_root) {
  276.                     _s.CopyTo(array, arrayIndex);
  277.                 }
  278.             }
  279.            
  280.             public override void Push(object value)
  281.             {
  282.                 lock (_root) {
  283.                     _s.Push(value);
  284.                 }
  285.             }
  286.            
  287.             public override object Pop()
  288.             {
  289.                 lock (_root) {
  290.                     return _s.Pop();
  291.                 }
  292.             }
  293.            
  294.             public override IEnumerator GetEnumerator()
  295.             {
  296.                 lock (_root) {
  297.                     return _s.GetEnumerator();
  298.                 }
  299.             }
  300.            
  301.             public override object Peek()
  302.             {
  303.                 lock (_root) {
  304.                     return _s.Peek();
  305.                 }
  306.             }
  307.            
  308.             public override object[] ToArray()
  309.             {
  310.                 lock (_root) {
  311.                     return _s.ToArray();
  312.                 }
  313.             }
  314.         }
  315.        
  316.        
  317.         [Serializable()]
  318.         private class StackEnumerator : IEnumerator, ICloneable
  319.         {
  320.             private Stack _stack;
  321.             private int _index;
  322.             private int _version;
  323.             private object currentElement;
  324.            
  325.             internal StackEnumerator(Stack stack)
  326.             {
  327.                 _stack = stack;
  328.                 _version = _stack._version;
  329.                 _index = -2;
  330.                 currentElement = null;
  331.             }
  332.            
  333.             public object Clone()
  334.             {
  335.                 return MemberwiseClone();
  336.             }
  337.            
  338.             public virtual bool MoveNext()
  339.             {
  340.                 bool retval;
  341.                 if (_version != _stack._version)
  342.                     throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumFailedVersion));
  343.                 if (_index == -2) {
  344.                     // First call to enumerator.
  345.                     _index = _stack._size - 1;
  346.                     retval = (_index >= 0);
  347.                     if (retval)
  348.                         currentElement = _stack._array[_index];
  349.                     return retval;
  350.                 }
  351.                 if (_index == -1) {
  352.                     // End of enumeration.
  353.                     return false;
  354.                 }
  355.                
  356.                 retval = (--_index >= 0);
  357.                 if (retval)
  358.                     currentElement = _stack._array[_index];
  359.                 else
  360.                     currentElement = null;
  361.                 return retval;
  362.             }
  363.            
  364.             public virtual object Current {
  365.                 get {
  366.                     if (_index == -2)
  367.                         throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumNotStarted));
  368.                     if (_index == -1)
  369.                         throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumEnded));
  370.                     return currentElement;
  371.                 }
  372.             }
  373.            
  374.             public virtual void Reset()
  375.             {
  376.                 if (_version != _stack._version)
  377.                     throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumFailedVersion));
  378.                 _index = -2;
  379.                 currentElement = null;
  380.             }
  381.         }
  382.        
  383.         internal class StackDebugView
  384.         {
  385.             private Stack stack;
  386.            
  387.             public StackDebugView(Stack stack)
  388.             {
  389.                 if (stack == null)
  390.                     throw new ArgumentNullException("stack");
  391.                
  392.                 this.stack = stack;
  393.             }
  394.            
  395.             [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
  396.             public object[] Items {
  397.                 get { return stack.ToArray(); }
  398.             }
  399.         }
  400.     }
  401. }

Developer Fusion