Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitb597ae6

Browse files
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 commitchanges that.Author: Aleksander Alekseev <aleksander@tigerdata.com>Discussion:https://postgr.es/m/CAJ7c6TMwp%2Bmb8MMoi%3DSMVMso2hYecoVu2Pwf2EOkesq0MiSKxw%40mail.gmail.com
1 parentdaf9bdc commitb597ae6

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')
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/
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+
ifdefUSE_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
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+
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+
}
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();
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+
CREATEFUNCTIONtest_binaryheap() RETURNS VOID
7+
AS'MODULE_PATHNAME' LANGUAGE 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+
staticint
27+
int_cmp(Datuma,Datumb,void*arg)
28+
{
29+
returnpg_cmp_s32(DatumGetInt32(a),DatumGetInt32(b));
30+
}
31+
32+
/*
33+
* Loops through all nodes and returns the maximum value.
34+
*/
35+
staticint
36+
get_max_from_heap(binaryheap*heap)
37+
{
38+
intmax=-1;
39+
40+
for (inti=0;i<binaryheap_size(heap);i++)
41+
max=Max(max,DatumGetInt32(binaryheap_get_node(heap,i)));
42+
43+
returnmax;
44+
}
45+
46+
/*
47+
* Generate a random permutation of the integers 0..size-1.
48+
*/
49+
staticint*
50+
get_permutation(intsize)
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 (inti=1;i<size;i++)
64+
{
65+
intj=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+
returnpermutation;
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+
staticvoid
80+
verify_heap_property(binaryheap*heap)
81+
{
82+
for (inti=0;i<binaryheap_size(heap);i++)
83+
{
84+
intleft=2*i+1;
85+
intright=2*i+2;
86+
intparent_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+
staticvoid
102+
test_basic(intsize)
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 (inti=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 (inti=0;i<size;i++)
127+
{
128+
intexpected=get_max_from_heap(heap);
129+
intactual=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+
staticvoid
144+
test_build(intsize)
145+
{
146+
binaryheap*heap=binaryheap_allocate(size,int_cmp,NULL);
147+
int*permutation=get_permutation(size);
148+
149+
for (inti=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+
staticvoid
163+
test_remove_node(intsize)
164+
{
165+
binaryheap*heap=binaryheap_allocate(size,int_cmp,NULL);
166+
int*permutation=get_permutation(size);
167+
intremove_count=pg_prng_uint64_range(&pg_global_prng_state,
168+
0,size-1);
169+
170+
for (inti=0;i<size;i++)
171+
binaryheap_add(heap,Int32GetDatum(permutation[i]));
172+
173+
for (inti=0;i<remove_count;i++)
174+
{
175+
intidx=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+
staticvoid
190+
test_replace_first(intsize)
191+
{
192+
binaryheap*heap=binaryheap_allocate(size,int_cmp,NULL);
193+
194+
for (inti=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+
staticvoid
220+
test_duplicates(intsize)
221+
{
222+
binaryheap*heap=binaryheap_allocate(size,int_cmp,NULL);
223+
intdup=pg_prng_uint64_range(&pg_global_prng_state,0,size-1);
224+
225+
for (inti=0;i<size;i++)
226+
binaryheap_add(heap,Int32GetDatum(dup));
227+
228+
for (inti=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+
staticvoid
239+
test_reset(intsize)
240+
{
241+
binaryheap*heap=binaryheap_allocate(size,int_cmp,NULL);
242+
243+
for (inti=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+
staticconstinttest_sizes[]= {1,2,3,10,100,1000};
261+
262+
for (inti=0;i<sizeof(test_sizes) /sizeof(int);i++)
263+
{
264+
intsize=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+
}
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)
[8]ページ先頭
©2009-2025 Movatter.jp