Fix a bug in pairing heap removal code.
authorHeikki Linnakangas <heikki.linnakangas@iki.fi>
Tue, 17 Feb 2015 20:55:53 +0000 (22:55 +0200)
committerHeikki Linnakangas <heikki.linnakangas@iki.fi>
Tue, 17 Feb 2015 20:55:53 +0000 (22:55 +0200)
commit931bf3eb9b203ca02d729f5122a44cc250c27695
tree1f0f81da92c9a07066e8090d186c9d2b4cf163bf
parentd17b6df239e6eebf288969e931cdbe8076d1fe12
Fix a bug in pairing heap removal code.

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.
src/backend/lib/pairingheap.c
src/include/lib/pairingheap.h