[Olsr-dev] Improving SPF with binary heaps

[Ferry Huberts]

Ok guys.

Henning and I talked about this and we're willing to merge the work.

However, don't cheer to soon because we do have a few demands that must 
be met before we actually merge it.

The plan:
1- I'll create a new branch 'dijkstra-binary-heap' next week
2- On that branch I'll put patches that create a new configuration 
setting 'dijkstraHeapBinary'.
3- You will rebase your branch on the new branch.
4- You will rework your patches such that:
    - they are reviewable (see )
    - the configuration setting 'dijkstraHeapBinary' determines whether 
the current heap code is used or your code.

If your rework is complete, we'll review it again.


How is that for a plan?
Please let us know.


Ferry & Henning

PS. Henning would like to pick up your work for olsrd v2 once complete.

On 31/07/15 08:48, Diogo Gonçalves wrote:
> ohh, you are right, thank you!
>
> If all node's pointers are NULL, the node isn't in the heap, but there
> is one special case for root node, this node doesn't point to another one.
>
> I already fixed it in the function. Thank you again.
>
> Diogo
>
> 2015-07-31 3:02 GMT-03:00 Henning Rogge <(spam-protected)
> <mailto:(spam-protected)>>:
>
>     No,
>
>     I think we are mostly fine...
>
>     Just a last question about the new "heap_is_node_added" inline... are
>     you sure about the second return command? I think it will only return
>     "true" if all three fields in the heap are NULL.
>
>     What are you trying to test, are ALL of these fields initialized
>     normally or just a few of them?
>
>     If all of them are !NULL I would suggest replacing the if() condition
>     and the both return with:
>      > return node && node->parent && node->left && node->right;
>
>     if just one of them should be !NULL, maybe this will work:
>      > return node && (node->parent || node->left || node->right);
>
>     Henning
>
>     On Fri, Jul 31, 2015 at 7:55 AM, Diogo Gonçalves
>     <(spam-protected)
>     <mailto:(spam-protected)>> wrote:
>      > Hi,
>      >
>      > I updated my binary heap lib in the olsrd [1] with some static
>     functions. Is
>      > there something else that I can do?
>      >
>      > [1]https://github.com/diogomg/olsrd
>      >
>      > 2015-07-30 9:22 GMT-03:00 Henning Rogge <(spam-protected)
>     <mailto:(spam-protected)>>:
>      >>
>      >> Hi,
>      >>
>      >> I lost a bit track of this while away at the IETF in Prague...
>      >>
>      >> Can you send a new patch with the current version of the code to the
>      >> list? I think we can clean up the rest inside the olsr.org
>     <http://olsr.org> repository.
>      >>
>      >> Is the github code still "up to date" in terms of the head.[ch]
>     code?
>      >> If yes I will give it a try to use it in the olsrd2 Dijkstra too.
>      >>
>      >> Henning Rogge
>      >>
>      >> On Tue, Jul 14, 2015 at 9:27 PM, Henning Rogge <(spam-protected)
>     <mailto:(spam-protected)>> wrote:
>      >> > Yes,
>      >> >
>      >> > that looks better... always a good idea to keep the internal
>     functions
>      >> > hidden.
>      >> >
>      >> > Henning
>      >> >
>      >> > On Tue, Jul 14, 2015 at 5:19 PM, Diogo Gonçalves
>      >> > <(spam-protected)
>     <mailto:(spam-protected)>> wrote:
>      >> >> HI,
>      >> >>
>      >> >> I cleaned up my heap.h[1], leaving only functions for the
>     users, as you
>      >> >> asked me. I hope i'm on right way but I know that there are
>      >> >> improvements to
>      >> >> do, so if you have something else to suggest you can ask me.
>      >> >>
>      >> >>
>      >> >> [1] https://github.com/diogomg/olsrd
>      >> >>
>      >> >> 2015-07-13 14:10 GMT-03:00 Henning Rogge <(spam-protected)
>     <mailto:(spam-protected)>>:
>      >> >>>
>      >> >>> Hi,
>      >> >>>
>      >> >>> since we have some people to ask when we have questions
>     about it, I
>      >> >>> think it will be good to merge.
>      >> >>>
>      >> >>> But I would also like someone of you to look after it when I
>     build it
>      >> >>> into the olsrd2 dijkstra. If you can clean up the "heap.h"
>     file so
>      >> >>> that it only contains the necessary functions for an user
>     (and not the
>      >> >>> internal ones), it should be easy to supply a few good
>     accessor macros
>      >> >>> (similar to list.h and avl.h in OONF).
>      >> >>>
>      >> >>> Henning
>      >> >>>
>      >> >>> On Mon, Jul 13, 2015 at 7:07 PM, Saulo Queiroz
>     <(spam-protected) <mailto:(spam-protected)>>
>      >> >>> wrote:
>      >> >>> > Ferry and Henning,  ok.
>      >> >>> > We have just to care about real routing metrics, like ETX
>      >> >>> > since the priority queue will be arranged based on such
>      >> >>> > real value. What you think?
>      >> >>> >
>      >> >>> >
>      >> >>> > On 13 July 2015 at 13:47, Henning Rogge <(spam-protected)
>     <mailto:(spam-protected)>> wrote:
>      >> >>> >>
>      >> >>> >> On Mon, Jul 13, 2015 at 6:01 PM, Saulo Queiroz
>      >> >>> >> <(spam-protected) <mailto:(spam-protected)>>
>      >> >>> >> wrote:
>      >> >>> >> > Yes,
>      >> >>> >> > something like 1/priority_value (for instance) might work.
>      >> >>> >>
>      >> >>> >> I thought more about (UINT32_MAX-value)
>      >> >>> >>
>      >> >>> >> Henning
>      >> >>> >
>      >> >>> >
>      >> >>> >
>      >> >>> >
>      >> >>> > --
>      >> >>> > Saulo Jorge bq
>      >> >>> > -
>      >> >>> > "In theory, there is no difference between practice and
>     theory, in
>      >> >>> > practice
>      >> >>> > there is"
>      >> >>> > -- Someone
>      >> >>
>      >> >>
>      >
>      >
>
>
>
>

-- 
Ferry Huberts