[Olsr-dev] Improving AVL insert function

[Diogo Gonçalves]

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.

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.

Best regards.

[1] https://github.com/diogomg/olsrd2
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.olsr.org/pipermail/olsr-dev/attachments/20160302/a15337a9/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: run_dijkstra_core_graph.pdf
Type: application/pdf
Size: 5011 bytes
Desc: not available
URL: <http://lists.olsr.org/pipermail/olsr-dev/attachments/20160302/a15337a9/attachment.pdf>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: avl_avl_opt_core_graph.pdf
Type: application/pdf
Size: 5616 bytes
Desc: not available
URL: <http://lists.olsr.org/pipermail/olsr-dev/attachments/20160302/a15337a9/attachment-0001.pdf>