pqmh.h

Go to the documentation of this file.

/* -*- C -*-
 * Serene programming language
 * Copyright (C) 2019-2026 Sameer Rahmani <[email protected]>
 *
 * This library is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this library.  If not, see <https://www.gnu.org/licenses/>.
 */
 
#pragma once
 
/** @file
 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.
*/
 
#include <stddef.h>
 
typedef struct srn_context_t srn_context_t;
 
/**
 * 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.
 */
typedef bool (*pqmh_less_fn)(srn_context_t *ctx, const void *a, const void *b);
 
/**
 * 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.
 */
typedef struct pqmh_control_t {
  pqmh_less_fn less;
} pqmh_control_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.
 */
typedef struct pqmh_t {
  const pqmh_control_t *ctl;
  void **data;
  size_t len;
  size_t cap;
} pqmh_t;
 
/**
 * 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`.
 */
[[nodiscard]] [[gnu::nonnull(1, 2)]]
pqmh_t pqmh_make(srn_context_t *ctx, const pqmh_control_t *ctl, size_t initial_cap);
 
/**
 * Insert `elem`, growing the backing array (doubling) if it is full. Panics if
 * the growth allocation fails.
 */
[[gnu::nonnull(1, 2)]]
void pqmh_push(srn_context_t *ctx, pqmh_t *pq, void *elem);
 
/**
 * Remove the highest priority element into `*out` and return true, or return
 * false (leaving `*out` untouched) when the queue is empty.
 */
[[nodiscard]] [[gnu::nonnull(1, 2, 3)]]
bool pqmh_pop(srn_context_t *ctx, pqmh_t *pq, void **out);
 
/**
 * 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.)
 */
[[nodiscard]] [[gnu::nonnull(1)]]
void *pqmh_peek(const pqmh_t *pq);
 
/**
 * The number of elements currently in the queue.
 */
[[nodiscard]] [[gnu::nonnull(1)]]
size_t pqmh_len(const 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.
 */
[[gnu::nonnull(1, 2)]]
void pqmh_free(srn_context_t *ctx, pqmh_t *pq);