linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* [PATCH v3 1/2] lib/btree.c: optimise the code by previously getpos function
@ 2017-05-18 13:40 Leno Hou
  2017-05-18 15:50 ` Andy Shevchenko
  0 siblings, 1 reply; 5+ messages in thread
From: Leno Hou @ 2017-05-18 13:40 UTC (permalink / raw)
  To: linux-kernel; +Cc: andy.shevchenko, akpm, Leno Hou

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..b9dff18 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,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

^ permalink raw reply related	[flat|nested] 5+ messages in thread
* Re: [PATCH v3 1/2] lib/btree.c: optimise the code by previously getpos function
  2017-05-18 13:40 [PATCH v3 1/2] lib/btree.c: optimise the code by previously getpos function Leno Hou
@ 2017-05-18 15:50 ` Andy Shevchenko
  0 siblings, 0 replies; 5+ messages in thread
From: Andy Shevchenko @ 2017-05-18 15:50 UTC (permalink / raw)
  To: Leno Hou; +Cc: linux-kernel, Andrew Morton

On Thu, May 18, 2017 at 4:40 PM, Leno Hou <lenohou@gmail.com> wrote:
> Rework the getpos() helper function and use it to remove various
> open-coded implemetnations of its funtionality.

>         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;

Now it makes sense to

return i;

instead.

-- 
With Best Regards,
Andy Shevchenko

^ permalink raw reply	[flat|nested] 5+ messages in thread
* [PATCH v3 1/2] lib/btree.c: optimise the code by previously getpos function
@ 2017-05-18 13:41 Leno Hou
  0 siblings, 0 replies; 5+ messages in thread
From: Leno Hou @ 2017-05-18 13:41 UTC (permalink / raw)
  To: linux-kernel; +Cc: andy.shevchenko, akpm, Leno Hou

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..b9dff18 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,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

^ permalink raw reply related	[flat|nested] 5+ messages in thread
* Re: [PATCH v3 1/2] lib/btree.c: optimise the code by previously getpos function
  2017-05-18  8:35 Leno Hou
@ 2017-05-18  9:50 ` Andy Shevchenko
  0 siblings, 0 replies; 5+ messages in thread
From: Andy Shevchenko @ 2017-05-18  9:50 UTC (permalink / raw)
  To: Leno Hou; +Cc: linux-kernel, Andrew Morton

On Thu, May 18, 2017 at 11:35 AM, Leno Hou <lenohou@gmail.com> wrote:
> 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

As far as I read Andrew's message he is not against new semantics of
getpos(), which I still consider is good to have, but rather not to
forget update users accordingly.

Would it be worth doing like that?

-- 
With Best Regards,
Andy Shevchenko

^ permalink raw reply	[flat|nested] 5+ messages in thread
* [PATCH v3 1/2] lib/btree.c: optimise the code by previously getpos function
@ 2017-05-18  8:35 Leno Hou
  2017-05-18  9:50 ` Andy Shevchenko
  0 siblings, 1 reply; 5+ messages in thread
From: Leno Hou @ 2017-05-18  8:35 UTC (permalink / raw)
  To: linux-kernel; +Cc: andy.shevchenko, akpm, Leno Hou

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

^ permalink raw reply related	[flat|nested] 5+ messages in thread
end of thread, other threads:[~2017-05-18 15:50 UTC | newest]

Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-05-18 13:40 [PATCH v3 1/2] lib/btree.c: optimise the code by previously getpos function Leno Hou
2017-05-18 15:50 ` Andy Shevchenko
  -- strict thread matches above, loose matches on Subject: below --
2017-05-18 13:41 Leno Hou
2017-05-18  8:35 Leno Hou
2017-05-18  9:50 ` Andy Shevchenko

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).