From 7591d8b862439dfae8b4b16d148ce567b6ff8cb7 Mon Sep 17 00:00:00 2001 From: Paul Jakma Date: Mon, 6 Aug 2007 18:52:45 +0000 Subject: [ospfd] Fix bad SPF calculation on some topologies - incorrect sorting 2007-08-07 Atis Elsts * ospf_spf.c: (ospf_spf_next) Sort heap in correct direction after vertex cost is changed, thus fixing incorrect SPF calculation on certain topologies. * lib/pqueue.{c,h}: Export trickle_up --- ospfd/ospf_spf.c | 9 ++++++--- 1 file changed, 6 insertions(+), 3 deletions(-) (limited to 'ospfd/ospf_spf.c') diff --git a/ospfd/ospf_spf.c b/ospfd/ospf_spf.c index 51e33832..41288f1e 100644 --- a/ospfd/ospf_spf.c +++ b/ospfd/ospf_spf.c @@ -896,9 +896,12 @@ ospf_spf_next (struct vertex *v, struct ospf_area *area, * will flush the old parents */ if (ospf_nexthop_calculation (area, v, w, l, distance)) - /* Decrease the key of the node in the heap, - * re-sort the heap. */ - trickle_down (w_lsa->stat, candidate); + /* Decrease the key of the node in the heap. + * trickle-sort it up towards root, just in case this + * node should now be the new root due the cost change. + * (pqueu_{de,en}queue + */ + trickle_up (w_lsa->stat, candidate); } } /* end W is already on the candidate list */ } /* end loop over the links in V's LSA */ -- cgit v1.2.1