lib/btree.c: optimise the code by previously getpos function
PATCH v2 1/1 lib/btree.c: optimise the code by previously getpos function
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()
--- lib/btree.c | 50 +++++++++++++++++++++----------------------------- 1 file changed, 21 insertions(+), 29 deletions(-)
lib/btree.c +21 -29
@@ -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;
Signature · 1 line
2.7.4
Quoted 8 lines · 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 keyv1:
- cleanup code by usinggetpos()
FWIW:
Quoted 113 lines
Signed-off-by Leno Hou <[email protected]>--- lib/btree.c | 50 +++++++++++++++++++++----------------------------- 1 file changed, 21 insertions(+), 29 deletions(-)lib/btree.c +21
-30@@ -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
Signature · 2 lines
With Best Regards, Andy Shevchenko
Andrew Morton
maintainerQuoted 2 lines · On Thu, 11 May 2017 17:42:21 +0800 Leno Hou <[email protected]> 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.
lib/btree.c static int btree_insert_level(struct btree_head *head, struct btree_geo *geo, · line 463
Quoted 10 lines
...
lib/btree.c +1
-1@@ -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.