heap.c File Reference

#include <config.h>
#include <isc/heap.h>
#include <isc/magic.h>
#include <isc/mem.h>
#include <isc/string.h>
#include <isc/util.h>

Go to the source code of this file.

Data Structures
struct	isc_heap
	ISC heap structure. More...
Defines
#define	SIZE_INCREMENT   1024
#define	HEAP_MAGIC   ISC_MAGIC('H', 'E', 'A', 'P')
#define	VALID_HEAP(h)   ISC_MAGIC_VALID(h, HEAP_MAGIC)
#define	HEAPCONDITION(i)
	When the heap is in a consistent state, the following invariant holds true: for every element i > 1, heap_parent(i) has a priority higher than or equal to that of i.
#define	heap_parent(i)   ((i) >> 1)
	Note: to make heap_parent and heap_left easy to compute, the first element of the heap array is not used; i.e. heap subscripts are 1-based, not 0-based. The parent is index/2, and the left-child is index*2. The right child is index*2+1.
#define	heap_left(i)   ((i) << 1)
	Note: to make heap_parent and heap_left easy to compute, the first element of the heap array is not used; i.e. heap subscripts are 1-based, not 0-based. The parent is index/2, and the left-child is index*2. The right child is index*2+1.
Functions
isc_result_t	isc_heap_create (isc_mem_t *mctx, isc_heapcompare_t compare, isc_heapindex_t idx, 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.
static isc_boolean_t	resize (isc_heap_t *heap)
static void	float_up (isc_heap_t *heap, unsigned int i, void *elt)
static void	sink_down (isc_heap_t *heap, unsigned int i, void *elt)
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 idx)
	Deletes an element from a heap, by element index.
void	isc_heap_increased (isc_heap_t *heap, unsigned int idx)
	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 idx)
	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 idx)
	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.

---

Detailed Description

Heap implementation of priority queues adapted from the following:

• "Introduction to Algorithms," Cormen, Leiserson, and Rivest, MIT Press / McGraw Hill, 1990, ISBN 0-262-03141-8, chapter 7.

• "Algorithms," Second Edition, Sedgewick, Addison-Wesley, 1988, ISBN 0-201-06673-4, chapter 11.

Definition in file heap.c.

---

Define Documentation

#define heap_parent

(

i

)

((i) >> 1)

Note: to make heap_parent and heap_left easy to compute, the first element of the heap array is not used; i.e. heap subscripts are 1-based, not 0-based. The parent is index/2, and the left-child is index*2. The right child is index*2+1.

Definition at line 45 of file heap.c.

Referenced by float_up().

#define heap_left

(

i

)

((i) << 1)

Note: to make heap_parent and heap_left easy to compute, the first element of the heap array is not used; i.e. heap subscripts are 1-based, not 0-based. The parent is index/2, and the left-child is index*2. The right child is index*2+1.

Definition at line 46 of file heap.c.

Referenced by sink_down().

#define SIZE_INCREMENT   1024

Definition at line 49 of file heap.c.

Referenced by isc_heap_create().

#define HEAP_MAGIC   ISC_MAGIC('H', 'E', 'A', 'P')

Definition at line 51 of file heap.c.

Referenced by isc_heap_create().

#define VALID_HEAP

(

h

)

ISC_MAGIC_VALID(h, HEAP_MAGIC)

Definition at line 52 of file heap.c.

Referenced by isc_heap_decreased(), isc_heap_delete(), isc_heap_destroy(), isc_heap_element(), isc_heap_foreach(), isc_heap_increased(), isc_heap_insert(), and resize().

#define HEAPCONDITION

(

i

)

Value:

((i) == 1 || \
                          ! heap->compare(heap->array[(i)], \
                                          heap->array[heap_parent(i)]))

When the heap is in a consistent state, the following invariant holds true: for every element i > 1, heap_parent(i) has a priority higher than or equal to that of i.

Definition at line 59 of file heap.c.

Referenced by float_up(), and sink_down().

---

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

static isc_boolean_t resize

(

isc_heap_t *

heap

)

[static]

Definition at line 124 of file heap.c.

References isc_heap::array, ISC_FALSE, isc_mem_get, isc_mem_put, ISC_TRUE, isc_heap::mctx, REQUIRE, isc_heap::size, isc_heap::size_increment, and VALID_HEAP.

Referenced by isc_heap_insert().

static void float_up	(	isc_heap_t *	heap,
		unsigned int	i,
		void *	elt
	)			[static]

Definition at line 146 of file heap.c.

References isc_heap::array, isc_heap::compare, heap_parent, HEAPCONDITION, isc_heap::index, and INSIST.

Referenced by isc_heap_delete(), isc_heap_increased(), and isc_heap_insert().

static void sink_down	(	isc_heap_t *	heap,
		unsigned int	i,
		void *	elt
	)			[static]

Definition at line 164 of file heap.c.

References isc_heap::array, isc_heap::compare, compare(), heap_left, HEAPCONDITION, isc_heap::index, INSIST, and isc_heap::last.

Referenced by isc_heap_decreased(), and isc_heap_delete().

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.

---