heap.h File Reference

#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.

---

Detailed Description

Definition in file heap.h.

---

Define Documentation

#define ISC_HEAP_H   1

Definition at line 21 of file heap.h.

---

Typedef Documentation

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.

Definition at line 42 of file heap.h.

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().

Definition at line 50 of file heap.h.

typedef struct isc_heap isc_heap_t

Definition at line 52 of file heap.h.

---

Function Documentation

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:

• "mctx" is valid.
• "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.
• "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.
• "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.
• "heapp" is not NULL, and "*heap" is NULL.

Returns:

• ISC_R_SUCCESS - success
• ISC_R_NOMEMORY - insufficient memory

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:

• "heapp" is not NULL and "*heap" points to a valid isc_heap_t.

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:

• "heapp" is not NULL and "*heap" points to a valid isc_heap_t.

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:

• "heapp" is not NULL and "*heap" points to a valid isc_heap_t.
• "index" is a valid element index, as provided by the "index" callback provided during heap creation.

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:

• "heapp" is not NULL and "*heap" points to a valid isc_heap_t.
• "index" is a valid element index, as provided by the "index" callback provided during heap creation.

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:

• "heapp" is not NULL and "*heap" points to a valid isc_heap_t.
• "index" is a valid element index, as provided by the "index" callback provided during heap creation.

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:

• "heapp" is not NULL and "*heap" points to a valid isc_heap_t.
• "index" is a valid element index, as provided by the "index" callback provided during heap creation.

Returns:

• A pointer to the element for the element index.

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:

• "heapp" is not NULL and "*heap" points to a valid isc_heap_t.
• "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.
• "uap" is a caller-provided argument, and may be NULL.

Note:

• The heap structure CANNOT be modified during this iteration. The only safe function to call while iterating the heap is isc_heap_element().

Definition at line 257 of file heap.c.

References isc_heap::array, isc_heap::last, REQUIRE, and VALID_HEAP.

---

Variable Documentation

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.

---