util/heap.c

   1 /*
   2  * Copyright (c) 1998 - 2002 Kungliga Tekniska Högskolan
   3  * (Royal Institute of Technology, Stockholm, Sweden).
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  *
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  *
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  *
  17  * 3. Neither the name of the Institute nor the names of its contributors
  18  *    may be used to endorse or promote products derived from this software
  19  *    without specific prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
  22  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24  * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
  25  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31  * SUCH DAMAGE.
  32  */
  33
  34 /*
  35  * Heap
  36  */
  37
  38 #ifdef HAVE_CONFIG_H
  39 #include <config.h>
  40 RCSID("$Id$");
  41 #endif
  42
  43 #include <assert.h>
  44 #include <stdio.h>
  45 #include <stdlib.h>
  46 #include "heap.h"
  47
  48 /*
  49  * Allocate a new heap of size `sz' with compare function `cmp'.
  50  */
  51
  52 Heap *
  53 heap_new (unsigned sz, heap_cmp_fn cmp)
  54 {
  55     Heap *ret;
  56     int i;
  57
  58     ret = malloc (sizeof(*ret));
  59     if (ret == NULL)
  60         return ret;
  61
  62     ret->cmp    = cmp;
  63     ret->max_sz = sz;
  64     ret->sz     = 0;
  65     ret->data   = malloc (sz * sizeof(*ret->data));
  66     if (ret->sz != 0 && ret->data == NULL) {
  67         free (ret);
  68         return NULL;
  69     }
  70     for (i = 0; i < sz; ++i) {
  71         ret->data[i].data = NULL;
  72         ret->data[i].ptr  = NULL;
  73     }
  74     return ret;
  75 }
  76
  77 static inline unsigned
  78 parent (unsigned n)
  79 {
  80     return (n + 1) / 2 - 1;
  81 }
  82
  83 static inline unsigned
  84 left_child (unsigned n)
  85 {
  86     return 2 * n + 1;
  87 }
  88
  89 static inline unsigned
  90 right_child (unsigned n)
  91 {
  92     return 2 * n + 2;
  93 }
  94
  95 static heap_ptr dummy;
  96
  97 /*
  98  *
  99  */
 100
 101 static void
 102 assign (Heap *h, unsigned n, heap_element el)
 103 {
 104     h->data[n] = el;
 105     *(h->data[n].ptr) = n;
 106 }
 107
 108 /*
 109  *
 110  */
 111
 112 static void
 113 upheap (Heap *h, unsigned n)
 114 {
 115     heap_element v = h->data[n];
 116
 117     while (n > 0 && (*h->cmp)(h->data[parent(n)].data, v.data) > 0) {
 118         assign (h, n, h->data[parent(n)]);
 119         n = parent(n);
 120     }
 121     assign (h, n, v);
 122 }
 123
 124 /*
 125  *
 126  */
 127
 128 static void
 129 downheap (Heap *h, unsigned n)
 130 {
 131     heap_element v = h->data[n];
 132
 133     while (n < h->sz / 2) {
 134         int cmp1, cmp2;
 135         unsigned new_n;
 136
 137         assert (left_child(n) < h->sz);
 138
 139         new_n = left_child(n);
 140
 141         cmp1 = (*h->cmp)(v.data, h->data[new_n].data);
 142
 143         if (right_child(n) < h->sz) {
 144             cmp2 = (*h->cmp)(v.data, h->data[right_child(n)].data);
 145             if (cmp2 > cmp1) {
 146                 cmp1  = cmp2;
 147                 new_n = right_child(n);
 148             }
 149         }
 150
 151         if (cmp1 > 0) {
 152             assign (h, n, h->data[new_n]);
 153             n = new_n;
 154         } else {
 155             break;
 156         }
 157     }
 158     assign (h, n, v);
 159 }
 160
 161 /*
 162  * Insert a new element `data' into `h'.
 163  * Return 0 if succesful or else -1.
 164  */
 165
 166 int
 167 heap_insert (Heap *h, const void *data, heap_ptr *ptr)
 168 {
 169     assert (data != NULL);
 170
 171     if (h->sz == h->max_sz) {
 172         unsigned new_sz = h->max_sz * 2;
 173         heap_element *tmp;
 174
 175         tmp = realloc (h->data, new_sz * sizeof(*h->data));
 176         if (tmp == NULL)
 177             return -1;
 178         h->max_sz = new_sz;
 179         h->data   = tmp;
 180     }
 181     if (ptr == NULL)
 182         ptr = &dummy;
 183
 184     h->data[h->sz].data = data;
 185     h->data[h->sz].ptr  = ptr;
 186     upheap (h, h->sz);
 187     ++h->sz;
 188     return 0;
 189 }
 190
 191 /*
 192  * Return the head of the heap `h' (or NULL if it's empty).
 193  */
 194
 195 const void *
 196 heap_head (Heap *h)
 197 {
 198     if (h->sz == 0)
 199         return NULL;
 200     else
 201         return h->data[0].data;
 202 }
 203
 204 /*
 205  * Remove element `n' from the heap `h'
 206  */
 207
 208 static void
 209 remove_this (Heap *h, unsigned n)
 210 {
 211     assert (n < h->sz);
 212
 213     --h->sz;
 214     h->data[n] = h->data[h->sz];
 215     h->data[h->sz].data = NULL;
 216     h->data[h->sz].ptr  = NULL;
 217     if (n != h->sz) {
 218         downheap (h, n);
 219         upheap (h, n);
 220     }
 221 }
 222
 223 /*
 224  * Remove the head from the heap `h'.
 225  */
 226
 227 void
 228 heap_remove_head (Heap *h)
 229 {
 230     remove_this (h, 0);
 231 }
 232
 233 /*
 234  * Remove this very element from the heap `h'.
 235  * Return 0 if succesful and -1 if it couldn't be found.
 236  */
 237
 238 int
 239 heap_remove (Heap *h, heap_ptr ptr)
 240 {
 241     if (h->sz == 0)
 242         return -1;
 243
 244     assert (h->data[ptr].ptr != &dummy);
 245
 246     remove_this (h, ptr);
 247     return 0;
 248 }
 249
 250 /*
 251  * Delete the heap `h'
 252  */
 253
 254 void
 255 heap_delete (Heap *h)
 256 {
 257     free (h->data);
 258     free (h);
 259 }
 260
 261 /*
 262  *
 263  */
 264
 265 static Bool
 266 do_verify (Heap *h, unsigned n)
 267 {
 268     if (left_child(n) < h->sz) {
 269         if((*h->cmp)(h->data[n].data, h->data[left_child(n)].data) > 0)
 270             return FALSE;
 271         if (!do_verify (h, left_child(n)))
 272             return FALSE;
 273     }
 274     if (right_child(n) < h->sz) {
 275         if((*h->cmp)(h->data[n].data, h->data[right_child(n)].data) > 0)
 276             return FALSE;
 277         if (!do_verify (h, right_child(n)))
 278             return FALSE;
 279     }
 280     return TRUE;
 281 }
 282
 283 /*
 284  * Verify that `h' is really a heap.
 285  */
 286
 287 Bool
 288 heap_verify (Heap *h)
 289 {
 290     return do_verify (h, 0);
 291 }