diff options
Diffstat (limited to 'contrib/bind9/lib/isc/include/isc/heap.h')
| -rw-r--r-- | contrib/bind9/lib/isc/include/isc/heap.h | 143 |
1 files changed, 131 insertions, 12 deletions
diff --git a/contrib/bind9/lib/isc/include/isc/heap.h b/contrib/bind9/lib/isc/include/isc/heap.h index 5ebf404..7c7f3c2 100644 --- a/contrib/bind9/lib/isc/include/isc/heap.h +++ b/contrib/bind9/lib/isc/include/isc/heap.h @@ -1,5 +1,5 @@ /* - * Copyright (C) 2004 Internet Systems Consortium, Inc. ("ISC") + * Copyright (C) 2004-2006 Internet Systems Consortium, Inc. ("ISC") * Copyright (C) 1997-2001 Internet Software Consortium. * * Permission to use, copy, modify, and distribute this software for any @@ -15,36 +15,155 @@ * PERFORMANCE OF THIS SOFTWARE. */ -/* $Id: heap.h,v 1.16.206.1 2004/03/06 08:14:41 marka Exp $ */ +/* $Id: heap.h,v 1.16.206.2 2006/04/17 18:27:20 explorer Exp $ */ #ifndef ISC_HEAP_H #define ISC_HEAP_H 1 +/*! \file */ + #include <isc/lang.h> #include <isc/types.h> ISC_LANG_BEGINDECLS -/* +/*% * The comparision function returns ISC_TRUE if the first argument has * higher priority than the second argument, and ISC_FALSE otherwise. */ typedef isc_boolean_t (*isc_heapcompare_t)(void *, void *); +/*% + * The index function allows the client of the heap to receive a callback + * when an item's index number changes. This allows it to maintain + * sync with its external state, but still delete itself, since deletions + * from the heap require the index be provided. + */ typedef void (*isc_heapindex_t)(void *, unsigned int); + +/*% + * The heapaction function is used when iterating over the heap. + * + * NOTE: The heap structure CANNOT BE MODIFIED during the call to + * isc_heap_foreach(). + */ typedef void (*isc_heapaction_t)(void *, void *); typedef struct isc_heap isc_heap_t; -isc_result_t isc_heap_create(isc_mem_t *, isc_heapcompare_t, - isc_heapindex_t, unsigned int, isc_heap_t **); -void isc_heap_destroy(isc_heap_t **); -isc_result_t isc_heap_insert(isc_heap_t *, void *); -void isc_heap_delete(isc_heap_t *, unsigned int); -void isc_heap_increased(isc_heap_t *, unsigned int); -void isc_heap_decreased(isc_heap_t *, unsigned int); -void * isc_heap_element(isc_heap_t *, unsigned int); -void isc_heap_foreach(isc_heap_t *, isc_heapaction_t, void *); +isc_result_t +isc_heap_create(isc_mem_t *mctx, isc_heapcompare_t compare, + isc_heapindex_t index, unsigned int size_increment, + isc_heap_t **heapp); +/*!< + * \brief Create a new heap. The heap is implemented using a space-efficient + * storage method. When the heap elements are deleted space is not freed + * but will be reused when new elements are inserted. + * + * Requires: + *\li "mctx" is valid. + *\li "compare" is a function which takes two void * arguments and + * returns ISC_TRUE if the first argument has a higher priority than + * the second, and ISC_FALSE otherwise. + *\li "index" is a function which takes a void *, and an unsigned int + * argument. This function will be called whenever an element's + * index value changes, so it may continue to delete itself from the + * heap. This option may be NULL if this functionality is unneeded. + *\li "size_increment" is a hint about how large the heap should grow + * when resizing is needed. If this is 0, a default size will be + * used, which is currently 1024, allowing space for an additional 1024 + * heap elements to be inserted before adding more space. + *\li "heapp" is not NULL, and "*heap" is NULL. + * + * Returns: + *\li ISC_R_SUCCESS - success + *\li ISC_R_NOMEMORY - insufficient memory + */ + +void +isc_heap_destroy(isc_heap_t **heapp); +/*!< + * \brief Destroys a heap. + * + * Requires: + *\li "heapp" is not NULL and "*heap" points to a valid isc_heap_t. + */ + +isc_result_t +isc_heap_insert(isc_heap_t *heap, void *elt); +/*!< + * \brief Inserts a new element into a heap. + * + * Requires: + *\li "heapp" is not NULL and "*heap" points to a valid isc_heap_t. + */ + +void +isc_heap_delete(isc_heap_t *heap, unsigned int index); +/*!< + * \brief Deletes an element from a heap, by element index. + * + * Requires: + *\li "heapp" is not NULL and "*heap" points to a valid isc_heap_t. + *\li "index" is a valid element index, as provided by the "index" callback + * provided during heap creation. + */ + +void +isc_heap_increased(isc_heap_t *heap, unsigned int index); +/*!< + * \brief Indicates to the heap that an element's priority has increased. + * This function MUST be called whenever an element has increased in priority. + * + * Requires: + *\li "heapp" is not NULL and "*heap" points to a valid isc_heap_t. + *\li "index" is a valid element index, as provided by the "index" callback + * provided during heap creation. + */ + +void +isc_heap_decreased(isc_heap_t *heap, unsigned int index); +/*!< + * \brief Indicates to the heap that an element's priority has decreased. + * This function MUST be called whenever an element has decreased in priority. + * + * Requires: + *\li "heapp" is not NULL and "*heap" points to a valid isc_heap_t. + *\li "index" is a valid element index, as provided by the "index" callback + * provided during heap creation. + */ + +void * +isc_heap_element(isc_heap_t *heap, unsigned int index); +/*!< + * \brief Returns the element for a specific element index. + * + * Requires: + *\li "heapp" is not NULL and "*heap" points to a valid isc_heap_t. + *\li "index" is a valid element index, as provided by the "index" callback + * provided during heap creation. + * + * Returns: + *\li A pointer to the element for the element index. + */ + +void +isc_heap_foreach(isc_heap_t *heap, isc_heapaction_t action, void *uap); +/*!< + * \brief Iterate over the heap, calling an action for each element. The + * order of iteration is not sorted. + * + * Requires: + *\li "heapp" is not NULL and "*heap" points to a valid isc_heap_t. + *\li "action" is not NULL, and is a function which takes two arguments. + * The first is a void *, representing the element, and the second is + * "uap" as provided to isc_heap_foreach. + *\li "uap" is a caller-provided argument, and may be NULL. + * + * Note: + *\li The heap structure CANNOT be modified during this iteration. The only + * safe function to call while iterating the heap is isc_heap_element(). + */ ISC_LANG_ENDDECLS |
