lib/isc/heap.c

	heap.c revision 89085bebd38357d7953f3217a220a57c1c9fcff7
1633838b8255282d10af15c5c84cee5a51466712Bob Halley/*
69fe9aaafdd6a141610e86a777d325db75422070Mark Andrews * Copyright (C) 1997-2001, 2004-2007, 2010-2016  Internet Systems Consortium, Inc. ("ISC")
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews *
40f53fa8d9c6a4fc38c0014495e7a42b08f52481David Lawrence * This Source Code Form is subject to the terms of the Mozilla Public
1633838b8255282d10af15c5c84cee5a51466712Bob Halley * License, v. 2.0. If a copy of the MPL was not distributed with this
1633838b8255282d10af15c5c84cee5a51466712Bob Halley * file, You can obtain one at http://mozilla.org/MPL/2.0/.
1633838b8255282d10af15c5c84cee5a51466712Bob Halley */
40f53fa8d9c6a4fc38c0014495e7a42b08f52481David Lawrence
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews/* $Id$ */
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews/*! \file
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * Heap implementation of priority queues adapted from the following:
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews *
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews *  \li "Introduction to Algorithms," Cormen, Leiserson, and Rivest,
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews *  MIT Press / McGraw Hill, 1990, ISBN 0-262-03141-8, chapter 7.
1633838b8255282d10af15c5c84cee5a51466712Bob Halley *
c50fd34a4e0e6978f8ca5f6f3ad8545549c3cfeeBob Halley *  \li "Algorithms," Second Edition, Sedgewick, Addison-Wesley, 1988,
c5223c9cb7c22620d5ee6611228673e95b48a270Mark Andrews *  ISBN 0-201-06673-4, chapter 11.
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein */
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein
9c3531d72aeaad6c5f01efe6a1c82023e1379e4dDavid Lawrence#include <config.h>
d25afd60ee2286cb171c4960a790f3d7041b6f85Bob Halley
d25afd60ee2286cb171c4960a790f3d7041b6f85Bob Halley#include <isc/heap.h>
e4e071ae12aee942fefc2c0a3280e402938669deBob Halley#include <isc/magic.h>
364a82f7c25b62967678027043425201a5e5171aBob Halley#include <isc/mem.h>
96754ed7b400ce080279de2f92111ad868105290Bob Halley#include <isc/string.h>     /* Required for memmove. */
c50fd34a4e0e6978f8ca5f6f3ad8545549c3cfeeBob Halley#include <isc/util.h>
96754ed7b400ce080279de2f92111ad868105290Bob Halley
c50fd34a4e0e6978f8ca5f6f3ad8545549c3cfeeBob Halley/*@{*/
6d12fdf96621801e80f3f4c2a8a569fe48766a20David Lawrence/*%
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein * Note: to make heap_parent and heap_left easy to compute, the first
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein * element of the heap array is not used; i.e. heap subscripts are 1-based,
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein * not 0-based.  The parent is index/2, and the left-child is index*2.
b6309ed962c4988a314d61742c4fbc4935467d68Mark Andrews * The right child is index*2+1.
b6309ed962c4988a314d61742c4fbc4935467d68Mark Andrews */
b6309ed962c4988a314d61742c4fbc4935467d68Mark Andrews#define heap_parent(i)          ((i) >> 1)
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein#define heap_left(i)            ((i) << 1)
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein/*@}*/
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein#define SIZE_INCREMENT          1024
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein#define HEAP_MAGIC          ISC_MAGIC('H', 'E', 'A', 'P')
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein#define VALID_HEAP(h)           ISC_MAGIC_VALID(h, HEAP_MAGIC)
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein/*%
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein * When the heap is in a consistent state, the following invariant
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein * holds true: for every element i > 1, heap_parent(i) has a priority
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein * higher than or equal to that of i.
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein */
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein#define HEAPCONDITION(i) ((i) == 1 || \
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein              ! heap->compare(heap->array[(i)], \
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein                      heap->array[heap_parent(i)]))
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein/*% ISC heap structure. */
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austeinstruct isc_heap {
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    unsigned int            magic;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    isc_mem_t *         mctx;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    unsigned int            size;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    unsigned int            size_increment;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    unsigned int            last;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    void                **array;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    isc_heapcompare_t       compare;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    isc_heapindex_t         index;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein};
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein#ifdef ISC_HEAP_CHECK
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austeinstatic void
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austeinheap_check(isc_heap_t *heap) {
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    unsigned int i;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    for (i = 1; i <= heap->last; i++) {
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein        INSIST(HEAPCONDITION(i));
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    }
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein}
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein#else
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein#define heap_check(x) (void)0
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein#endif
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austeinisc_result_t
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austeinisc_heap_create(isc_mem_t *mctx, isc_heapcompare_t compare,
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein        isc_heapindex_t idx, unsigned int size_increment,
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein        isc_heap_t **heapp)
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein{
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    isc_heap_t *heap;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    REQUIRE(heapp != NULL && *heapp == NULL);
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    REQUIRE(compare != NULL);
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    heap = isc_mem_get(mctx, sizeof(*heap));
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    if (heap == NULL)
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein        return (ISC_R_NOMEMORY);
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    heap->magic = HEAP_MAGIC;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    heap->size = 0;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    heap->mctx = NULL;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    isc_mem_attach(mctx, &heap->mctx);
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    if (size_increment == 0)
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein        heap->size_increment = SIZE_INCREMENT;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    else
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein        heap->size_increment = size_increment;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    heap->last = 0;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    heap->array = NULL;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    heap->compare = compare;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    heap->index = idx;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    *heapp = heap;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    return (ISC_R_SUCCESS);
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein}
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austeinvoid
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austeinisc_heap_destroy(isc_heap_t **heapp) {
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    isc_heap_t *heap;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    REQUIRE(heapp != NULL);
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    heap = *heapp;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    REQUIRE(VALID_HEAP(heap));
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    if (heap->array != NULL)
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein        isc_mem_put(heap->mctx, heap->array,
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein                heap->size * sizeof(void *));
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    heap->magic = 0;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    isc_mem_putanddetach(&heap->mctx, heap, sizeof(*heap));
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    *heapp = NULL;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein}
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austeinstatic isc_boolean_t
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austeinresize(isc_heap_t *heap) {
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    void **new_array;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    unsigned int new_size;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    REQUIRE(VALID_HEAP(heap));
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    new_size = heap->size + heap->size_increment;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    new_array = isc_mem_get(heap->mctx, new_size * sizeof(void *));
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    if (new_array == NULL)
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein        return (ISC_FALSE);
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    if (heap->array != NULL) {
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein        memmove(new_array, heap->array, heap->size * sizeof(void *));
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein        isc_mem_put(heap->mctx, heap->array,
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein                heap->size * sizeof(void *));
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    }
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    heap->size = new_size;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    heap->array = new_array;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    return (ISC_TRUE);
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein}
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austeinstatic void
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austeinfloat_up(isc_heap_t *heap, unsigned int i, void *elt) {
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    unsigned int p;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    for (p = heap_parent(i) ;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein         i > 1 && heap->compare(elt, heap->array[p]) ;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein         i = p, p = heap_parent(i)) {
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein        heap->array[i] = heap->array[p];
c5223c9cb7c22620d5ee6611228673e95b48a270Mark Andrews        if (heap->index != NULL)
c5223c9cb7c22620d5ee6611228673e95b48a270Mark Andrews            (heap->index)(heap->array[i], i);
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halley    }
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halley    heap->array[i] = elt;
6d12fdf96621801e80f3f4c2a8a569fe48766a20David Lawrence    if (heap->index != NULL)
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein        (heap->index)(heap->array[i], i);
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    INSIST(HEAPCONDITION(i));
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    heap_check(heap);
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein}
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austeinstatic void
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austeinsink_down(isc_heap_t *heap, unsigned int i, void *elt) {
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    unsigned int j, size, half_size;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    size = heap->last;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    half_size = size / 2;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein    while (i <= half_size) {
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein        /* Find the smallest of the (at most) two children. */
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein        j = heap_left(i);
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein        if (j < size && heap->compare(heap->array[j+1],
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein                          heap->array[j]))
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein            j++;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein        if (heap->compare(elt, heap->array[j]))
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein            break;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein        heap->array[i] = heap->array[j];
c50fd34a4e0e6978f8ca5f6f3ad8545549c3cfeeBob Halley        if (heap->index != NULL)
c50fd34a4e0e6978f8ca5f6f3ad8545549c3cfeeBob Halley            (heap->index)(heap->array[i], i);
138a6660fb74d458270511ca0ba24aa19bf375d5Bob Halley        i = j;
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halley    }
138a6660fb74d458270511ca0ba24aa19bf375d5Bob Halley    heap->array[i] = elt;
d8dcd6ad4617cc8d7df979bd62101fa9c4bac1bcBob Halley    if (heap->index != NULL)
e4e071ae12aee942fefc2c0a3280e402938669deBob Halley        (heap->index)(heap->array[i], i);
e4e071ae12aee942fefc2c0a3280e402938669deBob Halley
e4e071ae12aee942fefc2c0a3280e402938669deBob Halley    INSIST(HEAPCONDITION(i));
e4e071ae12aee942fefc2c0a3280e402938669deBob Halley    heap_check(heap);
e4e071ae12aee942fefc2c0a3280e402938669deBob Halley}
e4e071ae12aee942fefc2c0a3280e402938669deBob Halley
138a6660fb74d458270511ca0ba24aa19bf375d5Bob Halleyisc_result_t
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halleyisc_heap_insert(isc_heap_t *heap, void *elt) {
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halley    unsigned int new_last;
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halley
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halley    REQUIRE(VALID_HEAP(heap));
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halley
e4e071ae12aee942fefc2c0a3280e402938669deBob Halley    heap_check(heap);
e4e071ae12aee942fefc2c0a3280e402938669deBob Halley    new_last = heap->last + 1;
e4e071ae12aee942fefc2c0a3280e402938669deBob Halley    RUNTIME_CHECK(new_last > 0); /* overflow check */
e4e071ae12aee942fefc2c0a3280e402938669deBob Halley    if (new_last >= heap->size && !resize(heap))
e4e071ae12aee942fefc2c0a3280e402938669deBob Halley        return (ISC_R_NOMEMORY);
e4e071ae12aee942fefc2c0a3280e402938669deBob Halley    heap->last = new_last;
e4e071ae12aee942fefc2c0a3280e402938669deBob Halley
96754ed7b400ce080279de2f92111ad868105290Bob Halley    float_up(heap, new_last, elt);
e4e071ae12aee942fefc2c0a3280e402938669deBob Halley
e4e071ae12aee942fefc2c0a3280e402938669deBob Halley    return (ISC_R_SUCCESS);
e4e071ae12aee942fefc2c0a3280e402938669deBob Halley}
6d12fdf96621801e80f3f4c2a8a569fe48766a20David Lawrence
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halleyvoid
e4e071ae12aee942fefc2c0a3280e402938669deBob Halleyisc_heap_delete(isc_heap_t *heap, unsigned int idx) {
e4e071ae12aee942fefc2c0a3280e402938669deBob Halley    void *elt;
e4e071ae12aee942fefc2c0a3280e402938669deBob Halley    isc_boolean_t less;
e4e071ae12aee942fefc2c0a3280e402938669deBob Halley
e4e071ae12aee942fefc2c0a3280e402938669deBob Halley    REQUIRE(VALID_HEAP(heap));
e4e071ae12aee942fefc2c0a3280e402938669deBob Halley    REQUIRE(idx >= 1 && idx <= heap->last);
e4e071ae12aee942fefc2c0a3280e402938669deBob Halley
e4e071ae12aee942fefc2c0a3280e402938669deBob Halley    heap_check(heap);
c50fd34a4e0e6978f8ca5f6f3ad8545549c3cfeeBob Halley    if (idx == heap->last) {
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halley        heap->array[heap->last] = NULL;
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halley        heap->last--;
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halley        heap_check(heap);
711b0bed7b7f9e505c81e5810224f01df80a2ee4Bob Halley    } else {
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halley        elt = heap->array[heap->last];
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halley        heap->array[heap->last] = NULL;
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halley        heap->last--;
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halley
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halley        less = heap->compare(elt, heap->array[idx]);
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halley        heap->array[idx] = elt;
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halley        if (less)
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halley            float_up(heap, idx, heap->array[idx]);
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halley        else
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halley            sink_down(heap, idx, heap->array[idx]);
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halley    }
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halley}
542189f21b3ea9b27b0fbc047d832a34dcaf75bcAndreas Gustafsson
fa756a197b059b28c44f24e332bd072178861dc6Mark Andrewsvoid
542189f21b3ea9b27b0fbc047d832a34dcaf75bcAndreas Gustafssonisc_heap_increased(isc_heap_t *heap, unsigned int idx) {
34b394b43e2207e8f8f3703f0402422121455638David Lawrence    REQUIRE(VALID_HEAP(heap));
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halley    REQUIRE(idx >= 1 && idx <= heap->last);
34b394b43e2207e8f8f3703f0402422121455638David Lawrence
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halley    float_up(heap, idx, heap->array[idx]);
34b394b43e2207e8f8f3703f0402422121455638David Lawrence}
b6309ed962c4988a314d61742c4fbc4935467d68Mark Andrews
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halleyvoid
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halleyisc_heap_decreased(isc_heap_t *heap, unsigned int idx) {
34b394b43e2207e8f8f3703f0402422121455638David Lawrence    REQUIRE(VALID_HEAP(heap));
34b394b43e2207e8f8f3703f0402422121455638David Lawrence    REQUIRE(idx >= 1 && idx <= heap->last);
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halley
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halley    sink_down(heap, idx, heap->array[idx]);
b6309ed962c4988a314d61742c4fbc4935467d68Mark Andrews}
34b394b43e2207e8f8f3703f0402422121455638David Lawrence
34b394b43e2207e8f8f3703f0402422121455638David Lawrencevoid *
34b394b43e2207e8f8f3703f0402422121455638David Lawrenceisc_heap_element(isc_heap_t *heap, unsigned int idx) {
34b394b43e2207e8f8f3703f0402422121455638David Lawrence    REQUIRE(VALID_HEAP(heap));
34b394b43e2207e8f8f3703f0402422121455638David Lawrence    REQUIRE(idx >= 1);
34b394b43e2207e8f8f3703f0402422121455638David Lawrence
04b8111f2137a9cf9b0b71228f76b3e40ffa1173Brian Wellington    heap_check(heap);
34b394b43e2207e8f8f3703f0402422121455638David Lawrence    if (idx <= heap->last)
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halley        return (heap->array[idx]);
147fd0bdf83272952521a7f343d88a421e2ff997Brian Wellington    return (NULL);
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halley}
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halley
147fd0bdf83272952521a7f343d88a421e2ff997Brian Wellingtonvoid
04b8111f2137a9cf9b0b71228f76b3e40ffa1173Brian Wellingtonisc_heap_foreach(isc_heap_t *heap, isc_heapaction_t action, void *uap) {
95b604c5e972a5e9eb713bf45cf0b2d9b98da27eMark Andrews    unsigned int i;
04b8111f2137a9cf9b0b71228f76b3e40ffa1173Brian Wellington
04b8111f2137a9cf9b0b71228f76b3e40ffa1173Brian Wellington    REQUIRE(VALID_HEAP(heap));
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halley    REQUIRE(action != NULL);
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halley
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halley    for (i = 1 ; i <= heap->last ; i++)
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halley        (action)(heap->array[i], uap);
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halley}
25e43e68b7431d5e4ff8b5427108cd7f5f9bcf3eBob Halley