|
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
using System.Diagnostics;
using System.Diagnostics.CodeAnalysis;
using System.Runtime.CompilerServices;
namespace System.Collections.Generic
{
/// <summary>
/// Represents a first-in, first-out collection of objects.
/// </summary>
/// <remarks>
/// Implemented as a circular buffer, so <see cref="Enqueue(T)"/> and <see cref="Dequeue"/> are typically <c>O(1)</c>.
/// </remarks>
[DebuggerTypeProxy(typeof(QueueDebugView<>))]
[DebuggerDisplay("Count = {Count}")]
[Serializable]
[TypeForwardedFrom("System, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089")]
public class Queue<T> : IEnumerable<T>,
ICollection,
IReadOnlyCollection<T>
{
private T[] _array;
private int _head; // The index from which to dequeue if the queue isn't empty.
private int _tail; // The index at which to enqueue if the queue isn't full.
private int _size; // Number of elements.
private int _version;
// Creates a queue with room for capacity objects. The default initial
// capacity and grow factor are used.
public Queue()
{
_array = Array.Empty<T>();
}
// Creates a queue with room for capacity objects. The default grow factor
// is used.
public Queue(int capacity)
{
ArgumentOutOfRangeException.ThrowIfNegative(capacity);
_array = new T[capacity];
}
// Fills a Queue with the elements of an ICollection. Uses the enumerator
// to get each of the elements.
public Queue(IEnumerable<T> collection)
{
ArgumentNullException.ThrowIfNull(collection);
_array = EnumerableHelpers.ToArray(collection, out _size);
if (_size != _array.Length) _tail = _size;
}
public int Count => _size;
/// <summary>
/// Gets the total numbers of elements the internal data structure can hold without resizing.
/// </summary>
public int Capacity => _array.Length;
/// <inheritdoc cref="ICollection{T}"/>
bool ICollection.IsSynchronized => false;
object ICollection.SyncRoot => this;
// Removes all Objects from the queue.
public void Clear()
{
if (_size != 0)
{
if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
{
if (_head < _tail)
{
Array.Clear(_array, _head, _size);
}
else
{
Array.Clear(_array, _head, _array.Length - _head);
Array.Clear(_array, 0, _tail);
}
}
_size = 0;
}
_head = 0;
_tail = 0;
_version++;
}
// CopyTo copies a collection into an Array, starting at a particular
// index into the array.
public void CopyTo(T[] array, int arrayIndex)
{
ArgumentNullException.ThrowIfNull(array);
if (arrayIndex < 0 || arrayIndex > array.Length)
{
throw new ArgumentOutOfRangeException(nameof(arrayIndex), arrayIndex, SR.ArgumentOutOfRange_IndexMustBeLessOrEqual);
}
if (array.Length - arrayIndex < _size)
{
throw new ArgumentException(SR.Argument_InvalidOffLen);
}
int numToCopy = _size;
if (numToCopy == 0) return;
int firstPart = Math.Min(_array.Length - _head, numToCopy);
Array.Copy(_array, _head, array, arrayIndex, firstPart);
numToCopy -= firstPart;
if (numToCopy > 0)
{
Array.Copy(_array, 0, array, arrayIndex + _array.Length - _head, numToCopy);
}
}
void ICollection.CopyTo(Array array, int index)
{
ArgumentNullException.ThrowIfNull(array);
if (array.Rank != 1)
{
throw new ArgumentException(SR.Arg_RankMultiDimNotSupported, nameof(array));
}
if (array.GetLowerBound(0) != 0)
{
throw new ArgumentException(SR.Arg_NonZeroLowerBound, nameof(array));
}
int arrayLen = array.Length;
if (index < 0 || index > arrayLen)
{
throw new ArgumentOutOfRangeException(nameof(index), index, SR.ArgumentOutOfRange_IndexMustBeLessOrEqual);
}
if (arrayLen - index < _size)
{
throw new ArgumentException(SR.Argument_InvalidOffLen);
}
int numToCopy = _size;
if (numToCopy == 0) return;
try
{
int firstPart = (_array.Length - _head < numToCopy) ? _array.Length - _head : numToCopy;
Array.Copy(_array, _head, array, index, firstPart);
numToCopy -= firstPart;
if (numToCopy > 0)
{
Array.Copy(_array, 0, array, index + _array.Length - _head, numToCopy);
}
}
catch (ArrayTypeMismatchException)
{
throw new ArgumentException(SR.Argument_IncompatibleArrayType, nameof(array));
}
}
// Adds item to the tail of the queue.
public void Enqueue(T item)
{
if (_size == _array.Length)
{
Grow(_size + 1);
}
_array[_tail] = item;
MoveNext(ref _tail);
_size++;
_version++;
}
// GetEnumerator returns an IEnumerator over this Queue. This
// Enumerator will support removing.
public Enumerator GetEnumerator() => new Enumerator(this);
/// <internalonly/>
IEnumerator<T> IEnumerable<T>.GetEnumerator() =>
Count == 0 ? SZGenericArrayEnumerator<T>.Empty :
GetEnumerator();
IEnumerator IEnumerable.GetEnumerator() => ((IEnumerable<T>)this).GetEnumerator();
// Removes the object at the head of the queue and returns it. If the queue
// is empty, this method throws an
// InvalidOperationException.
public T Dequeue()
{
int head = _head;
T[] array = _array;
if (_size == 0)
{
ThrowForEmptyQueue();
}
T removed = array[head];
if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
{
array[head] = default!;
}
MoveNext(ref _head);
_size--;
_version++;
return removed;
}
public bool TryDequeue([MaybeNullWhen(false)] out T result)
{
int head = _head;
T[] array = _array;
if (_size == 0)
{
result = default;
return false;
}
result = array[head];
if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
{
array[head] = default!;
}
MoveNext(ref _head);
_size--;
_version++;
return true;
}
// Returns the object at the head of the queue. The object remains in the
// queue. If the queue is empty, this method throws an
// InvalidOperationException.
public T Peek()
{
if (_size == 0)
{
ThrowForEmptyQueue();
}
return _array[_head];
}
public bool TryPeek([MaybeNullWhen(false)] out T result)
{
if (_size == 0)
{
result = default;
return false;
}
result = _array[_head];
return true;
}
// Returns true if the queue contains at least one object equal to item.
// Equality is determined using EqualityComparer<T>.Default.Equals().
public bool Contains(T item)
{
if (_size == 0)
{
return false;
}
if (_head < _tail)
{
return Array.IndexOf(_array, item, _head, _size) >= 0;
}
// We've wrapped around. Check both partitions, the least recently enqueued first.
return
Array.IndexOf(_array, item, _head, _array.Length - _head) >= 0 ||
Array.IndexOf(_array, item, 0, _tail) >= 0;
}
// Iterates over the objects in the queue, returning an array of the
// objects in the Queue, or an empty array if the queue is empty.
// The order of elements in the array is first in to last in, the same
// order produced by successive calls to Dequeue.
public T[] ToArray()
{
if (_size == 0)
{
return Array.Empty<T>();
}
T[] arr = new T[_size];
if (_head < _tail)
{
Array.Copy(_array, _head, arr, 0, _size);
}
else
{
Array.Copy(_array, _head, arr, 0, _array.Length - _head);
Array.Copy(_array, 0, arr, _array.Length - _head, _tail);
}
return arr;
}
// PRIVATE Grows or shrinks the buffer to hold capacity objects. Capacity
// must be >= _size.
private void SetCapacity(int capacity)
{
Debug.Assert(capacity >= _size);
T[] newarray = new T[capacity];
if (_size > 0)
{
if (_head < _tail)
{
Array.Copy(_array, _head, newarray, 0, _size);
}
else
{
Array.Copy(_array, _head, newarray, 0, _array.Length - _head);
Array.Copy(_array, 0, newarray, _array.Length - _head, _tail);
}
}
_array = newarray;
_head = 0;
_tail = (_size == capacity) ? 0 : _size;
_version++;
}
// Increments the index wrapping it if necessary.
private void MoveNext(ref int index)
{
// It is tempting to use the remainder operator here but it is actually much slower
// than a simple comparison and a rarely taken branch.
// JIT produces better code than with ternary operator ?:
int tmp = index + 1;
if (tmp == _array.Length)
{
tmp = 0;
}
index = tmp;
}
private void ThrowForEmptyQueue()
{
Debug.Assert(_size == 0);
throw new InvalidOperationException(SR.InvalidOperation_EmptyQueue);
}
public void TrimExcess()
{
int threshold = (int)(_array.Length * 0.9);
if (_size < threshold)
{
SetCapacity(_size);
}
}
/// <summary>
/// Sets the capacity of a <see cref="Queue{T}"/> object to the specified number of entries.
/// </summary>
/// <param name="capacity">The new capacity.</param>
/// <exception cref="ArgumentOutOfRangeException">Passed capacity is lower than entries count.</exception>
public void TrimExcess(int capacity)
{
ArgumentOutOfRangeException.ThrowIfNegative(capacity);
ArgumentOutOfRangeException.ThrowIfLessThan(capacity, _size);
if (capacity == _array.Length)
return;
SetCapacity(capacity);
}
/// <summary>
/// Ensures that the capacity of this Queue is at least the specified <paramref name="capacity"/>.
/// </summary>
/// <param name="capacity">The minimum capacity to ensure.</param>
/// <returns>The new capacity of this queue.</returns>
public int EnsureCapacity(int capacity)
{
ArgumentOutOfRangeException.ThrowIfNegative(capacity);
if (_array.Length < capacity)
{
Grow(capacity);
}
return _array.Length;
}
private void Grow(int capacity)
{
Debug.Assert(_array.Length < capacity);
const int GrowFactor = 2;
const int MinimumGrow = 4;
int newcapacity = GrowFactor * _array.Length;
// Allow the list to grow to maximum possible capacity (~2G elements) before encountering overflow.
// Note that this check works even when _items.Length overflowed thanks to the (uint) cast
if ((uint)newcapacity > Array.MaxLength) newcapacity = Array.MaxLength;
// Ensure minimum growth is respected.
newcapacity = Math.Max(newcapacity, _array.Length + MinimumGrow);
// If the computed capacity is still less than specified, set to the original argument.
// Capacities exceeding Array.MaxLength will be surfaced as OutOfMemoryException by Array.Resize.
if (newcapacity < capacity) newcapacity = capacity;
SetCapacity(newcapacity);
}
// Implements an enumerator for a Queue. The enumerator uses the
// internal version number of the list to ensure that no modifications are
// made to the list while an enumeration is in progress.
public struct Enumerator : IEnumerator<T>,
IEnumerator
{
private readonly Queue<T> _q;
private readonly int _version;
private int _index; // -1 = not started, -2 = ended/disposed
private T? _currentElement;
internal Enumerator(Queue<T> q)
{
_q = q;
_version = q._version;
_index = -1;
_currentElement = default;
}
public void Dispose()
{
_index = -2;
_currentElement = default;
}
public bool MoveNext()
{
if (_version != _q._version) throw new InvalidOperationException(SR.InvalidOperation_EnumFailedVersion);
if (_index == -2)
return false;
_index++;
if (_index == _q._size)
{
// We've run past the last element
_index = -2;
_currentElement = default;
return false;
}
// Cache some fields in locals to decrease code size
T[] array = _q._array;
uint capacity = (uint)array.Length;
// _index represents the 0-based index into the queue, however the queue
// doesn't have to start from 0 and it may not even be stored contiguously in memory.
uint arrayIndex = (uint)(_q._head + _index); // this is the actual index into the queue's backing array
if (arrayIndex >= capacity)
{
// NOTE: Originally we were using the modulo operator here, however
// on Intel processors it has a very high instruction latency which
// was slowing down the loop quite a bit.
// Replacing it with simple comparison/subtraction operations sped up
// the average foreach loop by 2x.
arrayIndex -= capacity; // wrap around if needed
}
_currentElement = array[arrayIndex];
return true;
}
public T Current
{
get
{
if (_index < 0)
ThrowEnumerationNotStartedOrEnded();
return _currentElement!;
}
}
private void ThrowEnumerationNotStartedOrEnded()
{
Debug.Assert(_index == -1 || _index == -2);
throw new InvalidOperationException(_index == -1 ? SR.InvalidOperation_EnumNotStarted : SR.InvalidOperation_EnumEnded);
}
object? IEnumerator.Current
{
get { return Current; }
}
void IEnumerator.Reset()
{
if (_version != _q._version) throw new InvalidOperationException(SR.InvalidOperation_EnumFailedVersion);
_index = -1;
_currentElement = default;
}
}
}
}
|