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