17c478bd9Sstevel@tonic-gate /*
29525b14bSRao 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 *
99525b14bSRao Shoaib * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES
109525b14bSRao Shoaib * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
119525b14bSRao Shoaib * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR
129525b14bSRao Shoaib * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
139525b14bSRao Shoaib * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
149525b14bSRao Shoaib * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
159525b14bSRao Shoaib * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
167c478bd9Sstevel@tonic-gate */
177c478bd9Sstevel@tonic-gate
189525b14bSRao 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 #include "port_before.h"
297c478bd9Sstevel@tonic-gate
307c478bd9Sstevel@tonic-gate #include <stddef.h>
317c478bd9Sstevel@tonic-gate #include <stdlib.h>
327c478bd9Sstevel@tonic-gate #include <errno.h>
337c478bd9Sstevel@tonic-gate
347c478bd9Sstevel@tonic-gate #include "port_after.h"
357c478bd9Sstevel@tonic-gate
367c478bd9Sstevel@tonic-gate #include <isc/heap.h>
377c478bd9Sstevel@tonic-gate
389525b14bSRao Shoaib /*%
397c478bd9Sstevel@tonic-gate * Note: to make heap_parent and heap_left easy to compute, the first
407c478bd9Sstevel@tonic-gate * element of the heap array is not used; i.e. heap subscripts are 1-based,
417c478bd9Sstevel@tonic-gate * not 0-based.
427c478bd9Sstevel@tonic-gate */
437c478bd9Sstevel@tonic-gate #define heap_parent(i) ((i) >> 1)
447c478bd9Sstevel@tonic-gate #define heap_left(i) ((i) << 1)
457c478bd9Sstevel@tonic-gate
467c478bd9Sstevel@tonic-gate #define ARRAY_SIZE_INCREMENT 512
477c478bd9Sstevel@tonic-gate
487c478bd9Sstevel@tonic-gate heap_context
heap_new(heap_higher_priority_func higher_priority,heap_index_func index,int array_size_increment)497c478bd9Sstevel@tonic-gate heap_new(heap_higher_priority_func higher_priority, heap_index_func index,
507c478bd9Sstevel@tonic-gate int array_size_increment) {
517c478bd9Sstevel@tonic-gate heap_context ctx;
527c478bd9Sstevel@tonic-gate
539525b14bSRao Shoaib if (higher_priority == NULL)
549525b14bSRao Shoaib return (NULL);
559525b14bSRao Shoaib
567c478bd9Sstevel@tonic-gate ctx = (heap_context)malloc(sizeof (struct heap_context));
579525b14bSRao Shoaib if (ctx == NULL)
587c478bd9Sstevel@tonic-gate return (NULL);
599525b14bSRao Shoaib
607c478bd9Sstevel@tonic-gate ctx->array_size = 0;
617c478bd9Sstevel@tonic-gate if (array_size_increment == 0)
627c478bd9Sstevel@tonic-gate ctx->array_size_increment = ARRAY_SIZE_INCREMENT;
637c478bd9Sstevel@tonic-gate else
647c478bd9Sstevel@tonic-gate ctx->array_size_increment = array_size_increment;
657c478bd9Sstevel@tonic-gate ctx->heap_size = 0;
667c478bd9Sstevel@tonic-gate ctx->heap = NULL;
677c478bd9Sstevel@tonic-gate ctx->higher_priority = higher_priority;
687c478bd9Sstevel@tonic-gate ctx->index = index;
697c478bd9Sstevel@tonic-gate return (ctx);
707c478bd9Sstevel@tonic-gate }
717c478bd9Sstevel@tonic-gate
727c478bd9Sstevel@tonic-gate int
heap_free(heap_context ctx)737c478bd9Sstevel@tonic-gate heap_free(heap_context ctx) {
747c478bd9Sstevel@tonic-gate if (ctx == NULL) {
757c478bd9Sstevel@tonic-gate errno = EINVAL;
767c478bd9Sstevel@tonic-gate return (-1);
777c478bd9Sstevel@tonic-gate }
787c478bd9Sstevel@tonic-gate
797c478bd9Sstevel@tonic-gate if (ctx->heap != NULL)
807c478bd9Sstevel@tonic-gate free(ctx->heap);
817c478bd9Sstevel@tonic-gate free(ctx);
827c478bd9Sstevel@tonic-gate
837c478bd9Sstevel@tonic-gate return (0);
847c478bd9Sstevel@tonic-gate }
857c478bd9Sstevel@tonic-gate
867c478bd9Sstevel@tonic-gate static int
heap_resize(heap_context ctx)877c478bd9Sstevel@tonic-gate heap_resize(heap_context ctx) {
887c478bd9Sstevel@tonic-gate void **new_heap;
897c478bd9Sstevel@tonic-gate
907c478bd9Sstevel@tonic-gate ctx->array_size += ctx->array_size_increment;
917c478bd9Sstevel@tonic-gate new_heap = (void **)realloc(ctx->heap,
927c478bd9Sstevel@tonic-gate (ctx->array_size) * (sizeof (void *)));
937c478bd9Sstevel@tonic-gate if (new_heap == NULL) {
947c478bd9Sstevel@tonic-gate errno = ENOMEM;
957c478bd9Sstevel@tonic-gate return (-1);
967c478bd9Sstevel@tonic-gate }
977c478bd9Sstevel@tonic-gate ctx->heap = new_heap;
987c478bd9Sstevel@tonic-gate return (0);
997c478bd9Sstevel@tonic-gate }
1007c478bd9Sstevel@tonic-gate
1017c478bd9Sstevel@tonic-gate static void
float_up(heap_context ctx,int i,void * elt)1027c478bd9Sstevel@tonic-gate float_up(heap_context ctx, int i, void *elt) {
1037c478bd9Sstevel@tonic-gate int p;
1047c478bd9Sstevel@tonic-gate
105*55fea89dSDan Cross for ( p = heap_parent(i);
1067c478bd9Sstevel@tonic-gate i > 1 && ctx->higher_priority(elt, ctx->heap[p]);
1077c478bd9Sstevel@tonic-gate i = p, p = heap_parent(i) ) {
1087c478bd9Sstevel@tonic-gate ctx->heap[i] = ctx->heap[p];
1097c478bd9Sstevel@tonic-gate if (ctx->index != NULL)
1107c478bd9Sstevel@tonic-gate (ctx->index)(ctx->heap[i], i);
1117c478bd9Sstevel@tonic-gate }
1127c478bd9Sstevel@tonic-gate ctx->heap[i] = elt;
1137c478bd9Sstevel@tonic-gate if (ctx->index != NULL)
1147c478bd9Sstevel@tonic-gate (ctx->index)(ctx->heap[i], i);
1157c478bd9Sstevel@tonic-gate }
1167c478bd9Sstevel@tonic-gate
1177c478bd9Sstevel@tonic-gate static void
sink_down(heap_context ctx,int i,void * elt)1187c478bd9Sstevel@tonic-gate sink_down(heap_context ctx, int i, void *elt) {
1197c478bd9Sstevel@tonic-gate int j, size, half_size;
1207c478bd9Sstevel@tonic-gate
1217c478bd9Sstevel@tonic-gate size = ctx->heap_size;
1227c478bd9Sstevel@tonic-gate half_size = size / 2;
1237c478bd9Sstevel@tonic-gate while (i <= half_size) {
1247c478bd9Sstevel@tonic-gate /* find smallest of the (at most) two children */
1257c478bd9Sstevel@tonic-gate j = heap_left(i);
1267c478bd9Sstevel@tonic-gate if (j < size && ctx->higher_priority(ctx->heap[j+1],
1277c478bd9Sstevel@tonic-gate ctx->heap[j]))
1287c478bd9Sstevel@tonic-gate j++;
1297c478bd9Sstevel@tonic-gate if (ctx->higher_priority(elt, ctx->heap[j]))
1307c478bd9Sstevel@tonic-gate break;
1317c478bd9Sstevel@tonic-gate ctx->heap[i] = ctx->heap[j];
1327c478bd9Sstevel@tonic-gate if (ctx->index != NULL)
1337c478bd9Sstevel@tonic-gate (ctx->index)(ctx->heap[i], i);
1347c478bd9Sstevel@tonic-gate i = j;
1357c478bd9Sstevel@tonic-gate }
1367c478bd9Sstevel@tonic-gate ctx->heap[i] = elt;
1377c478bd9Sstevel@tonic-gate if (ctx->index != NULL)
1387c478bd9Sstevel@tonic-gate (ctx->index)(ctx->heap[i], i);
1397c478bd9Sstevel@tonic-gate }
1407c478bd9Sstevel@tonic-gate
1417c478bd9Sstevel@tonic-gate int
heap_insert(heap_context ctx,void * elt)1427c478bd9Sstevel@tonic-gate heap_insert(heap_context ctx, void *elt) {
1437c478bd9Sstevel@tonic-gate int i;
1447c478bd9Sstevel@tonic-gate
1457c478bd9Sstevel@tonic-gate if (ctx == NULL || elt == NULL) {
1467c478bd9Sstevel@tonic-gate errno = EINVAL;
1477c478bd9Sstevel@tonic-gate return (-1);
1487c478bd9Sstevel@tonic-gate }
1497c478bd9Sstevel@tonic-gate
1507c478bd9Sstevel@tonic-gate i = ++ctx->heap_size;
1517c478bd9Sstevel@tonic-gate if (ctx->heap_size >= ctx->array_size && heap_resize(ctx) < 0)
1527c478bd9Sstevel@tonic-gate return (-1);
153*55fea89dSDan Cross
1547c478bd9Sstevel@tonic-gate float_up(ctx, i, elt);
1557c478bd9Sstevel@tonic-gate
1567c478bd9Sstevel@tonic-gate return (0);
1577c478bd9Sstevel@tonic-gate }
1587c478bd9Sstevel@tonic-gate
1597c478bd9Sstevel@tonic-gate int
heap_delete(heap_context ctx,int i)1607c478bd9Sstevel@tonic-gate heap_delete(heap_context ctx, int i) {
1617c478bd9Sstevel@tonic-gate void *elt;
1629525b14bSRao Shoaib int less;
1637c478bd9Sstevel@tonic-gate
1647c478bd9Sstevel@tonic-gate if (ctx == NULL || i < 1 || i > ctx->heap_size) {
1657c478bd9Sstevel@tonic-gate errno = EINVAL;
1667c478bd9Sstevel@tonic-gate return (-1);
1677c478bd9Sstevel@tonic-gate }
1687c478bd9Sstevel@tonic-gate
1699525b14bSRao Shoaib if (i == ctx->heap_size) {
1709525b14bSRao Shoaib ctx->heap_size--;
1719525b14bSRao Shoaib } else {
1729525b14bSRao Shoaib elt = ctx->heap[ctx->heap_size--];
1739525b14bSRao Shoaib less = ctx->higher_priority(elt, ctx->heap[i]);
1749525b14bSRao Shoaib ctx->heap[i] = elt;
1759525b14bSRao Shoaib if (less)
1769525b14bSRao Shoaib float_up(ctx, i, ctx->heap[i]);
1779525b14bSRao Shoaib else
1789525b14bSRao Shoaib sink_down(ctx, i, ctx->heap[i]);
1799525b14bSRao Shoaib }
1807c478bd9Sstevel@tonic-gate
1817c478bd9Sstevel@tonic-gate return (0);
1827c478bd9Sstevel@tonic-gate }
1837c478bd9Sstevel@tonic-gate
1847c478bd9Sstevel@tonic-gate int
heap_increased(heap_context ctx,int i)1857c478bd9Sstevel@tonic-gate heap_increased(heap_context ctx, int i) {
1867c478bd9Sstevel@tonic-gate if (ctx == NULL || i < 1 || i > ctx->heap_size) {
1877c478bd9Sstevel@tonic-gate errno = EINVAL;
1887c478bd9Sstevel@tonic-gate return (-1);
1897c478bd9Sstevel@tonic-gate }
190*55fea89dSDan Cross
1917c478bd9Sstevel@tonic-gate float_up(ctx, i, ctx->heap[i]);
1927c478bd9Sstevel@tonic-gate
1937c478bd9Sstevel@tonic-gate return (0);
1947c478bd9Sstevel@tonic-gate }
1957c478bd9Sstevel@tonic-gate
1967c478bd9Sstevel@tonic-gate int
heap_decreased(heap_context ctx,int i)1977c478bd9Sstevel@tonic-gate heap_decreased(heap_context ctx, int i) {
1987c478bd9Sstevel@tonic-gate if (ctx == NULL || i < 1 || i > ctx->heap_size) {
1997c478bd9Sstevel@tonic-gate errno = EINVAL;
2007c478bd9Sstevel@tonic-gate return (-1);
2017c478bd9Sstevel@tonic-gate }
202*55fea89dSDan Cross
2037c478bd9Sstevel@tonic-gate sink_down(ctx, i, ctx->heap[i]);
2047c478bd9Sstevel@tonic-gate
2057c478bd9Sstevel@tonic-gate return (0);
2067c478bd9Sstevel@tonic-gate }
2077c478bd9Sstevel@tonic-gate
2087c478bd9Sstevel@tonic-gate void *
heap_element(heap_context ctx,int i)2097c478bd9Sstevel@tonic-gate heap_element(heap_context ctx, int i) {
2107c478bd9Sstevel@tonic-gate if (ctx == NULL || i < 1 || i > ctx->heap_size) {
2117c478bd9Sstevel@tonic-gate errno = EINVAL;
2127c478bd9Sstevel@tonic-gate return (NULL);
2137c478bd9Sstevel@tonic-gate }
2147c478bd9Sstevel@tonic-gate
2157c478bd9Sstevel@tonic-gate return (ctx->heap[i]);
2167c478bd9Sstevel@tonic-gate }
2177c478bd9Sstevel@tonic-gate
2187c478bd9Sstevel@tonic-gate int
heap_for_each(heap_context ctx,heap_for_each_func action,void * uap)2197c478bd9Sstevel@tonic-gate heap_for_each(heap_context ctx, heap_for_each_func action, void *uap) {
2207c478bd9Sstevel@tonic-gate int i;
2217c478bd9Sstevel@tonic-gate
2227c478bd9Sstevel@tonic-gate if (ctx == NULL || action == NULL) {
2237c478bd9Sstevel@tonic-gate errno = EINVAL;
2247c478bd9Sstevel@tonic-gate return (-1);
2257c478bd9Sstevel@tonic-gate }
2267c478bd9Sstevel@tonic-gate
2277c478bd9Sstevel@tonic-gate for (i = 1; i <= ctx->heap_size; i++)
2287c478bd9Sstevel@tonic-gate (action)(ctx->heap[i], uap);
2297c478bd9Sstevel@tonic-gate return (0);
2307c478bd9Sstevel@tonic-gate }
2319525b14bSRao Shoaib
2329525b14bSRao Shoaib /*! \file */
233