[PATCH] vt: Use bsearch library function in is_double_width

[PATCH] vt: Use bsearch library function in is_double_width

[Thomas Meyer]

Signed-off-by: Thomas Meyer <thomas@m3y3r.de>
---
 drivers/tty/vt/vt.c | 25 ++++++++++---------------
 1 file changed, 10 insertions(+), 15 deletions(-)

diff --git a/drivers/tty/vt/vt.c b/drivers/tty/vt/vt.c
index 2ebaba16f785..725777a5d35e 100644
--- a/drivers/tty/vt/vt.c
+++ b/drivers/tty/vt/vt.c
@@ -102,6 +102,7 @@
 #include <linux/uaccess.h>
 #include <linux/kdb.h>
 #include <linux/ctype.h>
+#include <linux/bsearch.h>
 
 #define MAX_NR_CON_DRIVER 16
 
@@ -2142,22 +2143,15 @@ struct interval {
 	uint32_t last;
 };
 
-static int bisearch(uint32_t ucs, const struct interval *table, int max)
+static int ucs_cmp(const void *key, const void *elt)
 {
-	int min = 0;
-	int mid;
+	uint32_t ucs = *(uint32_t *)key;
+	struct interval e = *(struct interval *) elt;
 
-	if (ucs < table[0].first || ucs > table[max].last)
-		return 0;
-	while (max >= min) {
-		mid = (min + max) / 2;
-		if (ucs > table[mid].last)
-			min = mid + 1;
-		else if (ucs < table[mid].first)
-			max = mid - 1;
-		else
-			return 1;
-	}
+	if (ucs > e.last)
+		return 1;
+	else if (ucs < e.first)
+		return -1;
 	return 0;
 }
 
@@ -2169,7 +2163,8 @@ static int is_double_width(uint32_t ucs)
 		{ 0xFE10, 0xFE19 }, { 0xFE30, 0xFE6F }, { 0xFF00, 0xFF60 },
 		{ 0xFFE0, 0xFFE6 }, { 0x20000, 0x2FFFD }, { 0x30000, 0x3FFFD }
 	};
-	return bisearch(ucs, double_width, ARRAY_SIZE(double_width) - 1);
+	return bsearch(&ucs, double_width, ARRAY_SIZE(double_width),
+			sizeof(struct interval), ucs_cmp) != NULL;
 }
 
 static void con_flush(struct vc_data *vc, unsigned long draw_from,
-- 
2.11.0

Re: [PATCH] vt: Use bsearch library function in is_double_width

[Greg KH]

On Thu, Aug 31, 2017 at 03:04:32PM +0200, Thomas Meyer wrote:
> Signed-off-by: Thomas Meyer <thomas@m3y3r.de>
> ---

I can't take patches without any changelog text, sorry.

greg k-h

[PATCH v2] ipv6: sr: Use ARRAY_SIZE macro

[Thomas Meyer]

Grepping for "sizeof\(.+\) / sizeof\(" found this as one of the first
candidates.
Maybe a coccinelle can catch all of those.

Signed-off-by: Thomas Meyer <thomas@m3y3r.de>
---
 net/ipv6/seg6_hmac.c | 7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)

diff --git a/net/ipv6/seg6_hmac.c b/net/ipv6/seg6_hmac.c
index f950cb53d5e3..33fb35cbfac1 100644
--- a/net/ipv6/seg6_hmac.c
+++ b/net/ipv6/seg6_hmac.c
@@ -12,6 +12,7 @@
  */
 
 #include <linux/errno.h>
+#include <linux/kernel.h>
 #include <linux/types.h>
 #include <linux/socket.h>
 #include <linux/sockios.h>
@@ -110,7 +111,7 @@ static struct seg6_hmac_algo *__hmac_get_algo(u8 alg_id)
 	struct seg6_hmac_algo *algo;
 	int i, alg_count;
 
-	alg_count = sizeof(hmac_algos) / sizeof(struct seg6_hmac_algo);
+	alg_count = ARRAY_SIZE(hmac_algos);
 	for (i = 0; i < alg_count; i++) {
 		algo = &hmac_algos[i];
 		if (algo->alg_id == alg_id)
@@ -360,7 +361,7 @@ static int seg6_hmac_init_algo(void)
 	struct shash_desc *shash;
 	int i, alg_count, cpu;
 
-	alg_count = sizeof(hmac_algos) / sizeof(struct seg6_hmac_algo);
+	alg_count = ARRAY_SIZE(hmac_algos);
 
 	for (i = 0; i < alg_count; i++) {
 		struct crypto_shash **p_tfm;
@@ -421,7 +422,7 @@ void seg6_hmac_exit(void)
 	struct seg6_hmac_algo *algo = NULL;
 	int i, alg_count, cpu;
 
-	alg_count = sizeof(hmac_algos) / sizeof(struct seg6_hmac_algo);
+	alg_count = ARRAY_SIZE(hmac_algos);
 	for (i = 0; i < alg_count; i++) {
 		algo = &hmac_algos[i];
 		for_each_possible_cpu(cpu) {
-- 
2.11.0

Re: [PATCH v2] ipv6: sr: Use ARRAY_SIZE macro

[Greg KH]

On Thu, Aug 31, 2017 at 04:20:18PM +0200, Thomas Meyer wrote:
> Grepping for "sizeof\(.+\) / sizeof\(" found this as one of the first
> candidates.
> Maybe a coccinelle can catch all of those.
> 
> Signed-off-by: Thomas Meyer <thomas@m3y3r.de>
> ---
>  net/ipv6/seg6_hmac.c | 7 ++++---
>  1 file changed, 4 insertions(+), 3 deletions(-)

Why are you sending this to me?

Please, use scripts/get_maintainers.pl properly please.

Re: [PATCH v2] ipv6: sr: Use ARRAY_SIZE macro

[Thomas Meyer]

On Thu, Aug 31, 2017 at 05:02:09PM +0200, Greg KH wrote:
> On Thu, Aug 31, 2017 at 04:20:18PM +0200, Thomas Meyer wrote:
> > Grepping for "sizeof\(.+\) / sizeof\(" found this as one of the first
> > candidates.
> > Maybe a coccinelle can catch all of those.
> > 
> > Signed-off-by: Thomas Meyer <thomas@m3y3r.de>
> > ---
> >  net/ipv6/seg6_hmac.c | 7 ++++---
> >  1 file changed, 4 insertions(+), 3 deletions(-)
> 
> Why are you sending this to me?
Sorry, I messed up git send-email.

> 
> Please, use scripts/get_maintainers.pl properly please.

[PATCH v2] vt: Use bsearch library function in is_double_width

[Thomas Meyer]

Use bsearch library function instead of duplicated functionality.

v2: Re-introduce early exit from old binary search.

Signed-off-by: Thomas Meyer <thomas@m3y3r.de>
---
 drivers/tty/vt/vt.c | 29 ++++++++++++++---------------
 1 file changed, 14 insertions(+), 15 deletions(-)

diff --git a/drivers/tty/vt/vt.c b/drivers/tty/vt/vt.c
index 2ebaba16f785..ca55004a639e 100644
--- a/drivers/tty/vt/vt.c
+++ b/drivers/tty/vt/vt.c
@@ -102,6 +102,7 @@
 #include <linux/uaccess.h>
 #include <linux/kdb.h>
 #include <linux/ctype.h>
+#include <linux/bsearch.h>
 
 #define MAX_NR_CON_DRIVER 16
 
@@ -2142,22 +2143,15 @@ struct interval {
 	uint32_t last;
 };
 
-static int bisearch(uint32_t ucs, const struct interval *table, int max)
+static int ucs_cmp(const void *key, const void *elt)
 {
-	int min = 0;
-	int mid;
+	uint32_t ucs = *(uint32_t *)key;
+	struct interval e = *(struct interval *) elt;
 
-	if (ucs < table[0].first || ucs > table[max].last)
-		return 0;
-	while (max >= min) {
-		mid = (min + max) / 2;
-		if (ucs > table[mid].last)
-			min = mid + 1;
-		else if (ucs < table[mid].first)
-			max = mid - 1;
-		else
-			return 1;
-	}
+	if (ucs > e.last)
+		return 1;
+	else if (ucs < e.first)
+		return -1;
 	return 0;
 }
 
@@ -2169,7 +2163,12 @@ static int is_double_width(uint32_t ucs)
 		{ 0xFE10, 0xFE19 }, { 0xFE30, 0xFE6F }, { 0xFF00, 0xFF60 },
 		{ 0xFFE0, 0xFFE6 }, { 0x20000, 0x2FFFD }, { 0x30000, 0x3FFFD }
 	};
-	return bisearch(ucs, double_width, ARRAY_SIZE(double_width) - 1);
+	if (ucs < double_width[0].first ||
+	    ucs > double_width[ARRAY_SIZE(double_width) - 1].last)
+		return 0;
+
+	return bsearch(&ucs, double_width, ARRAY_SIZE(double_width),
+			sizeof(struct interval), ucs_cmp) != NULL;
 }
 
 static void con_flush(struct vc_data *vc, unsigned long draw_from,
-- 
2.11.0

Re: [PATCH v2] vt: Use bsearch library function in is_double_width

[Greg KH]

On Thu, Aug 31, 2017 at 04:21:15PM +0200, Thomas Meyer wrote:
> Use bsearch library function instead of duplicated functionality.
> 
> v2: Re-introduce early exit from old binary search.

That's not the difference from the previous patch...

And that info goes below the --- line, as the documentation states.

Please fix and resend it properly.  After you take some time to relax
and verify you did it correct, there is no rush here.

greg k-h

Re: [PATCH v2] vt: Use bsearch library function in is_double_width

[Thomas Meyer]

On Thu, Aug 31, 2017 at 05:02:53PM +0200, Greg KH wrote:
> On Thu, Aug 31, 2017 at 04:21:15PM +0200, Thomas Meyer wrote:
> > Use bsearch library function instead of duplicated functionality.
> > 
One question: Having above changelog text and a nearly similar subject line is
fine for you?

> > v2: Re-introduce early exit from old binary search.
> 
> That's not the difference from the previous patch...

It isn't?

v2 adds those lines:
+      if (ucs < double_width[0].first ||
+          ucs > double_width[ARRAY_SIZE(double_width) - 1].last)
+              return 0;

Which is the early exit from the old binary search, i.e. the current
implementation
What do you mean with "that's not the difference from the previous
patch"?

> 
> And that info goes below the --- line, as the documentation states.

So besides adding v2 comment below the --- line, what else do you want
me to change to accept this patch?

[PATCH] vt: Use bsearch library function in is_double_width

[Thomas Meyer]

Use bsearch library function instead of duplicated functionality.

Signed-off-by: Thomas Meyer <thomas@m3y3r.de>
---
 drivers/tty/vt/vt.c | 29 ++++++++++++++---------------
 1 file changed, 14 insertions(+), 15 deletions(-)

diff --git a/drivers/tty/vt/vt.c b/drivers/tty/vt/vt.c
index 2ebaba16f785..ca55004a639e 100644
--- a/drivers/tty/vt/vt.c
+++ b/drivers/tty/vt/vt.c
@@ -102,6 +102,7 @@
 #include <linux/uaccess.h>
 #include <linux/kdb.h>
 #include <linux/ctype.h>
+#include <linux/bsearch.h>
 
 #define MAX_NR_CON_DRIVER 16
 
@@ -2142,22 +2143,15 @@ struct interval {
 	uint32_t last;
 };
 
-static int bisearch(uint32_t ucs, const struct interval *table, int max)
+static int ucs_cmp(const void *key, const void *elt)
 {
-	int min = 0;
-	int mid;
+	uint32_t ucs = *(uint32_t *)key;
+	struct interval e = *(struct interval *) elt;
 
-	if (ucs < table[0].first || ucs > table[max].last)
-		return 0;
-	while (max >= min) {
-		mid = (min + max) / 2;
-		if (ucs > table[mid].last)
-			min = mid + 1;
-		else if (ucs < table[mid].first)
-			max = mid - 1;
-		else
-			return 1;
-	}
+	if (ucs > e.last)
+		return 1;
+	else if (ucs < e.first)
+		return -1;
 	return 0;
 }
 
@@ -2169,7 +2163,12 @@ static int is_double_width(uint32_t ucs)
 		{ 0xFE10, 0xFE19 }, { 0xFE30, 0xFE6F }, { 0xFF00, 0xFF60 },
 		{ 0xFFE0, 0xFFE6 }, { 0x20000, 0x2FFFD }, { 0x30000, 0x3FFFD }
 	};
-	return bisearch(ucs, double_width, ARRAY_SIZE(double_width) - 1);
+	if (ucs < double_width[0].first ||
+	    ucs > double_width[ARRAY_SIZE(double_width) - 1].last)
+		return 0;
+
+	return bsearch(&ucs, double_width, ARRAY_SIZE(double_width),
+			sizeof(struct interval), ucs_cmp) != NULL;
 }
 
 static void con_flush(struct vc_data *vc, unsigned long draw_from,
-- 
2.11.0

[PATCH] vt: Use bsearch library function in is_double_width

[Thomas Meyer]

Use bsearch library function instead of duplicated functionality.

Signed-off-by: Thomas Meyer <thomas@m3y3r.de>
---
 drivers/tty/vt/vt.c | 29 ++++++++++++++---------------
 1 file changed, 14 insertions(+), 15 deletions(-)

diff --git a/drivers/tty/vt/vt.c b/drivers/tty/vt/vt.c
index 2ebaba16f785..ca55004a639e 100644
--- a/drivers/tty/vt/vt.c
+++ b/drivers/tty/vt/vt.c
@@ -102,6 +102,7 @@
 #include <linux/uaccess.h>
 #include <linux/kdb.h>
 #include <linux/ctype.h>
+#include <linux/bsearch.h>
 
 #define MAX_NR_CON_DRIVER 16
 
@@ -2142,22 +2143,15 @@ struct interval {
 	uint32_t last;
 };
 
-static int bisearch(uint32_t ucs, const struct interval *table, int max)
+static int ucs_cmp(const void *key, const void *elt)
 {
-	int min = 0;
-	int mid;
+	uint32_t ucs = *(uint32_t *)key;
+	struct interval e = *(struct interval *) elt;
 
-	if (ucs < table[0].first || ucs > table[max].last)
-		return 0;
-	while (max >= min) {
-		mid = (min + max) / 2;
-		if (ucs > table[mid].last)
-			min = mid + 1;
-		else if (ucs < table[mid].first)
-			max = mid - 1;
-		else
-			return 1;
-	}
+	if (ucs > e.last)
+		return 1;
+	else if (ucs < e.first)
+		return -1;
 	return 0;
 }
 
@@ -2169,7 +2163,12 @@ static int is_double_width(uint32_t ucs)
 		{ 0xFE10, 0xFE19 }, { 0xFE30, 0xFE6F }, { 0xFF00, 0xFF60 },
 		{ 0xFFE0, 0xFFE6 }, { 0x20000, 0x2FFFD }, { 0x30000, 0x3FFFD }
 	};
-	return bisearch(ucs, double_width, ARRAY_SIZE(double_width) - 1);
+	if (ucs < double_width[0].first ||
+	    ucs > double_width[ARRAY_SIZE(double_width) - 1].last)
+		return 0;
+
+	return bsearch(&ucs, double_width, ARRAY_SIZE(double_width),
+			sizeof(struct interval), ucs_cmp) != NULL;
 }
 
 static void con_flush(struct vc_data *vc, unsigned long draw_from,
-- 
2.11.0