Re: [PATCH] Prio_heap: heap_remove(), heap_maximum(), heap_replace()and heap_cherrypick()
From: Paul Menage
Date: Fri Oct 08 2010 - 17:53:25 EST
On Thu, Oct 7, 2010 at 12:03 PM, Mathieu Desnoyers
<mathieu.desnoyers@xxxxxxxxxxxx> wrote:
> These added interfaces lets prio_heap users lookup the top of heap item without
> performing any insertion, perform removal of the topmost heap entry, and also
> replacement of topmost heap entry. This is useful if one need to use the result
> of the lookup to determine if the current maximum should simply be removed or if
> it should be replaced.
>
> This is used by the Generic Ring Buffer to perform timestamp-based fusion-merge
> of per-cpu buffer records into a single stream.
>
> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@xxxxxxxxxxxx>
Looks fine, other than a couple of suggestions to make the code
slightly clearer.
Acked-by: Paul Menage <menage@xxxxxxxxxx>
> Acked-by: Balbir Singh <balbir@xxxxxxxxxx>
> Cc: Paul Menage <menage@xxxxxxxxxx>
> Cc: David Rientjes <rientjes@xxxxxxxxxx>
> Cc: Cedric Le Goater <clg@xxxxxxxxxx>
> Cc: "Eric W. Biederman" <ebiederm@xxxxxxxxxxxx>
> Cc: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
> Cc: Linus Torvalds <torvalds@xxxxxxxxxxxxxxxxxxxx>
> ---
> include/linux/prio_heap.h | 44 ++++++++++++++++++++++
> lib/prio_heap.c | 91 ++++++++++++++++++++++++++++++++++++----------
> 2 files changed, 116 insertions(+), 19 deletions(-)
>
> Index: linux.trees.git/include/linux/prio_heap.h
> ===================================================================
> --- linux.trees.git.orig/include/linux/prio_heap.h 2010-07-06 14:25:29.000000000 -0400
> +++ linux.trees.git/include/linux/prio_heap.h 2010-07-07 10:04:33.000000000 -0400
> @@ -23,6 +23,18 @@ struct ptr_heap {
> };
>
> /**
> + * heap_maximum - return the largest element in the heap
> + * @heap: the heap to be operated on
> + *
> + * Returns the largest element in the heap, without performing any modification
> + * to the heap structure. Returns NULL if the heap is empty.
> + */
> +static inline void *heap_maximum(const struct ptr_heap *heap)
> +{
> + return heap->size ? heap->ptrs[0] : NULL;
> +}
> +
> +/**
> * heap_init - initialize an empty heap with a given memory size
> * @heap: the heap structure to be initialized
> * @size: amount of memory to use in bytes
> @@ -53,6 +65,38 @@ void heap_free(struct ptr_heap *heap);
> */
> extern void *heap_insert(struct ptr_heap *heap, void *p);
>
> +/**
> + * heap_remove - remove the largest element from the heap
> + * @heap: the heap to be operated on
> + *
> + * Returns the largest element in the heap. It removes this element from the
> + * heap. Returns NULL if the heap is empty.
> + */
> +extern void *heap_remove(struct ptr_heap *heap);
>
> +/**
> + * heap_cherrypick - remove a given element from the heap
> + * @heap: the heap to be operated on
> + * @p: the element
> + *
> + * Remove the given element from the heap. Return the element if present, else
> + * return NULL. This algorithm has a complexity of O(n), which is higher than
> + * O(log(n)) provided by the rest of this API.
> + */
> +extern void *heap_cherrypick(struct ptr_heap *heap, void *p);
> +
> +/**
> + * heap_replace_max - replace the the largest element from the heap
> + * @heap: the heap to be operated on
> + * @p: the pointer to be inserted as topmost element replacement
> + *
> + * Returns the largest element in the heap. It removes this element from the
> + * heap. The heap is rebalanced only once after the insertion. Returns NULL if
> + * the heap is empty.
> + *
> + * This is the equivalent of calling heap_remove() and then heap_insert(), but
> + * it only rebalances the heap once.
> + */
> +extern void *heap_replace_max(struct ptr_heap *heap, void *p);
>
> #endif /* _LINUX_PRIO_HEAP_H */
> Index: linux.trees.git/lib/prio_heap.c
> ===================================================================
> --- linux.trees.git.orig/lib/prio_heap.c 2010-07-06 14:25:29.000000000 -0400
> +++ linux.trees.git/lib/prio_heap.c 2010-07-07 10:18:32.000000000 -0400
> @@ -23,12 +23,49 @@ void heap_free(struct ptr_heap *heap)
> kfree(heap->ptrs);
> }
>
> -void *heap_insert(struct ptr_heap *heap, void *p)
> +static void heapify(struct ptr_heap *heap, void **ptrs, void *p, int pos)
I'd be inclined to not pass "ptrs" or "p" as an argument, and instead
get ptrs from heap->ptrs and p from ptrs[pos]. It makes it clearer
what heapify() is doing.
> +void *heap_replace_max(struct ptr_heap *heap, void *p)
> {
> void *res;
> void **ptrs = heap->ptrs;
> int pos;
No need for "pos" - just pass a constant 0 to heapify()
>
> + if (!heap->size) {
> + ptrs[heap->size++] = p;
Maybe make this clearer?
ptrs[0] = p;
heap->size = 1;
> +void *heap_remove(struct ptr_heap *heap)
> +{
> + void **ptrs = heap->ptrs;
> +
> + switch (heap->size) {
> + case 0:
> + return NULL;
> + case 1:
> + return ptrs[--heap->size];
Maybe clearer:
heap->size = 0;
return ptrs[0];
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/