1 files changed, 133 insertions, 0 deletions
diff --git a/src/jit/arraystack.h b/src/jit/arraystack.h
new file mode 100644
index 0000000000..8693fe8f24
--- /dev/null
+++ b/src/jit/arraystack.h
@@ -0,0 +1,133 @@
+//
+// Copyright (c) Microsoft. All rights reserved.
+// Licensed under the MIT license. See LICENSE file in the project root for full license information.
+//
+
+//
+// ArrayStack: A stack, implemented as a growable array
+
+template <class T>
+class ArrayStack
+{
+    static const int builtinSize = 8;
+    
+public:
+    ArrayStack(Compiler *comp, int initialSize = builtinSize)
+    {
+        compiler = comp;
+
+        if (initialSize > builtinSize)
+        {
+            maxIndex = initialSize;
+            data = new(compiler, CMK_ArrayStack) T[initialSize];
+        }
+        else
+        {
+            maxIndex = builtinSize;
+            data = builtinData;
+        }
+
+        tosIndex = 0;
+    }
+
+    void Push(T item)
+    {
+        if (tosIndex == maxIndex)
+            Realloc();
+        
+        data[tosIndex] = item;
+        tosIndex++;
+    }
+
+    void Realloc()
+    {
+        // get a new chunk 2x the size of the old one
+        // and copy over
+        T* oldData = data;
+        noway_assert(maxIndex*2 > maxIndex);
+        data = new(compiler, CMK_ArrayStack) T[maxIndex*2];
+        for (int i=0; i<maxIndex; i++)
+        {
+            data[i] = oldData[i];
+        }
+        maxIndex *= 2;
+    }
+
+    // reverse the top N in the stack
+    void ReverseTop(int number)
+    {
+        if (number < 2)
+            return;
+
+        assert(number <= tosIndex);
+
+        int start = tosIndex - number;
+        int offset = 0;
+        while (offset < number/2)
+        {
+            T temp;
+            int index = start+offset;
+            int otherIndex = tosIndex - 1 - offset;
+            temp = data[index];
+            data[index] = data[otherIndex];
+            data[otherIndex] = temp;
+
+            offset++;
+        }
+    }
+
+    T Pop()
+    {
+        assert(tosIndex > 0);
+        tosIndex--;
+        return data[tosIndex];
+    }
+
+    T Top()
+    {
+        assert(tosIndex > 0);
+        return data[tosIndex-1];
+    }
+
+    // return the i'th from the top
+    T Index(int idx)
+    {
+        assert(tosIndex > idx);
+        return data[tosIndex - 1 - idx];
+    }
+
+    int Height()
+    {
+        return tosIndex;
+    }
+
+    // return the bottom of the stack
+    T Bottom()
+    {
+        assert(tosIndex > 0);
+        return data[0];
+    }
+
+    // return the i'th from the bottom
+    T Bottom(int indx)
+    {
+        assert(tosIndex > indx);
+        return data[indx];
+    }
+
+    void Reset()
+    {
+        tosIndex = 0;
+    }
+
+private:
+    Compiler *compiler; // needed for allocation
+    int tosIndex; // first free location
+    int maxIndex;
+    T* data;
+    // initial allocation
+    T builtinData[builtinSize]; 
+};
+    
+
+