heap.c revision af669cb4fd7ecfb67ed145b176e5e764b249573b
499b34cea04a46823d003d4c0520c8b03e8513cbBrian Wellington * Copyright (C) 2004-2007, 2010-2014 Internet Systems Consortium, Inc. ("ISC")
40f53fa8d9c6a4fc38c0014495e7a42b08f52481David Lawrence * Copyright (C) 1997-2001 Internet Software Consortium.
9178881e1bf6a4b01db886b355406c8bed61cc2aMichael Graff * Permission to use, copy, modify, and/or distribute this software for any
9178881e1bf6a4b01db886b355406c8bed61cc2aMichael Graff * purpose with or without fee is hereby granted, provided that the above
40f53fa8d9c6a4fc38c0014495e7a42b08f52481David Lawrence * copyright notice and this permission notice appear in all copies.
15a44745412679c30a6d022733925af70a38b715David Lawrence * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
15a44745412679c30a6d022733925af70a38b715David Lawrence * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
15a44745412679c30a6d022733925af70a38b715David Lawrence * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
15a44745412679c30a6d022733925af70a38b715David Lawrence * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
15a44745412679c30a6d022733925af70a38b715David Lawrence * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
15a44745412679c30a6d022733925af70a38b715David Lawrence * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
15a44745412679c30a6d022733925af70a38b715David Lawrence * PERFORMANCE OF THIS SOFTWARE.
9178881e1bf6a4b01db886b355406c8bed61cc2aMichael Graff * Heap implementation of priority queues adapted from the following:
9178881e1bf6a4b01db886b355406c8bed61cc2aMichael Graff * \li "Introduction to Algorithms," Cormen, Leiserson, and Rivest,
9178881e1bf6a4b01db886b355406c8bed61cc2aMichael Graff * MIT Press / McGraw Hill, 1990, ISBN 0-262-03141-8, chapter 7.
1a69a1a78cfaa86f3b68bbc965232b7876d4da2aDavid Lawrence * \li "Algorithms," Second Edition, Sedgewick, Addison-Wesley, 1988,
6028d1ce0380d0ba7f6c6ecd1ad20b31ddd1becbDavid Lawrence * ISBN 0-201-06673-4, chapter 11.
294ae26fb3e1376b4c34c6b8d15737e39cc2cb48Andreas Gustafsson#include <isc/string.h> /* Required for memmove. */
09f22ac5b09e70bc526015f37168ba33e21ea91fDavid Lawrence * Note: to make heap_parent and heap_left easy to compute, the first
0f80bfec687db08a6e6ce945ef1d818da06c7ca9Brian Wellington * element of the heap array is not used; i.e. heap subscripts are 1-based,
09f22ac5b09e70bc526015f37168ba33e21ea91fDavid Lawrence * not 0-based. The parent is index/2, and the left-child is index*2.
6d4886fa7430889a96dbf9b88a2a4eb6f9d04674Brian Wellington * The right child is index*2+1.
ac77fece9a62537a9e0e5852498ebeda7b2978c3Bob Halley#define VALID_HEAP(h) ISC_MAGIC_VALID(h, HEAP_MAGIC)
f9df80f4348ef68043903efa08299480324f4823Michael Graff * When the heap is in a consistent state, the following invariant
f9df80f4348ef68043903efa08299480324f4823Michael Graff * holds true: for every element i > 1, heap_parent(i) has a priority
f9df80f4348ef68043903efa08299480324f4823Michael Graff * higher than or equal to that of i.
1ed4ba5a1fcb6aecd1c92fdcc75c6b4bbb7cc60fMichael Sawyer/*% ISC heap structure. */
f9df80f4348ef68043903efa08299480324f4823Michael Graff unsigned int magic;
f9df80f4348ef68043903efa08299480324f4823Michael Graff unsigned int size;
97e7d389d54a9e3a1ba8313ed140b04afabc7081Michael Graff unsigned int last;
f9df80f4348ef68043903efa08299480324f4823Michael Graffisc_heap_create(isc_mem_t *mctx, isc_heapcompare_t compare,
c95a89b433e42ecf9108b6c263f405fecc0d8a65Michael Sawyer isc_heapindex_t idx, unsigned int size_increment,
c95a89b433e42ecf9108b6c263f405fecc0d8a65Michael Sawyer isc_mem_putanddetach(&heap->mctx, heap, sizeof(*heap));
c95a89b433e42ecf9108b6c263f405fecc0d8a65Michael Sawyer new_size = heap->size + heap->size_increment;
c95a89b433e42ecf9108b6c263f405fecc0d8a65Michael Sawyer new_array = isc_mem_get(heap->mctx, new_size * sizeof(void *));
f9df80f4348ef68043903efa08299480324f4823Michael Graff memmove(new_array, heap->array, heap->size * sizeof(void *));
97e7d389d54a9e3a1ba8313ed140b04afabc7081Michael Grafffloat_up(isc_heap_t *heap, unsigned int i, void *elt) {
97e7d389d54a9e3a1ba8313ed140b04afabc7081Michael Graff unsigned int p;
9178881e1bf6a4b01db886b355406c8bed61cc2aMichael Graff i = p, p = heap_parent(i)) {
9178881e1bf6a4b01db886b355406c8bed61cc2aMichael Graffsink_down(isc_heap_t *heap, unsigned int i, void *elt) {
9178881e1bf6a4b01db886b355406c8bed61cc2aMichael Graff while (i <= half_size) {
9178881e1bf6a4b01db886b355406c8bed61cc2aMichael Graff /* Find the smallest of the (at most) two children. */
9178881e1bf6a4b01db886b355406c8bed61cc2aMichael Graff if (j < size && heap->compare(heap->array[j+1],
9178881e1bf6a4b01db886b355406c8bed61cc2aMichael Graff RUNTIME_CHECK(new_last > 0); /* overflow check */
f9df80f4348ef68043903efa08299480324f4823Michael Graffisc_heap_delete(isc_heap_t *heap, unsigned int idx) {
d68838693666ba930ec4143f848c18bff2bfc244Michael Graffisc_heap_increased(isc_heap_t *heap, unsigned int idx) {
d68838693666ba930ec4143f848c18bff2bfc244Michael Graffisc_heap_decreased(isc_heap_t *heap, unsigned int idx) {
d68838693666ba930ec4143f848c18bff2bfc244Michael Graffisc_heap_element(isc_heap_t *heap, unsigned int idx) {
d68838693666ba930ec4143f848c18bff2bfc244Michael Graffisc_heap_foreach(isc_heap_t *heap, isc_heapaction_t action, void *uap) {
d68838693666ba930ec4143f848c18bff2bfc244Michael Graff unsigned int i;