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