diff options
| -rw-r--r-- | src/backend/lib/pairingheap.c | 59 | ||||
| -rw-r--r-- | src/include/lib/pairingheap.h | 11 |
2 files changed, 70 insertions, 0 deletions
diff --git a/src/backend/lib/pairingheap.c b/src/backend/lib/pairingheap.c index 213c9d3466c..17278fde6ea 100644 --- 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 index e3e320fc434..eb1856a7c10 100644 --- 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) |