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> 40RCSID("$Id$"); 41#endif 42 43#include <assert.h> 44#include <stdio.h> 45#include <stdlib.h> 46#include "heap.h" 47 48struct heap { 49 heap_cmp_fn cmp; 50 unsigned max_sz; 51 unsigned sz; 52 heap_element *data; 53}; 54 55/* 56 * Allocate a new heap of size `sz' with compare function `cmp'. 57 */ 58 59Heap * 60heap_new (unsigned sz, heap_cmp_fn cmp) 61{ 62 Heap *ret; 63 int i; 64 65 ret = malloc (sizeof(*ret)); 66 if (ret == NULL) 67 return ret; 68 69 ret->cmp = cmp; 70 ret->max_sz = sz; 71 ret->sz = 0; 72 ret->data = malloc (sz * sizeof(*ret->data)); 73 if (ret->sz != 0 && ret->data == NULL) { 74 free (ret); 75 return NULL; 76 } 77 for (i = 0; i < sz; ++i) { 78 ret->data[i].data = NULL; 79 ret->data[i].ptr = NULL; 80 } 81 return ret; 82} 83 84static inline unsigned 85parent (unsigned n) 86{ 87 return (n + 1) / 2 - 1; 88} 89 90static inline unsigned 91left_child (unsigned n) 92{ 93 return 2 * n + 1; 94} 95 96static inline unsigned 97right_child (unsigned n) 98{ 99 return 2 * n + 2; 100} 101 102static heap_ptr dummy; 103 104/* 105 * 106 */ 107 108static void 109assign (Heap *h, unsigned n, heap_element el) 110{ 111 h->data[n] = el; 112 *(h->data[n].ptr) = n; 113} 114 115/* 116 * 117 */ 118 119static void 120upheap (Heap *h, unsigned n) 121{ 122 heap_element v = h->data[n]; 123 124 while (n > 0 && (*h->cmp)(h->data[parent(n)].data, v.data) > 0) { 125 assign (h, n, h->data[parent(n)]); 126 n = parent(n); 127 } 128 assign (h, n, v); 129} 130 131/* 132 * 133 */ 134 135static void 136downheap (Heap *h, unsigned n) 137{ 138 heap_element v = h->data[n]; 139 140 while (n < h->sz / 2) { 141 int cmp1, cmp2; 142 unsigned new_n; 143 144 assert (left_child(n) < h->sz); 145 146 new_n = left_child(n); 147 148 cmp1 = (*h->cmp)(v.data, h->data[new_n].data); 149 150 if (right_child(n) < h->sz) { 151 cmp2 = (*h->cmp)(v.data, h->data[right_child(n)].data); 152 if (cmp2 > cmp1) { 153 cmp1 = cmp2; 154 new_n = right_child(n); 155 } 156 } 157 158 if (cmp1 > 0) { 159 assign (h, n, h->data[new_n]); 160 n = new_n; 161 } else { 162 break; 163 } 164 } 165 assign (h, n, v); 166} 167 168/* 169 * Insert a new element `data' into `h'. 170 * Return 0 if succesful or else -1. 171 */ 172 173int 174heap_insert (Heap *h, const void *data, heap_ptr *ptr) 175{ 176 assert (data != NULL); 177 178 if (h->sz == h->max_sz) { 179 unsigned new_sz = h->max_sz * 2; 180 heap_element *tmp; 181 182 tmp = realloc (h->data, new_sz * sizeof(*h->data)); 183 if (tmp == NULL) 184 return -1; 185 h->max_sz = new_sz; 186 h->data = tmp; 187 } 188 if (ptr == NULL) 189 ptr = &dummy; 190 191 h->data[h->sz].data = data; 192 h->data[h->sz].ptr = ptr; 193 upheap (h, h->sz); 194 ++h->sz; 195 return 0; 196} 197 198/* 199 * Return the head of the heap `h' (or NULL if it's empty). 200 */ 201 202const void * 203heap_head (Heap *h) 204{ 205 if (h->sz == 0) 206 return NULL; 207 else 208 return h->data[0].data; 209} 210 211/* 212 * Remove element `n' from the heap `h' 213 */ 214 215static void 216remove_this (Heap *h, unsigned n) 217{ 218 assert (n < h->sz); 219 220 --h->sz; 221 h->data[n] = h->data[h->sz]; 222 h->data[h->sz].data = NULL; 223 h->data[h->sz].ptr = NULL; 224 if (n != h->sz) { 225 downheap (h, n); 226 upheap (h, n); 227 } 228} 229 230/* 231 * Remove the head from the heap `h'. 232 */ 233 234void 235heap_remove_head (Heap *h) 236{ 237 remove_this (h, 0); 238} 239 240/* 241 * Remove this very element from the heap `h'. 242 * Return 0 if succesful and -1 if it couldn't be found. 243 */ 244 245int 246heap_remove (Heap *h, heap_ptr ptr) 247{ 248 if (h->sz == 0) 249 return -1; 250 251 assert (h->data[ptr].ptr != &dummy); 252 253 remove_this (h, ptr); 254 return 0; 255} 256 257/* 258 * Delete the heap `h' 259 */ 260 261void 262heap_delete (Heap *h) 263{ 264 free (h->data); 265 free (h); 266} 267 268/* 269 * 270 */ 271 272static int 273do_verify (Heap *h, unsigned n) 274{ 275 if (left_child(n) < h->sz) { 276 if((*h->cmp)(h->data[n].data, h->data[left_child(n)].data) > 0) 277 return 0; 278 if (!do_verify (h, left_child(n))) 279 return 0; 280 } 281 if (right_child(n) < h->sz) { 282 if((*h->cmp)(h->data[n].data, h->data[right_child(n)].data) > 0) 283 return 0; 284 if (!do_verify (h, right_child(n))) 285 return 0; 286 } 287 return 1; 288} 289 290/* 291 * Verify that `h' is really a heap. 292 */ 293 294int 295heap_verify (Heap *h) 296{ 297 return do_verify (h, 0); 298} 299