* [PATCH v2] lib/btree.c: optimise the code by previously getpos function
@ 2017-05-11 9:42 Leno Hou
2017-05-11 11:00 ` Andy Shevchenko
2017-05-12 20:58 ` Andrew Morton
0 siblings, 2 replies; 3+ messages in thread
From: Leno Hou @ 2017-05-11 9:42 UTC (permalink / raw)
To: linux-kernel; +Cc: andy.shevchenko, hch, Leno Hou
This patch optimized the code by previously getpos function call.
Therefore, It's takes the convenience to understand logic of code.
v2:
- getpos() returns errorno if not found the key
v1:
- cleanup code by using getpos()
Signed-off-by: Leno Hou <lenohou@gmail.com>
---
lib/btree.c | 50 +++++++++++++++++++++-----------------------------
1 file changed, 21 insertions(+), 29 deletions(-)
diff --git a/lib/btree.c b/lib/btree.c
index f93a945..8604773 100644
--- a/lib/btree.c
+++ b/lib/btree.c
@@ -238,6 +238,18 @@ static int keyzero(struct btree_geo *geo, unsigned long *key)
return 1;
}
+static int getpos(struct btree_geo *geo, unsigned long *node,
+ unsigned long *key)
+{
+ unsigned int i;
+
+ for (i = 0; i < geo->no_pairs; i++) {
+ if (keycmp(geo, node, i, key) <= 0)
+ return i;
+ }
+ return -ENOENT;
+}
+
void *btree_lookup(struct btree_head *head, struct btree_geo *geo,
unsigned long *key)
{
@@ -248,10 +260,8 @@ void *btree_lookup(struct btree_head *head, struct btree_geo *geo,
return NULL;
for ( ; height > 1; height--) {
- for (i = 0; i < geo->no_pairs; i++)
- if (keycmp(geo, node, i, key) <= 0)
- break;
- if (i == geo->no_pairs)
+ i = getpos(geo, node, key);
+ if (i < 0)
return NULL;
node = bval(geo, node, i);
if (!node)
@@ -278,10 +288,8 @@ int btree_update(struct btree_head *head, struct btree_geo *geo,
return -ENOENT;
for ( ; height > 1; height--) {
- for (i = 0; i < geo->no_pairs; i++)
- if (keycmp(geo, node, i, key) <= 0)
- break;
- if (i == geo->no_pairs)
+ i = getpos(geo, node, key);
+ if (i < 0)
return -ENOENT;
node = bval(geo, node, i);
if (!node)
@@ -326,10 +334,8 @@ void *btree_get_prev(struct btree_head *head, struct btree_geo *geo,
node = head->node;
for (height = head->height ; height > 1; height--) {
- for (i = 0; i < geo->no_pairs; i++)
- if (keycmp(geo, node, i, key) <= 0)
- break;
- if (i == geo->no_pairs)
+ i = getpos(geo, node, key);
+ if (i < 0)
goto miss;
oldnode = node;
node = bval(geo, node, i);
@@ -360,18 +366,6 @@ void *btree_get_prev(struct btree_head *head, struct btree_geo *geo,
}
EXPORT_SYMBOL_GPL(btree_get_prev);
-static int getpos(struct btree_geo *geo, unsigned long *node,
- unsigned long *key)
-{
- int i;
-
- for (i = 0; i < geo->no_pairs; i++) {
- if (keycmp(geo, node, i, key) <= 0)
- break;
- }
- return i;
-}
-
static int getfill(struct btree_geo *geo, unsigned long *node, int start)
{
int i;
@@ -392,11 +386,9 @@ static unsigned long *find_level(struct btree_head *head, struct btree_geo *geo,
int i, height;
for (height = head->height; height > level; height--) {
- for (i = 0; i < geo->no_pairs; i++)
- if (keycmp(geo, node, i, key) <= 0)
- break;
+ i = getpos(geo, node, key);
- if ((i == geo->no_pairs) || !bval(geo, node, i)) {
+ if ((i < 0) || !bval(geo, node, i)) {
/* right-most key is too large, update it */
/* FIXME: If the right-most key on higher levels is
* always zero, this wouldn't be necessary. */
@@ -466,7 +458,7 @@ static int btree_insert_level(struct btree_head *head, struct btree_geo *geo,
/* two identical keys are not allowed */
BUG_ON(pos < fill && keycmp(geo, node, pos, key) == 0);
- if (fill == geo->no_pairs) {
+ if (fill < 0) {
/* need to split node */
unsigned long *new;
--
2.7.4
^ permalink raw reply [flat|nested] 3+ messages in thread* Re: [PATCH v2] lib/btree.c: optimise the code by previously getpos function
2017-05-11 9:42 [PATCH v2] lib/btree.c: optimise the code by previously getpos function Leno Hou
@ 2017-05-11 11:00 ` Andy Shevchenko
2017-05-12 20:58 ` Andrew Morton
1 sibling, 0 replies; 3+ messages in thread
From: Andy Shevchenko @ 2017-05-11 11:00 UTC (permalink / raw)
To: Leno Hou; +Cc: linux-kernel, Christoph Hellwig
On Thu, May 11, 2017 at 12:42 PM, Leno Hou <lenohou@gmail.com> wrote:
> This patch optimized the code by previously getpos function call.
> Therefore, It's takes the convenience to understand logic of code.
>
> v2:
> - getpos() returns errorno if not found the key
>
> v1:
> - cleanup code by using getpos()
FWIW:
Reviewed-by: Andy Shevchenko <andy.shevchenko@gmail.com>
>
> Signed-off-by: Leno Hou <lenohou@gmail.com>
> ---
> lib/btree.c | 50 +++++++++++++++++++++-----------------------------
> 1 file changed, 21 insertions(+), 29 deletions(-)
>
> diff --git a/lib/btree.c b/lib/btree.c
> index f93a945..8604773 100644
> --- a/lib/btree.c
> +++ b/lib/btree.c
> @@ -238,6 +238,18 @@ static int keyzero(struct btree_geo *geo, unsigned long *key)
> return 1;
> }
>
> +static int getpos(struct btree_geo *geo, unsigned long *node,
> + unsigned long *key)
> +{
> + unsigned int i;
> +
> + for (i = 0; i < geo->no_pairs; i++) {
> + if (keycmp(geo, node, i, key) <= 0)
> + return i;
> + }
> + return -ENOENT;
> +}
> +
> void *btree_lookup(struct btree_head *head, struct btree_geo *geo,
> unsigned long *key)
> {
> @@ -248,10 +260,8 @@ void *btree_lookup(struct btree_head *head, struct btree_geo *geo,
> return NULL;
>
> for ( ; height > 1; height--) {
> - for (i = 0; i < geo->no_pairs; i++)
> - if (keycmp(geo, node, i, key) <= 0)
> - break;
> - if (i == geo->no_pairs)
> + i = getpos(geo, node, key);
> + if (i < 0)
> return NULL;
> node = bval(geo, node, i);
> if (!node)
> @@ -278,10 +288,8 @@ int btree_update(struct btree_head *head, struct btree_geo *geo,
> return -ENOENT;
>
> for ( ; height > 1; height--) {
> - for (i = 0; i < geo->no_pairs; i++)
> - if (keycmp(geo, node, i, key) <= 0)
> - break;
> - if (i == geo->no_pairs)
> + i = getpos(geo, node, key);
> + if (i < 0)
> return -ENOENT;
> node = bval(geo, node, i);
> if (!node)
> @@ -326,10 +334,8 @@ void *btree_get_prev(struct btree_head *head, struct btree_geo *geo,
>
> node = head->node;
> for (height = head->height ; height > 1; height--) {
> - for (i = 0; i < geo->no_pairs; i++)
> - if (keycmp(geo, node, i, key) <= 0)
> - break;
> - if (i == geo->no_pairs)
> + i = getpos(geo, node, key);
> + if (i < 0)
> goto miss;
> oldnode = node;
> node = bval(geo, node, i);
> @@ -360,18 +366,6 @@ void *btree_get_prev(struct btree_head *head, struct btree_geo *geo,
> }
> EXPORT_SYMBOL_GPL(btree_get_prev);
>
> -static int getpos(struct btree_geo *geo, unsigned long *node,
> - unsigned long *key)
> -{
> - int i;
> -
> - for (i = 0; i < geo->no_pairs; i++) {
> - if (keycmp(geo, node, i, key) <= 0)
> - break;
> - }
> - return i;
> -}
> -
> static int getfill(struct btree_geo *geo, unsigned long *node, int start)
> {
> int i;
> @@ -392,11 +386,9 @@ static unsigned long *find_level(struct btree_head *head, struct btree_geo *geo,
> int i, height;
>
> for (height = head->height; height > level; height--) {
> - for (i = 0; i < geo->no_pairs; i++)
> - if (keycmp(geo, node, i, key) <= 0)
> - break;
> + i = getpos(geo, node, key);
>
> - if ((i == geo->no_pairs) || !bval(geo, node, i)) {
> + if ((i < 0) || !bval(geo, node, i)) {
> /* right-most key is too large, update it */
> /* FIXME: If the right-most key on higher levels is
> * always zero, this wouldn't be necessary. */
> @@ -466,7 +458,7 @@ static int btree_insert_level(struct btree_head *head, struct btree_geo *geo,
> /* two identical keys are not allowed */
> BUG_ON(pos < fill && keycmp(geo, node, pos, key) == 0);
>
> - if (fill == geo->no_pairs) {
> + if (fill < 0) {
> /* need to split node */
> unsigned long *new;
>
> --
> 2.7.4
>
--
With Best Regards,
Andy Shevchenko
^ permalink raw reply [flat|nested] 3+ messages in thread* Re: [PATCH v2] lib/btree.c: optimise the code by previously getpos function
2017-05-11 9:42 [PATCH v2] lib/btree.c: optimise the code by previously getpos function Leno Hou
2017-05-11 11:00 ` Andy Shevchenko
@ 2017-05-12 20:58 ` Andrew Morton
1 sibling, 0 replies; 3+ messages in thread
From: Andrew Morton @ 2017-05-12 20:58 UTC (permalink / raw)
To: Leno Hou; +Cc: linux-kernel, andy.shevchenko, hch
On Thu, 11 May 2017 17:42:21 +0800 Leno Hou <lenohou@gmail.com> wrote:
> This patch optimized the code by previously getpos function call.
> Therefore, It's takes the convenience to understand logic of code.
I would rewrite this changelog to read
: Rework the getpos() helper function and use it to remove various
: open-coded implemetnations of its funtionality.
> ...
>
> @@ -466,7 +458,7 @@ static int btree_insert_level(struct btree_head *head, struct btree_geo *geo,
> /* two identical keys are not allowed */
> BUG_ON(pos < fill && keycmp(geo, node, pos, key) == 0);
>
> - if (fill == geo->no_pairs) {
> + if (fill < 0) {
> /* need to split node */
> unsigned long *new;
The code here is a bit awkward.
: retry:
: node = find_level(head, geo, key, level);
: pos = getpos(geo, node, key);
: fill = getfill(geo, node, pos);
: /* two identical keys are not allowed */
: BUG_ON(pos < fill && keycmp(geo, node, pos, key) == 0);
:
: if (fill < 0) {
If getpos() returns -ENOENT then we're passing -ENOENT into getfill().
That might happen to work OK (or it might go BUG) but it's ugly and
unobvious.
There's a similar issue in rebalance() and in btree_remove_level():
failed to update existing getpos() callers for the new getpos() return
value semantics.
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2017-05-12 20:59 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-05-11 9:42 [PATCH v2] lib/btree.c: optimise the code by previously getpos function Leno Hou
2017-05-11 11:00 ` Andy Shevchenko
2017-05-12 20:58 ` Andrew Morton
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®