NotificationsYou must be signed in to change notification settings
Fork5
Star27

Commit931bf3e

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 commit931bf3eCopy full SHA for 931bf3e

File tree

2 files changed

+70

-0

lines changed

src
- backend/lib
  - pairingheap.c
- include/lib
  - pairingheap.h

2 files changed

+70

-0

lines changed

`‎src/backend/lib/pairingheap.c‎`

Lines changed: 59 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -70,6 +70,10 @@ pairingheap_free(pairingheap *heap)`
`70`	`70`	`*`
`71`	`71`	`* The subheap with smaller value is put as a child of the other one (assuming`
`72`	`72`	`* 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.`
`73`	`77`	`*/`
`74`	`78`	`staticpairingheap_node*`
`75`	`79`	`merge(pairingheapheap,pairingheap_nodea,pairingheap_node*b)`
`@@ -111,6 +115,8 @@ pairingheap_add(pairingheap heap, pairingheap_node node)`
`111`	`115`
`112`	`116`	`/* Link the new node as a new tree */`
`113`	`117`	`heap->ph_root=merge(heap,heap->ph_root,node);`
	`118`	`+heap->ph_root->prev_or_parent=NULL;`
	`119`	`+heap->ph_root->next_sibling=NULL;`
`114`	`120`	`}`
`115`	`121`
`116`	`122`	`/*`
`@@ -148,6 +154,11 @@ pairingheap_remove_first(pairingheap *heap)`
`148`	`154`	`children=result->first_child;`
`149`	`155`
`150`	`156`	`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`	`+}`
`151`	`162`
`152`	`163`	`returnresult;`
`153`	`164`	`}`
`@@ -272,3 +283,51 @@ merge_children(pairingheap heap, pairingheap_node children)`
`272`	`283`
`273`	`284`	`returnnewroot;`
`274`	`285`	`}`
	`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_nodenode,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_nodenode,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 number	Diff line number	Diff line change
`@@ -11,6 +11,11 @@`
`11`	`11`	`#ifndefPAIRINGHEAP_H`
`12`	`12`	`#definePAIRINGHEAP_H`
`13`	`13`
	`14`	`+#include"lib/stringinfo.h"`
	`15`	`+`
	`16`	`+/* Enable if you need the pairingheap_dump() debug function */`
	`17`	`+/* #define PAIRINGHEAP_DEBUG */`
	`18`	`+`
`14`	`19`	`/*`
`15`	`20`	`* This represents an element stored in the heap. Embed this in a larger`
`16`	`21`	`* struct containing the actual data you're storing.`
`@@ -78,6 +83,12 @@ extern pairingheap_node pairingheap_first(pairingheap heap);`
`78`	`83`	`externpairingheap_nodepairingheap_remove_first(pairingheapheap);`
`79`	`84`	`externvoidpairingheap_remove(pairingheapheap,pairingheap_nodenode);`
`80`	`85`
	`86`	`+#ifdefPAIRINGHEAP_DEBUG`
	`87`	`+externcharpairingheap_dump(pairingheapheap,`
	`88`	`+void (dumpfunc) (pairingheap_nodenode,StringInfobuf,void*opaque),`
	`89`	`+void*opaque);`
	`90`	`+#endif`
	`91`	`+`
`81`	`92`	`/* Resets the heap to be empty. */`
`82`	`93`	`#definepairingheap_reset(h)((h)->ph_root = NULL)`
`83`	`94`

0 commit comments

Comments

(0)

Movatterモバイル変換

Navigation Menu

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

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Commit931bf3e

File tree

2 files changed

2 files changed

`‎src/backend/lib/pairingheap.c‎`

`‎src/include/lib/pairingheap.h‎`

0 commit comments