Age Owner Branch data TLA 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 : :
51 nathan@postgresql.or 21 :GNC 1 : PG_MODULE_MAGIC;
22 : :
23 : : /*
24 : : * Test binaryheap_comparator for max-heap of integers.
25 : : */
26 : : static int
27 : 44256 : int_cmp(Datum a, Datum b, void *arg)
28 : : {
29 : 44256 : 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 : 3290 : 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 : 2589 : verify_heap_property(binaryheap *heap)
81 : : {
82 [ + + ]: 1271381 : for (int i = 0; i < binaryheap_size(heap); i++)
83 : : {
84 : 1268792 : int left = 2 * i + 1;
85 : 1268792 : int right = 2 * i + 2;
86 : 1268792 : int parent_val = DatumGetInt32(binaryheap_get_node(heap, i));
87 : :
88 [ + + - + ]: 1902542 : if (left < binaryheap_size(heap) &&
89 : 633750 : parent_val < DatumGetInt32(binaryheap_get_node(heap, left)))
51 nathan@postgresql.or 90 [ # # ]:UNC 0 : elog(ERROR, "parent node less than left child");
91 : :
51 nathan@postgresql.or 92 [ + + - + ]:GNC 1901251 : if (right < binaryheap_size(heap) &&
93 : 632459 : parent_val < DatumGetInt32(binaryheap_get_node(heap, right)))
51 nathan@postgresql.or 94 [ # # ]:UNC 0 : elog(ERROR, "parent node less than right child");
95 : : }
51 nathan@postgresql.or 96 :GNC 2589 : }
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))
51 nathan@postgresql.or 108 [ # # ]:UNC 0 : elog(ERROR, "new heap not empty");
51 nathan@postgresql.or 109 [ - + ]:GNC 6 : if (binaryheap_size(heap) != 0)
51 nathan@postgresql.or 110 [ # # ]:UNC 0 : elog(ERROR, "wrong size for new heap");
111 : :
51 nathan@postgresql.or 112 [ + + ]:GNC 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))
51 nathan@postgresql.or 119 [ # # ]:UNC 0 : elog(ERROR, "heap empty after adding values");
51 nathan@postgresql.or 120 [ - + ]:GNC 6 : if (binaryheap_size(heap) != size)
51 nathan@postgresql.or 121 [ # # ]:UNC 0 : elog(ERROR, "wrong size for heap after adding values");
122 : :
51 nathan@postgresql.or 123 [ - + ]:GNC 6 : if (DatumGetInt32(binaryheap_first(heap)) != get_max_from_heap(heap))
51 nathan@postgresql.or 124 [ # # ]:UNC 0 : elog(ERROR, "incorrect root node after adding values");
125 : :
51 nathan@postgresql.or 126 [ + + ]:GNC 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)
51 nathan@postgresql.or 132 [ # # ]:UNC 0 : elog(ERROR, "incorrect root node after removing root");
51 nathan@postgresql.or 133 :GNC 1116 : verify_heap_property(heap);
134 : : }
135 : :
136 [ - + ]: 6 : if (!binaryheap_empty(heap))
51 nathan@postgresql.or 137 [ # # ]:UNC 0 : elog(ERROR, "heap not empty after removing all nodes");
51 nathan@postgresql.or 138 :GNC 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)
51 nathan@postgresql.or 153 [ # # ]:UNC 0 : elog(ERROR, "wrong size for heap after unordered additions");
154 : :
51 nathan@postgresql.or 155 :GNC 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 [ + + ]: 339 : for (int i = 0; i < remove_count; i++)
174 : : {
175 : 666 : int idx = pg_prng_uint64_range(&pg_global_prng_state,
176 : 333 : 0, binaryheap_size(heap) - 1);
177 : :
178 : 333 : binaryheap_remove_node(heap, idx);
179 : 333 : verify_heap_property(heap);
180 : : }
181 : :
182 [ - + ]: 6 : if (binaryheap_size(heap) != size - remove_count)
51 nathan@postgresql.or 183 [ # # ]:UNC 0 : elog(ERROR, "wrong size after removing nodes");
51 nathan@postgresql.or 184 :GNC 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)
51 nathan@postgresql.or 231 [ # # ]:UNC 0 : elog(ERROR, "unexpected value in heap with duplicates");
232 : : }
51 nathan@postgresql.or 233 :GNC 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))
51 nathan@postgresql.or 249 [ # # ]:UNC 0 : elog(ERROR, "heap not empty after resetting");
51 nathan@postgresql.or 250 :GNC 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 : : }
|
