1 /* 2 * Copyright (C) Internet Systems Consortium, Inc. ("ISC") 3 * 4 * Permission to use, copy, modify, and/or distribute this software for any 5 * purpose with or without fee is hereby granted, provided that the above 6 * copyright notice and this permission notice appear in all copies. 7 * 8 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH 9 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 10 * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, 11 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 12 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 13 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 14 * PERFORMANCE OF THIS SOFTWARE. 15 */ 16 17 /* $Id: heap.h,v 1.4 2020/09/14 08:40:44 florian Exp $ */ 18 19 #ifndef ISC_HEAP_H 20 #define ISC_HEAP_H 1 21 22 /*! \file isc/heap.h */ 23 24 #include <isc/types.h> 25 26 /*% 27 * The comparison function returns 1 if the first argument has 28 * higher priority than the second argument, and 0 otherwise. 29 */ 30 typedef int (*isc_heapcompare_t)(void *, void *); 31 32 /*% 33 * The index function allows the client of the heap to receive a callback 34 * when an item's index number changes. This allows it to maintain 35 * sync with its external state, but still delete itself, since deletions 36 * from the heap require the index be provided. 37 */ 38 typedef void (*isc_heapindex_t)(void *, unsigned int); 39 40 /*% 41 * The heapaction function is used when iterating over the heap. 42 * 43 * NOTE: The heap structure CANNOT BE MODIFIED during the call to 44 * isc_heap_foreach(). 45 */ 46 typedef void (*isc_heapaction_t)(void *, void *); 47 48 typedef struct isc_heap isc_heap_t; 49 50 isc_result_t 51 isc_heap_create(isc_heapcompare_t compare, 52 isc_heapindex_t index, unsigned int size_increment, 53 isc_heap_t **heapp); 54 /*!< 55 * \brief Create a new heap. The heap is implemented using a space-efficient 56 * storage method. When the heap elements are deleted space is not freed 57 * but will be reused when new elements are inserted. 58 * 59 * Heap elements are indexed from 1. 60 * 61 * Requires: 62 *\li "mctx" is valid. 63 *\li "compare" is a function which takes two void * arguments and 64 * returns 1 if the first argument has a higher priority than 65 * the second, and 0 otherwise. 66 *\li "index" is a function which takes a void *, and an unsigned int 67 * argument. This function will be called whenever an element's 68 * index value changes, so it may continue to delete itself from the 69 * heap. This option may be NULL if this functionality is unneeded. 70 *\li "size_increment" is a hint about how large the heap should grow 71 * when resizing is needed. If this is 0, a default size will be 72 * used, which is currently 1024, allowing space for an additional 1024 73 * heap elements to be inserted before adding more space. 74 *\li "heapp" is not NULL, and "*heap" is NULL. 75 * 76 * Returns: 77 *\li ISC_R_SUCCESS - success 78 *\li ISC_R_NOMEMORY - insufficient memory 79 */ 80 81 void 82 isc_heap_destroy(isc_heap_t **heapp); 83 /*!< 84 * \brief Destroys a heap. 85 * 86 * Requires: 87 *\li "heapp" is not NULL and "*heap" points to a valid isc_heap_t. 88 */ 89 90 isc_result_t 91 isc_heap_insert(isc_heap_t *heap, void *elt); 92 /*!< 93 * \brief Inserts a new element into a heap. 94 * 95 * Requires: 96 *\li "heapp" is not NULL and "*heap" points to a valid isc_heap_t. 97 */ 98 99 void 100 isc_heap_delete(isc_heap_t *heap, unsigned int index); 101 /*!< 102 * \brief Deletes an element from a heap, by element index. 103 * 104 * Requires: 105 *\li "heapp" is not NULL and "*heap" points to a valid isc_heap_t. 106 *\li "index" is a valid element index, as provided by the "index" callback 107 * provided during heap creation. 108 */ 109 110 void 111 isc_heap_increased(isc_heap_t *heap, unsigned int index); 112 /*!< 113 * \brief Indicates to the heap that an element's priority has increased. 114 * This function MUST be called whenever an element has increased in priority. 115 * 116 * Requires: 117 *\li "heapp" is not NULL and "*heap" points to a valid isc_heap_t. 118 *\li "index" is a valid element index, as provided by the "index" callback 119 * provided during heap creation. 120 */ 121 122 void 123 isc_heap_decreased(isc_heap_t *heap, unsigned int index); 124 /*!< 125 * \brief Indicates to the heap that an element's priority has decreased. 126 * This function MUST be called whenever an element has decreased in priority. 127 * 128 * Requires: 129 *\li "heapp" is not NULL and "*heap" points to a valid isc_heap_t. 130 *\li "index" is a valid element index, as provided by the "index" callback 131 * provided during heap creation. 132 */ 133 134 void * 135 isc_heap_element(isc_heap_t *heap, unsigned int index); 136 /*!< 137 * \brief Returns the element for a specific element index. 138 * 139 * Requires: 140 *\li "heapp" is not NULL and "*heap" points to a valid isc_heap_t. 141 *\li "index" is a valid element index, as provided by the "index" callback 142 * provided during heap creation. 143 * 144 * Returns: 145 *\li A pointer to the element for the element index. 146 */ 147 148 #endif /* ISC_HEAP_H */ 149