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