lkml.org 
[lkml]   [2020]   [Feb]   [17]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [PATCH v6 2/6] lib: introduce generic min-heap
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@infradead.org>
>
-whitespace

> Signed-off-by: Ian Rogers <irogers@google.com>
> ---
> 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(..);

\
 
 \ /
  Last update: 2020-02-17 17:30    [W:0.135 / U:2.224 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site