[Olsr-dev] Improving SPF with binary heaps
Diogo Gonçalves
(spam-protected)
Sat Aug 1 01:52:09 CEST 2015
Hi,
Thanks for trusting in my work.
This plan is fine to me, I will work on it. I just suggest to rename the
configuration setting 'dijkstraHeapBinary' to 'dijkstraBinaryHeap'.
Diogo.
2015-07-31 7:43 GMT-03:00 Ferry Huberts <(spam-protected)>:
> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.olsr.org/pipermail/olsr-dev/attachments/20150731/ec132312/attachment.html>
More information about the Olsr-dev
mailing list