[Olsr-dev] Improving SPF with binary heaps

[Henning Rogge]

Just another thought about the code itself...

any reason we could not simplify the following function to something like this?

static unsigned int
heap_perfect_log2 (unsigned int number) {
    unsigned int log = 0, pow=1, original_number=number, i;
    while (number >>= 1) ++log;
    return original_number - (1 << log);
}

Henning Rogge

On Thu, Jul 30, 2015 at 2:22 PM, Henning Rogge <(spam-protected)> wrote:
> 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 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)> 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)> 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)>:
>>>>
>>>> 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)>
>>>> 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)> wrote:
>>>> >>
>>>> >> On Mon, Jul 13, 2015 at 6:01 PM, Saulo Queiroz <(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
>>>
>>>