* [rfc, PATCH v1 1/1] min_heap: Make use of cmp_func_t and swap_func_t types
@ 2023-08-17 17:06 Andy Shevchenko
2023-08-17 17:51 ` Ian Rogers
0 siblings, 1 reply; 2+ messages in thread
From: Andy Shevchenko @ 2023-08-17 17:06 UTC (permalink / raw)
To: Andy Shevchenko, Peter Zijlstra, linux-kernel, linux-perf-users
Cc: Ingo Molnar, Arnaldo Carvalho de Melo, Mark Rutland,
Alexander Shishkin, Jiri Olsa, Namhyung Kim, Ian Rogers,
Adrian Hunter
The types.h defines standard types for comparator and swap functions.
Convert min_heap to use it.
Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
---
include/linux/min_heap.h | 8 ++++----
kernel/events/core.c | 4 ++--
lib/test_min_heap.c | 6 +++---
3 files changed, 9 insertions(+), 9 deletions(-)
diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h
index 44077837385f..14da37caa235 100644
--- a/include/linux/min_heap.h
+++ b/include/linux/min_heap.h
@@ -26,8 +26,8 @@ struct min_heap {
*/
struct min_heap_callbacks {
int elem_size;
- bool (*less)(const void *lhs, const void *rhs);
- void (*swp)(void *lhs, void *rhs);
+ cmp_func_t less;
+ swap_func_t swp;
};
/* Sift the element at pos down the heap. */
@@ -55,7 +55,7 @@ void min_heapify(struct min_heap *heap, int pos,
}
if (smallest == parent)
break;
- func->swp(smallest, parent);
+ func->swp(smallest, parent, func->elem_size);
if (smallest == left)
pos = (pos * 2) + 1;
else
@@ -127,7 +127,7 @@ void min_heap_push(struct min_heap *heap, const void *element,
parent = data + ((pos - 1) / 2) * func->elem_size;
if (func->less(parent, child))
break;
- func->swp(parent, child);
+ func->swp(parent, child, func->elem_size);
}
}
diff --git a/kernel/events/core.c b/kernel/events/core.c
index 4c72a41f11af..fa344b916290 100644
--- a/kernel/events/core.c
+++ b/kernel/events/core.c
@@ -3639,7 +3639,7 @@ void __perf_event_task_sched_out(struct task_struct *task,
perf_cgroup_switch(next);
}
-static bool perf_less_group_idx(const void *l, const void *r)
+static int perf_less_group_idx(const void *l, const void *r)
{
const struct perf_event *le = *(const struct perf_event **)l;
const struct perf_event *re = *(const struct perf_event **)r;
@@ -3647,7 +3647,7 @@ static bool perf_less_group_idx(const void *l, const void *r)
return le->group_index < re->group_index;
}
-static void swap_ptr(void *l, void *r)
+static void swap_ptr(void *l, void *r, int size)
{
void **lp = l, **rp = r;
diff --git a/lib/test_min_heap.c b/lib/test_min_heap.c
index 7b01b4387cfb..63d0b2f6c060 100644
--- a/lib/test_min_heap.c
+++ b/lib/test_min_heap.c
@@ -11,17 +11,17 @@
#include <linux/printk.h>
#include <linux/random.h>
-static __init bool less_than(const void *lhs, const void *rhs)
+static __init int less_than(const void *lhs, const void *rhs)
{
return *(int *)lhs < *(int *)rhs;
}
-static __init bool greater_than(const void *lhs, const void *rhs)
+static __init int greater_than(const void *lhs, const void *rhs)
{
return *(int *)lhs > *(int *)rhs;
}
-static __init void swap_ints(void *lhs, void *rhs)
+static __init void swap_ints(void *lhs, void *rhs, int size)
{
int temp = *(int *)lhs;
--
2.40.0.1.gaa8946217a0b
^ permalink raw reply [flat|nested] 2+ messages in thread* Re: [rfc, PATCH v1 1/1] min_heap: Make use of cmp_func_t and swap_func_t types
2023-08-17 17:06 [rfc, PATCH v1 1/1] min_heap: Make use of cmp_func_t and swap_func_t types Andy Shevchenko
@ 2023-08-17 17:51 ` Ian Rogers
0 siblings, 0 replies; 2+ messages in thread
From: Ian Rogers @ 2023-08-17 17:51 UTC (permalink / raw)
To: Andy Shevchenko
Cc: Peter Zijlstra, linux-kernel, linux-perf-users, Ingo Molnar,
Arnaldo Carvalho de Melo, Mark Rutland, Alexander Shishkin,
Jiri Olsa, Namhyung Kim, Adrian Hunter
On Thu, Aug 17, 2023 at 10:09 AM Andy Shevchenko
<andriy.shevchenko@linux.intel.com> wrote:
>
> The types.h defines standard types for comparator and swap functions.
> Convert min_heap to use it.
>
> Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
> ---
> include/linux/min_heap.h | 8 ++++----
> kernel/events/core.c | 4 ++--
> lib/test_min_heap.c | 6 +++---
> 3 files changed, 9 insertions(+), 9 deletions(-)
>
> diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h
> index 44077837385f..14da37caa235 100644
> --- a/include/linux/min_heap.h
> +++ b/include/linux/min_heap.h
> @@ -26,8 +26,8 @@ struct min_heap {
> */
> struct min_heap_callbacks {
> int elem_size;
> - bool (*less)(const void *lhs, const void *rhs);
> - void (*swp)(void *lhs, void *rhs);
> + cmp_func_t less;
This looks wrong. A cmp_func_t will return -1, for less-than, 0 for
equal, +1 for greater-than whilst the less function here is just
providing less-than as true/false. This is done to avoid common
pitfalls around minimum integer.
> + swap_func_t swp;
Why pass a size argument when we're specifying the swap function to use anyway?
Thanks,
Ian
> };
>
> /* Sift the element at pos down the heap. */
> @@ -55,7 +55,7 @@ void min_heapify(struct min_heap *heap, int pos,
> }
> if (smallest == parent)
> break;
> - func->swp(smallest, parent);
> + func->swp(smallest, parent, func->elem_size);
> if (smallest == left)
> pos = (pos * 2) + 1;
> else
> @@ -127,7 +127,7 @@ void min_heap_push(struct min_heap *heap, const void *element,
> parent = data + ((pos - 1) / 2) * func->elem_size;
> if (func->less(parent, child))
> break;
> - func->swp(parent, child);
> + func->swp(parent, child, func->elem_size);
> }
> }
>
> diff --git a/kernel/events/core.c b/kernel/events/core.c
> index 4c72a41f11af..fa344b916290 100644
> --- a/kernel/events/core.c
> +++ b/kernel/events/core.c
> @@ -3639,7 +3639,7 @@ void __perf_event_task_sched_out(struct task_struct *task,
> perf_cgroup_switch(next);
> }
>
> -static bool perf_less_group_idx(const void *l, const void *r)
> +static int perf_less_group_idx(const void *l, const void *r)
> {
> const struct perf_event *le = *(const struct perf_event **)l;
> const struct perf_event *re = *(const struct perf_event **)r;
> @@ -3647,7 +3647,7 @@ static bool perf_less_group_idx(const void *l, const void *r)
> return le->group_index < re->group_index;
> }
>
> -static void swap_ptr(void *l, void *r)
> +static void swap_ptr(void *l, void *r, int size)
> {
> void **lp = l, **rp = r;
>
> diff --git a/lib/test_min_heap.c b/lib/test_min_heap.c
> index 7b01b4387cfb..63d0b2f6c060 100644
> --- a/lib/test_min_heap.c
> +++ b/lib/test_min_heap.c
> @@ -11,17 +11,17 @@
> #include <linux/printk.h>
> #include <linux/random.h>
>
> -static __init bool less_than(const void *lhs, const void *rhs)
> +static __init int less_than(const void *lhs, const void *rhs)
> {
> return *(int *)lhs < *(int *)rhs;
> }
>
> -static __init bool greater_than(const void *lhs, const void *rhs)
> +static __init int greater_than(const void *lhs, const void *rhs)
> {
> return *(int *)lhs > *(int *)rhs;
> }
>
> -static __init void swap_ints(void *lhs, void *rhs)
> +static __init void swap_ints(void *lhs, void *rhs, int size)
> {
> int temp = *(int *)lhs;
>
> --
> 2.40.0.1.gaa8946217a0b
>
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2023-08-17 17:52 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-08-17 17:06 [rfc, PATCH v1 1/1] min_heap: Make use of cmp_func_t and swap_func_t types Andy Shevchenko
2023-08-17 17:51 ` Ian Rogers
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®