pqmh_tests.h

Go to the documentation of this file.

/* -*- C -*-
 * Serene programming language
 * Copyright (C) 2019-2026 Sameer Rahmani <[email protected]>
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program 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 General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 */
 
#pragma once
 
#include <stdint.h>
 
#include "acutest.h"
#include "base.h"
#include "serene/rt/impl/pqmh.h"
 
#define PQMH_TESTS(X)                                                         \
  X("pqmh::empty", test_pqmh_empty), X("pqmh::ordering", test_pqmh_ordering), \
    X("pqmh::peek", test_pqmh_peek), X("pqmh::grow", test_pqmh_grow)
 
// Elements are stored by pointer; the tests stuff small ints into the pointer
// so no per-element allocation is needed.
static bool pqmh_int_less(srn_context_t *ctx, const void *a, const void *b) {
  UNUSED(ctx);
  return (intptr_t)a < (intptr_t)b;
}
 
static const pqmh_control_t pqmh_int_ctl = {.less = pqmh_int_less};
 
#define PQ_INT(v) ((void *)(intptr_t)(v))
 
// An empty queue, length 0, peek is NULL, pop fails and leaves `out` untouched.
static void test_pqmh_empty() {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  pqmh_t pq = pqmh_make(ctx, &pqmh_int_ctl, 0);
  TEST_CHECK(pqmh_len(&pq) == 0);
  TEST_CHECK(pqmh_peek(&pq) == nullptr);
 
  void *out = PQ_INT(123);
  TEST_CHECK(!pqmh_pop(ctx, &pq, &out));
  TEST_CHECK(out == PQ_INT(123)); // untouched on empty
 
  pqmh_free(ctx, &pq);
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}
 
// Push out of order, pop in ascending order (min-heap).
static void test_pqmh_ordering() {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  pqmh_t pq = pqmh_make(ctx, &pqmh_int_ctl, 4);
  int in[]  = {5, 1, 4, 2, 8, 3, 7, 6, 0, 9};
  enum { N = (int)(sizeof(in) / sizeof(in[0])) };
  for (int i = 0; i < N; i++) {
    pqmh_push(ctx, &pq, PQ_INT(in[i]));
  }
  TEST_CHECK(pqmh_len(&pq) == (size_t)N);
 
  for (int i = 0; i < N; i++) {
    void *out = nullptr;
    TEST_CHECK(pqmh_pop(ctx, &pq, &out));
    TEST_CHECK((intptr_t)out == i);
  }
  TEST_CHECK(pqmh_len(&pq) == 0);
 
  pqmh_free(ctx, &pq);
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}
 
// peek returns the min without removing it.
static void test_pqmh_peek() {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  pqmh_t pq = pqmh_make(ctx, &pqmh_int_ctl, 0);
  pqmh_push(ctx, &pq, PQ_INT(42));
  pqmh_push(ctx, &pq, PQ_INT(7));
  pqmh_push(ctx, &pq, PQ_INT(99));
 
  TEST_CHECK((intptr_t)pqmh_peek(&pq) == 7);
  TEST_CHECK(pqmh_len(&pq) == 3); // peek does not remove
 
  void *out = nullptr;
  TEST_CHECK(pqmh_pop(ctx, &pq, &out));
  TEST_CHECK((intptr_t)out == 7);
  TEST_CHECK((intptr_t)pqmh_peek(&pq) == 42);
 
  pqmh_free(ctx, &pq);
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}
 
// Start tiny and push far past the initial capacity to exercise growth, then
// confirm everything still comes out sorted.
static void test_pqmh_grow() {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  pqmh_t pq = pqmh_make(ctx, &pqmh_int_ctl, 2); // forces several doublings
  enum { N = 1000 };
  for (int i = N - 1; i >= 0; i--) { // descending in, each push sifts to root
    pqmh_push(ctx, &pq, PQ_INT(i));
  }
  TEST_CHECK(pqmh_len(&pq) == (size_t)N);
 
  for (int i = 0; i < N; i++) {
    void *out = nullptr;
    TEST_CHECK(pqmh_pop(ctx, &pq, &out));
    TEST_CHECK((intptr_t)out == i);
  }
  TEST_CHECK(pqmh_len(&pq) == 0);
 
  pqmh_free(ctx, &pq);
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}