heap_api.h File Reference

Binary heap API built on the Array abstraction. More...

#include "juno/ds/array_api.h"
#include "juno/macros.h"
#include "juno/memory/pointer_api.h"
#include "juno/status.h"
#include "juno/module.h"
#include <stdbool.h>
#include <stddef.h>

Include dependency graph for heap_api.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	JUNO_DS_HEAP_POINTER_API_TAG
	Element-level operations required by the heap. More...
struct	JUNO_DS_HEAP_API_TAG
	Heap API vtable. More...

Typedefs
typedef struct JUNO_DS_HEAP_ROOT_TAG	JUNO_DS_HEAP_ROOT_T
	Heap root type holding state and API pointer.
typedef struct JUNO_DS_HEAP_API_TAG	JUNO_DS_HEAP_API_T
	Heap API vtable type.
typedef struct JUNO_DS_HEAP_POINTER_API_TAG	JUNO_DS_HEAP_POINTER_API_T
	Element-level operations (compare/swap) used by the heap.

Functions
	JUNO_MODULE_RESULT (JUNO_DS_HEAP_INDEX_RESULT_T, size_t)
	Result type carrying an index on success. tStatus conveys success/error; tOk holds the index.
	JUNO_MODULE_OPTION (JUNO_DS_HEAP_INDEX_OPTION_T, size_t)
	Option type for an index. bIsSome indicates presence; tSome is the index.
	JUNO_MODULE_RESULT (JUNO_DS_HEAP_INDEX_OPTION_RESULT_T, JUNO_DS_HEAP_INDEX_OPTION_T)
	Result that wraps an optional index.
	JUNO_MODULE_RESULT (JUNO_DS_HEAP_COMPARE_RESULT_T, bool)
	Result of a comparison between parent/child respecting heap order.
struct JUNO_DS_HEAP_ROOT_TAG	JUNO_MODULE_ROOT (JUNO_DS_HEAP_API_T, const JUNO_DS_HEAP_POINTER_API_T *ptHeapPointerApi;JUNO_DS_ARRAY_ROOT_T *ptHeapArray;size_t zLength;)
	Heap root instance and state.
JUNO_STATUS_T	JunoDs_Heap_Update (JUNO_DS_HEAP_ROOT_T *ptHeap)
	Bubble-up the last inserted element to restore the heap property.
JUNO_STATUS_T	JunoDs_Heap_Insert (JUNO_DS_HEAP_ROOT_T *ptHeap, JUNO_POINTER_T tValue)
	Insert a new element into the heap.
JUNO_STATUS_T	JunoDs_Heap_Heapify (JUNO_DS_HEAP_ROOT_T *ptHeap)
	Transform the underlying array into a heap.
JUNO_STATUS_T	JunoDs_Heap_Pop (JUNO_DS_HEAP_ROOT_T *ptHeap, JUNO_POINTER_T tReturn)
	Pop the root element into tReturn.
JUNO_STATUS_T	JunoDs_Heap_Init (JUNO_DS_HEAP_ROOT_T *ptHeap, const JUNO_DS_HEAP_POINTER_API_T *ptHeapPointerApi, JUNO_DS_ARRAY_ROOT_T *ptHeapArray, JUNO_FAILURE_HANDLER_T pfcnFailureHdlr, JUNO_USER_DATA_T *pvUserData)
	Initialize a heap over a backing array and element pointer API.
JUNO_STATUS_T	JunoDs_Heap_SiftDown (JUNO_DS_HEAP_ROOT_T *ptHeap, size_t iStart)
	Sift down from a starting index to restore the heap property.
static JUNO_STATUS_T	JunoDs_Heap_Verify (JUNO_DS_HEAP_ROOT_T *ptHeap)
	Verify heap configuration and dependent APIs.

Detailed Description

Binary heap API built on the Array abstraction.

This API has been generated by LibJuno: https://www.robinonsay.com/libjuno/

Typedef Documentation

JUNO_DS_HEAP_API_T

typedef struct JUNO_DS_HEAP_API_TAG JUNO_DS_HEAP_API_T

Heap API vtable type.

JUNO_DS_HEAP_POINTER_API_T

typedef struct JUNO_DS_HEAP_POINTER_API_TAG JUNO_DS_HEAP_POINTER_API_T

Element-level operations (compare/swap) used by the heap.

JUNO_DS_HEAP_ROOT_T

typedef struct JUNO_DS_HEAP_ROOT_TAG JUNO_DS_HEAP_ROOT_T

Heap root type holding state and API pointer.

Function Documentation

JUNO_MODULE_OPTION()

JUNO_MODULE_OPTION	(	JUNO_DS_HEAP_INDEX_OPTION_T	,
		size_t
	)

Option type for an index. bIsSome indicates presence; tSome is the index.

Internal helper option for an index.

JUNO_MODULE_RESULT() [1/3]

JUNO_MODULE_RESULT	(	JUNO_DS_HEAP_COMPARE_RESULT_T	,
		bool
	)

Result of a comparison between parent/child respecting heap order.

JUNO_MODULE_RESULT() [2/3]

JUNO_MODULE_RESULT	(	JUNO_DS_HEAP_INDEX_OPTION_RESULT_T	,
		JUNO_DS_HEAP_INDEX_OPTION_T
	)

Result that wraps an optional index.

Internal helper result wrapping an optional index.

JUNO_MODULE_RESULT() [3/3]

JUNO_MODULE_RESULT	(	JUNO_DS_HEAP_INDEX_RESULT_T	,
		size_t
	)

Result type carrying an index on success. tStatus conveys success/error; tOk holds the index.

Internal helper result carrying an index.

JunoDs_Heap_Update()

JUNO_STATUS_T JunoDs_Heap_Update

(

JUNO_DS_HEAP_ROOT_T *

ptHeap

)

Bubble-up the last inserted element to restore the heap property.

Typical usage:

• Used internally by Insert after copying the new element.
• Can be called by users who directly modify the last element (index zLength-1) to restore the heap property.

Returns:

• JUNO_STATUS_SUCCESS on success.
• JUNO_STATUS_ERR if zLength == 0, or if Compare/Swap report an error, or if a computed parent index would exceed capacity.