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