heap.c revision 224092
1221807Sstas/* 2221807Sstas * Copyright (C) 2004-2007, 2010 Internet Systems Consortium, Inc. ("ISC") 3221807Sstas * Copyright (C) 1997-2001 Internet Software Consortium. 4221807Sstas * 5221807Sstas * Permission to use, copy, modify, and/or distribute this software for any 6221807Sstas * purpose with or without fee is hereby granted, provided that the above 7221807Sstas * copyright notice and this permission notice appear in all copies. 8221807Sstas * 9221807Sstas * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH 10221807Sstas * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 11221807Sstas * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, 12221807Sstas * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 13221807Sstas * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 14221807Sstas * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 15221807Sstas * PERFORMANCE OF THIS SOFTWARE. 16221807Sstas */ 17221807Sstas 18221807Sstas/* $Id: heap.c,v 1.39 2010-02-04 23:49:13 tbox Exp $ */ 19221807Sstas 20221807Sstas/*! \file 21221807Sstas * Heap implementation of priority queues adapted from the following: 22221807Sstas * 23221807Sstas * \li "Introduction to Algorithms," Cormen, Leiserson, and Rivest, 24221807Sstas * MIT Press / McGraw Hill, 1990, ISBN 0-262-03141-8, chapter 7. 25221807Sstas * 26221807Sstas * \li "Algorithms," Second Edition, Sedgewick, Addison-Wesley, 1988, 27221807Sstas * ISBN 0-201-06673-4, chapter 11. 28221807Sstas */ 29221807Sstas 30221807Sstas#include <config.h> 31221807Sstas 32221807Sstas#include <isc/heap.h> 33221807Sstas#include <isc/magic.h> 34221807Sstas#include <isc/mem.h> 35221807Sstas#include <isc/string.h> /* Required for memcpy. */ 36221807Sstas#include <isc/util.h> 37221807Sstas 38221807Sstas/*@{*/ 39221807Sstas/*% 40221807Sstas * Note: to make heap_parent and heap_left easy to compute, the first 41221807Sstas * element of the heap array is not used; i.e. heap subscripts are 1-based, 42221807Sstas * not 0-based. The parent is index/2, and the left-child is index*2. 43221807Sstas * The right child is index*2+1. 44221807Sstas */ 45221807Sstas#define heap_parent(i) ((i) >> 1) 46221807Sstas#define heap_left(i) ((i) << 1) 47221807Sstas/*@}*/ 48221807Sstas 49221807Sstas#define SIZE_INCREMENT 1024 50221807Sstas 51221807Sstas#define HEAP_MAGIC ISC_MAGIC('H', 'E', 'A', 'P') 52221807Sstas#define VALID_HEAP(h) ISC_MAGIC_VALID(h, HEAP_MAGIC) 53221807Sstas 54221807Sstas/*% 55227239Sed * When the heap is in a consistent state, the following invariant 56221807Sstas * holds true: for every element i > 1, heap_parent(i) has a priority 57221807Sstas * higher than or equal to that of i. 58221807Sstas */ 59221807Sstas#define HEAPCONDITION(i) ((i) == 1 || \ 60221807Sstas ! heap->compare(heap->array[(i)], \ 61221807Sstas heap->array[heap_parent(i)])) 62221807Sstas 63221807Sstas/*% ISC heap structure. */ 64221807Sstasstruct isc_heap { 65221807Sstas unsigned int magic; 66221807Sstas isc_mem_t * mctx; 67221807Sstas unsigned int size; 68221807Sstas unsigned int size_increment; 69221807Sstas unsigned int last; 70227239Sed void **array; 71221807Sstas isc_heapcompare_t compare; 72221807Sstas isc_heapindex_t index; 73221807Sstas}; 74221807Sstas 75221807Sstasisc_result_t 76221807Sstasisc_heap_create(isc_mem_t *mctx, isc_heapcompare_t compare, 77221807Sstas isc_heapindex_t index, unsigned int size_increment, 78221807Sstas isc_heap_t **heapp) 79221807Sstas{ 80221807Sstas isc_heap_t *heap; 81221807Sstas 82221807Sstas REQUIRE(heapp != NULL && *heapp == NULL); 83221807Sstas REQUIRE(compare != NULL); 84221807Sstas 85221807Sstas heap = isc_mem_get(mctx, sizeof(*heap)); 86221807Sstas if (heap == NULL) 87221807Sstas return (ISC_R_NOMEMORY); 88221807Sstas heap->magic = HEAP_MAGIC; 89221807Sstas heap->mctx = mctx; 90221807Sstas heap->size = 0; 91221807Sstas if (size_increment == 0) 92221807Sstas heap->size_increment = SIZE_INCREMENT; 93221807Sstas else 94221807Sstas heap->size_increment = size_increment; 95221807Sstas heap->last = 0; 96221807Sstas heap->array = NULL; 97221807Sstas heap->compare = compare; 98221807Sstas heap->index = index; 99221807Sstas 100221807Sstas *heapp = heap; 101221807Sstas 102221807Sstas return (ISC_R_SUCCESS); 103221807Sstas} 104221807Sstas 105221807Sstasvoid 106221807Sstasisc_heap_destroy(isc_heap_t **heapp) { 107221807Sstas isc_heap_t *heap; 108221807Sstas 109221807Sstas REQUIRE(heapp != NULL); 110221807Sstas heap = *heapp; 111221807Sstas REQUIRE(VALID_HEAP(heap)); 112221807Sstas 113221807Sstas if (heap->array != NULL) 114221807Sstas isc_mem_put(heap->mctx, heap->array, 115221807Sstas heap->size * sizeof(void *)); 116221807Sstas heap->magic = 0; 117221807Sstas isc_mem_put(heap->mctx, heap, sizeof(*heap)); 118221807Sstas 119221807Sstas *heapp = NULL; 120221807Sstas} 121221807Sstas 122221807Sstasstatic isc_boolean_t 123221807Sstasresize(isc_heap_t *heap) { 124221807Sstas void **new_array; 125221807Sstas size_t new_size; 126221807Sstas 127221807Sstas REQUIRE(VALID_HEAP(heap)); 128221807Sstas 129221807Sstas new_size = heap->size + heap->size_increment; 130221807Sstas new_array = isc_mem_get(heap->mctx, new_size * sizeof(void *)); 131221807Sstas if (new_array == NULL) 132221807Sstas return (ISC_FALSE); 133221807Sstas if (heap->array != NULL) { 134221807Sstas memcpy(new_array, heap->array, heap->size * sizeof(void *)); 135221807Sstas isc_mem_put(heap->mctx, heap->array, 136221807Sstas heap->size * sizeof(void *)); 137221807Sstas } 138221807Sstas heap->size = new_size; 139221807Sstas heap->array = new_array; 140221807Sstas 141221807Sstas return (ISC_TRUE); 142221807Sstas} 143221807Sstas 144221807Sstasstatic void 145221807Sstasfloat_up(isc_heap_t *heap, unsigned int i, void *elt) { 146221807Sstas unsigned int p; 147221807Sstas 148221807Sstas for (p = heap_parent(i) ; 149221807Sstas i > 1 && heap->compare(elt, heap->array[p]) ; 150221807Sstas i = p, p = heap_parent(i)) { 151221807Sstas heap->array[i] = heap->array[p]; 152221807Sstas if (heap->index != NULL) 153221807Sstas (heap->index)(heap->array[i], i); 154221807Sstas } 155221807Sstas heap->array[i] = elt; 156221807Sstas if (heap->index != NULL) 157221807Sstas (heap->index)(heap->array[i], i); 158221807Sstas 159221807Sstas INSIST(HEAPCONDITION(i)); 160221807Sstas} 161221807Sstas 162221807Sstasstatic void 163221807Sstassink_down(isc_heap_t *heap, unsigned int i, void *elt) { 164221807Sstas unsigned int j, size, half_size; 165221807Sstas size = heap->last; 166221807Sstas half_size = size / 2; 167221807Sstas while (i <= half_size) { 168221807Sstas /* Find the smallest of the (at most) two children. */ 169221807Sstas j = heap_left(i); 170221807Sstas if (j < size && heap->compare(heap->array[j+1], 171221807Sstas heap->array[j])) 172221807Sstas j++; 173221807Sstas if (heap->compare(elt, heap->array[j])) 174221807Sstas break; 175221807Sstas heap->array[i] = heap->array[j]; 176221807Sstas if (heap->index != NULL) 177221807Sstas (heap->index)(heap->array[i], i); 178221807Sstas i = j; 179221807Sstas } 180221807Sstas heap->array[i] = elt; 181221807Sstas if (heap->index != NULL) 182221807Sstas (heap->index)(heap->array[i], i); 183221807Sstas 184221807Sstas INSIST(HEAPCONDITION(i)); 185221807Sstas} 186221807Sstas 187221807Sstasisc_result_t 188221807Sstasisc_heap_insert(isc_heap_t *heap, void *elt) { 189221807Sstas unsigned int new_last; 190221807Sstas 191221807Sstas REQUIRE(VALID_HEAP(heap)); 192221807Sstas 193221807Sstas new_last = heap->last + 1; 194221807Sstas RUNTIME_CHECK(new_last > 0); /* overflow check */ 195221807Sstas if (new_last >= heap->size && !resize(heap)) 196221807Sstas return (ISC_R_NOMEMORY); 197221807Sstas heap->last = new_last; 198221807Sstas 199221807Sstas float_up(heap, new_last, elt); 200221807Sstas 201221807Sstas return (ISC_R_SUCCESS); 202221807Sstas} 203221807Sstas 204221807Sstasvoid 205221807Sstasisc_heap_delete(isc_heap_t *heap, unsigned int index) { 206221807Sstas void *elt; 207221807Sstas isc_boolean_t less; 208221807Sstas 209221807Sstas REQUIRE(VALID_HEAP(heap)); 210221807Sstas REQUIRE(index >= 1 && index <= heap->last); 211221807Sstas 212221807Sstas if (index == heap->last) { 213221807Sstas heap->array[heap->last] = NULL; 214221807Sstas heap->last--; 215221807Sstas } else { 216221807Sstas elt = heap->array[heap->last]; 217221807Sstas heap->array[heap->last] = NULL; 218221807Sstas heap->last--; 219221807Sstas 220221807Sstas less = heap->compare(elt, heap->array[index]); 221221807Sstas heap->array[index] = elt; 222221807Sstas if (less) 223221807Sstas float_up(heap, index, heap->array[index]); 224221807Sstas else 225221807Sstas sink_down(heap, index, heap->array[index]); 226221807Sstas } 227221807Sstas} 228221807Sstas 229221807Sstasvoid 230221807Sstasisc_heap_increased(isc_heap_t *heap, unsigned int index) { 231221807Sstas REQUIRE(VALID_HEAP(heap)); 232221807Sstas REQUIRE(index >= 1 && index <= heap->last); 233221807Sstas 234221807Sstas float_up(heap, index, heap->array[index]); 235221807Sstas} 236221807Sstas 237221807Sstasvoid 238221807Sstasisc_heap_decreased(isc_heap_t *heap, unsigned int index) { 239221807Sstas REQUIRE(VALID_HEAP(heap)); 240221807Sstas REQUIRE(index >= 1 && index <= heap->last); 241221807Sstas 242221807Sstas sink_down(heap, index, heap->array[index]); 243221807Sstas} 244221807Sstas 245221807Sstasvoid * 246221807Sstasisc_heap_element(isc_heap_t *heap, unsigned int index) { 247221807Sstas REQUIRE(VALID_HEAP(heap)); 248221807Sstas REQUIRE(index >= 1); 249221807Sstas 250221807Sstas if (index <= heap->last) 251221807Sstas return (heap->array[index]); 252221807Sstas return (NULL); 253221807Sstas} 254221807Sstas 255221807Sstasvoid 256221807Sstasisc_heap_foreach(isc_heap_t *heap, isc_heapaction_t action, void *uap) { 257221807Sstas unsigned int i; 258221807Sstas 259221807Sstas REQUIRE(VALID_HEAP(heap)); 260221807Sstas REQUIRE(action != NULL); 261221807Sstas 262221807Sstas for (i = 1 ; i <= heap->last ; i++) 263221807Sstas (action)(heap->array[i], uap); 264221807Sstas} 265221807Sstas