[PATCH v2 1/2] befs: remove unused BEFS_BT_MATCH

[PATCH v2 1/2] befs: remove unused BEFS_BT_MATCH

[Luis de Bethencourt]

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 <luisbg@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

[PATCH v2 2/2] befs: fix typo in befs_find_key

[Luis de Bethencourt]

Fixing skeep to skip.

Signed-off-by: Luis de Bethencourt <luisbg@osg.samsung.com>
---
 fs/befs/btree.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/fs/befs/btree.c b/fs/befs/btree.c
index bc7efb0..784688c 100644
--- a/fs/befs/btree.c
+++ b/fs/befs/btree.c
@@ -343,7 +343,7 @@ befs_find_key(struct super_block *sb, struct befs_btree_node *node,
 
 	findkey_len = strlen(findkey);
 
-	/* if node can not contain key, just skeep this node */
+	/* if node can not contain key, just skip this node */
 	last = node->head.all_key_count - 1;
 	thiskey = befs_bt_get_key(sb, node, last, &keylen);
 
-- 
2.5.1

Re: [PATCH v2 1/2] befs: remove unused BEFS_BT_MATCH

[Salah Triki]

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 <luisbg@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

Re: [PATCH v2 2/2] befs: fix typo in befs_find_key

[Salah Triki]

On Fri, Aug 05, 2016 at 01:41:21PM +0100, Luis de Bethencourt wrote:
> Fixing skeep to skip.
> 
> Signed-off-by: Luis de Bethencourt <luisbg@osg.samsung.com>
> ---
>  fs/befs/btree.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/fs/befs/btree.c b/fs/befs/btree.c
> index bc7efb0..784688c 100644
> --- a/fs/befs/btree.c
> +++ b/fs/befs/btree.c
> @@ -343,7 +343,7 @@ befs_find_key(struct super_block *sb, struct befs_btree_node *node,
>  
>  	findkey_len = strlen(findkey);
>  
> -	/* if node can not contain key, just skeep this node */
> +	/* if node can not contain key, just skip this node */
>  	last = node->head.all_key_count - 1;
>  	thiskey = befs_bt_get_key(sb, node, last, &keylen);
>  
> -- 
> 2.5.1
> 

Ack-by: Salah Triki <salah.triki@gmail.com>

Thanx Luis :)
Salah

Re: [PATCH v2 1/2] befs: remove unused BEFS_BT_MATCH

[Luis de Bethencourt]

On 06/08/16 19:34, Salah Triki wrote:
> 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 <luisbg@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
> 

Hi,

Yeah, I agree. The ternary property of the function due to one call wanting to see if it
is overflow or not, and the second call wanting to see if it is found or not. This makes
it good to have BEFS_BT_MATCH, BEFS_BT_NOT_FOUND, and BEFS_BT_OVERFLOW as returns. Better
readability.

Will send a corrected patch soon.

Thanks for the review,
Luis

[PATCH v3 1/2] befs: remove unused BEFS_BT_PARMATCH

[Luis de Bethencourt]

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_PARMATCH. Make the overflow return clearer
by having BEFS_BT_OVERFLOW instead of BEFS_BT_PARMATCH.

Signed-off-by: Luis de Bethencourt <luisbg@osg.samsung.com>
---
v3: check for BEFS_BT_OVERFLOW instead of value == 0


Hi,

Switching to using BEFS_BT_OVERFLOW. This makes logic of befs_find_key()
clearer.

Thanks,
Luis

 fs/befs/befs.h  |  2 +-
 fs/befs/btree.c | 38 ++++++++++++++++----------------------
 2 files changed, 17 insertions(+), 23 deletions(-)

diff --git a/fs/befs/befs.h b/fs/befs/befs.h
index c5c6cd1..a8ca7fc 100644
--- a/fs/befs/befs.h
+++ b/fs/befs/befs.h
@@ -79,7 +79,7 @@ enum befs_err {
 	BEFS_BT_END,
 	BEFS_BT_EMPTY,
 	BEFS_BT_MATCH,
-	BEFS_BT_PARMATCH,
+	BEFS_BT_OVERFLOW,
 	BEFS_BT_NOT_FOUND
 };
 
diff --git a/fs/befs/btree.c b/fs/befs/btree.c
index 3f1a391..27b0336 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 (res == BEFS_BT_OVERFLOW)
 			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);
@@ -323,16 +322,12 @@ befs_btree_find(struct super_block *sb, const befs_data_stream *ds,
  * @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?
- *
- * 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 match and node's value array is too small for key, return
+ * BEFS_BT_OVERFLOW.
+ * If no match and node should countain this key, return 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,9 +350,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__);
-		return BEFS_BT_NOT_FOUND;
+		befs_debug(sb, "<--- node can't contain %s", findkey);
+		return BEFS_BT_OVERFLOW;
 	}
 
 	valarray = befs_bt_valarray(node);
@@ -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

[PATCH v3 2/2] befs: fix typo in befs_find_key

[Luis de Bethencourt]

Fixing skeep to skip.

Signed-off-by: Luis de Bethencourt <luisbg@osg.samsung.com>
---
v3: no change

 fs/befs/btree.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/fs/befs/btree.c b/fs/befs/btree.c
index 27b0336..54a1f95 100644
--- a/fs/befs/btree.c
+++ b/fs/befs/btree.c
@@ -344,7 +344,7 @@ befs_find_key(struct super_block *sb, struct befs_btree_node *node,
 
 	findkey_len = strlen(findkey);
 
-	/* if node can not contain key, just skeep this node */
+	/* if node can not contain key, just skip this node */
 	last = node->head.all_key_count - 1;
 	thiskey = befs_bt_get_key(sb, node, last, &keylen);
 
-- 
2.5.1

Re: [PATCH v3 1/2] befs: remove unused BEFS_BT_PARMATCH

[Salah Triki]

On Mon, Aug 08, 2016 at 03:21: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_PARMATCH. Make the overflow return clearer
> by having BEFS_BT_OVERFLOW instead of BEFS_BT_PARMATCH.
> 
> Signed-off-by: Luis de Bethencourt <luisbg@osg.samsung.com>
> ---
> v3: check for BEFS_BT_OVERFLOW instead of value == 0
> 
> 
> Hi,
> 
> Switching to using BEFS_BT_OVERFLOW. This makes logic of befs_find_key()
> clearer.
> 
> Thanks,
> Luis
> 
>  fs/befs/befs.h  |  2 +-
>  fs/befs/btree.c | 38 ++++++++++++++++----------------------
>  2 files changed, 17 insertions(+), 23 deletions(-)
> 
> diff --git a/fs/befs/befs.h b/fs/befs/befs.h
> index c5c6cd1..a8ca7fc 100644
> --- a/fs/befs/befs.h
> +++ b/fs/befs/befs.h
> @@ -79,7 +79,7 @@ enum befs_err {
>  	BEFS_BT_END,
>  	BEFS_BT_EMPTY,
>  	BEFS_BT_MATCH,
> -	BEFS_BT_PARMATCH,
> +	BEFS_BT_OVERFLOW,
>  	BEFS_BT_NOT_FOUND
>  };
>  
> diff --git a/fs/befs/btree.c b/fs/befs/btree.c
> index 3f1a391..27b0336 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 (res == BEFS_BT_OVERFLOW)
>  			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);
> @@ -323,16 +322,12 @@ befs_btree_find(struct super_block *sb, const befs_data_stream *ds,
>   * @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?
> - *
> - * 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 match and node's value array is too small for key, return
> + * BEFS_BT_OVERFLOW.
> + * If no match and node should countain this key, return 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,9 +350,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__);
> -		return BEFS_BT_NOT_FOUND;
> +		befs_debug(sb, "<--- node can't contain %s", findkey);
> +		return BEFS_BT_OVERFLOW;
>  	}
>  
>  	valarray = befs_bt_valarray(node);
> @@ -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
> 

Signed-off-by: Salah Triki <salah.triki@gmail.com>

Thanx :)
Salah