lkml.org 
[lkml]   [2019]   [Nov]   [17]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
SubjectRe: [PATCH v3 02/10] lib: introduce generic min max heap
From
Date
On Wed, 2019-11-13 at 16:30 -0800, Ian Rogers wrote:
> Based-on-work-by: Peter Zijlstra (Intel) <peterz@infradead.org>

Perhaps some functions are a bit large for inline
and perhaps the function names are too generic?

> diff --git a/include/linux/min_max_heap.h b/include/linux/min_max_heap.h
[]
> +/* Sift the element at pos down the heap. */
> +static inline void heapify(struct min_max_heap *heap, int pos,
> + const struct min_max_heap_callbacks *func) {
> + void *left_child, *right_child, *parent, *large_or_smallest;
> + char *data = (char *)heap->data;

The kernel already depends on void * arithmetic so it
seems char *data could just as well be void *data and
it might be more readable without the temporary at all.

> +
> + 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;
> +
> + 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;
> + }
> +}

[]

> +static void heap_pop_push(struct min_max_heap *heap,
> + const void *element,
> + const struct min_max_heap_callbacks *func)
> +{
> + char *data = (char *)heap->data;
> +
> + memcpy(data, element, func->elem_size);
> + heapify(heap, 0, func);
> +}

missing inline.

> +
> +/* Push an element on to the heap, O(log2(size)). */
> +static inline void
> +heap_push(struct min_max_heap *heap, const void *element,
> + const struct min_max_heap_callbacks *func)
> +{
> + void *child, *parent;
> + int pos;
> + char *data = (char *)heap->data;

Same comment about char * vs void * and unnecessary temporary.

> +
> + if (WARN_ONCE(heap->size >= heap->cap, "Pushing on a full heap"))
> + return;
> +
> + /* Place at the end of data. */
> + pos = heap->size;
> + memcpy(data + (pos * func->elem_size), element, func->elem_size);
> + heap->size++;
> +
> + /* Sift up. */
> + for (; pos > 0; pos = (pos - 1) / 2) {
> + child = data + (pos * func->elem_size);
> + parent = data + ((pos - 1) / 2) * func->elem_size;
> + if (func->cmp(parent, child))
> + break;
> + func->swp(parent, child);
> + }
> +}
> +
> +#endif /* _LINUX_MIN_MAX_HEAP_H */


\
 
 \ /
  Last update: 2019-11-17 19:29    [W:0.362 / U:5.776 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site