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 struct 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 59 Heap * 60 heap_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 86 static inline unsigned 87 parent (unsigned n) 88 { 89 return (n + 1) / 2 - 1; 90 } 91 92 static inline unsigned 93 left_child (unsigned n) 94 { 95 return 2 * n + 1; 96 } 97 98 static inline unsigned 99 right_child (unsigned n) 100 { 101 return 2 * n + 2; 102 } 103 104 static heap_ptr dummy; 105 106 /* 107 * 108 */ 109 110 static void 111 assign (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 121 static void 122 upheap (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 137 static void 138 downheap (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 175 int 176 heap_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 204 const void * 205 heap_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 217 static void 218 remove_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 236 void 237 heap_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 247 int 248 heap_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 263 void 264 heap_delete (Heap *h) 265 { 266 free (h->data); 267 free (h); 268 } 269 270 /* 271 * 272 */ 273 274 static int 275 do_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 296 int 297 heap_verify (Heap *h) 298 { 299 return do_verify (h, 0); 300 }