diff options
Diffstat (limited to 'contrib/bind9/lib/isc/heap.c')
| -rw-r--r-- | contrib/bind9/lib/isc/heap.c | 58 |
1 files changed, 31 insertions, 27 deletions
diff --git a/contrib/bind9/lib/isc/heap.c b/contrib/bind9/lib/isc/heap.c index 78b1925..fd67d7b 100644 --- a/contrib/bind9/lib/isc/heap.c +++ b/contrib/bind9/lib/isc/heap.c @@ -1,5 +1,5 @@ /* - * Copyright (C) 2004 Internet Systems Consortium, Inc. ("ISC") + * Copyright (C) 2004-2006 Internet Systems Consortium, Inc. ("ISC") * Copyright (C) 1997-2001 Internet Software Consortium. * * Permission to use, copy, modify, and distribute this software for any @@ -15,15 +15,15 @@ * PERFORMANCE OF THIS SOFTWARE. */ -/* $Id: heap.c,v 1.28.12.3 2004/03/08 09:04:48 marka Exp $ */ +/* $Id: heap.c,v 1.28.12.4 2006/04/17 18:27:20 explorer Exp $ */ -/* +/*! \file * Heap implementation of priority queues adapted from the following: * - * _Introduction to Algorithms_, Cormen, Leiserson, and Rivest, + * \li "Introduction to Algorithms," Cormen, Leiserson, and Rivest, * MIT Press / McGraw Hill, 1990, ISBN 0-262-03141-8, chapter 7. * - * _Algorithms_, Second Edition, Sedgewick, Addison-Wesley, 1988, + * \li "Algorithms," Second Edition, Sedgewick, Addison-Wesley, 1988, * ISBN 0-201-06673-4, chapter 11. */ @@ -35,20 +35,23 @@ #include <isc/string.h> /* Required for memcpy. */ #include <isc/util.h> -/* +/*@{*/ +/*% * Note: to make heap_parent and heap_left easy to compute, the first * element of the heap array is not used; i.e. heap subscripts are 1-based, - * not 0-based. + * not 0-based. The parent is index/2, and the left-child is index*2. + * The right child is index*2+1. */ #define heap_parent(i) ((i) >> 1) #define heap_left(i) ((i) << 1) +/*@}*/ #define SIZE_INCREMENT 1024 #define HEAP_MAGIC ISC_MAGIC('H', 'E', 'A', 'P') #define VALID_HEAP(h) ISC_MAGIC_VALID(h, HEAP_MAGIC) -/* +/*% * When the heap is in a consistent state, the following invariant * holds true: for every element i > 1, heap_parent(i) has a priority * higher than or equal to that of i. @@ -57,6 +60,7 @@ ! heap->compare(heap->array[(i)], \ heap->array[heap_parent(i)])) +/*% ISC heap structure. */ struct isc_heap { unsigned int magic; isc_mem_t * mctx; @@ -141,8 +145,8 @@ static void float_up(isc_heap_t *heap, unsigned int i, void *elt) { unsigned int p; - for (p = heap_parent(i); - i > 1 && heap->compare(elt, heap->array[p]); + for (p = heap_parent(i) ; + i > 1 && heap->compare(elt, heap->array[p]) ; i = p, p = heap_parent(i)) { heap->array[i] = heap->array[p]; if (heap->index != NULL) @@ -196,48 +200,48 @@ isc_heap_insert(isc_heap_t *heap, void *elt) { } void -isc_heap_delete(isc_heap_t *heap, unsigned int i) { +isc_heap_delete(isc_heap_t *heap, unsigned int index) { void *elt; isc_boolean_t less; REQUIRE(VALID_HEAP(heap)); - REQUIRE(i >= 1 && i <= heap->last); + REQUIRE(index >= 1 && index <= heap->last); - if (i == heap->last) { + if (index == heap->last) { heap->last--; } else { elt = heap->array[heap->last--]; - less = heap->compare(elt, heap->array[i]); - heap->array[i] = elt; + less = heap->compare(elt, heap->array[index]); + heap->array[index] = elt; if (less) - float_up(heap, i, heap->array[i]); + float_up(heap, index, heap->array[index]); else - sink_down(heap, i, heap->array[i]); + sink_down(heap, index, heap->array[index]); } } void -isc_heap_increased(isc_heap_t *heap, unsigned int i) { +isc_heap_increased(isc_heap_t *heap, unsigned int index) { REQUIRE(VALID_HEAP(heap)); - REQUIRE(i >= 1 && i <= heap->last); + REQUIRE(index >= 1 && index <= heap->last); - float_up(heap, i, heap->array[i]); + float_up(heap, index, heap->array[index]); } void -isc_heap_decreased(isc_heap_t *heap, unsigned int i) { +isc_heap_decreased(isc_heap_t *heap, unsigned int index) { REQUIRE(VALID_HEAP(heap)); - REQUIRE(i >= 1 && i <= heap->last); + REQUIRE(index >= 1 && index <= heap->last); - sink_down(heap, i, heap->array[i]); + sink_down(heap, index, heap->array[index]); } void * -isc_heap_element(isc_heap_t *heap, unsigned int i) { +isc_heap_element(isc_heap_t *heap, unsigned int index) { REQUIRE(VALID_HEAP(heap)); - REQUIRE(i >= 1 && i <= heap->last); + REQUIRE(index >= 1 && index <= heap->last); - return (heap->array[i]); + return (heap->array[index]); } void @@ -247,6 +251,6 @@ isc_heap_foreach(isc_heap_t *heap, isc_heapaction_t action, void *uap) { REQUIRE(VALID_HEAP(heap)); REQUIRE(action != NULL); - for (i = 1; i <= heap->last; i++) + for (i = 1 ; i <= heap->last ; i++) (action)(heap->array[i], uap); } |
