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, 11 insertions, 3 deletions

diff --git a/py/pairheap.c b/py/pairheap.c
index a1eececa0..d3a011c4a 100644
--- a/py/pairheap.c
+++ b/py/pairheap.c
@@ -72,9 +72,11 @@ mp_pairheap_t *mp_pairheap_pairing(mp_pairheap_lt_t lt, mp_pairheap_t *child) {
     while (!NEXT_IS_RIGHTMOST_PARENT(child)) {
         mp_pairheap_t *n1 = child;
         child = child->next;
+        n1->next = NULL;
         if (!NEXT_IS_RIGHTMOST_PARENT(child)) {
             mp_pairheap_t *n2 = child;
             child = child->next;
+            n2->next = NULL;
             n1 = mp_pairheap_meld(lt, n1, n2);
         }
         heap = mp_pairheap_meld(lt, heap, n1);
@@ -87,7 +89,9 @@ mp_pairheap_t *mp_pairheap_pairing(mp_pairheap_lt_t lt, mp_pairheap_t *child) {
 mp_pairheap_t *mp_pairheap_delete(mp_pairheap_lt_t lt, mp_pairheap_t *heap, mp_pairheap_t *node) {
     // Simple case of the top being the node to delete
     if (node == heap) {
-        return mp_pairheap_pairing(lt, heap->child);
+        mp_pairheap_t *child = heap->child;
+        node->child = NULL;
+        return mp_pairheap_pairing(lt, child);
     }
 
     // Case where node is not in the heap
@@ -113,18 +117,22 @@ mp_pairheap_t *mp_pairheap_delete(mp_pairheap_lt_t lt, mp_pairheap_t *heap, mp_p
         node->next = NULL;
         return heap;
     } else if (node == parent->child) {
+        mp_pairheap_t *child = node->child;
         next = node->next;
+        node->child = NULL;
         node->next = NULL;
-        node = mp_pairheap_pairing(lt, node->child);
+        node = mp_pairheap_pairing(lt, child);
         parent->child = node;
     } else {
         mp_pairheap_t *n = parent->child;
         while (node != n->next) {
             n = n->next;
         }
+        mp_pairheap_t *child = node->child;
         next = node->next;
+        node->child = NULL;
         node->next = NULL;
-        node = mp_pairheap_pairing(lt, node->child);
+        node = mp_pairheap_pairing(lt, child);
         if (node == NULL) {
             node = n;
         } else {