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