Re: [PATCH v6 2/6] lib: introduce generic min-heap

[Peter Zijlstra]

On Thu, Feb 13, 2020 at 11:51:29PM -0800, Ian Rogers wrote:
> Supports push, pop and converting an array into a heap. If the sense of
> the compare function is inverted then it can provide a max-heap.

+whitespace

> Based-on-work-by: Peter Zijlstra (Intel) <peterz@xxxxxxxxxxxxx>
> 
-whitespace

> Signed-off-by: Ian Rogers <irogers@xxxxxxxxxx>
> ---
>  include/linux/min_heap.h | 135 +++++++++++++++++++++++++++
>  lib/Kconfig.debug        |  10 ++
>  lib/Makefile             |   1 +
>  lib/test_min_heap.c      | 194 +++++++++++++++++++++++++++++++++++++++
>  4 files changed, 340 insertions(+)
>  create mode 100644 include/linux/min_heap.h
>  create mode 100644 lib/test_min_heap.c
> 
> diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h
> new file mode 100644
> index 000000000000..0f04f49c0779
> --- /dev/null
> +++ b/include/linux/min_heap.h
> @@ -0,0 +1,135 @@
> +/* SPDX-License-Identifier: GPL-2.0 */
> +#ifndef _LINUX_MIN_HEAP_H
> +#define _LINUX_MIN_HEAP_H
> +
> +#include <linux/bug.h>
> +#include <linux/string.h>
> +#include <linux/types.h>
> +
> +/**
> + * struct min_heap - Data structure to hold a min-heap.
> + * @data: Start of array holding the heap elements.
> + * @size: Number of elements currently in the heap.
> + * @cap: Maximum number of elements that can be held in current storage.
> + */
> +struct min_heap {
> +	void *data;
> +	int size;
> +	int cap;
> +};
> +
> +/**
> + * struct min_heap_callbacks - Data/functions to customise the min_heap.
> + * @elem_size: The size of each element in bytes.
> + * @cmp: Partial order function for this heap 'less'/'<' for min-heap,
> + *       'greater'/'>' for max-heap.

Since the thing is now called min_heap, 's/cmp/less/g'. cmp in C is a
-1,0,1 like thing.

> + * @swp: Swap elements function.
> + */
> +struct min_heap_callbacks {
> +	int elem_size;
> +	bool (*cmp)(const void *lhs, const void *rhs);
> +	void (*swp)(void *lhs, void *rhs);
> +};
> +
> +/* Sift the element at pos down the heap. */
> +static __always_inline
> +void min_heapify(struct min_heap *heap, int pos,
> +		const struct min_heap_callbacks *func)
> +{
> +	void *left_child, *right_child, *parent, *large_or_smallest;

's/large_or_smallest/smallest/g' ?

> +	u8 *data = (u8 *)heap->data;

void * has byte sized arithmetic

> +
> +	for (;;) {
> +		if (pos * 2 + 1 >= heap->size)
> +			break;
> +
> +		left_child = data + ((pos * 2 + 1) * func->elem_size);
> +		parent = data + (pos * func->elem_size);

> +		large_or_smallest = parent;
> +		if (func->cmp(left_child, large_or_smallest))
> +			large_or_smallest = left_child;

		smallest = parent;
		if (func->less(left_child, smallest);
			smallest = left_child;

Makes sense, no?

> +
> +		if (pos * 2 + 2 < heap->size) {
> +			right_child = data + ((pos * 2 + 2) * func->elem_size);
> +			if (func->cmp(right_child, large_or_smallest))
> +				large_or_smallest = right_child;
> +		}
> +		if (large_or_smallest == parent)
> +			break;
> +		func->swp(large_or_smallest, parent);
> +		if (large_or_smallest == left_child)
> +			pos = (pos * 2) + 1;
> +		else
> +			pos = (pos * 2) + 2;

> +/*
> + * Remove the minimum element and then push the given element. The
> + * implementation performs 1 sift (O(log2(size))) and is therefore more
> + * efficient than a pop followed by a push that does 2.
> + */
> +static __always_inline
> +void min_heap_pop_push(struct min_heap *heap,
> +		const void *element,
> +		const struct min_heap_callbacks *func)
> +{
> +	memcpy(heap->data, element, func->elem_size);
> +	min_heapify(heap, 0, func);
> +}

I still think this is a mightly weird primitive. I think I simply did:

	*evt = perf_event_group(next);
	if (*evt)
		min_heapify(..);