[Olsr-dev] lsdb refactoring (2)

[Hannes Gredler]

this time with no perturbing tabs to make the results readable ;-)

--

hi olsr developers,

please find attached a patch to that consolidates
the link-state database and the spf-calculation in order
to calculate routes more efficiently.

below there are measurement results taken on a pentium mobile 1300 mhz.
   [ to get those results set SPF_PROFILING in lq_route.c ]

the results are the median of 1000 SPF runs expressed in units of
microseconds based on the funkfeuer.at topology:
   [ 202 nodes / 850 edges / 360 routes ]

total	init	run	route	kernel	cleanup
1917.00 827.00  378.00  403.00  147.00  131.00  [ olsrd.0.5.1]
  382.00   8.00  140.00  193.00   40.00    0.00  [ olsrd.0.5.3 + lsdb-refactoring-2]
-----------------------------------------------
   20%	  1%	 37%	 48%	 27%	  0%

change list:

-use the link-state (tc) database for SPF calculations rather than
  replicating the notion of vertices and edges for a SPF run.
  this heavily reduces malloc() calls and shrinks the total CPU
  load of the route calculation path between 60%-80%.

patch is at:

http://gredler.at/download/olsrd/lsdb-refactoring-2.diff.gz

asking for review, testing and inclusion into CVS.

/hannes