Fix a bug in pairing heap removal code.

hlinnaka · hlinnaka · commit 931bf3eb9b20 · 2015-02-17T22:55:53.000+02:00
After removal, the next_sibling pointer of a node was sometimes incorrectly
left to point to another node in the heap, which meant that a node was
sometimes linked twice into the heap. Surprisingly that didn't cause any
crashes in my testing, but it was clearly wrong and could easily segfault
in other scenarios.

Also always keep the prev_or_parent pointer as NULL on the root node. That
was not a correctness issue AFAICS, but let's be tidy.

Add a debugging function, to dump the contents of a pairing heap as a
string. It's #ifdef'd out, as it's not used for anything in any normal
code, but it was highly useful in debugging this. Let's keep it handy for
further reference.
diff --git a/src/backend/lib/pairingheap.c b/src/backend/lib/pairingheap.c
@@ -70,6 +70,10 @@ pairingheap_free(pairingheap *heap)
  *
  * The subheap with smaller value is put as a child of the other one (assuming
  * a max-heap).
+ *
+ * The next_sibling and prev_or_parent pointers of the input nodes are
+ * ignored. On return, the returned node's next_sibling and prev_or_parent
+ * pointers are garbage.
  */
 static pairingheap_node *
 merge(pairingheap *heap, pairingheap_node *a, pairingheap_node *b)
@@ -111,6 +115,8 @@ pairingheap_add(pairingheap *heap, pairingheap_node *node)
 
 	/* Link the new node as a new tree */
 	heap->ph_root = merge(heap, heap->ph_root, node);
+	heap->ph_root->prev_or_parent = NULL;
+	heap->ph_root->next_sibling = NULL;
 }
 
 /*
@@ -148,6 +154,11 @@ pairingheap_remove_first(pairingheap *heap)
 	children = result->first_child;
 
 	heap->ph_root = merge_children(heap, children);
+	if (heap->ph_root)
+	{
+		heap->ph_root->prev_or_parent = NULL;
+		heap->ph_root->next_sibling = NULL;
+	}
 
 	return result;
 }
@@ -272,3 +283,51 @@ merge_children(pairingheap *heap, pairingheap_node *children)
 
 	return newroot;
 }
+
+/*
+ * A debug function to dump the contents of the heap as a string.
+ *
+ * The 'dumpfunc' callback appends a string representation of a single node
+ * to the StringInfo. 'opaque' can be used to pass more information to the
+ * callback.
+ */
+#ifdef PAIRINGHEAP_DEBUG
+static void
+pairingheap_dump_recurse(StringInfo buf,
+						 pairingheap_node *node,
+						 void (*dumpfunc) (pairingheap_node *node, StringInfo buf, void *opaque),
+						 void *opaque,
+						 int depth,
+						 pairingheap_node *prev_or_parent)
+{
+	while (node)
+	{
+		Assert(node->prev_or_parent == prev_or_parent);
+
+		appendStringInfoSpaces(buf, depth * 4);
+		dumpfunc(node, buf, opaque);
+		appendStringInfoString(buf, "\n");
+		if (node->first_child)
+			pairingheap_dump_recurse(buf, node->first_child, dumpfunc, opaque, depth + 1, node);
+		prev_or_parent = node;
+		node = node->next_sibling;
+	}
+}
+
+char *
+pairingheap_dump(pairingheap *heap,
+				 void (*dumpfunc) (pairingheap_node *node, StringInfo buf, void *opaque),
+				 void *opaque)
+{
+	StringInfoData buf;
+
+	if (!heap->ph_root)
+		return pstrdup("(empty)");
+
+	initStringInfo(&buf);
+
+	pairingheap_dump_recurse(&buf, heap->ph_root, dumpfunc, opaque, 0, NULL);
+
+	return buf.data;
+}
+#endif
diff --git a/src/include/lib/pairingheap.h b/src/include/lib/pairingheap.h
@@ -11,6 +11,11 @@
 #ifndef PAIRINGHEAP_H
 #define PAIRINGHEAP_H
 
+#include "lib/stringinfo.h"
+
+/* Enable if you need the pairingheap_dump() debug function */
+/* #define PAIRINGHEAP_DEBUG */
+
 /*
  * This represents an element stored in the heap. Embed this in a larger
  * struct containing the actual data you're storing.
@@ -78,6 +83,12 @@ extern pairingheap_node *pairingheap_first(pairingheap *heap);
 extern pairingheap_node *pairingheap_remove_first(pairingheap *heap);
 extern void pairingheap_remove(pairingheap *heap, pairingheap_node *node);
 
+#ifdef PAIRINGHEAP_DEBUG
+extern char *pairingheap_dump(pairingheap *heap,
+							  void (*dumpfunc) (pairingheap_node *node, StringInfo buf, void *opaque),
+							  void *opaque);
+#endif
+
 /* Resets the heap to be empty. */
 #define pairingheap_reset(h)			((h)->ph_root = NULL)
 
