1258945Sroberto/* 2280849Scy * Copyright (C) 2004-2007, 2010-2012 Internet Systems Consortium, Inc. ("ISC") 3258945Sroberto * Copyright (C) 1997-2001 Internet Software Consortium. 4258945Sroberto * 5258945Sroberto * Permission to use, copy, modify, and/or distribute this software for any 6258945Sroberto * purpose with or without fee is hereby granted, provided that the above 7258945Sroberto * copyright notice and this permission notice appear in all copies. 8258945Sroberto * 9258945Sroberto * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH 10258945Sroberto * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 11258945Sroberto * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, 12258945Sroberto * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 13258945Sroberto * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 14258945Sroberto * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 15258945Sroberto * PERFORMANCE OF THIS SOFTWARE. 16258945Sroberto */ 17258945Sroberto 18280849Scy/* $Id$ */ 19258945Sroberto 20258945Sroberto/*! \file 21258945Sroberto * Heap implementation of priority queues adapted from the following: 22258945Sroberto * 23258945Sroberto * \li "Introduction to Algorithms," Cormen, Leiserson, and Rivest, 24258945Sroberto * MIT Press / McGraw Hill, 1990, ISBN 0-262-03141-8, chapter 7. 25258945Sroberto * 26258945Sroberto * \li "Algorithms," Second Edition, Sedgewick, Addison-Wesley, 1988, 27258945Sroberto * ISBN 0-201-06673-4, chapter 11. 28258945Sroberto */ 29258945Sroberto 30258945Sroberto#include <config.h> 31258945Sroberto 32258945Sroberto#include <isc/heap.h> 33258945Sroberto#include <isc/magic.h> 34258945Sroberto#include <isc/mem.h> 35258945Sroberto#include <isc/string.h> /* Required for memcpy. */ 36258945Sroberto#include <isc/util.h> 37258945Sroberto 38258945Sroberto/*@{*/ 39258945Sroberto/*% 40258945Sroberto * Note: to make heap_parent and heap_left easy to compute, the first 41258945Sroberto * element of the heap array is not used; i.e. heap subscripts are 1-based, 42258945Sroberto * not 0-based. The parent is index/2, and the left-child is index*2. 43258945Sroberto * The right child is index*2+1. 44258945Sroberto */ 45258945Sroberto#define heap_parent(i) ((i) >> 1) 46258945Sroberto#define heap_left(i) ((i) << 1) 47258945Sroberto/*@}*/ 48258945Sroberto 49258945Sroberto#define SIZE_INCREMENT 1024 50258945Sroberto 51258945Sroberto#define HEAP_MAGIC ISC_MAGIC('H', 'E', 'A', 'P') 52258945Sroberto#define VALID_HEAP(h) ISC_MAGIC_VALID(h, HEAP_MAGIC) 53258945Sroberto 54258945Sroberto/*% 55258945Sroberto * When the heap is in a consistent state, the following invariant 56258945Sroberto * holds true: for every element i > 1, heap_parent(i) has a priority 57258945Sroberto * higher than or equal to that of i. 58258945Sroberto */ 59258945Sroberto#define HEAPCONDITION(i) ((i) == 1 || \ 60258945Sroberto ! heap->compare(heap->array[(i)], \ 61258945Sroberto heap->array[heap_parent(i)])) 62258945Sroberto 63258945Sroberto/*% ISC heap structure. */ 64258945Srobertostruct isc_heap { 65258945Sroberto unsigned int magic; 66258945Sroberto isc_mem_t * mctx; 67258945Sroberto unsigned int size; 68258945Sroberto unsigned int size_increment; 69258945Sroberto unsigned int last; 70258945Sroberto void **array; 71258945Sroberto isc_heapcompare_t compare; 72258945Sroberto isc_heapindex_t index; 73258945Sroberto}; 74258945Sroberto 75258945Srobertoisc_result_t 76258945Srobertoisc_heap_create(isc_mem_t *mctx, isc_heapcompare_t compare, 77258945Sroberto isc_heapindex_t index, unsigned int size_increment, 78258945Sroberto isc_heap_t **heapp) 79258945Sroberto{ 80258945Sroberto isc_heap_t *heap; 81258945Sroberto 82258945Sroberto REQUIRE(heapp != NULL && *heapp == NULL); 83258945Sroberto REQUIRE(compare != NULL); 84258945Sroberto 85258945Sroberto heap = isc_mem_get(mctx, sizeof(*heap)); 86258945Sroberto if (heap == NULL) 87258945Sroberto return (ISC_R_NOMEMORY); 88258945Sroberto heap->magic = HEAP_MAGIC; 89258945Sroberto heap->size = 0; 90280849Scy heap->mctx = NULL; 91280849Scy isc_mem_attach(mctx, &heap->mctx); 92258945Sroberto if (size_increment == 0) 93258945Sroberto heap->size_increment = SIZE_INCREMENT; 94258945Sroberto else 95258945Sroberto heap->size_increment = size_increment; 96258945Sroberto heap->last = 0; 97258945Sroberto heap->array = NULL; 98258945Sroberto heap->compare = compare; 99258945Sroberto heap->index = index; 100258945Sroberto 101258945Sroberto *heapp = heap; 102258945Sroberto 103258945Sroberto return (ISC_R_SUCCESS); 104258945Sroberto} 105258945Sroberto 106258945Srobertovoid 107258945Srobertoisc_heap_destroy(isc_heap_t **heapp) { 108258945Sroberto isc_heap_t *heap; 109258945Sroberto 110258945Sroberto REQUIRE(heapp != NULL); 111258945Sroberto heap = *heapp; 112258945Sroberto REQUIRE(VALID_HEAP(heap)); 113258945Sroberto 114258945Sroberto if (heap->array != NULL) 115258945Sroberto isc_mem_put(heap->mctx, heap->array, 116258945Sroberto heap->size * sizeof(void *)); 117258945Sroberto heap->magic = 0; 118280849Scy isc_mem_putanddetach(&heap->mctx, heap, sizeof(*heap)); 119258945Sroberto 120258945Sroberto *heapp = NULL; 121258945Sroberto} 122258945Sroberto 123258945Srobertostatic isc_boolean_t 124258945Srobertoresize(isc_heap_t *heap) { 125258945Sroberto void **new_array; 126258945Sroberto size_t new_size; 127258945Sroberto 128258945Sroberto REQUIRE(VALID_HEAP(heap)); 129258945Sroberto 130258945Sroberto new_size = heap->size + heap->size_increment; 131258945Sroberto new_array = isc_mem_get(heap->mctx, new_size * sizeof(void *)); 132258945Sroberto if (new_array == NULL) 133258945Sroberto return (ISC_FALSE); 134258945Sroberto if (heap->array != NULL) { 135258945Sroberto memcpy(new_array, heap->array, heap->size * sizeof(void *)); 136258945Sroberto isc_mem_put(heap->mctx, heap->array, 137258945Sroberto heap->size * sizeof(void *)); 138258945Sroberto } 139258945Sroberto heap->size = new_size; 140258945Sroberto heap->array = new_array; 141258945Sroberto 142258945Sroberto return (ISC_TRUE); 143258945Sroberto} 144258945Sroberto 145258945Srobertostatic void 146258945Srobertofloat_up(isc_heap_t *heap, unsigned int i, void *elt) { 147258945Sroberto unsigned int p; 148258945Sroberto 149258945Sroberto for (p = heap_parent(i) ; 150258945Sroberto i > 1 && heap->compare(elt, heap->array[p]) ; 151258945Sroberto i = p, p = heap_parent(i)) { 152258945Sroberto heap->array[i] = heap->array[p]; 153258945Sroberto if (heap->index != NULL) 154258945Sroberto (heap->index)(heap->array[i], i); 155258945Sroberto } 156258945Sroberto heap->array[i] = elt; 157258945Sroberto if (heap->index != NULL) 158258945Sroberto (heap->index)(heap->array[i], i); 159258945Sroberto 160258945Sroberto INSIST(HEAPCONDITION(i)); 161258945Sroberto} 162258945Sroberto 163258945Srobertostatic void 164258945Srobertosink_down(isc_heap_t *heap, unsigned int i, void *elt) { 165258945Sroberto unsigned int j, size, half_size; 166258945Sroberto size = heap->last; 167258945Sroberto half_size = size / 2; 168258945Sroberto while (i <= half_size) { 169258945Sroberto /* Find the smallest of the (at most) two children. */ 170258945Sroberto j = heap_left(i); 171258945Sroberto if (j < size && heap->compare(heap->array[j+1], 172258945Sroberto heap->array[j])) 173258945Sroberto j++; 174258945Sroberto if (heap->compare(elt, heap->array[j])) 175258945Sroberto break; 176258945Sroberto heap->array[i] = heap->array[j]; 177258945Sroberto if (heap->index != NULL) 178258945Sroberto (heap->index)(heap->array[i], i); 179258945Sroberto i = j; 180258945Sroberto } 181258945Sroberto heap->array[i] = elt; 182258945Sroberto if (heap->index != NULL) 183258945Sroberto (heap->index)(heap->array[i], i); 184258945Sroberto 185258945Sroberto INSIST(HEAPCONDITION(i)); 186258945Sroberto} 187258945Sroberto 188258945Srobertoisc_result_t 189258945Srobertoisc_heap_insert(isc_heap_t *heap, void *elt) { 190280849Scy unsigned int new_last; 191258945Sroberto 192258945Sroberto REQUIRE(VALID_HEAP(heap)); 193258945Sroberto 194280849Scy new_last = heap->last + 1; 195280849Scy RUNTIME_CHECK(new_last > 0); /* overflow check */ 196280849Scy if (new_last >= heap->size && !resize(heap)) 197258945Sroberto return (ISC_R_NOMEMORY); 198280849Scy heap->last = new_last; 199258945Sroberto 200280849Scy float_up(heap, new_last, elt); 201258945Sroberto 202258945Sroberto return (ISC_R_SUCCESS); 203258945Sroberto} 204258945Sroberto 205258945Srobertovoid 206258945Srobertoisc_heap_delete(isc_heap_t *heap, unsigned int index) { 207258945Sroberto void *elt; 208258945Sroberto isc_boolean_t less; 209258945Sroberto 210258945Sroberto REQUIRE(VALID_HEAP(heap)); 211258945Sroberto REQUIRE(index >= 1 && index <= heap->last); 212258945Sroberto 213258945Sroberto if (index == heap->last) { 214258945Sroberto heap->array[heap->last] = NULL; 215258945Sroberto heap->last--; 216258945Sroberto } else { 217258945Sroberto elt = heap->array[heap->last]; 218258945Sroberto heap->array[heap->last] = NULL; 219258945Sroberto heap->last--; 220258945Sroberto 221258945Sroberto less = heap->compare(elt, heap->array[index]); 222258945Sroberto heap->array[index] = elt; 223258945Sroberto if (less) 224258945Sroberto float_up(heap, index, heap->array[index]); 225258945Sroberto else 226258945Sroberto sink_down(heap, index, heap->array[index]); 227258945Sroberto } 228258945Sroberto} 229258945Sroberto 230258945Srobertovoid 231258945Srobertoisc_heap_increased(isc_heap_t *heap, unsigned int index) { 232258945Sroberto REQUIRE(VALID_HEAP(heap)); 233258945Sroberto REQUIRE(index >= 1 && index <= heap->last); 234258945Sroberto 235258945Sroberto float_up(heap, index, heap->array[index]); 236258945Sroberto} 237258945Sroberto 238258945Srobertovoid 239258945Srobertoisc_heap_decreased(isc_heap_t *heap, unsigned int index) { 240258945Sroberto REQUIRE(VALID_HEAP(heap)); 241258945Sroberto REQUIRE(index >= 1 && index <= heap->last); 242258945Sroberto 243258945Sroberto sink_down(heap, index, heap->array[index]); 244258945Sroberto} 245258945Sroberto 246258945Srobertovoid * 247258945Srobertoisc_heap_element(isc_heap_t *heap, unsigned int index) { 248258945Sroberto REQUIRE(VALID_HEAP(heap)); 249258945Sroberto REQUIRE(index >= 1); 250258945Sroberto 251258945Sroberto if (index <= heap->last) 252258945Sroberto return (heap->array[index]); 253258945Sroberto return (NULL); 254258945Sroberto} 255258945Sroberto 256258945Srobertovoid 257258945Srobertoisc_heap_foreach(isc_heap_t *heap, isc_heapaction_t action, void *uap) { 258258945Sroberto unsigned int i; 259258945Sroberto 260258945Sroberto REQUIRE(VALID_HEAP(heap)); 261258945Sroberto REQUIRE(action != NULL); 262258945Sroberto 263258945Sroberto for (i = 1 ; i <= heap->last ; i++) 264258945Sroberto (action)(heap->array[i], uap); 265258945Sroberto} 266