[Olsr-dev] [PATCH] fix hash handling for IP{v4,v6}

[Hannes Gredler]

On Tue, May 06, 2008 at 09:30:01AM +0200, Hagen Paul Pfeifer wrote:
| > in fact we have converted most data structures to use AVL trees rather
| > than hashed lookups.
| 
| Nice! But one question about that: are there any advantages to use AVL
| trees rather then rbtrees? I know that olsrd often remove elements from the
| trees and then the re-balancing is more time and CPU consuming as the
| rbtree.

not really, when we started olsr-ng, thomas lopatic left us a
threaded AVL implementation which we have used since then.

please find the results of a valgrind profiling run at 

  http://gredler.at/download/olsrd/callgrind.out.7305.gz
  (use the kcachegrind KDE application to visualize).

  as you may see about 20% of CPU time is spent doing
  AVL tree operations (lookup/inserteion/deletion).

if you have an idea how to further improve this,
you are welcome to contribute code :-).

/hannes