Line data Source code
1 : /*--------------------------------------------------------------------------
2 : *
3 : * test_binaryheap.c
4 : * Test correctness of binary heap implementation.
5 : *
6 : * Copyright (c) 2025-2026, 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 1 : PG_MODULE_MAGIC;
22 :
23 : /*
24 : * Test binaryheap_comparator for max-heap of integers.
25 : */
26 : static int
27 45494 : int_cmp(Datum a, Datum b, void *arg)
28 : {
29 45494 : 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 1122 : get_max_from_heap(binaryheap *heap)
37 : {
38 1122 : int max = -1;
39 :
40 507853 : for (int i = 0; i < binaryheap_size(heap); i++)
41 506731 : max = Max(max, DatumGetInt32(binaryheap_get_node(heap, i)));
42 :
43 1122 : return max;
44 : }
45 :
46 : /*
47 : * Generate a random permutation of the integers 0..size-1.
48 : */
49 : static int *
50 18 : get_permutation(int size)
51 : {
52 18 : int *permutation = (int *) palloc(size * sizeof(int));
53 :
54 18 : 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 3348 : for (int i = 1; i < size; i++)
64 : {
65 3330 : int j = pg_prng_uint64_range(&pg_global_prng_state, 0, i);
66 :
67 3330 : if (j < i) /* avoid fetching undefined data if j=i */
68 3285 : permutation[i] = permutation[j];
69 3330 : permutation[j] = i;
70 : }
71 :
72 18 : 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 2956 : verify_heap_property(binaryheap *heap)
81 : {
82 1465845 : for (int i = 0; i < binaryheap_size(heap); i++)
83 : {
84 1462889 : int left = 2 * i + 1;
85 1462889 : int right = 2 * i + 2;
86 1462889 : int parent_val = DatumGetInt32(binaryheap_get_node(heap, i));
87 :
88 2193596 : if (left < binaryheap_size(heap) &&
89 730707 : parent_val < DatumGetInt32(binaryheap_get_node(heap, left)))
90 0 : elog(ERROR, "parent node less than left child");
91 :
92 2192121 : if (right < binaryheap_size(heap) &&
93 729232 : parent_val < DatumGetInt32(binaryheap_get_node(heap, right)))
94 0 : elog(ERROR, "parent node less than right child");
95 : }
96 2956 : }
97 :
98 : /*
99 : * Check correctness of basic operations.
100 : */
101 : static void
102 6 : test_basic(int size)
103 : {
104 6 : binaryheap *heap = binaryheap_allocate(size, int_cmp, NULL);
105 6 : int *permutation = get_permutation(size);
106 :
107 6 : if (!binaryheap_empty(heap))
108 0 : elog(ERROR, "new heap not empty");
109 6 : if (binaryheap_size(heap) != 0)
110 0 : elog(ERROR, "wrong size for new heap");
111 :
112 1122 : for (int i = 0; i < size; i++)
113 : {
114 1116 : binaryheap_add(heap, Int32GetDatum(permutation[i]));
115 1116 : verify_heap_property(heap);
116 : }
117 :
118 6 : if (binaryheap_empty(heap))
119 0 : elog(ERROR, "heap empty after adding values");
120 6 : if (binaryheap_size(heap) != size)
121 0 : elog(ERROR, "wrong size for heap after adding values");
122 :
123 6 : if (DatumGetInt32(binaryheap_first(heap)) != get_max_from_heap(heap))
124 0 : elog(ERROR, "incorrect root node after adding values");
125 :
126 1122 : for (int i = 0; i < size; i++)
127 : {
128 1116 : int expected = get_max_from_heap(heap);
129 1116 : int actual = DatumGetInt32(binaryheap_remove_first(heap));
130 :
131 1116 : if (actual != expected)
132 0 : elog(ERROR, "incorrect root node after removing root");
133 1116 : verify_heap_property(heap);
134 : }
135 :
136 6 : if (!binaryheap_empty(heap))
137 0 : elog(ERROR, "heap not empty after removing all nodes");
138 6 : }
139 :
140 : /*
141 : * Test building heap after unordered additions.
142 : */
143 : static void
144 6 : test_build(int size)
145 : {
146 6 : binaryheap *heap = binaryheap_allocate(size, int_cmp, NULL);
147 6 : int *permutation = get_permutation(size);
148 :
149 1122 : for (int i = 0; i < size; i++)
150 1116 : binaryheap_add_unordered(heap, Int32GetDatum(permutation[i]));
151 :
152 6 : if (binaryheap_size(heap) != size)
153 0 : elog(ERROR, "wrong size for heap after unordered additions");
154 :
155 6 : binaryheap_build(heap);
156 6 : verify_heap_property(heap);
157 6 : }
158 :
159 : /*
160 : * Test removing nodes.
161 : */
162 : static void
163 6 : test_remove_node(int size)
164 : {
165 6 : binaryheap *heap = binaryheap_allocate(size, int_cmp, NULL);
166 6 : int *permutation = get_permutation(size);
167 12 : int remove_count = pg_prng_uint64_range(&pg_global_prng_state,
168 6 : 0, size - 1);
169 :
170 1122 : for (int i = 0; i < size; i++)
171 1116 : binaryheap_add(heap, Int32GetDatum(permutation[i]));
172 :
173 706 : for (int i = 0; i < remove_count; i++)
174 : {
175 1400 : int idx = pg_prng_uint64_range(&pg_global_prng_state,
176 700 : 0, binaryheap_size(heap) - 1);
177 :
178 700 : binaryheap_remove_node(heap, idx);
179 700 : verify_heap_property(heap);
180 : }
181 :
182 6 : if (binaryheap_size(heap) != size - remove_count)
183 0 : elog(ERROR, "wrong size after removing nodes");
184 6 : }
185 :
186 : /*
187 : * Test replacing the root node.
188 : */
189 : static void
190 6 : test_replace_first(int size)
191 : {
192 6 : binaryheap *heap = binaryheap_allocate(size, int_cmp, NULL);
193 :
194 1122 : for (int i = 0; i < size; i++)
195 1116 : binaryheap_add(heap, Int32GetDatum(i));
196 :
197 : /*
198 : * Replace root with a value smaller than everything in the heap.
199 : */
200 6 : binaryheap_replace_first(heap, Int32GetDatum(-1));
201 6 : verify_heap_property(heap);
202 :
203 : /*
204 : * Replace root with a value in the middle of the heap.
205 : */
206 6 : binaryheap_replace_first(heap, Int32GetDatum(size / 2));
207 6 : verify_heap_property(heap);
208 :
209 : /*
210 : * Replace root with a larger value than everything in the heap.
211 : */
212 6 : binaryheap_replace_first(heap, Int32GetDatum(size + 1));
213 6 : verify_heap_property(heap);
214 6 : }
215 :
216 : /*
217 : * Test duplicate values.
218 : */
219 : static void
220 6 : test_duplicates(int size)
221 : {
222 6 : binaryheap *heap = binaryheap_allocate(size, int_cmp, NULL);
223 6 : int dup = pg_prng_uint64_range(&pg_global_prng_state, 0, size - 1);
224 :
225 1122 : for (int i = 0; i < size; i++)
226 1116 : binaryheap_add(heap, Int32GetDatum(dup));
227 :
228 1122 : for (int i = 0; i < size; i++)
229 : {
230 1116 : if (DatumGetInt32(binaryheap_remove_first(heap)) != dup)
231 0 : elog(ERROR, "unexpected value in heap with duplicates");
232 : }
233 6 : }
234 :
235 : /*
236 : * Test resetting.
237 : */
238 : static void
239 6 : test_reset(int size)
240 : {
241 6 : binaryheap *heap = binaryheap_allocate(size, int_cmp, NULL);
242 :
243 1122 : for (int i = 0; i < size; i++)
244 1116 : binaryheap_add(heap, Int32GetDatum(i));
245 :
246 6 : binaryheap_reset(heap);
247 :
248 6 : if (!binaryheap_empty(heap))
249 0 : elog(ERROR, "heap not empty after resetting");
250 6 : }
251 :
252 : /*
253 : * SQL-callable entry point to perform all tests.
254 : */
255 2 : PG_FUNCTION_INFO_V1(test_binaryheap);
256 :
257 : Datum
258 1 : test_binaryheap(PG_FUNCTION_ARGS)
259 : {
260 : static const int test_sizes[] = {1, 2, 3, 10, 100, 1000};
261 :
262 7 : for (int i = 0; i < sizeof(test_sizes) / sizeof(int); i++)
263 : {
264 6 : int size = test_sizes[i];
265 :
266 6 : test_basic(size);
267 6 : test_build(size);
268 6 : test_remove_node(size);
269 6 : test_replace_first(size);
270 6 : test_duplicates(size);
271 6 : test_reset(size);
272 : }
273 :
274 1 : PG_RETURN_VOID();
275 : }
|
