[Olsr-dev] Improving SPF with binary heaps
Ferry Huberts
(spam-protected)
Thu Aug 20 12:31:54 CEST 2015
No hurries, I'll be offline for 5 week, starting next Sunday.
On 20/08/15 11:24, Henning Rogge wrote:
> Hi,
>
> any status update on your work?
>
> We are still waiting for the initial merge of your code into the new branch.
>
> Henning Rogge
>
>
> On Mon, Aug 3, 2015 at 12:25 PM, Ferry Huberts <(spam-protected)
> <mailto:(spam-protected)>> wrote:
>
> Ok.
>
> There now is a branch 'dijkstra-binary-heap' on the olsrd repo.
>
> The setting in the configuration file is 'DijkstraBinaryHeap', which
> adjusts the setting 'olsr_cnf->dijkstra_binary_heap' (which is false
> by default).
>
> Please follow the plan and when done, notify us.
>
> And I still want to see performance numbers to justify pulling in
> these changes to the core of olsrd.
>
>
> Ferry
>
> On 01/08/15 01:52, Diogo Gonçalves wrote:
>
> 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)
> <mailto:(spam-protected)>
> <mailto:(spam-protected) <mailto:(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)>
> <mailto:(spam-protected) <mailto:(spam-protected)>>
> <mailto:(spam-protected) <mailto:(spam-protected)>
> <mailto:(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)>
> <mailto:(spam-protected)
> <mailto:(spam-protected)>>
> <mailto:(spam-protected)
> <mailto:(spam-protected)>
> <mailto:(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)>
> <mailto:(spam-protected) <mailto:(spam-protected)>>
> <mailto:(spam-protected) <mailto:(spam-protected)>
> <mailto:(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> <http://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)>
> <mailto:(spam-protected) <mailto:(spam-protected)>>
> <mailto:(spam-protected) <mailto:(spam-protected)>
> <mailto:(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)>
> <mailto:(spam-protected)
> <mailto:(spam-protected)>>
> <mailto:(spam-protected)
> <mailto:(spam-protected)>
> <mailto:(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)>
> <mailto:(spam-protected) <mailto:(spam-protected)>>
> <mailto:(spam-protected) <mailto:(spam-protected)>
> <mailto:(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)> <mailto:(spam-protected)
> <mailto:(spam-protected)>>
> <mailto:(spam-protected)
> <mailto:(spam-protected)> <mailto:(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)>
> <mailto:(spam-protected) <mailto:(spam-protected)>>
> <mailto:(spam-protected) <mailto:(spam-protected)>
> <mailto:(spam-protected) <mailto:(spam-protected)>>>> wrote:
> >> >>> >>
> >> >>> >> On Mon, Jul 13, 2015 at 6:01 PM, Saulo
> Queiroz
> >> >>> >> <(spam-protected)
> <mailto:(spam-protected)>
> <mailto:(spam-protected)
> <mailto:(spam-protected)>> <mailto:(spam-protected)
> <mailto:(spam-protected)>
> <mailto:(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
>
>
>
> --
> Ferry Huberts
>
>
>
>
--
Ferry Huberts
More information about the Olsr-dev
mailing list