Hi Jan,
>> Let's say that slot[0] of the current leaf (A) has key=10. And let's
>> say that its parent node (N) has key=5 (and not 10). Let's say we have
>> a previous leaf (B), whose last slot has key=2.
>> If such tree is valid, then: btrfs_prev_leaf() will search for key==9.
>> Then btrfs_search_slot() would bring us node N and leaf A again,
>> wouldn't it? Because key(N)<=9. So we will receive leaf A back, and
>> will think that there is no previous leaf, while there is.
>> What am I missing here?
>
> It wouldn't. btrfs_search_slot always sets up the path such that it
> points to the position where such an key would be inserted. And we never
> insert at the beginning of a leaf. So in your example, this would be at
> the end of leaf B: your path object will have nodes[1] = N, nodes[0] = B
> and slots[0] = number_of_slots_used_in_B + 1.
I have re-looked at btrfs_search_slot, and don't see how it would end
up in leaf B. The bin_search() function will clearly return the slot
*after* the slot of N that has key==5 (which is the parent slot of A).
So then the following code:
if (level != 0) {
int dec = 0;
if (ret && slot > 0) {
dec = 1;
slot -= 1;
}
will bring us back into the slot of N with key=5. And we will go to
leaf A. While if key(N) of that slot was 10, we would never have ended
up in that slot, unless there is no lesser key in the tree. Actually,
it looks like "no lesser key" is the only case when we can get ret==1
and slot==0. Except perhaps an empty leaf, which I am not sure can
happen.
But I may be way off here, as my understanding is still pretty limited.
Thanks!
Alex.
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
