pqmh.c File Reference

#include "serene/rt/impl/pqmh.h"
#include "serene/rt/context.h"
#include "serene/rt/engine.h"
#include "serene/rt/mm/interface.h"
#include "serene/utils.h"

Include dependency graph for pqmh.c:

Go to the source code of this file.

Macros
#define	PQMH_MIN_CAP   8U
	Capacity a queue created with initial_cap == 0 starts at.

Functions
static void	sift_up (srn_context_t *ctx, pqmh_t *pq, size_t i)
	Move the element at i up toward the root until the heap order holds (its parent is no longer ordered after it).
static void	sift_down (srn_context_t *ctx, pqmh_t *pq, size_t i)
	Move the element at i down toward the leaves until the heap order holds (neither child is ordered before it).
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.

Macro Definition Documentation

PQMH_MIN_CAP

#define PQMH_MIN_CAP   8U

Capacity a queue created with initial_cap == 0 starts at.

Definition at line 27 of file pqmh.c.

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:

sift_down()

void sift_down ( srn_context_t * ctx, pqmh_t * pq, size_t i )

static

Move the element at i down toward the leaves until the heap order holds (neither child is ordered before it).

Definition at line 56 of file pqmh.c.

                                                                {
  for (;;) {
    size_t left     = (2 * i) + 1;
    size_t right    = (2 * i) + 2;
    size_t smallest = i;
 
    if (left < pq->len && (int)pq->ctl->less(ctx, pq->data[left], pq->data[smallest])) {
      smallest = left;
    }
 
    if (right < pq->len && (int)pq->ctl->less(ctx, pq->data[right], pq->data[smallest])) {
      smallest = right;
    }
 
    if (smallest == i) {
      break;
    }
 
    void *tmp          = pq->data[i];
    pq->data[i]        = pq->data[smallest];
    pq->data[smallest] = tmp;
    i                  = smallest;
  }
}

Here is the caller graph for this function:

sift_up()

void sift_up ( srn_context_t * ctx, pqmh_t * pq, size_t i )

static

Move the element at i up toward the root until the heap order holds (its parent is no longer ordered after it).

Definition at line 36 of file pqmh.c.

                                                              {
  while (i > 0) {
    size_t parent = (i - 1) / 2;
 
    if (!pq->ctl->less(ctx, pq->data[i], pq->data[parent])) {
      // Now the order is correct
      break;
    }
 
    void *tmp        = pq->data[i];
    pq->data[i]      = pq->data[parent];
    pq->data[parent] = tmp;
    i                = parent;
  }
}

Here is the caller graph for this function: