heap.c revision 170223
1241754Suqs/* 2241754Suqs * Copyright (C) 2004-2006 Internet Systems Consortium, Inc. ("ISC") 3241754Suqs * Copyright (C) 1997-2001 Internet Software Consortium. 4241754Suqs * 5241754Suqs * Permission to use, copy, modify, and distribute this software for any 6241754Suqs * purpose with or without fee is hereby granted, provided that the above 7241754Suqs * copyright notice and this permission notice appear in all copies. 8241754Suqs * 9241754Suqs * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH 10241754Suqs * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 11241754Suqs * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, 12241754Suqs * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 13241754Suqs * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 14241754Suqs * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 15241754Suqs * PERFORMANCE OF THIS SOFTWARE. 16241754Suqs */ 17241754Suqs 18241754Suqs/* $Id: heap.c,v 1.30.18.3 2006/04/17 18:27:33 explorer Exp $ */ 19241754Suqs 20241754Suqs/*! \file 21241754Suqs * Heap implementation of priority queues adapted from the following: 22241754Suqs * 23 * \li "Introduction to Algorithms," Cormen, Leiserson, and Rivest, 24 * MIT Press / McGraw Hill, 1990, ISBN 0-262-03141-8, chapter 7. 25 * 26 * \li "Algorithms," Second Edition, Sedgewick, Addison-Wesley, 1988, 27 * ISBN 0-201-06673-4, chapter 11. 28 */ 29 30#include <config.h> 31 32#include <isc/heap.h> 33#include <isc/magic.h> 34#include <isc/mem.h> 35#include <isc/string.h> /* Required for memcpy. */ 36#include <isc/util.h> 37 38/*@{*/ 39/*% 40 * Note: to make heap_parent and heap_left easy to compute, the first 41 * element of the heap array is not used; i.e. heap subscripts are 1-based, 42 * not 0-based. The parent is index/2, and the left-child is index*2. 43 * The right child is index*2+1. 44 */ 45#define heap_parent(i) ((i) >> 1) 46#define heap_left(i) ((i) << 1) 47/*@}*/ 48 49#define SIZE_INCREMENT 1024 50 51#define HEAP_MAGIC ISC_MAGIC('H', 'E', 'A', 'P') 52#define VALID_HEAP(h) ISC_MAGIC_VALID(h, HEAP_MAGIC) 53 54/*% 55 * When the heap is in a consistent state, the following invariant 56 * holds true: for every element i > 1, heap_parent(i) has a priority 57 * higher than or equal to that of i. 58 */ 59#define HEAPCONDITION(i) ((i) == 1 || \ 60 ! heap->compare(heap->array[(i)], \ 61 heap->array[heap_parent(i)])) 62 63/*% ISC heap structure. */ 64struct isc_heap { 65 unsigned int magic; 66 isc_mem_t * mctx; 67 unsigned int size; 68 unsigned int size_increment; 69 unsigned int last; 70 void **array; 71 isc_heapcompare_t compare; 72 isc_heapindex_t index; 73}; 74 75isc_result_t 76isc_heap_create(isc_mem_t *mctx, isc_heapcompare_t compare, 77 isc_heapindex_t index, unsigned int size_increment, 78 isc_heap_t **heapp) 79{ 80 isc_heap_t *heap; 81 82 REQUIRE(heapp != NULL && *heapp == NULL); 83 REQUIRE(compare != NULL); 84 85 heap = isc_mem_get(mctx, sizeof(*heap)); 86 if (heap == NULL) 87 return (ISC_R_NOMEMORY); 88 heap->magic = HEAP_MAGIC; 89 heap->mctx = mctx; 90 heap->size = 0; 91 if (size_increment == 0) 92 heap->size_increment = SIZE_INCREMENT; 93 else 94 heap->size_increment = size_increment; 95 heap->last = 0; 96 heap->array = NULL; 97 heap->compare = compare; 98 heap->index = index; 99 100 *heapp = heap; 101 102 return (ISC_R_SUCCESS); 103} 104 105void 106isc_heap_destroy(isc_heap_t **heapp) { 107 isc_heap_t *heap; 108 109 REQUIRE(heapp != NULL); 110 heap = *heapp; 111 REQUIRE(VALID_HEAP(heap)); 112 113 if (heap->array != NULL) 114 isc_mem_put(heap->mctx, heap->array, 115 heap->size * sizeof(void *)); 116 heap->magic = 0; 117 isc_mem_put(heap->mctx, heap, sizeof(*heap)); 118 119 *heapp = NULL; 120} 121 122static isc_boolean_t 123resize(isc_heap_t *heap) { 124 void **new_array; 125 size_t new_size; 126 127 REQUIRE(VALID_HEAP(heap)); 128 129 new_size = heap->size + heap->size_increment; 130 new_array = isc_mem_get(heap->mctx, new_size * sizeof(void *)); 131 if (new_array == NULL) 132 return (ISC_FALSE); 133 if (heap->array != NULL) { 134 memcpy(new_array, heap->array, heap->size * sizeof(void *)); 135 isc_mem_put(heap->mctx, heap->array, 136 heap->size * sizeof(void *)); 137 } 138 heap->size = new_size; 139 heap->array = new_array; 140 141 return (ISC_TRUE); 142} 143 144static void 145float_up(isc_heap_t *heap, unsigned int i, void *elt) { 146 unsigned int p; 147 148 for (p = heap_parent(i) ; 149 i > 1 && heap->compare(elt, heap->array[p]) ; 150 i = p, p = heap_parent(i)) { 151 heap->array[i] = heap->array[p]; 152 if (heap->index != NULL) 153 (heap->index)(heap->array[i], i); 154 } 155 heap->array[i] = elt; 156 if (heap->index != NULL) 157 (heap->index)(heap->array[i], i); 158 159 INSIST(HEAPCONDITION(i)); 160} 161 162static void 163sink_down(isc_heap_t *heap, unsigned int i, void *elt) { 164 unsigned int j, size, half_size; 165 size = heap->last; 166 half_size = size / 2; 167 while (i <= half_size) { 168 /* Find the smallest of the (at most) two children. */ 169 j = heap_left(i); 170 if (j < size && heap->compare(heap->array[j+1], 171 heap->array[j])) 172 j++; 173 if (heap->compare(elt, heap->array[j])) 174 break; 175 heap->array[i] = heap->array[j]; 176 if (heap->index != NULL) 177 (heap->index)(heap->array[i], i); 178 i = j; 179 } 180 heap->array[i] = elt; 181 if (heap->index != NULL) 182 (heap->index)(heap->array[i], i); 183 184 INSIST(HEAPCONDITION(i)); 185} 186 187isc_result_t 188isc_heap_insert(isc_heap_t *heap, void *elt) { 189 unsigned int i; 190 191 REQUIRE(VALID_HEAP(heap)); 192 193 i = ++heap->last; 194 if (heap->last >= heap->size && !resize(heap)) 195 return (ISC_R_NOMEMORY); 196 197 float_up(heap, i, elt); 198 199 return (ISC_R_SUCCESS); 200} 201 202void 203isc_heap_delete(isc_heap_t *heap, unsigned int index) { 204 void *elt; 205 isc_boolean_t less; 206 207 REQUIRE(VALID_HEAP(heap)); 208 REQUIRE(index >= 1 && index <= heap->last); 209 210 if (index == heap->last) { 211 heap->last--; 212 } else { 213 elt = heap->array[heap->last--]; 214 less = heap->compare(elt, heap->array[index]); 215 heap->array[index] = elt; 216 if (less) 217 float_up(heap, index, heap->array[index]); 218 else 219 sink_down(heap, index, heap->array[index]); 220 } 221} 222 223void 224isc_heap_increased(isc_heap_t *heap, unsigned int index) { 225 REQUIRE(VALID_HEAP(heap)); 226 REQUIRE(index >= 1 && index <= heap->last); 227 228 float_up(heap, index, heap->array[index]); 229} 230 231void 232isc_heap_decreased(isc_heap_t *heap, unsigned int index) { 233 REQUIRE(VALID_HEAP(heap)); 234 REQUIRE(index >= 1 && index <= heap->last); 235 236 sink_down(heap, index, heap->array[index]); 237} 238 239void * 240isc_heap_element(isc_heap_t *heap, unsigned int index) { 241 REQUIRE(VALID_HEAP(heap)); 242 REQUIRE(index >= 1 && index <= heap->last); 243 244 return (heap->array[index]); 245} 246 247void 248isc_heap_foreach(isc_heap_t *heap, isc_heapaction_t action, void *uap) { 249 unsigned int i; 250 251 REQUIRE(VALID_HEAP(heap)); 252 REQUIRE(action != NULL); 253 254 for (i = 1 ; i <= heap->last ; i++) 255 (action)(heap->array[i], uap); 256} 257