1 /* $NetBSD: heap.h,v 1.1.1.3 2014/07/12 11:57:56 spz Exp $ */ 2 /* 3 * Copyright (C) 2004-2007 Internet Systems Consortium, Inc. ("ISC") 4 * Copyright (C) 1997-2001 Internet Software Consortium. 5 * 6 * Permission to use, copy, modify, and distribute this software for any 7 * purpose with or without fee is hereby granted, provided that the above 8 * copyright notice and this permission notice appear in all copies. 9 * 10 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH 11 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 12 * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, 13 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 14 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 15 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 16 * PERFORMANCE OF THIS SOFTWARE. 17 */ 18 19 /* Id: heap.h,v 1.3 2007/05/19 19:16:25 dhankins Exp */ 20 21 #ifndef ISC_HEAP_H 22 #define ISC_HEAP_H 1 23 24 /*! \file isc/heap.h */ 25 26 /*% 27 * The comparision function returns ISC_TRUE if the first argument has 28 * higher priority than the second argument, and ISC_FALSE otherwise. 29 */ 30 typedef isc_boolean_t (*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 * Requires: 60 *\li "mctx" is valid. 61 *\li "compare" is a function which takes two void * arguments and 62 * returns ISC_TRUE if the first argument has a higher priority than 63 * the second, and ISC_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 #endif /* ISC_HEAP_H */ 165