src/jitcs_int_adt_smallheap.h

   1 //===-- src/jitcs_int_adt_smallheap.h ---------------------------*- C++ -*-===//
   2 // A binary heap object with a limited size.
   3 //
   4 // Copyright (C) 2013-2014 Dirk Steinke.
   5 // See copyright and license notice in COPYRIGHT or include/jitcs.h
   6 //
   7 // While currently unused, it might be used in the register allocator.
   8 // The choice of which register to spill seems to fit this ADT perfectly.
   9 //===----------------------------------------------------------------------===//
  10
  11 #ifndef _JITCS_INT_ADT_SMALLHEAP_H_
  12 #define _JITCS_INT_ADT_SMALLHEAP_H_
  13
  14 #include "jitcs_base.h"
  15 #include "jitcs_adt_ref.h"
  16
  17 #include <stdio.h>
  18
  19 namespace jitcs {
  20 // SmallTopHeap can store pairs of (IX, V), where IX is between 0 and N - 1,
  21 // and V is the values to be ordered by. In this case, the largest V is on top.
  22
  23 // TODO: add RELIABLE way of checking if an item is on the heap or not
  24 // the current way is WAY too fishy
  25 template <typename VAL, unsigned N, bool ORDERVAL>
  26 struct SmallTopHeap {
  27   static const unsigned NUM = N;
  28   typedef typename std::conditional<N <= 256, u8,
  29                    typename std::conditional<N <= 65536, u16,
  30                             u32>::type>::type IxType;
  31   // heap ordered storage area: POS -> IX
  32   IxType heap[N];
  33   // reverse lookup: IX -> POS
  34   IxType hpos[N];
  35   // values to be ordered by:
  36   // this is: IX -> VAL if !ORDERVAL, POS -> VAL if ORDERVAL
  37   VAL values[N];
  38   unsigned size;
  39
  40   SmallTopHeap() : size(0) {
  41   }
  42
  43   bool isEmpty() const { return size == 0; }
  44   bool isFull() const { return size == N; }
  45
  46   bool check() const {
  47     // check that hpos is the reverse of heap
  48     for (u32 pos = 0; pos < size; ++pos) {
  49       if (hpos[heap[pos]] != pos) return false;
  50     }
  51     // check that parents are never smaller than their children
  52     for (u32 pos = size; pos > 1;) {
  53       --pos;
  54       unsigned ppos = (pos - 1) >> 1;
  55       if (_val(ppos) < _val(pos)) return false;
  56     }
  57     return true;
  58   }
  59
  60   IxType peekTop() const {
  61     _JITCS_DBG_CHECK_(!isEmpty());
  62     return heap[0];
  63   }
  64   VAL peekTopValue() const {
  65     _JITCS_DBG_CHECK_(!isEmpty());
  66     return _val(0);
  67   }
  68   void push(unsigned ix, VAL val) {
  69     _JITCS_DBG_CHECK_(ix < N);
  70     _JITCS_DBG_CHECK_(!isFull());
  71     // add hole at end of storage space
  72     unsigned pos = _moveHoleUp(size++, val);
  73     values[ORDERVAL ? pos : ix] = val;
  74     heap[pos] = ix;
  75     hpos[ix] = pos;
  76   }
  77   void dropTop() {
  78     _JITCS_DBG_CHECK_(!isEmpty());
  79     if (!--size) return;
  80     VAL val = _val(size);
  81     unsigned pos = _moveHoleDown(0, val);
  82     if (ORDERVAL) values[pos] = val;
  83     heap[pos] = heap[size];
  84     hpos[heap[pos]] = pos;
  85   }
  86   void drop(unsigned ix) {
  87     _JITCS_DBG_CHECK_(ix < N);
  88     _JITCS_DBG_CHECK_(heap[hpos[ix]] == ix);
  89     if (!--size) return;
  90     VAL val = _val(size);
  91     u32 pos = hpos[ix];
  92     if (pos > 0 && _val((pos - 1) >> 1) < val) {
  93       pos = _moveHoleUp(pos, val);
  94     } else {
  95       pos = _moveHoleDown(pos, val);
  96     }
  97     if (ORDERVAL) values[pos] = val;
  98     heap[pos] = heap[size];
  99     hpos[heap[pos]] = pos;
 100   }
 101 private:
 102   const VAL& _val(unsigned pos) const {
 103     return (ORDERVAL ? values[pos] : values[heap[pos]]);
 104   }
 105   unsigned _moveHoleUp(unsigned pos, VAL val) {
 106     // move hole up while the new value is larger than its parent
 107     while (pos > 0) {
 108       unsigned ppos = (pos - 1) >> 1;
 109       if (_val(ppos) >= val) return pos;
 110       // swap parent with hole.
 111       if (ORDERVAL) values[pos] = values[ppos];
 112       heap[pos] = heap[ppos];
 113       hpos[heap[pos]] = pos;
 114       pos = ppos;
 115     }
 116     return pos;
 117   }
 118   unsigned _moveHoleDown(unsigned pos, VAL val) {
 119     // move hole up while the new value is larger than its parent
 120     unsigned cpos = pos * 2 + 1;
 121     while (cpos < size) {
 122       if (cpos + 1 >= size) {
 123         // only the "left" child. this also means, it's a leaf.
 124         if (_val(cpos) > val) {
 125           if (ORDERVAL) values[pos] = values[cpos];
 126           heap[pos] = heap[cpos];
 127           hpos[heap[pos]] = pos;
 128           pos = cpos;
 129         }
 130         return pos;
 131       }
 132       // both children available
 133       // choose the child with the bigger value. if both children's values
 134       // a below val, we are done.
 135       VAL vpos = _val(cpos), vpos1 = _val(cpos + 1);
 136       if (vpos1 > val) {
 137         if (vpos1 >= vpos) {
 138           // choose right child if it is greater than the left child
 139           ++cpos;
 140           vpos = vpos1;
 141         }
 142       } else {
 143         if (vpos <= val) return pos;
 144       }
 145       // swap child with hole.
 146       if (ORDERVAL) values[pos] = vpos;
 147       heap[pos] = heap[cpos];
 148       hpos[heap[pos]] = pos;
 149       pos = cpos;
 150       cpos = pos * 2 + 1;
 151     }
 152     return pos;
 153   }
 154 };
 155
 156
 157 } // end of jitcs namespace
 158
 159 #endif
 160 // _JITCS_INT_ADT_SMALLHEAP_H_