On Fri, Jun 27, 2025 at 02:02:22PM +0300, Aleksander Alekseev wrote: >> I'm not sure I see much point in testing both min-heaps and max-heaps. The >> only difference between the two is in the comparator, so IMHO the extra >> tests really only serve to test the test comparator. > > Make sense. Here is the corrected patch.
I trimmed this down some more while trying to keep the coverage the same. -- nathan
>From 246de76a2777a45f4ab5571712d905356e7f3713 Mon Sep 17 00:00:00 2001 From: Aleksander Alekseev <aleksan...@timescale.com> Date: Thu, 26 Jun 2025 16:05:36 +0300 Subject: [PATCH v3 1/1] Add tests for binaryheap.c Test our heap implementation more thoroughly at the binaryheap API level. Aleksander Alekseev, reviewed by Nathan Bossart Discussion: https://postgr.es/m/CAJ7c6TMwp%2Bmb8MMoi%3DSMVMso2hYecoVu2Pwf2EOkesq0MiSKxw%40mail.gmail.com --- src/test/modules/Makefile | 1 + src/test/modules/meson.build | 1 + src/test/modules/test_binaryheap/.gitignore | 4 + src/test/modules/test_binaryheap/Makefile | 24 ++ .../expected/test_binaryheap.out | 12 + src/test/modules/test_binaryheap/meson.build | 33 +++ .../test_binaryheap/sql/test_binaryheap.sql | 8 + .../test_binaryheap/test_binaryheap--1.0.sql | 7 + .../modules/test_binaryheap/test_binaryheap.c | 250 ++++++++++++++++++ .../test_binaryheap/test_binaryheap.control | 5 + 10 files changed, 345 insertions(+) create mode 100644 src/test/modules/test_binaryheap/.gitignore create mode 100644 src/test/modules/test_binaryheap/Makefile create mode 100644 src/test/modules/test_binaryheap/expected/test_binaryheap.out create mode 100644 src/test/modules/test_binaryheap/meson.build create mode 100644 src/test/modules/test_binaryheap/sql/test_binaryheap.sql create mode 100644 src/test/modules/test_binaryheap/test_binaryheap--1.0.sql create mode 100644 src/test/modules/test_binaryheap/test_binaryheap.c create mode 100644 src/test/modules/test_binaryheap/test_binaryheap.control diff --git a/src/test/modules/Makefile b/src/test/modules/Makefile index aa1d27bbed3..056c7316ec9 100644 --- a/src/test/modules/Makefile +++ b/src/test/modules/Makefile @@ -33,6 +33,7 @@ SUBDIRS = \ test_pg_dump \ test_predtest \ test_radixtree \ + test_binaryheap \ test_rbtree \ test_regex \ test_resowner \ diff --git a/src/test/modules/meson.build b/src/test/modules/meson.build index 9de0057bd1d..595f84323ab 100644 --- a/src/test/modules/meson.build +++ b/src/test/modules/meson.build @@ -32,6 +32,7 @@ subdir('test_parser') subdir('test_pg_dump') subdir('test_predtest') subdir('test_radixtree') +subdir('test_binaryheap') subdir('test_rbtree') subdir('test_regex') subdir('test_resowner') diff --git a/src/test/modules/test_binaryheap/.gitignore b/src/test/modules/test_binaryheap/.gitignore new file mode 100644 index 00000000000..5dcb3ff9723 --- /dev/null +++ b/src/test/modules/test_binaryheap/.gitignore @@ -0,0 +1,4 @@ +# Generated subdirectories +/log/ +/results/ +/tmp_check/ diff --git a/src/test/modules/test_binaryheap/Makefile b/src/test/modules/test_binaryheap/Makefile new file mode 100644 index 00000000000..d310fbc9e88 --- /dev/null +++ b/src/test/modules/test_binaryheap/Makefile @@ -0,0 +1,24 @@ +# src/test/modules/test_binaryheap/Makefile + +MODULE_big = test_binaryheap +OBJS = \ + $(WIN32RES) \ + test_binaryheap.o + +PGFILEDESC = "test_binaryheap - test code for binaryheap" + +EXTENSION = test_binaryheap +DATA = test_binaryheap--1.0.sql + +REGRESS = test_binaryheap + +ifdef USE_PGXS +PG_CONFIG = pg_config +PGXS := $(shell $(PG_CONFIG) --pgxs) +include $(PGXS) +else +subdir = src/test/modules/test_binaryheap +top_builddir = ../../../.. +include $(top_builddir)/src/Makefile.global +include $(top_srcdir)/contrib/contrib-global.mk +endif diff --git a/src/test/modules/test_binaryheap/expected/test_binaryheap.out b/src/test/modules/test_binaryheap/expected/test_binaryheap.out new file mode 100644 index 00000000000..16ce07875e3 --- /dev/null +++ b/src/test/modules/test_binaryheap/expected/test_binaryheap.out @@ -0,0 +1,12 @@ +CREATE EXTENSION test_binaryheap; +-- +-- These tests don't produce any interesting output. We're checking that +-- the operations complete without crashing or hanging and that none of their +-- internal sanity tests fail. +-- +SELECT test_binaryheap(); + test_binaryheap +----------------- + +(1 row) + diff --git a/src/test/modules/test_binaryheap/meson.build b/src/test/modules/test_binaryheap/meson.build new file mode 100644 index 00000000000..a71643cffa0 --- /dev/null +++ b/src/test/modules/test_binaryheap/meson.build @@ -0,0 +1,33 @@ +# Copyright (c) 2025, PostgreSQL Global Development Group + +test_binaryheap_sources = files( + 'test_binaryheap.c', +) + +if host_system == 'windows' + test_binaryheap_sources += rc_lib_gen.process(win32ver_rc, extra_args: [ + '--NAME', 'test_binaryheap', + '--FILEDESC', 'test_binaryheap - test code for binary heap library',]) +endif + +test_binaryheap = shared_module('test_binaryheap', + test_binaryheap_sources, + kwargs: pg_test_mod_args, +) +test_install_libs += test_binaryheap + +test_install_data += files( + 'test_binaryheap.control', + 'test_binaryheap--1.0.sql', +) + +tests += { + 'name': 'test_binaryheap', + 'sd': meson.current_source_dir(), + 'bd': meson.current_build_dir(), + 'regress': { + 'sql': [ + 'test_binaryheap', + ], + }, +} diff --git a/src/test/modules/test_binaryheap/sql/test_binaryheap.sql b/src/test/modules/test_binaryheap/sql/test_binaryheap.sql new file mode 100644 index 00000000000..8439545815b --- /dev/null +++ b/src/test/modules/test_binaryheap/sql/test_binaryheap.sql @@ -0,0 +1,8 @@ +CREATE EXTENSION test_binaryheap; + +-- +-- These tests don't produce any interesting output. We're checking that +-- the operations complete without crashing or hanging and that none of their +-- internal sanity tests fail. +-- +SELECT test_binaryheap(); diff --git a/src/test/modules/test_binaryheap/test_binaryheap--1.0.sql b/src/test/modules/test_binaryheap/test_binaryheap--1.0.sql new file mode 100644 index 00000000000..cddceeee603 --- /dev/null +++ b/src/test/modules/test_binaryheap/test_binaryheap--1.0.sql @@ -0,0 +1,7 @@ +/* src/test/modules/test_binaryheap/test_binaryheap--1.0.sql */ + +-- complain if script is sourced in psql, rather than via CREATE EXTENSION +\echo Use "CREATE EXTENSION test_binaryheap" to load this file. \quit + +CREATE FUNCTION test_binaryheap() RETURNS VOID + AS 'MODULE_PATHNAME' LANGUAGE C; diff --git a/src/test/modules/test_binaryheap/test_binaryheap.c b/src/test/modules/test_binaryheap/test_binaryheap.c new file mode 100644 index 00000000000..07346ef175c --- /dev/null +++ b/src/test/modules/test_binaryheap/test_binaryheap.c @@ -0,0 +1,250 @@ +/*-------------------------------------------------------------------------- + * + * test_binaryheap.c + * Test correctness of binary heap implementation. + * + * Copyright (c) 2025, PostgreSQL Global Development Group + * + * IDENTIFICATION + * src/test/modules/test_binaryheap/test_binaryheap.c + * + * ------------------------------------------------------------------------- + */ + +#include "postgres.h" + +#include "common/int.h" +#include "common/pg_prng.h" +#include "fmgr.h" +#include "lib/binaryheap.h" + +PG_MODULE_MAGIC; + +static int +int_cmp(Datum a, Datum b, void *arg) +{ + return pg_cmp_s32(DatumGetInt32(a), DatumGetInt32(b)); +} + +static int +get_max_from_heap(binaryheap *heap) +{ + int max = -1; + + for (int i = 0; i < binaryheap_size(heap); i++) + max = Max(max, DatumGetInt32(binaryheap_get_node(heap, i))); + + return max; +} + +/* + * Generate a random permutation of the integers 0..size-1 + */ +static int * +get_permutation(int size) +{ + int *permutation = (int *) palloc(size * sizeof(int)); + + permutation[0] = 0; + + /* + * This is the "inside-out" variant of the Fisher-Yates shuffle algorithm. + * Notionally, we append each new value to the array and then swap it with + * a randomly-chosen array element (possibly including itself, else we + * fail to generate permutations with the last integer last). The swap + * step can be optimized by combining it with the insertion. + */ + for (int i = 1; i < size; i++) + { + int j = pg_prng_uint64_range(&pg_global_prng_state, 0, i); + + if (j < i) /* avoid fetching undefined data if j=i */ + permutation[i] = permutation[j]; + permutation[j] = i; + } + + return permutation; +} + +static void +verify_heap_property(binaryheap *heap) +{ + for (int i = 0; i < binaryheap_size(heap); i++) + { + int left = 2 * i + 1; + int right = 2 * i + 2; + int parent_val = DatumGetInt32(binaryheap_get_node(heap, i)); + + if (left < binaryheap_size(heap)) + { + int lval = DatumGetInt32(binaryheap_get_node(heap, left)); + + if (parent_val < lval) + elog(ERROR, "heap property violated: parent %d < left child %d", + parent_val, lval); + } + + if (right < binaryheap_size(heap)) + { + int rval = DatumGetInt32(binaryheap_get_node(heap, right)); + + if (parent_val < rval) + elog(ERROR, "heap property violated: parent %d < right child %d", + parent_val, rval); + } + } +} + +static void +test_basic(int size) +{ + binaryheap *heap = binaryheap_allocate(size, int_cmp, NULL); + int *permutation = get_permutation(size); + + if (!binaryheap_empty(heap)) + elog(ERROR, "new heap should be empty"); + if (binaryheap_size(heap) != 0) + elog(ERROR, "new heap should have size 0"); + + for (int i = 0; i < size; i++) + { + binaryheap_add(heap, Int32GetDatum(permutation[i])); + verify_heap_property(heap); + } + + if (binaryheap_empty(heap)) + elog(ERROR, "heap should not be empty after adding elements"); + if (binaryheap_size(heap) != size) + elog(ERROR, "heap size should be %d, got %d", size, binaryheap_size(heap)); + + if (DatumGetInt32(binaryheap_first(heap)) != get_max_from_heap(heap)) + elog(ERROR, "heap first element should be %d, got %d", + get_max_from_heap(heap), DatumGetInt32(binaryheap_first(heap))); + + for (int i = 0; i < size; i++) + { + int expected = get_max_from_heap(heap); + int actual = DatumGetInt32(binaryheap_remove_first(heap)); + + if (actual != expected) + elog(ERROR, "remove_first should return %d, got %d", expected, actual); + verify_heap_property(heap); + } + + if (!binaryheap_empty(heap)) + elog(ERROR, "heap should be empty after removing all elements"); +} + +static void +test_build(int size) +{ + binaryheap *heap = binaryheap_allocate(size, int_cmp, NULL); + int *permutation = get_permutation(size); + + for (int i = 0; i < size; i++) + binaryheap_add_unordered(heap, Int32GetDatum(permutation[i])); + + if (binaryheap_size(heap) != size) + elog(ERROR, "heap size should be %d after unordered adds", size); + + binaryheap_build(heap); + verify_heap_property(heap); +} + +static void +test_remove_node(int size) +{ + binaryheap *heap = binaryheap_allocate(size, int_cmp, NULL); + int *permutation = get_permutation(size); + int remove_count = pg_prng_uint64_range(&pg_global_prng_state, + 0, size - 1);; + + for (int i = 0; i < size; i++) + binaryheap_add(heap, Int32GetDatum(permutation[i])); + + for (int i = 0; i < remove_count; i++) + { + int idx = pg_prng_uint64_range(&pg_global_prng_state, + 0, binaryheap_size(heap) - 1); + + binaryheap_remove_node(heap, idx); + verify_heap_property(heap); + } + + if (binaryheap_size(heap) != size - remove_count) + elog(ERROR, "heap size should be %d after removing %d nodes, got %d", + size - remove_count, remove_count, binaryheap_size(heap)); +} + +static void +test_replace_first(int size) +{ + binaryheap *heap = binaryheap_allocate(size, int_cmp, NULL); + + for (int i = 0; i < size; i++) + binaryheap_add(heap, Int32GetDatum(i)); + + binaryheap_replace_first(heap, Int32GetDatum(size / 2)); + verify_heap_property(heap); + + if (DatumGetInt32(binaryheap_first(heap)) != get_max_from_heap(heap)) + elog(ERROR, "first element should be %d after replacement, got %d", + get_max_from_heap(heap), DatumGetInt32(binaryheap_first(heap))); + + binaryheap_replace_first(heap, Int32GetDatum(size + 1)); + verify_heap_property(heap); + + if (DatumGetInt32(binaryheap_first(heap)) != size + 1) + elog(ERROR, "first element should be %d after replacement, got %d", + size + 1, DatumGetInt32(binaryheap_first(heap))); +} + +static void +test_duplicates(int size) +{ + binaryheap *heap = binaryheap_allocate(size, int_cmp, NULL); + int dup = pg_prng_uint64_range(&pg_global_prng_state, 0, size - 1); + + for (int i = 0; i < size; i++) + binaryheap_add(heap, Int32GetDatum(dup)); + + for (int i = 0; i < size; i++) + { + if (DatumGetInt32(binaryheap_remove_first(heap)) != dup) + elog(ERROR, "all elements should be %d", dup); + } +} + +static void +test_reset(int size) +{ + binaryheap *heap = binaryheap_allocate(size, int_cmp, NULL); + + for (int i = 0; i < size; i++) + binaryheap_add(heap, Int32GetDatum(i)); + + binaryheap_reset(heap); + + if (!binaryheap_empty(heap)) + elog(ERROR, "heap should be empty after reset"); +} + +PG_FUNCTION_INFO_V1(test_binaryheap); + +Datum +test_binaryheap(PG_FUNCTION_ARGS) +{ + static const int test_sizes[] = {1, 2, 3, 10, 100, 1000}; + + for (int i = 0; i < sizeof(test_sizes) / sizeof(int); i++) + { + test_basic(test_sizes[i]); + test_build(test_sizes[i]); + test_remove_node(test_sizes[i]); + test_replace_first(test_sizes[i]); + test_duplicates(test_sizes[i]); + test_reset(test_sizes[i]); + } + + PG_RETURN_VOID(); +} diff --git a/src/test/modules/test_binaryheap/test_binaryheap.control b/src/test/modules/test_binaryheap/test_binaryheap.control new file mode 100644 index 00000000000..5400783d078 --- /dev/null +++ b/src/test/modules/test_binaryheap/test_binaryheap.control @@ -0,0 +1,5 @@ +# test_binaryheap extension +comment = 'Test code for binary heap' +default_version = '1.0' +module_pathname = '$libdir/test_binaryheap' +relocatable = true -- 2.39.5 (Apple Git-154)
