juno_heap.c File Reference

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

Include dependency graph for juno_heap.c:

Functions
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.
static JUNO_DS_HEAP_INDEX_RESULT_T	JunoDs_Heap_ChildGetLeft (JUNO_DS_HEAP_ROOT_T *ptHeap, size_t iIndex)
	Compute the left child index of iIndex.
static JUNO_DS_HEAP_INDEX_RESULT_T	JunoDs_Heap_ChildGetRight (JUNO_DS_HEAP_ROOT_T *ptHeap, size_t iIndex)
	Compute the right child index of iIndex.
static JUNO_DS_HEAP_INDEX_RESULT_T	JunoDs_Heap_ChildGetParent (JUNO_DS_HEAP_ROOT_T *ptHeap, size_t iIndex)
	Compute the parent index of iIndex.
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_SiftDown (JUNO_DS_HEAP_ROOT_T *ptHeap, size_t iStart)
	Sift down from a starting index to restore the heap property.
JUNO_STATUS_T	JunoDs_Heap_Insert (JUNO_DS_HEAP_ROOT_T *ptHeap, JUNO_POINTER_T tValue)
	Reserve a new slot at the end of the heap array and return its index.
JUNO_STATUS_T	JunoDs_Heap_Heapify (JUNO_DS_HEAP_ROOT_T *ptHeap)
	Build a heap in-place from the current array contents.
JUNO_STATUS_T	JunoDs_Heap_Pop (JUNO_DS_HEAP_ROOT_T *ptHeap, JUNO_POINTER_T tReturn)
	Remove the root element and restore the heap property.

Variables
static const JUNO_DS_HEAP_API_T	tHeapApi

Function Documentation

JunoDs_Heap_ChildGetLeft()

static JUNO_DS_HEAP_INDEX_RESULT_T JunoDs_Heap_ChildGetLeft ( JUNO_DS_HEAP_ROOT_T *  ptHeap, size_t  iIndex  )

inlinestatic

Compute the left child index of iIndex.

Returns

A result wrapping an optional index:

• tStatus = SUCCESS and bIsSome = true when the left child is within current length.
• tStatus = SUCCESS and bIsSome = false when the left child would be beyond zLength.
• tStatus = ERR when the computed index would exceed zCapacity.

JunoDs_Heap_ChildGetParent()

static JUNO_DS_HEAP_INDEX_RESULT_T JunoDs_Heap_ChildGetParent ( JUNO_DS_HEAP_ROOT_T *  ptHeap, size_t  iIndex  )

inlinestatic

Compute the parent index of iIndex.

Returns

A result wrapping an optional index:

• tStatus = SUCCESS and bIsSome = true when the left child is within current length.
• tStatus = SUCCESS and bIsSome = false when the left child would be beyond zLength.
• tStatus = ERR when the computed index would exceed zCapacity.

JunoDs_Heap_ChildGetRight()

static JUNO_DS_HEAP_INDEX_RESULT_T JunoDs_Heap_ChildGetRight ( JUNO_DS_HEAP_ROOT_T *  ptHeap, size_t  iIndex  )

inlinestatic

Compute the right child index of iIndex.

Returns

A result wrapping an optional index:

• tStatus = SUCCESS and bIsSome = true when the left child is within current length.
• tStatus = SUCCESS and bIsSome = false when the left child would be beyond zLength.
• tStatus = ERR when the computed index would exceed zCapacity.

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.

Variable Documentation

tHeapApi

const JUNO_DS_HEAP_API_T tHeapApi

static

Initial value:

= {
    JunoDs_Heap_Insert,
    JunoDs_Heap_Heapify,
    JunoDs_Heap_Pop,
}