1 /* $NetBSD: heap.h,v 1.1 2024/02/18 20:57:52 christos Exp $ */ 2 3 /* 4 * Copyright (C) Internet Systems Consortium, Inc. ("ISC") 5 * 6 * SPDX-License-Identifier: MPL-2.0 7 * 8 * This Source Code Form is subject to the terms of the Mozilla Public 9 * License, v. 2.0. If a copy of the MPL was not distributed with this 10 * file, you can obtain one at https://mozilla.org/MPL/2.0/. 11 * 12 * See the COPYRIGHT file distributed with this work for additional 13 * information regarding copyright ownership. 14 */ 15 16 #ifndef ISC_HEAP_H 17 #define ISC_HEAP_H 1 18 19 /*! \file isc/heap.h */ 20 21 #include <stdbool.h> 22 23 #include <isc/lang.h> 24 #include <isc/types.h> 25 26 ISC_LANG_BEGINDECLS 27 28 /*% 29 * The comparison function returns true if the first argument has 30 * higher priority than the second argument, and false otherwise. 31 */ 32 typedef bool (*isc_heapcompare_t)(void *, void *); 33 34 /*% 35 * The index function allows the client of the heap to receive a callback 36 * when an item's index number changes. This allows it to maintain 37 * sync with its external state, but still delete itself, since deletions 38 * from the heap require the index be provided. 39 */ 40 typedef void (*isc_heapindex_t)(void *, unsigned int); 41 42 /*% 43 * The heapaction function is used when iterating over the heap. 44 * 45 * NOTE: The heap structure CANNOT BE MODIFIED during the call to 46 * isc_heap_foreach(). 47 */ 48 typedef void (*isc_heapaction_t)(void *, void *); 49 50 typedef struct isc_heap isc_heap_t; 51 52 void 53 isc_heap_create(isc_mem_t *mctx, isc_heapcompare_t compare, 54 isc_heapindex_t index, unsigned int size_increment, 55 isc_heap_t **heapp); 56 /*!< 57 * \brief Create a new heap. The heap is implemented using a space-efficient 58 * storage method. When the heap elements are deleted space is not freed 59 * but will be reused when new elements are inserted. 60 * 61 * Heap elements are indexed from 1. 62 * 63 * Requires: 64 *\li "mctx" is valid. 65 *\li "compare" is a function which takes two void * arguments and 66 * returns true if the first argument has a higher priority than 67 * the second, and false otherwise. 68 *\li "index" is a function which takes a void *, and an unsigned int 69 * argument. This function will be called whenever an element's 70 * index value changes, so it may continue to delete itself from the 71 * heap. This option may be NULL if this functionality is unneeded. 72 *\li "size_increment" is a hint about how large the heap should grow 73 * when resizing is needed. If this is 0, a default size will be 74 * used, which is currently 1024, allowing space for an additional 1024 75 * heap elements to be inserted before adding more space. 76 *\li "heapp" is not NULL, and "*heap" is NULL. 77 */ 78 79 void 80 isc_heap_destroy(isc_heap_t **heapp); 81 /*!< 82 * \brief Destroys a heap. 83 * 84 * Requires: 85 *\li "heapp" is not NULL and "*heap" points to a valid isc_heap_t. 86 */ 87 88 void 89 isc_heap_insert(isc_heap_t *heap, void *elt); 90 /*!< 91 * \brief Inserts a new element into a heap. 92 * 93 * Requires: 94 *\li "heapp" is not NULL and "*heap" points to a valid isc_heap_t. 95 */ 96 97 void 98 isc_heap_delete(isc_heap_t *heap, unsigned int index); 99 /*!< 100 * \brief Deletes an element from a heap, by element index. 101 * 102 * Requires: 103 *\li "heapp" is not NULL and "*heap" points to a valid isc_heap_t. 104 *\li "index" is a valid element index, as provided by the "index" callback 105 * provided during heap creation. 106 */ 107 108 void 109 isc_heap_increased(isc_heap_t *heap, unsigned int index); 110 /*!< 111 * \brief Indicates to the heap that an element's priority has increased. 112 * This function MUST be called whenever an element has increased in priority. 113 * 114 * Requires: 115 *\li "heapp" is not NULL and "*heap" points to a valid isc_heap_t. 116 *\li "index" is a valid element index, as provided by the "index" callback 117 * provided during heap creation. 118 */ 119 120 void 121 isc_heap_decreased(isc_heap_t *heap, unsigned int index); 122 /*!< 123 * \brief Indicates to the heap that an element's priority has decreased. 124 * This function MUST be called whenever an element has decreased in priority. 125 * 126 * Requires: 127 *\li "heapp" is not NULL and "*heap" points to a valid isc_heap_t. 128 *\li "index" is a valid element index, as provided by the "index" callback 129 * provided during heap creation. 130 */ 131 132 void * 133 isc_heap_element(isc_heap_t *heap, unsigned int index); 134 /*!< 135 * \brief Returns the element for a specific element index. 136 * 137 * Requires: 138 *\li "heapp" is not NULL and "*heap" points to a valid isc_heap_t. 139 *\li "index" is a valid element index, as provided by the "index" callback 140 * provided during heap creation. 141 * 142 * Returns: 143 *\li A pointer to the element for the element index. 144 */ 145 146 void 147 isc_heap_foreach(isc_heap_t *heap, isc_heapaction_t action, void *uap); 148 /*!< 149 * \brief Iterate over the heap, calling an action for each element. The 150 * order of iteration is not sorted. 151 * 152 * Requires: 153 *\li "heapp" is not NULL and "*heap" points to a valid isc_heap_t. 154 *\li "action" is not NULL, and is a function which takes two arguments. 155 * The first is a void *, representing the element, and the second is 156 * "uap" as provided to isc_heap_foreach. 157 *\li "uap" is a caller-provided argument, and may be NULL. 158 * 159 * Note: 160 *\li The heap structure CANNOT be modified during this iteration. The only 161 * safe function to call while iterating the heap is isc_heap_element(). 162 */ 163 164 ISC_LANG_ENDDECLS 165 166 #endif /* ISC_HEAP_H */ 167