Heap
Specifies the heap structure. the heap could be a Min-Heap or a Max-Heap.
- Author
Matheus T. dos Santos (tenoriomatheus0@gmail.com)
- Version
0.1.0
- Date
19/09/2021
- Copyright
Matheus T. dos Santos todos os direitos reservados (c) 2021
Defines
-
BP_MIN_HEAP_INIT(array_, cmp_)
Macro to initialize a Min-Heap.
- Parameters
-
array_ – Buffer where the elements will be stored.
cmp_ – Function to compare the heap elements.
-
BP_MAX_HEAP_INIT(array_, cmp_)
Macro to initialize a Max-Heap.
- Parameters
-
array_ – Buffer where the elements will be stored.
cmp_ – Function to compare the heap elements.
Typedefs
-
typedef int (*bp_heap_cmp_t)(void *left, void *right)
Type for heap compare function. The return must be 0 for equals values, less than 0 if (<= 0) the left is less than the right, and greater than 0 (>= 0) if the left is greater than the right.
Enums
Functions
-
void *bp_heap_top(bp_heap_t *heap)
Get the root element of the Heap tree.
- Parameters
heap – Reference to bp_heap.
- Returns
A reference to the root element.
- Returns
NULL if the ‘heap’ argument is NULL or if the heap is empty.
-
int bp_heap_clear(bp_heap_t *heap)
Drop all elements in the heap.
Warning
After this function the heap size is zero, but the elements stay in the buffer.
- Parameters
heap – Reference to bp_heap.
- Returns
0 on success. @retrun -ENODEV if the ‘heap’ argument is NULL.
-
int bp_heap_pop(bp_heap_t *heap, void *el)
Remove the root element of the Heap tree and put it in el argument variable.
- Parameters
-
heap – Reference to bp_heap.
el – [out] Reference to a variable, where the removed element will be put.
- Returns
0 on success.
- Returns
-ENODEV if the ‘heap’ argument is NULL.
- Returns
-ENOENT if the stack size is zero.
- Returns
-EINVAL if the heap ‘_cmp’ field is NULL.
-
int bp_heap_push(bp_heap_t *heap, void *el)
Push an element on the Heap tree.
- Parameters
-
heap – Reference to bp_heap.
el – Reference to the element to be pushed.
- Returns
0 on success.
- Returns
-ENODEV if the ‘heap’ or the ‘el’ argument is NULL.
- Returns
-EINVAL if the heap ‘_cmp’ field is NULL.
-
int bp_heap_del(bp_heap_t *heap, void *param, bool (*cmp)(void *el, void *param))
Delete an array element, based at some parameter related to the element. This parameter could be the element itself, or some field of its type. The match will be done based on cmp function pointer. If the cmp function point argument is null, then the elements will be compared with the parameter byte by byte.
- Parameters
-
heap – Reference to bp_heap.
param – Reference to the parameter used to compare elements.
cmp – Function to compare an element with the parameter passed at argument param.
- Returns
0 on success.
- Returns
-ENODEV if the ‘heap’ or the ‘param’ argument is NULL.
- Returns
-ENOENT if the element isn’t in the heap.
- Returns
-EINVAL if the heap ‘_cmp’ field is NULL.
-
void *bp_heap_find(bp_heap_t *heap, void *param, bool (*cmp)(void *el, void *param))
Find the element in the heap, based at some parameter related to the element. This parameter could be the element itself, or some field of its type. The match will be done based on cmp function pointer. If the cmp function point argument is null, then the elements will be compared with the parameter byte by byte.
- Parameters
-
heap – Reference to bp_heap.
param – Reference to the parameter used to compare elements.
cmp – Function to compare an element with the parameter passed at argument param.
- Returns
A reference to the found element.
- Returns
NULL if the element wasn’t found or if the ‘heap’ or the ‘el’ argument is NULL.
-
bp_iter_t bp_heap_bfs_iter(bp_heap_t *heap)
Get a iterator to walk through the bp_heap, in Breadth-First-Search (BFS) sequence.
Warning
This function doesn’t check if the heap argument is null. So if this argument is null, a crash will occur. That check must be done outside the function.
- Parameters
heap – Reference to bp_heap.
- Returns
A new iterator instance for the bp_heap, using BFS sequence.
-
bp_iter_t bp_heap_dfs_iter(bp_heap_t *heap)
Get a iterator to walk through the bp_heap, in Depth-First-Search (DFS) sequence.
Warning
This function doesn’t check if the heap argument is null. So if this argument is null, a crash will occur. That check must be done outside the function.
- Parameters
heap – Reference to bp_heap.
- Returns
A new iterator instance for the bp_heap, using DFS sequence.
-
struct bp_heap_t
- #include <bp_heap.h>
Structure with metadata about the heap.
Note
This struct need an external buffer to work properly.
Public Members
-
bp_array_t _coll
Array that holds the heap elements.
-
bp_heap_kind_t _kind
Kind of the heap.
-
bp_heap_cmp_t _cmp
Function to compare two elements of the heap.
-
bp_array_t _coll