diff options
| author | Paul Jakma <paul.jakma@sun.com> | 2007-08-06 18:52:45 +0000 |
|---|---|---|
| committer | Paul Jakma <paul.jakma@sun.com> | 2007-08-06 18:52:45 +0000 |
| commit | 7591d8b862439dfae8b4b16d148ce567b6ff8cb7 (patch) | |
| tree | b9d24293663be04e4c80bcd78f8d1f5e86c2c3f1 | |
| parent | fc787e873dff0091069742b34fb3631ac529c92a (diff) | |
| download | quagga-7591d8b862439dfae8b4b16d148ce567b6ff8cb7.tar.bz2 quagga-7591d8b862439dfae8b4b16d148ce567b6ff8cb7.tar.xz | |
[ospfd] Fix bad SPF calculation on some topologies - incorrect sorting
2007-08-07 Atis Elsts <atis@mikrotik.com>
* 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
| -rw-r--r-- | lib/ChangeLog | 4 | ||||
| -rw-r--r-- | lib/pqueue.c | 2 | ||||
| -rw-r--r-- | lib/pqueue.h | 1 | ||||
| -rw-r--r-- | ospfd/ChangeLog | 6 | ||||
| -rw-r--r-- | ospfd/ospf_spf.c | 9 |
5 files changed, 18 insertions, 4 deletions
diff --git a/lib/ChangeLog b/lib/ChangeLog index 41689d03..ee329114 100644 --- a/lib/ChangeLog +++ b/lib/ChangeLog @@ -1,3 +1,7 @@ +2007-07-06 Atis Elsts <atis@mikrotik.com> + + * pqueue.{c,h}: Export trickle_up + 2007-07-26 Paul Jakma <paul.jakma@sun.com> * log.c: (mes_lookup) warning about code not being in same-number diff --git a/lib/pqueue.c b/lib/pqueue.c index a974a49e..12a779f2 100644 --- a/lib/pqueue.c +++ b/lib/pqueue.c @@ -42,7 +42,7 @@ Boston, MA 02111-1307, USA. */ #define RIGHT_OF(x) (2 * x + 2) #define HAVE_CHILD(x,q) (x < (q)->size / 2) -static void +void trickle_up (int index, struct pqueue *queue) { void *tmp; diff --git a/lib/pqueue.h b/lib/pqueue.h index 1f3201b9..be37f98d 100644 --- a/lib/pqueue.h +++ b/lib/pqueue.h @@ -40,5 +40,6 @@ extern void pqueue_enqueue (void *data, struct pqueue *queue); extern void *pqueue_dequeue (struct pqueue *queue); extern void trickle_down (int index, struct pqueue *queue); +extern void trickle_up (int index, struct pqueue *queue); #endif /* _ZEBRA_PQUEUE_H */ diff --git a/ospfd/ChangeLog b/ospfd/ChangeLog index bb0e9083..422208e8 100644 --- a/ospfd/ChangeLog +++ b/ospfd/ChangeLog @@ -1,3 +1,9 @@ +2007-08-07 Atis Elsts <atis@mikrotik.com> + + * ospf_spf.c: (ospf_spf_next) Sort heap in correct direction + after vertex cost is changed, thus fixing incorrect SPF + calculation on certain topologies. + 2007-08-06 Paul Jakma <paul.jakma@sun.com> * ospf_lsa.c: (router_lsa_flags) Bug #331, NSSA regression caused 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 */ |