Skip to content

Commit b597ae6

Browse files
nathan-bossartnathan-bossart
committed
Add a test harness for the binary heap code.
binaryheap is heavily used and already has decent test coverage, but it lacks dedicated tests for its correctness. This commit changes that. Author: Aleksander Alekseev <aleksander@tigerdata.com> Discussion: https://postgr.es/m/CAJ7c6TMwp%2Bmb8MMoi%3DSMVMso2hYecoVu2Pwf2EOkesq0MiSKxw%40mail.gmail.com
1 parent daf9bdc commit b597ae6

File tree

10 files changed

+370
-0
lines changed

10 files changed

+370
-0
lines changed

‎src/test/modules/Makefile

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -15,6 +15,7 @@ SUBDIRS = \
1515
plsample \
1616
spgist_name_ops \
1717
test_aio \
18+
test_binaryheap \
1819
test_bloomfilter \
1920
test_copy_callbacks \
2021
test_custom_rmgrs \

‎src/test/modules/meson.build

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -14,6 +14,7 @@ subdir('plsample')
1414
subdir('spgist_name_ops')
1515
subdir('ssl_passphrase_callback')
1616
subdir('test_aio')
17+
subdir('test_binaryheap')
1718
subdir('test_bloomfilter')
1819
subdir('test_copy_callbacks')
1920
subdir('test_custom_rmgrs')

‎src/test/modules/test_binaryheap/.gitignore

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,4 @@
1+
# Generated subdirectories
2+
/log/
3+
/results/
4+
/tmp_check/

‎src/test/modules/test_binaryheap/Makefile

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
# src/test/modules/test_binaryheap/Makefile
2+
3+
MODULE_big = test_binaryheap
4+
OBJS = \
5+
$(WIN32RES) \
6+
test_binaryheap.o
7+
8+
PGFILEDESC = "test_binaryheap - test code for binaryheap"
9+
10+
EXTENSION = test_binaryheap
11+
DATA = test_binaryheap--1.0.sql
12+
13+
REGRESS = test_binaryheap
14+
15+
ifdef USE_PGXS
16+
PG_CONFIG = pg_config
17+
PGXS := $(shell $(PG_CONFIG) --pgxs)
18+
include $(PGXS)
19+
else
20+
subdir = src/test/modules/test_binaryheap
21+
top_builddir = ../../../..
22+
include $(top_builddir)/src/Makefile.global
23+
include $(top_srcdir)/contrib/contrib-global.mk
24+
endif

‎src/test/modules/test_binaryheap/expected/test_binaryheap.out

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
CREATE EXTENSION test_binaryheap;
2+
--
3+
-- These tests don't produce any interesting output. We're checking that
4+
-- the operations complete without crashing or hanging and that none of their
5+
-- internal sanity tests fail.
6+
--
7+
SELECT test_binaryheap();
8+
test_binaryheap
9+
-----------------
10+
11+
(1 row)
12+

‎src/test/modules/test_binaryheap/meson.build

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
# Copyright (c) 2025, PostgreSQL Global Development Group
2+
3+
test_binaryheap_sources = files(
4+
'test_binaryheap.c',
5+
)
6+
7+
if host_system == 'windows'
8+
test_binaryheap_sources += rc_lib_gen.process(win32ver_rc, extra_args: [
9+
'--NAME', 'test_binaryheap',
10+
'--FILEDESC', 'test_binaryheap - test code for binaryheap',])
11+
endif
12+
13+
test_binaryheap = shared_module('test_binaryheap',
14+
test_binaryheap_sources,
15+
kwargs: pg_test_mod_args,
16+
)
17+
test_install_libs += test_binaryheap
18+
19+
test_install_data += files(
20+
'test_binaryheap.control',
21+
'test_binaryheap--1.0.sql',
22+
)
23+
24+
tests += {
25+
'name': 'test_binaryheap',
26+
'sd': meson.current_source_dir(),
27+
'bd': meson.current_build_dir(),
28+
'regress': {
29+
'sql': [
30+
'test_binaryheap',
31+
],
32+
},
33+
}

‎src/test/modules/test_binaryheap/sql/test_binaryheap.sql

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
CREATE EXTENSION test_binaryheap;
2+
3+
--
4+
-- These tests don't produce any interesting output. We're checking that
5+
-- the operations complete without crashing or hanging and that none of their
6+
-- internal sanity tests fail.
7+
--
8+
SELECT test_binaryheap();

‎src/test/modules/test_binaryheap/test_binaryheap--1.0.sql

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
/* src/test/modules/test_binaryheap/test_binaryheap--1.0.sql */
2+
3+
-- complain if script is sourced in psql, rather than via CREATE EXTENSION
4+
\echo Use "CREATE EXTENSION test_binaryheap" to load this file. \quit
5+
6+
CREATE FUNCTION test_binaryheap() RETURNS VOID
7+
AS 'MODULE_PATHNAME' LANGUAGE C;

‎src/test/modules/test_binaryheap/test_binaryheap.c

Lines changed: 275 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,275 @@
1+
/*--------------------------------------------------------------------------
2+
*
3+
* test_binaryheap.c
4+
* Test correctness of binary heap implementation.
5+
*
6+
* Copyright (c) 2025, PostgreSQL Global Development Group
7+
*
8+
* IDENTIFICATION
9+
* src/test/modules/test_binaryheap/test_binaryheap.c
10+
*
11+
* -------------------------------------------------------------------------
12+
*/
13+
14+
#include "postgres.h"
15+
16+
#include "common/int.h"
17+
#include "common/pg_prng.h"
18+
#include "fmgr.h"
19+
#include "lib/binaryheap.h"
20+
21+
PG_MODULE_MAGIC;
22+
23+
/*
24+
* Test binaryheap_comparator for max-heap of integers.
25+
*/
26+
static int
27+
int_cmp(Datum a, Datum b, void *arg)
28+
{
29+
return pg_cmp_s32(DatumGetInt32(a), DatumGetInt32(b));
30+
}
31+
32+
/*
33+
* Loops through all nodes and returns the maximum value.
34+
*/
35+
static int
36+
get_max_from_heap(binaryheap *heap)
37+
{
38+
int max = -1;
39+
40+
for (int i = 0; i < binaryheap_size(heap); i++)
41+
max = Max(max, DatumGetInt32(binaryheap_get_node(heap, i)));
42+
43+
return max;
44+
}
45+
46+
/*
47+
* Generate a random permutation of the integers 0..size-1.
48+
*/
49+
static int *
50+
get_permutation(int size)
51+
{
52+
int *permutation = (int *) palloc(size * sizeof(int));
53+
54+
permutation[0] = 0;
55+
56+
/*
57+
* This is the "inside-out" variant of the Fisher-Yates shuffle algorithm.
58+
* Notionally, we append each new value to the array and then swap it with
59+
* a randomly-chosen array element (possibly including itself, else we
60+
* fail to generate permutations with the last integer last). The swap
61+
* step can be optimized by combining it with the insertion.
62+
*/
63+
for (int i = 1; i < size; i++)
64+
{
65+
int j = pg_prng_uint64_range(&pg_global_prng_state, 0, i);
66+
67+
if (j < i) /* avoid fetching undefined data if j=i */
68+
permutation[i] = permutation[j];
69+
permutation[j] = i;
70+
}
71+
72+
return permutation;
73+
}
74+
75+
/*
76+
* Ensure that the heap property holds for the given heap, i.e., each parent is
77+
* greater than or equal to its children.
78+
*/
79+
static void
80+
verify_heap_property(binaryheap *heap)
81+
{
82+
for (int i = 0; i < binaryheap_size(heap); i++)
83+
{
84+
int left = 2 * i + 1;
85+
int right = 2 * i + 2;
86+
int parent_val = DatumGetInt32(binaryheap_get_node(heap, i));
87+
88+
if (left < binaryheap_size(heap) &&
89+
parent_val < DatumGetInt32(binaryheap_get_node(heap, left)))
90+
elog(ERROR, "parent node less than left child");
91+
92+
if (right < binaryheap_size(heap) &&
93+
parent_val < DatumGetInt32(binaryheap_get_node(heap, right)))
94+
elog(ERROR, "parent node less than right child");
95+
}
96+
}
97+
98+
/*
99+
* Check correctness of basic operations.
100+
*/
101+
static void
102+
test_basic(int size)
103+
{
104+
binaryheap *heap = binaryheap_allocate(size, int_cmp, NULL);
105+
int *permutation = get_permutation(size);
106+
107+
if (!binaryheap_empty(heap))
108+
elog(ERROR, "new heap not empty");
109+
if (binaryheap_size(heap) != 0)
110+
elog(ERROR, "wrong size for new heap");
111+
112+
for (int i = 0; i < size; i++)
113+
{
114+
binaryheap_add(heap, Int32GetDatum(permutation[i]));
115+
verify_heap_property(heap);
116+
}
117+
118+
if (binaryheap_empty(heap))
119+
elog(ERROR, "heap empty after adding values");
120+
if (binaryheap_size(heap) != size)
121+
elog(ERROR, "wrong size for heap after adding values");
122+
123+
if (DatumGetInt32(binaryheap_first(heap)) != get_max_from_heap(heap))
124+
elog(ERROR, "incorrect root node after adding values");
125+
126+
for (int i = 0; i < size; i++)
127+
{
128+
int expected = get_max_from_heap(heap);
129+
int actual = DatumGetInt32(binaryheap_remove_first(heap));
130+
131+
if (actual != expected)
132+
elog(ERROR, "incorrect root node after removing root");
133+
verify_heap_property(heap);
134+
}
135+
136+
if (!binaryheap_empty(heap))
137+
elog(ERROR, "heap not empty after removing all nodes");
138+
}
139+
140+
/*
141+
* Test building heap after unordered additions.
142+
*/
143+
static void
144+
test_build(int size)
145+
{
146+
binaryheap *heap = binaryheap_allocate(size, int_cmp, NULL);
147+
int *permutation = get_permutation(size);
148+
149+
for (int i = 0; i < size; i++)
150+
binaryheap_add_unordered(heap, Int32GetDatum(permutation[i]));
151+
152+
if (binaryheap_size(heap) != size)
153+
elog(ERROR, "wrong size for heap after unordered additions");
154+
155+
binaryheap_build(heap);
156+
verify_heap_property(heap);
157+
}
158+
159+
/*
160+
* Test removing nodes.
161+
*/
162+
static void
163+
test_remove_node(int size)
164+
{
165+
binaryheap *heap = binaryheap_allocate(size, int_cmp, NULL);
166+
int *permutation = get_permutation(size);
167+
int remove_count = pg_prng_uint64_range(&pg_global_prng_state,
168+
0, size - 1);
169+
170+
for (int i = 0; i < size; i++)
171+
binaryheap_add(heap, Int32GetDatum(permutation[i]));
172+
173+
for (int i = 0; i < remove_count; i++)
174+
{
175+
int idx = pg_prng_uint64_range(&pg_global_prng_state,
176+
0, binaryheap_size(heap) - 1);
177+
178+
binaryheap_remove_node(heap, idx);
179+
verify_heap_property(heap);
180+
}
181+
182+
if (binaryheap_size(heap) != size - remove_count)
183+
elog(ERROR, "wrong size after removing nodes");
184+
}
185+
186+
/*
187+
* Test replacing the root node.
188+
*/
189+
static void
190+
test_replace_first(int size)
191+
{
192+
binaryheap *heap = binaryheap_allocate(size, int_cmp, NULL);
193+
194+
for (int i = 0; i < size; i++)
195+
binaryheap_add(heap, Int32GetDatum(i));
196+
197+
/*
198+
* Replace root with a value smaller than everything in the heap.
199+
*/
200+
binaryheap_replace_first(heap, Int32GetDatum(-1));
201+
verify_heap_property(heap);
202+
203+
/*
204+
* Replace root with a value in the middle of the heap.
205+
*/
206+
binaryheap_replace_first(heap, Int32GetDatum(size / 2));
207+
verify_heap_property(heap);
208+
209+
/*
210+
* Replace root with a larger value than everything in the heap.
211+
*/
212+
binaryheap_replace_first(heap, Int32GetDatum(size + 1));
213+
verify_heap_property(heap);
214+
}
215+
216+
/*
217+
* Test duplicate values.
218+
*/
219+
static void
220+
test_duplicates(int size)
221+
{
222+
binaryheap *heap = binaryheap_allocate(size, int_cmp, NULL);
223+
int dup = pg_prng_uint64_range(&pg_global_prng_state, 0, size - 1);
224+
225+
for (int i = 0; i < size; i++)
226+
binaryheap_add(heap, Int32GetDatum(dup));
227+
228+
for (int i = 0; i < size; i++)
229+
{
230+
if (DatumGetInt32(binaryheap_remove_first(heap)) != dup)
231+
elog(ERROR, "unexpected value in heap with duplicates");
232+
}
233+
}
234+
235+
/*
236+
* Test resetting.
237+
*/
238+
static void
239+
test_reset(int size)
240+
{
241+
binaryheap *heap = binaryheap_allocate(size, int_cmp, NULL);
242+
243+
for (int i = 0; i < size; i++)
244+
binaryheap_add(heap, Int32GetDatum(i));
245+
246+
binaryheap_reset(heap);
247+
248+
if (!binaryheap_empty(heap))
249+
elog(ERROR, "heap not empty after resetting");
250+
}
251+
252+
/*
253+
* SQL-callable entry point to perform all tests.
254+
*/
255+
PG_FUNCTION_INFO_V1(test_binaryheap);
256+
257+
Datum
258+
test_binaryheap(PG_FUNCTION_ARGS)
259+
{
260+
static const int test_sizes[] = {1, 2, 3, 10, 100, 1000};
261+
262+
for (int i = 0; i < sizeof(test_sizes) / sizeof(int); i++)
263+
{
264+
int size = test_sizes[i];
265+
266+
test_basic(size);
267+
test_build(size);
268+
test_remove_node(size);
269+
test_replace_first(size);
270+
test_duplicates(size);
271+
test_reset(size);
272+
}
273+
274+
PG_RETURN_VOID();
275+
}

‎src/test/modules/test_binaryheap/test_binaryheap.control

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
# test_binaryheap extension
2+
comment = 'Test code for binaryheap'
3+
default_version = '1.0'
4+
module_pathname = '$libdir/test_binaryheap'
5+
relocatable = true

0 commit comments

Comments
 (0)