PostgreSQL Source Code: src/backend/lib/pairingheap.c Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
26
28
33
34
35
36
37
38
39
40
43{
45
49
51
52 return heap;
53}
54
55
56
57
58
59
60
61
62void
64{
66}
67
68
69
70
71
72
73
74
75
76
77
80{
81 if (a == NULL)
82 return b;
83 if (b == NULL)
84 return a;
85
86
88 {
90
91 tmp = a;
93 b = tmp;
94 }
95
96
97 if (a->first_child)
98 a->first_child->prev_or_parent = b;
100 b->next_sibling = a->first_child;
102
103 return a;
104}
105
106
107
108
109
110
111void
113{
115
116
120}
121
122
123
124
125
126
127
128
131{
133
135}
136
137
138
139
140
141
142
143
146{
149
151
152
155
158 {
161 }
162
163 return result;
164}
165
166
167
168
169void
171{
176
177
178
179
180
181 if (node == heap->ph_root)
182 {
184 return;
185 }
186
187
188
189
190
193
194
195
196
197
200 else
202 Assert(*prev_ptr == node);
203
204
205
206
207
208
209 if (children)
210 {
212
215 *prev_ptr = replacement;
216 if (next_sibling)
218 }
219 else
220 {
221 *prev_ptr = next_sibling;
222 if (next_sibling)
224 }
225}
226
227
228
229
230
231
232
235{
240
241 if (children == NULL || children->next_sibling == NULL)
242 return children;
243
244
245 next = children;
246 pairs = NULL;
247 for (;;)
248 {
250
251 if (curr == NULL)
252 break;
253
255 {
256
258 pairs = curr;
259 break;
260 }
261
263
264
265
268 pairs = curr;
269 }
270
271
272
273
274 newroot = pairs;
277 {
280
281 newroot = merge(heap, newroot, curr);
282 }
283
284 return newroot;
285}
286
287
288
289
290
291
292
293
294#ifdef PAIRINGHEAP_DEBUG
295static void
299 void *opaque,
300 int depth,
302{
303 while (node)
304 {
306
308 dumpfunc(node, buf, opaque);
311 pairingheap_dump_recurse(buf, node->first_child, dumpfunc, opaque, depth + 1, node);
312 prev_or_parent = node;
314 }
315}
316
317char *
320 void *opaque)
321{
323
325 return pstrdup("(empty)");
326
328
329 pairingheap_dump_recurse(&buf, heap->ph_root, dumpfunc, opaque, 0, NULL);
330
331 return buf.data;
332}
333#endif
static int compare(const void *arg1, const void *arg2)
Assert(PointerIsAligned(start, uint64))
char * pstrdup(const char *in)
void pfree(void *pointer)
void pairingheap_remove(pairingheap *heap, pairingheap_node *node)
void pairingheap_add(pairingheap *heap, pairingheap_node *node)
static pairingheap_node * merge(pairingheap *heap, pairingheap_node *a, pairingheap_node *b)
pairingheap * pairingheap_allocate(pairingheap_comparator compare, void *arg)
pairingheap_node * pairingheap_remove_first(pairingheap *heap)
void pairingheap_free(pairingheap *heap)
pairingheap_node * pairingheap_first(pairingheap *heap)
static pairingheap_node * merge_children(pairingheap *heap, pairingheap_node *children)
#define pairingheap_is_empty(h)
int(* pairingheap_comparator)(const pairingheap_node *a, const pairingheap_node *b, void *arg)
void appendStringInfoSpaces(StringInfo str, int count)
void appendStringInfoChar(StringInfo str, char ch)
void initStringInfo(StringInfo str)
struct pairingheap_node * next_sibling
struct pairingheap_node * prev_or_parent
struct pairingheap_node * first_child
pairingheap_comparator ph_compare
pairingheap_node * ph_root