1 /* 2 * Copyright (C) Internet Systems Consortium, Inc. ("ISC") 3 * 4 * This Source Code Form is subject to the terms of the Mozilla Public 5 * License, v. 2.0. If a copy of the MPL was not distributed with this 6 * file, You can obtain one at http://mozilla.org/MPL/2.0/. 7 * 8 * See the COPYRIGHT file distributed with this work for additional 9 * information regarding copyright ownership. 10 */ 11 12 #ifndef ISC_HEAP_H 13 #define ISC_HEAP_H 1 14 15 /*! \file isc/heap.h */ 16 17 #include <stdbool.h> 18 19 #include <isc/lang.h> 20 #include <isc/types.h> 21 22 ISC_LANG_BEGINDECLS 23 24 /*% 25 * The comparison function returns true if the first argument has 26 * higher priority than the second argument, and false otherwise. 27 */ 28 typedef bool (*isc_heapcompare_t)(void *, void *); 29 30 /*% 31 * The index function allows the client of the heap to receive a callback 32 * when an item's index number changes. This allows it to maintain 33 * sync with its external state, but still delete itself, since deletions 34 * from the heap require the index be provided. 35 */ 36 typedef void (*isc_heapindex_t)(void *, unsigned int); 37 38 /*% 39 * The heapaction function is used when iterating over the heap. 40 * 41 * NOTE: The heap structure CANNOT BE MODIFIED during the call to 42 * isc_heap_foreach(). 43 */ 44 typedef void (*isc_heapaction_t)(void *, void *); 45 46 typedef struct isc_heap isc_heap_t; 47 48 isc_result_t 49 isc_heap_create(isc_mem_t *mctx, isc_heapcompare_t compare, 50 isc_heapindex_t index, unsigned int size_increment, 51 isc_heap_t **heapp); 52 /*!< 53 * \brief Create a new heap. The heap is implemented using a space-efficient 54 * storage method. When the heap elements are deleted space is not freed 55 * but will be reused when new elements are inserted. 56 * 57 * Heap elements are indexed from 1. 58 * 59 * Requires: 60 *\li "mctx" is valid. 61 *\li "compare" is a function which takes two void * arguments and 62 * returns true if the first argument has a higher priority than 63 * the second, and false otherwise. 64 *\li "index" is a function which takes a void *, and an unsigned int 65 * argument. This function will be called whenever an element's 66 * index value changes, so it may continue to delete itself from the 67 * heap. This option may be NULL if this functionality is unneeded. 68 *\li "size_increment" is a hint about how large the heap should grow 69 * when resizing is needed. If this is 0, a default size will be 70 * used, which is currently 1024, allowing space for an additional 1024 71 * heap elements to be inserted before adding more space. 72 *\li "heapp" is not NULL, and "*heap" is NULL. 73 * 74 * Returns: 75 *\li ISC_R_SUCCESS - success 76 *\li ISC_R_NOMEMORY - insufficient memory 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 isc_result_t 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