Messages in this thread | | | From | Ian Rogers <> | Date | Thu, 17 Aug 2023 10:51:04 -0700 | Subject | Re: [rfc, PATCH v1 1/1] min_heap: Make use of cmp_func_t and swap_func_t types |
| |
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 >
| |