#include <stdint.h>

// See monton.S.  This is kind of a reimplementation.
typedef struct {
  int k;
  void *v;
} kvpair;

typedef struct node {
  struct node *left, *right;
  kvpair kv;
} node;

typedef struct snap {
  char *beta;                   // allocation pointer β
  struct node *root;
  struct snap *parent, *x;
} snap;

typedef snap *monton;

kvpair
peek(monton *s)
{
  return (*s)->root->kv;
}

void
restore(monton *s)
{
  *s = (*s)->parent;
}

node*
steal(snap *s, node *n)
{
  node *new = (node*)s->beta;
  s->beta += sizeof(*new);
  *new = *n;
  return new;
}

void
save(monton *s)
{
  snap *old = *s;
  snap *new = (snap*)old->beta;
  new->parent = old;
  new->beta = old->beta + sizeof(*new);
  new->root = steal(new, old->root);
  *s = new;
}
  
void
siftdown(snap *s, node *n)
{
  int k = n->kv.k, lk = n->left->kv.k, rk = n->right->kv.k;
  if (k < lk && k < rk) return;

  node *kid;
  if (lk < rk) {
    kid = n->left;
    if ((uintptr_t)kid < (uintptr_t)s) n->left = kid = steal(s, kid);
  } else {
    kid = n->right;
    if ((uintptr_t)kid < (uintptr_t)s) n->right = kid = steal(s, kid);
  }

  kvpair tmp = n->kv;
  n->kv = kid->kv;
  kid->kv = tmp;
  siftdown(s, kid);
}

void
kick(monton *s, int new_priority)
{
  snap *t = *s;
  node *root = t->root;
  root->kv.k = new_priority;
  siftdown(t, root);
}