Re: [RFC PATCH] Prio_heap: heap_remove(), heap_maximum(), heap_replace() and heap_cherrypick()

[Balbir Singh <balbir@linux.vnet.ibm.com>]

* Mathieu Desnoyers <mathieu.desnoyers@efficios.com> [2010-10-06 14:03:23]:

> 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@efficios.com>
> Cc: Paul Menage <menage@google.com>
> Cc: David Rientjes <rientjes@google.com>
> Cc: Nick Piggin <nickpiggin@yahoo.com.au>
> Cc: Balbir Singh <balbir@in.ibm.com>
> Cc: Cedric Le Goater <clg@fr.ibm.com>
> Cc: "Eric W. Biederman" <ebiederm@xmission.com>
> Cc: Andrew Morton <akpm@linux-foundation.org>
> Cc: Linus Torvalds <torvalds@linux-foundation.org>
> ---

The patchset looks good to me, one comment on cherry picking below

Acked-by: Balbir Singh <balbir@linux.vnet.ibm.com>
 

>  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);

One way to reduce cherrypick'ing in O(n) if n is large, is to sort the
entire heap using heapify() and then doing a binary search. The cost
of sorting is high, so it depends on how often and in what phases we
cherry pick.

-- 
	Three Cheers,
	Balbir