Messages in this thread | | | Date | Mon, 17 Feb 2020 17:29:19 +0100 | From | Peter Zijlstra <> | Subject | Re: [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(..);
| |