src/jit/arraystack.h

   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
   8 template <class T>
   9 class ArrayStack
  10 {
  11     static const int builtinSize = 8;
  12
  13 public:
  14     ArrayStack(Compiler *comp, int initialSize = builtinSize)
  15     {
  16         compiler = comp;
  17
  18         if (initialSize > builtinSize)
  19         {
  20             maxIndex = initialSize;
  21             data = new(compiler, CMK_ArrayStack) T[initialSize];
  22         }
  23         else
  24         {
  25             maxIndex = builtinSize;
  26             data = builtinData;
  27         }
  28
  29         tosIndex = 0;
  30     }
  31
  32     void Push(T item)
  33     {
  34         if (tosIndex == maxIndex)
  35             Realloc();
  36
  37         data[tosIndex] = item;
  38         tosIndex++;
  39     }
  40
  41     void Realloc()
  42     {
  43         // get a new chunk 2x the size of the old one
  44         // and copy over
  45         T* oldData = data;
  46         noway_assert(maxIndex*2 > maxIndex);
  47         data = new(compiler, CMK_ArrayStack) T[maxIndex*2];
  48         for (int i=0; i<maxIndex; i++)
  49         {
  50             data[i] = oldData[i];
  51         }
  52         maxIndex *= 2;
  53     }
  54
  55     // reverse the top N in the stack
  56     void ReverseTop(int number)
  57     {
  58         if (number < 2)
  59             return;
  60
  61         assert(number <= tosIndex);
  62
  63         int start = tosIndex - number;
  64         int offset = 0;
  65         while (offset < number/2)
  66         {
  67             T temp;
  68             int index = start+offset;
  69             int otherIndex = tosIndex - 1 - offset;
  70             temp = data[index];
  71             data[index] = data[otherIndex];
  72             data[otherIndex] = temp;
  73
  74             offset++;
  75         }
  76     }
  77
  78     T Pop()
  79     {
  80         assert(tosIndex > 0);
  81         tosIndex--;
  82         return data[tosIndex];
  83     }
  84
  85     T Top()
  86     {
  87         assert(tosIndex > 0);
  88         return data[tosIndex-1];
  89     }
  90
  91     T& TopRef()
  92     {
  93         assert(tosIndex > 0);
  94         return data[tosIndex-1];
  95     }
  96
  97     // return the i'th from the top
  98     T Index(int idx)
  99     {
 100         assert(tosIndex > idx);
 101         return data[tosIndex - 1 - idx];
 102     }
 103
 104     // return a reference to the i'th from the top
 105     T& IndexRef(int idx)
 106     {
 107         assert(tosIndex > idx);
 108         return data[tosIndex - 1 - idx];
 109     }
 110
 111     int Height()
 112     {
 113         return tosIndex;
 114     }
 115
 116     // return the bottom of the stack
 117     T Bottom()
 118     {
 119         assert(tosIndex > 0);
 120         return data[0];
 121     }
 122
 123     // return the i'th from the bottom
 124     T Bottom(int indx)
 125     {
 126         assert(tosIndex > indx);
 127         return data[indx];
 128     }
 129
 130     void Reset()
 131     {
 132         tosIndex = 0;
 133     }
 134
 135 private:
 136     Compiler *compiler; // needed for allocation
 137     int tosIndex; // first free location
 138     int maxIndex;
 139     T* data;
 140     // initial allocation
 141     T builtinData[builtinSize];
 142 };
 143
 144
 145