v2.0.0
Data Structures | Macros | Typedefs | Functions
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)
| 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 \
};
pheap_node
Definition: pheap.h:51
pheap
Definition: pheap.h:62

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.