#include "pico.h"

Include dependency graph for pheap.h:

Data Structures
struct	pheap_node

struct	pheap

Macros
#define	PARAM_ASSERTIONS_ENABLED_PHEAP 0

#define	PICO_PHEAP_MAX_ENTRIES 255

#define	PHEAP_DEFINE_STATIC(name, _max_nodes)
	Define a statically allocated pairing heap. This must be initialized by ph_post_alloc_init. More...

Typedefs
typedef uint8_t	pheap_node_id_t

typedef struct pheap_node	pheap_node_t

typedef bool(*	pheap_comparator) (void *user_data, pheap_node_id_t a, pheap_node_id_t b)
	A user comparator function for nodes in a pairing heap. More...

typedef struct pheap	pheap_t

Functions
pheap_t *	ph_create (uint max_nodes, pheap_comparator comparator, void *user_data)
	Create a pairing heap, which effectively maintains an efficient sorted ordering of nodes. The heap itself stores no user per-node state, it is expected that the user maintains a companion array. A comparator function must be provided so that the heap implementation can determine the relative ordering of nodes. More...

void	ph_clear (pheap_t *heap)
	Removes all nodes from the pairing heap. More...

void	ph_destroy (pheap_t *heap)
	De-allocates a pairing heap. More...

static pheap_node_t *	ph_get_node (pheap_t *heap, pheap_node_id_t id)

static void	ph_add_child_node (pheap_t *heap, pheap_node_id_t parent_id, pheap_node_id_t child_id)

static pheap_node_id_t	ph_merge_nodes (pheap_t *heap, pheap_node_id_t a, pheap_node_id_t b)

static pheap_node_id_t	ph_new_node (pheap_t *heap)
	Allocate a new node from the unused space in the heap. More...

static pheap_node_id_t	ph_insert_node (pheap_t *heap, pheap_node_id_t id)
	Inserts a node into the heap. More...

static pheap_node_id_t	ph_peek_head (pheap_t *heap)
	Returns the head node in the heap, i.e. the node which compares first, but without removing it from the heap. More...

pheap_node_id_t	ph_remove_head (pheap_t *heap, bool free)
	Remove the head node from the pairing heap. This head node is the node which compares first in the logical ordering provided by the comparator. More...

static pheap_node_id_t	ph_remove_and_free_head (pheap_t *heap)
	Remove the head node from the pairing heap. This head node is the node which compares first in the logical ordering provided by the comparator. More...

bool	ph_remove_and_free_node (pheap_t *heap, pheap_node_id_t id)
	Remove and free an arbitrary node from the pairing heap. This is a more costly operation than removing the head via ph_remove_and_free_head() More...

static bool	ph_contains_node (pheap_t *heap, pheap_node_id_t id)
	Determine if the heap contains a given node. Note containment refers to whether the node is inserted (ph_insert_node()) vs allocated (ph_new_node()) More...

static void	ph_free_node (pheap_t *heap, pheap_node_id_t id)
	Free a node that is not currently in the heap, but has been allocated. More...

void	ph_dump (pheap_t heap, void(dump_key)(pheap_node_id_t id, void user_data), void user_data)
	Print a representation of the heap for debugging. More...

void	ph_post_alloc_init (pheap_t heap, uint max_nodes, pheap_comparator comparator, void user_data)
	Initialize a statically allocated heap (ph_create() using the C heap). The heap member `nodes` must be allocated of size max_nodes. More...

Macro Definition Documentation

◆ PHEAP_DEFINE_STATIC

#define PHEAP_DEFINE_STATIC	(	name,
		_max_nodes
	)

Value:

    static_assert(_max_nodes && _max_nodes < (1u << (8 * sizeof(pheap_node_id_t))), ""); \
    static pheap_node_t name ## _nodes[_max_nodes]; \
    static pheap_t name = { \
            .nodes = name ## _nodes, \
            .max_nodes = _max_nodes \
    };

Define a statically allocated pairing heap. This must be initialized by ph_post_alloc_init.

Typedef Documentation

◆ pheap_comparator

typedef bool(* pheap_comparator) (void *user_data, pheap_node_id_t a, pheap_node_id_t b)

A user comparator function for nodes in a pairing heap.

Returns: true if a < b in natural order. Note this relative ordering must be stable from call to call.

Function Documentation

◆ ph_clear()

void ph_clear ( pheap_t * heap )

Removes all nodes from the pairing heap.

Parameters

heap the heap

◆ ph_contains_node()

static bool ph_contains_node	(	pheap_t *	heap,
		pheap_node_id_t	id
	)

inlinestatic

Determine if the heap contains a given node. Note containment refers to whether the node is inserted (ph_insert_node()) vs allocated (ph_new_node())

Parameters

heap	the heap
id	the id of the node

Returns: true if the heap contains a node with the given id, false otherwise.

◆ ph_create()

pheap_t * ph_create	(	uint	max_nodes,
		pheap_comparator	comparator,
		void *	user_data
	)

Create a pairing heap, which effectively maintains an efficient sorted ordering of nodes. The heap itself stores no user per-node state, it is expected that the user maintains a companion array. A comparator function must be provided so that the heap implementation can determine the relative ordering of nodes.

Parameters

max_nodes	the maximum number of nodes that may be in the heap (this is bounded by PICO_PHEAP_MAX_ENTRIES which defaults to 255 to be able to store indexes in a single byte).
comparator	the node comparison function
user_data	a user data pointer associated with the heap that is provided in callbacks

Returns: a newly allocated and initialized heap

◆ ph_destroy()

void ph_destroy ( pheap_t * heap )

De-allocates a pairing heap.

Note this method must ONLY be called on heaps created by ph_create()

Parameters

heap the heap

◆ ph_dump()

void ph_dump	(	pheap_t *	heap,
		void()(pheap_node_id_t id, void user_data)	dump_key,
		void *	user_data
	)

Print a representation of the heap for debugging.

Parameters

heap	the heap
dump_key	a method to print a node value
user_data	the user data to pass to the dump_key method

◆ ph_free_node()

static void ph_free_node	(	pheap_t *	heap,
		pheap_node_id_t	id
	)

inlinestatic

Free a node that is not currently in the heap, but has been allocated.

Parameters

heap	the heap
id	the id of the node

◆ ph_insert_node()

static pheap_node_id_t ph_insert_node	(	pheap_t *	heap,
		pheap_node_id_t	id
	)

inlinestatic

Inserts a node into the heap.

This method inserts a node (previously allocated by ph_new_node()) into the heap, determining the correct order by calling the heap's comparator

Parameters

heap	the heap
id	the id of the node to insert

Returns: the id of the new head of the pairing heap (i.e. node that compares first)

◆ ph_new_node()

static pheap_node_id_t ph_new_node ( pheap_t * heap )

inlinestatic

Allocate a new node from the unused space in the heap.

Parameters

heap the heap

Returns: an identifier for the node, or 0 if the heap is full

◆ ph_peek_head()

static pheap_node_id_t ph_peek_head ( pheap_t * heap )

inlinestatic

Returns the head node in the heap, i.e. the node which compares first, but without removing it from the heap.

Parameters

heap the heap

Returns: the current head node id

◆ ph_post_alloc_init()

void ph_post_alloc_init	(	pheap_t *	heap,
		uint	max_nodes,
		pheap_comparator	comparator,
		void *	user_data
	)

Initialize a statically allocated heap (ph_create() using the C heap). The heap member nodes must be allocated of size max_nodes.

Parameters

heap	the heap
max_nodes	the max number of nodes in the heap (matching the size of the heap's nodes array)
comparator	the comparator for the heap
user_data	the user data for the heap.

◆ ph_remove_and_free_head()

static pheap_node_id_t ph_remove_and_free_head ( pheap_t * heap )

inlinestatic

Remove the head node from the pairing heap. This head node is the node which compares first in the logical ordering provided by the comparator.

Note that the returned id will be freed, and thus may be re-used by future node allocations, so the caller should retrieve any per node state from the companion array before modifying the heap further.

Parameters

heap the heap

Returns: the old head node id.

◆ ph_remove_and_free_node()

bool ph_remove_and_free_node	(	pheap_t *	heap,
		pheap_node_id_t	id
	)

Remove and free an arbitrary node from the pairing heap. This is a more costly operation than removing the head via ph_remove_and_free_head()

Parameters

heap	the heap
id	the id of the node to free

Returns: true if the the node was in the heap, false otherwise

◆ ph_remove_head()

pheap_node_id_t ph_remove_head	(	pheap_t *	heap,
		bool	free
	)

Remove the head node from the pairing heap. This head node is the node which compares first in the logical ordering provided by the comparator.

Note that in the case of free == true, the returned id is no longer allocated and may be re-used by future node allocations, so the caller should retrieve any per node state from the companion array before modifying the heap further.

Parameters

heap	the heap
free	true if the id is also to be freed; false if not - useful if the caller may wish to re-insert an item with the same id)

Returns: the old head node id.

Data Structures

Macros

Typedefs

Functions

Macro Definition Documentation

◆ PHEAP_DEFINE_STATIC

Typedef Documentation

◆ pheap_comparator

Function Documentation

◆ ph_clear()

◆ ph_contains_node()

◆ ph_create()

◆ ph_destroy()

◆ ph_dump()

◆ ph_free_node()

◆ ph_insert_node()

◆ ph_new_node()

◆ ph_peek_head()

◆ ph_post_alloc_init()

◆ ph_remove_and_free_head()

◆ ph_remove_and_free_node()

◆ ph_remove_head()