[Olsr-dev] Improving SPF with binary heaps
Sat Jul 11 08:34:00 CEST 2015
On Sat, Jul 11, 2015 at 12:43 AM, Saulo Queiroz <(spam-protected)> wrote:
> Hi Henning,
> I've supervised the work of Diogo.
> Regarding you first question, response is no. Not all procedures are used.
> Diogo just listed in .h all classical procedures of a binary heap but only
> the ones required by Dijkstra are implemented. The other are there just
> as a reminder, but he can clean .h, No problem.
I would suggest moving everything that is "internal" to a static
function... this makes it easier for new users of the API to
understand what they need because they only have to look at the header
> Regarding the second question: heap_extract_min is the procedure you asked
> Note however that the idea is to replace AVL only for Dijkstra and keeping
> AVL there for other stuff. ok?
I would like to have this as a generic API, so I am looking which
basic functions we have, we still need or we cannot get.
Basics for both lists and AVL trees in OONF (which is the base of OLSRv2) is
and a good way to iterate over the elements of the tree/list (which
would enable me to write iterator macros like the ones in
Can we have the same functions for a binary heap?
If yes, it makes sense to disallow AVL trees with overlapping keys
(which is a parameter in avl_init at the moment) and tell the
developers "use a binary heap instead for this case".
The heap (because its different than AVL) might of course have a few
more functions, like the "modify key later" functions you have. Its
just about the same "basic set".
More information about the Olsr-dev