PostgreSQL Source Code: src/test/modules/test_binaryheap/test_binaryheap.c Source File

PostgreSQL Source Code git master
test_binaryheap.c
Go to the documentation of this file.
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 */
26static int
27 int_cmp(Datum a, Datum b, void *arg)
28{
29 return pg_cmp_s32(DatumGetInt32(a), DatumGetInt32(b));
30}
31
32/*
33 * Loops through all nodes and returns the maximum value.
34 */
35static int
36 get_max_from_heap(binaryheap *heap)
37{
38 int max = -1;
39
40 for (int i = 0; i < binaryheap_size(heap); i++)
41 max = Max(max, DatumGetInt32(binaryheap_get_node(heap, i)));
42
43 return max;
44}
45
46/*
47 * Generate a random permutation of the integers 0..size-1.
48 */
49static int *
50 get_permutation(int size)
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 (int i = 1; i < size; i++)
64 {
65 int j = 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 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 */
79static void
80 verify_heap_property(binaryheap *heap)
81{
82 for (int i = 0; i < binaryheap_size(heap); i++)
83 {
84 int left = 2 * i + 1;
85 int right = 2 * i + 2;
86 int parent_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 */
101static void
102 test_basic(int size)
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 (int i = 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 (int i = 0; i < size; i++)
127 {
128 int expected = get_max_from_heap(heap);
129 int actual = 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 */
143static void
144 test_build(int size)
145{
146 binaryheap *heap = binaryheap_allocate(size, int_cmp, NULL);
147 int *permutation = get_permutation(size);
148
149 for (int i = 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 */
162static void
163 test_remove_node(int size)
164{
165 binaryheap *heap = binaryheap_allocate(size, int_cmp, NULL);
166 int *permutation = get_permutation(size);
167 int remove_count = pg_prng_uint64_range(&pg_global_prng_state,
168 0, size - 1);
169
170 for (int i = 0; i < size; i++)
171 binaryheap_add(heap, Int32GetDatum(permutation[i]));
172
173 for (int i = 0; i < remove_count; i++)
174 {
175 int idx = 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 */
189static void
190 test_replace_first(int size)
191{
192 binaryheap *heap = binaryheap_allocate(size, int_cmp, NULL);
193
194 for (int i = 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 */
219static void
220 test_duplicates(int size)
221{
222 binaryheap *heap = binaryheap_allocate(size, int_cmp, NULL);
223 int dup = pg_prng_uint64_range(&pg_global_prng_state, 0, size - 1);
224
225 for (int i = 0; i < size; i++)
226 binaryheap_add(heap, Int32GetDatum(dup));
227
228 for (int i = 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 */
238static void
239 test_reset(int size)
240{
241 binaryheap *heap = binaryheap_allocate(size, int_cmp, NULL);
242
243 for (int i = 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
257Datum
258 test_binaryheap(PG_FUNCTION_ARGS)
259{
260 static const int test_sizes[] = {1, 2, 3, 10, 100, 1000};
261
262 for (int i = 0; i < sizeof(test_sizes) / sizeof(int); i++)
263 {
264 int size = 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}
Datum idx(PG_FUNCTION_ARGS)
Definition: _int_op.c:262
void binaryheap_remove_node(binaryheap *heap, int n)
Definition: binaryheap.c:225
void binaryheap_build(binaryheap *heap)
Definition: binaryheap.c:138
void binaryheap_replace_first(binaryheap *heap, bh_node_type d)
Definition: binaryheap.c:255
void binaryheap_reset(binaryheap *heap)
Definition: binaryheap.c:63
bh_node_type binaryheap_first(binaryheap *heap)
Definition: binaryheap.c:177
void binaryheap_add(binaryheap *heap, bh_node_type d)
Definition: binaryheap.c:154
bh_node_type binaryheap_remove_first(binaryheap *heap)
Definition: binaryheap.c:192
void binaryheap_add_unordered(binaryheap *heap, bh_node_type d)
Definition: binaryheap.c:116
binaryheap * binaryheap_allocate(int capacity, binaryheap_comparator compare, void *arg)
Definition: binaryheap.c:39
#define binaryheap_size(h)
Definition: binaryheap.h:66
#define binaryheap_empty(h)
Definition: binaryheap.h:65
#define binaryheap_get_node(h, n)
Definition: binaryheap.h:67
#define Max(x, y)
Definition: c.h:997
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:226
#define PG_RETURN_VOID()
Definition: fmgr.h:349
#define PG_FUNCTION_ARGS
Definition: fmgr.h:193
static int pg_cmp_s32(int32 a, int32 b)
Definition: int.h:646
b
int b
Definition: isn.c:74
a
int a
Definition: isn.c:73
j
int j
Definition: isn.c:78
i
int i
Definition: isn.c:77
void * palloc(Size size)
Definition: mcxt.c:1365
void * arg
uint64 pg_prng_uint64_range(pg_prng_state *state, uint64 rmin, uint64 rmax)
Definition: pg_prng.c:144
pg_prng_state pg_global_prng_state
Definition: pg_prng.c:34
uint64_t Datum
Definition: postgres.h:70
static Datum Int32GetDatum(int32 X)
Definition: postgres.h:222
static int32 DatumGetInt32(Datum X)
Definition: postgres.h:212
static int int_cmp(Datum a, Datum b, void *arg)
Datum test_binaryheap(PG_FUNCTION_ARGS)
static int * get_permutation(int size)
static void test_reset(int size)
static int get_max_from_heap(binaryheap *heap)
static void verify_heap_property(binaryheap *heap)
static void test_remove_node(int size)
PG_MODULE_MAGIC
static void test_build(int size)
static void test_duplicates(int size)
static void test_basic(int size)
static void test_replace_first(int size)
PG_FUNCTION_INFO_V1(test_binaryheap)

AltStyle によって変換されたページ (->オリジナル) /