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