[Olsr-dev] Improving AVL insert function

[Diogo Gonçalves]

Thank you :)
On Mar 2, 2016 3:03 AM, "Henning Rogge" <(spam-protected)> wrote:

> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.olsr.org/pipermail/olsr-dev/attachments/20160302/ec1e830f/attachment.html>