[Olsr-dev] Improving AVL insert function

[Henning Rogge]

On Wed, Mar 2, 2016 at 6:56 AM, Diogo Gonçalves
<(spam-protected)> wrote:
> Hi all,
>
> I have looked at the management of avl_insert function about its non unique
> keys. Today the function inserts the key at end of the linked list from the
> avl node with the same key, as all nodes in the list have the same key,
> there is a difference between insert at the beginning or at the end of the
> list? Why is it not inserted at the begin of the list? Insert the key at the
> beginning is cheaper.

I must admit I have no clue... the AVL functions are a direct copy
from olsrd, which were written before I joined the project. There were
so much code to rewrite that I did not dive into the AVL one.

GOOD catch!

( I hope my dijkstra implementation was not too difficult to read )

> The second point is that when key to be inserted is a unique key in the
> tree, the function finds the last node of it parent node's linked list. It
> is not necessary when the key is inserted in the left of the node.

> I did some changes in the avl_insert function that try to optimize these
> points[1]. The graphs (attached) show the improvement of performance in
> _insert_into_working_tree function and the its results in
> _handle_working_queue and _run_dijkstra functions.

The performance analysis looks VERY good...

if the avl_test runs through I would like you to merge your code into
the master branch.

Henning Rogge