lkml.org 
[lkml]   [2009]   [Jan]   [8]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    SubjectRe: [RFC] B+Tree library V2
    From
    Date
    On Thu, 2009-01-08 at 21:02 +0100, Jörn Engel wrote:

    > > #define btree_for_each_key(head, geo, key, tmp) \
    > > for (key = btree_last(head, geo), tmp = btree_get_prev_key(head, geo, key);
    > > key; key = tmp, tmp = btree_get_prev_key(head, geo, key))
    >
    > [ Changed the function name above. It really isn't a lookup, it returns
    > a key, not a value. My fault. ]

    Right.

    > Looks correct otherwise. Probably needs a comment that without "tmp" we
    > would skip a 0 key. Or am I the only one who wants to simplify the code
    > before spotting this little subtlety?

    I, uh, I didn't even realise that. I think the code for
    btree_last/btree_get_prev_key isn't correct as is since the 0 key is
    valid, but you can't tell whether it returned 0 because it didn't find
    anything, or because there was no more entry. Or am I missing something?

    > > (and possibly some type-checking variants that hardcode the geo)
    > >
    > > Does that seem correct? And would it be possible to provide btree_last()
    > > that takes an void ** and fills it with the last entry, and the same for
    > > lookup_less(), so we can write btree_for_each_entry() too?
    >
    > Not sure what you mean. Something with the same effect as this?
    >
    > #define btree_for_each_val(head, geo, key, val) \
    > for (key = btree_last(head, geo), \
    > val = btree_lookup(head, geo, key); \
    > val; \
    > key = btree_get_prev_key(head, geo, key), \
    > val = btree_lookup(head, geo, key))

    Well, that does lots of lookups that don't seem necessary, since a
    function like btree_last should be able to return the value right away.
    Also, if it was

    #define btree_for_each_val(head, geo, key, val)
    for (val = btree_last(head, geo, &key);
    val;
    val = btree_get_prev(head, geo, &key))

    it would be more correct, I think?

    johannes
    [unhandled content-type:application/pgp-signature]
    \
     
     \ /
      Last update: 2009-01-08 21:21    [W:2.225 / U:0.016 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site