#include <isc/lang.h>
#include <isc/types.h>
Go to the source code of this file.
Defines | |
#define | ISC_HEAP_H 1 |
Typedefs | |
typedef void(* | isc_heapindex_t )(void *, unsigned int) |
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_heapaction_t )(void *, void *) |
The heapaction function is used when iterating over the heap. | |
typedef struct isc_heap | isc_heap_t |
Functions | |
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) |
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. | |
void | isc_heap_destroy (isc_heap_t **heapp) |
Destroys a heap. | |
isc_result_t | isc_heap_insert (isc_heap_t *heap, void *elt) |
Inserts a new element into a heap. | |
void | isc_heap_delete (isc_heap_t *heap, unsigned int index) |
Deletes an element from a heap, by element index. | |
void | isc_heap_increased (isc_heap_t *heap, unsigned int index) |
Indicates to the heap that an element's priority has increased. This function MUST be called whenever an element has increased in priority. | |
void | isc_heap_decreased (isc_heap_t *heap, unsigned int index) |
Indicates to the heap that an element's priority has decreased. This function MUST be called whenever an element has decreased in priority. | |
void * | isc_heap_element (isc_heap_t *heap, unsigned int index) |
Returns the element for a specific element index. | |
void | isc_heap_foreach (isc_heap_t *heap, isc_heapaction_t action, void *uap) |
Iterate over the heap, calling an action for each element. The order of iteration is not sorted. | |
Variables | |
ISC_LANG_BEGINDECLS typedef isc_boolean_t(* | isc_heapcompare_t )(void *, void *) |
The comparison function returns ISC_TRUE if the first argument has higher priority than the second argument, and ISC_FALSE otherwise. |
Definition in file heap.h.
typedef void(* isc_heapindex_t)(void *, unsigned int) |
typedef void(* isc_heapaction_t)(void *, void *) |
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 struct isc_heap isc_heap_t |
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 | |||
) |
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.
Heap elements are indexed from 1.
Requires:
Definition at line 76 of file heap.c.
References isc_heap::array, isc_heap::compare, HEAP_MAGIC, isc_heap::index, isc_mem_attach(), isc_mem_get, ISC_R_NOMEMORY, ISC_R_SUCCESS, isc_heap::last, isc_heap::magic, isc_heap::mctx, REQUIRE, isc_heap::size, SIZE_INCREMENT, and isc_heap::size_increment.
Referenced by dns_rbtdb_create(), isc__timermgr_create(), and verifyzone().
void isc_heap_destroy | ( | isc_heap_t ** | heapp | ) |
Destroys a heap.
Requires:
Definition at line 107 of file heap.c.
References isc_heap::array, isc_mem_put, isc_mem_putanddetach, isc_heap::magic, isc_heap::mctx, REQUIRE, isc_heap::size, and VALID_HEAP.
Referenced by dns_rbtdb_create(), free_rbtdb(), isc__timermgr_create(), isc__timermgr_destroy(), and verifyzone().
isc_result_t isc_heap_insert | ( | isc_heap_t * | heap, | |
void * | elt | |||
) |
Inserts a new element into a heap.
Requires:
Definition at line 189 of file heap.c.
References float_up(), ISC_R_NOMEMORY, ISC_R_SUCCESS, isc_heap::last, REQUIRE, resize(), RUNTIME_CHECK, isc_heap::size, and VALID_HEAP.
Referenced by add32(), rbt_datafixer(), record_nsec3(), resign_insert(), and schedule().
void isc_heap_delete | ( | isc_heap_t * | heap, | |
unsigned int | index | |||
) |
Deletes an element from a heap, by element index.
Requires:
Definition at line 206 of file heap.c.
References isc_heap::array, isc_heap::compare, float_up(), isc_heap::last, REQUIRE, sink_down(), and VALID_HEAP.
Referenced by deschedule(), dispatch(), free_rdataset(), resign_delete(), setsigningtime(), and verify_nsec3_chains().
void isc_heap_increased | ( | isc_heap_t * | heap, | |
unsigned int | index | |||
) |
Indicates to the heap that an element's priority has increased. This function MUST be called whenever an element has increased in priority.
Requires:
Definition at line 231 of file heap.c.
References isc_heap::array, float_up(), REQUIRE, and VALID_HEAP.
Referenced by schedule(), set_ttl(), and setsigningtime().
void isc_heap_decreased | ( | isc_heap_t * | heap, | |
unsigned int | index | |||
) |
Indicates to the heap that an element's priority has decreased. This function MUST be called whenever an element has decreased in priority.
Requires:
Definition at line 239 of file heap.c.
References isc_heap::array, REQUIRE, sink_down(), and VALID_HEAP.
Referenced by schedule(), set_ttl(), and setsigningtime().
void* isc_heap_element | ( | isc_heap_t * | heap, | |
unsigned int | index | |||
) |
Returns the element for a specific element index.
Requires:
Definition at line 247 of file heap.c.
References isc_heap::array, REQUIRE, and VALID_HEAP.
Referenced by addrdataset(), dispatch(), getsigningtime(), overmem_purge(), and verify_nsec3_chains().
void isc_heap_foreach | ( | isc_heap_t * | heap, | |
isc_heapaction_t | action, | |||
void * | uap | |||
) |
Iterate over the heap, calling an action for each element. The order of iteration is not sorted.
Requires:
Definition at line 257 of file heap.c.
References isc_heap::array, isc_heap::last, REQUIRE, and VALID_HEAP.
ISC_LANG_BEGINDECLS typedef isc_boolean_t(* isc_heapcompare_t)(void *, void *) |
The comparison function returns ISC_TRUE if the first argument has higher priority than the second argument, and ISC_FALSE otherwise.