* [PATCH v3 1/2] lib/btree.c: optimise the code by previously getpos function
@ 2017-05-18 13:41 Leno Hou
2017-05-18 13:41 ` [PATCH v3 2/2] lib/btree.c: add testcase for in-memory b+ tree Leno Hou
0 siblings, 1 reply; 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
* [PATCH v3 2/2] lib/btree.c: add testcase for in-memory b+ tree
2017-05-18 13:41 [PATCH v3 1/2] lib/btree.c: optimise the code by previously getpos function Leno Hou
@ 2017-05-18 13:41 ` Leno Hou
2017-05-18 15:51 ` Andy Shevchenko
0 siblings, 1 reply; 5+ messages in thread
From: Leno Hou @ 2017-05-18 13:41 UTC (permalink / raw)
To: linux-kernel; +Cc: andy.shevchenko, akpm, Leno Hou
Signed-off-by: Leno Hou <lenohou@gmail.com>
---
lib/btree_test.c | 77 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 77 insertions(+)
create mode 100644 lib/btree_test.c
diff --git a/lib/btree_test.c b/lib/btree_test.c
new file mode 100644
index 0000000..90d9048
--- /dev/null
+++ b/lib/btree_test.c
@@ -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 <lenohou@gmai.com>");
+MODULE_DESCRIPTION("Simple In-memory B+ Tree test");
--
2.7.4
^ permalink raw reply related [flat|nested] 5+ messages in thread
* Re: [PATCH v3 2/2] lib/btree.c: add testcase for in-memory b+ tree
2017-05-18 13:41 ` [PATCH v3 2/2] lib/btree.c: add testcase for in-memory b+ tree Leno Hou
@ 2017-05-18 15:51 ` Andy Shevchenko
0 siblings, 0 replies; 5+ messages in thread
From: Andy Shevchenko @ 2017-05-18 15:51 UTC (permalink / raw)
To: Leno Hou; +Cc: linux-kernel, Andrew Morton
On Thu, May 18, 2017 at 4:41 PM, Leno Hou <lenohou@gmail.com> wrote:
> Signed-off-by: Leno Hou <lenohou@gmail.com>
> ---
Please, address my comments.
This version doesn't look modified anyhow.
> lib/btree_test.c | 77 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
> 1 file changed, 77 insertions(+)
> create mode 100644 lib/btree_test.c
>
> diff --git a/lib/btree_test.c b/lib/btree_test.c
> new file mode 100644
> index 0000000..90d9048
> --- /dev/null
> +++ b/lib/btree_test.c
> @@ -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 <lenohou@gmai.com>");
> +MODULE_DESCRIPTION("Simple In-memory B+ Tree test");
> --
> 2.7.4
>
--
With Best Regards,
Andy Shevchenko
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH v3 2/2] lib/btree.c: add testcase for in-memory b+ tree
2017-05-18 8:35 ` [PATCH v3 2/2] lib/btree.c: add testcase for in-memory b+ tree Leno Hou
@ 2017-05-18 10:00 ` Andy Shevchenko
0 siblings, 0 replies; 5+ messages in thread
From: Andy Shevchenko @ 2017-05-18 10:00 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:
Commit message, please.
And I think you do introduce test cases first, then you update the
code. This way is naturally like things would be done.
> +++ b/lib/btree_test.c
Okay, this will be 5th in the pattern foo_bar_test.c :-)
I think it's okay since we have that pattern for tree implementations.
> @@ -0,0 +1,77 @@
> +#include <linux/module.h>
> +#include <linux/kernel.h>
> +#include <linux/init.h>
> +#include <linux/btree.h>
> +#include <linux/types.h>
Alphabetical order, please.
> +
> +#define NODES 24
BTREE_TEST_...
> +
> +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;
Assignments look to me redundant. for_each should do that, shouldn't it?
> + int i, rc;
unsigned int i;
?
> +
> + pr_alert("btree testing\n");
We are using pr_info() / pr_warn() pair in the rest of test_* modules.
Please, follow.
E.g. here pr_info() is suitable.
> +
> + init();
> + rc = btree_init32(&bh);
> +
Move this empty line to be after init();.
> + 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);
Is this necessary to be 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;
Consider to return -EINVAL if tests are failed. Thus, you need to
introduce actual testing function.
> +}
--
With Best Regards,
Andy Shevchenko
^ permalink raw reply [flat|nested] 5+ messages in thread
* [PATCH v3 2/2] lib/btree.c: add testcase for in-memory b+ tree
2017-05-18 8:35 [PATCH v3 1/2] lib/btree.c: optimise the code by previously getpos function Leno Hou
@ 2017-05-18 8:35 ` Leno Hou
2017-05-18 10:00 ` 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
Signed-off-by: Leno Hou <lenohou@gmail.com>
---
lib/btree_test.c | 77 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 77 insertions(+)
create mode 100644 lib/btree_test.c
diff --git a/lib/btree_test.c b/lib/btree_test.c
new file mode 100644
index 0000000..90d9048
--- /dev/null
+++ b/lib/btree_test.c
@@ -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 <lenohou@gmai.com>");
+MODULE_DESCRIPTION("Simple In-memory B+ Tree test");
--
2.7.4
^ permalink raw reply related [flat|nested] 5+ messages in thread
end of thread, other threads:[~2017-05-18 15:51 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:41 [PATCH v3 1/2] lib/btree.c: optimise the code by previously getpos function Leno Hou
2017-05-18 13:41 ` [PATCH v3 2/2] lib/btree.c: add testcase for in-memory b+ tree Leno Hou
2017-05-18 15:51 ` Andy Shevchenko
-- strict thread matches above, loose matches on Subject: below --
2017-05-18 8:35 [PATCH v3 1/2] lib/btree.c: optimise the code by previously getpos function Leno Hou
2017-05-18 8:35 ` [PATCH v3 2/2] lib/btree.c: add testcase for in-memory b+ tree Leno Hou
2017-05-18 10:00 ` 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).