High Performance OPC UA Server SDK
1.2.0.193
|
A binary tree based min/max heap aka priority queue. More...
Data Structures | |
struct | util_heap_node |
Simple node structure for binary tree, see also heap. More... | |
struct | util_heap |
The heap data structure, see also heap. More... | |
Typedefs | |
typedef int(* | util_heap_compar )(const void *a, const void *b) |
Comparison function that must be provided for the heap. More... | |
Functions | |
size_t | util_heap_size (unsigned int num_elements) |
Computes the size in bytes for num_elements heap entries. More... | |
void | util_heap_init (struct util_heap *heap, void *data, size_t size) |
Initializes a heap. More... | |
void * | util_heap_clear (struct util_heap *heap) |
Clear a heap heap . More... | |
int | util_heap_count (struct util_heap *heap) |
Returns the number of used elements in the given heap . More... | |
int | util_heap_enqueue (struct util_heap *heap, void *data, util_heap_compar comp) |
Add the given element to the heap. More... | |
void * | util_heap_dequeue (struct util_heap *heap, util_heap_compar comp) |
Remove the element with highest/lowest value from the heap. More... | |
void * | util_heap_first (struct util_heap *heap) |
Get the element with highest/lowest value from the heap. More... | |
A binary tree based min/max heap aka priority queue.
The heap is a complete binary tree (all levels except the last one are full). This allows to embedd the tree nodes into an simple array and omit the left, right, parent pointers. These relations can be calculated using the zero based array index i:
Usage example:
typedef int(* util_heap_compar)(const void *a, const void *b) |
Comparison function that must be provided for the heap.
Function capable of comparing the data added to heap by util_heap_enqueue. If the comparison function returns -1 for a < b the heap is a maximum heap. If you change the comparison function to return -1 for a > b the heap will become a minimum heap.
void* util_heap_clear | ( | struct util_heap * | heap | ) |
Clear a heap heap
.
No furhter operations may be performed on this heap after clearing.
int util_heap_count | ( | struct util_heap * | heap | ) |
Returns the number of used elements in the given heap
.
void* util_heap_dequeue | ( | struct util_heap * | heap, |
util_heap_compar | comp | ||
) |
Remove the element with highest/lowest value from the heap.
int util_heap_enqueue | ( | struct util_heap * | heap, |
void * | data, | ||
util_heap_compar | comp | ||
) |
Add the given element to the heap.
heap | The heap context. |
data | Element to add must be suitable for util_heap_compar. |
void* util_heap_first | ( | struct util_heap * | heap | ) |
Get the element with highest/lowest value from the heap.
Does not remove the element.
void util_heap_init | ( | struct util_heap * | heap, |
void * | data, | ||
size_t | size | ||
) |
Initializes a heap.
heap | The heap context. |
comp | util_heap_compar function, determines the sort order. |
data | Pointer to preallocated memory to use for the heap. |
size | Size of data in bytes determined by util_heap_size. |
size_t util_heap_size | ( | unsigned int | num_elements | ) |
Computes the size in bytes for num_elements
heap entries.
This can be used by the caller to allocate the correct amount of memory to be passed to util_heap_init.