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