1// Licensed to the .NET Foundation under one or more agreements.
2// The .NET Foundation licenses this file to you under the MIT license.
3// See the LICENSE file in the project root for more information.
4
5//
6// ArrayStack: A stack, implemented as a growable array
7
8template <class T>
9class ArrayStack
10{
11 static const int builtinSize = 8;
12
13public:
14 ArrayStack(CompAllocator alloc, int initialCapacity = builtinSize) : m_alloc(alloc)
15 {
16 if (initialCapacity > builtinSize)
17 {
18 maxIndex = initialCapacity;
19 data = m_alloc.allocate<T>(initialCapacity);
20 }
21 else
22 {
23 maxIndex = builtinSize;
24 data = reinterpret_cast<T*>(builtinData);
25 }
26
27 tosIndex = 0;
28 }
29
30 void Push(T item)
31 {
32 if (tosIndex == maxIndex)
33 {
34 Realloc();
35 }
36
37 data[tosIndex] = item;
38 tosIndex++;
39 }
40
41 template <typename... Args>
42 void Emplace(Args&&... args)
43 {
44 if (tosIndex == maxIndex)
45 {
46 Realloc();
47 }
48
49 new (&data[tosIndex], jitstd::placement_t()) T(jitstd::forward<Args>(args)...);
50 tosIndex++;
51 }
52
53 void Realloc()
54 {
55 // get a new chunk 2x the size of the old one
56 // and copy over
57 T* oldData = data;
58 noway_assert(maxIndex * 2 > maxIndex);
59 data = m_alloc.allocate<T>(maxIndex * 2);
60 for (int i = 0; i < maxIndex; i++)
61 {
62 data[i] = oldData[i];
63 }
64 maxIndex *= 2;
65 }
66
67 T Pop()
68 {
69 assert(tosIndex > 0);
70 tosIndex--;
71 return data[tosIndex];
72 }
73
74 T Top()
75 {
76 assert(tosIndex > 0);
77 return data[tosIndex - 1];
78 }
79
80 T& TopRef()
81 {
82 assert(tosIndex > 0);
83 return data[tosIndex - 1];
84 }
85
86 // return the i'th from the top
87 T Index(int idx)
88 {
89 assert(tosIndex > idx);
90 return data[tosIndex - 1 - idx];
91 }
92
93 // return a reference to the i'th from the top
94 T& IndexRef(int idx)
95 {
96 assert(tosIndex > idx);
97 return data[tosIndex - 1 - idx];
98 }
99
100 int Height()
101 {
102 return tosIndex;
103 }
104
105 bool Empty()
106 {
107 return tosIndex == 0;
108 }
109
110 // return the bottom of the stack
111 T Bottom()
112 {
113 assert(tosIndex > 0);
114 return data[0];
115 }
116
117 // return the i'th from the bottom
118 T Bottom(int indx)
119 {
120 assert(tosIndex > indx);
121 return data[indx];
122 }
123
124 // return a reference to the i'th from the bottom
125 T BottomRef(int indx)
126 {
127 assert(tosIndex > indx);
128 return data[indx];
129 }
130
131 void Reset()
132 {
133 tosIndex = 0;
134 }
135
136private:
137 CompAllocator m_alloc;
138 int tosIndex; // first free location
139 int maxIndex;
140 T* data;
141 // initial allocation
142 char builtinData[builtinSize * sizeof(T)];
143};
144