lib/btree.c: optimise the code by previously getpos function
PATCH v3 1/2 lib/btree.c: optimise the code by previously getpos function
Rework the getpos() helper function and use it to remove various open-coded implemetnations of its funtionality.
v2 -> v3:
- getfill() returns no entry if not found the fill position
v1 -> v2:
- getpos() returns no entry if not found the key
Reviewed-by Andy Shevchenko <[email protected]>
Signed-off-by Leno Hou <[email protected]>
--- lib/btree.c | 79 +++++++++++++++++++++++++++++-------------------------------- 1 file changed, 37 insertions(+), 42 deletions(-)
lib/btree.c +37 -42
@@ -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,26 +366,17 @@ 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; +unsigned int i; + +if (unlikely (start <0 )) +return -ENOENT ;for (i = start; i < geo->no_pairs; i++)if (!bval (geo, node, i)) -break ; -return i; +return i; +return -ENOENT ; }/*
@@ -392,11 +389,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 +461,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;
@@ -474,27 +469,27 @@ static int btree_insert_level(struct btree_head *head, struct btree_geo *geo,if (!new)return -ENOMEM ; err =btree_insert_level (head, geo, -bkey (geo, node, fill /2 -1 ), +bkey (geo, node, geo->no_pairs /2 -1 ), new, level +1 , gfp);if (err) {mempool_free (new, head->mempool);return err; } -for (i =0 ; i < fill /2 ; i++) { +for (i =0 ; i < geo->no_pairs /2 ; i++) {setkey (geo, new, i,bkey (geo, node, i));setval (geo, new, i,bval (geo, node, i)); -setkey (geo, node, i,bkey (geo, node, i + fill /2 )); -setval (geo, node, i,bval (geo, node, i + fill /2 )); -clearpair (geo, node, i + fill /2 ); +setkey (geo, node, i,bkey (geo, node, i + geo->no_pairs /2 )); +setval (geo, node, i,bval (geo, node, i + geo->no_pairs /2 )); +clearpair (geo, node, i + geo->no_pairs /2 ); } -if (fill &1 ) { -setkey (geo, node, i,bkey (geo, node, fill -1 )); -setval (geo, node, i,bval (geo, node, fill -1 )); -clearpair (geo, node, fill -1 ); +if (geo->no_pairs &1 ) { +setkey (geo, node, i,bkey (geo, node, geo->no_pairs -1 )); +setval (geo, node, i,bval (geo, node, geo->no_pairs -1 )); +clearpair (geo, node, geo->no_pairs -1 ); } goto retry; } -BUG_ON (fill >= geo->no_pairs); +BUG_ON (fill <0 );/* shift and insert */ for (i = fill; i > pos; i--) {
Signature · 1 line
2.7.4
lib/btree.c int btree_update(struct btree_head *head, struct btree_geo *geo, · line 293
Quoted 11 lines · Leno Hou
Rework the
getpos()helper function and use it to remove various open-coded implemetnations of its funtionality.for ( ; height > 1; height--) {lib/btree.c +2
-4-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 ;
Now it makes sense to
return i;
instead.
Signature · 2 lines
With Best Regards, Andy Shevchenko