17c478bd9Sstevel@tonic-gate /* 2*9525b14bSRao Shoaib * Copyright (c) 2004 by Internet Systems Consortium, Inc. ("ISC") 37c478bd9Sstevel@tonic-gate * Copyright (c) 1997,1999 by Internet Software Consortium. 47c478bd9Sstevel@tonic-gate * 57c478bd9Sstevel@tonic-gate * Permission to use, copy, modify, and distribute this software for any 67c478bd9Sstevel@tonic-gate * purpose with or without fee is hereby granted, provided that the above 77c478bd9Sstevel@tonic-gate * copyright notice and this permission notice appear in all copies. 87c478bd9Sstevel@tonic-gate * 9*9525b14bSRao Shoaib * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES 10*9525b14bSRao Shoaib * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 11*9525b14bSRao Shoaib * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR 12*9525b14bSRao Shoaib * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 13*9525b14bSRao Shoaib * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 14*9525b14bSRao Shoaib * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT 15*9525b14bSRao Shoaib * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 167c478bd9Sstevel@tonic-gate */ 177c478bd9Sstevel@tonic-gate 18*9525b14bSRao Shoaib /*% 197c478bd9Sstevel@tonic-gate * Heap implementation of priority queues adapted from the following: 207c478bd9Sstevel@tonic-gate * 217c478bd9Sstevel@tonic-gate * _Introduction to Algorithms_, Cormen, Leiserson, and Rivest, 227c478bd9Sstevel@tonic-gate * MIT Press / McGraw Hill, 1990, ISBN 0-262-03141-8, chapter 7. 237c478bd9Sstevel@tonic-gate * 247c478bd9Sstevel@tonic-gate * _Algorithms_, Second Edition, Sedgewick, Addison-Wesley, 1988, 257c478bd9Sstevel@tonic-gate * ISBN 0-201-06673-4, chapter 11. 267c478bd9Sstevel@tonic-gate */ 277c478bd9Sstevel@tonic-gate 287c478bd9Sstevel@tonic-gate #if !defined(LINT) && !defined(CODECENTER) 29*9525b14bSRao Shoaib static const char rcsid[] = "$Id: heap.c,v 1.4 2006/03/09 23:57:56 marka Exp $"; 307c478bd9Sstevel@tonic-gate #endif /* not lint */ 317c478bd9Sstevel@tonic-gate 327c478bd9Sstevel@tonic-gate #include "port_before.h" 337c478bd9Sstevel@tonic-gate 347c478bd9Sstevel@tonic-gate #include <stddef.h> 357c478bd9Sstevel@tonic-gate #include <stdlib.h> 367c478bd9Sstevel@tonic-gate #include <errno.h> 377c478bd9Sstevel@tonic-gate 387c478bd9Sstevel@tonic-gate #include "port_after.h" 397c478bd9Sstevel@tonic-gate 407c478bd9Sstevel@tonic-gate #include <isc/heap.h> 417c478bd9Sstevel@tonic-gate 42*9525b14bSRao Shoaib /*% 437c478bd9Sstevel@tonic-gate * Note: to make heap_parent and heap_left easy to compute, the first 447c478bd9Sstevel@tonic-gate * element of the heap array is not used; i.e. heap subscripts are 1-based, 457c478bd9Sstevel@tonic-gate * not 0-based. 467c478bd9Sstevel@tonic-gate */ 477c478bd9Sstevel@tonic-gate #define heap_parent(i) ((i) >> 1) 487c478bd9Sstevel@tonic-gate #define heap_left(i) ((i) << 1) 497c478bd9Sstevel@tonic-gate 507c478bd9Sstevel@tonic-gate #define ARRAY_SIZE_INCREMENT 512 517c478bd9Sstevel@tonic-gate 527c478bd9Sstevel@tonic-gate heap_context 537c478bd9Sstevel@tonic-gate heap_new(heap_higher_priority_func higher_priority, heap_index_func index, 547c478bd9Sstevel@tonic-gate int array_size_increment) { 557c478bd9Sstevel@tonic-gate heap_context ctx; 567c478bd9Sstevel@tonic-gate 57*9525b14bSRao Shoaib if (higher_priority == NULL) 587c478bd9Sstevel@tonic-gate return (NULL); 59*9525b14bSRao Shoaib 60*9525b14bSRao Shoaib ctx = (heap_context)malloc(sizeof (struct heap_context)); 61*9525b14bSRao Shoaib if (ctx == NULL) 62*9525b14bSRao Shoaib return (NULL); 63*9525b14bSRao Shoaib 647c478bd9Sstevel@tonic-gate ctx->array_size = 0; 657c478bd9Sstevel@tonic-gate if (array_size_increment == 0) 667c478bd9Sstevel@tonic-gate ctx->array_size_increment = ARRAY_SIZE_INCREMENT; 677c478bd9Sstevel@tonic-gate else 687c478bd9Sstevel@tonic-gate ctx->array_size_increment = array_size_increment; 697c478bd9Sstevel@tonic-gate ctx->heap_size = 0; 707c478bd9Sstevel@tonic-gate ctx->heap = NULL; 717c478bd9Sstevel@tonic-gate ctx->higher_priority = higher_priority; 727c478bd9Sstevel@tonic-gate ctx->index = index; 737c478bd9Sstevel@tonic-gate return (ctx); 747c478bd9Sstevel@tonic-gate } 757c478bd9Sstevel@tonic-gate 767c478bd9Sstevel@tonic-gate int 777c478bd9Sstevel@tonic-gate heap_free(heap_context ctx) { 787c478bd9Sstevel@tonic-gate if (ctx == NULL) { 797c478bd9Sstevel@tonic-gate errno = EINVAL; 807c478bd9Sstevel@tonic-gate return (-1); 817c478bd9Sstevel@tonic-gate } 827c478bd9Sstevel@tonic-gate 837c478bd9Sstevel@tonic-gate if (ctx->heap != NULL) 847c478bd9Sstevel@tonic-gate free(ctx->heap); 857c478bd9Sstevel@tonic-gate free(ctx); 867c478bd9Sstevel@tonic-gate 877c478bd9Sstevel@tonic-gate return (0); 887c478bd9Sstevel@tonic-gate } 897c478bd9Sstevel@tonic-gate 907c478bd9Sstevel@tonic-gate static int 917c478bd9Sstevel@tonic-gate heap_resize(heap_context ctx) { 927c478bd9Sstevel@tonic-gate void **new_heap; 937c478bd9Sstevel@tonic-gate 947c478bd9Sstevel@tonic-gate ctx->array_size += ctx->array_size_increment; 957c478bd9Sstevel@tonic-gate new_heap = (void **)realloc(ctx->heap, 967c478bd9Sstevel@tonic-gate (ctx->array_size) * (sizeof (void *))); 977c478bd9Sstevel@tonic-gate if (new_heap == NULL) { 987c478bd9Sstevel@tonic-gate errno = ENOMEM; 997c478bd9Sstevel@tonic-gate return (-1); 1007c478bd9Sstevel@tonic-gate } 1017c478bd9Sstevel@tonic-gate ctx->heap = new_heap; 1027c478bd9Sstevel@tonic-gate return (0); 1037c478bd9Sstevel@tonic-gate } 1047c478bd9Sstevel@tonic-gate 1057c478bd9Sstevel@tonic-gate static void 1067c478bd9Sstevel@tonic-gate float_up(heap_context ctx, int i, void *elt) { 1077c478bd9Sstevel@tonic-gate int p; 1087c478bd9Sstevel@tonic-gate 1097c478bd9Sstevel@tonic-gate for ( p = heap_parent(i); 1107c478bd9Sstevel@tonic-gate i > 1 && ctx->higher_priority(elt, ctx->heap[p]); 1117c478bd9Sstevel@tonic-gate i = p, p = heap_parent(i) ) { 1127c478bd9Sstevel@tonic-gate ctx->heap[i] = ctx->heap[p]; 1137c478bd9Sstevel@tonic-gate if (ctx->index != NULL) 1147c478bd9Sstevel@tonic-gate (ctx->index)(ctx->heap[i], i); 1157c478bd9Sstevel@tonic-gate } 1167c478bd9Sstevel@tonic-gate ctx->heap[i] = elt; 1177c478bd9Sstevel@tonic-gate if (ctx->index != NULL) 1187c478bd9Sstevel@tonic-gate (ctx->index)(ctx->heap[i], i); 1197c478bd9Sstevel@tonic-gate } 1207c478bd9Sstevel@tonic-gate 1217c478bd9Sstevel@tonic-gate static void 1227c478bd9Sstevel@tonic-gate sink_down(heap_context ctx, int i, void *elt) { 1237c478bd9Sstevel@tonic-gate int j, size, half_size; 1247c478bd9Sstevel@tonic-gate 1257c478bd9Sstevel@tonic-gate size = ctx->heap_size; 1267c478bd9Sstevel@tonic-gate half_size = size / 2; 1277c478bd9Sstevel@tonic-gate while (i <= half_size) { 1287c478bd9Sstevel@tonic-gate /* find smallest of the (at most) two children */ 1297c478bd9Sstevel@tonic-gate j = heap_left(i); 1307c478bd9Sstevel@tonic-gate if (j < size && ctx->higher_priority(ctx->heap[j+1], 1317c478bd9Sstevel@tonic-gate ctx->heap[j])) 1327c478bd9Sstevel@tonic-gate j++; 1337c478bd9Sstevel@tonic-gate if (ctx->higher_priority(elt, ctx->heap[j])) 1347c478bd9Sstevel@tonic-gate break; 1357c478bd9Sstevel@tonic-gate ctx->heap[i] = ctx->heap[j]; 1367c478bd9Sstevel@tonic-gate if (ctx->index != NULL) 1377c478bd9Sstevel@tonic-gate (ctx->index)(ctx->heap[i], i); 1387c478bd9Sstevel@tonic-gate i = j; 1397c478bd9Sstevel@tonic-gate } 1407c478bd9Sstevel@tonic-gate ctx->heap[i] = elt; 1417c478bd9Sstevel@tonic-gate if (ctx->index != NULL) 1427c478bd9Sstevel@tonic-gate (ctx->index)(ctx->heap[i], i); 1437c478bd9Sstevel@tonic-gate } 1447c478bd9Sstevel@tonic-gate 1457c478bd9Sstevel@tonic-gate int 1467c478bd9Sstevel@tonic-gate heap_insert(heap_context ctx, void *elt) { 1477c478bd9Sstevel@tonic-gate int i; 1487c478bd9Sstevel@tonic-gate 1497c478bd9Sstevel@tonic-gate if (ctx == NULL || elt == NULL) { 1507c478bd9Sstevel@tonic-gate errno = EINVAL; 1517c478bd9Sstevel@tonic-gate return (-1); 1527c478bd9Sstevel@tonic-gate } 1537c478bd9Sstevel@tonic-gate 1547c478bd9Sstevel@tonic-gate i = ++ctx->heap_size; 1557c478bd9Sstevel@tonic-gate if (ctx->heap_size >= ctx->array_size && heap_resize(ctx) < 0) 1567c478bd9Sstevel@tonic-gate return (-1); 1577c478bd9Sstevel@tonic-gate 1587c478bd9Sstevel@tonic-gate float_up(ctx, i, elt); 1597c478bd9Sstevel@tonic-gate 1607c478bd9Sstevel@tonic-gate return (0); 1617c478bd9Sstevel@tonic-gate } 1627c478bd9Sstevel@tonic-gate 1637c478bd9Sstevel@tonic-gate int 1647c478bd9Sstevel@tonic-gate heap_delete(heap_context ctx, int i) { 1657c478bd9Sstevel@tonic-gate void *elt; 166*9525b14bSRao Shoaib int less; 1677c478bd9Sstevel@tonic-gate 1687c478bd9Sstevel@tonic-gate if (ctx == NULL || i < 1 || i > ctx->heap_size) { 1697c478bd9Sstevel@tonic-gate errno = EINVAL; 1707c478bd9Sstevel@tonic-gate return (-1); 1717c478bd9Sstevel@tonic-gate } 1727c478bd9Sstevel@tonic-gate 173*9525b14bSRao Shoaib if (i == ctx->heap_size) { 174*9525b14bSRao Shoaib ctx->heap_size--; 175*9525b14bSRao Shoaib } else { 176*9525b14bSRao Shoaib elt = ctx->heap[ctx->heap_size--]; 177*9525b14bSRao Shoaib less = ctx->higher_priority(elt, ctx->heap[i]); 178*9525b14bSRao Shoaib ctx->heap[i] = elt; 179*9525b14bSRao Shoaib if (less) 180*9525b14bSRao Shoaib float_up(ctx, i, ctx->heap[i]); 181*9525b14bSRao Shoaib else 182*9525b14bSRao Shoaib sink_down(ctx, i, ctx->heap[i]); 183*9525b14bSRao Shoaib } 1847c478bd9Sstevel@tonic-gate 1857c478bd9Sstevel@tonic-gate return (0); 1867c478bd9Sstevel@tonic-gate } 1877c478bd9Sstevel@tonic-gate 1887c478bd9Sstevel@tonic-gate int 1897c478bd9Sstevel@tonic-gate heap_increased(heap_context ctx, int i) { 1907c478bd9Sstevel@tonic-gate if (ctx == NULL || i < 1 || i > ctx->heap_size) { 1917c478bd9Sstevel@tonic-gate errno = EINVAL; 1927c478bd9Sstevel@tonic-gate return (-1); 1937c478bd9Sstevel@tonic-gate } 1947c478bd9Sstevel@tonic-gate 1957c478bd9Sstevel@tonic-gate float_up(ctx, i, ctx->heap[i]); 1967c478bd9Sstevel@tonic-gate 1977c478bd9Sstevel@tonic-gate return (0); 1987c478bd9Sstevel@tonic-gate } 1997c478bd9Sstevel@tonic-gate 2007c478bd9Sstevel@tonic-gate int 2017c478bd9Sstevel@tonic-gate heap_decreased(heap_context ctx, int i) { 2027c478bd9Sstevel@tonic-gate if (ctx == NULL || i < 1 || i > ctx->heap_size) { 2037c478bd9Sstevel@tonic-gate errno = EINVAL; 2047c478bd9Sstevel@tonic-gate return (-1); 2057c478bd9Sstevel@tonic-gate } 2067c478bd9Sstevel@tonic-gate 2077c478bd9Sstevel@tonic-gate sink_down(ctx, i, ctx->heap[i]); 2087c478bd9Sstevel@tonic-gate 2097c478bd9Sstevel@tonic-gate return (0); 2107c478bd9Sstevel@tonic-gate } 2117c478bd9Sstevel@tonic-gate 2127c478bd9Sstevel@tonic-gate void * 2137c478bd9Sstevel@tonic-gate heap_element(heap_context ctx, int i) { 2147c478bd9Sstevel@tonic-gate if (ctx == NULL || i < 1 || i > ctx->heap_size) { 2157c478bd9Sstevel@tonic-gate errno = EINVAL; 2167c478bd9Sstevel@tonic-gate return (NULL); 2177c478bd9Sstevel@tonic-gate } 2187c478bd9Sstevel@tonic-gate 2197c478bd9Sstevel@tonic-gate return (ctx->heap[i]); 2207c478bd9Sstevel@tonic-gate } 2217c478bd9Sstevel@tonic-gate 2227c478bd9Sstevel@tonic-gate int 2237c478bd9Sstevel@tonic-gate heap_for_each(heap_context ctx, heap_for_each_func action, void *uap) { 2247c478bd9Sstevel@tonic-gate int i; 2257c478bd9Sstevel@tonic-gate 2267c478bd9Sstevel@tonic-gate if (ctx == NULL || action == NULL) { 2277c478bd9Sstevel@tonic-gate errno = EINVAL; 2287c478bd9Sstevel@tonic-gate return (-1); 2297c478bd9Sstevel@tonic-gate } 2307c478bd9Sstevel@tonic-gate 2317c478bd9Sstevel@tonic-gate for (i = 1; i <= ctx->heap_size; i++) 2327c478bd9Sstevel@tonic-gate (action)(ctx->heap[i], uap); 2337c478bd9Sstevel@tonic-gate return (0); 2347c478bd9Sstevel@tonic-gate } 235*9525b14bSRao Shoaib 236*9525b14bSRao Shoaib /*! \file */ 237