1 /* $NetBSD: heap.h,v 1.2 2018/04/07 22:37:29 christos Exp $ */ 2 3 /* 4 * Copyright (C) 2004-2017 Internet Systems Consortium, Inc. ("ISC") 5 * Copyright (C) 1997-2003 Internet Software Consortium. 6 * 7 * This Source Code Form is subject to the terms of the Mozilla Public 8 * License, v. 2.0. If a copy of the MPL was not distributed with this 9 * file, You can obtain one at http://mozilla.org/MPL/2.0/. 10 * 11 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH 12 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 13 * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, 14 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 15 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 16 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 17 * PERFORMANCE OF THIS SOFTWARE. 18 */ 19 20 /* Id: heap.h,v 1.3 2007/05/19 19:16:25 dhankins Exp */ 21 22 #ifndef ISC_HEAP_H 23 #define ISC_HEAP_H 1 24 25 /*! \file isc/heap.h */ 26 27 /*% 28 * The comparision function returns ISC_TRUE if the first argument has 29 * higher priority than the second argument, and ISC_FALSE otherwise. 30 */ 31 typedef isc_boolean_t (*isc_heapcompare_t)(void *, void *); 32 33 /*% 34 * The index function allows the client of the heap to receive a callback 35 * when an item's index number changes. This allows it to maintain 36 * sync with its external state, but still delete itself, since deletions 37 * from the heap require the index be provided. 38 */ 39 typedef void (*isc_heapindex_t)(void *, unsigned int); 40 41 /*% 42 * The heapaction function is used when iterating over the heap. 43 * 44 * NOTE: The heap structure CANNOT BE MODIFIED during the call to 45 * isc_heap_foreach(). 46 */ 47 typedef void (*isc_heapaction_t)(void *, void *); 48 49 typedef struct isc_heap isc_heap_t; 50 51 isc_result_t 52 isc_heap_create(isc_heapcompare_t compare, 53 isc_heapindex_t index, unsigned int size_increment, 54 isc_heap_t **heapp); 55 /*!< 56 * \brief Create a new heap. The heap is implemented using a space-efficient 57 * storage method. When the heap elements are deleted space is not freed 58 * but will be reused when new elements are inserted. 59 * 60 * Requires: 61 *\li "mctx" is valid. 62 *\li "compare" is a function which takes two void * arguments and 63 * returns ISC_TRUE if the first argument has a higher priority than 64 * the second, and ISC_FALSE otherwise. 65 *\li "index" is a function which takes a void *, and an unsigned int 66 * argument. This function will be called whenever an element's 67 * index value changes, so it may continue to delete itself from the 68 * heap. This option may be NULL if this functionality is unneeded. 69 *\li "size_increment" is a hint about how large the heap should grow 70 * when resizing is needed. If this is 0, a default size will be 71 * used, which is currently 1024, allowing space for an additional 1024 72 * heap elements to be inserted before adding more space. 73 *\li "heapp" is not NULL, and "*heap" is NULL. 74 * 75 * Returns: 76 *\li ISC_R_SUCCESS - success 77 *\li ISC_R_NOMEMORY - insufficient memory 78 */ 79 80 void 81 isc_heap_destroy(isc_heap_t **heapp); 82 /*!< 83 * \brief Destroys a heap. 84 * 85 * Requires: 86 *\li "heapp" is not NULL and "*heap" points to a valid isc_heap_t. 87 */ 88 89 isc_result_t 90 isc_heap_insert(isc_heap_t *heap, void *elt); 91 /*!< 92 * \brief Inserts a new element into a heap. 93 * 94 * Requires: 95 *\li "heapp" is not NULL and "*heap" points to a valid isc_heap_t. 96 */ 97 98 void 99 isc_heap_delete(isc_heap_t *heap, unsigned int index); 100 /*!< 101 * \brief Deletes an element from a heap, by element index. 102 * 103 * Requires: 104 *\li "heapp" is not NULL and "*heap" points to a valid isc_heap_t. 105 *\li "index" is a valid element index, as provided by the "index" callback 106 * provided during heap creation. 107 */ 108 109 void 110 isc_heap_increased(isc_heap_t *heap, unsigned int index); 111 /*!< 112 * \brief Indicates to the heap that an element's priority has increased. 113 * This function MUST be called whenever an element has increased in priority. 114 * 115 * Requires: 116 *\li "heapp" is not NULL and "*heap" points to a valid isc_heap_t. 117 *\li "index" is a valid element index, as provided by the "index" callback 118 * provided during heap creation. 119 */ 120 121 void 122 isc_heap_decreased(isc_heap_t *heap, unsigned int index); 123 /*!< 124 * \brief Indicates to the heap that an element's priority has decreased. 125 * This function MUST be called whenever an element has decreased in priority. 126 * 127 * Requires: 128 *\li "heapp" is not NULL and "*heap" points to a valid isc_heap_t. 129 *\li "index" is a valid element index, as provided by the "index" callback 130 * provided during heap creation. 131 */ 132 133 void * 134 isc_heap_element(isc_heap_t *heap, unsigned int index); 135 /*!< 136 * \brief Returns the element for a specific element index. 137 * 138 * Requires: 139 *\li "heapp" is not NULL and "*heap" points to a valid isc_heap_t. 140 *\li "index" is a valid element index, as provided by the "index" callback 141 * provided during heap creation. 142 * 143 * Returns: 144 *\li A pointer to the element for the element index. 145 */ 146 147 void 148 isc_heap_foreach(isc_heap_t *heap, isc_heapaction_t action, void *uap); 149 /*!< 150 * \brief Iterate over the heap, calling an action for each element. The 151 * order of iteration is not sorted. 152 * 153 * Requires: 154 *\li "heapp" is not NULL and "*heap" points to a valid isc_heap_t. 155 *\li "action" is not NULL, and is a function which takes two arguments. 156 * The first is a void *, representing the element, and the second is 157 * "uap" as provided to isc_heap_foreach. 158 *\li "uap" is a caller-provided argument, and may be NULL. 159 * 160 * Note: 161 *\li The heap structure CANNOT be modified during this iteration. The only 162 * safe function to call while iterating the heap is isc_heap_element(). 163 */ 164 165 #endif /* ISC_HEAP_H */ 166