blob: b193036a262955c3aa776be6b4b09fe49105cef0 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
|
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.
/*============================================================
**
**
** Private version of Stack<T> for internal System.Private.CoreLib use. This
** permits sharing more source between BCL and System.Private.CoreLib (as well as the
** fact that Stack<T> is just a useful class in general.)
**
** This does not strive to implement the full api surface area
** (but any portion it does implement should match the real Stack<T>'s
** behavior.)
**
===========================================================*/
namespace System.Collections.Generic
{
// Implements a variable-size Stack that uses an array of objects to store the
// elements. A Stack has a capacity, which is the allocated length
// of the internal array. As elements are added to a Stack, the capacity
// of the Stack is automatically increased as required by reallocating the
// internal array.
//
/// <summary>
/// LowLevelStack with no interface implementation to minimize both code and data size
/// Data size is smaller because there will be minimal virtual function table.
/// Code size is smaller because only functions called will be in the binary.
/// </summary>
internal class LowLevelStack<T>
{
protected T[] _items;
protected int _size;
protected int _version;
private static readonly T[] s_emptyArray = new T[0];
public LowLevelStack()
{
_items = s_emptyArray;
}
public LowLevelStack(int capacity)
{
if (capacity < 0)
throw new ArgumentOutOfRangeException(nameof(capacity));
if (capacity == 0)
_items = s_emptyArray;
else
{
_size = capacity;
_items = new T[capacity];
}
}
public LowLevelStack(IEnumerable<T> collection)
{
if (collection == null)
throw new ArgumentNullException(nameof(collection));
ICollection<T> c = collection as ICollection<T>;
if (c != null)
{
int count = c.Count;
if (count == 0)
{
_items = s_emptyArray;
}
else
{
_items = new T[count];
c.CopyTo(_items, 0);
_size = count;
}
}
else
{
_size = 0;
_items = s_emptyArray;
using (IEnumerator<T> en = collection.GetEnumerator())
{
while (en.MoveNext())
{
Push(en.Current);
}
}
}
}
public int Count
{
get
{
return _items.Length;
}
}
public void Push(T item)
{
_size = _size + 1;
Array.Resize(ref _items, _size);
_items[_size - 1] = item;
_version++;
}
public T Pop()
{
ThrowIfEmptyStack();
_size = _size - 1;
T item = _items[_size];
Array.Resize(ref _items, _size);
_version++;
return item;
}
public bool TryPop(out T result)
{
if (_size == 0)
{
result = default;
return false;
}
_size = _size - 1;
result = _items[_size];
Array.Resize(ref _items, _size);
_version++;
return true;
}
public T Peek()
{
ThrowIfEmptyStack();
return _items[_size - 1];
}
public bool TryPeek(out T result)
{
if (_size == 0)
{
result = default;
return false;
}
result = _items[_size - 1];
_version++;
return true;
}
private void ThrowIfEmptyStack()
{
if (_size == 0)
throw new InvalidOperationException();
}
}
}
|
