heap.h File Reference

Go to the source code of this file.

Typedefs
typedef isc_boolean_t(*	isc_heapcompare_t) (void *, void *)
typedef void(*	isc_heapindex_t) (void *, unsigned int)
typedef void(*	isc_heapaction_t) (void *, void *)
typedef struct isc_heap	isc_heap_t

Functions
isc_result_t	isc_heap_create (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. More...
void	isc_heap_destroy (isc_heap_t **heapp)
	Destroys a heap. More...
isc_result_t	isc_heap_insert (isc_heap_t *heap, void *elt)
	Inserts a new element into a heap. More...
void	isc_heap_delete (isc_heap_t *heap, unsigned int index)
	Deletes an element from a heap, by element index. More...
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. More...
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. More...
void *	isc_heap_element (isc_heap_t *heap, unsigned int index)
	Returns the element for a specific element index. More...
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. More...

Typedef Documentation

isc_heap_t

typedef struct isc_heap isc_heap_t

Definition at line 47 of file heap.h.

isc_heapaction_t

typedef void(* isc_heapaction_t) (void *, void *)

Definition at line 45 of file heap.h.

isc_heapcompare_t

typedef isc_boolean_t(* isc_heapcompare_t) (void *, void *)

Definition at line 29 of file heap.h.

isc_heapindex_t

typedef void(* isc_heapindex_t) (void *, unsigned int)

Definition at line 37 of file heap.h.

Function Documentation

isc_heap_create()

isc_result_t isc_heap_create	(	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.

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

isc_heap_decreased()

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.

isc_heap_delete()

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.

isc_heap_destroy()

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.

isc_heap_element()

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.

isc_heap_foreach()

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

isc_heap_increased()

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.

isc_heap_insert()

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.