pqmh.h File Reference

A generic priority queue backed by a binary min-heap. More...

#include <stddef.h>

Include dependency graph for pqmh.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	pqmh_control_t
	Per type configuration. More...
struct	pqmh_t
	A priority queue. More...

Typedefs
typedef bool(*	pqmh_less_fn) (srn_context_t *ctx, const void *a, const void *b)
	Strict weak ordering predicate over two elements.
typedef struct pqmh_control_t	pqmh_control_t
	Per type configuration.
typedef struct pqmh_t	pqmh_t
	A priority queue.

Functions
pqmh_t	pqmh_make (srn_context_t *ctx, const pqmh_control_t *ctl, size_t initial_cap)
	Create an empty queue ordered by ctl, with room for initial_cap elements (a small default is used when 0).
void	pqmh_push (srn_context_t *ctx, pqmh_t *pq, void *elem)
	Insert elem, growing the backing array (doubling) if it is full.
bool	pqmh_pop (srn_context_t *ctx, pqmh_t *pq, void **out)
	Remove the highest priority element into *out and return true, or return false (leaving *out untouched) when the queue is empty.
void *	pqmh_peek (const pqmh_t *pq)
	The highest priority element without removing it, or NULL when the queue is empty.
size_t	pqmh_len (const pqmh_t *pq)
	The number of elements currently in the queue.
void	pqmh_free (srn_context_t *ctx, pqmh_t *pq)
	Release the backing array and reset the queue to empty.

Detailed Description

A generic priority queue backed by a binary min-heap.

Elements are stored by pointer (void *), and the ordering is supplied through a control vtable (pqmh_control_t), so the same heap serves any element type – the only thing that varies per type is the comparison. The element the control orders first is the one at the root, returned by pqmh_peek and removed by pqmh_pop. A "less" predicate that returns a < b yields a min-heap, its inverse a max-heap.

This is a mutable, growable container. Its backing array is held in the manual lifetime allocator (srn_mm_malloc/srn_mm_reallocate/srn_mm_free) and grows by doubling, so a pqmh_t must be released with pqmh_free. By convention the operations take a srn_context_t * and reach the memory manager through ctx->engine->mm.

It is not synchronized; a pqmh_t is owned by a single thread and IS NOT THREAD SAFE.

Definition in file pqmh.h.

Typedef Documentation

pqmh_control_t

typedef struct pqmh_control_t pqmh_control_t

Per type configuration.

Only the comparison varies between element types. The heap operations themselves are type independent, so the control carries just the ordering predicate.

pqmh_less_fn

typedef bool(* pqmh_less_fn) (srn_context_t *ctx, const void *a, const void *b)

Strict weak ordering predicate over two elements.

Returns true when a should leave the queue before b (for a min-heap, when a < b). ctx is the context handed to the operation, for comparators that need it.

Definition at line 50 of file pqmh.h.

pqmh_t

typedef struct pqmh_t pqmh_t

A priority queue.

data is the backing heap array of element pointers, len the live count, cap the allocated capacity. The control is bound at pqmh_make and not re-passed per operation.

Function Documentation

pqmh_free()

void pqmh_free	(	srn_context_t *	ctx,
		pqmh_t *	pq )

Release the backing array and reset the queue to empty.

The elements themselves are not touched – their lifetime belongs to the caller.

Definition at line 142 of file pqmh.c.

                                               {
  PANIC_IF_NULL(ctx);
  PANIC_IF_NULL(pq);
 
  srn_mm_free(ctx->engine->mm, (void *)pq->data);
  pq->data = nullptr;
  pq->len  = 0;
  pq->cap  = 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

pqmh_len()

size_t pqmh_len ( const pqmh_t * pq )

nodiscard

The number of elements currently in the queue.

Definition at line 137 of file pqmh.c.

                                  {
  PANIC_IF_NULL(pq);
  return pq->len;
}

Here is the caller graph for this function:

pqmh_make()

pqmh_t pqmh_make ( srn_context_t * ctx, const pqmh_control_t * ctl, size_t initial_cap )

nodiscard

Create an empty queue ordered by ctl, with room for initial_cap elements (a small default is used when 0).

The backing array comes from the manual allocator, so the queue must later be released with pqmh_free.

Definition at line 81 of file pqmh.c.

                                                                                    {
  PANIC_IF_NULL(ctx);
  PANIC_IF_NULL(ctl);
 
  size_t cap  = (initial_cap == 0) ? PQMH_MIN_CAP : initial_cap;
  void **data = (void **)srn_mm_malloc(ctx->engine->mm, cap * sizeof(void *));
  PANIC_IF_NULL(data);
 
  return (pqmh_t){.ctl = ctl, .data = data, .len = 0, .cap = cap};
}

Here is the call graph for this function:

Here is the caller graph for this function:

pqmh_peek()

void * pqmh_peek ( const pqmh_t * pq )

nodiscard

The highest priority element without removing it, or NULL when the queue is empty.

(A queue holding NULL elements cannot tell empty from a NULL root via this call; use pqmh_len if that matters.)

Definition at line 132 of file pqmh.c.

                                  {
  PANIC_IF_NULL(pq);
  return (pq->len == 0) ? nullptr : pq->data[0];
}

Here is the caller graph for this function:

pqmh_pop()

bool pqmh_pop ( srn_context_t * ctx, pqmh_t * pq, void ** out )

nodiscard

Remove the highest priority element into *out and return true, or return false (leaving *out untouched) when the queue is empty.

Definition at line 111 of file pqmh.c.

                                                          {
  PANIC_IF_NULL(ctx);
  PANIC_IF_NULL(pq);
  PANIC_IF_NULL(out);
 
  if (pq->len == 0) {
    return false;
  }
 
  *out = pq->data[0];
  pq->len--;
 
  if (pq->len > 0) {
    // Promote the last element to the root and sink it into place.
    pq->data[0] = pq->data[pq->len];
    sift_down(ctx, pq, 0);
  }
 
  return true;
}

Here is the call graph for this function:

Here is the caller graph for this function:

pqmh_push()

void pqmh_push	(	srn_context_t *	ctx,
		pqmh_t *	pq,
		void *	elem )

Insert elem, growing the backing array (doubling) if it is full.

Panics if the growth allocation fails.

Definition at line 92 of file pqmh.c.

                                                           {
  PANIC_IF_NULL(ctx);
  PANIC_IF_NULL(pq);
 
  if (pq->len == pq->cap) {
    PANIC_IF(pq->cap > SIZE_MAX / 2 / sizeof(void *), "priority queue capacity overflows");
    size_t new_cap = pq->cap * 2;
    void **new_data =
      (void **)srn_mm_reallocate(ctx->engine->mm, (void *)pq->data, new_cap * sizeof(void *));
    PANIC_IF_NULL(new_data);
    pq->data = new_data;
    pq->cap  = new_cap;
  }
 
  pq->data[pq->len] = elem;
  pq->len++;
  sift_up(ctx, pq, pq->len - 1);
}

Here is the call graph for this function:

Here is the caller graph for this function: