pqmh.c

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/>.
 */
 
#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"
 
/// Capacity a queue created with `initial_cap == 0` starts at.
#define PQMH_MIN_CAP 8U
 
// Array-backed binary heap, the children of index `i` live at `2i+1` and
// `2i+2`, its parent at `(i-1)/2`.
 
/**
 * 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_up(srn_context_t *ctx, pqmh_t *pq, size_t i) {
  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;
  }
}
 
/**
 * Move the element at `i` down toward the leaves until the heap order holds
 * (neither child is ordered before it).
 */
static void sift_down(srn_context_t *ctx, pqmh_t *pq, size_t i) {
  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;
  }
}
 
pqmh_t pqmh_make(srn_context_t *ctx, const pqmh_control_t *ctl, size_t initial_cap) {
  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};
}
 
void pqmh_push(srn_context_t *ctx, pqmh_t *pq, void *elem) {
  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);
}
 
bool pqmh_pop(srn_context_t *ctx, pqmh_t *pq, void **out) {
  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;
}
 
void *pqmh_peek(const pqmh_t *pq) {
  PANIC_IF_NULL(pq);
  return (pq->len == 0) ? nullptr : pq->data[0];
}
 
size_t pqmh_len(const pqmh_t *pq) {
  PANIC_IF_NULL(pq);
  return pq->len;
}
 
void pqmh_free(srn_context_t *ctx, pqmh_t *pq) {
  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;
}