heap.c

   1 /* Copyright (C) 2007 Keith Rarick and Philotic Inc.
   2  * Copyright 2011 Keith Rarick
   3
   4  * This program is free software: you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation, either version 3 of the License, or
   7  * (at your option) any later version.
   8
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  16  */
  17
  18 #include <stdint.h>
  19 #include <stdlib.h>
  20 #include <string.h>
  21 #include "dat.h"
  22
  23
  24 static void
  25 set(Heap *h, int k, void *x)
  26 {
  27     h->data[k] = x;
  28     h->rec(x, k);
  29 }
  30
  31
  32 static void
  33 swap(Heap *h, int a, int b)
  34 {
  35     void *tmp;
  36
  37     tmp = h->data[a];
  38     set(h, a, h->data[b]);
  39     set(h, b, tmp);
  40 }
  41
  42
  43 static int
  44 cmp(Heap *h, int a, int b)
  45 {
  46     return h->cmp(h->data[a], h->data[b]);
  47 }
  48
  49
  50 static void
  51 siftdown(Heap *h, int k)
  52 {
  53     for (;;) {
  54         int p = (k-1) / 2; /* parent */
  55
  56         if (k == 0 || cmp(h, k, p) >= 0) {
  57             return;
  58         }
  59
  60         swap(h, k, p);
  61         k = p;
  62     }
  63 }
  64
  65
  66 static void
  67 siftup(Heap *h, int k)
  68 {
  69     for (;;) {
  70         int l, r, s;
  71
  72         l = k*2 + 1; /* left child */
  73         r = k*2 + 2; /* right child */
  74
  75         /* find the smallest of the three */
  76         s = k;
  77         if (l < h->len && cmp(h, l, s) < 0) s = l;
  78         if (r < h->len && cmp(h, r, s) < 0) s = r;
  79
  80         if (s == k) {
  81             return; /* satisfies the heap property */
  82         }
  83
  84         swap(h, k, s);
  85         k = s;
  86     }
  87 }
  88
  89
  90 int
  91 heapinsert(Heap *h, void *x)
  92 {
  93     int k;
  94
  95     if (h->len == h->cap) {
  96         void **ndata;
  97         int ncap = (h->len+1) * 2; /* allocate twice what we need */
  98
  99         ndata = malloc(sizeof(void*) * ncap);
 100         if (!ndata) {
 101             return 0;
 102         }
 103
 104         memcpy(ndata, h->data, sizeof(void*)*h->len);
 105         free(h->data);
 106         h->data = ndata;
 107         h->cap = ncap;
 108     }
 109
 110     k = h->len;
 111     h->len++;
 112     set(h, k, x);
 113     siftdown(h, k);
 114     return 1;
 115 }
 116
 117
 118 void *
 119 heapremove(Heap *h, int k)
 120 {
 121     void *x;
 122
 123     if (k >= h->len) {
 124         return 0;
 125     }
 126
 127     x = h->data[k];
 128     h->len--;
 129     set(h, k, h->data[h->len]);
 130     siftdown(h, k);
 131     siftup(h, k);
 132     h->rec(x, -1);
 133     return x;
 134 }