#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. |
Definition in file heap.c.
#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 |
#define HEAP_MAGIC ISC_MAGIC('H', 'E', 'A', 'P') |
#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)]))
Definition at line 59 of file heap.c.
Referenced by float_up(), and sink_down().
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().
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:
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.