Decompiled System.Collections.Generic.Queue<T>

Queue.cs

// Type: System.Collections.Generic.Queue`1
// Assembly: System, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089
// Assembly location: C:\Windows\Microsoft.NET\Framework\v4.0.30319\System.dll

using System;
using System.Collections;
using System.Diagnostics;
using System.Runtime;
using System.Runtime.InteropServices;
using System.Threading;

namespace System.Collections.Generic
{
  [DebuggerTypeProxy(typeof (System_QueueDebugView<>))]
  [ComVisible(false)]
  [DebuggerDisplay("Count = {Count}")]
  [Serializable]
  public class Queue<T> : IEnumerable<T>, ICollection, IEnumerable
  {
    private static T[] _emptyArray = new T[0];
    private T[] _array;
    private int _head;
    private int _tail;
    private int _size;
    private int _version;
    [NonSerialized]
    private object _syncRoot;
    private const int _MinimumGrow = 4;
    private const int _ShrinkThreshold = 32;
    private const int _GrowFactor = 200;
    private const int _DefaultCapacity = 4;

    public int Count
    {
      [TargetedPatchingOptOut("Performance critical to inline this type of method across NGen image boundaries")] get
      {
        return this._size;
      }
    }

    bool ICollection.IsSynchronized
    {
      get
      {
        return false;
      }
    }

    object ICollection.SyncRoot
    {
      get
      {
        if (this._syncRoot == null)
          Interlocked.CompareExchange<object>(ref this._syncRoot, new object(), (object) null);
        return this._syncRoot;
      }
    }

    static Queue()
    {
    }

    public Queue()
    {
      this._array = Queue<T>._emptyArray;
    }

    public Queue(int capacity)
    {
      if (capacity < 0)
        ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity, ExceptionResource.ArgumentOutOfRange_NeedNonNegNumRequired);
      this._array = new T[capacity];
      this._head = 0;
      this._tail = 0;
      this._size = 0;
    }

    public Queue(IEnumerable<T> collection)
    {
      if (collection == null)
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);
      this._array = new T[4];
      this._size = 0;
      this._version = 0;
      foreach (T obj in collection)
        this.Enqueue(obj);
    }

    public void Clear()
    {
      if (this._head < this._tail)
      {
        Array.Clear((Array) this._array, this._head, this._size);
      }
      else
      {
        Array.Clear((Array) this._array, this._head, this._array.Length - this._head);
        Array.Clear((Array) this._array, 0, this._tail);
      }
      this._head = 0;
      this._tail = 0;
      this._size = 0;
      ++this._version;
    }

    public void CopyTo(T[] array, int arrayIndex)
    {
      if (array == null)
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
      if (arrayIndex < 0 || arrayIndex > array.Length)
        ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.arrayIndex, ExceptionResource.ArgumentOutOfRange_Index);
      int length1 = array.Length;
      if (length1 - arrayIndex < this._size)
        ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
      int num = length1 - arrayIndex < this._size ? length1 - arrayIndex : this._size;
      if (num == 0)
        return;
      int length2 = this._array.Length - this._head < num ? this._array.Length - this._head : num;
      Array.Copy((Array) this._array, this._head, (Array) array, arrayIndex, length2);
      int length3 = num - length2;
      if (length3 <= 0)
        return;
      Array.Copy((Array) this._array, 0, (Array) array, arrayIndex + this._array.Length - this._head, length3);
    }

    void ICollection.CopyTo(Array array, int index)
    {
      if (array == null)
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
      if (array.Rank != 1)
        ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported);
      if (array.GetLowerBound(0) != 0)
        ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NonZeroLowerBound);
      int length1 = array.Length;
      if (index < 0 || index > length1)
        ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index);
      if (length1 - index < this._size)
        ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
      int num = length1 - index < this._size ? length1 - index : this._size;
      if (num == 0)
        return;
      try
      {
        int length2 = this._array.Length - this._head < num ? this._array.Length - this._head : num;
        Array.Copy((Array) this._array, this._head, array, index, length2);
        int length3 = num - length2;
        if (length3 <= 0)
          return;
        Array.Copy((Array) this._array, 0, array, index + this._array.Length - this._head, length3);
      }
      catch (ArrayTypeMismatchException ex)
      {
        ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType);
      }
    }

    public void Enqueue(T item)
    {
      if (this._size == this._array.Length)
      {
        int capacity = (int) ((long) this._array.Length * 200L / 100L);
        if (capacity < this._array.Length + 4)
          capacity = this._array.Length + 4;
        this.SetCapacity(capacity);
      }
      this._array[this._tail] = item;
      this._tail = (this._tail + 1) % this._array.Length;
      ++this._size;
      ++this._version;
    }

    public Queue<T>.Enumerator GetEnumerator()
    {
      return new Queue<T>.Enumerator(this);
    }

    IEnumerator<T> IEnumerable<T>.GetEnumerator()
    {
      return (IEnumerator<T>) new Queue<T>.Enumerator(this);
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
      return (IEnumerator) new Queue<T>.Enumerator(this);
    }

    public T Dequeue()
    {
      if (this._size == 0)
        ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EmptyQueue);
      T obj = this._array[this._head];
      this._array[this._head] = default (T);
      this._head = (this._head + 1) % this._array.Length;
      --this._size;
      ++this._version;
      return obj;
    }

    public T Peek()
    {
      if (this._size == 0)
        ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EmptyQueue);
      return this._array[this._head];
    }

    public bool Contains(T item)
    {
      int index = this._head;
      int num = this._size;
      EqualityComparer<T> @default = EqualityComparer<T>.Default;
      while (num-- > 0)
      {
        if ((object) item == null)
        {
          if ((object) this._array[index] == null)
            return true;
        }
        else if ((object) this._array[index] != null && @default.Equals(this._array[index], item))
          return true;
        index = (index + 1) % this._array.Length;
      }
      return false;
    }

    internal T GetElement(int i)
    {
      return this._array[(this._head + i) % this._array.Length];
    }

    public T[] ToArray()
    {
      T[] objArray = new T[this._size];
      if (this._size == 0)
        return objArray;
      if (this._head < this._tail)
      {
        Array.Copy((Array) this._array, this._head, (Array) objArray, 0, this._size);
      }
      else
      {
        Array.Copy((Array) this._array, this._head, (Array) objArray, 0, this._array.Length - this._head);
        Array.Copy((Array) this._array, 0, (Array) objArray, this._array.Length - this._head, this._tail);
      }
      return objArray;
    }

    private void SetCapacity(int capacity)
    {
      T[] objArray = new T[capacity];
      if (this._size > 0)
      {
        if (this._head < this._tail)
        {
          Array.Copy((Array) this._array, this._head, (Array) objArray, 0, this._size);
        }
        else
        {
          Array.Copy((Array) this._array, this._head, (Array) objArray, 0, this._array.Length - this._head);
          Array.Copy((Array) this._array, 0, (Array) objArray, this._array.Length - this._head, this._tail);
        }
      }
      this._array = objArray;
      this._head = 0;
      this._tail = this._size == capacity ? 0 : this._size;
      ++this._version;
    }

    public void TrimExcess()
    {
      if (this._size >= (int) ((double) this._array.Length * 0.9))
        return;
      this.SetCapacity(this._size);
    }

    [Serializable]
    public struct Enumerator : IEnumerator<T>, IDisposable, IEnumerator
    {
      private Queue<T> _q;
      private int _index;
      private int _version;
      private T _currentElement;

      public T Current
      {
        get
        {
          if (this._index < 0)
          {
            if (this._index == -1)
              ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumNotStarted);
            else
              ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumEnded);
          }
          return this._currentElement;
        }
      }

      object IEnumerator.Current
      {
        get
        {
          if (this._index < 0)
          {
            if (this._index == -1)
              ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumNotStarted);
            else
              ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumEnded);
          }
          return (object) this._currentElement;
        }
      }

      internal Enumerator(Queue<T> q)
      {
        this._q = q;
        this._version = this._q._version;
        this._index = -1;
        this._currentElement = default (T);
      }

      public void Dispose()
      {
        this._index = -2;
        this._currentElement = default (T);
      }

      public bool MoveNext()
      {
        if (this._version != this._q._version)
          ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
        if (this._index == -2)
          return false;
        ++this._index;
        if (this._index == this._q._size)
        {
          this._index = -2;
          this._currentElement = default (T);
          return false;
        }
        else
        {
          this._currentElement = this._q.GetElement(this._index);
          return true;
        }
      }

      void IEnumerator.Reset()
      {
        if (this._version != this._q._version)
          ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
        this._index = -1;
        this._currentElement = default (T);
      }
    }
  }
}