@web-font-path: "roboto-debian.css";
v2.2.0 (RP2040)
Loading...
Searching...
No Matches
pheap
pico_util

Pairing Heap Implementation. More...

## Macros

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

## Typedefs

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.

## 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.
void | ph_clear (pheap_t *heap)
| Removes all nodes from the pairing heap.
void | ph_destroy (pheap_t *heap)
| De-allocates a pairing heap.
static pheap_node_id_t | ph_new_node (pheap_t *heap)
| Allocate a new node from the unused space in the heap.
static pheap_node_id_t | ph_insert_node (pheap_t *heap, pheap_node_id_t id)
| Inserts a node into the heap.
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.
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.
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.
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().
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()).
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.
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.
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.

## Detailed Description

Pairing Heap Implementation.

pheap defines a simple pairing heap. The implementation simply tracks array indexes, it is up to the user to provide storage for heap entries and a comparison function.

NOTE: This class is not safe for concurrent usage. It should be externally protected. Furthermore if used concurrently, the caller needs to protect around their use of the returned id. For example, ph_remove_and_free_head returns the id of an element that is no longer in the heap. The user can still use this to look at the data in their companion array, however obviously further operations on the heap may cause them to overwrite that data as the id may be reused on subsequent operations

## 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()

bool ph_contains_node | ( | pheap_t * | heap,
|  | pheap_node_id_t | id )

inline static

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(* | dump_key )(pheap_node_id_t id, void *user_data),
|  | 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()

void ph_free_node | ( | pheap_t * | heap,
|  | pheap_node_id_t | id )

inline static

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()

pheap_node_id_t ph_insert_node | ( | pheap_t * | heap,
|  | pheap_node_id_t | id )

inline static

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()

pheap_node_id_t ph_new_node | ( | pheap_t * | heap | ) |

inline static

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()

pheap_node_id_t ph_peek_head | ( | pheap_t * | heap | ) |

inline static

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()

pheap_node_id_t ph_remove_and_free_head | ( | pheap_t * | heap | ) |

inline static

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.