py/pairheap: Properly unlink node on pop and delete.

This fixes a bug in the pairing-heap implementation when nodes are deleted
with mp_pairheap_delete and then reinserted later on.

1 files changed, 6 insertions, 3 deletions

diff --git a/py/pairheap.h b/py/pairheap.h
index 8a9138b17..16ae78809 100644
--- a/py/pairheap.h
+++ b/py/pairheap.h
@@ -35,6 +35,7 @@
 // Algorithmica 1:111-129, 1986.
 // https://www.cs.cmu.edu/~sleator/papers/pairing-heaps.pdf
 
+#include <assert.h>
 #include "py/obj.h"
 
 // This struct forms the nodes of the heap and is intended to be extended, by
@@ -77,14 +78,16 @@ static inline mp_pairheap_t *mp_pairheap_peek(mp_pairheap_lt_t lt, mp_pairheap_t
 
 // Push new node onto existing heap.  Returns the new heap.
 static inline mp_pairheap_t *mp_pairheap_push(mp_pairheap_lt_t lt, mp_pairheap_t *heap, mp_pairheap_t *node) {
-    node->child = NULL;
-    node->next = NULL;
+    assert(node->child == NULL && node->next == NULL);
     return mp_pairheap_meld(lt, node, heap); // node is first to be stable
 }
 
 // Pop the top off the heap, which must not be empty.  Returns the new heap.
 static inline mp_pairheap_t *mp_pairheap_pop(mp_pairheap_lt_t lt, mp_pairheap_t *heap) {
-    return mp_pairheap_pairing(lt, heap->child);
+    assert(heap->next == NULL);
+    mp_pairheap_t *child = heap->child;
+    heap->child = NULL;
+    return mp_pairheap_pairing(lt, child);
 }
 
 #endif // MICROPY_INCLUDED_PY_PAIRHEAP_H