[Olsr-dev] Improving SPF with binary heaps

[Ferry Huberts]

On 31/07/15 12:43, Ferry Huberts wrote:
> 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 )

see https://wiki.eclipse.org/EGit/Contributor_Guide#Granularity_of_Changes

>     - 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