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