heap.c revision 193149
1181641Skmacy/* 2181641Skmacy * Copyright (C) 2004-2007 Internet Systems Consortium, Inc. ("ISC") 3181641Skmacy * Copyright (C) 1997-2001 Internet Software Consortium. 4181641Skmacy * 5181641Skmacy * Permission to use, copy, modify, and/or distribute this software for any 6181641Skmacy * purpose with or without fee is hereby granted, provided that the above 7181641Skmacy * copyright notice and this permission notice appear in all copies. 8181641Skmacy * 9181641Skmacy * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH 10181641Skmacy * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 11181641Skmacy * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, 12181641Skmacy * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 13181641Skmacy * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 14181641Skmacy * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 15181641Skmacy * PERFORMANCE OF THIS SOFTWARE. 16181641Skmacy */ 17181641Skmacy 18181641Skmacy/* $Id: heap.c,v 1.37 2007/10/19 17:15:53 explorer Exp $ */ 19181641Skmacy 20181641Skmacy/*! \file 21181641Skmacy * Heap implementation of priority queues adapted from the following: 22181641Skmacy * 23181641Skmacy * \li "Introduction to Algorithms," Cormen, Leiserson, and Rivest, 24181641Skmacy * MIT Press / McGraw Hill, 1990, ISBN 0-262-03141-8, chapter 7. 25181641Skmacy * 26181641Skmacy * \li "Algorithms," Second Edition, Sedgewick, Addison-Wesley, 1988, 27181641Skmacy * ISBN 0-201-06673-4, chapter 11. 28181641Skmacy */ 29181641Skmacy 30181641Skmacy#include <config.h> 31181641Skmacy 32181641Skmacy#include <isc/heap.h> 33181641Skmacy#include <isc/magic.h> 34181641Skmacy#include <isc/mem.h> 35181641Skmacy#include <isc/string.h> /* Required for memcpy. */ 36181641Skmacy#include <isc/util.h> 37181641Skmacy 38181641Skmacy/*@{*/ 39181641Skmacy/*% 40181641Skmacy * Note: to make heap_parent and heap_left easy to compute, the first 41181641Skmacy * element of the heap array is not used; i.e. heap subscripts are 1-based, 42181641Skmacy * not 0-based. The parent is index/2, and the left-child is index*2. 43181641Skmacy * The right child is index*2+1. 44181641Skmacy */ 45181641Skmacy#define heap_parent(i) ((i) >> 1) 46181641Skmacy#define heap_left(i) ((i) << 1) 47181641Skmacy/*@}*/ 48181641Skmacy 49181641Skmacy#define SIZE_INCREMENT 1024 50181641Skmacy 51181641Skmacy#define HEAP_MAGIC ISC_MAGIC('H', 'E', 'A', 'P') 52181641Skmacy#define VALID_HEAP(h) ISC_MAGIC_VALID(h, HEAP_MAGIC) 53181641Skmacy 54181641Skmacy/*% 55181641Skmacy * When the heap is in a consistent state, the following invariant 56181641Skmacy * holds true: for every element i > 1, heap_parent(i) has a priority 57181641Skmacy * higher than or equal to that of i. 58181641Skmacy */ 59181641Skmacy#define HEAPCONDITION(i) ((i) == 1 || \ 60181641Skmacy ! heap->compare(heap->array[(i)], \ 61181641Skmacy heap->array[heap_parent(i)])) 62181641Skmacy 63181641Skmacy/*% ISC heap structure. */ 64181641Skmacystruct isc_heap { 65181641Skmacy unsigned int magic; 66181641Skmacy isc_mem_t * mctx; 67181641Skmacy unsigned int size; 68181641Skmacy unsigned int size_increment; 69181641Skmacy unsigned int last; 70181641Skmacy void **array; 71181641Skmacy isc_heapcompare_t compare; 72181641Skmacy isc_heapindex_t index; 73181641Skmacy}; 74181641Skmacy 75181641Skmacyisc_result_t 76181641Skmacyisc_heap_create(isc_mem_t *mctx, isc_heapcompare_t compare, 77181641Skmacy isc_heapindex_t index, unsigned int size_increment, 78181641Skmacy isc_heap_t **heapp) 79181641Skmacy{ 80181641Skmacy isc_heap_t *heap; 81181641Skmacy 82181641Skmacy REQUIRE(heapp != NULL && *heapp == NULL); 83181641Skmacy REQUIRE(compare != NULL); 84181641Skmacy 85181641Skmacy heap = isc_mem_get(mctx, sizeof(*heap)); 86181641Skmacy if (heap == NULL) 87181641Skmacy return (ISC_R_NOMEMORY); 88181641Skmacy heap->magic = HEAP_MAGIC; 89181641Skmacy heap->mctx = mctx; 90181641Skmacy heap->size = 0; 91181641Skmacy if (size_increment == 0) 92181641Skmacy heap->size_increment = SIZE_INCREMENT; 93181641Skmacy else 94181641Skmacy heap->size_increment = size_increment; 95181641Skmacy heap->last = 0; 96181641Skmacy heap->array = NULL; 97181641Skmacy heap->compare = compare; 98181641Skmacy heap->index = index; 99181641Skmacy 100181641Skmacy *heapp = heap; 101181641Skmacy 102181641Skmacy return (ISC_R_SUCCESS); 103181641Skmacy} 104181641Skmacy 105181641Skmacyvoid 106181641Skmacyisc_heap_destroy(isc_heap_t **heapp) { 107181641Skmacy isc_heap_t *heap; 108181641Skmacy 109181641Skmacy REQUIRE(heapp != NULL); 110181641Skmacy heap = *heapp; 111181641Skmacy REQUIRE(VALID_HEAP(heap)); 112181641Skmacy 113181641Skmacy if (heap->array != NULL) 114181641Skmacy isc_mem_put(heap->mctx, heap->array, 115181641Skmacy heap->size * sizeof(void *)); 116181641Skmacy heap->magic = 0; 117181641Skmacy isc_mem_put(heap->mctx, heap, sizeof(*heap)); 118181641Skmacy 119181641Skmacy *heapp = NULL; 120181641Skmacy} 121181641Skmacy 122181641Skmacystatic isc_boolean_t 123181641Skmacyresize(isc_heap_t *heap) { 124195949Skib void **new_array; 125181641Skmacy size_t new_size; 126181641Skmacy 127181641Skmacy REQUIRE(VALID_HEAP(heap)); 128181641Skmacy 129181641Skmacy new_size = heap->size + heap->size_increment; 130181641Skmacy new_array = isc_mem_get(heap->mctx, new_size * sizeof(void *)); 131181641Skmacy if (new_array == NULL) 132181641Skmacy return (ISC_FALSE); 133181641Skmacy if (heap->array != NULL) { 134181641Skmacy memcpy(new_array, heap->array, heap->size * sizeof(void *)); 135181641Skmacy isc_mem_put(heap->mctx, heap->array, 136181641Skmacy heap->size * sizeof(void *)); 137181641Skmacy } 138181641Skmacy heap->size = new_size; 139181641Skmacy heap->array = new_array; 140181641Skmacy 141181641Skmacy return (ISC_TRUE); 142181641Skmacy} 143181641Skmacy 144181641Skmacystatic void 145181641Skmacyfloat_up(isc_heap_t *heap, unsigned int i, void *elt) { 146181641Skmacy unsigned int p; 147181641Skmacy 148181641Skmacy for (p = heap_parent(i) ; 149181641Skmacy i > 1 && heap->compare(elt, heap->array[p]) ; 150181641Skmacy i = p, p = heap_parent(i)) { 151181641Skmacy heap->array[i] = heap->array[p]; 152181641Skmacy if (heap->index != NULL) 153181641Skmacy (heap->index)(heap->array[i], i); 154181641Skmacy } 155181641Skmacy heap->array[i] = elt; 156181641Skmacy if (heap->index != NULL) 157181641Skmacy (heap->index)(heap->array[i], i); 158186557Skmacy 159181641Skmacy INSIST(HEAPCONDITION(i)); 160181641Skmacy} 161181641Skmacy 162181641Skmacystatic void 163181641Skmacysink_down(isc_heap_t *heap, unsigned int i, void *elt) { 164181641Skmacy unsigned int j, size, half_size; 165181641Skmacy size = heap->last; 166181641Skmacy half_size = size / 2; 167181641Skmacy while (i <= half_size) { 168181641Skmacy /* Find the smallest of the (at most) two children. */ 169181641Skmacy j = heap_left(i); 170181641Skmacy if (j < size && heap->compare(heap->array[j+1], 171181641Skmacy heap->array[j])) 172181641Skmacy j++; 173181641Skmacy if (heap->compare(elt, heap->array[j])) 174181641Skmacy break; 175181641Skmacy heap->array[i] = heap->array[j]; 176204041Sed if (heap->index != NULL) 177204041Sed (heap->index)(heap->array[i], i); 178204041Sed i = j; 179202628Sed } 180204041Sed heap->array[i] = elt; 181181641Skmacy if (heap->index != NULL) 182181641Skmacy (heap->index)(heap->array[i], i); 183181641Skmacy 184181641Skmacy INSIST(HEAPCONDITION(i)); 185181641Skmacy} 186181641Skmacy 187181641Skmacyisc_result_t 188181641Skmacyisc_heap_insert(isc_heap_t *heap, void *elt) { 189181641Skmacy unsigned int i; 190181641Skmacy 191181641Skmacy REQUIRE(VALID_HEAP(heap)); 192181747Skmacy 193181747Skmacy i = ++heap->last; 194181747Skmacy if (heap->last >= heap->size && !resize(heap)) 195181641Skmacy return (ISC_R_NOMEMORY); 196181641Skmacy 197181641Skmacy float_up(heap, i, elt); 198181641Skmacy 199181641Skmacy return (ISC_R_SUCCESS); 200181641Skmacy} 201181641Skmacy 202181641Skmacyvoid 203181641Skmacyisc_heap_delete(isc_heap_t *heap, unsigned int index) { 204181641Skmacy void *elt; 205181641Skmacy isc_boolean_t less; 206181641Skmacy 207181641Skmacy REQUIRE(VALID_HEAP(heap)); 208181641Skmacy REQUIRE(index >= 1 && index <= heap->last); 209181641Skmacy 210181641Skmacy if (index == heap->last) { 211181641Skmacy heap->array[heap->last] = NULL; 212181641Skmacy heap->last--; 213181641Skmacy } else { 214181641Skmacy elt = heap->array[heap->last]; 215181641Skmacy heap->array[heap->last] = NULL; 216181641Skmacy heap->last--; 217181641Skmacy 218181641Skmacy less = heap->compare(elt, heap->array[index]); 219182902Skmacy heap->array[index] = elt; 220181641Skmacy if (less) 221181641Skmacy float_up(heap, index, heap->array[index]); 222181641Skmacy else 223181641Skmacy sink_down(heap, index, heap->array[index]); 224181641Skmacy } 225181641Skmacy} 226181641Skmacy 227181641Skmacyvoid 228181641Skmacyisc_heap_increased(isc_heap_t *heap, unsigned int index) { 229181641Skmacy REQUIRE(VALID_HEAP(heap)); 230196726Sadrian REQUIRE(index >= 1 && index <= heap->last); 231196726Sadrian 232181641Skmacy float_up(heap, index, heap->array[index]); 233181641Skmacy} 234181641Skmacy 235181641Skmacyvoid 236181747Skmacyisc_heap_decreased(isc_heap_t *heap, unsigned int index) { 237181641Skmacy REQUIRE(VALID_HEAP(heap)); 238181641Skmacy REQUIRE(index >= 1 && index <= heap->last); 239181641Skmacy 240181641Skmacy sink_down(heap, index, heap->array[index]); 241181641Skmacy} 242181641Skmacy 243181641Skmacyvoid * 244181641Skmacyisc_heap_element(isc_heap_t *heap, unsigned int index) { 245181641Skmacy REQUIRE(VALID_HEAP(heap)); 246181641Skmacy REQUIRE(index >= 1); 247181641Skmacy 248181641Skmacy if (index <= heap->last) 249181641Skmacy return (heap->array[index]); 250181641Skmacy return (NULL); 251181641Skmacy} 252181641Skmacy 253181641Skmacyvoid 254181641Skmacyisc_heap_foreach(isc_heap_t *heap, isc_heapaction_t action, void *uap) { 255204160Skmacy unsigned int i; 256181641Skmacy 257181641Skmacy REQUIRE(VALID_HEAP(heap)); 258181641Skmacy REQUIRE(action != NULL); 259181641Skmacy 260181641Skmacy for (i = 1 ; i <= heap->last ; i++) 261181641Skmacy (action)(heap->array[i], uap); 262181641Skmacy} 263181641Skmacy