added the SPF refactoring from Hannes Gredler <hannes@gredler.at>:
authorBernd Petrovitsch <bernd@firmix.at>
Thu, 5 Jul 2007 22:43:47 +0000 (22:43 +0000)
committerBernd Petrovitsch <bernd@firmix.at>
Thu, 5 Jul 2007 22:43:47 +0000 (22:43 +0000)
commit9179fdb6f51eab214a598ca3ce381b1208e979c8
tree584e7c9393cd7c93dac450c648a158924f6e996c
parent25bbb8953e45e4cfc876544de1eb442e2e0379e5
added the SPF refactoring from Hannes Gredler <hannes@gredler.at>:

1. use of an AVL tree as a min-heap implementation

   as a means for efficient sorting.
   (the etx metric is used as the key in the candidate tree)

2. next-hop propagation

   rather than tracking the previous node in olsr_relax()
   i have changed that model and pre-populate all one-hop neighbors
   with their own IP adress as 'next-hop' and pull that
   pointer up once new paths are explored.

   as a result no walker for counting hops and extracting next-hops
   is required - it turns out at this is slighly more efficient
   than the existing behaviour (even with the cache applied).
CHANGELOG
src/lq_avl.c
src/lq_avl.h
src/lq_route.c
src/lq_route.h
src/net_olsr.c
src/olsr.c