PostgreSQL Source Code: src/common/binaryheap.c Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
13
14#ifdef FRONTEND
16#else
18#endif
19
20#include <math.h>
21
22#ifdef FRONTEND
24#endif
26
29
30
31
32
33
34
35
36
37
40{
41 int sz;
43
49
52
53 return heap;
54}
55
56
57
58
59
60
61
62void
64{
67}
68
69
70
71
72
73
74void
76{
78}
79
80
81
82
83
84
85
86
87
88
89static inline int
91{
92 return 2 * i + 1;
93}
94
95static inline int
97{
98 return 2 * i + 2;
99}
100
101static inline int
103{
104 return (i - 1) / 2;
105}
106
107
108
109
110
111
112
113
114
115void
117{
119 {
120#ifdef FRONTEND
121 pg_fatal("out of binary heap slots");
122#else
123 elog(ERROR, "out of binary heap slots");
124#endif
125 }
129}
130
131
132
133
134
135
136
137void
139{
140 int i;
141
145}
146
147
148
149
150
151
152
153void
155{
157 {
158#ifdef FRONTEND
159 pg_fatal("out of binary heap slots");
160#else
161 elog(ERROR, "out of binary heap slots");
162#endif
163 }
167}
168
169
170
171
172
173
174
175
178{
181}
182
183
184
185
186
187
188
189
190
193{
195
197
198
200
201
203 {
205 return result;
206 }
207
208
209
210
211
214
215 return result;
216}
217
218
219
220
221
222
223
224void
226{
228
230 Assert(n >= 0 && n < heap->bh_size);
231
232
236
237
239
240
241 if (cmp > 0)
243 else if (cmp < 0)
245}
246
247
248
249
250
251
252
253
254void
256{
258
260
263}
264
265
266
267
268
269static void
271{
273
274
275
276
277
278
279 while (node_off != 0)
280 {
282 int parent_off;
284
285
286
287
288
290 parent_val = heap->bh_nodes[parent_off];
292 parent_val,
294 if (cmp <= 0)
295 break;
296
297
298
299
300
301 heap->bh_nodes[node_off] = parent_val;
302 node_off = parent_off;
303 }
304
305 heap->bh_nodes[node_off] = node_val;
306}
307
308
309
310
311
312static void
314{
316
317
318
319
320
321
322 while (true)
323 {
326 int swap_off = left_off;
327
328
329 if (right_off < heap->bh_size &&
333 swap_off = right_off;
334
335
336
337
338
339 if (left_off >= heap->bh_size ||
343 break;
344
345
346
347
348
350 node_off = swap_off;
351 }
352
353 heap->bh_nodes[node_off] = node_val;
354}
void binaryheap_remove_node(binaryheap *heap, int n)
void binaryheap_build(binaryheap *heap)
void binaryheap_replace_first(binaryheap *heap, bh_node_type d)
void binaryheap_reset(binaryheap *heap)
bh_node_type binaryheap_first(binaryheap *heap)
void binaryheap_add(binaryheap *heap, bh_node_type d)
bh_node_type binaryheap_remove_first(binaryheap *heap)
static void sift_down(binaryheap *heap, int node_off)
static int parent_offset(int i)
static void sift_up(binaryheap *heap, int node_off)
static int right_offset(int i)
static int left_offset(int i)
void binaryheap_free(binaryheap *heap)
void binaryheap_add_unordered(binaryheap *heap, bh_node_type d)
binaryheap * binaryheap_allocate(int capacity, binaryheap_comparator compare, void *arg)
#define binaryheap_empty(h)
int(* binaryheap_comparator)(bh_node_type a, bh_node_type b, void *arg)
static int compare(const void *arg1, const void *arg2)
Assert(PointerIsAligned(start, uint64))
void pfree(void *pointer)
static int cmp(const chr *x, const chr *y, size_t len)
bool bh_has_heap_property
binaryheap_comparator bh_compare
bh_node_type bh_nodes[FLEXIBLE_ARRAY_MEMBER]