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

  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: Queue
  18. **
  19. ** Purpose: A circular-array implementation of a queue.
  20. **
  21. **
  22. =============================================================================*/
  23. namespace System.Collections
  24. {
  25.     using System;
  26.     using System.Security.Permissions;
  27.     using System.Diagnostics;
  28.    
  29.     // A simple Queue of objects. Internally it is implemented as a circular
  30.     // buffer, so Enqueue can be O(n). Dequeue is O(1).
  31.     [DebuggerTypeProxy(typeof(System.Collections.Queue.QueueDebugView))]
  32.     [DebuggerDisplay("Count = {Count}")]
  33.     [System.Runtime.InteropServices.ComVisible(true)]
  34.     [Serializable()]
  35.     public class Queue : ICollection, ICloneable
  36.     {
  37.         private object[] _array;
  38.         private int _head;
  39.         // First valid element in the queue
  40.         private int _tail;
  41.         // Last valid element in the queue
  42.         private int _size;
  43.         // Number of elements.
  44.         private int _growFactor;
  45.         // 100 == 1.0, 130 == 1.3, 200 == 2.0
  46.         private int _version;
  47.         [NonSerialized()]
  48.         private object _syncRoot;
  49.        
  50.         private const int _MinimumGrow = 4;
  51.         private const int _ShrinkThreshold = 32;
  52.        
  53.         // Creates a queue with room for capacity objects. The default initial
  54.         // capacity and grow factor are used.
  55.         public Queue() : this(32, (float)2.0)
  56.         {
  57.         }
  58.        
  59.         // Creates a queue with room for capacity objects. The default grow factor
  60.         // is used.
  61.         //
  62.         public Queue(int capacity) : this(capacity, (float)2.0)
  63.         {
  64.         }
  65.        
  66.         // Creates a queue with room for capacity objects. When full, the new
  67.         // capacity is set to the old capacity * growFactor.
  68.         //
  69.         public Queue(int capacity, float growFactor)
  70.         {
  71.             if (capacity < 0)
  72.                 throw new ArgumentOutOfRangeException("capacity", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
  73.             if (!(growFactor >= 1.0 && growFactor <= 10.0))
  74.                 throw new ArgumentOutOfRangeException("growFactor", Environment.GetResourceString("ArgumentOutOfRange_QueueGrowFactor", 1, 10));
  75.            
  76.             _array = new object[capacity];
  77.             _head = 0;
  78.             _tail = 0;
  79.             _size = 0;
  80.             _growFactor = (int)(growFactor * 100);
  81.         }
  82.        
  83.         // Fills a Queue with the elements of an ICollection. Uses the enumerator
  84.         // to get each of the elements.
  85.         //
  86.         public Queue(ICollection col) : this((col == null ? 32 : col.Count))
  87.         {
  88.             if (col == null)
  89.                 throw new ArgumentNullException("col");
  90.             IEnumerator en = col.GetEnumerator();
  91.             while (en.MoveNext())
  92.                 Enqueue(en.Current);
  93.         }
  94.        
  95.        
  96.         public virtual int Count {
  97.             get { return _size; }
  98.         }
  99.        
  100.         public virtual object Clone()
  101.         {
  102.             Queue q = new Queue(_size);
  103.             q._size = _size;
  104.            
  105.             int numToCopy = _size;
  106.             int firstPart = (_array.Length - _head < numToCopy) ? _array.Length - _head : numToCopy;
  107.             Array.Copy(_array, _head, q._array, 0, firstPart);
  108.             numToCopy -= firstPart;
  109.             if (numToCopy > 0)
  110.                 Array.Copy(_array, 0, q._array, _array.Length - _head, numToCopy);
  111.            
  112.             q._version = _version;
  113.             return q;
  114.         }
  115.        
  116.         public virtual bool IsSynchronized {
  117.             get { return false; }
  118.         }
  119.        
  120.         public virtual object SyncRoot {
  121.             get {
  122.                 if (_syncRoot == null) {
  123.                     System.Threading.Interlocked.CompareExchange(ref _syncRoot, new object(), null);
  124.                 }
  125.                 return _syncRoot;
  126.             }
  127.         }
  128.        
  129.         // Removes all Objects from the queue.
  130.         public virtual void Clear()
  131.         {
  132.             if (_head < _tail)
  133.                 Array.Clear(_array, _head, _size);
  134.             else {
  135.                 Array.Clear(_array, _head, _array.Length - _head);
  136.                 Array.Clear(_array, 0, _tail);
  137.             }
  138.            
  139.             _head = 0;
  140.             _tail = 0;
  141.             _size = 0;
  142.             _version++;
  143.         }
  144.        
  145.         // CopyTo copies a collection into an Array, starting at a particular
  146.         // index into the array.
  147.         //
  148.         public virtual void CopyTo(Array array, int index)
  149.         {
  150.             if (array == null)
  151.                 throw new ArgumentNullException("array");
  152.             if (array.Rank != 1)
  153.                 throw new ArgumentException(Environment.GetResourceString("Arg_RankMultiDimNotSupported"));
  154.             if (index < 0)
  155.                 throw new ArgumentOutOfRangeException("index", Environment.GetResourceString("ArgumentOutOfRange_Index"));
  156.             int arrayLen = array.Length;
  157.             if (arrayLen - index < _size)
  158.                 throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen"));
  159.            
  160.             int numToCopy = _size;
  161.             if (numToCopy == 0)
  162.                 return;
  163.             int firstPart = (_array.Length - _head < numToCopy) ? _array.Length - _head : numToCopy;
  164.             Array.Copy(_array, _head, array, index, firstPart);
  165.             numToCopy -= firstPart;
  166.             if (numToCopy > 0)
  167.                 Array.Copy(_array, 0, array, index + _array.Length - _head, numToCopy);
  168.         }
  169.        
  170.         // Adds obj to the tail of the queue.
  171.         //
  172.         public virtual void Enqueue(object obj)
  173.         {
  174.             if (_size == _array.Length) {
  175.                 int newcapacity = (int)((long)_array.Length * (long)_growFactor / 100);
  176.                 if (newcapacity < _array.Length + _MinimumGrow) {
  177.                     newcapacity = _array.Length + _MinimumGrow;
  178.                 }
  179.                 SetCapacity(newcapacity);
  180.             }
  181.            
  182.             _array[_tail] = obj;
  183.             _tail = (_tail + 1) % _array.Length;
  184.             _size++;
  185.             _version++;
  186.         }
  187.        
  188.         // GetEnumerator returns an IEnumerator over this Queue. This
  189.         // Enumerator will support removing.
  190.         //
  191.         public virtual IEnumerator GetEnumerator()
  192.         {
  193.             return new QueueEnumerator(this);
  194.         }
  195.        
  196.         // Removes the object at the head of the queue and returns it. If the queue
  197.         // is empty, this method simply returns null.
  198.         public virtual object Dequeue()
  199.         {
  200.             if (_size == 0)
  201.                 throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EmptyQueue"));
  202.            
  203.             object removed = _array[_head];
  204.             _array[_head] = null;
  205.             _head = (_head + 1) % _array.Length;
  206.             _size--;
  207.             _version++;
  208.             return removed;
  209.         }
  210.        
  211.         // Returns the object at the head of the queue. The object remains in the
  212.         // queue. If the queue is empty, this method throws an
  213.         // InvalidOperationException.
  214.         public virtual object Peek()
  215.         {
  216.             if (_size == 0)
  217.                 throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EmptyQueue"));
  218.            
  219.             return _array[_head];
  220.         }
  221.        
  222.         // Returns a synchronized Queue. Returns a synchronized wrapper
  223.         // class around the queue - the caller must not use references to the
  224.         // original queue.
  225.         //
  226.         [HostProtection(Synchronization = true)]
  227.         public static Queue Synchronized(Queue queue)
  228.         {
  229.             if (queue == null)
  230.                 throw new ArgumentNullException("queue");
  231.             return new SynchronizedQueue(queue);
  232.         }
  233.        
  234.         // Returns true if the queue contains at least one object equal to obj.
  235.         // Equality is determined using obj.Equals().
  236.         //
  237.         // Exceptions: ArgumentNullException if obj == null.
  238.         public virtual bool Contains(object obj)
  239.         {
  240.             int index = _head;
  241.             int count = _size;
  242.            
  243.             while (count-- > 0) {
  244.                 if (obj == null) {
  245.                     if (_array[index] == null)
  246.                         return true;
  247.                 }
  248.                 else if (_array[index] != null && _array[index].Equals(obj)) {
  249.                     return true;
  250.                 }
  251.                 index = (index + 1) % _array.Length;
  252.             }
  253.            
  254.             return false;
  255.         }
  256.        
  257.         internal object GetElement(int i)
  258.         {
  259.             return _array[(_head + i) % _array.Length];
  260.         }
  261.        
  262.         // Iterates over the objects in the queue, returning an array of the
  263.         // objects in the Queue, or an empty array if the queue is empty.
  264.         // The order of elements in the array is first in to last in, the same
  265.         // order produced by successive calls to Dequeue.
  266.         public virtual object[] ToArray()
  267.         {
  268.             object[] arr = new object[_size];
  269.             if (_size == 0)
  270.                 return arr;
  271.            
  272.             if (_head < _tail) {
  273.                 Array.Copy(_array, _head, arr, 0, _size);
  274.             }
  275.             else {
  276.                 Array.Copy(_array, _head, arr, 0, _array.Length - _head);
  277.                 Array.Copy(_array, 0, arr, _array.Length - _head, _tail);
  278.             }
  279.            
  280.             return arr;
  281.         }
  282.        
  283.        
  284.         // PRIVATE Grows or shrinks the buffer to hold capacity objects. Capacity
  285.         // must be >= _size.
  286.         private void SetCapacity(int capacity)
  287.         {
  288.             object[] newarray = new object[capacity];
  289.             if (_size > 0) {
  290.                 if (_head < _tail) {
  291.                     Array.Copy(_array, _head, newarray, 0, _size);
  292.                 }
  293.                 else {
  294.                     Array.Copy(_array, _head, newarray, 0, _array.Length - _head);
  295.                     Array.Copy(_array, 0, newarray, _array.Length - _head, _tail);
  296.                 }
  297.             }
  298.            
  299.             _array = newarray;
  300.             _head = 0;
  301.             _tail = (_size == capacity) ? 0 : _size;
  302.             _version++;
  303.         }
  304.        
  305.         public virtual void TrimToSize()
  306.         {
  307.             SetCapacity(_size);
  308.         }
  309.        
  310.        
  311.         // Implements a synchronization wrapper around a queue.
  312.         [Serializable()]
  313.         private class SynchronizedQueue : Queue
  314.         {
  315.             private Queue _q;
  316.             private object root;
  317.            
  318.             internal SynchronizedQueue(Queue q)
  319.             {
  320.                 this._q = q;
  321.                 root = _q.SyncRoot;
  322.             }
  323.            
  324.             public override bool IsSynchronized {
  325.                 get { return true; }
  326.             }
  327.            
  328.             public override object SyncRoot {
  329.                 get { return root; }
  330.             }
  331.            
  332.             public override int Count {
  333.                 get {
  334.                     lock (root) {
  335.                         return _q.Count;
  336.                     }
  337.                 }
  338.             }
  339.            
  340.             public override void Clear()
  341.             {
  342.                 lock (root) {
  343.                     _q.Clear();
  344.                 }
  345.             }
  346.            
  347.             public override object Clone()
  348.             {
  349.                 lock (root) {
  350.                     return new SynchronizedQueue((Queue)_q.Clone());
  351.                 }
  352.             }
  353.            
  354.             public override bool Contains(object obj)
  355.             {
  356.                 lock (root) {
  357.                     return _q.Contains(obj);
  358.                 }
  359.             }
  360.            
  361.             public override void CopyTo(Array array, int arrayIndex)
  362.             {
  363.                 lock (root) {
  364.                     _q.CopyTo(array, arrayIndex);
  365.                 }
  366.             }
  367.            
  368.             public override void Enqueue(object value)
  369.             {
  370.                 lock (root) {
  371.                     _q.Enqueue(value);
  372.                 }
  373.             }
  374.            
  375.             public override object Dequeue()
  376.             {
  377.                 lock (root) {
  378.                     return _q.Dequeue();
  379.                 }
  380.             }
  381.            
  382.             public override IEnumerator GetEnumerator()
  383.             {
  384.                 lock (root) {
  385.                     return _q.GetEnumerator();
  386.                 }
  387.             }
  388.            
  389.             public override object Peek()
  390.             {
  391.                 lock (root) {
  392.                     return _q.Peek();
  393.                 }
  394.             }
  395.            
  396.             public override object[] ToArray()
  397.             {
  398.                 lock (root) {
  399.                     return _q.ToArray();
  400.                 }
  401.             }
  402.            
  403.             public override void TrimToSize()
  404.             {
  405.                 lock (root) {
  406.                     _q.TrimToSize();
  407.                 }
  408.             }
  409.         }
  410.        
  411.        
  412.         // Implements an enumerator for a Queue. The enumerator uses the
  413.         // internal version number of the list to ensure that no modifications are
  414.         // made to the list while an enumeration is in progress.
  415.         [Serializable()]
  416.         private class QueueEnumerator : IEnumerator, ICloneable
  417.         {
  418.             private Queue _q;
  419.             private int _index;
  420.             private int _version;
  421.             private object currentElement;
  422.            
  423.             internal QueueEnumerator(Queue q)
  424.             {
  425.                 _q = q;
  426.                 _version = _q._version;
  427.                 _index = 0;
  428.                 currentElement = _q._array;
  429.                 if (_q._size == 0)
  430.                     _index = -1;
  431.             }
  432.            
  433.             public object Clone()
  434.             {
  435.                 return MemberwiseClone();
  436.             }
  437.            
  438.             public virtual bool MoveNext()
  439.             {
  440.                 if (_version != _q._version)
  441.                     throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumFailedVersion));
  442.                
  443.                 if (_index < 0) {
  444.                     currentElement = _q._array;
  445.                     return false;
  446.                 }
  447.                
  448.                 currentElement = _q.GetElement(_index);
  449.                 _index++;
  450.                
  451.                 if (_index == _q._size)
  452.                     _index = -1;
  453.                 return true;
  454.             }
  455.            
  456.             public virtual object Current {
  457.                 get {
  458.                     if (currentElement == _q._array) {
  459.                         if (_index == 0)
  460.                             throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumNotStarted));
  461.                         else
  462.                             throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumEnded));
  463.                     }
  464.                     return currentElement;
  465.                 }
  466.             }
  467.            
  468.             public virtual void Reset()
  469.             {
  470.                 if (_version != _q._version)
  471.                     throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumFailedVersion));
  472.                 if (_q._size == 0)
  473.                     _index = -1;
  474.                 else
  475.                     _index = 0;
  476.                 currentElement = _q._array;
  477.             }
  478.         }
  479.        
  480.         internal class QueueDebugView
  481.         {
  482.             private Queue queue;
  483.            
  484.             public QueueDebugView(Queue queue)
  485.             {
  486.                 if (queue == null)
  487.                     throw new ArgumentNullException("queue");
  488.                
  489.                 this.queue = queue;
  490.             }
  491.            
  492.             [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
  493.             public object[] Items {
  494.                 get { return queue.ToArray(); }
  495.             }
  496.         }
  497.     }
  498. }

Developer Fusion