On Fri, Aug 05, 2016 at 01:41:20PM +0100, Luis de Bethencourt wrote:
> befs_btree_find(), the only caller of befs_find_key(), only cares about if
> the return from that function is BEFS_BT_MATCH or not. It never uses the
> partial match given with BEFS_BT_MATCH. Removing that return and don't set
> the value that will go unused.
>
> Signed-off-by: Luis de Bethencourt <lui...@osg.samsung.com>
> ---
> v2: fix overflow != not found
> keep a value for the while(!leafnode()) loop to find a leaf node and exit
>
>
> Hi,
>
> This is a correction. Now I understand the difference between returning
> NOT_FOUND when the key is in a full node and we have to look in the overflow.
> Compared to NOT_FOUND when the key doesn't exist.
>
> For the former, we can set the key value to 0 and that means check the
> overflow.
>
> For the latter, we need to return an existing value, even if not correct, so
> the while loop [while (!befs_leafnode(this_node))] can find a leaf, exit and
> then see it is not the correct node in the call of befs_find_next() right
> after
> the loop body.
>
> This makes the code more readable than a mysterious "partial match" that
> actually means no match.
>
> There is still an issue with the comparison of the strings in the binary
> search. About to start looking into that but wanted to send this corrected
> patch first before any of you reviewed the faulty first version.
>
> Thanks,
> Luis
>
> fs/befs/befs.h | 1 -
> fs/befs/btree.c | 38 ++++++++++++++++----------------------
> 2 files changed, 16 insertions(+), 23 deletions(-)
>
> diff --git a/fs/befs/befs.h b/fs/befs/befs.h
> index c5c6cd1..faf3fac 100644
> --- a/fs/befs/befs.h
> +++ b/fs/befs/befs.h
> @@ -79,7 +79,6 @@ enum befs_err {
> BEFS_BT_END,
> BEFS_BT_EMPTY,
> BEFS_BT_MATCH,
> - BEFS_BT_PARMATCH,
> BEFS_BT_NOT_FOUND
> };
>
> diff --git a/fs/befs/btree.c b/fs/befs/btree.c
> index 3f1a391..bc7efb0 100644
> --- a/fs/befs/btree.c
> +++ b/fs/befs/btree.c
> @@ -281,9 +281,9 @@ befs_btree_find(struct super_block *sb, const
> befs_data_stream *ds,
>
> while (!befs_leafnode(this_node)) {
> res = befs_find_key(sb, this_node, key, &node_off);
> - if (res == BEFS_BT_NOT_FOUND)
> + /* if no key set, try the overflow node */
> + if (node_off == 0)
> node_off = this_node->head.overflow;
> - /* if no match, go to overflow node */
> if (befs_bt_read_node(sb, ds, this_node, node_off) != BEFS_OK) {
> befs_error(sb, "befs_btree_find() failed to read "
> "node at %llu", node_off);
> @@ -291,8 +291,7 @@ befs_btree_find(struct super_block *sb, const
> befs_data_stream *ds,
> }
> }
>
> - /* at the correct leaf node now */
> -
> + /* at a leaf node now, check if it is correct */
> res = befs_find_key(sb, this_node, key, value);
>
> brelse(this_node->bh);
> @@ -321,18 +320,13 @@ befs_btree_find(struct super_block *sb, const
> befs_data_stream *ds,
> * @sb: Filesystem superblock
> * @node: Node to find the key within
> * @findkey: Keystring to search for
> - * @value: If key is found, the value stored with the key is put here
> - *
> - * finds exact match if one exists, and returns BEFS_BT_MATCH
> - * If no exact match, finds first key in node that is greater
> - * (alphabetically) than the search key and returns BEFS_BT_PARMATCH
> - * (for partial match, I guess). Can you think of something better to
> - * call it?
> + * @value: If key is found, the value stored with the key is put here.
> + * If not, the value is returned as 0.
> *
> - * If no key was a match or greater than the search key, return
> - * BEFS_BT_NOT_FOUND.
> + * Finds exact match if one exists, and returns BEFS_BT_MATCH.
> + * If there is no exact match, it returns BEFS_BT_NOT_FOUND.
> *
> - * Use binary search instead of a linear.
> + * Uses binary search instead of a linear.
> */
> static int
> befs_find_key(struct super_block *sb, struct befs_btree_node *node,
> @@ -355,8 +349,8 @@ befs_find_key(struct super_block *sb, struct
> befs_btree_node *node,
>
> eq = befs_compare_strings(thiskey, keylen, findkey, findkey_len);
> if (eq < 0) {
> - befs_error(sb, "<--- %s %s not found", __func__, findkey);
> - befs_debug(sb, "<--- %s ERROR", __func__);
> + *value = 0;
> + befs_debug(sb, "<--- node can't contain %s", findkey);
> return BEFS_BT_NOT_FOUND;
> }
>
> @@ -385,12 +379,12 @@ befs_find_key(struct super_block *sb, struct
> befs_btree_node *node,
> else
> first = mid + 1;
> }
> - if (eq < 0)
> - *value = fs64_to_cpu(sb, valarray[mid + 1]);
> - else
> - *value = fs64_to_cpu(sb, valarray[mid]);
> - befs_debug(sb, "<--- %s found %s at %d", __func__, thiskey, mid);
> - return BEFS_BT_PARMATCH;
> +
> + /* return an existing value so caller can arrive to a leaf node */
> + *value = fs64_to_cpu(sb, valarray[mid]);
> + befs_error(sb, "<--- %s %s not found", __func__, findkey);
> + befs_debug(sb, "<--- %s ERROR", __func__);
> + return BEFS_BT_NOT_FOUND;
> }
>
> /**
> --
> 2.5.1
>
Hi,
> For the former, we can set the key value to 0 and that means check the
> overflow.
Making befs_find_tree return BEFS_BT_OVERFLOW is more readable than checking
the key value.
Nacked.
Thanx,
Salah
