Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit931bf3e

Browse files
committed
Fix a bug in pairing heap removal code.
After removal, the next_sibling pointer of a node was sometimes incorrectlyleft to point to another node in the heap, which meant that a node wassometimes linked twice into the heap. Surprisingly that didn't cause anycrashes in my testing, but it was clearly wrong and could easily segfaultin other scenarios.Also always keep the prev_or_parent pointer as NULL on the root node. Thatwas not a correctness issue AFAICS, but let's be tidy.Add a debugging function, to dump the contents of a pairing heap as astring. It's #ifdef'd out, as it's not used for anything in any normalcode, but it was highly useful in debugging this. Let's keep it handy forfurther reference.
1 parentd17b6df commit931bf3e

File tree

2 files changed

+70
-0
lines changed

2 files changed

+70
-0
lines changed

‎src/backend/lib/pairingheap.c

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -70,6 +70,10 @@ pairingheap_free(pairingheap *heap)
7070
*
7171
* The subheap with smaller value is put as a child of the other one (assuming
7272
* a max-heap).
73+
*
74+
* The next_sibling and prev_or_parent pointers of the input nodes are
75+
* ignored. On return, the returned node's next_sibling and prev_or_parent
76+
* pointers are garbage.
7377
*/
7478
staticpairingheap_node*
7579
merge(pairingheap*heap,pairingheap_node*a,pairingheap_node*b)
@@ -111,6 +115,8 @@ pairingheap_add(pairingheap *heap, pairingheap_node *node)
111115

112116
/* Link the new node as a new tree */
113117
heap->ph_root=merge(heap,heap->ph_root,node);
118+
heap->ph_root->prev_or_parent=NULL;
119+
heap->ph_root->next_sibling=NULL;
114120
}
115121

116122
/*
@@ -148,6 +154,11 @@ pairingheap_remove_first(pairingheap *heap)
148154
children=result->first_child;
149155

150156
heap->ph_root=merge_children(heap,children);
157+
if (heap->ph_root)
158+
{
159+
heap->ph_root->prev_or_parent=NULL;
160+
heap->ph_root->next_sibling=NULL;
161+
}
151162

152163
returnresult;
153164
}
@@ -272,3 +283,51 @@ merge_children(pairingheap *heap, pairingheap_node *children)
272283

273284
returnnewroot;
274285
}
286+
287+
/*
288+
* A debug function to dump the contents of the heap as a string.
289+
*
290+
* The 'dumpfunc' callback appends a string representation of a single node
291+
* to the StringInfo. 'opaque' can be used to pass more information to the
292+
* callback.
293+
*/
294+
#ifdefPAIRINGHEAP_DEBUG
295+
staticvoid
296+
pairingheap_dump_recurse(StringInfobuf,
297+
pairingheap_node*node,
298+
void (*dumpfunc) (pairingheap_node*node,StringInfobuf,void*opaque),
299+
void*opaque,
300+
intdepth,
301+
pairingheap_node*prev_or_parent)
302+
{
303+
while (node)
304+
{
305+
Assert(node->prev_or_parent==prev_or_parent);
306+
307+
appendStringInfoSpaces(buf,depth*4);
308+
dumpfunc(node,buf,opaque);
309+
appendStringInfoString(buf,"\n");
310+
if (node->first_child)
311+
pairingheap_dump_recurse(buf,node->first_child,dumpfunc,opaque,depth+1,node);
312+
prev_or_parent=node;
313+
node=node->next_sibling;
314+
}
315+
}
316+
317+
char*
318+
pairingheap_dump(pairingheap*heap,
319+
void (*dumpfunc) (pairingheap_node*node,StringInfobuf,void*opaque),
320+
void*opaque)
321+
{
322+
StringInfoDatabuf;
323+
324+
if (!heap->ph_root)
325+
returnpstrdup("(empty)");
326+
327+
initStringInfo(&buf);
328+
329+
pairingheap_dump_recurse(&buf,heap->ph_root,dumpfunc,opaque,0,NULL);
330+
331+
returnbuf.data;
332+
}
333+
#endif

‎src/include/lib/pairingheap.h

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -11,6 +11,11 @@
1111
#ifndefPAIRINGHEAP_H
1212
#definePAIRINGHEAP_H
1313

14+
#include"lib/stringinfo.h"
15+
16+
/* Enable if you need the pairingheap_dump() debug function */
17+
/* #define PAIRINGHEAP_DEBUG */
18+
1419
/*
1520
* This represents an element stored in the heap. Embed this in a larger
1621
* struct containing the actual data you're storing.
@@ -78,6 +83,12 @@ extern pairingheap_node *pairingheap_first(pairingheap *heap);
7883
externpairingheap_node*pairingheap_remove_first(pairingheap*heap);
7984
externvoidpairingheap_remove(pairingheap*heap,pairingheap_node*node);
8085

86+
#ifdefPAIRINGHEAP_DEBUG
87+
externchar*pairingheap_dump(pairingheap*heap,
88+
void (*dumpfunc) (pairingheap_node*node,StringInfobuf,void*opaque),
89+
void*opaque);
90+
#endif
91+
8192
/* Resets the heap to be empty. */
8293
#definepairingheap_reset(h)((h)->ph_root = NULL)
8394

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp