[PATCH v3 0/4] new macro: find_closest()

[PATCH v3 0/4] new macro: find_closest()

[Bartosz Golaszewski]

This series proposes to unduplicate the code used to find the
member in an array closest to 'x'.

The first patch adds a macro implementing the algorithm in two
flavors - for arrays sorted in ascending and descending order.
Other three patches replace duplicated code with calls to one
of these macros in some hwmon drivers.

v3:
- don't add find_closest() to kernel.h - instead create a new include
  for helper macros
- don't remove RANGE_TO_REG() and FREQ_TO_REG(), but replace their
  contents with find_closest() expansions
- use kernel-docs to document new macros
- rename find_closest_desc() to find_closest_descending()

v2:
https://lkml.org/lkml/2015/3/10/582

v1:
https://lkml.org/lkml/2015/2/24/509

Bartosz Golaszewski (4):
  util_macros.h: add find_closest() macro
  hwmon: (ina2xx) replace ina226_avg_bits() with find_closest()
  hwmon: (lm85) use find_closest() in x_TO_REG() functions
  hwmon: (w83795) use find_closest_descending() in pwm_freq_to_reg()

 drivers/hwmon/ina2xx.c      | 17 +++--------------
 drivers/hwmon/lm85.c        | 26 ++++++++------------------
 drivers/hwmon/w83795.c      |  8 +++-----
 include/linux/util_macros.h | 39 +++++++++++++++++++++++++++++++++++++++
 4 files changed, 53 insertions(+), 37 deletions(-)
 create mode 100644 include/linux/util_macros.h

-- 
2.1.4

[PATCH v3 1/4] util_macros.h: add find_closest() macro

[Bartosz Golaszewski]

Searching for the member of an array closest to 'x' is
duplicated in several places.

Add a new include - util_macros.h - and two macros that
implement this algorithm for arrays sorted both in ascending
and descending order.

Signed-off-by: Bartosz Golaszewski <bgolaszewski@baylibre.com>
---
 include/linux/util_macros.h | 39 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 39 insertions(+)
 create mode 100644 include/linux/util_macros.h

diff --git a/include/linux/util_macros.h b/include/linux/util_macros.h
new file mode 100644
index 0000000..f2097ce
--- /dev/null
+++ b/include/linux/util_macros.h
@@ -0,0 +1,39 @@
+#ifndef _LINUX_HELPER_MACROS_H_
+#define _LINUX_HELPER_MACROS_H_
+
+#define __find_closest(x, a, as, op)(					\
+{									\
+	typeof(as) _i, _as = (as) - 1;					\
+	typeof(x) _x = (x);						\
+	typeof(*a) *_a = (a);						\
+	for (_i = 0; _i < _as; _i++) {					\
+		if (_x op DIV_ROUND_CLOSEST(_a[_i] + _a[_i + 1], 2))	\
+			break;						\
+	}								\
+	(_i);								\
+})
+
+/*
+ * find_closest - locate the closest element in a sorted array
+ * @x: The reference value.
+ * @a: The array in which to look for the closest element. Must be sorted
+ *  in ascending order.
+ * @as: Size of 'a'.
+ *
+ * Returns the index of the element closest to 'x'.
+ */
+#define find_closest(x, a, as) __find_closest(x, a, as, <=)
+
+/*
+ * find_closest_descending - locate the closest element in a sorted array
+ * @x: The reference value.
+ * @a: The array in which to look for the closest element. Must be sorted
+ *  in descending order.
+ * @as: Size of 'a'.
+ *
+ * Similar to get_closest() but 'a' is expected to be sorted in descending
+ * order.
+ */
+#define find_closest_descending(x, a, as) __find_closest(x, a, as, >)
+
+#endif
-- 
2.1.4

Re: [PATCH v3 1/4] util_macros.h: add find_closest() macro

[Joe Perches]

On Thu, 2015-03-19 at 15:30 +0100, Bartosz Golaszewski wrote:
> Searching for the member of an array closest to 'x' is
> duplicated in several places.
[]
> diff --git a/include/linux/util_macros.h b/include/linux/util_macros.h
[]
> @@ -0,0 +1,39 @@
> +#ifndef _LINUX_HELPER_MACROS_H_
> +#define _LINUX_HELPER_MACROS_H_
> +
> +#define __find_closest(x, a, as, op)(					\
> +{									\
> +	typeof(as) _i, _as = (as) - 1;					\
> +	typeof(x) _x = (x);						\
> +	typeof(*a) *_a = (a);						\
> +	for (_i = 0; _i < _as; _i++) {					\
> +		if (_x op DIV_ROUND_CLOSEST(_a[_i] + _a[_i + 1], 2))	\
> +			break;						\
> +	}								\
> +	(_i);								\
> +})

Please use consistent statement expression start/top whitespace.

> +
> +/*

This should be /** for proper kernel-doc style

> + * find_closest - locate the closest element in a sorted array
> + * @x: The reference value.
> + * @a: The array in which to look for the closest element. Must be sorted
> + *  in ascending order.
> + * @as: Size of 'a'.
> + *
> + * Returns the index of the element closest to 'x'.
> + */
> +#define find_closest(x, a, as) __find_closest(x, a, as, <=)
> +
> +/*
> + * find_closest_descending - locate the closest element in a sorted array
> + * @x: The reference value.
> + * @a: The array in which to look for the closest element. Must be sorted
> + *  in descending order.
> + * @as: Size of 'a'.
> + *
> + * Similar to get_closest() but 'a' is expected to be sorted in descending
> + * order.
> + */
> +#define find_closest_descending(x, a, as) __find_closest(x, a, as, >)

Again, why is this > not >= ?

Re: [PATCH v3 1/4] util_macros.h: add find_closest() macro

[Bartosz Golaszewski]

2015-03-19 16:15 GMT+01:00 Joe Perches <joe@perches.com>:
> On Thu, 2015-03-19 at 15:30 +0100, Bartosz Golaszewski wrote:
>> Searching for the member of an array closest to 'x' is
>> duplicated in several places.
> []
>> diff --git a/include/linux/util_macros.h b/include/linux/util_macros.h
> []
>> @@ -0,0 +1,39 @@
>> +#ifndef _LINUX_HELPER_MACROS_H_
>> +#define _LINUX_HELPER_MACROS_H_
>> +
>> +#define __find_closest(x, a, as, op)(                                        \
>> +{                                                                    \
>> +     typeof(as) _i, _as = (as) - 1;                                  \
>> +     typeof(x) _x = (x);                                             \
>> +     typeof(*a) *_a = (a);                                           \
>> +     for (_i = 0; _i < _as; _i++) {                                  \
>> +             if (_x op DIV_ROUND_CLOSEST(_a[_i] + _a[_i + 1], 2))    \
>> +                     break;                                          \
>> +     }                                                               \
>> +     (_i);                                                           \
>> +})
>
> Please use consistent statement expression start/top whitespace.
>
>> +
>> +/*
>
> This should be /** for proper kernel-doc style
>
>> + * find_closest - locate the closest element in a sorted array
>> + * @x: The reference value.
>> + * @a: The array in which to look for the closest element. Must be sorted
>> + *  in ascending order.
>> + * @as: Size of 'a'.
>> + *
>> + * Returns the index of the element closest to 'x'.
>> + */
>> +#define find_closest(x, a, as) __find_closest(x, a, as, <=)
>> +
>> +/*
>> + * find_closest_descending - locate the closest element in a sorted array
>> + * @x: The reference value.
>> + * @a: The array in which to look for the closest element. Must be sorted
>> + *  in descending order.
>> + * @as: Size of 'a'.
>> + *
>> + * Similar to get_closest() but 'a' is expected to be sorted in descending
>> + * order.
>> + */
>> +#define find_closest_descending(x, a, as) __find_closest(x, a, as, >)
>
> Again, why is this > not >= ?

Hi Joe,

sorry I missed your comment last time. You're right of course. My
reasoning was this: the only caller of find_closest_descending()
(w83795) used '>' previously, so let's stay compatible. After giving
it some testing thought, it turned out that when using '>' the value
closest to 2 in pwm_freq_cksel0 is... 1. I'll fix that in the next
iteration.

Best regards,
Bartosz Golaszewski

Re: [PATCH v3 1/4] util_macros.h: add find_closest() macro

[Steven Rostedt]

BTW, it's best to email this account and not my Red Hat one.


On Thu, 19 Mar 2015 11:53:06 -0400
Bartosz Golaszewski <bgolaszewski@baylibre.com> wrote:

> Searching for the member of an array closest to 'x' is
> duplicated in several places.
> 
> Add a new include - util_macros.h - and two macros that
> implement this algorithm for arrays sorted both in ascending
> and descending order.
> 
> Signed-off-by: Bartosz Golaszewski <bgolaszewski@baylibre.com>
> ---
>  include/linux/util_macros.h | 39 +++++++++++++++++++++++++++++++++++++++
>  1 file changed, 39 insertions(+)
>  create mode 100644 include/linux/util_macros.h
> 
> diff --git a/include/linux/util_macros.h b/include/linux/util_macros.h
> new file mode 100644
> index 0000000..f2097ce
> --- /dev/null
> +++ b/include/linux/util_macros.h
> @@ -0,0 +1,39 @@
> +#ifndef _LINUX_HELPER_MACROS_H_
> +#define _LINUX_HELPER_MACROS_H_
> +
> +#define __find_closest(x, a, as, op)(					\
> +{									\
> +	typeof(as) _i, _as = (as) - 1;					\
> +	typeof(x) _x = (x);						\
> +	typeof(*a) *_a = (a);						\

The above variables are not very unique. I've been thinking about all
the variables that are defined in macros, and we may want to establish
some kind of naming convention to keep from having name space
collisions.

Maybe something like...

	typeof(as) __fc_i_, __fc_a_ = (as) -1;
	typeof(__fc_x_) = (x);
	typeof(*a) *__fc_a_ = (a);

-- Steve


> +	for (_i = 0; _i < _as; _i++) {					\
> +		if (_x op DIV_ROUND_CLOSEST(_a[_i] + _a[_i + 1], 2))	\
> +			break;						\
> +	}								\
> +	(_i);								\
> +})

Re: [PATCH v3 1/4] util_macros.h: add find_closest() macro

[Bartosz Golaszewski]

2015-03-19 17:03 GMT+01:00 Steven Rostedt <rostedt@goodmis.org>:
>
> The above variables are not very unique. I've been thinking about all
> the variables that are defined in macros, and we may want to establish
> some kind of naming convention to keep from having name space
> collisions.
>
> Maybe something like...
>
>         typeof(as) __fc_i_, __fc_a_ = (as) -1;
>         typeof(__fc_x_) = (x);
>         typeof(*a) *__fc_a_ = (a);
>
> -- Steve

Definitely a good idea - it should probably be added to section 12 of
the CodingStyle doc. What does 'fc' stand for?

Bart

Re: [PATCH v3 1/4] util_macros.h: add find_closest() macro

[Steven Rostedt]

On Thu, 19 Mar 2015 17:28:47 +0100
Bartosz Golaszewski <bgolaszewski@baylibre.com> wrote:


> Definitely a good idea - it should probably be added to section 12 of
> the CodingStyle doc. What does 'fc' stand for?

fc == "find_closest" ;-)

-- Steve

Re: [PATCH v3 1/4] util_macros.h: add find_closest() macro

[Steven Rostedt]

On Thu, 19 Mar 2015 12:32:24 -0400
Steven Rostedt <rostedt@goodmis.org> wrote:

> On Thu, 19 Mar 2015 17:28:47 +0100
> Bartosz Golaszewski <bgolaszewski@baylibre.com> wrote:
> 
> 
> > Definitely a good idea - it should probably be added to section 12 of
> > the CodingStyle doc. What does 'fc' stand for?
> 
> fc == "find_closest" ;-)
> 

I originally was going to suggest "__find_closest_<var>_" but then it
got a bit messy. But maybe that would be better, as it make it even
more likely not to have name collisions.

-- Steve

Re: [PATCH v3 1/4] util_macros.h: add find_closest() macro

[Bartosz Golaszewski]

2015-03-19 17:33 GMT+01:00 Steven Rostedt <rostedt@goodmis.org>:
> On Thu, 19 Mar 2015 12:32:24 -0400
> Steven Rostedt <rostedt@goodmis.org> wrote:
>
>> On Thu, 19 Mar 2015 17:28:47 +0100
>> Bartosz Golaszewski <bgolaszewski@baylibre.com> wrote:
>>
>>
>> > Definitely a good idea - it should probably be added to section 12 of
>> > the CodingStyle doc. What does 'fc' stand for?
>>
>> fc == "find_closest" ;-)
>>
>
> I originally was going to suggest "__find_closest_<var>_" but then it
> got a bit messy. But maybe that would be better, as it make it even
> more likely not to have name collisions.
>

I think __fc_<var> is enough. With variable names that long it's no
longer readable.

Bart

Re: [PATCH v3 1/4] util_macros.h: add find_closest() macro

[Bartosz Golaszewski]

2015-03-19 17:32 GMT+01:00 Steven Rostedt <rostedt@goodmis.org>:
>
>> Definitely a good idea - it should probably be added to section 12 of
>> the CodingStyle doc. What does 'fc' stand for?
>
> fc == "find_closest" ;-)

Alright, I thought you proposed some global naming convention with fc
standing for something like 'function context'. :)

Bart

[PATCH v3 2/4] hwmon: (ina2xx) replace ina226_avg_bits() with find_closest()

[Bartosz Golaszewski]

Use find_closest() to locate the closest average in ina226_avg_tab.

Signed-off-by: Bartosz Golaszewski <bgolaszewski@baylibre.com>
---
 drivers/hwmon/ina2xx.c | 17 +++--------------
 1 file changed, 3 insertions(+), 14 deletions(-)

diff --git a/drivers/hwmon/ina2xx.c b/drivers/hwmon/ina2xx.c
index d1542b7..4d28150 100644
--- a/drivers/hwmon/ina2xx.c
+++ b/drivers/hwmon/ina2xx.c
@@ -36,6 +36,7 @@
 #include <linux/jiffies.h>
 #include <linux/of.h>
 #include <linux/delay.h>
+#include <linux/util_macros.h>
 
 #include <linux/platform_data/ina2xx.h>
 
@@ -141,19 +142,6 @@ static const struct ina2xx_config ina2xx_config[] = {
  */
 static const int ina226_avg_tab[] = { 1, 4, 16, 64, 128, 256, 512, 1024 };
 
-static int ina226_avg_bits(int avg)
-{
-	int i;
-
-	/* Get the closest average from the tab. */
-	for (i = 0; i < ARRAY_SIZE(ina226_avg_tab) - 1; i++) {
-		if (avg <= (ina226_avg_tab[i] + ina226_avg_tab[i + 1]) / 2)
-			break;
-	}
-
-	return i; /* Return 0b0111 for values greater than 1024. */
-}
-
 static int ina226_reg_to_interval(u16 config)
 {
 	int avg = ina226_avg_tab[INA226_READ_AVG(config)];
@@ -171,7 +159,8 @@ static u16 ina226_interval_to_reg(int interval, u16 config)
 
 	avg = DIV_ROUND_CLOSEST(interval * 1000,
 				INA226_TOTAL_CONV_TIME_DEFAULT);
-	avg_bits = ina226_avg_bits(avg);
+	avg_bits = find_closest(avg, ina226_avg_tab,
+				ARRAY_SIZE(ina226_avg_tab));
 
 	return (config & ~INA226_AVG_RD_MASK) | INA226_SHIFT_AVG(avg_bits);
 }
-- 
2.1.4

[PATCH v3 3/4] hwmon: (lm85) use find_closest() in x_TO_REG() functions

[Bartosz Golaszewski]

Replace RANGE_TO_REG() and FREQ_TO_REG() implementations with
calls to find_closest().

Signed-off-by: Bartosz Golaszewski <bgolaszewski@baylibre.com>
---
 drivers/hwmon/lm85.c | 26 ++++++++------------------
 1 file changed, 8 insertions(+), 18 deletions(-)

diff --git a/drivers/hwmon/lm85.c b/drivers/hwmon/lm85.c
index 2b4b419..6ff773f 100644
--- a/drivers/hwmon/lm85.c
+++ b/drivers/hwmon/lm85.c
@@ -34,6 +34,7 @@
 #include <linux/hwmon-sysfs.h>
 #include <linux/err.h>
 #include <linux/mutex.h>
+#include <linux/util_macros.h>
 
 /* Addresses to scan */
 static const unsigned short normal_i2c[] = { 0x2c, 0x2d, 0x2e, I2C_CLIENT_END };
@@ -190,15 +191,7 @@ static const int lm85_range_map[] = {
 
 static int RANGE_TO_REG(long range)
 {
-	int i;
-
-	/* Find the closest match */
-	for (i = 0; i < 15; ++i) {
-		if (range <= (lm85_range_map[i] + lm85_range_map[i + 1]) / 2)
-			break;
-	}
-
-	return i;
+	return find_closest(range, lm85_range_map, ARRAY_SIZE(lm85_range_map));
 }
 #define RANGE_FROM_REG(val)	lm85_range_map[(val) & 0x0f]
 
@@ -209,16 +202,12 @@ static const int lm85_freq_map[8] = { /* 1 Hz */
 static const int adm1027_freq_map[8] = { /* 1 Hz */
 	11, 15, 22, 29, 35, 44, 59, 88
 };
+#define FREQ_MAP_LEN	8
 
-static int FREQ_TO_REG(const int *map, unsigned long freq)
+static int FREQ_TO_REG(const int *map,
+		       unsigned int map_size, unsigned long freq)
 {
-	int i;
-
-	/* Find the closest match */
-	for (i = 0; i < 7; ++i)
-		if (freq <= (map[i] + map[i + 1]) / 2)
-			break;
-	return i;
+	return find_closest(freq, map, map_size);
 }
 
 static int FREQ_FROM_REG(const int *map, u8 reg)
@@ -828,7 +817,8 @@ static ssize_t set_pwm_freq(struct device *dev,
 		data->cfg5 &= ~ADT7468_HFPWM;
 		lm85_write_value(client, ADT7468_REG_CFG5, data->cfg5);
 	} else {					/* Low freq. mode */
-		data->pwm_freq[nr] = FREQ_TO_REG(data->freq_map, val);
+		data->pwm_freq[nr] = FREQ_TO_REG(data->freq_map,
+						 FREQ_MAP_LEN, val);
 		lm85_write_value(client, LM85_REG_AFAN_RANGE(nr),
 				 (data->zone[nr].range << 4)
 				 | data->pwm_freq[nr]);
-- 
2.1.4

[PATCH v3 4/4] hwmon: (w83795) use find_closest_descending() in pwm_freq_to_reg()

[Bartosz Golaszewski]

Replace the loop iterating over pwm_freq_cksel0 with a call to
find_closest_descending().

Signed-off-by: Bartosz Golaszewski <bgolaszewski@baylibre.com>
---
 drivers/hwmon/w83795.c | 8 +++-----
 1 file changed, 3 insertions(+), 5 deletions(-)

diff --git a/drivers/hwmon/w83795.c b/drivers/hwmon/w83795.c
index 2189413..49276bb 100644
--- a/drivers/hwmon/w83795.c
+++ b/drivers/hwmon/w83795.c
@@ -35,6 +35,7 @@
 #include <linux/err.h>
 #include <linux/mutex.h>
 #include <linux/jiffies.h>
+#include <linux/util_macros.h>
 
 /* Addresses to scan */
 static const unsigned short normal_i2c[] = {
@@ -308,11 +309,8 @@ static u8 pwm_freq_to_reg(unsigned long val, u16 clkin)
 	unsigned long best0, best1;
 
 	/* Best fit for cksel = 0 */
-	for (reg0 = 0; reg0 < ARRAY_SIZE(pwm_freq_cksel0) - 1; reg0++) {
-		if (val > (pwm_freq_cksel0[reg0] +
-			   pwm_freq_cksel0[reg0 + 1]) / 2)
-			break;
-	}
+	reg0 = find_closest_descending(val, pwm_freq_cksel0,
+				       ARRAY_SIZE(pwm_freq_cksel0));
 	if (val < 375)	/* cksel = 1 can't beat this */
 		return reg0;
 	best0 = pwm_freq_cksel0[reg0];
-- 
2.1.4