kbtree: add kb_itr_prev and more precise kb_itr_getp

[bfredl]

It doesn't look to me like kb_itr_get is working: for instance the iterator will always store index 0 for the root node no matter what is the correct index in the root node, and the index found in the innermost traversed node (either because the key was found or an external node was reached) is never stored.

This PR implements a working version (to my testing), called kb_itr_getp, which also has the following useful behavior when the key is not found: the iterator then cannot be directly dereferenced, but kb_itr_next and kb_itr_prev (also added with this PR) will still take the iterator to the closest next or previous existing value respectively.

Also just like itr_next and itr_valid this returns nonzero when the iterator is valid (the key was found), it looks like kb_itr_get intended opposite behavior for some reason.

A simple test program to check the intended behavior: https://gist.github.com/bfredl/211dade1f913171dc0c95b195840fdfe

[justinmk]

@bfredl Can the test be added to https://github.com/attractivechaos/klib/blob/master/test/kbtree_test.c ?

[bfredl]

Not sure, that looks more like a benchmark than a unit test, though my test could be turned more benchmarklike by making sure time is not dominated by verification, either by qsort-ing the list or precomputing some random permutation of the odd numbers before starting the timing.

[stranger48]

Hi bfredl,

there's kb_itr_first() in kbtree which works perfectly. Is there a way to implement function returning end() iterator of btree?

Thanks

[bfredl]

That should be perfectly analogous to kb_itr_first, but always go down the last subnode instead of the first subnode at every level. Or use kb_itr_getp with a MAX_KEY value.

[stranger48]

thanks for a quick reponse and points. I'll try (although I'm not sure I fully understand at this stage how everything works).

[till-s]

I created an issue #141 for this bug. This PR seems to fix the kb_itr_get() bug -- in principle, that is; the newly introduced kb_itr_getp() is correct but the original kb_itr_get() is not fixed by this PR. Note also that the return value is inversed, i.e.

static inline int kb_itr_get_##name(kbtree_##name##_t *b, const key_t  k, kbitr_t *itr)
{
    return ! kb_itr_getp_##name(b, &k, itr);
}