src/jitcs_int_adt_heap.h

   1 //===-- evm/function.h - Class to represent a single basic block --*- C++ -*-===//
   2 //
   3 // A basicblock contains nodes, and must end in a terminal instruction node.
   4 // Nodes can be instructions, constants. Each node may produce more than one
   5 // result.
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #ifndef _JITCS_INT_ADT_HEAP_H_
  10 #define _JITCS_INT_ADT_HEAP_H_
  11
  12 #include "jitcs_base.h"
  13 #include "jitcs_adt_ref.h"
  14 #include <vector>
  15 #include <stdio.h>
  16
  17 namespace jitcs {
  18 // SmallTopHeap can store pairs of (IX, V), where IX is between 0 and N - 1,
  19 // and V is the values to be ordered by. In this case, the largest V is on top.
  20
  21 template <typename T>
  22 struct DefaultTopHeapTrait {
  23   typedef std::vector<T> ContainerType;
  24   typedef T ItemType;
  25   typedef typeof(T::value) ValueType;
  26   static size_t GetHeapPos(T t) { return t.heappos; }
  27   static ValueType GetValue(T t) { return t.value; }
  28   static void SetHeapPos(T& t, size_t pos) { t.heappos = pos; }
  29   static void PushBack(ContainerType& c, T t) { c.push_back(t); }
  30   static T PopBack(ContainerType& c) { T t = c.back(); c.pop_back(); return t; }
  31 };
  32
  33 template <typename T, typename TRAITS = DefaultTopHeapTrait<T>>
  34 struct TopHeap {
  35   typedef typename TRAITS::ContainerType ContainerType;
  36   typedef typename TRAITS::ItemType ItemType;
  37   typedef typename TRAITS::ValueType ValueType;
  38   ContainerType data;
  39
  40   TopHeap() {}
  41
  42   bool isEmpty() const { return data.size() == 0; }
  43
  44   bool check() const {
  45     // check that hpos is the reverse of heap
  46     for (size_t pos = 0; pos < data.size(); ++pos) {
  47       if (TRAITS::GetHeapPos(data[pos]) != pos) return false;
  48     }
  49     // check that parents are never smaller than their children
  50     for (size_t pos = data.size(); pos > 1;) {
  51       --pos;
  52       size_t ppos = (pos - 1) >> 1;
  53       if (TRAITS::GetValue(data[ppos]) < TRAITS::GetValue(data[pos]))
  54         return false;
  55     }
  56     return true;
  57   }
  58
  59   ItemType peekTop() const {
  60     _JITCS_DBG_CHECK_(!isEmpty());
  61     return data[0];
  62   }
  63   ValueType peekTopValue() const {
  64     _JITCS_DBG_CHECK_(!isEmpty());
  65     return TRAITS::GetValue(data[0]);
  66   }
  67   void push(ItemType i) {
  68     _JITCS_DBG_CHECK_(TRAITS::GetHeapPos(i) >= data.size()
  69                       || data[TRAITS::GetHeapPos(i)] != i);
  70     // add hole at end of storage space
  71     TRAITS::PushBack(data, i);
  72     unsigned pos = _moveHoleUp(data.size() - 1, TRAITS::GetValue(i));
  73     data[pos] = i;
  74     TRAITS::SetHeapPos(data[pos], pos);
  75   }
  76   ItemType dropTop() {
  77     _JITCS_DBG_CHECK_(!isEmpty());
  78     ItemType i = TRAITS::PopBack(data);
  79     if (!isEmpty()) {
  80       unsigned pos = _moveHoleDown(0, TRAITS::GetValue(i));
  81       data[pos] = i;
  82       TRAITS::SetHeapPos(data[pos], pos);
  83     }
  84     return i;
  85   }
  86   ItemType drop(ItemType j) {
  87     _JITCS_DBG_CHECK_(TRAITS::GetHeapPos(j) < data.size()
  88                       && data[TRAITS::GetHeapPos(j)] == j);
  89     ItemType i = TRAITS::PopBack(data);
  90     if (!isEmpty()) {
  91       ValueType val = TRAITS::GetValue(i);
  92       size_t pos = TRAITS::GetHeapPos(j);
  93       if (pos > 0 && TRAITS::GetValue(data[(pos - 1) >> 1]) < val) {
  94         pos = _moveHoleUp(pos, val);
  95       } else {
  96         pos = _moveHoleDown(pos, val);
  97       }
  98       data[pos] = i;
  99       TRAITS::SetHeapPos(data[pos], pos);
 100     }
 101     return j;
 102   }
 103 private:
 104   unsigned _moveHoleUp(unsigned pos, ValueType val) {
 105     // move hole up while the new value is larger than its parent
 106     while (pos > 0) {
 107       unsigned ppos = (pos - 1) >> 1;
 108       if (TRAITS::GetValue(data[ppos]) >= val) return pos;
 109       // swap parent with hole.
 110       data[pos] = data[ppos];
 111       TRAITS::SetHeapPos(data[pos], pos);
 112       pos = ppos;
 113     }
 114     return pos;
 115   }
 116   unsigned _moveHoleDown(unsigned pos, ValueType val) {
 117     // move hole up while the new value is larger than its parent
 118     size_t cpos = pos * 2 + 1, sz = data.size();
 119     while (cpos < sz) {
 120       if (cpos + 1 >= sz) {
 121         // only the "left" child. this also means, it's a leaf.
 122         if (TRAITS::GetValue(data[cpos]) > val) {
 123           data[pos] = data[cpos];
 124           TRAITS::SetHeapPos(data[pos], pos);
 125           pos = cpos;
 126         }
 127         return pos;
 128       }
 129       // both children available
 130       // choose the child with the bigger value. if both children's values
 131       // a below val, we are done.
 132       ValueType vpos = TRAITS::GetValue(data[cpos]),
 133                 vpos1 = TRAITS::GetValue(data[cpos + 1]);
 134       if (vpos1 > val) {
 135         if (vpos1 >= vpos) {
 136           // choose right child if it is greater than the left child
 137           ++cpos;
 138           vpos = vpos1;
 139         }
 140       } else {
 141         if (vpos <= val) return pos;
 142       }
 143       // swap child with hole.
 144       data[pos] = data[cpos];
 145       TRAITS::SetHeapPos(data[pos], pos);
 146       pos = cpos;
 147       cpos = pos * 2 + 1;
 148     }
 149     return pos;
 150   }
 151 };
 152
 153 } // end of jitcs namespace
 154
 155 #endif
 156 // _JITCS_INT_ADT_HEAP_H_