PostgreSQL Source Code git master
Functions | Variables
test_binaryheap.c File Reference
#include "postgres.h"
#include "common/int.h"
#include "common/pg_prng.h"
#include "fmgr.h"
#include "lib/binaryheap.h"
Include dependency graph for test_binaryheap.c:

Go to the source code of this file.

Functions

static int  int_cmp (Datum a, Datum b, void *arg)
 
static int  get_max_from_heap (binaryheap *heap)
 
static int *  get_permutation (int size)
 
static void  verify_heap_property (binaryheap *heap)
 
static void  test_basic (int size)
 
static void  test_build (int size)
 
static void  test_remove_node (int size)
 
static void  test_replace_first (int size)
 
static void  test_duplicates (int size)
 
static void  test_reset (int size)
 
  PG_FUNCTION_INFO_V1 (test_binaryheap)
 
Datum  test_binaryheap (PG_FUNCTION_ARGS)
 

Variables

  PG_MODULE_MAGIC
 

Function Documentation

◆ get_max_from_heap()

static int get_max_from_heap ( binaryheap *  heap )
static

Definition at line 36 of file test_binaryheap.c.

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}
#define binaryheap_size(h)
Definition: binaryheap.h:66
#define binaryheap_get_node(h, n)
Definition: binaryheap.h:67
#define Max(x, y)
Definition: c.h:997
i
int i
Definition: isn.c:77
static int32 DatumGetInt32(Datum X)
Definition: postgres.h:212

References binaryheap_get_node, binaryheap_size, DatumGetInt32(), i, and Max.

Referenced by test_basic().

◆ get_permutation()

static int * get_permutation ( int  size )
static

Definition at line 50 of file test_binaryheap.c.

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 {
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}
j
int j
Definition: isn.c:78
void * palloc(Size size)
Definition: mcxt.c:1365
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

References i, j, palloc(), pg_global_prng_state, and pg_prng_uint64_range().

Referenced by test_basic(), test_build(), and test_remove_node().

◆ int_cmp()

static int int_cmp ( Datum  a,
Datum  b,
void *  arg 
)
static

Definition at line 27 of file test_binaryheap.c.

28{
30}
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

References a, b, DatumGetInt32(), and pg_cmp_s32().

Referenced by test_basic(), test_build(), test_duplicates(), test_remove_node(), test_replace_first(), and test_reset().

◆ PG_FUNCTION_INFO_V1()

PG_FUNCTION_INFO_V1 ( test_binaryheap  )

◆ test_basic()

static void test_basic ( int  size )
static

Definition at line 102 of file test_binaryheap.c.

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]));
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
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");
134 }
135
136 if (!binaryheap_empty(heap))
137 elog(ERROR, "heap not empty after removing all nodes");
138}
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
binaryheap * binaryheap_allocate(int capacity, binaryheap_comparator compare, void *arg)
Definition: binaryheap.c:39
#define binaryheap_empty(h)
Definition: binaryheap.h:65
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:226
static Datum Int32GetDatum(int32 X)
Definition: postgres.h:222
static int int_cmp(Datum a, Datum b, void *arg)
static int * get_permutation(int size)
static int get_max_from_heap(binaryheap *heap)
static void verify_heap_property(binaryheap *heap)

References binaryheap_add(), binaryheap_allocate(), binaryheap_empty, binaryheap_first(), binaryheap_remove_first(), binaryheap_size, DatumGetInt32(), elog, ERROR, get_max_from_heap(), get_permutation(), i, Int32GetDatum(), int_cmp(), and verify_heap_property().

Referenced by test_binaryheap().

◆ test_binaryheap()

Datum test_binaryheap ( PG_FUNCTION_ARGS  )

Definition at line 258 of file test_binaryheap.c.

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
275}
#define PG_RETURN_VOID()
Definition: fmgr.h:349
static void test_reset(int size)
static void test_remove_node(int size)
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)

References i, PG_RETURN_VOID, test_basic(), test_build(), test_duplicates(), test_remove_node(), test_replace_first(), and test_reset().

◆ test_build()

static void test_build ( int  size )
static

Definition at line 144 of file test_binaryheap.c.

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);
157}
void binaryheap_build(binaryheap *heap)
Definition: binaryheap.c:138
void binaryheap_add_unordered(binaryheap *heap, bh_node_type d)
Definition: binaryheap.c:116

References binaryheap_add_unordered(), binaryheap_allocate(), binaryheap_build(), binaryheap_size, elog, ERROR, get_permutation(), i, Int32GetDatum(), int_cmp(), and verify_heap_property().

Referenced by test_binaryheap().

◆ test_duplicates()

static void test_duplicates ( int  size )
static

Definition at line 220 of file test_binaryheap.c.

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}

References binaryheap_add(), binaryheap_allocate(), binaryheap_remove_first(), DatumGetInt32(), elog, ERROR, i, Int32GetDatum(), int_cmp(), pg_global_prng_state, and pg_prng_uint64_range().

Referenced by test_binaryheap().

◆ test_remove_node()

static void test_remove_node ( int  size )
static

Definition at line 163 of file test_binaryheap.c.

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 {
176 0, binaryheap_size(heap) - 1);
177
180 }
181
182 if (binaryheap_size(heap) != size - remove_count)
183 elog(ERROR, "wrong size after removing nodes");
184}
Datum idx(PG_FUNCTION_ARGS)
Definition: _int_op.c:262
void binaryheap_remove_node(binaryheap *heap, int n)
Definition: binaryheap.c:225

References binaryheap_add(), binaryheap_allocate(), binaryheap_remove_node(), binaryheap_size, elog, ERROR, get_permutation(), i, idx(), Int32GetDatum(), int_cmp(), pg_global_prng_state, pg_prng_uint64_range(), and verify_heap_property().

Referenced by test_binaryheap().

◆ test_replace_first()

static void test_replace_first ( int  size )
static

Definition at line 190 of file test_binaryheap.c.

191{
192 binaryheap *heap = binaryheap_allocate(size, int_cmp, NULL);
193
194 for (int i = 0; i < size; i++)
196
197 /*
198 * Replace root with a value smaller than everything in the heap.
199 */
202
203 /*
204 * Replace root with a value in the middle of the heap.
205 */
208
209 /*
210 * Replace root with a larger value than everything in the heap.
211 */
214}
void binaryheap_replace_first(binaryheap *heap, bh_node_type d)
Definition: binaryheap.c:255

References binaryheap_add(), binaryheap_allocate(), binaryheap_replace_first(), i, Int32GetDatum(), int_cmp(), and verify_heap_property().

Referenced by test_binaryheap().

◆ test_reset()

static void test_reset ( int  size )
static

Definition at line 239 of file test_binaryheap.c.

240{
241 binaryheap *heap = binaryheap_allocate(size, int_cmp, NULL);
242
243 for (int i = 0; i < size; i++)
245
246 binaryheap_reset(heap);
247
248 if (!binaryheap_empty(heap))
249 elog(ERROR, "heap not empty after resetting");
250}
void binaryheap_reset(binaryheap *heap)
Definition: binaryheap.c:63

References binaryheap_add(), binaryheap_allocate(), binaryheap_empty, binaryheap_reset(), elog, ERROR, i, Int32GetDatum(), and int_cmp().

Referenced by test_binaryheap().

◆ verify_heap_property()

static void verify_heap_property ( binaryheap *  heap )
static

Definition at line 80 of file test_binaryheap.c.

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}

References binaryheap_get_node, binaryheap_size, DatumGetInt32(), elog, ERROR, and i.

Referenced by test_basic(), test_build(), test_remove_node(), and test_replace_first().

Variable Documentation

◆ PG_MODULE_MAGIC

PG_MODULE_MAGIC

Definition at line 21 of file test_binaryheap.c.

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