pheap.h File Reference

#include "pico.h"

Include dependency graph for pheap.h:

Go to the source code of this file.

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)

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)
typedef struct pheap	pheap_t

Functions
pheap_t *	ph_create (uint max_nodes, pheap_comparator comparator, void *user_data)
void	ph_clear (pheap_t *heap)
void	ph_destroy (pheap_t *heap)
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)
static pheap_node_id_t	ph_insert_node (pheap_t *heap, pheap_node_id_t id)
static pheap_node_id_t	ph_peek_head (pheap_t *heap)
pheap_node_id_t	ph_remove_head (pheap_t *heap, bool free)
static pheap_node_id_t	ph_remove_and_free_head (pheap_t *heap)
bool	ph_remove_and_free_node (pheap_t *heap, pheap_node_id_t id)
static bool	ph_contains_node (pheap_t *heap, pheap_node_id_t id)
static void	ph_free_node (pheap_t *heap, pheap_node_id_t id)
void	ph_dump (pheap_t *heap, void(*dump_key)(pheap_node_id_t id, void *user_data), void *user_data)
void	ph_post_alloc_init (pheap_t *heap, uint max_nodes, pheap_comparator comparator, void *user_data)

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.