1 /* 2 * Copyright (c) 2004 by Internet Systems Consortium, Inc. ("ISC") 3 * Copyright (c) 1997,1999 by Internet Software Consortium. 4 * 5 * Permission to use, copy, modify, and distribute this software for any 6 * purpose with or without fee is hereby granted, provided that the above 7 * copyright notice and this permission notice appear in all copies. 8 * 9 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES 10 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 11 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR 12 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 13 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 14 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT 15 * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 16 */ 17 18 /*% 19 * Heap implementation of priority queues adapted from the following: 20 * 21 * _Introduction to Algorithms_, Cormen, Leiserson, and Rivest, 22 * MIT Press / McGraw Hill, 1990, ISBN 0-262-03141-8, chapter 7. 23 * 24 * _Algorithms_, Second Edition, Sedgewick, Addison-Wesley, 1988, 25 * ISBN 0-201-06673-4, chapter 11. 26 */ 27 28 #if !defined(LINT) && !defined(CODECENTER) 29 static const char rcsid[] = "$Id: heap.c,v 1.4 2006/03/09 23:57:56 marka Exp $"; 30 #endif /* not lint */ 31 32 #include "port_before.h" 33 34 #include <stddef.h> 35 #include <stdlib.h> 36 #include <errno.h> 37 38 #include "port_after.h" 39 40 #include <isc/heap.h> 41 42 /*% 43 * Note: to make heap_parent and heap_left easy to compute, the first 44 * element of the heap array is not used; i.e. heap subscripts are 1-based, 45 * not 0-based. 46 */ 47 #define heap_parent(i) ((i) >> 1) 48 #define heap_left(i) ((i) << 1) 49 50 #define ARRAY_SIZE_INCREMENT 512 51 52 heap_context 53 heap_new(heap_higher_priority_func higher_priority, heap_index_func index, 54 int array_size_increment) { 55 heap_context ctx; 56 57 if (higher_priority == NULL) 58 return (NULL); 59 60 ctx = (heap_context)malloc(sizeof (struct heap_context)); 61 if (ctx == NULL) 62 return (NULL); 63 64 ctx->array_size = 0; 65 if (array_size_increment == 0) 66 ctx->array_size_increment = ARRAY_SIZE_INCREMENT; 67 else 68 ctx->array_size_increment = array_size_increment; 69 ctx->heap_size = 0; 70 ctx->heap = NULL; 71 ctx->higher_priority = higher_priority; 72 ctx->index = index; 73 return (ctx); 74 } 75 76 int 77 heap_free(heap_context ctx) { 78 if (ctx == NULL) { 79 errno = EINVAL; 80 return (-1); 81 } 82 83 if (ctx->heap != NULL) 84 free(ctx->heap); 85 free(ctx); 86 87 return (0); 88 } 89 90 static int 91 heap_resize(heap_context ctx) { 92 void **new_heap; 93 94 ctx->array_size += ctx->array_size_increment; 95 new_heap = (void **)realloc(ctx->heap, 96 (ctx->array_size) * (sizeof (void *))); 97 if (new_heap == NULL) { 98 errno = ENOMEM; 99 return (-1); 100 } 101 ctx->heap = new_heap; 102 return (0); 103 } 104 105 static void 106 float_up(heap_context ctx, int i, void *elt) { 107 int p; 108 109 for ( p = heap_parent(i); 110 i > 1 && ctx->higher_priority(elt, ctx->heap[p]); 111 i = p, p = heap_parent(i) ) { 112 ctx->heap[i] = ctx->heap[p]; 113 if (ctx->index != NULL) 114 (ctx->index)(ctx->heap[i], i); 115 } 116 ctx->heap[i] = elt; 117 if (ctx->index != NULL) 118 (ctx->index)(ctx->heap[i], i); 119 } 120 121 static void 122 sink_down(heap_context ctx, int i, void *elt) { 123 int j, size, half_size; 124 125 size = ctx->heap_size; 126 half_size = size / 2; 127 while (i <= half_size) { 128 /* find smallest of the (at most) two children */ 129 j = heap_left(i); 130 if (j < size && ctx->higher_priority(ctx->heap[j+1], 131 ctx->heap[j])) 132 j++; 133 if (ctx->higher_priority(elt, ctx->heap[j])) 134 break; 135 ctx->heap[i] = ctx->heap[j]; 136 if (ctx->index != NULL) 137 (ctx->index)(ctx->heap[i], i); 138 i = j; 139 } 140 ctx->heap[i] = elt; 141 if (ctx->index != NULL) 142 (ctx->index)(ctx->heap[i], i); 143 } 144 145 int 146 heap_insert(heap_context ctx, void *elt) { 147 int i; 148 149 if (ctx == NULL || elt == NULL) { 150 errno = EINVAL; 151 return (-1); 152 } 153 154 i = ++ctx->heap_size; 155 if (ctx->heap_size >= ctx->array_size && heap_resize(ctx) < 0) 156 return (-1); 157 158 float_up(ctx, i, elt); 159 160 return (0); 161 } 162 163 int 164 heap_delete(heap_context ctx, int i) { 165 void *elt; 166 int less; 167 168 if (ctx == NULL || i < 1 || i > ctx->heap_size) { 169 errno = EINVAL; 170 return (-1); 171 } 172 173 if (i == ctx->heap_size) { 174 ctx->heap_size--; 175 } else { 176 elt = ctx->heap[ctx->heap_size--]; 177 less = ctx->higher_priority(elt, ctx->heap[i]); 178 ctx->heap[i] = elt; 179 if (less) 180 float_up(ctx, i, ctx->heap[i]); 181 else 182 sink_down(ctx, i, ctx->heap[i]); 183 } 184 185 return (0); 186 } 187 188 int 189 heap_increased(heap_context ctx, int i) { 190 if (ctx == NULL || i < 1 || i > ctx->heap_size) { 191 errno = EINVAL; 192 return (-1); 193 } 194 195 float_up(ctx, i, ctx->heap[i]); 196 197 return (0); 198 } 199 200 int 201 heap_decreased(heap_context ctx, int i) { 202 if (ctx == NULL || i < 1 || i > ctx->heap_size) { 203 errno = EINVAL; 204 return (-1); 205 } 206 207 sink_down(ctx, i, ctx->heap[i]); 208 209 return (0); 210 } 211 212 void * 213 heap_element(heap_context ctx, int i) { 214 if (ctx == NULL || i < 1 || i > ctx->heap_size) { 215 errno = EINVAL; 216 return (NULL); 217 } 218 219 return (ctx->heap[i]); 220 } 221 222 int 223 heap_for_each(heap_context ctx, heap_for_each_func action, void *uap) { 224 int i; 225 226 if (ctx == NULL || action == NULL) { 227 errno = EINVAL; 228 return (-1); 229 } 230 231 for (i = 1; i <= ctx->heap_size; i++) 232 (action)(ctx->heap[i], uap); 233 return (0); 234 } 235 236 /*! \file */ 237