[patch] libiberty/fibheap: bug when deleting nodes

[Michael Matz <matz at suse dot de>]

Hi,

this is a mean one.  For implementing node deletion in fibonacci heaps we 
reuse extract_min, which makes sense.  For this we have to be able to 
force the to-be-deleted node to be the new minimum.  
fibheap_replace_key_data goes to some length to ensure that this happens 
(including comments about this speciality), but those attempts sometimes 
fail because there's an early-out.  So the wrong node is deleted and 
further downhill we become very confused in hard to analyse ways.

It specifically happens when some other nodes have LONG_MIN as key, which 
is completely okay.  But this value is used also as marker for enforcing 
the minimum and hence sometimes needs to be special cased.  We could also 
solve this by artificially limiting the allowable set of priorities, but 
that would be harder for the callers, and isn't actually necessary if we 
don't do that early out in some cases.

Martin: this will fix your segfault with pretty-ipa on tramp3d.  I was 
too optimistic when saying that it probably isn't fibheap.c  :-)

I also added an assert to ensure this doesn't happen again.  It seems the 
libiberty style of asserts is a fprintf/abort pair, so that's what I used.

Regstrapping on x86_64-linux in progress.  Okay if that works?


Ciao,
Michael.
-- 
	* fibheap.c (fibheap_replace_key_data): Make sure we don't early
	out when forcing the minimum.
	(fibheap_delete_node): Assert that we managed to force the minimum.

Index: fibheap.c
===================================================================
--- fibheap.c	(Revision 147931)
+++ fibheap.c	(Arbeitskopie)
@@ -214,7 +214,10 @@ fibheap_replace_key_data (fibheap_t heap
   node->key = key;
   y = node->parent;
 
-  if (okey == key)
+  /* Short-circuit if the key is the same, as we then don't have to
+     do anything.  Except if we're trying to force the new node to
+     be the new minimum for delete.  */
+  if (okey == key && okey != FIBHEAPKEY_MIN)
     return odata;
 
   /* These two compares are specifically <= 0 to make sure that in the case
@@ -256,6 +259,11 @@ fibheap_delete_node (fibheap_t heap, fib
 
   /* To perform delete, we just make it the min key, and extract.  */
   fibheap_replace_key (heap, node, FIBHEAPKEY_MIN);
+  if (node != heap->min)
+    {
+      fprintf (stderr, "Can't force minimum on fibheap.\n");
+      abort ();
+    }
   fibheap_extract_min (heap);
 
   return ret;