heap.c

   1 #include "dat.h"
   2 #include <stdint.h>
   3 #include <stdlib.h>
   4 #include <string.h>
   5
   6
   7 static void
   8 set(Heap *h, size_t k, void *x)
   9 {
  10     h->data[k] = x;
  11     h->setpos(x, k);
  12 }
  13
  14
  15 static void
  16 swap(Heap *h, size_t a, size_t b)
  17 {
  18     void *tmp;
  19
  20     tmp = h->data[a];
  21     set(h, a, h->data[b]);
  22     set(h, b, tmp);
  23 }
  24
  25
  26 static int
  27 less(Heap *h, size_t a, size_t b)
  28 {
  29     return h->less(h->data[a], h->data[b]);
  30 }
  31
  32
  33 static void
  34 siftdown(Heap *h, size_t k)
  35 {
  36     for (;;) {
  37         size_t p = (k-1) / 2; /* parent */
  38
  39         if (k == 0 || less(h, p, k)) {
  40             return;
  41         }
  42
  43         swap(h, k, p);
  44         k = p;
  45     }
  46 }
  47
  48
  49 static void
  50 siftup(Heap *h, size_t k)
  51 {
  52     for (;;) {
  53         size_t l = k*2 + 1; /* left child */
  54         size_t r = k*2 + 2; /* right child */
  55
  56         /* find the smallest of the three */
  57         size_t s = k;
  58         if (l < h->len && less(h, l, s)) s = l;
  59         if (r < h->len && less(h, r, s)) s = r;
  60
  61         if (s == k) {
  62             return; /* satisfies the heap property */
  63         }
  64
  65         swap(h, k, s);
  66         k = s;
  67     }
  68 }
  69
  70
  71 // Heapinsert inserts x into heap h according to h->less.
  72 // It returns 1 on success, otherwise 0.
  73 int
  74 heapinsert(Heap *h, void *x)
  75 {
  76     if (h->len == h->cap) {
  77         void **ndata;
  78         size_t ncap = (h->len+1) * 2; /* allocate twice what we need */
  79
  80         ndata = malloc(sizeof(void*) * ncap);
  81         if (!ndata) {
  82             return 0;
  83         }
  84
  85         memcpy(ndata, h->data, sizeof(void*) * h->len);
  86         free(h->data);
  87         h->data = ndata;
  88         h->cap = ncap;
  89     }
  90
  91     size_t k = h->len;
  92     h->len++;
  93     set(h, k, x);
  94     siftdown(h, k);
  95     return 1;
  96 }
  97
  98
  99 void *
 100 heapremove(Heap *h, size_t k)
 101 {
 102     if (k >= h->len) {
 103         return 0;
 104     }
 105
 106     void *x = h->data[k];
 107     h->len--;
 108     set(h, k, h->data[h->len]);
 109     siftdown(h, k);
 110     siftup(h, k);
 111     return x;
 112 }