1135446Strhodes/* 2262706Serwin * Copyright (C) 2004-2007, 2010-2014 Internet Systems Consortium, Inc. ("ISC") 3135446Strhodes * Copyright (C) 1997-2001 Internet Software Consortium. 4135446Strhodes * 5193149Sdougb * Permission to use, copy, modify, and/or distribute this software for any 6135446Strhodes * purpose with or without fee is hereby granted, provided that the above 7135446Strhodes * copyright notice and this permission notice appear in all copies. 8135446Strhodes * 9135446Strhodes * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH 10135446Strhodes * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 11135446Strhodes * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, 12135446Strhodes * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 13135446Strhodes * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 14135446Strhodes * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 15135446Strhodes * PERFORMANCE OF THIS SOFTWARE. 16135446Strhodes */ 17135446Strhodes 18234010Sdougb/* $Id$ */ 19135446Strhodes 20165071Sdougb/*! \file 21135446Strhodes * Heap implementation of priority queues adapted from the following: 22135446Strhodes * 23165071Sdougb * \li "Introduction to Algorithms," Cormen, Leiserson, and Rivest, 24135446Strhodes * MIT Press / McGraw Hill, 1990, ISBN 0-262-03141-8, chapter 7. 25135446Strhodes * 26165071Sdougb * \li "Algorithms," Second Edition, Sedgewick, Addison-Wesley, 1988, 27135446Strhodes * ISBN 0-201-06673-4, chapter 11. 28135446Strhodes */ 29135446Strhodes 30135446Strhodes#include <config.h> 31135446Strhodes 32135446Strhodes#include <isc/heap.h> 33135446Strhodes#include <isc/magic.h> 34135446Strhodes#include <isc/mem.h> 35262706Serwin#include <isc/string.h> /* Required for memmove. */ 36135446Strhodes#include <isc/util.h> 37135446Strhodes 38165071Sdougb/*@{*/ 39165071Sdougb/*% 40135446Strhodes * Note: to make heap_parent and heap_left easy to compute, the first 41135446Strhodes * element of the heap array is not used; i.e. heap subscripts are 1-based, 42165071Sdougb * not 0-based. The parent is index/2, and the left-child is index*2. 43165071Sdougb * The right child is index*2+1. 44135446Strhodes */ 45135446Strhodes#define heap_parent(i) ((i) >> 1) 46135446Strhodes#define heap_left(i) ((i) << 1) 47165071Sdougb/*@}*/ 48135446Strhodes 49135446Strhodes#define SIZE_INCREMENT 1024 50135446Strhodes 51135446Strhodes#define HEAP_MAGIC ISC_MAGIC('H', 'E', 'A', 'P') 52135446Strhodes#define VALID_HEAP(h) ISC_MAGIC_VALID(h, HEAP_MAGIC) 53135446Strhodes 54165071Sdougb/*% 55135446Strhodes * When the heap is in a consistent state, the following invariant 56135446Strhodes * holds true: for every element i > 1, heap_parent(i) has a priority 57135446Strhodes * higher than or equal to that of i. 58135446Strhodes */ 59135446Strhodes#define HEAPCONDITION(i) ((i) == 1 || \ 60135446Strhodes ! heap->compare(heap->array[(i)], \ 61135446Strhodes heap->array[heap_parent(i)])) 62135446Strhodes 63165071Sdougb/*% ISC heap structure. */ 64135446Strhodesstruct isc_heap { 65135446Strhodes unsigned int magic; 66135446Strhodes isc_mem_t * mctx; 67135446Strhodes unsigned int size; 68135446Strhodes unsigned int size_increment; 69135446Strhodes unsigned int last; 70135446Strhodes void **array; 71135446Strhodes isc_heapcompare_t compare; 72135446Strhodes isc_heapindex_t index; 73135446Strhodes}; 74135446Strhodes 75135446Strhodesisc_result_t 76135446Strhodesisc_heap_create(isc_mem_t *mctx, isc_heapcompare_t compare, 77135446Strhodes isc_heapindex_t index, unsigned int size_increment, 78135446Strhodes isc_heap_t **heapp) 79135446Strhodes{ 80135446Strhodes isc_heap_t *heap; 81135446Strhodes 82135446Strhodes REQUIRE(heapp != NULL && *heapp == NULL); 83135446Strhodes REQUIRE(compare != NULL); 84135446Strhodes 85135446Strhodes heap = isc_mem_get(mctx, sizeof(*heap)); 86135446Strhodes if (heap == NULL) 87135446Strhodes return (ISC_R_NOMEMORY); 88135446Strhodes heap->magic = HEAP_MAGIC; 89135446Strhodes heap->size = 0; 90225361Sdougb heap->mctx = NULL; 91225361Sdougb isc_mem_attach(mctx, &heap->mctx); 92135446Strhodes if (size_increment == 0) 93135446Strhodes heap->size_increment = SIZE_INCREMENT; 94135446Strhodes else 95135446Strhodes heap->size_increment = size_increment; 96135446Strhodes heap->last = 0; 97135446Strhodes heap->array = NULL; 98135446Strhodes heap->compare = compare; 99135446Strhodes heap->index = index; 100135446Strhodes 101135446Strhodes *heapp = heap; 102135446Strhodes 103135446Strhodes return (ISC_R_SUCCESS); 104135446Strhodes} 105135446Strhodes 106135446Strhodesvoid 107135446Strhodesisc_heap_destroy(isc_heap_t **heapp) { 108135446Strhodes isc_heap_t *heap; 109135446Strhodes 110135446Strhodes REQUIRE(heapp != NULL); 111135446Strhodes heap = *heapp; 112135446Strhodes REQUIRE(VALID_HEAP(heap)); 113135446Strhodes 114135446Strhodes if (heap->array != NULL) 115135446Strhodes isc_mem_put(heap->mctx, heap->array, 116135446Strhodes heap->size * sizeof(void *)); 117135446Strhodes heap->magic = 0; 118225361Sdougb isc_mem_putanddetach(&heap->mctx, heap, sizeof(*heap)); 119135446Strhodes 120135446Strhodes *heapp = NULL; 121135446Strhodes} 122135446Strhodes 123135446Strhodesstatic isc_boolean_t 124135446Strhodesresize(isc_heap_t *heap) { 125135446Strhodes void **new_array; 126262706Serwin unsigned int new_size; 127135446Strhodes 128135446Strhodes REQUIRE(VALID_HEAP(heap)); 129135446Strhodes 130135446Strhodes new_size = heap->size + heap->size_increment; 131135446Strhodes new_array = isc_mem_get(heap->mctx, new_size * sizeof(void *)); 132135446Strhodes if (new_array == NULL) 133135446Strhodes return (ISC_FALSE); 134135446Strhodes if (heap->array != NULL) { 135262706Serwin memmove(new_array, heap->array, heap->size * sizeof(void *)); 136135446Strhodes isc_mem_put(heap->mctx, heap->array, 137135446Strhodes heap->size * sizeof(void *)); 138135446Strhodes } 139135446Strhodes heap->size = new_size; 140135446Strhodes heap->array = new_array; 141135446Strhodes 142135446Strhodes return (ISC_TRUE); 143135446Strhodes} 144135446Strhodes 145135446Strhodesstatic void 146135446Strhodesfloat_up(isc_heap_t *heap, unsigned int i, void *elt) { 147135446Strhodes unsigned int p; 148135446Strhodes 149165071Sdougb for (p = heap_parent(i) ; 150165071Sdougb i > 1 && heap->compare(elt, heap->array[p]) ; 151135446Strhodes i = p, p = heap_parent(i)) { 152135446Strhodes heap->array[i] = heap->array[p]; 153135446Strhodes if (heap->index != NULL) 154135446Strhodes (heap->index)(heap->array[i], i); 155135446Strhodes } 156135446Strhodes heap->array[i] = elt; 157135446Strhodes if (heap->index != NULL) 158135446Strhodes (heap->index)(heap->array[i], i); 159135446Strhodes 160135446Strhodes INSIST(HEAPCONDITION(i)); 161135446Strhodes} 162135446Strhodes 163135446Strhodesstatic void 164135446Strhodessink_down(isc_heap_t *heap, unsigned int i, void *elt) { 165135446Strhodes unsigned int j, size, half_size; 166135446Strhodes size = heap->last; 167135446Strhodes half_size = size / 2; 168135446Strhodes while (i <= half_size) { 169135446Strhodes /* Find the smallest of the (at most) two children. */ 170135446Strhodes j = heap_left(i); 171135446Strhodes if (j < size && heap->compare(heap->array[j+1], 172135446Strhodes heap->array[j])) 173135446Strhodes j++; 174135446Strhodes if (heap->compare(elt, heap->array[j])) 175135446Strhodes break; 176135446Strhodes heap->array[i] = heap->array[j]; 177135446Strhodes if (heap->index != NULL) 178135446Strhodes (heap->index)(heap->array[i], i); 179135446Strhodes i = j; 180135446Strhodes } 181135446Strhodes heap->array[i] = elt; 182135446Strhodes if (heap->index != NULL) 183135446Strhodes (heap->index)(heap->array[i], i); 184135446Strhodes 185135446Strhodes INSIST(HEAPCONDITION(i)); 186135446Strhodes} 187135446Strhodes 188135446Strhodesisc_result_t 189135446Strhodesisc_heap_insert(isc_heap_t *heap, void *elt) { 190204619Sdougb unsigned int new_last; 191135446Strhodes 192135446Strhodes REQUIRE(VALID_HEAP(heap)); 193135446Strhodes 194204619Sdougb new_last = heap->last + 1; 195204619Sdougb RUNTIME_CHECK(new_last > 0); /* overflow check */ 196204619Sdougb if (new_last >= heap->size && !resize(heap)) 197135446Strhodes return (ISC_R_NOMEMORY); 198204619Sdougb heap->last = new_last; 199135446Strhodes 200204619Sdougb float_up(heap, new_last, elt); 201135446Strhodes 202135446Strhodes return (ISC_R_SUCCESS); 203135446Strhodes} 204135446Strhodes 205135446Strhodesvoid 206165071Sdougbisc_heap_delete(isc_heap_t *heap, unsigned int index) { 207135446Strhodes void *elt; 208135446Strhodes isc_boolean_t less; 209135446Strhodes 210135446Strhodes REQUIRE(VALID_HEAP(heap)); 211165071Sdougb REQUIRE(index >= 1 && index <= heap->last); 212135446Strhodes 213165071Sdougb if (index == heap->last) { 214193149Sdougb heap->array[heap->last] = NULL; 215135446Strhodes heap->last--; 216135446Strhodes } else { 217193149Sdougb elt = heap->array[heap->last]; 218193149Sdougb heap->array[heap->last] = NULL; 219193149Sdougb heap->last--; 220193149Sdougb 221165071Sdougb less = heap->compare(elt, heap->array[index]); 222165071Sdougb heap->array[index] = elt; 223135446Strhodes if (less) 224165071Sdougb float_up(heap, index, heap->array[index]); 225135446Strhodes else 226165071Sdougb sink_down(heap, index, heap->array[index]); 227135446Strhodes } 228135446Strhodes} 229135446Strhodes 230135446Strhodesvoid 231165071Sdougbisc_heap_increased(isc_heap_t *heap, unsigned int index) { 232135446Strhodes REQUIRE(VALID_HEAP(heap)); 233165071Sdougb REQUIRE(index >= 1 && index <= heap->last); 234135446Strhodes 235165071Sdougb float_up(heap, index, heap->array[index]); 236135446Strhodes} 237135446Strhodes 238135446Strhodesvoid 239165071Sdougbisc_heap_decreased(isc_heap_t *heap, unsigned int index) { 240135446Strhodes REQUIRE(VALID_HEAP(heap)); 241165071Sdougb REQUIRE(index >= 1 && index <= heap->last); 242135446Strhodes 243165071Sdougb sink_down(heap, index, heap->array[index]); 244135446Strhodes} 245135446Strhodes 246135446Strhodesvoid * 247165071Sdougbisc_heap_element(isc_heap_t *heap, unsigned int index) { 248135446Strhodes REQUIRE(VALID_HEAP(heap)); 249193149Sdougb REQUIRE(index >= 1); 250135446Strhodes 251193149Sdougb if (index <= heap->last) 252193149Sdougb return (heap->array[index]); 253193149Sdougb return (NULL); 254135446Strhodes} 255135446Strhodes 256135446Strhodesvoid 257135446Strhodesisc_heap_foreach(isc_heap_t *heap, isc_heapaction_t action, void *uap) { 258135446Strhodes unsigned int i; 259135446Strhodes 260135446Strhodes REQUIRE(VALID_HEAP(heap)); 261135446Strhodes REQUIRE(action != NULL); 262135446Strhodes 263165071Sdougb for (i = 1 ; i <= heap->last ; i++) 264135446Strhodes (action)(heap->array[i], uap); 265135446Strhodes} 266