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
PATCH v3 2/2 lib/btree.c: add testcase for in-memory b+ tree
Signed-off-by Leno Hou <[email protected]>
--- lib/btree_test.c | 77 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 77 insertions(+) create mode 100644 lib/btree_test.c
lib/btree_test.c new file +77 -0
@@ -0,0 +1,77 @@ +#include <linux/module.h> +#include <linux/kernel.h> +#include <linux/init.h> +#include <linux/btree.h> +#include <linux/types.h> + +#define NODES 24 + +struct test_node { +u32 key; +u32 val; +}; + +static struct btree_head32 bh; +static struct test_node nodes[NODES ]; + +static void init (void ) +{ +int i; + +for (i =0 ; i <NODES ; i++) { + nodes[i].key = i; + nodes[i].val = i; + } +} +static int __init btree_test_init (void ) +{ +u32 key =0 ; +u32 *val =NULL ; +int i, rc; + +pr_alert ("btree testing\n" ); + +init (); + rc =btree_init32 (&bh); + +if (rc) +pr_alert ("Unable initialize btree memory\n" ); + +for (i =0 ; i <NODES ; i++) { + rc =btree_insert32 (&bh, + nodes[i].key, + &nodes[i].val, +GFP_ATOMIC ); + +if (rc) +pr_alert ("Unable to insert key into btree\n" ); + } + +pr_alert ("========================================\n" ); + +btree_for_each_safe32 (&bh, key, val) { +pr_alert ("val %d\n" , *val); + } + +btree_remove32 (&bh,11 ); + +pr_alert ("========================================\n" ); +btree_for_each_safe32 (&bh, key, val) { +pr_alert ("val %d\n" , *val); + } + +return 0 ; +} +static void __exit btree_test_exit(void) +{ +pr_alert ("test exit\n" ); +btree_destroy32 (&bh); + +} + +module_init (btree_test_init); +module_exit (btree_test_exit); + +MODULE_LICENSE ("Dual BSD/GPL" ); +MODULE_AUTHOR ("Leno Hou <[email protected]>" ); +MODULE_DESCRIPTION ("Simple In-memory B+ Tree test" );
Signature · 1 line
2.7.4
Re: [PATCH v3 2/2] lib/btree.c: add testcase for in-memory b+ tree
Quoted 2 lines · Leno Hou
Signed-off-by Leno Hou <[email protected]>---
Please, address my comments.
This version doesn't look modified anyhow.
Quoted 90 lines
lib/btree_test.c | 77 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 77 insertions(+) create mode 100644 lib/btree_test.clib/btree_test.c new file +77
-1@@ -0,0 +1,77 @@ +#include <linux/module.h> +#include <linux/kernel.h> +#include <linux/init.h> +#include <linux/btree.h> +#include <linux/types.h> + +#define NODES 24 + +struct test_node { +u32 key; +u32 val; +}; + +static struct btree_head32 bh; +static struct test_node nodes[NODES ]; + +static void init (void ) +{ +int i; + +for (i =0 ; i <NODES ; i++) { + nodes[i].key = i; + nodes[i].val = i; + } +} +static int __init btree_test_init (void ) +{ +u32 key =0 ; +u32 *val =NULL ; +int i, rc; + +pr_alert ("btree testing\n" ); + +init (); + rc =btree_init32 (&bh); + +if (rc) +pr_alert ("Unable initialize btree memory\n" ); + +for (i =0 ; i <NODES ; i++) { + rc =btree_insert32 (&bh, + nodes[i].key, + &nodes[i].val, +GFP_ATOMIC ); + +if (rc) +pr_alert ("Unable to insert key into btree\n" ); + } + +pr_alert ("========================================\n" ); + +btree_for_each_safe32 (&bh, key, val) { +pr_alert ("val %d\n" , *val); + } + +btree_remove32 (&bh,11 ); + +pr_alert ("========================================\n" ); +btree_for_each_safe32 (&bh, key, val) { +pr_alert ("val %d\n" , *val); + } + +return 0 ; +} +static void __exit btree_test_exit(void) +{ +pr_alert ("test exit\n" ); +btree_destroy32 (&bh); + +} + +module_init (btree_test_init); +module_exit (btree_test_exit); + +MODULE_LICENSE ("Dual BSD/GPL" ); +MODULE_AUTHOR ("Leno Hou <[email protected]>" ); +MODULE_DESCRIPTION ("Simple In-memory B+ Tree test" ); --2.7.4
Signature · 2 lines
With Best Regards, Andy Shevchenko