Messages in this thread Patch in this message | | | From | Leno Hou <> | Subject | [PATCH v3 1/2] lib/btree.c: optimise the code by previously getpos function | Date | Thu, 18 May 2017 16:35:55 +0800 |
| |
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 <andy.shevchenko@gmail.com> Signed-off-by: Leno Hou <lenohou@gmail.com> --- lib/btree.c | 79 +++++++++++++++++++++++++++++-------------------------------- 1 file changed, 37 insertions(+), 42 deletions(-)
diff --git a/lib/btree.c b/lib/btree.c index f93a945..a532f30 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) + break; + } + return i; +} + 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--) { -- 2.7.4
| |