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